基于块运动类型与阈值相结合的运动估计算法

叶仕通，万智萍

（1.广东工业大学 华立学院，广东 增城511325；2.中山大学 新华学院，广东 广州510520）

0 引 言

运动估计算法是现如今视频压缩领域中的一项核心技术，利用视频运动在时间与空间上的关联性有效地去除序列图像帧间的冗余进而对视频进行预测与压缩；在保证视频质量的前提下能够减少了视频压缩所需要的时间。因此，运动估计算法一直以来都是视频压缩领域中的研究热点，许多专家学者也提出了许多快速运动估计算法，如三步搜索法 （TSS）、钻石 搜索法 （DS）、全搜索算 法 （FS）等［1－3］，它们都是改进来降低整像素运动估计的复杂度，提高视频的压缩效率；但全搜索算法虽能保证视频质量但其计算量太大；而三步搜索法与钻石搜索法虽通过减少搜索点数来提高搜索速度，但却无法保证视频的质量；因此，这些算法都存在着不足，无法满足人们的需求。本文为了避免出现算法的局部优化问题，结合Chen zhi－bo等人提出了一种非对称十字型多层次六边形格点搜索算法，根据运动矢量的水平垂直偏置分布特性与半路中止的算法，并通过结合其他搜索模式的优点，最终提出一套新的算法；从而在比全搜索算法的计算量少90%的情况下，能得到了与之相近的视频压缩效果，但为了进一步提高算法的搜索效率［4］，本文根据视频的块运动的剧烈程度将其运动块划分为不同的运动矢量分布［5－7］，并且结合加阈值［8］的方法对UMHexagonS算法进行改进，以减小该算法中的算法搜索冗余为目的，对其进行优化，最终有效的减少算法在搜索过程的搜索点的数量，使得算法的搜索效率得到提高，更加有利于生活中的运用。

1 UMHexagonS算法基本步骤及改进

1.1 UMHexagonS算法总体思路与分析

视频压缩的过程中，采用多种模板进行宏块匹配，同时结合空间与时间的相关性进行运动矢量的预测，进而达到对视频压缩的目的。下面为对UMHexagonS算法的基本步骤：

步骤1 起始搜索点的预测，用五种预测模式对预测运动矢量MV进行预测。并对SAD的值进行判断，如果搜索点SAD的值很小，则跳到步骤6；如果SAD的值较大，则跳到步骤5；否则跳到步骤2。

步骤2 非对称十字形模板搜索。并对SAD的值进行判断，如果搜索点SAD的值很小，则跳到步骤6；如果SAD的值较大，则跳到步骤5；否则跳到步骤3。

步骤3 螺旋搜索

步骤4 多层六边形模板搜索

步骤5 中六边形模板搜索

步骤6 小菱形模板反复搜索，最终得到运动矢量。

UMHexagonS算法中的各种搜索模板如图1所示。

图1 UMHexagonS算法中的各种搜索模板

从UMHexagonS算法的流程我们可以看到，UMHexagonS算法在第一步的起始点搜索中，用5种预测模式进行搜索，有效的对运动块进行预测，从而提高了算法的效率，但在一些块进行搜索匹配点时依然存在着算法的冗余性，如在经过预测时，如果起始点一开始就是最优点，经过中值预测，就能把他选出最佳匹配点，但算法依然对其进行5种模式进行预测，进而增加了搜索的冗余；视频的块运动可以根据运动剧烈程度来划分不同的运动矢量分布，根据不同的情况进行分类搜索，而UMHexagonS算法对所有的候选搜索块都进行多层六边形搜索，因此也导致了算法的搜索冗余。

1.2 UMHexagons算法的改进

经过对UMHexagons算法的基本思路的分析与研究，我们可以看到，该算法虽然能够快速而高效的对视频进行运动估计，但其中依然存在着很多的不足，本文根据视频运动类型的自适应法与在算法中加入阈值的方法对其UMHexagons算法进行改进，其目标是减少UMHexagonS算法搜索冗余，方法如下所示。

