摘要：随着视频压缩技术的发展以及人们对大尺寸、高质量图像日益增长的需求，视频压缩算法已成为当前视频技术发展研究的热点，而搜索策略又是视频压缩算法中研究最多的领域。以传统经典快速搜索算法为依托，重点对当前研究的各种快速运动估计算法进行阐述、分析和比较。

　　关键词：运动；搜索算法；发展；应用

　　中图分类号：C939文献标志码：A文章编号：1673-291X（2010）34-0235-02

　　引言

　　随着网络上图像传输需求的增多，视频实时图像的处理越来越受到人们的重视，庞大的图像数据使视频的实时处理变得困难，因此，图像压缩技术成为视频实时图像处理技术的关键问题。

　　视频压缩可以从不同的角度进行优化，帧间预测算法的改进是提高整体视频压缩算法效率的关键。它改进和优化主要涉及以下三方面：搜索策略、块匹配准则和块尺寸的选择。块匹配算法主要有最小绝对误差和（SAD）、最小平均绝对误差（MAD）或最小均方误差（MSE）算法，还有改进后的最小绝对差分误差和（SADD）算法以及基于内容的运动搜索算法等。块尺寸方面，搜索的块尺寸从16×16到8×8，再到4×4，精度单位从整像素到1/2像素，再到1/4像素，这些算法的改进减少了不必要的搜索点，细化了块单位，提高了搜索精度和速度。

　　多数运动估计算法都是基于对搜索算法的改进，通过对搜索算法的改进，以消除搜索所带来的时间冗余和空间冗余。

　　最初提出的快速搜索算法是全搜索法（Full Search，FS）。全搜索算法运算准确度最高，但是运算量巨大，在编码过程中占据了总运算量的60%～80%，所以很少为实际所使用。为减小运动估计过程中的计算量，保证运动估计的准确性，运动估计领域提出了很多新的快速算法。

　　早期的快速估计算法有三步搜索法、二维对数搜索法、正交搜索算法、交叉搜索算法等。这些方法通过限制搜索点的数目有效地减少了运算量，相对全搜索算法有了较大改进，但这些算法为了满足搜索点的减少，往往将初始步长设的较大，使得搜索容易陷入局部最小，导致估计准确度不高。同时早期的算法在设计搜索策略时，多数会选择全向性作为搜索的方向，即会选择上下左右四向八点，或选择菱形搜索等作为搜索模型。这种搜索策略从搜索的全面性以及匹配的精度来讲，是有其优越性，但全向性搜索往往同时带来搜索计算量增大，产生大量计算冗余。针对这些问题，现阶段提出的新的快速搜索算法，从不同方面入手，改善搜索算法中的不足，提高搜索效率。为此本文将以经典算法作为研究前提，重点对当前研究的各种快速运动估计算法的对比分析其各自的利弊，提出对运动估计算法发展的新构思。

　　一、基于分层的自适应运动估计算法

　　基于分层的自适应运动估计算法，主要选取菱形作为搜索模型，通过相邻宏块间的运动矢量关系来判断运动状况，并对不同运动块采用不同的搜索方法，对于大运动块，采用分层结构搜索；其他运动使用小菱形搜索。同时结合多种提前截至准则，在保证匹配精度的前提下，提高了搜索速度。

　　基于分层的自适应运动估计算法是基于一种分层塔形的搜索思路延伸而成，但在算法上又明显优于分层塔形搜索。基于分层塔形的搜索，它的做法是：对于那些运动比较剧烈的宏块，先在低分辨力下一层层地搜索，然后再转到原始分辨力下搜索，从而以较低的计算复杂度获得较高的搜索精度。但现行的分层算法有时会出现重复搜索的问题，特别是在大运动搜索中，当预测起点已经是最优匹配点时，若判决准则不认为是最优，则还要先转到低分辨力层搜索，再在原分辨力层精确搜索，虽然最终也能找到原先的最优点，但搜索步数增加，搜索速度变慢。因此，若没有一个好的判决准则，分层方法有时会降低编码效率。基于分层的自适应运动估计算法，能充分发挥分层思想在大尺度运动中搜索效率高的优势，通过对各宏块运动情况进行准确判断，确定使用分层搜索的时机。使用自适应的搜索起点调整技术来逼近最优点，使用多种有效的提前阈值截止技术来防止重复搜索，与分层思想相结合，使得原来的分层算法效率有所提高。

