（计算机应用技术专业论文）基于过松弛算法和马尔可夫随机场的运动分割研究.pdf

哈尔滨工程大学硕士学位论文 摘要 运动对象的分割和跟踪技术一直是图像处理和计算机视觉领域 的重要研究课题。近年来，随着多媒体技术的迅猛发展及计算机性 能的不断提高，各种视频图像的应用越来越广泛。视频图像序列中 运动对象的分割技术也日益受到人们的青睐，得到了广泛的应用。 本文在阅读相关文献的基础上，对运动目标分割的发展及研究 现状进行了总结。然后介绍了运动估计的相关概念和基本原理，并 对马尔可夫随机场( m r f ) 方法进行了详细的阐述，提出了一种运 动估计与马尔可夫随机场模型相结合的运动分割方法该方法首先 采用多运动同步估计方法和过松弛算法进行运动估计，通过运动估 计确定每种运动的初始区域。采用鲁棒公式与误差模型相结合，选 择仿射运动为运动模型，通过过松弛迭代获得每种运动的运动参数； 取属于误差最小的运动为每个像素所属的运动，所有属于一种运动 的像素的集合为该运动对应区域的初值。根据马尔可夫模型的参数 较少、空间约束性强、易于结合其它方法等特点，采用马尔可夫随 机场模型对运动估计后结果进行平滑去噪。文中最后介绍了算法的 仿真实现并给出了实验结果。实验证明，该算法能较好地估计出运 动参数并分割出运动对象。 关键词：运动分割：运动估计；马尔可夫随机场；过松弛算法；鲁 棒估计 哈尔滨工程大学硕士学位论文 a b s t r a c t s e g m e n t a t i o na n dt r a c kt e c h n o l o g yo fm o t i o no b j e c t sa r ea l w a y s i m p o r t a n ts u b j e c t si ni m a g ep r o c e s s i n ga n dc o m p u t e rv i s i o n r e c e n t l y , w i t ht h ef a s td e v e l o p m e n to fm u l t i m e d i at e c h n o l o g ya n dc o n t i n u o u s i m p r o v e m e n to fc o m p u t e rp e r f o r m a n c ea l lk i n d so fv i d e oi m a g e sa r e w i d e l ya p p l i e d s e g m e n t a t i o nt e c h n o l o g yo fm o t i o no b j e c t si nv i d e o i m a g es e q u e n c e sa t t r a c t sm o r ea t t e n t i o na n di su s e di n c r e a s i n g l y a f t e rr e a d i n ga r t i c l e si nt h i sd o m a i nt h i st h e s i ss u m m a r i z e d e v e l o p m e n ta n dr e s e a r c hs t a t u so f m o t i o no b e c ts e g m e n t a t i o n f i r s t l y , r e l a t e dc o n c e p t sa n db a s i cp r i n c i p l e so fm o t i o ne s t i m a t i o na r e i n t r o d u c e di nt h et h e s i s t h e nm a r k o v r a n d o mf i e l d ( m r f ) a l g o r i t h mi s p r e s e n t e di nd e t a i l am o t i o ns e g m e n t a t i o nm e t h o dc o m b i n i n gm o t i o n e s t i m a t i o nw i t hm r fm o d e li sp u tf o r w a r d f i r s t l y , s y n c h r oe s t i m a t i o n o fm u l t i - m o t i o na n do v e r - r e l a x a t i o na l g o r i t h ma r eu s e di nm o t i o n e s t i m a t i o nt oo b t a i ni n i t i a lr e g i o n so fm o t i o n s t h er o b u s tf o r m u l ai s c o m b i n e dw i t he r r o rm o d e la n da 位n em o t i o ni ss e l e c t e da sm o t i o n m o d e l m o t i o np a r a m e t e r so fe v e r ym o t i o na r ea c h i e v e db y o v e r - r e l a x a t i o ni t e r a t i o n t h el e a s te r r o rm o t i o no fe a c hp i x e li st a k e n a st h e r e s p e c t i v em o t i o nt o w h i c hi t b e l o n g s t h ec o l l e c t i o no fa l l p i x e l sb e l o n g i n gt oo n em o t i o ni st h ei n i t i a lv a l u eo fc o r r e s p o n d i n g r e g i o no ft h em o t i o n a c c o r d i n gt ot h ec h a r a c t e r so fm r fo ff e w p a r a m e t e r so fm o d e l ，s t r o n gs p a t i a lc o n s t r a i n ta n de a s yc o m b i n a t i o n w i t ho t h e rm e t h o d s m r fm o d e li su s e dt os m o o t ht h er e s u l ta n dr e d u c e n o i s e t h es i m u l a t i n gi m p l e m e n t a t i o no ft h ea l g o r i t h ma n dr e s u l t so f e x p e r i m e n t sa r eg i v e ni nt h ee n do ft h e s i s t h ee x p e r i m e n t ss h o wt h e m e t h o di n t h i st h e s i sc a ng e tb e t t e re s t i m a t i o na n ds e g m e n t a t i o no f m o t i o no b e c t s k e y w o r d s ：m o t i o ns e g m e n t a t i o n ： f i e l d ： o v e r - r e l a x a t i o na l g o r i t h m ： m o t i o ne s t i m a t i o n ：m a r k o vr a n d o m r o b u s te s t i m a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指 导下，由作者本人独立完成的。有关观点、方法、数据 和文献的引用已在文中指出，并与参考文献相对应。除 文中已注明引用的内容外，本论文不包含任何其他个人 或集体已经公开发表的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 日期：i 川年1 月踟日 哈尔滨工程大学硕士学位论文 1 。1 课题研究意义 第1 章绪论 人类接受的外界信息有8 0 以上是来自于视觉，视觉是人类最重要 的信息交流方式。人类是通过眼睛与大脑来获取、处理与理解视觉信息 的。周围环境中的物体在可见光的照射下，在人眼的视网膜上形成图像， 由感光细胞转换成神经脉冲信号，经神经纤维传入大脑皮层进行处理与 理解。视觉不仅指对光信号的感受，还包括了对视觉信息的获取、传输、 处理、存储与理解的全过程。信号处理理论与计算机出现后，人们试图 用摄像机获取环境图像并将其转换成数字信号，用计算机实现对视觉信 息处理的全过程。 运动对象的分割和跟踪技术一直是图像处理和计算机视觉领域的 重要研究课题。近年来，随着多媒体技术的迅猛发展及计算机性能的不 断提高，各种视频图像的应用越来越广泛。视频图像序列中运动对象的 分割技术也日益受到人们的青睐，得到了广泛的应用。例如，在人工智 能系统中，要对运动对象进行判断与跟踪：在国防安全系统中，需要对 军事目标进行跟踪与识别：以及在生物医学领域的应用等等。为了实现 基于内容的存储、传输和检索等操作，如何快速有效的分割出运动对象 有着非常重要的作用和意义。 在目前使用的数字视频监控系统中引入视频运动目标分割技术，可 实现对图像序列中运动目标的自动分割，从而大大提升监控系统的性 能，使得监控系统能够自动监视重要区域，并能在有少数人或车辆活动 时立刻自动报警，保障被监控区域的安全。并且，在实现了视频运动且 标分割的基础上，加入运动目标识别或跟踪算法，能解决运动目标自动 识别和跟踪等问题，可以迸一步增进监控系统的智能化，最终实现无人 值守的智能场景监控系统。同时，在交通检测中应用视频运动目标分割 技术，使得自动测量车速、统计流量、自动记录肇事车辆等功能的实现 成为了可能。 哈尔滨工程大学硕士学位论文 ；j ；i i i i e i i i i 自i ；i i i _ i i | | 瞄 视频运动目标分割技术的采用，使得面向对象的图像编码技术的实 现成为了可能。传统的视频编码标准，如m p e g 1 m p e g 2 和h 2 6 1 h 2 6 2 ，均缺乏对视频内容高层次信息的描述，而m p e g 组织提出的 m p g e 4 视频压缩解压缩标准，是一种基于对象的编码技术，其中引入 了视频对象v o ( v i d e oo b j e c t ) 的概念。该标准要求在编码前将视频序列 分解成多个与不同视频对象相对应的视频对象平面( v i d e oo b j e c tp l a n e - - v o p ) ，然后对不同的视频对象进行单独编码，经过信道传输，在接收 端实现对视频对象的重构。 正是由于采用了视频运动目标分割技术，m p e g 4 标准才能够将视 频序列中每帧图像分解成具有定语义的视频对象和背景，实现了从基 于像素的传统编码向基于对象和内容的现代编码的转变，它代表了新一 代的智能图像编码，集合了以往的图像编码无法实现的卓越功能。 综上所述，对基于图像序列分析的视频运动分割算法进行研究，具 有很重要的应用前景和研究价值。 1 2 序列图像中运动目标分割技术的发展及研究动态 图像分割一直是数字图像处理过程中的重点，同时也是一个难点。 为此，国内外批学者从多角度、多方位入手，在图像分割领域迸行了 广泛的研究，提出了许多有价值的理论与方法。 运动目标分割技术是图像处理和计算机视觉领域的重要研究课题。 近年来，国内外对于运动目标分割技术的研究取得了许多成果，人们提 出了许多新的分割技术及方法。通过参阅近年来各研究人员提出的运动 目标的分割技术及方法，并进行归类可以看出，对运动目标的分割方法 大致可分为：检测变化区域的分割方法、基于非参数模型的运动分割方 法、基于参数模型的运动分割方法、基于形态学的方法以及其它一些分 割方法等m 2 哈尔滨工程大学硕士学位论文 1 2 1 检测变化区域的分割方法 检测变化区域的分割方法是经过全局运动估计和补偿后，相邻视频 帧的背景是静止的，经过帧问的差分图像，可以检测到运动区域”1 1 。文 献【3 】提出相邻的两个差分图像的方差之比服从f 统计分布，而且不需要 知道实际的方差。文献 4 】认为帧问差分符合两个零均值的拉普拉斯分布 的混合，并应用最大似然法估计分布参数，然后分割出背景和运动对象。 文献【5 仲首先利用相邻帧差并采用全局阈值获得变化检测模板，然 后采用局部阀值的迭代松弛技术来完成边沿的光滑滤波。为了分割不连 续运动的对象，使用了一个深度为l 的可调节存储器，如果存储器中的 某个像素在前几帧中的变化检测模板至少有一次属于运动对象，则该像 素属于运动对象。通过消除未覆盖的背景区域并使模扳边沿对齐图像边 沿来改进对象模板的定位。 由于直接通过两帧差检测变化区域的方法对噪声比较敏感，因此， 文献【4 ，6 】采用形态运动关联算子来间接利用帧差检测运动区域，同时根 据序列图像的运动程度，采用多帧处理来获取运动对象，该算法具有一 定的抗噪能力。 总的来说，这类方法计算简单，但是对于噪声仍比较敏感，且对象 运动不能太快。由于室外场景背景变化复杂，因此该方法比较适用于室 内场景运动视频对象的分割。 1 2 2 基于非参数模型的分割方法 基于非参数模型的分割方法对物体的运动是通过光流场来得到的。 通常假设相邻帧间外界照明条件不变，因此光流场反映了运动场。但是 由于孔径和遮挡问题，用光流法估计二维运动场的解是不稳定的，需要 使用附加的假设模型来模拟二维运动场”，。 典型的用于运动分割的方法是基于块运动估计的分割方法。块运动 模型主要应用在低码率视频编码应用中，基于平移的块运动模型的运动 3 哈尔滨工程大学硕士学位论文 估计不能处理旋转和缩放的情况，块运动模型的分割精度由块的大小决 定。由于运动估计运算量大，基于运动的目标分割和跟踪要求有准确的 运动估计，因此常采用一种“金字塔”式的由粗到细的快速估计方法n 1 “ 另一种典型的用于运动分割的方法是基于贝叶斯法“”- 。贝叶斯法 是在给定光流数据的条件下，搜索分割标记的最大后验概率，使得当前 分割与期望分割符合的程度最大。由于贝叶斯法同时进行分割和运动估 计，分割效果较好，但运算量大。 使用空间变换的网格( m e s h ) 模型成为目前一个积极的研究领域，网 格模型分为三类：规则网格、自适应网格和基于内容的网格。文献 i s 】 改进了六边形匹配的运动估计算法，降低了算法的复杂度。因此为了提 高运动估计准确度，文献 1 6 】提出了基于网格的自适应内插技术来实现 运动补偿；而为了提高运动估计的速度，文献【1 7 】提出了一种前向插值 方法代替迭代的网格运动估计，该方法的分割结果易受网格生成算法中 关键点数选择的影响。 在检测出变化区域的基础上，文献【1 8 】使用s n a k e 算法以及松弛法以 得到精确的对象边沿。文献【1 9 】通过改变s n a k e 能量项使其具有仿射不变 性的特点，并结合对象的参数原型可以很好的解决多个对象分割时的对 应问题。这类方法根据图像的梯度信息和时空光滑约束条件使曲线按能 量最小原则收敛，且可能收敛到局部最小。 1 2 3 基于参数模型的运动分割方法 基于参数模型的运动分割方法的基本思想是：假设有k 个相互独立 的运动物体，每一个光流矢量对应于单个不透明体的三维刚体运动的投 影，那么，每一个不同的运动可以通过一系列映射参数来正确描述参 数模型需要对视频图像进行分割，每个区域的运动用一个参数集来描 述。运动矢量可以从这些模型参数来合成。 一个由平面的三维刚体运动产生的二维运动场，在正交投影下可以 用6 个参数的仿射模型描述一“，而在投射投影下，则得到8 个参数的透 视模型n 。文献 2 2 1 采用对象的3 d 模型和深度信息分割对象。文献 2 5 】 哈尔滨工程大学硕士学位论文 采用二次空间变换，不仅可以补偿诸如平移、尺度变化、旋转等变化， 还能补偿形变和非均匀仲展等非线性变化。 相对于非参数模型，参数模型受噪声的影响较小，因为参数是由多 个像素结合在一起估算出来的。参数模型可以有效地处理对象间的遮挡 问题，缺点是只适用于刚体运动。 1 2 4 基于形态学的分割方法 基于形态学的分割方法，采用形态学分水岭算法分割对象c 一，的算 法被广泛使用，算法由图像简化、标记提取、决策和后处理四步构成。 文献【2 6 】提出了一种时空形态学分割方法，通过移去对人眼不敏感的细 节并保留对人眼敏感的细节，使得图像得到简化，再采用基于区域合并 和分割的算法得到各个区域，而且不产生弱边沿。文献【2 9 】提出采用多 尺寸形态学梯度算法对图像进行初始分割，再根据运动一致性进行区域 合并。由于采用彩色信息进行区域合并时，容易消除弱的边沿，文献 3 0 】 提出基于边沿和噪声模型的统计方法，认为对于弱边沿，标记的最优位 置对称位于边沿两边，且尽可能靠近边沿。该方法同时采用了边沿信息 和彩色信息，以提高边沿的准确定位。形态学分割算法运算简单，能较 好地提取运动目标的轮廓，但由于要依靠梯度信息，因此对噪声比较敏 感。 1 2 5 其它一些分割方法 文献 3 0 采用局部方差对比度和帧间差分对比度构成二维熵分布 图，用以分割运动目标。文献【3 l 】采用g a b o r 和m a l l a t 小波变换进行分 割，其中g a b o r 小波变换可在较低的空间分辨率下准确估计运动信息， m a l l a t 小波变换用于进行高分辨率下的目标分割。基于彩色快速递归最 短扫描树算法是一种由细到粗的分割方法，分割速度快，但是需要预先 制定最终分割的区域数，且对噪声也比较敏感。文献 3 2 】通过交互式预 先在整个视频中选择一些代表对象不同特征的关键帧，对关键帧进行对 s 哈尔滨工程大学硕士学位论文 象分割后作为分割其它帧时的参考，这种方式通过利用对象的多视点信 息可以达到鲁棒分割跟踪对象的目的。对于某些应用，可以采用多个单 目视频或立体视频来准确估计各个对象的运动信息、深度信息，通过融 合同一场景的多视点信息来有效地分割运动目标。 1 3 本文运动目标分割方案的选取 视频运动目标的分割问题可以描述为：提取出连续镜头的视频序列 中具有明确语义的视频对象，如人、车辆、皮球等分割视频语义对象 的难点在于：有语义意义的视频对象的视觉底层特征( 颜色、运动、光 流、速度及这些特性的组合) 往往不是一致或相似的；可用的自动分割 技术有限；多个前景物体的分割和跟踪；算法通用性差，大都仅在一定 的应用场景或假设环境下可以得到较满意的结果；环境变化及噪声影响 算法的鲁棒性。 运动估计是视频处理系统的一个重要组成部分。运动估计涉及到序 列图像中的二维运动和物体的三维运动的估计，以及序列图像中的二维 运动和真实的三维运动之间的关系。所有的运动估计算法都是基于图像 亮度的时间变化。实际上，基于亮度变化观察到的二维运动不同于真实 的二维运动。运动估计研究的主要内容是如何快速有效的获得有足够精 度的运动矢量。运动估计问题通常可转化为一个最优化问题，并且涉及 其中的一个个关键部分就是运动场参数化。本文的运动模型采用最运动 估计中最常用的二维仿射模型；参数求解的方法采用过松弛算法，该方 法是一种梯度下降方法，适用范围广 对于分割算法，基于马尔可夫随机场( m a r k o vr a n d o mf i e l d - - m r f ) 模型的运动目标分割算法，属于前文所述的基于像素的变化检测算法的 范畴。该算法充分利用了图像中像素间的马尔可夫性，并建立了m r f 模型以实现图像分割。 相对于其它分割方法，基于m r f 模型有如下优点： ( 1 ) 模型的参数较少，因此处理方便； ( 2 ) 模型的空间约束能得到更好的分割效果： 6 哈尔滨工程大学硕士学位论文 ( 3 ) 基于模型的方法易于结合其它方法，易于拓展； ( 4 ) 不同的模型先验可以反映各种图像属性，方法稳定。 综上所述，我们采用基于m r f 的运动目标分割算法作为最后的分 割算法。 本文采用鲁棒误差模型，通过过松弛算法计算仿射运动参数，多运 动同步估计方法先估计出运动参数，从而获得运动目标初始分割。这种 分割结果往往会包含大量的噪声。为了消除噪声达到更好的分割效果， 用m r f 进行平滑去噪，实现了更好的对运动目标进行提取。 1 4 本论文主要的工作和论文结构 本文采用的是二维仿射模型作为运动模型，并用鲁棒估计结合误差 模型，用松弛算法求运动参数。多运动同步估计方法，能同时估计出多 个运动，根据运动参数和误差最小归属原则，得到运动目标的初始分割。 最后用m r f 模型对运动估计后结果进行平滑去噪。基于m r f 的图像 分割问题，采用条件迭代模式( i c m ) 等方法来完成。本文最后仿真实现 了该算法，并通过实验结果证明该算法的有效性。 本论文的内容结构安排如下： 第1 章简单介绍了课题研究背景和意义，回顾了运动对象分割与跟 踪算法的研究现状，最后阐明了本文的主要研究内容和结构安排。 第2 章介绍了运动估计的基本原理和运动表示，并介绍了运动估计 的技术和准则。最后介绍了松弛算法和运动目标函数最小化。 第3 章介绍m r f 模型及相关的基本概念，并说明g i b b s 分布和m r f 的 等价性关系，m r f 模型是把一维因果马尔可夫链扩展到二维的结果 h a m m e r s l o y c l i f f o r d 定理确立了m r f 和g i b b s 分布之间等价性因此， 可以用g i b b s 分布来定义m r f 模型。并介绍了系统能量函数的定义。最 后介绍了基于m r f 的图像分割的三种算法。 第4 章提出了本文的算法，先用运动估计检测出运动目标后，再用 m r f 模型的算法对运动目标进行分割。最后介绍了算法的仿真实现并给 出了实验结果。实验证明，该算法能较好地分割出运动对象。 1 哈尔滨工程大学硕士学位论文 结论是对全文的总结和对今后工作的展望。 哈尔滨工程大学硕士学位论文 第2 章鲁棒的运动估计和松弛算法 对多帧间的运动信息的估计和利用，称之为运动估计与运动补偿。 运动估计与运动补偿在数字视频处理技术中占有相当重要的位置。在过 去的2 0 年里，产生了许多新的运动估计算法。一般的算法都是基于时 间域的确定性算法，近年来基于频率域和统计学理论的运动估计算法也 得到了飞速发展，并取得了丰硕的成果。 2 。1 运动估计 2 1 1 基本原理 运动估计是视频处理系统的一个重要组成部分运动估计涉及到序 列图像中的二维运动和物体的三维运动的估计，以及序列图像中的二维 运动和真实的三维运动之间的关系。三维运动估计时常是三维结构和运 动估计所需要的一个预处理阶段。同样，二维运动估计本身也有着广泛 的应用，包括视频图像序列分割、压缩、滤波和采样率转换等。 所有的运动估计算法都是基于图像亮度的时间变化。实际上，基于 亮度变化观察到的二维运动不同于真实的二维运动。为了更精确起见， 把观测的或表现的二维运动矢量的速度称为光流。运动场应被理解为光 流。它不仅可以由物体运动引起，而且可由摄像机运动或者照明条件的 变化引起。 运动估计研究的主要内容是如何快速有效的获得有足够精度的运动 矢量。运动估计问题通常可转化为一个最优化问题，并且涉及三个关键 部分：运动场参数化、最优化准则的公式和寻找最优参数。 9 哈尔滨工程大学硕士学位论文 2 1 2 运动表示 运动估计的一个关键问题是如何参数化运动场，即运动的表示问 题。由摄像机或物体运动产生的二维运动场通常可以用很少几个参数来 描述。但是，在成像的场景中一般会有多个物体做不同的运动。因此， 采用总体参数模型通常不合适。 最直接和不受约束的方法是为每个像素都找到运动矢量，即基于像 素表示法。这种表示法适用范围广，但是需要估计大量的未知量，并且 其解时常在物理上是不正确的，除非在估计过程中施加适当的物理约 束。如果仅是摄像机在运动，或者成像景物包含单个的具有平坦表面的 物体。就可以用整体运动表示法来描述整个运动场。 2 1 3 运动估计准则 序列图像的运动估计实际上就是参数优化问题。因此，需要一定目 标函数作为运动估计准则。在运动估计准则下，采用各种方法进行优化， 使目标函数达到最优。 ( 1 ) 基于位移帧差准则 最常用的运动估计准则是锚定帧和目标帧之间每个对应点对间亮 度值之差的和。考虑一个视频序列，其亮度用甲瓴y ，f ) 表示。在序列图 像中，假设点x 沿着轨迹运动时灰度保持不变，则式2 1 描述了时刻t 到时刻f + z 的运动补偿误差，称为位移帧差图像。 p ( 力= 甲2 “+ 以，y + 或，f + 4 ) 一甲i ( 工，y ，f ) ，y ，t ) ( 2 - 1 ) 其中 是t 时刻图像中所有像素的集合，以和矾分别是像素( x ，y ) 从时刻t 到时刻t + d t 水平和垂直方向上的运动位移。设集合 中的像素 个数为n ，则目标函数可以写成： e ，4 = 寺砂：“+ t ，y + 嘭，f + 吃) 一( 墨弘f ) r ( 2 2 ) 1 ，扣 p 是一个整数。当p = 1 时，上面的目标函数称为平均绝对差( m a d ) ；当 1 0 哈尔滨工程大学硕士学位论文 p = 2 时，称为均方差( m s e ) 。 ( 2 ) 基于光流方程准则 这种方法通过求解基于光流约束的方程组来实现。假定在时刻t 的 像素点( x ，y ) 在时刻f + 西移动到点0 + t ，y + d ，) 。在恒定亮度假设下， 同一个像素点在不同时刻的图像具有相同的亮度值。因此： y ( 善+ d ：，y + d ，f + 西) = 妒( y ，t ) ( 2 - 3 ) 应用泰勒公式展开，当d ，d ，很小时，有： 吣+ t 妒+ 面) = y ( 坝f ) + 警以+ 詈嘭+ 詈面 ( 2 - 4 ) 根据式( 2 3 ) 和( 2 4 ) ，可得到： 警t + 詈嘭+ 警唾= ” ( 2 5 ) 令似) ，) = 缈j ，f ) ，( 毛y ) = y “y , t + d 1 ) ，x = 似y ) ，d = ( t ，以) 。若 4 很小可以假设譬吐= ( j ) 一( x ) ，则式( ( 2 5 ) 可以写成： 詈以+ 詈办+ 帆训= o 或v 妒p + 帆啪) = o ( 2 - 6 ) 对于所有的x 求解上面的方程可转换为一个具有如下目标函数的最小化 的问题： z o = i ( v ( 石) ) 7 d ( 石) + ￥，2 ( 石) 一( x ) i ( 2 7 ) ( 3 ) 贝叶斯准则 在运动估计中，另一个经常使用的准则是贝叶斯准则。贝叶斯准则 是基于运动估计问题的概率公式，由k o n r a d 和d u b o i s 首先提出“。 给定一个锚定帧甲。在目标帧甲：的图像被认为是自由场甲的一个实现， 而运动场a 是另一个自由场d 的一个实现。根据贝叶斯公式，运动场 的后验概率分布可以写成： p ( d = d 肛嗍) = 坐掣蒿萨。| ( 2 - s ) 基于贝叶斯准则的估计是要使后验概率最大。 哈尔滨工程大学硕士学位论文 2 2 运动估计算法 法。 实际应用中运动估计技术主要分为两大类：像素递归法和块匹配 2 2 ：1 像素递归法 像素递归法的基本思想是，对当前帧运动区域中某一像素五似j ，) ， 在前一帧某一位移处找到一个具有相同灰度值的像素五一。o 一或，y d ，) ， 即： 、 。 石似y ) = 五 一以，y t )( 2 9 ) 式中，d = ( 以，或) 代表真实的运动矢量。 为了改进运动矢量的估计精度和扩大搜索范围，n e t r a v a l i 和r o b b i n s 提出了一种递归估计方法，即改进的估计d 由d m 产生： d “1 = d + 一 ( 2 1 0 ) 式中，为第i 次迭代的更新项，而0 并不表示真实的位移，只是一种 估计。每个像素经数次迭代，可使；逐步趋近于真实的二 设第k - 1 帧像素的位移估计为d “则可定义位移帧差d f d 为： d f d ( x ，y ，d “1 ) = 五( 五，) 一五一i ( 毒一谚，j ，一艺4 )( 2 1 1 ) 估计的目的即要产生新的争，使得l d ，d c 础争4 0 为步长因子。由式( 2 1 2 ) 知： a v d h d f d ( x , y , d “) 】= 耳一1 0 一露4 ，y 一砟1 )( 2 1 3 ) 将式( 2 1 3 ) 代入式( 2 1 2 ) 可得： d = d h 一暑d f d ( x , y , d h ) 咒- l ( 工一矿，_ ) ，一d ，_ 1 )( 2 1 4 ) 式( 2 1 4 ) 即为像素递归法的基本公式，亦称为n e t r a v a l i 和r o b b i n s 公式。 对像素递归法的评价有以下几种； ( 1 ) 用双线性内插加以定义 利用像素递归法时，和以并不一定都是整数，这个时候， 五一。o ，) ，一以) 可用双线性内插加以定义。 ； ( 2 ) 抗干扰能力较差 这种方法仅考虑一个点的灰度，故其抗干扰能力较差。为了从根本 上提高精度和可靠性，在作运动矢量估计时应多考虑几个像素点，即中 心点及其周围相邻点。这样一来不仅可使收敛速度加快，而且可靠性和 精度也可以进一步提高。 ( 3 ) 用梯度信息寻找最优匹配 将下面介绍的块匹配法所得( t ，d ，) 看成是块中心点的运动矢量，那 么这两种方法实际上都是用相邻点信息作运动估计，即二者本质上是相 同的。只不过像素递归法假设代价函数是光滑的，因此用梯度信息来帮 助寻找最优匹配。 2 2 2 块匹配法 按照一般的想法，运动估计应当首先将图像中静止背景和运动物体 1 3 哈尔滨工程大学硕士学位论文 区分开来，然后对运动物体的实际位移进行估值。但块匹配方法却不是 这样，它的思想是将图像划分为许多互不重叠的子块( 一般都是1 6 x 1 6 ) ， 并且认为子块内所有像素的位移量都相同。这意味着每个子块都被视为 运动物体假设在图像序列中，t 时刻对应于第k 帧图像，l f 时刻对 应于第k 1 帧图像。对于第k 帧中的一个子块，在k 1 帧中寻找与其最 相似的子块，这个过程称为寻找匹配块，并认为该匹配块在k 1 帧中所 处的位置就是k 帧子块位移前的位置，这种位置的变化用运动矢量d 来 表示。 图2 1 示出了待匹配与搜索区的几何位置关系。随着图像处理技术 的发展和对处理效率愈来愈高的要求，在很多场合均要求运动矢量 n + 2 一口y 一正一 r f 一 i _ - ； f 第k - l 赣 n 的擅索区 i 呻 第k 赣m xn 搜目 块 图2 i 待匹配块与搜索区的几何位置关系 精确到半像素级。将图像分割成m x n 的小块，并假设块内像素作相同 运动，且只作平移运动。虽然实际上块内各点运动不一定相同，也不一 定只有平移运动，但当m x n 较小时，为了简化运算，上述假设可近似 成立。块匹配法对当前帧图像的每一块，在上一帧的一定范围内搜索最 优匹配，并认为本块就是从上一帧最优匹配块位置处平移过来的。设可 能的最大偏移矢量为( 办。，痧。) ， 则搜索范围为 ( m + 2 x 出赫) x ( n + 2 x 砂。) 如图2 1 中第k 帧搜索块所示 为了算法的方便实现，子块的m 、n 一般取相等值，缸。、砂一都 1 4 哈尔滨工程大学硕士学位论文 取为w ，然而块的大小受到了两个矛盾的约束：块大时。块内各像素作 平移运动的假设易被破坏，影响估计的精度：块小时，则易受噪声影响， 估计不够可靠，而且运算量增加，所需传输的附加信息也增加了。因此 必须恰到好处地选择块的大小，以做到两者兼顾。目前，一般以1 6 x 1 6 大 小的块作为块匹配单元，这是己被实践证明了的折衷结果，能够取得较 好的分割效果。 针对块匹配算法的主要研究分为两类： ( 1 ) 关于搜索初始点、初始方向的确定 通常块匹配算法的初始点都是从原点开始的，为了使搜索更有效， 这类算法研究的重点是解决块匹配运动估计算法如何根据先验知识或 视频图像本身的信息确定当前搜索的初始点和初始方向。例如根据代价 函数利用梯度下降法搜索，利用相邻块的相关性采用自适应预测法确定 当前块的运动趋势，利用图像灰度进行预测等。 ，( 2 ) 关于提高搜索效率的研究 这类研究主要是解决块匹配运动估计的一对矛盾：计算复杂度和运 算质量。快速算法般是通过限制搜索位置来减少计算量，以牺牲运动 估计精度为代价。经典的三步法、四步法、二维对数法、交叉法和菱形 法等都是基于块匹配的运动估计快速搜索算法，它们正是通过减少匹配 点，提高了搜索速度，但可能在搜索时陷入局部最优，得不到最佳结果。 作为一种具有实用价值的方法，要求块匹配法在足够的精度下能实 时实现运动矢量场的估计，并以尽可能少的附加信息传输运动矢量信 息。具体的讲，就是要在满足尽可能提高运动估计效率这一总原则下， 解决块大小的选择，估计精度及运动矢量场的一致性等问题。块匹配法 的前提是块内各像素作相同的平移运动，因此，解决假设不成立时运动 估计也是一个非常重要的。 2 2 3 运动估计中的搜索算法 运动估计算法大致分为以下五类：全局搜索算法；分数精度搜索算 法；分级搜索算法；快速搜索算法和混和搜索算法。 1 5 哈尔滨工程大学硕士学位论文 ( 1 ) 全搜索算法 全搜索算法能为当前帧的给定块确定最优的运动矢量。在预先定义 的搜索区域内，把给定块与所有的候选块进行比较，寻找具有最小匹配 误差的候选块。 全搜索算法的精度是由搜索步长决定的。步长即相邻两个候选块在 水平或垂直方向上的距离。通常，两个方向采用相同的搜索步长。一般 情况下，步长为一个像素。 全搜索算法是最优搜索算法，但是计算复杂度极大，不能满足实时 视频压缩的要求。 ( 2 ) 分数精度搜索算法 在运动估计中搜索步长不一定是整数。可采用分数，这种算法称为 分数精度搜索算法一般来说，为了实现1 k 个像素步长的运动估计， 需要对参考帧进行k 倍的插值。 一 一般来说，半像素、1 4 像素等分数精度搜索算法与整像素精度搜 索相比较，估计精度有较大的提高，特别是对于低清晰度视频。但是， 应用分数像素步长，搜索算法的复杂性会大大增加。 ( 3 ) 分级搜索算法 分级搜索算法的基本思想是从最低分辨率开始逐级进行精度优化 的运动搜索策略。首先取得锚定帧和目标帧的金字塔表示，从上到下分 辨率逐渐变细，从顶端开始，选择一个尺寸比较大的数据块进行一个比 较粗略的运动搜索过程，在此基础上亚抽样，在下一个较细的级别来细 化运动矢量，而新的搜索过程在上一级搜索到的最优运动矢量的周围进 行。 这种算法的优点是运算量的下降比例比较大，搜索比较全面；缺点 是由于要采用亚抽样或者滤波器而对内存的需求增加，另外也可能陷入 局部最优点。 ( 4 ) 快速搜索算法 快速搜索算法和全搜索算法相比，虽然只能得到次优的匹配结果， 但是在减少计算复杂度方面效果显著 ( 5 ) 混和搜索算法 1 6 哈尔滨工程大学硕士学位论文 由于视频序列中物体的运动干变万化，很难用一种简单的模型来描 述，也很难用单一的搜索算法来得到较优的运动矢量，同时大幅度降低 计算复杂度因此，实际上大多采用多种搜索算法相组合的方法，可以 在很大程度上提高预测的有效性和健壮性。 2 3 运动目标函数最小化 2 3 1 鲁棒运动估计 对于运动场的估计，大多数方法都是在有限的图像范围内只存在单 个运动目标。但是在运动估计中经常会出现动作不连续，观测值由于空 间邻域中包含多个运动而出现“断裂”。b l a c k 和a n a n d a n 用鲁棒统计 结构解决这个问题，这个结构用区域内的主要像素点来恢复运动结构， 同时捧出与主要像素点不一致的点，这些不一致的点通常被认为是什夕 点”。 鲁棒估计的主要目标是发现适应数据变化趋势的最佳结构，在此过 程中要同时鉴别并捧除”外点”或”背离的结构”的干扰。由于计算机视觉 领域的应用经常集中在开发构建精确参数模型的优化策略，从而提取出 参数，而且经常会遇到模型不适应的情况，这就引发从事计算机视觉研 究对鲁棒统计产生了日益浓厚的兴趣。 参数a = a o ，a t ，】用于拟合模型1 l ( s ；8 ) ，一组数据观测值 d = d o ，吐，t ，j s ，当观测会值在统计上存在与模型不一致的情况 时，鲁棒估计m 用于解决求取参数值的问题。模型拟合的目标是寻找 参数a 的值，使残差( d 。一( s ；口) ) 最小： 呼n 户能一u 0 ；a ) ，疋) ( 2 1 5 ) 一 其中，正是可选尺度参数。p 是误差范式。当测量中的误差是正态分布 时，最理想的p 函数是二次函数： 1 7 哈尔滨工程大学硕士学位论文 p ( 吃一甜( 剐) ，正) ：盟二：；竺坐 ( 2 1 6 ) q 这里带来了一个标准的最小二乘估计问题。b l a c k 和a n a n d a n 展示如何 通过用p 鲁捧估计器来处理外点问题。鲁棒估计的基本思想是获取数 据的统计特征以除去外点。鲁棒估计的方法很多，如跨越最小中值平 方估计法、h o u g h 法、相似投票法和m 一估计法等。用m 一估计法最小化 ( 2 一1 5 ) 对应于一个最大似然估计。选择不同的p 函数会得到不同的鲁棒 估计器，一个特定的鲁棒估计器的鲁棒性取决于对外点的不敏感程度性 或模型总体误差大小。 2 3 2 松弛算法 运动估计的另一种实现方法是通过参数定义每一种运动，根据前文 的方法定义运动目标函数，通过最优化方法或解非线性方程组的方法确 定运动参数。较常用的确定运动参数方法有松驰算法、梯度下降算法等。 “松弛”一词最初用来描述一组迭代数值方法，用于对联立非线 性方程组求解1 。r o s e n f e l d 和k a k 一将这一词的含义延伸为系列的迭 代分类方法。依据的是二者之问的相似性。在这里，我们给出“松弛” 一词的通用定义。其中既包括了以上这些方法，也包括了一些更新的技 术。 一个松弛过程是一个多步算法，它具备以下性质：1 ) 每一步的输出 量与输入量具有相同的形式，以便算法可迭代远行；2 ) 算法收敛至一个 有界的结果。一些研究者还提出了第三个要求：对任一元素( 在这里，是 任一像素) 的操作仅与该元素的某个有限“邻域”内的像素的状态相关， 这里的“邻域”是明确定义的。 2 4 本章小结 由于本文的运动分割采用的是将运动估计与m r f 相结合的方法， 所以本章首先介绍了运动估计的基本原理和运动表示，并介绍了运动估 1 8 哈尔滨工程大学硕士学位论文 计准则和运动估计技术。最后介绍了鲁棒运动估计方法和求解运动准刚 函数的松弛算法。 1 9 哈尔滨工程大学硕士学位论文 第3 章马尔可夫随机场模型 本章介绍数字图像处理中的m r f 模型，m r f 理论是一种研究分析 物理现象的空问或时间相关特性的概率理论，m r f 理论为描述图像邻域 像素等其它空域上的邻近特征的相互依赖关系提供了一个十分方便而 且有效的建模方法。m r f 借助条件概率的方法来描述邻域像素或特征之 间的关系。在实际应用中，m r f 是一种非常有效的一致性平滑方法，本 文采用m r f 用于分割结果的平滑去噪。 3 1 马尔可夫随机场 维马尔可夫机过程“”( 一阶的情况) 很好的描述了随机过程中某点 的状态只与该点之前的一个点的状态有关系。二维m r f 的平面网格结 构同样可以较好的表现图像中像素之间的空间相关性。 对于定义在二维空间上的图像，也可以将它看为一个二维随机场， 自然也存在二维m r f ，此时必须考虑空间的关系，m r f 使用图论中的 概念表示二维平面上的随机场“”。 可以利用图来直观的表示图像中像素之间的相关模式。用图表示 m r f 的优点在于比较直观、清楚，可以将复杂的问题分解成几个简单的 问题。图的这些特点可以用来表示m r f 中的马尔可夫性，从而为贝叶 斯分析带来一定的帮助。下面分别给出二维方格n x n ( n = 1 ，2 ， ) 中 二维邻域系统和基团的概念。 ( 1 ) 二维邻域系统 设m = m ug ，) e n x ，m uc 册，如果对任何的( f 力n x ， r a a c n x n ，满足 1 ) o ，_ ，) 芒 2 ) 如果有 ，z ) ，那么也力 那么称为以，) 的一个邻域，m 就是n x n 上的一个邻域系统。 2 0 哈尔滨工程大学硕士学位论文 ( 2 ) 基团( c l i q u e s ) 设m 是n x n 上的一个邻域系统，c 是与m 有关的n x n 上的一个 子集，如果有 1 ) c 由单个像元( 平面上的点) 组成，或者 2 ) 如果( f ，) ( m ，h ) ，( f ，力c ，( 州，功c ，就得到( f ，j ) 刀。 那么称c 是与m 有关的一个基团。m 上所有的基团记为c 。下面的图 3 1 和图3 2 分别是一阶和二阶邻域系统和基团的例子： 图3 1 平面上的一阶邻域系统和基团 图3 2 平面上的二阶邻域系统和基团 ( 3 ) 二维m r f 设x = f ，_ ，e 忉是二维方格n x n ( = 1 ，2 ，) ) 上的随机场， m = ( f _ ，) e n n ，嘞c n x 册是邻域系统，如果对一切o ，力n x n 有p 五l 瓦，以力n x ，“，d ( 膏，研= p 乃i 也，蹶d ，就称x 是关 于邻