（计算数学专业论文）视频序列中基于边缘信息的运动分割方法.pdf

摘要 近年来，随着m p e g 一4 压缩标准的制定和越来越多数字视频形式的出现，人 们对自动分析视频技术的需求也越来越迫切。在m p e g 一4 压缩标准中，为了实现 视频内容的交互功能，视频序列的每一帧都由视频对象面( v o p ) 决定，而为了 生成这些视频对象面，需要对视频序列中的运动对象进行分割。分析视频的第一 步就是把视频序列分割成代表真实世界中不同物体的区域，而且每个区域都遵循 着各自对应物体的运动方式。实际上，真正有效的分割技术应该能够提供明确的 物体间的划分，以及它们之间相对的深度信息。 运动分割是许多视频分析与应用的必要过程，其目的是把视频序列中的各帧 图像按照不同的运动分割成不同的区域，从而分离出图像中的运动对象。本文运 刚了一种基于边缘信息的运动分割方法，来处理包含前后景两个运动的视频序 列。首先用c a n n y 算法提取较为连续的物体边缘，由边缘的法线方向追踪出法向 运动，然后对两个运动分别作最大似然法，交替估计出运动和各边缘所属运动的 概率，反复迭代直至收敛；再以这些边缘为严格界限，用区域增长法将整幅图像 分割成若干区域，最后由于区域标记过程交替估计出正确的运动层次，以确定最 后的分割。实验结果表明这种改进的运动跟踪和区域标记方法能够得到很好的分 割效果。 关键词；视频分割，最大似然法，运动跟踪，区域增长 a b s t r a c t f o l l o w i n gt h es t a n d a r do fm p e g 一4a n dt h ei n c r e a s i n ga v a i l a b i l i t yo f v i d e oi n d i g i t a lf o r m ，t h e r e i s g r o w i n g d e m a n df o rm e t h o d so f a u t o m a t i c a l l ya n a l y z i n gv i d e o i nt h eo b j e c t b a s e ds t a n d a r do fm p e g - 4 ， i no r d e rt os u p p o r tc o n t e n t - b a s e df u n c t i o n s ，e a c hf r a m eo fv i d e es h o u l d b er e p r e s e n t e di nt e r m so fv i d e oo b j e c tp l a n e s ( v o p ) t h ef i r s ts t a g ei s t h es e g m e n t a t i o no ft h ef r a m e si n t or e g i o n sr e p r e g e n t i n gd i f f e r e n tr e a l w o r ld o b j e c t s w h i c hh a v ed i f f e r e n tm o t i o n e x a c t l y ，t h e i d e a l s e g m e n t a t i o ns h o u l dp r o v i d eac l e a rp a r t i t i o no fo b j e c t sa n dt h er e l a t i v e d e p t ho r d e r i n go fe a c ho b j e c t m o t i o ns e g m e n t a t i o ni st h en e c e s s a r ys t a g eo fm o s tv i d e oa n a l y s i s i m p l e m e n t s ，a n di td i v i d e s f r a m e si n t od i f f e r e n t r e g i o n sa c c o r d i n g d i f f e r e n tm o t i o ns ot h a tt h o s em o t i o no bi e c t sc a nb ea b s t r a c t e d t h i s p a p e rp r e s e n t sa ni m p r o v e dt h e o r e t i c a lf r a m e w o r kf o rm o t i o ns e g m e n t a t i o n b a s e do nt h em o t i o no ft r a c k e de d g e s f i r s t l y ，a b s t r a c tt h e s ee d g e so f o b j e c t sb yc a n n ya l g o r i t h i n ，t h e nt r a c k i n ge d g e sa l o n gn o r m a ld i r e c t i o n t o g e t n o r m a lm o t i o n s e c o n d l y ，a p p l y i n ge x p e c t a t i o n - m a x i m i z a t i o n a l g o r i t h mt ot h et w om o t i o n sa l t e r n a t e l yt oc a l c u l a t et h em o t i o n sa n dt h e r e s p o n s i b i l i t yo fe v e r ye d g e s ，r e p e a tt h es t e pu n t i li ti sc o n v e r g e n t f i n a l l ys e g m e n tt h es e q u e n c ei n t or e g i o n sb yr e g i o ng r o w i n ga l g o r i t h m ， a n dg e tt h e f i n a lr e s u l tb yr e g i o n l a b e l i n g t h ep r a c t i c a lr e s u l th a s p r o v e dt h ev a l i d i t yo ft h ei m p r o v e dm o t i o nt r a c k i p ga n dr e g i o nl a b e l i n g m e t h o d k e y w o r d ： m o t i o n s e g m e n t a t i o n ，e x p e c t a t i o n m a x i m i z a t i o na l g o r i t h m ，m o t i o n t r a c k i n g ，r e g i o ng r o w i n g 观频序刃中墨j 二边缘信患的运动分方法 1 绪论 i p e g 一4 图像压缩标准的制定使得视频分割技术显得尤为重要。视频分割是 指视频序列棱定的标准分割成区域，从而从视频序列里分离出有意义的实体。 在m p e g 一4 标准的图像编码中，为了实现基于图像内容的交互功能，将视频序列 的各帧图像按照不同的视频对象面( v o p ) 来表示，然后对视频对象分别进行编码， 这样一方面提高了编码效率，一方面实现了用户与图像场景内容的交互性，所以 在编码的过程中正确的划分视频对象( v i d e oo b j e c t ) 和层次( 1 a y e r ) 是必不可少 的环节。这也正是视频分割的目的所在，实际上只要运用适当的分裁技术就可以 提取出符合实际的图像对象。 v o p 的运动估测是分析两个或更多帧上的v o p ，确定光流轴以判断下一帧中 v o p 可能出现的位鹭。v o p 的运动补偿是根据v o p 光流轴的取向和光流轴上v o p 自身变化得映射信息，矫正v o p 在时间轴上的运动矢量。运动预测和运动补偿技 术可以去除图像信息中的时间冗余成分，v o p 的运动信息编码可视为从像素向任 意形状的v o p 的延伸。 目前视频分割的技术有很多，基于像素的光流场法 6 ，7 是估计帧与帧之间 的光流场，然后将具有相似运动的像素分组。为了得到可靠的光流场需要对图像 进行平滑，但这样就打破了帧与帧之问的运动边界，割裂了图像的空间连续性， 从而不能精确的提取图像对象。马可夫随机场法( m r f ) 1 ，2 可以加强图像的空间 连续性，但它仍然只考虑像素的分组，也会导致不确定的运动边缘。其他的方法 还有基于模板的块匹配法，将提取到的运动对象作为模板再对后续的视频图像做 一定的度量匹配，来跟踪并提取后续帧中的运动对象。此外基于区域变化的时空 法 9 也是一种常用的方法，这种方法通过检测序列图像中的变化区域和不变区 域，结合时空图像亮度和独立运动区域来对运动物体和静止背景进行分割的。基 r 边缘特征的分割方法已经受到人们的重视 5 ，8 ，本文采用的基于边缘的运动 分割方法是利用视频序列中的两帧图像，对当前帧的边缘进行运动跟踪，将图像 分为i j 订后景两个运动层，再利用区域标记找到合理的分割以提取图像对象。相比 而言，运动分割法有较好的鲁棒性和稳定性，同时因为计算量较小，所以还有着 很高的效率。 1 1 m p e g 一4 图像压缩标准 m p e g 的全穆是运动图像专家组( m o v i n gp i c t u r ee x p e r t sg r d u p ) ，是专门 制定多媒体领域内的国际标准的一个组织 3 ，4 ，2 9 。该组织成立于1 9 8 8 年，由 全世界大约3 0 0 名多媒体技术专家组成。m p e g l ( i s o i a c1 1 1 7 2 ) 是l a p e g 组织于 1 9 9 2 年提出的第一个具有广泛影响的多媒体国际标准。m p e g 一1 标准的正式名称 为“基于数字存储媒体运动图像和声音的压缩标准”，可见，m p e g - 1 着眼于解 决多媒体的存储问题。由于m p e g 一1 的成功制定，以v c d 和】i l p 3 为代表的m p e g l 视频序列中基于边缘信息的运动分害i 方法 产品在世界范围内迅速普及。继成功制定m p e 6 一l 之后，m p e g 组织于1 9 9 6 年推 出解决多媒体传输问题的m p e g 一2 标准。m p e g 一2 的正式名称为“通用的图像和声 音压缩标准”。m p e g 一2 标准最为引人注目的产品是数字电视机顶盒与d v d 。此后， 艘e g 并没有停止前进的步伐，于1 9 9 9 年1 月公布了i s o 的m p e g - 4 ( 视频和音频 对象的压缩) 标准的第版，随后又于1 9 9 9 年1 2 月公布了此标准的第二版。 p e g 一4 的正式i s o 命名为i s o i e c l 4 4 9 6 。m p e g 一4 于1 9 9 1 年5 月首次提出，1 9 9 3 年7 月正式启动，于 9 9 9 年1 月成为国际标准，经历了长达6 年的研究与讨论。 m p e g 一4 从其提出之日起就引起了人们的广泛关注，每个人都对它寄予了很 人的希望。m p e g 一4 的最大创新在于赋予用户针对应用建立系统的能力，而不是 仅仅使用断向应用的固定标准。此外，m p e g 一4 将集成尽可能多的数据类型，例 如自然的和合成的数据，以实现各种传输媒体都支持的内容交互的表达方法。借 助于m p e g - 4 ，我们第一次有可能建立个性化的视听系统。 1 1 1 樯p e g - 4 的基本原理 在制定m p e g 一4 标准之前，运动图像专家组已经制定了两个运动图像的编码 标准，即m p e g l 和m p e g 一2 ：c c i t t ( 国际电报电话咨询委员会，现名国际电信 联盟( i t u ) ) 制定了两个运动图像的编码标准，即h 2 6 l 和h 2 6 3 。这四个运 动图像的编码标准都是把视频序列按时间先后分为帧，而把每一帧图像又分成 1 6 1 6 的宏块来进行运动补偿和编码，这种基于帧、块和像素的编码称为第一 代视频编码方案。这种方案在编码过程中不考虑图像的具体结构，并且由此可能 产生以下主要问题：1 将图像固定地分成相同大小的块，在高压缩比的情况一f 会 产生严重的块效应；2 不能对图像的内容进行查询、编辑、回放等操作：3 没有 利用人类的视觉系统的特性。 m e p g - 4 编码的基本原理是基于图像内容的第二代视频编码方案，并将基于 合成的编码方案也结合在标准中，如上图。第二代视频编码是基于图像的内容进 行编码的，它根据图像的内容将图像分割成不同的视频对象7 0 ( v i d e oo b j e c t ) 。 如在视频电话的应用中经常将讲话的人作为前景视频对象，将其余部分作为背景 视频对象，这样，前景视频对象由于包含有重要的边界和轮廓信息，同时前景对 象的纹理又是理解图像的很重要的附加信息，因而在编码过程中应尽可能的保留 这部分信息。这也是符合人类的视觉系统特点的。在编码过程中，前景对象和背 景对象采用不同的编码策略：前景对象的编码压缩尽可能保留视频对象的细节和 平滑性；对人们不太关心的背景视频对象，可以采用大压缩比的编码策略，甚至 可以不压缩并进行传输，而在解码端用其它的背景拼接成新的背景。基于对象的 视频编码，不仅解决了在大压缩比的编码中产生的块效应，而且能实现很高的压 缩比。采用这样的编码，就能对编码的视频对象的形状、大小、颜色等特征进行 描述，并把这些信息附加在编码的码流上，不用解码就能知道这段码流表示的是 视频序列中基于边缘信息的运动分割方法 怎样的物体及其特征。这种编码能很容易实现国际互联网的图像搜索引擎、基于 内容的图像数据库的检索和交互式的多媒体通讯等新功能。 1 1 2m p e g - 4 图像压缩标准的特点 内容、交互性、灵活与可扩展性是1 v i p e ( 3 4 的三个重要特征。 1 基于内容的交互性 ( 1 ) 基于物体的多媒体数据存取工具 ( 2 ) 基于物体的码流操作和编辑，提供编辑视频物体的手段 ( 3 ) 自然与合成数据的综合编码，提供语法规则和工具，支持自然视频与合 成数据的编码以及码流的混合与同步： ( 4 ) 基于物体的随机存取，能够对在某一限定时间内，以较高的分辨率在码 流内的任一点对物体进行的访问提供高效率的工具；“ 2 压缩 ( 5 ) 改进视频压缩效率，在同等条件下，主观视频质量要好于已有的或其他 正在制订中的标准； ( 6 ) 多并发数据流编码，支持对同一场景多视点的有效编码，对于立体视频 应用，要求具有利用信息冗余的能力，并支持与正常视频有( 或无) 兼容性要 求的条件下的联合编码方案； 3 通用存取 ( 7 ) 易出错环境中的鲁棒性，在发生严重错误的情况下，对各种有线与无线 网络和存储媒体提供纠错和恢复功能，特别注意到满足低比特率应用的要求； ( 8 ) 基于内容的时空可调性，包括物体分辨率的可调性和物体本身的可调性。 前者是指对视频图像的内容和质量，能够以较为精细的间隔实现时域和空域 的可调性，并由提供的工具和语法规则来实现；后者则指在解码后的场景中 加入或删除视频物体的能力。 这些功能无论在其技术先进程度上，还是在它们应用的重要性上都是不同的。此外， 它也说明了标准制订完成后所应达到的宏伟目标，前提是假定能够获得合适的终端设各，并 3 视频序列中基于边缘信息的运动分割方法 且由相关领域的专家投入必需的劳动。如今的绝大多数视频表达途径都是在上述意义 上实现了视觉的功能，把我们的视觉范围延伸到我们从未亲临的时间和空间。 m p e g i 和m p e g 一2 在各自的目标应用上都非常好地实现了这一功能。但是，视觉 还应当容许我们决定采取什么行动。在看见并理解了之后，视觉的下一步是采取 行动，从而完成整个“看”的过程。上述过程在人们的日常生活中是非常普遍的， 展现在人们面前的【盐界应该能够根据人们的行动而改变。m p e g 一4 是第一个实现 了从“看”到采取行动、从被动到主动的运动图像表达标准。下面的例子很好地 说明了m ) e g 一4 与以前的m p e g 标准的区别。由于人们不愿与抽象的事物( 如像素) 打交道，而更喜欢场景中有意义的实体，所以内容的概念是m p e g 一4 视频的核心。 音频采用的也是类似的基于内容的途径。 交互性是m p e g 一4 的另一个重要概念。事实上，由于其本身的复杂性，a v ( a u d i o v i d e o ，音频、视频) 研究被分割到许多技术领域，而各领域都或多或少地在进 行独立的研究。m p e g 意识到改变这种j 状态的时机己成熟，为此提出了一个a v 信 息可以以不同订式显现和处理的方案，这意味着m p e g - 4 试图同时集成自然的与 合成哟a v 物体，包括单声道、立体声和多声道音频，以及2 d 和3 d 或者单舀、 立体或多目视频。 与m p e g 一1 和m p e g 一2 相比，m p e g 一4 诞生在技术发展目新月异的时代。事实 i 二，m p e g 一4 不仅要面对计算能力、内存和可编程性的持续发展，而且要面对音 频和图像处理与表达技术的不断变化。过去一年中，技术环境的快速发展清楚表 明，如果标准不考虑硬件和方法的持续进步而仅仅试图确定惟一方案，就会有很 快过时的危险。因而构成m p e g 一4 基础的另一重要特征是灵活与可扩展性。这一 特征由m p e g 一4 句法描述语言( m s d l ) 提供。根据m s d l 的规范文件，为支持灵活 与刈扩展性，m s d i 。对解码器编程能力定义了三个级别：0 级为不可编程级，解码 器仅具有一种标准算法，该算法在商议阶段需经编码器同意；l 级为灵活级，解 码器能够提供一系列标准化的工具，编码器编码过程中可以灵活地将其配置成某 干1 l 算法；2 级为扩展级，解码器能为编码器提供一套可下载新工具和新算法的机 制。总之，m s d l 赋予了m p e g 一4 吸纳新技术和保持发展的能力，也使用户能够建 兢自己的专用m p e g 一4a v 系统。目前，m p e g 组织正在讨论和制定m p e g 一7 标准。 m p e g - 7 标准的正式名称叫“多媒体描述接口”，并将于2 0 0 1 年1 1 月发布。m p e g 制定这个标准的主要目的，是为了解决多媒体内容的检索问题。通过这个标准， m p e g 希望对以各种形式存储的多媒体结构有一个合理的描述，通过这个描述， 用户可以方便地根据内容访问多媒体信息。在m p e g 一7 体系下，用户可以更加自 由地访问媒体。 4 视频序列中基于边缘信息的运动分割方法 1 1 3 m p e g 一4 的新功能与新应用 i v i p e g 4 的主要目标是提供一套新的编码标准，支持数字a v 信息通讯、存取 和操作的新方法，为各领域融合而成的交互式a v 终端( 即希望中的未来m p e g 一4 终端) 提供一般的解决方案。从这一意义上来说，m p e g 一4 并不针对任何特殊的 应用，而是力图尽可能多地支持对各种应用中均有帮助的功能组。这就是m p e g 一4 以功能为基础的策略。 借助于基于功能的方法，m p e g - 4 就为应用领域出现的各种需求找到了统一 的答案。这些应用领域包括： ( 1 ) 交互式a v 服务，例如基于内容的a v 数据库存取，游戏或a v 家庭编辑 ( 2 ) 高级a v 通讯服务，例如移动a v 终端，改进p s t n a v 通讯或电子商店； ( 3 ) 远程监控，例如战场侦察或安全监视 ( 4 ) t n t e r n e t 多媒体 ( 5 ) 多媒体邮件； ( 6 ) 远程医疗系统； ( 7 ) 无线电与电视广播。 1 2 视频分割系统 视频分割系统的目的是要从序列图像中提取运动对象，以生成视频对象平面 ( v o p ) 。视频分割一般是指从视频序列图像中分离出有意义的运动内容。在某些 具有先验知识的技术领域，如微型遥感，医学成像等图像分割能够提供快速有效 的方法。而对于任意的复杂图像场景不能进行自动的分割，这需要加入人为的交 互参与。视频图像序列比静止的图像包含了更多的运动信息，因此视频分割主要 依据视频序列的运动特性来完成，并希望能够自动分割出一个或几个运动对象的 纹理，形状和运动方式。所以对任意的视频序列进行运动分割时，需要考虑一下 几点性能要求： 1 ) 一般性：视频运动对象分割是针对一般的视频序列的，对待处理的视频 图像没有任何先验的知识。 塑塑壁型：! ! 董王望堡堕璺塑兰垫坌型互堡 2 ) 灵活性：视频运动对象分割允许在发生错误的情况下能够交互的改正一 些错误。 3 ) 复杂性：视频运动对象分割能够在一般的计算机上实时快速的完成，而 不需要高端设备。 4 ) 高质量：视频运动对象分割能用最少的交互干预，自动的，精确的提取 对象的轮廓边缘。 研究视频分割的算法需要定义一种分割准则，其主要依据是视频图像的时空 特性，即在颜色，纹理，空问密度分布以及运动的某些特性来联合分割运动的区 域。 1 3 本文的主要工作 根据总结前人的研究成果，本文提出了一种改进的运动分割方法，利用边缘 信息来处理包含前后景两个运动的视频序列。首先，用c a n n y 算法得到连续的图 像边缘，由边缘的法线方向追踪出法向运动。然后对两个运动分别运用最大似然 法( e x p e c t a t i o n m a x i m i z a t i o na l g o r i t h m ，e m ) ，交替估计出运动和各边缘所 属运动的概率，反复迭代直至收敛；再以这些边缘为严格界线，用区域增长法分 割出各个区域；最后由区域标记过程交替估计出正确的运动层次，以确定最后的 分割。 本文分为四个部分：第一章是绪论，介绍了m p e g - 4 图像压缩标准和视频分 割系统；第二章介绍了些目前常用的视频分割方法；第三章是基于边缘信息进 行运动分割的理论框架和改进算法，包括边缘提取，最大似然法，运动跟踪，区 域增睦等内容；第四章为实验序列图像的测试结果，文中选取了两个典型的视频 实验序列进行测试，并与其它文献的结果进行比较，结果表明本文采用的方法能 得到令人满意的效果。 视频序列中基于边缘信息的运动分割方法 2 视频分割 视频分割是指对图像或视频序列按一定的标准分割成区域，分离出有一定意 义的实体。视频分割的一般方法 3 1 是：首先，对原始的视频图像数据进行简化 以便于分割，这种简化可以通过低通滤波、中值滤波、形态滤波等来完成；然后 对视频图像数据进行特征提取，这些特征可以是颜色、纹理、运动、帧差、位移 i 喙差乃至语义等；最后是进行分割的决策，根据提取的特征决定把哪些视频数据 归为一类，这种决策往往都是基于某种均匀性标准的。从所用的数学工具来看， 视频分割方法主要有三种：基于贝叶斯估计理论的视频分割方法；基于聚类理论 的视频分割方法：基于数学形态理论的视频分割方法，其中比较实用的是后两种 方法，特别是基于数学形态理论的视频分割方法得到了广泛的应用。从分割所在 的域来看，视频分割可以分为空间分割和时间分割，空间分割一般是一种静态分 割，时间分割一般是运动分割。 视频分割还可分为自动分割和半自动分割。视频分割技术是在静态i 虱像分割 的技术基础上发展而来的。静态图像的分割方法一般是利用图像的灰度，边缘， 梯度，纹理等信息进行基于区域的划分，典型的分为单层次方法和多层次方法。 单层次方法大多应用简单，如传统舂勺基于边缘图的方法；多层次方法目前得到了 越来越多的重视，其中使用比较广泛的有形态学滤波法和分水岭算法等 1 。但 是在进行视频分割时这些基于空间的分割方法没有利用到时间轴上的信息，所以 工作量很入而且得出的效果并不理想；由于视频序列是三维场景在二维平面上的 投影，所以我们可以利用视频图像在时间和空间轴上的信息来加以分割。自动分 割的方法目前有以下几种：基于光流场的分割，基于变化区域检测的时空法和运 动跟踪法等；而半自动分割方法有基于模板匹配的对象跟踪法等等。 2 1 块匹配方法 运动补偿是当前视频图像压缩技术中使用最普遍的方法之一。视频的相邻帧 问的运动部分具有连续性，即当前帧上的图像可以看成是前一帧图像的位移。位 移的幅度值和方向在画面各处可以不同。利用运动位移信息与前面某时刻的图像 对当前画面图像进行预测的方法，称为前向预测。反之，根据某时刻的图与位移 信息预测该时刻之前的图像，称为后向预测。m p e g 的运动补偿将画面分成若干 1 6 1 6 的子图像块( 称为补偿单元或宏块) ，并根据一定的条件分别进行帧内预 测、前后预测、后向预测及平均预测。以插补方法补偿运动信息是提高视频压缩 比的最有效措施之一。在时域中插补运动补偿是一种多分辨率压缩技术。例如 i i s 秒或l i o 秒时间隔选取参考子图，对对域较低分辨率予图进行编码，通过 低分辨子图反映运动趋势的附加校正信息( 运动天量) 进行插值，可得到满分辨 率( 帧率1 3 0 秒) 的视频信号。插值运动补偿也称为双向预测，因为它既利用 7 视频序列中基于边缘信息的运动分割方法 了前面帧的信息又利用了后面i 帧的信息。 基r 块的运动估算和补偿是最通用的算法 1 8 ，5 5 在国际标准上已经采用 了基十块的运动补偿进行数字视频压缩。不过这些标准没有指定待定的运动估算 法，于是基于块匹配的运动估算法成为简单自然的选择。基于块运动估算也广泛 用在几个其它的数字视频的应用中，包括用于标准变换的运动补偿滤波。块匹配 法由于它只有较少的硬件要求，所以对于实际运动来说是种比较通周的方法。 块匹配方法的主要思想是通过像素域搜索程序找到最佳的运动矢量估算，对 于f 贞k 中某一一像素( n l ，n 2 ) 的位移，考虑一个中心定位在( n l ，n 2 ) 的1 j ，的模板 块，同时搜索i 跌来找出相同大小最佳匹配块的位置。 块匹配法会凶以p 。因素的差异丽有所不_ j ： 匹配法则，如最大相关系数，最小误差等； 搜索方法，如三步搜索法，交叉搜索法等； 块大小的确定，如分级，自适应等。 块匹配可以依据各种准则来确定模板的大小，包括最大互相关系数( 类似于 相位栩关系数) ，最小均方误差函数( m s e ) ，最小平均绝对差值函数( m a d ) ，最 人匹配像素统计( m p c ) ，最大误差最小函数( m 皿) 等等。寻找最佳块匹配需要在 每个像素所以可能的候选位移矢量上优化匹配准则。这可以通过所谓的“全面搜 索”来实现，这种方法对每个像素的所有可能值评测匹配准则，所以相当费时。 通常情况下，常常使用比这种搜索法快得多的快速搜索方案，如全搜索法，三步 搜索法，交叉搜索法等，它们产生次优化的快速搜索结果。 2 ，1 1 匹配准则 匹配准则实质上是一种误差度量函数，以此为标准衡量两个子块的相似程 度。匹配准则的选取直接关系到运动位移估值的准确性。以下列举几种比较常见 的匹配准则 1 8 ，为了叙述方便，假设子块大小为m x n ，s ( k ，1 ) 表示子块中坐 标为( k ，1 ) 处的像素亮度值。s r ( k + i ，】十j ) 表示参考图像搜索窗中坐标为( k + i ，l + j ) 处的像素亮度值。运动位移矢量表示为( d 1 1 ，d ”，其中蹦表示水平方向位移， d v 表示垂直方向位移。 1 ) 归化互关函数准则 凸n c c p t 2j j = = i s ( k ，1 ) s 。( 走+ i , l + j ) = if = i 埔 埘 ， p , s ( ，z ) s ；( 十f ，z 十，) 圭 一1 - f ll lf t ( 1 ) ( d m d v ) 一( i ，j ) 【m a x e o ：a , ( i j ) )( 2 ) 视频序列中基于边缘信息的运动分割方法 2 ) 均方误差准则 ( i ，j ) = m ”1瓣善荟瞰) 一跗 “伽) d - i ) v ) = ( i ，j ) l r a i n e m s e ( i j ) l ( 4 ) 3 ) 平均绝对帧差准则 e m a d ( i ，j ) 一 赤粪薯i s ( k , 1 ) - - 8 。( k 扎z 州， ( 9 p d v ) 一( i ，j ) l r a i n ( e m a r l ( ，) )( 6 ) 前两种准则在本质上一致的。按这两种准则得到的运动位移矢量要比按平均 绝对帧差准则得到的结果更加准确，更能反应物体的真实运动。h g h a r a v i 和 m m 订1 s 提出的像素差值分类准则不同于以上几种准则。它基于最小风险准则， 在参考图像的搜索窗中选取含匹配像素最多的子块作为最佳匹配块。但由于各种 噪声的干扰，在亮度变化较为缓慢的区域，常有若干参考子块具有同样多的匹配 像素，很难确定哪个子块是最佳匹配块。 为了克服以前这些匹配准则的弱点，以较小的运算量得到较高的估值精度， 文献 1 8 提出一种改进算法：在像素差值分类的基础上，利用人眼对物体边缘运 动比较敏感的特性，提出了边缘像素点分类准则。其基本思路是对每个子块中物 体边缘位置的像素点进行分类，根据像素亮度值的差异分为匹配和不匹配两类， 统计参考帧中各候选子块所含边缘匹配像素点的数目，最多的那个子块为最佳匹 配块。按边缘像素点分类准则进行的运动矢量估值可分为以下四步完成： 第一步：提取当前帧各子块的物体边缘信息，记录边缘位置。选用s o b e l 边 缘检测器从水平和竖直两方向来提取图像子块的边缘信息。s o b e l 边缘检测器用 较小的运算量产生了较好的边缘检测效果，而且受噪声的影响比较小。 第二步：对各予块处于边缘位置的像索点进行分类。 式中：t 是分类门限值，( k ，1 ) 是各子块中物体边缘位置的坐标。t ( k ，1 ，i ，j ) = 1 表示s ( k ，】) 和s 。( k + i ，l + j ) 这两个像素点是匹配的，否则不匹配。 9 d p 十 z ， _r十+娃强 靠& 一 一m 力 女_ 文义 p， n弘 强 ? 视频序列中基于边缘信息的运动分割方法 第三步：统计各候选子块物体边缘位置匹配点的数目，得到边缘像素分类匹 配函数 g i ) = t ( 1 e ，f ，i ，m f ( ，z ) 处于物体边缘位置( 8 ) 第四步：按定搜索方式，如全搜索、：维对数搜索、三步法等，在参考帧 的搜索窗中寻找匹配函数g ( i ，j ) 的最大值。运动矢量为 ( d m d v ) 一( 2 ，j ) j m a x g ( i ，j ) ( 9 ) 2 1 2 搜索方法 块匹配的搜索方法有很多种，比较常用的一种方法叫做全搜索法，在具体应 用中，块匹配法将一副图像分成许多小的矩降块，并假设同一小块中的所有像素 郁有相同的位移。设图像块由们x n 个像素组成，中央矢量z 。= ( x = i , y = j ) ， 它对应十前一帧图像在水平和竖直方向的最大位移均为d ，则在前帧图像内搜 索区中的像素数为( m + 2 d ) ( + 2 d ) 。为使前后两帧的图像块相匹配，通常的 匹配准则为最小绝对帧差原则。具体步骤如下： 1 ) 把当前帧分害l 成长方形或三角形块。 2 ) 从初始猜测值开始，给搜索帧中的匹配四边形( 三角形) 的顶角坐标加 干扰。 3 ) 对每个四边形( 三角形) 来说，找到一个预先指定的空间变换参数，它 使川网( 三) 个匹配角坐标把这个四边形( 三角形) 映射到当前帧中的长方形( 三 角形) 块上。 4 ) 在使用已经计算过的空间变换的四边形( 三角形) 里找到每一个对应像 素的坐标，同时在指定的块和匹配分割块之间计算m s e 。 5 ) 选择生成最小的m s e 的空间变换。 块匹配算法的主要缺点是虽然基于平移的块模型运动估算方法很简单，但在 处理逐帧的块旋转和变形以及运动场中的不连续值时效果不太好；而且运算量很 大，这对于需要进行实时编码的系统，如可视电话、视频会议等是很不利的。选 用何种匹配准则是决定运算量大小的关键因素 2 2 基于光流场的分割 当物体从摄像机前面移过或摄像机移过固定的环境时，图像中会产生相应 的变化，这种变化可用于发现相对运动以及物体的形状：图像中各点的速度矢量 1 0 视频序列中基千边缘信息的运动分割方法 构成了速度场。光流场是可以看到的亮度图案的运动，或称为表观运动。我们可 以观察得到的是光流场，除了一些特殊情况外，一般情况下光流场与速度场相差 不大。因此我们能利用光流信息来估计相对运动。 有许多早期研究工作限制了场景中只能包含一个3 d 剐体运动。1 9 8 0 年， r o a c h 和a g g a r w a l 提出用非线性方程来恢复3 d 运动和结构，方程的求解应用了数 值迭代方法。但由于依赖于初值的猜测，这种方法不能保证唯一解。l o n g u e t h i g g i n g s ，t s a i 年h h u a n g 提出了基于线性方程的计算更简单的技术。随后z h u a n g 和f a u g e r a s 统一了线性算法并由z h u a n g 、h u a n g 和h a r a l i c k 进行简化。但线性算 法对噪声较敏感。考虑用鲁棒算法来解决这一问题。包含多个独立运动物体的光 流场的测定、分割和分析，是一个重要的具有挑战性的任务。t h o m p s o n 提出一种 分割方案，把对比度信息与光流场结合起来，用区域生长方法合并速度相似的碎 片。a d i v 发展一种基于h o u g h 投票方案的计算复杂的分组技术，用校验物体假设 ( v e r i f i e do b j e c th y p o t h e s e s ) 来恢复3 d 运动和结构。光流场可以是稀疏的、 有噪卢的、部分出错的，h o u g h 变换对噪声和部分错误的数据相对来说不太敏感。 m a r k o v 随机场彼用来模拟密集的光流场，找到符合全局最优解的分割。d a r r e 71 l h p e n t l a n d 将图像约束条件应用到一个多模型规则化网络的每一模型上。w a n g 和a n d e r s o n 将鲁棒估计和k 平均聚类方法结合起来，完成多运动群的分割。还有 其他一些用立体图像对或3 d 数据的方法。c h e n 和h u a n g 提出一种两步算法，首先 匹配3 d 线段，然后推断出多个可能的物体。z h a n g f a u g e r a s 发展了假设一检验 范例从两个3 d 帧中获取位移场。z h u a n g 和h u a n g 用盯估计方法来进行3 d 到3 d 多姿 态的鲁棒估引。 基于像素的光流场 6 的概念应用广泛，如刚体运动分析、图像匹配和图像 序列的编码等光流运动分析是计算机视觉中重要的视觉信息处理技术。主要包括 两个步骤：一是由时变图像序列的连续两帧图像计算光流场。二是解释所得的光 流场，检测或标记观察场景中的运动，推断运动参量和运动物体的表面结构。在 存在多个独立运动的物体的情况下，将光流场分割为相关的运动群并估计各自的 运动，这是一个极富挑战性的任务。尤其是光流数据存在噪声并有一部分数据出 错时，这个问题更加复杂。 早期的基于光流分割算法是采用非迭代方法，这样就孤立了运动分割和光 流场之间的关系。光流分割的成功与否与估算的光流场的正确性有着密切的关 系。有一些文献中提到了在进行光流场的估算和分隔时进行贝叶斯法，把运动场 描述为参数场和余量场之和，在m a p 的形式下，光流和分割场的互相依赖关系是 由g i b b s 分布表示的。利用最高信度优先和迭代条件模式算法求解最后的优化问 题。迭代算法可以得到较好的分割效果，但是同时也存在两个问题：一是计算量 大，二是收敛速度依赖于场最，噪声等因素。 由j ：运动对象通常与背景有着不一样的运动，所以可以从分析对象的运动 特征来分割视频序列。运动分割的经典算法是先估算密度场，然后在此基础上对 视频序列中基于边缘信息的运动分割方游 场景进行分割。运动场是三维物体在二维平面上的投影，而我们只能得到图像的 亮度随时间的变化，也就是所谓的光流场。但是光流场并不总是对应运动场，比 如当光照每帧都在变化，而物体并没有运动，这时也会产生光流场，另外在缺少 足够的空间梯度的区域里，运动往往是不可观测的。不过当我们只考虑理想状况 时，这种表观运动就反应了真实运动。基于光流法的分割就是通过研究光流场， 从序列图像里近似计算不能直接得到的运动场，然后根据运动场的特征进行视频 分割。 基于像素的光流法是从亮度不变性这一点出发的。这一条件是假定图像中 像素的亮度不随时间的变化而变化，或者是随时间的变化很缓慢，所以在研究连 续帧图像之间的运动时认定亮度恒定。根据t t o r n 芹d s c h u n k 的理论，图像的亮度对 时间的变化率为零，即 矗 g 蕊) 一 1 1 其中1 ( x ，y ，t ) 为图像亮度，t 为时间。展开后写作： 或者写成 蕊o i 磊d x ，筹萎 豢一。魄丞5 酗盘。撩 ” 豇t + 酗七磊= o ( i 2 ) 式是光流方程，其中t ，是图像亮度的空间导数，：是连续帧之间的微分， u ( x ，y ) 和v ( x ，y ) 是运动的两个分量。由于孔径效应的存在，只有一个光流方程 还不足以决定整个运动，还要加上其它的限制条件，比如平滑限制条件，参数化 运动求解等。 光流场是用于估算运动场的一个比较普遍的方法，它使用的是与投影位移 模型所不同的投影速度模型，但是由于存在孔径效应和遮挡问题，用光流法估算 的二维运动场是不确定的，还需要一些附加条件来模拟= 维运动场的结构，目前 有两种模型可以利用，分别是参数模型和非参数模型。 1 2 视频序列中基于边缘信息的运动分割方法 图2 1 基于像素的光流法运动分割。图中显示了全图范围内利用时空图像 梯度得到的光流场，在梯度较小的区域要用平滑的方式决定台理的运动 g 2 1p i x e l - b a s e dm o t i o ns e g m e n t a t i o nb ym o t i o nf i e l d 2 3 基于变化区域检测的时空法 一股分割视频运动对象的原则是依据视频序列中运动对象的时空一致性。其 中大多数的视频空间分割方法都是基于数学形态方法的，在数学形态方法中分水 岭变换以其优良的性能更是引人注目v i n c e n t 和s o i l l e 提出一种快速实现分水 岭变换的算法后，该分水岭算法就广泛地应用于视频分割中。 基于变化区域检测的时空法 1 0 ，2 4 ，3 1 是通过检测序列图像各帧的变化区 域和不变区域，将运动物体和背景相分离的。基于变化区域检测的时空法是在基 1 二时空亮度和梯度信息的独立运动区间进行图像分割的。通常情况下，为了消除 i 噪声利减小误差，都是选取邻近帧来检测变化区域的。分割过程分为参数模型和 非参数模型两种。 2 3 1 参数模型的分割方法 h o t t e r ； h 1 、h o m a 提出了是用参数模型的分层结构的自顶向下法，由于对不同 的运动物体可以计算不同的运动参数，所以可将不同的运动物体分割。步骤如下： 1 ) 先将当前帧通过变化检测分为变化区域和不变区域，每一个空间连续的 变化区域被看作是一个实际的物体。 2 ) 对每一个物体从时空亮度梯度直接估算出不同的参数，用最小二次方判 别法将参数模型从当前帧到后续帧你和到变化区域中去。 3 ) 如果运动补偿的预计误差比较大，就把这个区域分割成较小的区域，进 行层次出理，直到所有的区域都得到精确的补偿。 基于变化区域检测的时空法不需要光流法中光流的估算和特征点的对应，但 是依赖于时空图像的亮度梯度，所以精度容易受到噪声的影响，因为亮度梯度对 噪声非常敏感。 视频序列中基于边缘信息的运动分割方法 2 3 2 非参数模型的分割方法 非参数模型的分割方法的算法主要是考虑各象素点的统计特征，这种分割方 法町分为以下三个步骤： 1 ) 首先比较相邻两帧图像的变化得到初始的变化检测模板，由于物体运动 导致的亮度发生变化的每个像素都在模板中标记出来。为了保证视频对象的分割 在订、j 问上的稳定性，而不至于由于视频对象的r 一部分在某一时刻停止运动时导致 视频对象_ ；f 5 分或全部丢失，采用一个变化检测模板的存储器，根据视频序列自动 的存储器的时间深度l ，这样只有某个像素在这之前的l 个变化检测模板中至少出 现。次，那它就被标记为亮度改变模板的像素。 2 ) 由于亮度改变的像索包括哪些由于物体运动而显现出来的背景区域像 素，冈为将变化检测模板减去这部分未覆盖背景区域就可以得到物体模板。为了 得到未覆盖背景区域需要计算变化区域的运动向量，如果运动向量的起始点都在 当前的变化检测模板内，这该像素被视为前景对象，否则为背景。 3 ) 最后根据当前帧的边缘图像来调整物体模板一完成分割算法。有些方 法进一步考虑了空间分割的结果，将依据时间分割得到的区域和依据形态学算法 空问分割得到的区域进行比较，如果空间分割区域大部分时间分割区域内，则整 个空间分割区域被看作前景对象，否则当作背景。 2 4 运动跟踪法 一般来说，三维空间物体的运动在时间上表现出平滑性。运动跟踪法 2 5 的思想是根据视频对象的先前状态来估计它的当前状态。现在采用跟踪物体的运 动轨迹来进行视频分割的方法得到了人们的重视。运动跟踪法的基础是图像帧上 的特征匹配或者光流估算以及描述实时运动的动态模型。跟踪算法的性能取决于 它所采用的动态模型的准确性，动态模型大致分为两大类：一种是三维点的图像 、p 轨迹的二维运动模型；另一种足代表物理运动的动力学特性的三维运动模 型。 两利，模型都需要依次完成特征提取，特征匹配，运动分析等三个步骤。分 剖筇法通常重提取对象的特征入手，可以用来跟踪的特征包