　　二、方向延伸的快速运动搜索算法（DES）

　　方向延伸的快速运动搜索（DES）算法，利用图像块运动的方向特性，减小帧间编码中运动估计的运算量。该算法在钻石小模板块失真匹配运算的基础上引入搜索方向延伸方案、运动矢量预测和运动搜索的自适应门限等要素，先通过钻石小模块失真匹配运算找到最小失真检测点，确定初始搜索点到最小块失真检测点为搜索方向，若该最小块失真点不是中心检测点，则在搜索方向上不断延伸下一个相邻的检测点进行块失真匹配，直至下一个检测点的块失真大于当前检测点的块失真。接着以当前检测点作为中心检测点，重复以上操作，直至中心检测点为最优检测点，结束搜索。

　　DES算法是在DS算法的思想基础上的一种延伸。但其算法思想又明显有别于DS算法。DS算法是一种基于全向性的搜索思想，该算法以搜索模板形状而得名，其基本思想重复使用两种搜索模板，钻石搜索大模板及钻石搜索小模板以适应视频图像中运动变化的基本规律。在搜索过程先重复使用大模板，直到最佳匹配块落在大模板中心。然后再使用小模板来实现最佳匹配块的准确定位。但由于DS算法在每个搜索点位置都进行全向性搜索，容易产生大量的搜索冗余。

　　DES算法在秉承了DS的钻石搜索小模板的同时，针对运动不是特别剧烈的视频图像，提出方向延伸的搜索算法，使得搜索总是基于失真匹配最小的像素进行，这就大大减少了搜索的范围和搜索的冗余。但DES算法也有其不足之处，由于初始搜索点的选取时基于当前块的左方、正上方和右上方三个方向的候选点选取产生，虽然算法中考虑了相邻块运动矢量相关性及运动矢量中心偏移特性，也提到了通过阀值限定初始搜索点的选取，但由于算法中仅考虑了空间因素，而没有考虑时间相关性，而且也没有全面考虑空间因素，该算法还是会有最佳匹配点和初始搜索点不在相近的搜索区域的情况。这时放弃钻石搜索大模板而仅仅基于钻石搜索小模板搜索，就会在相同的算法复杂度的情况下，增加搜索的次数，从而降低搜索效率。DES算法在某些情况下优于DS算法，但由于其初始搜索点缺乏完善，很容易导致后面最佳匹配点的搜索产生繁复。

　　三、基于概率矩阵的快速运动估计算法

　　基于概率矩阵的快速运动估计算法，综合运用时空相关性来对各个帧宏块的运动向量的概率分布进行估计。该算法在综合运用时空相关性的基础上，首先根据当前宏块的运动向量概率矩阵及之前宏块的概率统计矩阵，通过相应的预测公式来估计下一宏块各个可能的运动向量对应的概率值，然后根据概率值组成和搜索窗口大小相同的概率矩阵，选取矩阵中概率较大的运动向量进行块匹配运算，找到最小平均绝对误差（MAD）点，再使用小菱形搜索算法进行修正来得到最终运动估计结果。

