（计算机应用技术专业论文）运动估计算法优化技术研究与应用.pdf

运动估计算法优化技术研究与应用 摘要 论文题目：运动估计算法优化技术研究与应用 专业：计算机应用技术 硕士生：汤子成 指导教师：罗笑南教授周凡讲师 摘要 随着数字电视、网络视频流等技术的飞速发展和广泛应用，对数字多媒体信 号的存储，处理以及传输的要求变得越来越高，视频压缩技术逐渐成为媒体、广 播的最基本组成部分。另一方面，近年来国际电信联盟( r r u ) 和国际标准化组 织( 1 s o ) 提出了一系列视频编码的国际标准，如m e p g - 1 ，m e p g 2 ，m e p g - 4 ， h 2 6 3 以及h 2 6 4 等。视频编解码的效率得到了很大程度的提高，但同时也带来 了运算量增加的问题。运动估计( m e ) 和运动补偿( m c ) 技术可以有效的去除 图像序列中的时间冗余，减少帧间的时间相关性，因此该技术被广泛应用于各种 视频压缩的标准中。运动估计是视频编码中计算复杂度最大的部分，因此提高运 动估计的速度和精确度一直是视频编码研究中的热点。 本文首先对视频编码的原理和基本概念进行了简单的阐述，然后介绍了当前 应用较广泛的视频编码标准；并针对运动估计中的块匹配法，介绍了其原理和匹 配准则，详细研究了几种著名的快速搜索算法，对几种算法的性能优劣进行了对 比。接着本文参考已有的运动估计算法的思想，在此基础上提出一种新的改进算 法近圆形可伸缩环快速搜索算法( c f r f s ) 。该运动估计算法选择近似于圆 形的搜索模板来进行块匹配算法的第一步匹配过程，并通过阙值判断对近圆形模 板的大小进行选择，从而达到在较快的搜索速度的情况下保证了匹配的精确度。 最后通过实验对比，证明了本算法有与u m h e x a g o n s 算法相近的效果，但在速 度上却有显著的提高。本文的算法在视频领域有着显著的意义，在网络实时视频 监控领域将会有相当广泛的应用。 关键词：视频编码、运动估计、运动补偿、近圆形搜索模式、提前终止 运动估计算法优化技术研究与应用 t i t l e ：r e s e a r c ha n da p p l i c a t i o no ni m p r o v e m e n tt e c h n o l o g yo fm o t i o ne s t i m a t i o n a l g o r i t h m m a j o r ：c o m p u t e r a p p l i c a t i o nt e c h n o l o g y n a m e ：t a n gz i c h e n g s u p e r v i s o r ：p r o f e s s e rl u ox i a o n a n ；i n s h - u c t o rz h o uf a n a b s t r a c t w i t ht h er a p i dd 耐o p r n e n ta n de x t e n s i v ea p p l i c a t i o no fd i g i t a lt e l e v i s i o na n d i n t e m e tv i d e os t r e a m i n gt e c h n o l o g y , t h er e q u i r e m e n t so fd i g i t a lm u l t i m e d i as i g n a l s t o r a g e ，p r o c e s s i n ga n dt r a n s m i s s i o na l eg e t t i n gl 缸g h e ra n dh i g h e r v i d e oc o m p r e s s i o n t e c h n o l o g yg r a d u a l l yb e c o m e st h eb a s i cc o m p o n e n t so fm e d i aa n db r o a d c a s t i n g o n t h eo t h e rh a n d , i nr e c e n ty e a r s , n ua n di s oh a sp u tf o r w a r das e r i e so f i n t e r n a t i o n a l v i d e oe n c o d es t a n d a r d ss u c ha sm e p g - 1 ，m p e g - 2 ，m p e g - 4 ，h 2 6 3a n dh 2 6 4a n d s oo i lt h ee f f i c i e n c yo f v i d e oc o d e ch a sb e e ng r e a t l yi m p r o v e d ，b u ti ta l s ob r i n g st h e i n c r e a s ei nc o m p u t a t i o n m o t i o ne s t i m a t i o n ( m e ) a n dm o t i o nc o m p e n s a t i o n ( m c ) t e c h n o l o g yc a ne f f e c t i v e l yr e m o v et h er e d u n d a n c yo f i m a g es e q u e n c a , r e d u c et h et i m e c o r r e l a t i o nb e t w e e nf r a m e s ，h e n c et h i st e c h n o l o g yh a sb e e nw i d e l yu s e di nv a r i o u s v i d e oc o m p r e s s i o ns t a n d a r d s m o t i o ne s t i m a t i o ni st h em o s tc o m p l i c a t e dp a r ti nv i d e o c o d i n g , i m p r o v i n gt h es p e e da n da c c u r a c yo f m o t i o ne s t i m a t i o nh a sb e e na h o ts p o t i nv i d e ee n c o d ed o m a i n t h i sp a p e r f i r s t l yi n t r o d u c e st h ep r i n c i p l e sa n db a s i cc o n c e p t so f v i d e ne n c o d i n g , t h e no nt h ec u r r e n ta p p l i c a t i o no f t h ew i d e rv i d e oe n c o d i n gs t a n d a r d a n dt h e na g a i n s t t h em o t i o ne s t i m a t i o nb l o c km a t c h i n gm e t h o d ，i n t r o d u c e st h et h e o r ya n dm a t c h i n g c r i t e r i a w ec o m p a r et h ep e r f o r m a n c eo fs e v e r a lf a m o u sf a s ts e a r c ha l g o r i t h m sb y d e t a i l e ds t u d y t h e nr e f e r e n c et ot h ec u r r e n tm o t i o ne s t i m a t i o na l g o r i t h m s ，w ep u t f o r w a r dan o wm o t i o ne s t i m a t i o na l g o 枷 1 m f r f s ( c i r c l e - l i k ef l e x i b l ei h n g f a s ts e a r c h ) a l g o r i t h m t h i sa l g o r i t h mu s e sac i r c l e - l i k ep a t t e r nf o rt h ef i r s ts t e po f b l o c k - m a t c h i n gs e a r c h ，a n dt h r o u g ht h et h r e s h o l dt oc h o o s et h es i z eo ft h ec 曲 c l e - l i k e p a t t e r n t h e s ec a l le n 吼n et h em a t c h i n gp r e c i s i o ni naf a s tp a c eo fs e a r c h i n g f i n a l l y , 运动估计算法优化技术研究与应用a b s t r a c t b ye x p e r i m e n t a lc o n t r a s t , t h ec f r f sa l g o r i t h mi sp r o v e ds i m i l a rr e s u l t sw i t l l u m h e x a g o n sa l g o r i t h m ，b u th a sa ne v i d e n ti n c r e a s ei nt h es e a r c h i n gs p e e d t h i s a l g o r i t h mw i l lh a v es i g n i f i c a n tm e a n i n gi nt h ef i e l do f v i d e oc o d e o , a n dw i l lh a v ea v e r yw i d eu s a g ei nr e a l - t i m ev i d e os u r v e i l l a n c ef i e l d k e y w o r d s ：v i d e oe n c o d i n g , m o t i o ne s t i m a t i o n , m o t i o nc o m p e n s a t i o n c i r c l e - l i k es e a r c h p a t t e r n , h a l f w a y - s t o p 1 1 1 运动估计算法优化技术研究与应用第1 章综述 第1 章综述 近年来，随着网络通信技术和多媒体传输技术的飞速发展，图形图像、视频 处理和计算机网络技术日趋融合。由于人眼对运动物体比对静止物体更加感兴 趣，所以对运动图像的分析和处理也越来越引起人们的浓厚兴趣。运动估计是数 字视频处理和计算机视觉领域的一个非常重要的分支，它在视频监控、视频压缩 编码、人工视觉、目标跟踪等多个领域都有相当广泛的应用。因此，对运动估计 算法的研究具有十分重要的意义。 1 1 研究背景 早在视频图像出现的时候，人们就已经意识到视频信号在时间域上存在着冗 余，多年以来，人们一直不断在数字图像压缩的领域进行研究，并在理论和实际 应用中都取得了很大的成果，目前在视频编码技术中主要包括三大类：运动补偿 以去除时间域的冗余；变换编码以去除空间域的冗余；熵编码以去除统计上的冗 余。运动估计的作用就是要尽量使预测的运动矢量精确，以减少帧与帧之间的冗 余，并使重建的图像接近原始图像。 表1 1 冗余类型及压缩方法 冗余类型产生原因压缩方法 空间冗余帧内相邻像素间的线性相关性预测编码和变换编码 时间冗余帧间像素之间的相关性运动估计和运动补偿 统计冗余每个像素值都用相同的比特数表示熵编码 视觉冗余 人眼对亮度信号的视觉敏感性不同 量化 目前，国际电信联盟( i t u ) 和国际标准化组织( i s o ) 公布的视频压缩编 码标准有m e p g 系列以及h 2 6 x 系列。这些压缩标准的实现，首先是要去除视 频序列中的空间和时间上的冗余。d c t 变换是一种无损恢复的可逆数学变换， 所以经常被用在去除视频信号的空问冗余上；在去除视频信号的时间冗余上，则 是通过运动估计和运动补偿来完成。由于运动估计中的块匹配法在算法时间复杂 运动估计算法优化技术研究与应用第1 章综述 度和预测精度上都有较好的表现，故目前的视频压缩算法如：m e p g 1 ，m e p g 2 ， m e p g - 4 以及h 2 6 4 等都采用基于块匹配的运动估计算法来进行运动矢量的预 测。因此，寻找更加快速，更加精确的块匹配运动估计算法，仍然是人们不断努 力追逐的目标。 1 2 基于块匹配的运动估计技术概述 块匹配( b l o c k - m a t d m g ) 算法【习是使用最广泛的运动估计算法，已被许多视频 编码标准如m p e g - 1 、m p e g - 2 以及h 2 6 、h 2 6 2 、h 2 6 3 等所采用。相对于其它 算法，如光流法( o p t i c a l 缸o w ) 【4 】及像素递归法( p c l r e e u r s i v e ) t 5 1 ，块匹配算法的计算 复杂性最低。 基于块匹配的运动估计方法，假设图像序列的最小运动单位是若干相邻像素 的集合( t l p 块，b l o c k ) 。根据先验的运动模型在相邻帧问进行全匹配，计算最优匹 配下的块运动参数，从而得到运动场的粗略估计。此方法的精度与速度依赖于运 动模型和匹配算法的选取。 1 2 1 基于块匹配的运动估计算法的研究点 基于块匹配的运动估计算法的性能取决于以下三个因素：1 搜索策略；2 匹 配准则；3 搜索范围参数。其复杂度亦由上述三个因素决定。显然，通过选择适 当的搜索策略、减少匹配准则的复杂性或缩短搜索距离可以降低块匹配算法的复 杂性。这就决定了基于块匹配的运动估计算法研究必须解决以下几个问题： ( 1 ) 搜索起点的选择 由于参考帧所对应的原点往往不是最优匹配点所在的位置，所以为了缩小且 标的搜索范围，缩短搜索起点与最有匹配点之间的距离，许多算法都采用了某种 方法预测目标在下一时刻可能出现的位置，并以其作为搜索范围的原点。 2 运动估计算法优化技术研究与应用 第1 章综述 ( 2 ) 匹配准则 为了检测当前帧中的匹配块与参考帧中候选块的相似度，必须定义一定的匹 配准则。常用的匹配准则有几种：平均平方误差( m e a n s q u a r e e r r o r ，m s e l ，平 均绝对误差( m e a n a b s o l u t ed i f f e r e n c e ，m a d ) 和归一化互相关函数( n o r m a l i z e d c r o s sc o r r e l a t i o nf u n c t i o n ，n c c f ) 。因为不需要乘法运算，平均绝对误差m a d 是最常用的匹配准则。但这些匹配准则通常要求块内所有像素都参与计算，研究 者们从抽样定理得到启发，运用在搜素区内只选取部分搜索点进行运动估计的思 路，从块内选取一定数量的像素来计算m s e 或m a d 也达到了相同的效果，这样 做最直接的好处是减小了计算量，提高搜索速度。 ( 3 ) 块匹配算法( b m a ) 全搜索法是最直接的块匹配算法，它通过对搜索窗中所有测试点的检查来获 得最优匹配点的运动矢量。全搜索算法虽然可以获得最精确的运动矢量，但由于 计算复杂性高，所以并不实用。对于有n 个点的块进行全搜索时，计算复杂度是 o ( n ) 。为了降低全搜索算法的计算复杂度，研究者们提出了很多减少搜索窗尺寸 或测试点数目的块匹配算法。最常用的方法有三步搜索法( t h r e e - s t e pa l g o r i t h m ) 1 6 1 ， 二维对数搜索法( t w o - d i m e n s i o nl o g a r i t h m i cs e a r c ha l g o r i t l l i n ) 川以及多层块匹配算 法( ( h i e r a r c h i c a lb l o c k - m a t c h i n ga l g o r i t h m ) 嘲。它们将计算复杂度降至数量级 o ( 1 0 9 n ) ，利用合适的硬件可以实时实现的。因此这些算法己成为发展新算法的 基准。 1 2 2 块匹配算法的研究动向 目前，研究者们基于这些成熟的算法，提出了一些新的混合搜索算法【9 l 。它 们的主要思想是首先对目标的运动类型进行预测，使用预先定义的阈值判断其是 否为静态，接着利用合适的搜索策略得到最佳匹配运动矢量。由于这种思路适用 于不同的搜索策略，因此在真实世界的视频序列运动估计中得到广泛的应用。 另一些减少检测点数目的算法是在计算块匹配误差( b l o c kd i s t o r t i o nm c a s l t r o ， b d m ) 时使用中途停止( h a l 所a y 咖d 1 删技术。在这种算法中，候选块的部分变形 3 运动估计算法优化技术研究与应用第1 章综述 ( t h e p a r t i a ld i s t o r t i o n ) 被与当前块的最小总变形相比较。如果候选块的部分变形大 于当前块的最小总变形，则该矢量不满足要求。这些算法中的比较运算较之于 m a d 匹配准则中的乘法运算，代价是相当低的，因而可以大大减少匹配准则的 计算复杂度。 尽管研究者们己经提出了很多基于块匹配的运动估计算法，但由于理论和实 际中所存在的难于解决的问题，使得实时实现运动参数估计及精确估计运动参 数，始终是基于块匹配的运动估计问题所固有的困难。自从运动估计技术的研究 开展以来，人们就在不遗余力地寻找克服这些困难的办法，并且提出了许多快速 块匹配算法，但时至今日，令人遗憾的是仍没有找到满意的最佳方案。进入九十 年代后，随着计算机、仿生学、分形学、数理统计学、计算机视觉等多门与运动 估计密切相关的学科的迅速发展，运动估计领域出现了许多新的研究方向，它们 或许会为克服甚至彻底解决这些困难提供一个契机，未来的研究方向将集中在以 下几个方面。 ( 1 ) 基于视频对象的运动估计研究 m p e g - 4 采用现代图象编码方法，利用人眼的视觉特性，抓住图象信息传输 的本质，从轮廓纹理的思路出发，支持基于视觉内容的交互功能。而实现基于 内容交互功能的关键在于基于视频对象的编码，为此m p e g - 4 引入了视频对象面 v o p 的概念。这一概念根据人眼感兴趣的一些特性如形状、运动、纹理等，将 图像序列中每一帧中的场景，看成是由不同视频对象v o p ( v i d e oo b j e c tp l a n e ) 所 组成的，而同一对象连续的v o p 称为视频对v o ( v i d o ao b j e c t ) ，因此要求研究 基于视频对象的运动估值算法，这里也包括全局运动估计( g l o b a lm o t i o n e s t i m a t i o n ) 、前景运动物体提取、背景( s p d t c ) 生成、处理形状( s h a p e ) 和透明 ( t r a n s p a r e n c y ) 信息等内容的研究【l i 】。 ( 2 ) 多阶段的运动估计算法 为了克服全搜索法过于复杂的缺点，各类运动估计快速算法应运而生。一些 算法【1 2 j 3 减少了匹配准则的计算量，另外一些减少了搜索点【1 和m ，还有一些缩小 了搜索范围。但现有的运动估计技术各自存在着优势与缺陷，因此，通过方法之 4 运动估计算法优化技术研究与应用 第l 章综述 问优势互补、相互结合所产生的混合搜索算法1 9 1 可以获得杰出的结果。较少一些 的算法还将减少匹配准则的计算量与减少搜索点组合在了一起，通过判断物体的 运动范围，混合算法可用于不同的运动估计算法。由此所建立的运动估计的多阶 段模型己成为运动估计技术发展的一个趋势。 ( 3 ) 可变块匹配的运动估计算法 传统的块匹配运动估计算法基于这样一个基本假设，物体的运动幅度较小， 即块之间的移动很小。基于此基本假设，可以得到块匹配运动估计算法的其他假 设，其中最常使用的两点为：1 ) 在当前帧与参考帧中，块中的各像素具有相同 的移动距离；2 ) 块匹配误差( b l o c kd i s t o r t i o nm e a s u r e ，b d m ) 随着匹配点逐渐远 离全局最小b d m 点而单调递增。但是，如果当前帧与参考帧之间的块存在旋转、 变形或者不连续，则块匹配算法就不适用了。为了解决这一问题，产生了一种可 变块匹配( d e f o r m a b l eb l o c km a t c h i n g ) 1 蛐1 】的运动估计算法。在可变块匹配中，当 前帧被分割成三角形、矩形或者任意四边形，在给定的空问变化规则下，在搜索 帧内寻找最匹配的三角形或者四边形在仿射变换( 只有六个独立变量) 的情况下， 三角面片( 每个节点两个方程) 提供了充分的自由度；透视变换和双线性变换有八 个自由变量，四边形面片提供了求解的方法。因此，三角面片以及四边形面片在 可变块的运动估计中是非常适用的。还有一类自适应块的运动估计算法 2 2 ，2 3 1 ，即 根据m s e 的大小来自适应改变匹配块大小，或者根据可变块的大小自适应地调 节搜索范围的大小。 可变块匹配虽然可以提供更好的运动估计精确度，但是在6 - 8 维变量空间上 的搜索较之两维空间，则显著增加了运动估计的复杂性。可变块的运动估计算法 同样基于某个假设，即当前帧中只能分割出一个移动物体。否则，只用一个空间 变换是无法估计多个局部移动的，因此为了解决多目标的运动估计，人们开始了 对规则和自适应网格划分的研究。 ( 4 ) 基于小波变换的多分辨率运动估计算法 m p e g - 4 标准提出后，考虑到硬件实现的可行性逐渐提出了许多新的基于小 波理论【2 抛6 1 和基于遗传算法思想2 刀的运动估计算法。这些方法各有千秋，但都 5 运动估计算法优化技术研究与应用 第1 章综述 有一个共同的发展趋势，即运动估计算法中的匹配块不再局限于矩形，可以自适 应地改变其大小和形状，且搜索路径趋于多样化。 一般的块匹配算法由于块的大小固定，因此存在如何选择合适大小的块的问 题。块太小时，对于大范围运动的场景，常常无法估计出真实的位移；而块太大 时，由于块内像素运动的不一致，可能无法得到精确的运动估计参数。为了解决 这一问题，产生了另一种可变块大小的运动估计方法多分辨率运动估计 【2 8 捌。它通过一个分辨尺度逐渐减小的过程来实现由粗到细的运动估计，不同尺 度采用不同大小的块，从而获得可靠性高、一致性好的运动矢量场。 ( 5 ) 半像素技术 在真实世界的视频序列中，帧与帧之问的位移并非总是与整数像素网格相关 的。为了增加运动预测的精度，研究者们提出了半像素( h a l p i x d ) 技术【3 0 3 。运 用半像素技术，上面提及的几乎所有算法都能获得半像素精度。许多编码标准， 例如m p e g - i 2 和h 2 6 2 h 2 6 3 都将运动矢量的半像素精度作为解的次要选择。 ( 6 ) 运动补偿后处理技术的研究 在h 2 6 1 ，m p e g - 1 以及m p e g - 2 中，由于每一个1 6 x 1 6 的矩形块都仅对应一 个运动矢量的估计值，因此可能造成运动补偿后的恢复图像具有可视块效应 ( v i s i b l eb l o c k i n ge f f e c t s ) t 3 冽。为了对付这种人造块效应，h 2 6 3 中采纳了凸面坐 标投影( p r o j c o t o no n t oc o n v e xs “p o c s ) 后处理技术以及非线性滤波技术等重 叠运动补偿技术。 1 3 本文的主要研究工作 本文在深入分析了目前的块匹配算法的基础上，提出了一种基于运动矢量分 布特征的具有近圆形可伸缩模板的块匹配算法。通过实验结果证明，在匹配精度 和运算复杂度上，本算法都取得了优秀的效果，具有理论研究和实际应用的意义。 本文的章节结构如下： 6 运动估计算法优化技术研究与应用第1 章综述 第一章综述部分。主要介绍本课题的来源及研究背景，对运动估计的研究现 状、应用和研究前景进行了概述。 第二章阐述了运动估计算法的原理和详细介绍了图像序列的常见运动估计 算法，并比较各种搜索算法的搜索策略和模板，分析它们的适用范围和优劣。 第三章在分析了现有的运动估计算法，并参考u m h e x a g o n s 算法的部分思 想，针对该算法的不足，提出一种具有自适应搜索区域的快速搜索算法- i 匠圆 形可伸缩环快速搜索算法( c f r f s ) 。 第四章对本文提出的c f r f s 算法进行实现和验证，并在算法复杂度和精度 方面进行分析。并模拟了该算法在视频监控方面的应用。 第五章总结了本文所做的工作和研究成果，指出研究的不足并提出对未来研 究的展望。 7 运动估计算法优化技术研究与应用 第2 章运动估计算法模型 第2 章运动估计算法模型 视频序列实际上是一个静止图像的序列，当它们以每秒不小于2 4 帧的速度 连续显示的时候，由于人眼的视觉暂留效应，看起来就是连续的图像。因此，在 一般情况下，相邻帧间的内容实际相差不多( 除了场景切换等) ，有很大一部分 甚至是完全一样的，所以帧与帧之间存在着很大的时间相关性，即时间冗余 ( t e m p o r a lr e d u n d a n c y ) 。通过运动估计可以有效的去除时间冗余，保留帧间的 有用信息，大幅度提高视频压缩的效率。运动估计的效率高低将对压缩全过程产 生重大影响。因此，有必要对运动估计算法进行分析。 2 1 运动估计和补偿原理 在数字视频压缩编码标准中，引入了运动估计和补偿技术来提高压缩效率。 运动补偿【3 5 】实际上是在对运动图像进行压缩时采用的一种帧问编码技术。由于运 动的连续性，图像序列中的第n 帧图像可以看作是前面预测参考帧第n 。帧( 例 如第n - - 1 帧) 图像经过一定平移得到的。因此在实际编码中，为了节省编码位 率，并不传输第n 帧的全部数据，而是利用运动估计技术计算出第n 帧与预测 参考帧n 饷差值。如果运动估计比较有效，则中的概率分布基本上在零附 近，从而导致的能量很小，相应的编码传输所需要的位数也很少。在解码端， 根据预测参考帧n 和差值，就可以基本恢复出初始的第n 帧图像。这就是运 动估计和补偿技术能够去除信源中时间冗余的本质所在。 运动估计对编码器的性能的影响十分的明显，有实验表明在搜索范围为1 6 时，运动矢量搜索占用了9 3 的c p u 时间。可见运动估计在整个编码过程中消 耗对闻最多。因此，运动估计速度的提高是整个编码速度提高的关键。此外，由 运动补偿原理可知，所寻找的运动矢量是否精确，将对恢复图像的质量产生决定 性影响。 运动估计算法是运动估计和补偿过程中的核心算法。它通常被归纳为两大 9 运动估计算法优化技术研究与应用 第2 章运动估计算法模型 类：一类是像素递归算法p r a ( p i x e lr e c u r s i v e a l g o r i t h m ) ；另一类是块匹配算 法b m a ( b l o c km a t c h i n ga l g o r i t h m ) 。p r a 是基于递归思想，如果连续帧中像 素数据的变化是因为物体的移位引起的，算法就会沿着梯度方向对某个像素周围 的若干像素做迭代运算，使连续的运算最后收敛于一个固定的运动估计矢量，从 而预测该像素的位移；而b m a 则是基于当前帧中一定大小的块，在当前帧的 前后帧的一定区域内搜索该像素块的最佳匹配块，作为它的预测块。尽管p r a 对比较复杂的运动形式来说，其预测精度要高于b m a ，但是由于其计算量比 b m a 大的多，同时b m a 本身也拥有较好的性能，因此视频压缩编码国际标准 都采用b m a 。 2 2 像素递归法 像素递归、法【3 q 的基本思想是：对当前帧运动区域中某一像素f k ( x ，y ) ，在 前一帧某一位移处找到一个具有相同灰度值的像素f k - t ( x - d x ，y - d y ) ，即 f a x ，y ) = 五一- o 一或，y 一或) 这里的位移d = ( d x ，d y ) 代表运动矢量。 ( 2 1 ) 为了改进运动矢量的估计精度和扩大搜索范围，n e t r a v a l i 和r o b b i n s 提出了 一种递归的运动估计方法【3 6 1 ，即由上一次的估计d i ，产生改进的估计值“l ： d ：d + ( 2 2 ) u i 是第i 次迭代的更新项，d i 是运动位移的估计值，而不是真实值。经过数 次的迭代，d i 可以逐步逼近真实的值。 设第k 1 帧的像素位移估计为d i 1 ，则位移差值d f d 为： d f d ( x , y ，d “) = 五( x ，y ) 一丘i o 一母，j ，一亏) ( 2 3 ) 迭代的目的就是要产生新的d i ，使得id f d ( x ，y ，d j ) j id f d ( x ，y ，d i 1 ) l o 运动估计算法优化技术研究与应用 第2 章运动估计算法模型 i 。最终使得d i d ，此时d f d ( x ，y ，d ) - - - - 0 ，因此， y ，d ) 】2 ，并利用梯度法求最小值。迭代的公式为： d im d - i 一三s v d “ d f d ( x , y ，d “1 ) 】2 = d “- s * d f d ( x , y ) * v d “ d f d ( x , y ，d “) 】 定义目标函数 d f d ( x ， ( 2 4 ) 其中，v d i - l 表示d f d 对以1 求梯度的算子，而e o 为步长因子。由上式有： w 。1 d f d ( x , y ，d “) 】= 一，( x 一母1 ，j ，一母1 ) ( 2 5 ) 将式( 2 5 ) 代入式( 2 - 4 ) 得： d = v d l - 1 _ s d f d ( x ，y ，d f - 1 ) v d 卜1 d f d ( x , y ，d 卜1 ) 】1 咒一i ( 工一谚，) ，一d ，1 ) ( 2 6 ) 上式称为n e t m v a l i 和r o b b i n s 公式【3 6 1 ，是像素递归法的基本公式。 2 3 块匹配法 2 3 1 块匹配法的原理 块匹配法【3 。n 是一种非常直观的运动估计算法，它是基于平移运动的假设来进 行运动估计的。在平移运动中，物体上的每一点均有相同的速度大小和方向，在 物体运动的轨迹上，当前时刻所处的位置是由前一时刻位置偏移得到的。将当前 帧划分为互不重叠的二维像素予块，( 例如每块1 6 x1 6 像素) ，假定每个子块内 的像素都做相等的平移运动，在其相邻帧中相对应的几何位置周围的一定范围 内，通过某种匹配准测，寻找这些像素子块的最佳匹配块。一旦找到，便将最佳 匹配块与当前块的相对位移( d x ，d y ) ，即通常所说的运动矢量( m o t i o n v e c t o r ， m v ) 送出，并传输到接收端。图2 1 给出了块匹配法的原理图。 运动估计算法优化技术研究与应用第2 章运动估计算法模型 2 3 。2 块匹配准则 最佳匹配宏块 图2 1 块匹配原理图d 7 l 从块匹配算法【3 叼的原理可以看到，算法有两个问题需要解决：匹配准则和运 动估计方式。运动估计算法中常用的匹配准则有三种d 8 】：平均绝对误差m a d ( m e a n a b s o l u t ed i f f e r e n c e ) 、均方误差m s e ( m e a ns q u a r ee r r o r ) 和归一化互相 关函数n c c f ( n o r m a l i z e dc r o s sc o r r e l a t i o nf u n c t i o n ) 。在一些应用中也使用子 采样匹配准则。 ( 1 ) 平均绝对误差m a d 的表达式【3 8 】为： 脚( f 加高善m 善i ”眦小川以胁“州) l 刖“w ( 2 7 ) 其中( i ，j ) 为位移量，f k ( m ，n ) 和f k a ( m “，n + j ) 分别为当前帧和上 一帧的灰度值，m x n 为宏块的大小，若在某一点( i o ，j o ) 处m a d 值达到最小， 则该点为要找的最佳匹配点。m a d 还可以进一步简化为s a d ，即求和绝对误差 ( s u m o f a b s o l u t e d i f f e r e n c e ) ，这样可以省去一个除法运算，且由于s a d 和m a d 达到最小值的条件相同，所以不会由于简化而产生误差。s a d 的表达式口8 1 为： 删d ( “) 2 萎善i 五( 小川一五1 ( 所+ 和+ 川一w s “s w ( 2 8 ) 1 2 运动估计算法优化技术研究与应用 第2 章运动估计算法模型 ( 2 ) 均方误差m s e 的表达式【3 明为： m s e ( i = 刍萎m 善h ( 伽川哌加“万删州郴w ( 2 9 ) m s e 值最小的点即为最佳匹配点。 ( 3 ) 归一化互相关函数n c c f 的表达式3 司为： a ( m ，n ) a 一。咖+ f ，一+ 力 n c c f ( i ，_ ，) = 1 1 牟她l f f 1 【m = l n = l ( 研，1 ) 】- t 。z ：，e 。：，z - ( 优+ ，栉+ _ ，) 】- 一w f ，w ( 2 1 0 ) m o jn i，j ，l - l n c c f 值最大的点为最佳匹配点。 ( 4 ) 子采样匹配准则s s m 的表达式【3 8 1 为： s s m ( i 2 萎善i 五( m ) 哌胁“斛j ) i p ( m 神训“s w 黼咖炉 ： m ，n 都是偶数 其他情况 ( 2 1 1 ) 子采样匹配准则大大降低了计算复杂度，运算量只有原来的1 4 ，在一些多 候选点算法中，可以采用子采样匹配准则。匹配准则对匹配的精度影响不是很大。 其中m a d 因为不含乘除法便于计算和易于硬件实现，所以获得广泛应用。 2 3 3 全搜索算法 全搜索( f u l ls e a r c h ，f s ) 算法【3 9 1 是所有的运动估计算法中计算量最大，精 度最高的，也称为穷尽搜索算法。它对搜索窗口内所有的位置由近而远全都进行 一次块匹配运算，最后对所有结果进行比较，找到最小的m a d 点，从而得到运 动矢量。 运动估计算法优化技术研究与应用第2 章运动估计算法模型 毫无疑问，全搜索算法必然能够找到全局最优的匹配点，因此单从匹配精度 的角度上来说，全搜索算法是最好的。但是由于其巨大的运算量，在实际应用中， 全搜索算法很少会被采用，而通常是作为其他算法性能比较的标准。 2 3 4 二维对数搜索算法 二维对数搜索( 1 w o d i m e n s i o nl o g a r i t h m i cs e a r c h ，1 i ) l s ) 算法由j r j a i n 和a i c j a i n 提出，它分多个阶段搜索，逐次减小搜索范围直到不能再小为止。 t d l $ 算法的基本思想是从( o ，o ) 开始，以十字型分布的5 个点构成每次的搜 索点群，通过快速搜索跟踪最小块误差m i n i m u m b l o c k d i s t o r t ，m b d ) 点。 算法流程如下： 第一步：从运动矢量( o ，o ) 开始，选定一定的步长，以十字型分布的5 个 点构成每次搜索的点群搜索其中的最小m a d 点。 第二步：如果最小m a d 点出现在十字型点群的边缘，则下次搜索以该点为 中心，步长不变；如果最小点出现在十字型点群的中心，则下次搜索仍以该点为 中心，步长减半；如果搜索过程中，新的十字型点群中心在搜索窗的边缘，步长 也要减半。如此循环操作直到步长为i 第三步：进一步搜索当前最佳位置周围8 个点，得到m a d 最小的匹配点就 是最佳匹配点。 二维对数搜索算法的性能比t s s ，略差一点，但速度快了许多。t d l s 算法 的前提是假设搜索窗内只有一个谷点，如果搜索窗内存在多个谷点时，该算法找 到的可能是局部最小点。图2 2 给出t d l s 算法的搜索过程。 1 4 运动估计算法优化技术研究与应用第2 章运动估计算法模型 - 7 - 6 - 5 - 4 - 3 - 2 一l0l23 56 7 上 ：茎= 上 上工x x 上 丫x x x 丫 爱7 上 卜1p y -) - -q 2 3 5 三步搜索算法 。 第h 步酌搜索点 最佳匹配点 图2 2t d l s 算法搜索过程”9 l 三步搜索( t h r e e - s t e ps e a r c h ，t s s ) 算法是由t k o g a 等人提出的，它 是一种由粗到精的搜索算法，快速而且高效，它基本保持了全搜索算法的性能， 但其计算量只有其1 0 左右。它使用m a d 准则，通过三步搜索，逐步减小搜索 步长。每次搜索都是以上一步的搜索结果为中心，在周围进行一定步长的3 x 3 像素搜索，搜索精度为1 个像素。 t s s 算法的流程如下： 第一步：以窗口中心点( o ，o ) 为中心搜索点，步长为4 ，包括周围的8 个 像素点，根据最小绝对误差m a d 得到一个m b d 点，共搜索9 个点。 第二步：以上一步的最佳匹配点为中心，步长为2 ，继续搜索周围8 个像素 点，根据最小绝对误差m a d 得到一个m b d 点，共搜索8 个点。 第三步：同上一步，只是步长减小1 ，最后得到的m b d 点就是需要的运动 估计的点，从而得到运动矢量。 如图2 3 给出一个可能的搜索例子。图中( 4 ，4 ) 和( 4 ，6 ) 是第一和第二 步的m b d 点，第三步得到运动矢量为( 3 ，7 ) 。 1 5 7 6 5 4 3 2，0吨噜畸q屿吨呵 运动估计算法优化技术研究与应用 第2 章运动估计算法模型 针对一个1 6 16 的像素子块，t s s 算法共搜索2 5 个点，而f s 要进行1 5 1 5 = 2 2 5 个点的搜索，运算时间明显减少。但是由于它在第一步中的步长过大， 容易陷入局部最优，从而引起误差，因而对小运动的搜索效率较低。总体来说， t s s 算法是一种较典型的快速搜索算法，因此后来在三步搜索算法的基础上，又 产生了很多改进的搜索算法。 - t 8 - 5 - 4 - 3 - 2 - 10l2 3 4 5 8 7 上：m t l 1 反1 r 了】 0 上 斧萍窿丫 v 。 + ， v上 丫t丫 l l j 上上 丫 i l 2 3 6 新三步搜索算法 。第步的搜索点 口 第= 步的搜索点 第三步的搜索点 最佳匹配点 一搜索路径 运动矢量 图2 3t s s 算法搜索过程【枷】 传统的快速搜索算法如三步法、二维对数法、共扼方向法等属于多级搜索方 法的范畴，在多级搜索的第一步，搜索点是固定的，这些点在搜索窗内的位置， 由于假定全局极值点位置出现的概率在搜索窗内均匀分布，所以也是均匀固定分 布的，这种搜索模式对于某些仅有细微运动的块来说，并非准确。因此如何在搜 索第一步时优化设计搜索模式非常重要。这种优化与全局极值点的概率分布密切 相关。因此，我们需要考虑视频序列的全局极值点的概率分布特征。 众所周知，自然的视频序列的运动矢量场通常是柔和平滑的，变化也比较缓 慢。通过用全搜索算法对全局极值点的概率分布进行统计，研究者发现全局极值 点的分布并非像传统的快速搜索算法预先假定的那样在搜索窗内均匀分布，而通 常是基于中心偏移的，即在搜索窗中心附近出现全局极值点的概率远远大于在搜 索窗边缘出现的概率。如图2 4 所示： 1 6 t 6 s 4 3 2o叶噜咕q i f 喝吖 运动估计算法优化技术研究与应用 第2 章运动估计算法模型 n 8 n 6 n 4 噍2 0 n 2 n 圬 n i 仉0 5 o ( a ) s a k s m a n 序w g m 妇s 触越蒯 图2 4 全搜索算法得到的1 0 0 帧图像运动矢量分布h 1 1 从图中我们可以看出，对于s a l e s m a n 序列，有约9 0 的运动矢量被限制在 中心附近5 5 的区域范围内，而对于m i s s a m e r i c a n 序列，虽然看起来它的运动 矢量分布比较分散，但它也有约8 3 的运动矢量被限制在中心附近5 5 的区域 范围内。因此，它们都可以视为是基于中心偏移的序列，如果在搜索的第一步考 ， 虑全局极值点向中心偏移的性质，将搜索模式进一步优化，可以得到更精确和快 速的搜索方法。 r e n x i a n g l i 和b i n g z c n g 等在三步算法的基础上做了一些改进得到了新三步 搜索( n e w1 1 l f s t e ps e a r c h ，n t s s ) 算法【4 ”。三步算法由于其简单高效和数据 存取的规律性受到普遍欢迎，但三步算法对现实视频序列的中心偏移特性欠缺考 虑。n t s s 算法在这方面做了改进，从而获得比三步算法更好的性能。 n t s s 算法的中心思想是，考虑到现实视频序列中，相邻两帧之间大部分块 可以认为是静止的或做缓慢移动的，因此，在算法的第一步，对搜索窗中心相邻 的8 个点也同时做匹配运算，这样，对做慢速运动的物体，可以