改进一：起始搜索点的预测，在进行的运动矢量预测时，先使用中值预测，得到当前搜索点，设当前点为最佳点mincost，加入自适应的阈值Th0进行预先判断：

当mincost＜Th0时，则判断为提前停止搜索；否则对其搜索点进行非对称十字搜索，后进行原点预测、uplager预测和相邻参考预测算法后，加入自适应的阈值Th1与Th2，对其mincost进行判断：

若mincost＜Th1；提前停止搜索

若Th1＜mincost＜Th2；跳到菱形模板搜索［9］

若Th2＜mincost；则执行下一步

式中：βstop——块的尺寸，αstop——常数组，

常数 组 αstop的 取 值 为 ｛0.30，0.33，0.33，0.27，0.13，0.13，0.44｝；

通过在起始点的预测过程在加入阈值，来到减少算法中的必要的搜索，从而节约了搜索的点数，进而提高搜索效率。在此过程中，能把运动矢量幅度小用菱形模板进行搜索，提前停止搜索，从而提高了搜索的效率。

改进二：加入运动类型的自适应法，在现实生活中，视频可以根据运动剧烈程度来划分不同的运动矢量分布，分为如下3种：

（1）块的运动幅度小的，其运动的矢量通常都是以（0，0）为中心向外扩散，而且越往外的，其发生的概率越小，因此，对于运动幅度小的可以理解为其运动矢量在搜索中心 （0，0）附近。

（2）块的运动幅度中等，其运动的矢量通常不在搜索中心 （0，0），它会在距离中心位置较远的地方出现，而且其出现的概率分布是向中心与外侧出现的概率越来越小，呈环状型，向中心与外侧递减。

（3）块的运动幅度很大，其运动的矢量通常分布在远离搜索中心 （0，0），主要出现在外侧范围。

为了能够快速的判断视频的运动剧烈程度，引入阈值T［10］，通过cost （珡m ，λ）［11］与 T 的比较，来判断视频运动的幅度大小，进而对其分类，提高搜索效率，减少搜索的冗余：

1）当cost（，λ）＜T0时，其视频图像的块运动幅度很小，可表示为相对静止状态，可以把搜索中心 （0，0）设置为最佳点，但由于在对起始点的阈值判断的时候，已经把运动矢量幅度小的排除了，因此，在这里无需对其进行判断。

2）当cost（m珡，λ）＜＝T时，其视频图像的块运动幅度中等，选用正方形搜索模板，即5×5的搜索。

3）当cost（m珡，λ）＞T时，其视频图像的块运动幅度很大，则跳到Step 5，用多层六边形模板搜索，后用中六边形模板搜索，最后用小菱形模板对其反复的搜索，直到得到最佳结果。

研究表明当T＝800时，其能准确的把块运动幅度中等与块运动幅度很大进行有效的判断。T＜＝800时，对于运动幅度中等的搜索效率很高，而在运动幅度很大的块不适用。公式

其中B根据不同情况可取16，8或4

其中SAD式绝对误差和；R是候选运动矢量码率；λ是平衡码率与失真度的因子；s是当前编码的数据、c（m）是编码重建的参考帧数据。

本文改进后UMHexagons算法的核心程序片段如下所示。

正方形搜索，只搜索前25点，相当于5×5区域全搜索：

多层六边形模板搜索：

六边形模板搜索：

2 改进后UMHexagons算

步骤1 起始搜索点的预测，先对搜索点进行中值预测，引入阈值Th0，进行初步的阈值判断，设当前点位最佳点mincost，进行比较，如果mincost＜Th0，即提前停止搜索，否则进行原点预测、uplager预测和相邻参考预测算法，后进行非对称十字搜索，加入自适应的阈值Th1与Th2，对其mincost进行判断：若mincost＜Th1；提前停止搜索若Th1＜mincost＜Th2；跳到菱形模板搜索若Th2＜mincost；则执行步骤2

步骤2 根据运动类型自适应法，对搜索点运动矢量幅度的大小进行判断，当cost（珡m，λ）＜＝T时，选用正方形搜索模板。当cost（珡m，λ）＞T时，其视频图像的块运动幅度很大，则继续步骤5。