　　传统的快速搜索算法基于两种思想：（1）通过限制搜索点的个数来降低块匹配法（BMA）的复杂度，如三步搜索法、四步搜索法、新三步搜索法等；（2）运用时空相关性，从得到的运动向量选择块匹配的初始点的方法，如本文提到的DES算法和优化预测运动矢量的快速运动估计算法。这些算法分别从某一个方面入手进行算法优化，而基于概率矩阵的快速运动估计算法则将限制搜索点的思想与时空相关性联系起来，使得算法将更加优越，而且精度还略有提高。摘要：随着视频压缩技术的发展以及人们对大尺寸、高质量图像日益增长的需求，视频压缩算法已成为当前视频技术发展研究的热点，而搜索策略又是视频压缩算法中研究最多的领域。以传统经典快速搜索算法为依托，重点对当前研究的各种快速运动估计算法进行阐述、分析和比较。

　　关键词：运动；搜索算法；发展；应用

　　中图分类号：C939文献标志码：A文章编号：1673-291X（2010）34-0235-02

　　引言

　　随着网络上图像传输需求的增多，视频实时图像的处理越来越受到人们的重视，庞大的图像数据使视频的实时处理变得困难，因此，图像压缩技术成为视频实时图像处理技术的关键问题。

　　视频压缩可以从不同的角度进行优化，帧间预测算法的改进是提高整体视频压缩算法效率的关键。它改进和优化主要涉及以下三方面：搜索策略、块匹配准则和块尺寸的选择。块匹配算法主要有最小绝对误差和（SAD）、最小平均绝对误差（MAD）或最小均方误差（MSE）算法，还有改进后的最小绝对差分误差和（SADD）算法以及基于内容的运动搜索算法等。块尺寸方面，搜索的块尺寸从16×16到8×8，再到4×4，精度单位从整像素到1/2像素，再到1/4像素，这些算法的改进减少了不必要的搜索点，细化了块单位，提高了搜索精度和速度。

　　多数运动估计算法都是基于对搜索算法的改进，通过对搜索算法的改进，以消除搜索所带来的时间冗余和空间冗余。

　　最初提出的快速搜索算法是全搜索法（Full Search，FS）。全搜索算法运算准确度最高，但是运算量巨大，在编码过程中占据了总运算量的60%～80%，所以很少为实际所使用。为减小运动估计过程中的计算量，保证运动估计的准确性，运动估计领域提出了很多新的快速算法。

　　早期的快速估计算法有三步搜索法、二维对数搜索法、正交搜索算法、交叉搜索算法等。这些方法通过限制搜索点的数目有效地减少了运算量，相对全搜索算法有了较大改进，但这些算法为了满足搜索点的减少，往往将初始步长设的较大，使得搜索容易陷入局部最小，导致估计准确度不高。同时早期的算法在设计搜索策略时，多数会选择全向性作为搜索的方向，即会选择上下左右四向八点，或选择菱形搜索等作为搜索模型。这种搜索策略从搜索的全面性以及匹配的精度来讲，是有其优越性，但全向性搜索往往同时带来搜索计算量增大，产生大量计算冗余。针对这些问题，现阶段提出的新的快速搜索算法，从不同方面入手，改善搜索算法中的不足，提高搜索效率。为此本文将以经典算法作为研究前提，重点对当前研究的各种快速运动估计算法的对比分析其各自的利弊，提出对运动估计算法发展的新构思。

　　一、基于分层的自适应运动估计算法

　　基于分层的自适应运动估计算法，主要选取菱形作为搜索模型，通过相邻宏块间的运动矢量关系来判断运动状况，并对不同运动块采用不同的搜索方法，对于大运动块，采用分层结构搜索；其他运动使用小菱形搜索。同时结合多种提前截至准则，在保证匹配精度的前提下，提高了搜索速度。

