（通信与信息系统专业论文）运动分割及其在视频编码中的应用.pdf

运动分割及其在视频编码中的应用 摘要 下随着计算机和通信技术的发展，多媒体压缩和通信技术进入了一 个新的时代o ) 随着第二代图象编码的代表m p e g 4 国际标准的出 现，标志着基于对象的多媒体通信技术的趋于成熟。相对于m p e g 1 2 和h 2 6 x 图象压缩标准而言，m p e g 4 为多媒体数据压缩提供了一个 更为广阔的平台。在m p e g 4 视频编码框架中，图象被定义为一组视 频音频对象的组合，通过对于视频音频对象的分析和合成，完成图 象的编码，并进而提供各种操作及功能。 。7m p e g 4 中，一个重要的i n - 1 题就是如何将图象视频分解为一系 列视频对象，具体的说就是视频的运动分割问题，运动分割效果的好 坏直接关系到编码的效率，所以不少学者和研究机构提出了各自的运 动分割算法，这些方法各有特色，但是也都存在着种种不足和缺陷。 本文结合了笔者对运动分割及其相关技术的研究工作，提出了自己的 算法和框架。 第一，对同运动分割密切相关的运动估计的问题进行了研究，分 析了运动估计问题的性质，回顾了主流的运动估计方法及其发展现 状，指出其主要优缺点。针对经典光流估计方法之一的l k 方法， 指出其运用信息的不对称性，提出了l k 方法的对称形式，充分地 利用了两幅图象的信息，采用了迭代求解的技术取代原先的方法，并 在此基础上提出了一种分层的光流估计方案，有效的提高了运动估计 的准确性和运动矢量范围。 第二，在总结分析了现有分割技术的基础上，指出大多数的分割 方法都有赖于相应的应用，特定的分割技术通常只适用于特定的场 合，而且分割效率和准确度的矛盾往往制约和限制了现有算法的应 用。本文特别指出分割决策过程中时间信息和空间信息融合使用的重 要性，在同时权衡了非局部特征和计算效率的同时，本章建立了一个 基于图的运动分割算法，该算法充分考虑了时间和空间信息在运动分 割中的不同作用，通过加权的方法有效地利用了时空信息，防止了过 度分割，取得了很好的效果。 第三，提出了一种基于特征的2 d 网格跟踪和运动补偿框架。传 统的基于2 d 网格的运动补偿方案，没有很好的解决网格生成与对象 内容的符合度，以及网格顶点运动估计的可靠性等问题，造成了运动 补偿过程中纹理映射的质量不佳。本文充分考虑了上述两个问题，采 用了特征跟踪的技术，提出了基于特征网格模型生成方法。受启于 l k 特征跟踪，该算法根据场景中的前两帧的纹理信息和运动信息建 立三角形网格模型，然后用网格跟踪算法对网格模型进行跟踪。这种 网格模型能够有效的提高网格模型的运动估计精度和纹理映射的质 量 第四，本文回顾和总结了已有的视频编码的技术特点和应用范 围，对基于对象的视频编码技术m p e g 4 视频编码进行了研究， 介绍了m p e g 4 编码方案中图象编码的原理及基本框架。) 关键词： 视频编码，运动估计，运动分割，网格跟踪，基于对象， m p e g 4 s p a t i o t e m p o r a l s e g m e n t a t i o n a n di t s a p p l i c a t i o n i nv i d e oc o d i n g a b s t r a c t w i mt h ef a s t d e v e l o p m e n t o f c o m p u t e r a n dc o m m u n i c a t i o n t e c h n o l o g i e s m u l t i m e d i ac o m p r e s s i o n a n dc o m m u n i c a t i o ni s e n t e r i n g i n t oan e wa g e t h ee m e r g e n c eo fm p e g - 4s t a n d a r d s ，r e p r e s e n t a t i o no f s e c o n dg e n e r a t i o ni m a g ec o d i n g ，i n d i c a t e st h em a t u r a t i o no fo b j e c t b a s e d m u l t i m e d i ac o m m u n i c a t i o nt e c h n o l o g y c o m p a r e dw i t hm p e g - 1 2a n d h 2 6 xv i d e o c o d i n gs t a n d a r d s ，m p e g 一4p r o v i d e s am o r eu n i v e r s a l p l a t f o r m i nt h ef r a m e w o r k o fm p e g 一4v i d e oc o d i n g ，i m a g ea r ed e f m e d a st h ec o m p o s i t i o no fa u d i o v i s u a lo b j e c t s v i at h ea n a l y s i sa n ds y n t h e s i s o fa u d i o v i s u a lo b j e c t s ，t h ei m a g e sa r ec o d e d a n dm o r em a n i p u l a t i o n sa n d f u n c t i o n a l i t i e sc a r lb e p r o v i d e d i nm p e g - 4 ，o n eo ft h em o s ti m p o r t a n tp r o b l e m si sh o w t os e g m e n t v i d e oo b j e c t sf r o mi m a g e v i d e o ，e g ，t h ep r o b l e mo fs p a t i o - t e m p o r a l v i d e o s e g r n e n t a t i o n ，w h i c h i s c l o s e l yr e l a t e d t ot h ec o d i n ge f f i c i e n c y m a n yr e s e a r c h e r s h a v ep r o p o s e dt h e i rv i d e os e g m e n t a t i o na l g o r i t h m t h o u g h v a r i o u st h e ya r e a l lr e m a i nk i n d so f p r o b l e m s i nt h i st l l e s i s ，t h e a u t h o r p r o p o s e d h i so w na l g o r i t h ma n df r a m e w o r k ，b a s e d o n p a s t r e s e a r c ho n s p a t i o t e m p o r a ls e g m e n t a t i o na n d r e l a t e dt e c h n i q u e s f i r s t ，m o t i o ne s t i m a t i o n ，w h i c hi sc l o s e l yr e l a t e d t os p a t i o - t e m p o r a l s e g m e n t a t i o n ，i s s t u d i e d t h en a t u r eo ft h ep r o b l e mi s a n a l y z e d ，t h e p o p u l a r m o t i o ne s t i m a t i o nm e t h o da n dt h es t a t u so ft h ep r o b l e m - s o l v i n g a r er e v i e w e da n dt h er e m a i n i n gd e f i c i e n c yi sp o i n t e do u t t h et r a d i t i o n a l l km e t h o di ss t u d i e da n di t sa s y m m e t r yi sp o i n t e do u t i no u rm e t h o d ， i n f o r m a t i o no f t w op i c t u r e si ss y m m e t r i c a l l y u s e da n da ni t e r a t i v em e t h o d i s a d o p t e d i n s t e a do ft h eo r i g i n a lo n e b a s e do n a l lt h o s ea b o v e ，a h i e r a r c h i c a l o p t i c a l f l o we s t i m a t i o ns c h e m ei s p r o p o s e d a n di tc a n e f f i c i e n t l yi m p r o v e t h e a c c u r a c y o ft h em o t i o ne s t i m a t i o na n dt h e e x t e n s i o no fm o t i o nv e c t o r s e c o n d ，b a s e d o nt h ec o n c l u s i o no f e x i s t i n gs e g m e n t a t i o nt e c h n i q u e s ， t h i st h e s i sp o i n to u tt h a tm o s ts e g m e n t a t i o nt e c h n i q u e sd e p e n do ns p e c i f i c a p p l i c a t i o na n d t h ec o n f l i c t sb e t w e e ne f f i c i e n c ya n da c c u r a c yl i m i tt h e i r a p p l i c a t i o n i nt h i st h e s i s ，t h ei m p o r t a n c eo f t h ec o m b i n a t i o no f t e m p o r a l a n ds p a t i a li n f o r m a t i o ni sp o i n t e do u t t h e n ，s i m u l t a n e o u s l yc o n s i d e r i n g t h en o n - l o c a lf e a t u r ea n dc o m p u t a t i o ne f f i c i e n c y , t h i st h e s i sp r o p o s e da g r a p h - b a s e ds e g m e n t a t i o na l g o r i t h m i nt h i sm e t h o d ，b o t ht e m p o r a la n d s p a t i a li n f o r m a t i o na r ec o n s i d e r e db y aw e i g h t e ds u m i tc a ne f f i c i e n t l y p r e v e n to v e r - s e g m e n t a t i o n a n da c h i e v eb e r e rp e r f o r m a n c e t h i r d ，af e a t u r e - b a s e d2 - dm e s ht r a c k i n ga n dm o t i o nc o m p e n s a t i o n s c h e m ei s p r o p o s e d i n t r a d i t i o n a l2 - dm e s hm o t i o n c o m p e n s a t i o n s c h e m e ，m e s hg e n e r a t i o n a n dc o n t e n to ft h e o b j e c t i sn o t a l w a y s c o n s i s t e n t a l s ob e c a u s eo ft h eu n r e l i a b i l i t yo ft h em o t i o ne s t i m a t i o no f m e s h 鲥d ，t h eq u a l i t yo f t h et e x t u r em a p p i n gi nm o t i o nc o m p e n s a t i o ni s n o tg u a r a n t e e d i nt h i st h e s i s ，t h ea b o v e2 p r o b l e m s a r eb o t hs o l v e d ，m e s h g e n e r a t i o nb a s e do nf e a t u r et r a c k i n gi sp r o p o s e d i n s p i r e db yt h el k f e a t u r et r a c k i n ga l g o r i t h m ，w eg e n e r a t e dt h et r i a n g u l a rm e s hm o d e lb a s e d o nt e x t u r ei n f o r m a t i o no ft h ef i r s t2f l a m e ，t h e nm o t i o n c o m p e n s a t i o ni s m a d ea c c o r d i n gt ot h em e s h t r a c k i n ga l g o r i t h m t h e m e s hm o d e l p r o p o s e d h e r ec a ne f f i c i e n t l y i m p r o v e t h e a c c u r a c y o fm e s hm o t i o n e s t i m a t i o na n dt h eq u a l i t yo f t e x t u r e m a p p i n g f o u r t h ，t h e f e a t u r ea n d a p p l i c a t i o n o fe x i s t e n tv i d e o c o d i n g i s r e v i e w e d t h e nt h eo b j e c t - b a s e dv i d e oc o d i n g t e c h n i q u e m p e g 4 v i d e o c o d i n gi s s t u d i e d t h ep r i n c i p l ea n dt h ef r a m e w o r ko fm e p g - 4v i d e o c o d i n g a r ei n t r o d u c e d k e yw o r d s ：v i d e o c o d i n g ，m o t i o ne s t i m a t i o n ，s p a t i o t e m p o r a l s e g m e n t a t i o n ，m e s ht r a c k i n g ，o b j e c t - b a s e d ，m p e g - 4 1 1 引言 第一章绪论 现代社会中，视觉信息占据了很大的比重，据统计人类察觉的信息中有8 属于视觉信息，而且这一趋势将随着数字化技术的进展而继续加强。针对人类视 觉信息的图象和视频技术将在通信、商业和娱乐等各个方面改变我们的生活。在 数字化技术飞速发展的今天，热点之一就是数字电视，多媒体及相关的视频序列 压缩编码技术”】。 在目前为止应用较为广泛的第一代图象编码标准中，图象和视频主要采用波 形表示每一帧图象描述为象素的集合。从场景内容角度来说，这种表示缺乏对 于图象内容的分析和理解，是属于无语义的。波形表示是许多编码标准的基石， 如j p e g f 引，m p e g 1 f 引，m p e g 2 1 “，h 2 6 1 1 引，h 2 6 3 f ”。这些技术虽然达到了很 好的压缩率，但是由于其波形表示的内质使得最终用户的功能受到了限制，不能 随意操作接收的视觉信息。更广义的说，图象和视频的波形表示同场景内容无关， 所以只允许有限的用户交互。 为了达到良好的交互，并且考虑人类感知视觉信息的方式，图象和视频的表 示必须是语义上有意义的，而只有当图象和视频由描述场景中的物体来表示时， 才能达到完全的交互。在交互式视频应用框架中，视觉信息被完全分割为具有意 义的对象和物体，通过对这些物体的描述达到对图象的表示。在这种表示基础上， 可以实现某些功能，如基于内容的检索，数据库浏览，基于内容的图象操作等。 随着计算机和通信技术的发展，多媒体压缩和通信技术进入了一个新的时 代。早在8 0 年代，k u n t i7 】和m u s m a n n j 就提出了基于对象的第二代图象编码理 论，他们认为通过对图象和视频的分析，将其分解为有意义的对象，然后对对象 进行编码和压缩，能够有效地提高编码效果，并能进一步提供更多功能。作为第 二代图象编码的代表m p e g 4 1 9 国际标准的出现，标志着基于内容或基于对 象的多媒体通信技术的趋于成熟。i s o 组织的m p e g - 4 标准的第一版已于1 9 9 9 年1 月正式公布，目前已经进入第二版标准制定的最后阶段。相对于m p e g 1 2 图象压缩标准而言，m p e g - 4 为多媒体数据压缩提供了一个更为广阔的平台，它 更多定义的是一种格式和框架，而不是具体的算法，这就为我们在其框架内部进 行算法和策略研究提供了可能和极大的自由度。与以往的标准相比，m p e g 4 的 视频方面的特色可以归纳为四大方面： 1 ) 基于内容的可交互性。在不作解码的情况下，支持基于内容的处理和码 流的编辑；支持合成图象声音与自然图象声音的合成；支持基于内容的 随机存取。 2 ) 更好的压缩性能。在码率相近的情况下，m p e g - - 4 有比现有标准更好的 视觉效果；支持多路码流( c o n c u r r e n t d a t as t r e a m ) 的同时编码。 3 ) 在不同应用环境下都具有较好的健壮性： 4 ) 支持基于内容的可分级编码。 1 2 问题的提出 由于m p e g 4 国际标准中许多编码技术是建立在图象分析与合成、计算机图 形学、虚拟现实和计算机视觉等基础上，这些新的技术要走向实用化还需要配合 大量的工具和研究，如基于对象的编码和形状的描述就需要图象和视频分割工 具、精灵的编码需要前景，背景的分离和全景图象的生成、基于模型的编码要建 立模型和跟踪模型、三维人脸和身体的编码需要分析和合成工具等。这些技术和 工具不包含在标准之中，而是作为标准的开放部分留待深入研究。 在m p e g 4 视频编码框架中，图象被定义为一组视频- 音频对象( a u d i o v i s u a l o b j e c t ：a v o ) ( j 的组合，通过对于视频音频对象的分析和合成，完成图象的编 码，并进而提供各种操作及功能。所以在m p e g 4 中，一个重要的问题就是如何 将图象视频分解为一系列视频对象，在基于对象的图象分析和合成中，具体的 说就是运动分割的问题。 本文认为，视频序列由对象或物体构成。从语义上对象和物体定义为能被理 解和识别的物体，在数字图象的表示中定义为具有一致运动的象素的集合。同时， 空间一致性是仅次于时间一致性需要考虑的因素。所以，对象就是具有时空一致 性的实体，而将其检测出来的方法就是运动分割技术。本文对于视频序列的运 动分割问题进行了研究，并将其细化为运动估计，分割决策和跟踪三个部分，最 后对m p e g - 4 视频编码框架进行了讨论。 1 3 本文的章节安排和创新成果 综上所述，运动分割技术是m p e g - 4 标准能够在各个领域中得到广泛应用的 基本前提。本文解决的问题有：运动估计，分割决策、二维网格的设计和跟踪。 全文内容安排如下： 第一章首先概述基于对象的多媒体国际标准m p e g - 4 的基本要求，然后指出基 于对象的视频运动分割与上述标准的关系，提出了本文研究的重点。 第二章主要研究了视频编码和分析中的运动估计问题。首先对运动估计的问题 性质进行了分析，然后分别回顾了基于参数模型和基于非参数模型两类 运动估计技术的方法、发展现状及主要优缺点。在总结了现有运动估计 技术的基础上，提出了一种分层的l k 光流估计技术，提高了运动估计 的准确性。 第三章主要研究了基于对象的多媒体应用中的分割问题。在总结分析了现有分 割技术的基础上，指出大多数的分割方法都有赖于相应的应用，特定的 分割技术通常只适用于特定的场合，而且分割效率和准确度的矛盾往往 制约和限制了现有算法的应用。在同时权衡了非局部特征和计算效率的 同时，本章建立了一个基于图论的运动分割算法，该算法充分考虑了时 间和空间信息在运动分割中的作用。实验结果证明，本章提出的基于图 的分割方法，能够有效的防止过度分割，取得了很好的效果。 第四章提出了一种基于特征的三角形网格模型的生成和跟踪方法。首先总结了 基于网格的运动补偿的基本原理，然后比较了多种网格模型的算法和优 缺点。在此基础上，本文提出了基于特征的网格补偿和跟踪算法。该算 法根据场景中的前两帧的纹理信息和运动信息建立三角形网格模型，然 后用网格跟踪算法对网格模型进行跟踪。本文提出的网格模型能够有效 的提高网格模型的运动估计精度和纹理映射的质量。与其它网格模型迸 行比较实验表明：本文算法获得了较为理想的运动补偿效果。 第五章回顾了已有的视频编码的技术特点和应用范围，重点对基于对象的视频 编码技术- - m p e g 4 视频编码框架进行了研究和概述。 综观全文，本论文主要创新性研究成果包括： 1 ) 对经典光流场估计方法之一的l k 方法进行了改进，提出了一种迭代和 分层的光流场估计算法，较为有效的解决了光流估计中的效率和精度的 问题。 2 ) 提出了一种建立在图论基础上的运动图象分割框架，该方法融合了运动 信息和空间信息，在运动分割中达到了良好的效果。 3 ) 提出了一种基于特征的2 d 网格前向跟踪算法，该方法更好的反映了对 象的运动特性，提高了网格的运动估计精度和纹理映射的质量。 参考文献： 1 】c h i a r i g l i o n el ，m p e ga n dm u l t i m e d i ac o m m u n i c a t i o n s ，i e e et r a n s c i r c u i t s a n ds y s t e m sf o r v i d e o t e c h n o l o g y , 1 9 9 7 ，v 0 1 7 ，n o 1 ，p p 5 - 1 8 【2 【3 【4 】 【5 6 7 】 8 9 【l o 1 1 】 w a l l a c eg k ，t 1 1 ej p e g s t i l lp i c t u r ec o m p r e s s i o ns t a n d a r d ，c o m m u n i c a t i o n so f t h ea c m ，1 9 9 1 ，、，0 1 3 4 ，n o 4 ，p p 3 0 - 4 4 i s o i e c1 1 1 7 2 ，m p e g 1 ，i n f o r m a t i o nt e c h n o l o g y - c o d i n go f m o v i n g p i c t u r e s a n d a s s o c i a t e d a u d i o f o r d i g i t a ls t o r a g e m e d i a u p t o a b o u t l 5 m b i t s ，1 9 9 3 i s o i e c1 3 8 1 8 ，m p e g 2 ，i n f o r m a t i o nt e c h n o l o g y - g e n e r i cc o d i n go f m o v i n g p i c t u r e sa n da s s o c i a t e da u d i o ，1 9 9 4 c c i t t , s t u d yg r o u px v r e c h 2 6 1 ，v i d e oc o d e c f o ra u d i o v i s u a ls e r v i c e sa t p 6 4 k b i t s ，1 9 9 0 i t u t d r a f ti t u - tr e c o m m e n d a t i o nh 2 6 3 ，v i d e oc o d i n gf o rl o wb i t r a t e c o m m u n i c a t i o n ，1 9 9 6 k u n tm ，i k o n o m o p o u l o sa a n dk o c h e rm ，s e c o n dg e n e r a t i o ni m a g ec o d i n g t e c h n i q u e s ，p r o c e e d i n g so f i e e e ，19 8 5 ，v 0 1 7 3 ，p p 5 4 9 - 5 7 5 m u s m a n n h g ，h o e a e rm a n d o s t e r m a n n j ，0 b j e c t - o r i e n t e da n a l y s i ss y n t h e s i s c o d i n go fm o v i n gi m a g e s ，s i g n a lp r o c e s s i n g ：i m a g ec o m m u n i c a t i o n ，1 9 8 9 ， v 0 1 1 ，n o 2 ，p p 1 1 7 - 1 3 8 i s o i e c1 4 4 9 6 ，m p e g - 4 ，i n f o r m a t i o nt e c h n o l o g y c o d i n go fa u d i o v i s u a l o b j e c t s ，2 0 0 0 i s 0 i e cj t c l s c 2 9 w g l1n 2 9 9 5 ，o v e r v i e wo f t h em p e g 一4s t a n d a r d ，1 9 9 9 m o s c h e n ie ，s p a t i o t e m p o r a ls e g m e n t a t i o na n do b j e c tt r a c k i n g ：a na p p l i c a t i o n t os e c o n dg e n e r a t i o nv i d e oc o d i n g ，【p h d d i s s e r t a t i o n ，s w i s sf e d e r a li n s t i t u t e o f t e c h n o l o g y , 1 9 9 7 4 2 1 引言 第二章运动估计 由前一章所述，在运动图象分割框架中。运动估计和图象分割是一对相辅相 成的元素，所以如何有效而准确的进行图象内物体的运动估计对于分割决策具有 十分重要的意义。 事实上，大部分视频序列图象在时间上均具有很强的相关性，采用帧间编码 技术可以获得较高的压缩比。利用运动估计和运动补偿技术可以有效地去除图象 帧间冗余度，实现高码率压缩比。对于现在较广泛使用的图象压缩国际标准和建 议，如h 2 6 1 i ”，h 2 6 3 t ”，m p e g 1 1 ”，m p e g 一2 m p e g 4 等，其编码系统的 复杂性一定程度上取决于运动估计技术。对于视频编码算法，其编码效率和性能 很大程度上也取决于运动估计。由此可见，运动估计技术是数字视频处理m 】的基 本问题之一，它可能涉及到图象平面( 二维运动) 或物体运动( 三维运动) 的估 算。 2 2 二维运动估计 2 2 1 二维运动定义 运动图象可表示为空间；和时间f 的函数，r ，f ) ，( ；，f ) r 3 。二维运动是 三维场景的二维投影，所以也被称为投影( p r o j e c t i o n ) 运动，指三维运动在图象 平面上的透视或正交投影，如图( 2 1 ) 所示。对于所有的( ；，f r 3 ，时刻f 和 r = t + f f ( ，是整数，f 是瞬时采样i n - l 辗i ) 间的投影位移，可定义为一个连续 一 ，呻、 时空变量的实值二维位移矢量函数d ，t ；h ti 。二维位移矢量场涉及到这个函数 、 f 珍只 么 投影中心 图象半回 图2 1 投影示意图 f i g 2 - 1d i a g r a mo f p r o j e c t i o n 小倘) 吐( ；以丛r ) 协， 在；，f 为离散情况下，图象序列可以表示为三维离散点阵a 3 ，公式( 2 - i ) 等效于： d o ，七；，) = d ，( ；，r ；，r ) j k 。，】= y k l , r 2 , k ( z - 2 ) 其中，v 是a 3 点阵的采样矩阵。因此，一个二维位移场是二维位移矢量 dr , t ；i a t ) ，( ( 斗a 3 的舱 同样可以定义时刻r 的投影速度函数v 。( ；，f 和二维速度矢量场v ，f ，r ) ，离 散情况下为v i ，】。 观察一个视频序列，每一个象素会随时间而变化，引起这种变化的原因有三 种情况：全局运动，局部运动，光照变化： 1 ) 全局运动或摄像机运动。即使场景中没有任何运动，摄像机的运动产生 一个采集图象的全局位移。 2 ) 局部运动。即场景内物体本身的运动。 3 ) 光照变化8 。如果摄像机和场景内物体均无任何运动，光照的变化也 会引起象素值的变化。 2 2 2 运动估计问题的病态性质 在没有对其运动作任何假设或约束的前提下，序列图象的二维运动估计是一 种病态的问题1 0 】。这是因为二维运动估计一般不满足以下的三个条件： 4 ) 解的存在性：即遮挡问题，无法为覆盖显露的背景象索建立对应。 5 ) 解的唯一性：如果每一个象素的位移分量被当作独立分量，那么未知量 的个数将是已知量个数的两倍，即未知数是方程数的两倍，显然无法满 足解的唯一性的要求。 6 ) 解的连续性：运动估计对于视频图象中出现的观察噪声是非常敏感的。 一个极小的噪声也可能引起运动估计中很大的误差。 由于该问题的病态性质，运动估计的算法需要有关二维运动场结构的附加假 设模型。 2 2 3 运动假设 目前已经提出许多技术用来估计三维运动投影下的二维视在运动，但是由于 任务的复杂度，所有技术和算法都是基于某些假设。在这些假设中，通常有三个 共同的假设：强度不变性，运动的空间连续性和时间连续性。 强度不变性。该假设认为在运动轨迹上，象素值保持不变，其数学表达式为： 巾f ) = ，( 乙；，r 一，) ( 2 3 ) j i ，ti 表示位置为r ，时间为t 的象素强度，r 表示在f 时间内的运动位 l 移矢量。尽管公式非常简单，却是非线性的，在分析运动用的较多的是其线性近 似。将公式右端进行泰勒展开，导出时空约束方程( s p a t i o t e m p o r a lc o n s t r a i n t e q u a t i o n ) 或光流方程( o p t i c a l f l o w e q u a t i o n ：o f e ) ，这将在( 2 4 1 ) 中进一步 讨论。 运动的空间连续性。由于场景由物体构成，物体内象素的运动有其相关性， 所以该假设认为相邻象素的运动有其相似性。空间连续性可以通过一个显式约 束，如h o r n s c h u n c k 方法【】”和l u c a s k a n a d e 方法1 1 ”，也可以通过隐含约束。 空间连续性的假设能够解决孔径效应( a p e r t u r ep r o b l e m ) 。但是，该假设也 会发生错误，典型的是在场景内物体的边界处。在这种情况下，相邻象素的运动 大不相同。运动空间连续性的问题归结为广义孔径效应1 1 3 1 h 】。一方面，需要在 大区域内对运动估计进行约束，另一方面，大区域内可能包含多种运动。这一问 题的解决同时空分割紧密连接。 运动的时问连续性如上所述，二维运动由摄像机和物体的运动组成，可以 认为这些运动随着时间的变化进行着平稳的变化。实际上，通常组成场景的物体 也遵循可预测的轨迹，意味着它们在t a t 时刻，与t 时刻的位置和运动具有很 大的相关性。 但是，运动的时间连续性并不具有普遍性。如突如其来的外力完全改变了象 素的运动，另外出现遮挡问题时，时间连续性假设也无效。 2 2 4 运动估计分类 一般，二维运动估计有两种提法m l 。 1 ) 时刻f 和f + f f 之间的位移矢量估计。 2 ) 时刻t 和h l a t 之间的速度矢量估计。 同时二维运动估算也可以假设为前向运动估计和后向运动估计，后向估计比 较方便，在视频编码中运用较广。 1 ) 前向运动估计中，求解的运动矢量从时刻f 变化到t + ，f 。 2 ) 后向运动估计中，求解的运动矢量由时刻t 变化到，一，。 2 3 基于参数模型描述的运动估计 参数模型旨在描述三维运动( 位移或速度) 在图象平面的正交或透视投影。 例如，三维刚体表面正交投影下的二维运动场模型是一个6 参数的仿射模型，而 透视投影是一个8 参数的非线性模型，同时也存在其它更为复杂的参数模型。与 非参数模型的密度场描述相比，参数模型显得更为简洁，而且不易受噪声影响。 2 3 1 正交模型 假设( j ，y ，z ) ，伍，y 1 ，z ) 分别为物体在，和f + l 时刻的三维坐标。如果三维 m 铡眺 之间的关系为： yy 图象平面 、 ， x 、 z 一 _ ( x ，y ，： 图2 2 正交投影 f i g 2 - 2o r t h o g o n a lp r o j e c t i o n k y ) - - ( ，y ) ( 2 5 ) 从式( 2 - 5 ) ，可以导出仿射模型。 x 2 a i x + a 2 y + a 3 ( 2 6 ) y2 a 4 x + a s y + a 6 正交投影计算上效率较高，而且当物体和摄像机的距离相比物体的深度足够 大时是一个合理的近似。在u l l m a n f i “的经典著作中，提出了三帧上的四点对应 可以得到唯一解，a i z a w a 【i “ 提出的简单的两步迭代法，成为基于三维模型的视 频压缩的m b a s i c 算法的一部分，而b o z d a g i l ”在此基础上给出了改进算法。 2 3 2 透视模型 更符合实际情况的是透视投影。从图( 2 - - 3 ) 可知： k 小( ，害，厂班) = ( 厂等，刳 c z 忉 y y 图象平面 h ， x 多 i “ f ( x ，y 图2 3 透视投影 f i g 2 - 3p e r s p e c t i v ep r o j e c t i o n 导出8 参数非线性模型： 工，= ! ! 兰1 2 1 ! 。7工+口8y+1(2-8) 。= ! ! 兰! 兰1 6 。 a 7 x + a s y + 1 r o a c h ”m 对基于透视模型的方法的收敛性进行了研究，w e n g l i 。) 提出了最大似 然和最小方差估算法，改善了噪声情况下解的正确性。仿射变换和8 参数非线性 变换模型都十分流行，但是还存在基于其它假设的变换模型如1 。 与非参数型运动估计不同的是，参数型运动估计不需要显式地作约束条件的 假设，因为约束条件已经隐含在区域的运动模型当中。运动参数的估计有两种方 法t 一种方法先利用非参数模型求出密集运动场，在此基础上求出物体的运动参 数，类似于三维运动分析。由于运动参数是根据密集运动场得到的( 因此称为运 动参数的间接求法) ，整个算法的性能受非参数型运动估计准确度的影响。另一 种是直接运动参数的估计方法。 2 4 基于非参数模型描述的运动估计 非参数模型将非参数均匀性( 平滑度) 约束条件强加于二维运动场上。该运 动模型需要显式的边界条件才能获取景物的运动信息。非参数约束条件可归纳为 确定性和随机性的平滑度模型，主要有基于光流方程的方法( o f e ) 、象素递归 法、基- y - 块的分析法和贝叶斯法等。 2 4 1 光流场法 基- y - o f e 的方法，试图依据于时空图象亮度梯度来得到一个光流场的估算。 而实际上，来自两副图象的光流估算在特定假设条件下等价于对应运动。这就是 光流场法的基本思想。其具体算法如下： 假设j ( ；，f ) 表示连续时空亮度分布。如果当出_ 。时，沿着运动轨迹上的 亮度保持不变，则有： 掣：。 陋， 出 、 7 其e pr 沿着运动轨迹随f 变化。两边运用微分连锁法，可得光流方程： ( v 巾砂( 五) ) + 掣：。 ( 2 - l o ) + r + 、以i ，tj 其中v fr ，tl - ，表示空间坐标速度矢量，( ，是矢量内积。方程( 2 1 0 ) 、a t 1 是仅给出含两个未知数的标量方程，所以单凭式( 2 1 0 ) 是无法求解光流场。我 们仅能估算出空间图象梯度法线方向的份量，所以必须另外进行假设。光流方程 一般可设定如下假设条件： 1 ) 光流场是光滑的，即可微分的。 2 ) 亮度的偏微分是可以得到的。 3 ) 光流场的运动模型是限定的。 n a g e l 提出基于空间图象梯度守恒的光流场估计。l u c a sa n dk a n a d e 提 出运动矢量在象素块上保持不变。h o r n 和s c h u n c k 提出了速度场；平滑的假 设，并把闯题转变为求光流o f e 误差和速度场局部变化量度的加权最小值： r n j n 叫卜丸爿2 耐 陪) 2 + 滢h 刳2 + 陪门卜 在特定条件下，采用光流方程获得的两幅图象的光流估算等价于运动估计。 但是，光流方法有三个主要缺陷： 1 ) 在运动物体的边界，平滑度约束条件或者运动局部一致性的假设将造成 错误的运动估计。为此，文献【2 2 】提出了导向平滑约束。 2 ) 空间梯度的估计在噪声情况下缺乏健壮性。 3 ) 泰勒系数一次展开，是基于运动较小的假设，不适用于大运动的场景。 2 4 2 象素递归法 象素递归法( p e l r e c u r s i v e ) 的基本思想是，对当前帧运动区域中某一象素， 在前一帧某一位移处找到一具有相同灰度值的象素。从而使位移帧差( d i s p l a c e d f r a m ed i f f e r e n c e ：d f d ) 函数值最小来解决运动估计问题的。 象素递归法可以看作是预测值校正器估值器，具有形式： 小f ；f ) = 坼f ；f ) 小f ；f ) ( 2 1 2 ) j 。p 一r ) 代表位置为；，r 时刻的运动矢量的计算值，d “p ( r ，f ；f ) 代表位 置为；，f 时刻的运动矢量的预测值， ，呻、 “lr ，t ；a ti 是修i e 项。根据象素递归法的基 本思想，( 2 - - 1 2 ) 式也可写为下式，其中k 表示迭代次数。 + l斗l d = d + ( 2 - 1 3 ) 经过一次或多次迭代，可使孑逐步趋近于真实值。一般，我们取前一个象素 的最满意估计值作为下一个象素的预测估值，这个值加上单一的基于梯度的、使 那个象素位移帧差二次方达到最小的修正值。 根据修正项和修正方式的不同，有不同的象素递归算法5 2 3 心】。基本的象素 递归思想，其迭代过程是为了取位移帧差( d f d ) 的最小值。当运动矢量趋向于 真实值时，d f d 趋于零。由此，在f 和t = t + a t 之间的时间段定义d f d 为： z ，r d ( i , d ) 】e ( 。r - k 孑( ；，；r ) ，r + r ) 一，( ；，r ) ( z - - 4 ) 对于基于梯度的优化，如采用最陡下降法，可得如下迭代公式： 孑( + 1 = 孑a v j d f d (