（计算机应用技术专业论文）两相运动对象分割的分裂方法.pdf

a b s t r a c t o p t i c a lc o m p u t a t i o ni sw i d e l yu s e di nm a n yf i e l d s ，f o re x a m p l e ，c o m p u t e rv i s i o n , t h r e e d i m e n s i o n a lr e c o n s t r u c t i o na n ds oo n 1 1 l e r ea r em a n yw a y st oc a l c u l a t et h eo p t i c a l f l o wf i e l d ，t h ev a r i a t i o n a lm e t h o di sa l le f f e c t i v em e t h o dt oe a l c u l a t et h ed e n s eo p t i c a l f l o wf i e l d b u tt h ec a l c u l a t i o nc o s t sl o n gt i m ea n dt h ee 伍c i e n c yi sl o w a i m i n ga tt h em o d e i sw i t hr o b u s td a t at e r m sa n ds m o o t ht e r m si nt v n o t 2 l lv 撕a t i o n ) t y p e o no n eh a n d ，t h es p l i tm e t h o df o rh i g hc o m p u t a t i o ne f f i c i e n c yi sd e s i g n e d ，t h e o r i g i n a lm i n i m i z a t i o np r o b l e m sa r es p l i tt os o m es u b m i n i m i z a t i o np r o b l e m st h r o u g h i n t r o d u c i n ga u x i l i a r yv a r i a b l e sw h i c hc a nb ei m p l e m e n t e db ys o f tt h r e s h o l d i n gf o r m u l a s s h r i n k i n go p e r a t o r sa n dg a u s s s e i d e li t e r a t i o n s t h eo r i g i n a lv a r i a l i o nm e t h o da n dt h e s p l i tm e t h o da r ec o m p a r e df o rd a t at e r m sw i t hc o n s t a n ta s s u m p t i o no fi n t e n s i t y , g r a d i e n t ， h e s s i a nm a t r i x ，n o r mo fg r a d i e n t ，l a p l a c i a na n dd e t e r m i n a n to fh e s s i a nm a t r i x o nt h e o t h e rh a n d ，t h e s p l i tb r e g m a na l g o r i t h mi sd e s i g n e dt h r o u g hi n t r o d u c i n ga u x i l i a r y v a r i a b l e sa n di t e r a t i v ep a r a m e t e r sw h i c ha c h i e v et h ef a s to p t i c a lf l o wc a l c u l a t i o n ，a n dt h e s p l i tb r e g m a nm e t h o di sc o m p a r e dw i t ht h eo r i g i n a lv a r i a t i o nm e t h o d i nt h ep r o c e s s i n go fv i d e o ，t h em o t i o ns e g m e n t a t i o np l a y sa ni m p o r t a n tm e a n i n g a l t h o u g ht h eo r i g i n a lv a r i a t i o n a lm e t h o dt a i lb eu s e d 。i ti sn o ti m m e d i a t e t h i ss p l i t m e t h o di sa p p l i e dt ot h et w op h a s em o t i o ns e g m e n t a t i o nm o d e la n di sc o m p a r e dw i t ht h e o r i g i n a lv a r i a t i o n a lm e t h o d r e s u l t sp r o v et h a ts p l i tm e t h o di se f f e c t i v et oi m p r o v et h e s p e e do fc o m p u t a t i o n 1 1 1 er a p i ds p l i tm e t h o di ss t u d i e di na s p e c t so fo p t i c a lc o m p u t a t i o na n dt w op h a s e m o t i o ns e g m e n t a t i o n i tg e t ss o m ev a l u a b l er e s u l t s t h es p l i tm e t h o di ss t i l lap o t e n t i a l a r e ao fr e s e a r c h k e yw o r d s ：o p t i c a lf l o wc o m p u t a t i o n ；s p l i tm e t h o d ；s p l i tb r e g m a nm e t h o d ； t w op h a s e sm o t i o ns e g m e n t a t i o n 0叭78 3洲371洲y 目录 第一章绪论1 1 1 课题研究目的和意义1 1 2 国内外研究现状2 1 3 论文的主要工作3 第二章光流模型和水平集方法5 2 1 数据项模型5 2 2 光滑项模型8 2 3 水平集方法1 0 2 3 1 曲线演化理论1 0 2 3 2 水平集方法及初始化1 1 第三章基于多网格法的光流计算1 3 3 1 多网格法基本思想1 3 3 2 实验结果与分析1 4 3 3 本章小结1 5 第四章小位移变分光流计算的分裂方法1 7 4 1 分裂方法原理1 7 4 2 传统的直接变分方法1 8 4 3 基于g a u s s - s e i d e l 迭代的分裂方法1 9 4 3 1 公式推导及数值运算1 9 4 3 2 实验结果与分析2 4 4 4s p l i tb r e g m a n 方法2 7 4 4 1 公式推导及数值运算2 7 4 4 2 实验结果与分析2 9 4 5 本章小结3 2 第五章两相运动对象分割3 3 5 1 基于区域信息的分割模型3 3 5 2 水平集函数的区域划分3 7 5 3 两相运动对象分割模型3 7 5 4 两相运动对象分割模型的分裂方法3 8 5 5 实验结果与分析4 2 5 6 本章小结4 4 第六章总结与展望4 5 参考文献4 7 攻读学位期间的研究成果5 l 致谢5 2 学位论文独创性声明5 3 学位论文知识产权权属声明5 3 第一章绪论 1 1 课题研究目的和意义 第一章绪论 世界有静止的物体也有运动的对象，运动图像的处理是为了更好的研究现实世 界，因为动态图像给出了比静止图片更为丰富的信息，在运动图像处理中，重要的 研究内容就是观察者与运动对象之间的相对运动，通过认识和分析多帧图像序列， 可以获得相对运动的信息，这些运动信息通常是场景中运动对象的速度和方向，这 都是从单一静止图像中不可能得到的。 光流在计算机视觉、三维物体运动分析中有非常重要的作用，目前光流比较通 用的定义是：描述了空间运动场在二维平面上的投影，是运动物体像素运动的一个 瞬时速度，而像素点的运动由序列图像中像素强度随时间的变化来确定，因此将二 维图像平面上的某个坐标点灰度的变化作为光流矢量。虽然光流仅仅是空间场景中 物体真实运动的一个投影，但是在导航系统、汽车辅助驾驶、运动对象跟踪、人机 接口、视频压缩、图像配准、三维重建等多个领域有着重要的应用。 光流场包含了各个像素点的运动速度信息，反映了图像每个点的灰度变化，是 一个二维的矢量场，因此研究光流场就相当于研究空间运动物体的运动场，所以它 计算的可靠性和实时性成了重要的研究方向，尽管人们基于不同的理论基础提出的 各种光流计算方法及算法性能各有不同，但基本思想一致，首先对视频或者图像序 列进行预处理、消除噪声等影响，从中选取图像帧数，再根据图像序列的先验条件 选取适当的光流模型，光流模型的计算结果就估计出了运动参数。 随着当今社会不断信息化，关于多媒体的信息不断增加，学者的研究也越来越 偏重各种多媒体信息的处理技术，在各种多媒体中，人们更多关注的是视频信息， 因为它有生动、形象、直观的特点，而在视频的分析、视频的检索、视频的监控、 视频的编解码等视频信息处理应用中，运动对象分割有着重要的意义。 图像有区域、边界、噪声等信息，图像分割就是把图像中感兴趣的部分划分出 来，在此基础之上，从视频或者图像序列中提取感兴趣的运动对象就是运动对象分 割，它是图像分割的深化，针对的不是静态图像而是运动目标，是计算机视觉与图 像处理中的关键。 人们研究视频或图像序列时，首先为了识别出需要的目标，会根据一些特殊的 信息划分区域，图像序列包含很多不一样的运动信息，比如运动速度、运动方向等， 按照不同的方法根据这些信息检测这些对象，然后再进行分割。两相运动对象分割 仅仅是分割运动对象和静止背景，它只需要一个水平集函数就可以把前景区域和背 景区域划分出来，从而取出前景中的运动区域，如果是区分不同信息的许多个运动 青岛大学硕士学位论文 对象则需要研究多相运动对象分割。 1 2 国内外研究现状 运动分割最重要的一步就是运动目标对象的检测，它直接影响分割结果是否精 确、是否正确。人们已经提出了很多算法，有基于变化检测的算法、基于光流法的 算法和基于统计模型的算法等。基于变化检测的算法是将两帧静止图像相减，得到 的差值部分就是运动信息，这是因为图像序列是由运动对象在背景上多次叠加而形 成的【l j ；基于光流法的算法是图像上的像素点包含运动大小和运动方向，要得到不 同运动对象合并同质区域即可【2 】；基于统计模型的算法是将统计模型引入到检测模 型中对随机因素进行分析1 3 j 。 由于光流广泛应用于多个领域，光流计算方法的研究得到了很大推动，这些方 法包括局部微分方法( l o c a ld i f f e r e n t i a lm e t h o d s ) 【4 】、基于特征的光流计算方法 ( f e a t u r e b a s e dt e c h n i q u e s ) 1 5 j 、基于区域的方法( a r e a b a s e da p p r o a c h e s ) 扣j 、基 于相位的方法( p h a s e b a s e da p p r o a c h e s ) 1 7 】和变分方法( v a r i a t i o n a lm e t h o d s ) 1 8 j 。 1 9 8 1 年，h o r na n ds c h u n c k 提出了光流计算的变分方法，此方法根据序列图像亮度变 化和视频中含有的运动成分等确定出由数据项和光滑项组成的能量模型，再通过变 分方法获得能量泛函的e u l e r - l a g r a n g e 方程，并用差分方法对偏分方程进行离散化求 解。与其它光流计算方法【9 , 1 0 】相比较，变分方法的优点体现在模型具有通用性、建模 具有精确性、计算出的光流场稠密等，因而成为实现光流计算和运动分割的主流方 法之一，引起国内外广泛关注与研究【1 1 1 。 变分方法计算是通过最小化一个能量函数来实现的，能够为光流计算提供统一 的建模框架，并能方便的计算出稠密的光流场，但是采用此方法计算光流场时计算 机算量大，迭代的收敛速度比较慢，需要多次迭代才能得到近似解，耗时较多，计 算效率较低，不能够满足实时应用。研究快速的变分光流计算方法成为该领域目前 国内外研究的重要问题【1 2 】。多重网格方法【1 3 1 、图割方法及对偶方法【1 5 1 是力图满足 这一要求的新方法。 ( 1 ) 多网格方法 近年来，多网格方法是国内外活跃的研究课题之一。它的基本思想是首先在初 始的网格上进行几次迭代计算，将得到的变量值和残差值传递到下一层较粗的网格 上，继续迭代，沿着粗网格重复进行这个过程，最终直到最粗的网格为止，在最粗 的网格上计算出解之后，再向上沿着每一层网格对上一层的变量进行校正，一直到 最初始的网格停止，最终得到的就是要求的精确解。多网格方法收敛速度快，能明 显加快运算速度，广泛应用于光流计算、医学图像处理、运动对象分析等领域。 ( 2 ) 图割方法【蛉1 7 】 2 第一章绪论 2 0 0 1 年，y b o y k o v 等人将图割方法应用到图像分割领域。它的基本思想为：通 过映射将图像转化为一个网络，用不同的标记表示要分割的目标物体内部和外部的 像素点，并且给这些像素点赋予不相同的权重，用最小化能量泛函进行分割，最后 得到物体的轮廓线。这种方法的优点是快速、全局最优、抗噪。图割方法还可以应 用在目标提取、图像匹配等领域。 ( 3 ) 对偶方法1 1 5 j 对偶方法的基本思想是由于t v 项中存在奇点使得求解困难，通过引入附加变量 加快了数值解的计算，同时也增加了数值解的精确度。此方法可应用于图像去噪、 图像扩散、图像分解等方向。 在上述几种快速计算方法中，用多网格方法和图割方法计算时数据结构复杂并 且占用大量内存，用对偶方法计算时需要借助硬件( g p u ) 加速。 1 3 论文的主要工作 变分光流计算的能量泛函包括数据项和光滑项，本文采用的光流模型，其数据 项是可以处理超界点的稳健估计数据项，光滑项是可以保持边界的总变差形式，对 于数据项可以进行不同的假设得到不同的光流模型，考虑的数据项假设有亮度、梯 度、h e s s i a n 矩阵、梯度的模、拉普拉斯算子以及h e s s i a n 矩阵的行列式为常值等。在 基于光流法的运动对象分割中，运动对象分割模型利用光流模型进行分割，并且利 用水平集的优点演化曲线。 ， 本文的研究有以下内容：用多网格法快速计算光流模型；分裂方法应用于图像 恢复的快速计算中，并被推广应用于变分图像分割中，在此基础上，本文将分裂方 法应用于六种基于不同数据项假设的光流模型计算中，实验证明了理论的有效性； 设计了光流场快速计算的s p l i tb r e g m a n 方法；光流模型与基于区域信息分割模型中 的c h a n - v e s e 模型相结合，提出了两相运动对象分割模型，用分裂方法计算两相运动 对象分割模型，实验证明此方法可有效缩短运算时间。 论文章节的安排如下： 第一章，概述课题研究的目的及意义、本课题的发展现状和国内外研究动态， 同时介绍了近几年人们广泛使用的快速计算方法，最后简述了本文研究的主要内容 和创新的地方。 第二章，介绍了具有稳健估计数据项和t v 光滑项的光流模型，根据不同的先验 知识可以选择不同的数据项。 第三章，用多网格法计算光流模型，实验证明其可以快速提高计算效率。 第四章，一方面设计了分裂方法，引入辅助变量，将原优化问题转化为交替优 化的子优化问题，并通过简单的软阈值公式、收缩算子和g a u s s s e i d e l 迭代实现计算， 3 青岛大学硕士学位论文 另一方面设计- s p l i tb r e g m a n 方法，通过引入辅助变量和迭代参数实现计算。给出 了两种方法的理论描述和公式推导，并与传统直接变分的方法进行了比较，最终用 实验结果证明两种方法都可以有效提高光流场运算速度。 第五章，将光流模型引入到c h a n v e s e 模型中，利用光流模型检测运动对象， 并结合水平集方法对运动对象进行分割，实现了两相运动对象的分割。将能实现快 速计算的分裂方法推广到运动对象分割模型中，同时给出了理论上的支持和公式推 导，并与传统直接变分方法进行比较，最后用实验结果进行验证。 第六章，总结了本论文的主要工作，并对两相运动对象分割的下一步研究重点 作了展望。 4 第二章光流模型和水平集方法 第二章光流模型和水平集方法 1 9 8 1 年，h o r n , s c h u n c k 8 1 提出的变分光流计算的能量泛函为： e ( 材) ：( ( 甜r v ，+ 口2iv i z ) 出 2 ( 1 ) 口 i = l 其中，甜= ( “l ，d 2 ，1 ) 丁，“2 是光流场在_ ，秘方向上的分量，v u , q = 1 ，2 ) 是梯度， 是图像强度，v ，= ( 厶，厶，厶) r ，x 3 是时间变量。 光流模型的能量泛函通用形式： e ( 幻= f ( 坂秒厂，甜) + a s ( v f ，v “) ) 西c 2 ( 2 ) 其中积分域q 为时间域或空间域，m ( d 。f ，“) 代表数据项，s ( 夥，v “) 代表光滑 项，式中的口是规整参数，用来调整解的光滑程度，若口越大，那么计算得到的光 流场就会越光滑，最小化能量泛函e ( 甜) 可以得到光流场u 。 用厂( 而，恐，黾) 表示序y u f 茎i 像的图像强度，其中( 五，) 是像素点的位置，屯是时 间。一般厂由初始的图像序列石和高斯函数巧卷积预处理得到1 8 1 ： f = k * f o 2 一( 3 ) 通过这个公式进行预处理，可以消除噪声及其它的扰乱性高频成分，a 通常被看 为噪声尺度。预处理有两个不足：( 1 ) 在细节上，去除了一些有用的信息。( 2 ) 光流场 的计算结果可能与原来的图像序列有些偏差。 2 1 数据项模型 数据项采用稳健估计函数1 9 1 ，m ( d f ，甜) = i p ( “) l ，处理超界点很有效。先验知 识在光流计算模型的数据项选取中起了极其重要的作用。图像设备信息( 如：噪声 影响) 、视频材料类型( 如：图像亮度的变化) 和物体运动的种类( 如：平移或旋转) 青岛大学硕士学位论文 都是先验知识，都可以影响数据项的选择。针对不同具体问题，可以根据先验知识 选择最佳数据项，进行能量函数演算和比较。 在帧间移动位移很小的情况下，针对数据项有不同的模型假设，对亮度、梯度、 h e s s i a n 矩阵、梯度的模、拉普拉斯算予以及h e s s i a n 矩阵的行列式为常值的情况分别 进行探究。 ( 1 ) 假定序列图像的亮度为常值 假定对于照明变化敏感度较低的物体，在运动过程中亮度始终保持不变，简单 一些，可以认为物体像素点的灰度值保持不变。这样用厂( 五，屯，x 3 ) 代表图像序列， 假设帧间的时间间隔为1 ，那么黾时刻与墨+ 1 时刻的两帧之间的亮度常值假设可表 示为【1 8 】： 厂( 五- t - u l ，而+ ，x s + 1 ) - f ( x 1 ，x 2 ，恐) = 02 一( 4 ) 假定位移8 1 曼d , ，即小于或等于一个像素，并且光流场随时间的变化是平滑的， 左边的项可以用一阶泰勒公式在x = ( 而，x 2 ，而) r 点处展开，即犯川 f ( x i + u l ，x 2 + z 乞，x 3 + 1 ) f ( x a ，x 2 ，玛) + m + 厶z 乞+ 2 - ( 5 ) 基于2 ( 5 ) 可定义数据项为m = 矿v 3 f i 。 数据项m 是光流计算最早的研究方向，应用十分广泛，但是如果图像序列的图 像亮度变化较低，光流场的计算结果就会不是很理想。 ( 2 ) 假定序列图像的梯度为常值 当序列图像对照明变化敏感度较低时，亮度常值假设计算得到的结果较好，但 是当运动的物体亮度有变化时，亮度常值假设计算得到的结果较差。所以，当运动 物体的亮度均匀变化的时候，可以假设图像亮度梯度( 厶，厶) 7 不会随时间的变化而 变化，此时得到两个约束方程： ( x l + “l ，x 2 + u 2 ，屯+ 1 ) 一厶( 石l ，x 2 ，x 3 ) = 0 i = 1 , 22 - ( 6 ) - 对2 一( 6 ) 式的左边进行泰勒公式展开，简化得： 6 i = 1 , 22 - ( 7 ) 第二章光流模型和水平集方法 相加得数据项： 鸠= i 酽2v ，厶i 鸠= l “7 v ，厶l i 陪ii 2 一( 8 ) ( 3 ) 假定序列图像的h e s s i a n 矩阵为常值 ? 进一步递推，常值假设同样可以用在高阶导数上。对于视频中物体的亮度保持 某恒定加速度递增或者递减的情况，可以假设序列图像灰度的二阶导数是常值。即 假设序列图像的皿厂是常值， 其中= 眨尝 ，得到数据项如下 m 3 = l u r v ，岛i 2 - ( 9 ) 光照发生变化时，数据项鸩和心都可以进行处理。但是需要注意的是鸩和 必光流场的计算效果依赖于物体运动的类型。这是因为和图像亮度的常值假设相 比，图像的梯度和h e s s i a n 矩阵都有关于方向性的信息，这样就造成了：当视频中 的物体平移、扩散和缓慢旋转时，相邻两帧的物体运动方向变化很小，光流场计算 出的效果很好。但是当相邻两帧间运动方向变化很大的时候，如快速旋转等，由于 不能保持方向性常值，光流场计算结果就会比较差。 ( 4 ) 假定序列图像的梯度的模为常值 为了解决运动方向性的约束，可以不再规定图像亮度的梯度为常值，而是限制 梯度的大小不随着时间的变化而变化。这样数据项可以写为： ( 5 ) 假定序列图像的拉普拉斯算子为常值 假定序列图像拉普拉斯算子保持不变，可得出数据项如下： 心= p v ，( ：叫 7 2 一( 1 0 ) 2 - ( 1 1 ) 青岛大学硕士学位论文 ( 6 ) 假定序列图像的h e s s i a n 矩阵行列式为常值 图像序? l jf ( x l ，x 2 ，x 3 ) 的h e s s i a n 矩阵是 驴眨 得出的数据项是： 眠= 妒v ，d e t ( h 2 f ) i 2 - ( 1 2 ) 数据项心坛减少了序列图像亮度方向的变化对光流场的影响，但是对噪声 敏感。 光流模型的数据项假设具体见表2 1 。 表2 1 数据项m m 6 的比较 m ( d ，l ，) i 以甜) i 常值假设光照变化运动类型 m 矿v ，厂i 亮度常值无任意 2 平移扩散 鸩 “7 v ， 梯度常值有 j ；i 缓慢旋转 鸠 l t = ，i i h e s s i a n 矩阵 有 平移扩散 ii 常值缓慢旋转 梯度的模 m l p v ，i v f l i 有任意 常值 m s 矿v ，( ：力i 拉普拉斯 算子常值 有任意 h e s s i a n 矩阵 m 6 妒v ，d e t ( h 2 f ) l 有任意 行列式常值 2 2 光滑项模型 数据项模型有两个需要求解的变量“。，甜：，无法计算出唯一解，为了使不可解问 题变成可解问题，根据t i k h o n o v 2 1 1 对此类病态问题求解时使用的规整项的设计思想， 在光流模型中引入了光滑项。 8 第二章光流模型和水平集方法 假设厂= u ( 功，厶( x ) ) r 是多通道图像，图像扩散的模型是 初始条件是 色= d i v ( t ( v f ，v u ) v u , ) ( i = 1 ，刀)2 - ( 1 3 ) ( x ，o ) = 彳( x )o = 1 ，刀) 其中t ( v f ，v u ) 是扩散张量。 2 一( 1 4 ) 当t ( v f ，v u ) = ，时，该扩散称为均匀扩斟2 2 】。 对上述图像扩散的定义进行推导，假定最终计算的光流场是光滑的，变量“，9 2 随着位置的变化为极小量，该变化的度量用它们的梯度v u 。，v u 2 ，那么均匀扩散的光 滑项表示为： 2 s ( v f ，v u ) - a i v 1 2 ，毒l 2 - ( 1 5 ) 其中，厂表示图像强度，材表示光流场。 均匀扩散的光滑项惩罚光流场中任何偏离，导致光流场变得模糊，以至于运动 对象不连续的运动会形成模糊不清的边缘，结果使光流场变得混乱。 上述光滑项模型是用i v 材1 2 作为光滑性的度量，在运动对象边缘等图像灰度值较 大的地方会有较大的计算值，这样就影响了光流场的计算，本文使用r u d i n ，o s h e r 和f a t i m e 2 3 1 提出的图像光滑性度量i v “l ，这是因为i v “1 2 与i v “i 计算最小值时，二者 梯度下降流的方程嬲i j 是缸黝v c 尚j ，在较大梯度值的地舶v l 尚户有较小 值，从而减小对光流场计算的影响，能较好地保持图像的边缘。 基于上述理论，均匀扩散的光滑项改进为： 2 s ( v f ，v u ) iv f 置l 9 2 - ( 1 6 ) 青岛大学硕士学位论文 改进前与改进后的光滑项表示如表2 2 ： 表2 2 光滑项比较 均匀扩散光滑项基于图像扩散的表示改进后的光滑项 22 s s ( v f ，v u ) 厶- iv u i1 2s ( v f ，v u ) 垒l v u ，i f = li = 1 2 3 水平集方法 2 3 1 曲线演化理论 曲线演化【冽是目前流行的一种分割方法，是曲线上每一点沿着法矢量方向随时 间的变化丽演化，实质是描述曲线的参数的变化，其中两个重要参数是单位法矢量 与曲率k ，前者描述曲线的方向，后者描述曲线弯曲程度。 假设( c ：【o ，1 】专尺2 ，p 专c ( p ) ) 是平面上初始化封闭曲线。当t 时刻时， c ( p ，t ) = ( 而( p ，) ，x 2 ( p ，f ) ) 是初始曲线c o ( p ) 沿法矢量演化的曲线，p 是任意参数。 则曲线演化的方程可以表示为： fc = 1 ，( c ) n 【c ( p ，o ) = c o ( p ) 其中，曲线c 上每点的演化快慢由速度函数v ( c ) 决定，如图2 1 所示。 2 - ( 1 7 ) 图2 1 曲线演化的示意图 曲线演化有曲率演化和常速率演化两种形式，但是无论哪种形式都会改变运动 l o 第二章光流模型和水平集方法 过程中的拓扑结构，曲率演化将原始平滑封闭曲线的尖角在演化过程中趋于平滑， 最终变为一个闭合的圆，常速率演化导致曲线出现分裂、尖角等。由于火苗外形拓 扑结构变化的随意性和复杂性，难以用参数化的曲线或曲面表述这种变化，所以 s j o s h e r 和j a s e t h i a n 2 5 j 于1 9 8 8 年提出了水平集方法，用来解决火苗外形的变化过 程。水平集方法将演化问题转化为一个求解偏微分方程的数学问题，即用差分方法 来实现水平集函数随时间不断运动的数值近似解。水平集方法的基本原理是将当前 正在演化的闭合曲线或者曲面转化为高一维空间中水平集函数【2 6 1 ，在高一维的水平 集函数中嵌入当做零水平集的运动界面。水平集实质是有相同的水平集函数值的点 集合，只要找到零水平集就停止曲线的演化，而随着时间不断变化，由水平集函数 就可以得到零水平集。从而，低一维空间中曲线或曲面的变化可以代替高一维空间 中不断变化的水平集函数，所以即使闭合曲线的拓扑结构发生了变化，水平集函数 仍是一个有效的函划z 7 1 ，在曲线演化过程中仍然能够有效处理拓扑结构的变化。水 平集方法扩展到更高维空间很方便，例如可以很容易扩展到三维闭合曲面，从而应 用到三维重建与曲面上的图像分割中。 2 3 2 水平集方法及初始化 本章仅介绍二维平面上的曲线演化。对于平面上一条闭合曲线，当t 时刻时，二 维平面闭合曲线用c ( t ) = c ( 五，而，f ) 表示，如图2 2 所示，在一个三维空间上，( 而，屯，) 处一个曲面和一个垂直于t 轴的平面会有一个交线r ，这个交线就可以看作曲线 c ( ，) ，因此，在三维空间上，有相同函数值的一簇曲线就可用曲线c ( f ) 隐式表示。 用q 血和q 。眦表示闭合曲线的内部区域和外部区域。 叁， y c | ( 1 3 i x 图2 2 二维平面曲面在三维空间的表示 如图2 2 所示，在垂直于r 轴的平面上，三维空间里的函数矽( 五，而，f ) ：r 3 - 9 r 具 有如下性质： j 。 青岛大学硕士学位论文 ( x l ，x 2 ) c q i i i ( 坼，x 2 ) c 厂( f ) 2 - ( 1 8 ) ( x 1 ，x 2 ) cq 0 u t 则可以用 ( 而，而) i ( 而，而，r = 丁) 2 0 ) 集合来表示水平集，此时用c ( t 2 丁) 表示二维平面 上的曲线。 c ( ，) = c ( 而，x 2 ，) 是二维平面上的一条闭合曲线，它将平面分成两个区域，符号 距离函数( s i g n e dd i s t a n c ef u n c t i o n , s d f ) 的定义是点( x l ，x 2 ) 到曲线c ( f ) 的最短距 离( _ ，x 2 ，) ，并且： ( 而，x 2 ) i si n s i d ec ( f ) ( 而，x 2 ) i so nc ) 2 - ( 1 9 ) ( x l ，x 2 ) i so u t s i d eo f c ( t ) 那么曲线c ( f ) 可以用零水平集( 五，x 2 ，f ) 来表示，即c ( t ) = ( x ，y ) l 矽( 而，x 2 ，) = 0 ) 。 综上所述，在初始条件下，二维平面上的封闭曲线c ( t ) 演化的问题等同于三维 空间上嵌入的函数演化问题，那么二维平面上的封闭曲线就可以由水平集 矽( 五，x 2 ，) = 0 计算得到。 水平集函数通常用符号距离函数进行初始化，一般将曲线初始化为一个圆，这 样可以减少选取的初始化封闭曲线对计算速度的影响。在水平集函数的计算过程中， 水平集函数初始化只需要进行一次，但在迭代几步之后，水平集函数会逐渐远离符 号距离函数，因此为了保证数据算法的稳定性，需要周期性地重新进行符号距离函 数的初始化。 1 2 o 0 o = = 形 矿p ( 甜) f p ( 材) 占， 1 ) 由4 - ( 11 ) 计算区域的光流场值计”，, 2 k “； 2 ) 由广义软阈值公式4 - ( 1 3 ) 计算辅助变量矿“； 3 ) 由收缩算子4 - ( 1 5 ) 计算辅助变量矿+ 1 ： e n d 本节研究的是采用基于g a u s s s e i d e l j 迭代的分裂方法来实现小位移光流计算模 型。考虑的光流计算模型的数据项假设有亮度、梯度、h e s s i a n 矩阵、梯度的模、拉 普拉斯算子以及h e s s i a n 矩阵的行列式为常值。 ( 1 ) 假定序列图像的亮度为常值 数据项m = i u r v ，f i 其e u l e r - l a g r a n g e 方程为： j q ，( 一v ? + 岛5 “? 一v ? 厶2 0 4 - ( 1 6 ) i 一岛( 甜：- v w 2 ) + ( n ( “) 一1 ，) 厶= o 第四章小位移变分光流计算的分裂方法 4 - ( 1 6 ) 式可采用g a u s s s e i d e l 迭代计算，迭代最终公式为： ( 2 ) 假定序列图像的梯度为常值 数据项鸠= 忙壹。u t v 3 厶l 其e u l e r - l a g r a n g e 方程为： 4 - ( 1 7 ) j - o l ，( a u t - v 。m 、) + ! ：岛5 z | 一1 ：? | ! ：厶 + 厶 2 2 o 4 ( 1 8 ) l _ 岛( a u ：一v ) + ( 岛( 甜) 一v ) ( 厶屯+ 厶而) = o 。 4 - ( 18 ) 式可采用g a u s s s e i d e l 迭代计算，迭代最终公式为： ( 4 岛h 2 + ( 而+ 岛) ) n + l = ( 一厶，一岛一吆( 厶恐+ 如) ) ( 1 + 岛) 鹄( ( 讯。j + 硝, j + l l - 维：+ 嘶n 铲+ l 。) 户一v w )4 ( 1 9 ) ( 4 0 2 1 h 2 + ( 厶之+ k 、j u 一2 州i , j = ( 吃一厶，一如一 ”i , j 1 ( 1 + 岛) ) ( 吃+ 如) 坞( ( 吆w + 咙川+ 础+ 蟛一。) 胪一v 嵋) ( 3 ) 假定序列图像的h e s s i a n 矩阵为常值 数据项：坞= 陲喜“r v ，厶勺i 其e u l e r - l a g r a n g e 方程为： 2 1 州 玑 坷 胪渺 “h 州 叫 u 哪 雄 m 小 吃磅 卜 + j “ 研幺 + + 丘、j、j厶厶 。埘 州” 材 材 一 一 z z 一 一 吃吗 以以 i i = 蟛蟛皤蛾 + + 亿缘 徽嬲咖咖 池池 青岛大学硕士学位论文 4 - ( 2 0 ) 式可采用g a u s s s e i d e l 迭代计算，迭代最终公式为： 卜饿归一) 隧 鹄( ( + + 喝+ 昭胪习叩) 卜像绯) 倭+ f x e z 色 坞( ( + 嘶+ 吼+ 略泸* 噬) ( 4 ) 假定序列图像的梯度的模为常值 数据项：心= i u t v ，i 夥0 取丁= ( 露+ + z 2 ) 2 ，固定w 和v 求z ，其e u l e r - l a g r a n g e 方程为： 4 - ( 2 1 ) 卜哗坷w l 一( ? ( 寥) 毛卸4 - ( 2 2 ) i 一岛( 材：- v 坞) + ( 反( u ) - 0 r 而= o 4 - ( 2 2 ) 式可采用g a u s s s e i d e l 迭代计算，迭代最终公式为： i ( 钾炉+ 暇) 彤= ( 吃一彳一吃夏) 夏+ 鸟( ( + + 础+ 龆) 序一v 。w ) i ( 鸲膨+ 斌) 蟛= ( 吃。一蟛五) 夏+ 岛( ( + l 乞 j + l + g l j + 咀) 胪一v 噬) ( 5 ) 假定序列图像的的拉普拉斯算子为常值 数据项：坞= i u t v 。( ：门l ， 第四章小位移变分光流计算的分裂方法 其e u l e r - l a g r a n g e 方程为： ”乳，+ ? ：f ) i 叫而+ 厶乜而) _ o 4 - ( 2 4 ) i 一皖( - v w 2 ) + ( 岛( 甜) 一v ) ( 厶而屯+ 厶屯屯) = o 、。 4 - ( 2 4 ) 式可采用g a u s s - s e i d e l 迭代计算，迭代最终公式为： ( 4 岛肌( k 划= 乏莨麓小“一 + b ( ( “：w + 皖小。+ n + 吐l ，+ 磁。) h 2 一v w ) ( 4 q 肌( k 岷j ) 势 笺篆甓小一) + 岛( ( 甜，+ 磁+ 。+ 吃n + 吐l ，+ 吃n + 少l 。) h 2 一v 嵋) 4 - ( 2 5 ) ( 6 ) 假定序列图像的的h e s s i a n 矩阵行列式为常值 序列图蝴瑚的n e s s i a n 矩阵为：皿_ ( 乏磊 ，由此得数据项为： 心= 矿v ，d e t ( h 2 f ) ，其中：d e t ( h j ) = 厶而厶而- l 而厶而， 其e u l e r - l a g r a n g e 方程为： 4 - ( 2 6 ) 式可采用g a u s s s e i d e l 迭代计算，迭代最终公式为： 4 一( 2 6 ) o 卸 卜jk k 吒k 吒k 氐岷篾议d 小纵 m 岬 廿 舭 舭 ，一。一、 青岛大学硕士学位论文 【4 0 1 h 2 + ( 厶q q 如屹+ 厶川厶啪一厶屹川如可一厶屹晶川) 气vin吆j-，f_，x(1厶xltfqx屹2x如2-屹fxl+xl厶fx川2x如2t+屹f砣xlx一2t厶fx2珈x1+如fxlxq2fx厶2xl宅t如川屹) ( 厶q 川如屹+ 厶q 厶瑚厶屹q 岛川一厶屹岛川川) + 研( ( “_ ，+ 材嚣+ lm n + l 川n 训+ 1 ) h 2 _ v w ) 【4 a 2 h z + ( 厶q 屹如砣+ 厶习f x 2 x 2 x - - 厶宅屹如川一厶砣如川屹 ( ! u j n 融+ l ：缴+ 镪撒擘舷川川) j ( 厶川宅如砣+ 厶川厶聊一厶砣屹岛川一厶砣厶q 袍j + 岛( ( 磋，+ l ，- ，+ 材易一l + 磁品，+ 磁乃一1 ) h 2 _ v 嵋) 4 。3 2 实验结果与分析 1 n + ，l ： ) ) 2 k n + 1 ，：4 万1 i 1 矿pu k + 1 ) 占， 1 ) 岛+ 1 = 包。+ v u ，一彬 2 ) 由) 4 ( 31 ) 计算区域的光流场值材。，u 2 “1 ； 3 ) 由广义软阈值公式4 - ( 3 3 ) _ i , t 算辅助变量矿； 4 ) 由收缩算子4 - ( 3 5 ) 计算辅助变量1 ，“1 ； e n d 4 4 2 实验结果与分析 实验在p c 机( i n t e l ( r ) ，c p u2 5 3 g h x ，内存2 0 0 g b ) 上实现，软件工具为 m a t l a b 7 0 。 实验一： 实验是由缓慢逆时针旋转的绿色纹理球序列的第3 ，4 帧计算得到光流场。如图 4 5 所示，其中( a ) 、( b ) 分别是序列图片的第3 帧、第4 帧，( c ) 、( d ) 分别为光流模型 采用传统直接变分方法和s p l i tb r e g m a n 迭代方法得到的结果，计算过程采用相同的 数据项m 。 青岛大学硕士学位论文 ( a ) 绿色旋转球序列第3 帧( b ) 绿色旋转球序列第4 帧 + 、一一二 ：i ：= = = ；二；： ：苌：= = = = 二z ；z i ： 一i i 瀑意匿玢 、n q v y v _ y 一7 ：。 。、n 、_ o - r r _ 一：。 - 、h 、_ _ - 矿， ： 忒= ：= = ；： i i 过瀑釜豸j ! ! ! ( c ) 传统直接变分方法计算结果( d ) s p l i tb r e g m a n 方法计算结果 图4 5 光流模型不同方法计算光流场的结果 图4 6 中，针对数据项为m 的光流模型，曲线( 1 ) 为采用传统直接变分方法计算 的能量下降曲线，曲线( 2 ) 为采用s p l i tb r e g m a n 方法计算得到的能量下降曲线，其中 = o 1 ，名= 1 0 0 , q = 1 5 0 ，岛= 1 5 0 。 图4 6 能量下降曲线 从图4 6 中可以明显看到采用s p l i tb r e g m a n 方法，在最初的几次迭代中，能量 一器一一 第四章小位移变分光流计算的分裂方法 迅速下降，并且能够更快地达到稳定值，更快地收敛。 表4 3 给出了光流模型分别采用传统直接变分方法和s p l i tb r e g m a n 方法的实验 数据。 表4 3 实验相关数据的对比 方法迭代次数时间( 秒)能量 传统直接变分方法 4 3 93 8