　　基于分层的自适应运动估计算法是基于一种分层塔形的搜索思路延伸而成，但在算法上又明显优于分层塔形搜索。基于分层塔形的搜索，它的做法是：对于那些运动比较剧烈的宏块，先在低分辨力下一层层地搜索，然后再转到原始分辨力下搜索，从而以较低的计算复杂度获得较高的搜索精度。但现行的分层算法有时会出现重复搜索的问题，特别是在大运动搜索中，当预测起点已经是最优匹配点时，若判决准则不认为是最优，则还要先转到低分辨力层搜索，再在原分辨力层精确搜索，虽然最终也能找到原先的最优点，但搜索步数增加，搜索速度变慢。因此，若没有一个好的判决准则，分层方法有时会降低编码效率。基于分层的自适应运动估计算法，能充分发挥分层思想在大尺度运动中搜索效率高的优势，通过对各宏块运动情况进行准确判断，确定使用分层搜索的时机。使用自适应的搜索起点调整技术来逼近最优点，使用多种有效的提前阈值截止技术来防止重复搜索，与分层思想相结合，使得原来的分层算法效率有所提高。

　　二、方向延伸的快速运动搜索算法（DES）

　　方向延伸的快速运动搜索（DES）算法，利用图像块运动的方向特性，减小帧间编码中运动估计的运算量。该算法在钻石小模板块失真匹配运算的基础上引入搜索方向延伸方案、运动矢量预测和运动搜索的自适应门限等要素，先通过钻石小模块失真匹配运算找到最小失真检测点，确定初始搜索点到最小块失真检测点为搜索方向，若该最小块失真点不是中心检测点，则在搜索方向上不断延伸下一个相邻的检测点进行块失真匹配，直至下一个检测点的块失真大于当前检测点的块失真。接着以当前检测点作为中心检测点，重复以上操作，直至中心检测点为最优检测点，结束搜索。

　　DES算法是在DS算法的思想基础上的一种延伸。但其算法思想又明显有别于DS算法。DS算法是一种基于全向性的搜索思想，该算法以搜索模板形状而得名，其基本思想重复使用两种搜索模板，钻石搜索大模板及钻石搜索小模板以适应视频图像中运动变化的基本规律。在搜索过程先重复使用大模板，直到最佳匹配块落在大模板中心。然后再使用小模板来实现最佳匹配块的准确定位。但由于DS算法在每个搜索点位置都进行全向性搜索，容易产生大量的搜索冗余。

　　DES算法在秉承了DS的钻石搜索小模板的同时，针对运动不是特别剧烈的视频图像，提出方向延伸的搜索算法，使得搜索总是基于失真匹配最小的像素进行，这就大大减少了搜索的范围和搜索的冗余。但DES算法也有其不足之处，由于初始搜索点的选取时基于当前块的左方、正上方和右上方三个方向的候选点选取产生，虽然算法中考虑了相邻块运动矢量相关性及运动矢量中心偏移特性，也提到了通过阀值限定初始搜索点的选取，但由于算法中仅考虑了空间因素，而没有考虑时间相关性，而且也没有全面考虑空间因素，该算法还是会有最佳匹配点和初始搜索点不在相近的搜索区域的情况。这时放弃钻石搜索大模板而仅仅基于钻石搜索小模板搜索，就会在相同的算法复杂度的情况下，增加搜索的次数，从而降低搜索效率。DES算法在某些情况下优于DS算法，但由于其初始搜索点缺乏完善，很容易导致后面最佳匹配点的搜索产生繁复。

　　三、基于概率矩阵的快速运动估计算法

　　基于概率矩阵的快速运动估计算法，综合运用时空相关性来对各个帧宏块的运动向量的概率分布进行估计。该算法在综合运用时空相关性的基础上，首先根据当前宏块的运动向量概率矩阵及之前宏块的概率统计矩阵，通过相应的预测公式来估计下一宏块各个可能的运动向量对应的概率值，然后根据概率值组成和搜索窗口大小相同的概率矩阵，选取矩阵中概率较大的运动向量进行块匹配运算，找到最小平均绝对误差（MAD）点，再使用小菱形搜索算法进行修正来得到最终运动估计结果。