步骤3 菱形模板搜索，得到最终的运动矢量。

步骤4 正方形搜索模板，得到最终的结果。

步骤5 多层六边形模板搜索

步骤6 中六边形模板搜索

步骤7 小菱形模板反复搜索，最终得到运动矢量。

改进后UMHexagons算法流程图如图2所示。

3 实验结果与分析

图2 UMHexagons算法

使用JVT的h.264／AVC编码参考模，在JM12.2平台上进行改进算法的验证。本文根据运动幅度的大小选取了QCIF的3个标准视频测试序列：mobile、foreman、akiyo对算法进行仿真，其中akiyo的空间细节比较少，并且运动较为缓慢，因此用来表示运动幅度小的运动序列；Foreman虽然镜头与画面的背景一起运动，但其纹理复杂度一般，因此用来表示运动幅度中等的运动序列；mobile运动形式丰富并且其纹理的复杂度极高，因此用来表示运动幅度很大的运动序列。编码帧数为60，参考帧数为5，帧率为30，编码格式为IPPPP。两种种算法在不同的量化参数 （QP）下进行测试。

运动估计算法的效率主要依据是视频的峰值信噪比高低和搜索速度快慢。只有做到运动估计的准确性，才能做到的图像质量就越高，视频序列的搜索越块的效果；本文根据本文主要采用Y、U、V各分量的峰值信噪比（PSNR）、运动估计时间 （MET）作为算法性能评判的标准。Y、U、V各分量的PSNR表明压缩后图像的质量，而运动估计时间能有效的表明算法的有效性。其测试结果：表1为原UMHexagons算法与改进后算法的运动估计时间比较，表2为原UMHexagons算法与改进后算法的各分量峰值信噪比较，如下所示。

通过实验可以看，本文通过改进后的算法与原始的UMHexagons算法的PSNR各分量数据进行比较，可以再表2中看出，在QP值变化的情况下，PSNR的各个分量的峰值变化很小，最大的变化也只有3%，而从表1中，我们可以看出，在QP值变化的情况下，skiyo视频测试序列的运动估计时间变化平均在18%左右，foreman视频测试序列的运动估计时间变化平均在37%左右，而mobile视频测试序列的运动估计时间变化平均在26%左右；由此可见，本文改进后的UMHexagons算能在保持了原算法的率失真性能下，减少运动估计编码时间。

表1 原始算法与改进算法的运动估计时间比较 （表1题目排列参表2）

表2 原始算法与改进算法的各分量峰值信噪比较

为了更加直观的展示原始算法与改进后算法在搜索点数的优化程度，本文用过MATLAB对其进行仿真，经实验，图3为skiyo视频测试序列的搜索数、图4为foreman视频测试序列的搜索、图5为mobile视频测试序列的搜索数。

通过MATLAB对其算法搜索点数的验证，我们可以看到，本文根据视频运动块的运动幅度的大小，有效的减少了UMHexagons算法中的搜索冗余性，在视频预测序列skiyo与foreman和mobile的搜索数与原UMHexagons算的搜索点相比有明显的减少，其中视频预测序列foreman的搜索点个数减少的最多；与预测的结果相符，充分证明的算法的可行性。

4 结束语

本文通过在UMHexagons算法中增加阈值的形式，来减少原UMHexagons算法中的搜索冗余，通过比较判断，根据运动矢量幅度的大小，对视频的运动块进行分类，有效的减少模块的不必要重复搜索，从而减少运用估计时间，结果表明，改进后的运动估计算法在运动幅度平缓的视频序列中，性能略有提高；在运动幅度很快的视频序列中，性能较好；在运动幅度中等的视频序列中，性能优异，与预期的效果相符。但改进后算法还存在着不足，如可通过优化各种搜索模板使算法更加完善，在日后的研究工作中，会将其作为深入的研究，使其能够更加适用于实际的生活。

：