　　传统的快速搜索算法基于两种思想：（1）通过限制搜索点的个数来降低块匹配法（BMA）的复杂度，如三步搜索法、四步搜索法、新三步搜索法等；（2）运用时空相关性，从得到的运动向量选择块匹配的初始点的方法，如本文提到的DES算法和优化预测运动矢量的快速运动估计算法。这些算法分别从某一个方面入手进行算法优化，而基于概率矩阵的快速运动估计算法则将限制搜索点的思想与时空相关性联系起来，使得算法将更加优越，而且精度还略有提高。该算法在算法设计中有两点可取之处，首先选取与搜索窗口大小相同的概率矩阵，使得搜索窗口中所有的方向向量都得到了考虑。而概率矩阵预测算法P（t）=P（t-1）×0.3+P0×0.7的运用提高了概率矩阵预测值的精确性。通过对高概率的运动矢量的块匹配运算，减少因对低概率的运动矢量进行块匹配运算而造成的运算速度和精度的低效性。但算法也有其不足之处，该算法思想通过有效地减少了搜索的次数，简化了搜索的复杂度，提高了搜索精度。但由此产生的概率矩阵同样产生了计算的低效性。由于概率矩阵的设计是基于与搜索窗口同样大小，则在概率计算中，就要将窗口中所有运动矢量都要进行计算和概率统计，概率矩阵预测有别于其他搜索算法，相应产生的多余计算，也是其他算法没有的。

　　小结

　　优化预测运动矢量的快速运动估计算法与DES算法在压缩思想上都是基于通过优化搜索方向算法，减少大量时间消耗和冗余信息。但在算法上两者又有明显不同。DES算法是基于钻石搜索算法，将中心检测点到最小块失真检测点定为搜索方向；而预测运动矢量的快速估计算法，在确定方向时，同时考虑了中心、中值和时间相关的三个矢量作为基本预测矢量，在考虑了序列空间相关性的同时考虑到序列的时间相关性。在算法的精确上比DES算法有了明显的改进。

　　而概率搜索矩阵的搜索思想与上述思想有着明显的差别，该算法在综合考虑了运动帧间时空相关性的同时，根据搜索半径确定与搜索窗口同样大小的概率矩阵。通过寻找概率矩阵中概率值较大的运动向量来进行块匹配运算，找到最小平均绝对误差（MAD）点。该算法通过概率矩阵的计算，有效地减少了搜索的次数，简化了搜索的复杂度，提高了搜索精度。但由此产生的概率矩阵同样产生了计算的低效性。由于概率矩阵的设计有别于其他搜索算法，相应产生的多余计算，也是其他算法没有的。

　　总的来讲，新的快速搜索算法都是在原有经典算法的基础上的改进和延伸。算法思想也主要是基于对时运动帧间时空相关性的考虑，利用菱形搜索算法，大小钻石搜索算法以及运动向量概率矩阵等，以更为高效的方式，通过更少的运算寻找到最佳匹配块，达到提高算法的速度和精度。 中国论文联盟http://www.lwlm.com编辑整理。

　　参考文献：

　　[1]杨志云，郝红卫，等。一种精确而快速的块匹配算法[J].计算机工程与设计，2008，（2）。

　　[2]乐培玉，张太镒，等。一种基于概率矩阵的快速运动估计算法[J].中国图像图形学报，2007，（1）。

　　[3]闫敬文，余见，等。优化预测运动矢量的快速运动估计算法[J].光学精密工程，2007，（10）。

　　[4]俞柏锋，赵飞，等。基于分层的自适应运动估计算法[J].电视技术，2008，（3）。

　　[5]齐美彬，王德宝，等。一种方向延伸的快速运动搜索算法[J].工程图学学报，2008，（1）。

　　[6]刘伟锋，汪增福，等。基于内容的视频压缩改进算法[J].计算机工程与设计，2009，（1）。

　　[7]Andy Beach.视频压缩宝典[M].田尊华，程钢，译。北京：清华大学出版社，2009.

　　[8]全予一，门爱东，等。数字视频图像处理[M].北京：电子工业出版社，2005.