［1］WANG Yanying，FENG Jinmei.Improved H.264motion estimation algorithm based on EPZS ［J］.Computer Technology and Development，2012，22 （1）：103－107 （in Chinese）. ［王艳营，冯进玫.基于EPZS的H.264运动估计算法的改进［J］.计算机技术与发展，2012，22 （1）：103－107.］

［2］ZHANG Sha，TIAN Fengchun，TAN Hongtao.Fast block matching search algorithm based on down－sampling and its application in denoising ［J］.Journal of Computer Applications，2010，30 （10）：2819－2822 （in Chinese）.［张莎，田逢春，谭洪涛.基于下采样的快速块匹配搜索算法及降噪应用 ［J］.计算机应用，2010，30 （10）：2819－2822.］

［3］CHEN Gong，Niu Qinzhou.On classical bma in motion estimation of image sequence ［J］.Computer Applications and Software，2012，29 （5）：147－151 （in Chinese）.［陈宫，牛秦洲.图像序列运动估计中经典块匹配算法研究 ［J］.计算机应用与软件，2012，29 （5）：147－151.］

［4］HUANG Chunqing，QIU Xiaobin.Optimization on fast motion estimation algorithm based on x264 ［J］.Control Engineering of China，2010，19 （6）：820－823 （in Chinese）.［黄春庆，邱晓彬.基于x264的快速运动估计算法优化 ［J］.控制工程，2010，19 （6）：820－823.］

［5］ZHANG Xinan，GONG Yanjun，LI Xiaowu.Fast integer pixel motion estimation algorithm for AVS－M ［J］.Journal of Chinese Computer Systems，2011，32 （4）：793－796 （in Chinese）.［张新安，宫彦军，李小武.一种AVS－M整数像素运动估计快速算法 ［J］.小型微型计算机系统，2011，32 （4）：793－796.］

［6］CHEN Tianzhuang，LIANG Jiuzhen，HAN Jun.A fast algorithm based on mot ion classification and direct ion prediction［J］.Computer Engineering ＆ Science，2100，33 （7）：112－117（in Chinese）.［陈天壮，梁久祯，韩军.一种基于块运动类型和方向预测相结合的快速搜索算法 ［J］.计算机工程与科学，2100，33 （7）：112－117.］

［7］FANG Muyun，WU Yuan，LI Qian.Improvement on motion vector field adaptive search algorithm ［J］.Computer Technology and Development，2011，21 （6）：70－73 （in Chinese）.［方木云，吴元，李倩.运动矢量场自适应搜索算法的一种改进方案 ［J］.计算机技术与发展，2011，21 （6）：70－73.］

［8］XIE Hongtu，GAO Guangzhu，HE Zhiyong.Research of adaptive motion estimation and compensation algorithm based on redundant discrete wavelet transformation ［J］.Application Research of Computers，2011，28 （1）：368－370 （in Chinese）.［谢洪途，高广珠，何智勇.基于冗余小波变换的自适应运动估计与补偿算法研究 ［J］.计算机应用研究，2011，28 （1）：368－370.］

［9］MENG Lei，LI Hang.Adaptivemotion estimation search algorithm in H.264／AVC ［J］.Computer Applications and Software，2010，27 （8）：145－147 （in Chinese）.［孟磊，李航.H.264／AVC自适应运动估计搜索算法 ［J］.计算机应用与软件，2010，27 （8）：145－147.］

［10］ZHU Xiaolong，LUO Xing，CHEN Zujue.Improved directional diamond algorithm with mode decision ［J］.Application Research of Computers，2010，27 （1）：393－395 （in Chinese）.［朱小龙，罗星，陈祖爵.带有模式选择的改进的方向性菱形搜索算法 ［J］.计算机应用研究，2010，27 （1）：393－395.］

［11］HUANG Wenbin，WANG Guanglong.Research of optimization on fast motion estimation algorithm based on multi－template search ［J］.Computer Measurement ＆ Control，2012，20 （5）：1326－1329 （in Chinese）.［黄文斌，王广龙.基于多模板快速搜索的运动估计算法优化研究 ［J］.计算机测量与控制，2012，20 （5）：1326－1329.］