引入搜索预测与阈值决策的改进菱形运动估计算法

刘 艳

(山西金融职业学院信息技术系，山西 太原 030008)

引入搜索预测与阈值决策的改进菱形运动估计算法

刘 艳

(山西金融职业学院信息技术系，山西 太原 030008)

为了提高视频的压缩效率，在传统菱形搜索算法基础上提出一种改进菱形搜索算法。该算法通过引入动态阈值，在起始搜索点预测、菱形搜索模式和搜索中止算法方面进行了优化，减少了SAD计算的内部冗余和搜索区域中不相关的块匹配计算，同时采用自适应搜索模式选择技术减少运输复杂度。实验结果表明：提出的改进菱形搜索算法适合各种运动类型的视频序列，特别适用于运动变化剧烈的序列，相比于FS算法，能够在PSNR值和码率值极其接近于FS算法的情况下对所有序列的MET减少约95%，大大减少运动估计时间。

视频压缩；H.264；运动估计；菱形搜索；块匹配

在帧间预测编码中，由于活动图像邻近帧中的景物存在着一定的相关性。因此，可将活动图像分成若干块或宏块，并设法搜索出每个块或宏块在邻近帧图像中的位置，并得出两者之间的空间位置的相对偏移量，得到的相对偏移量就是通常所指的运动矢量，得到运动矢量的过程被称为运动估计[1-2]。H.264是ITU-T的联合视频组(joint video team，JVT)开发的一个新的数字视频编码标

准，因压缩比和网络亲和性好而被广泛使用，但是，H.264标准与其他标准相比需要消耗更多的运动估计时间和资源[3-4]。运动估计算法决定了视频压缩的性能和速度，是视频压缩编码系统中的关键环节，因此寻求更高效的运动估计算法成了节省编码时间和资源，提高编码质量的重中之重。通常情况下，可以将快速算法分为两类：基于模板的运动估计算法和基于全局的运动估计算法[5-7]。基于全局的运动估计算法主要是针对基于模板的运动估计算法容易出现估计精度下降的问题而提出的，虽然其搜索速度比全搜索算法(full search，FS)快，但相对于三步搜索法(three-step search，TSS)[8]、新三步搜索法(novel three-step search，NTSS)[9]、六边形搜索法(Hexagonal block search algorithm，HEXBS)[10]、菱形搜索法(diamond search，DS)[11]和十字搜索法(cross diamond search，CDS)[12]等基于模板的运动估计算法，其运算复杂度增加。其中，DS法由于充分考虑到实际视频序列中物体在水平和垂直两个方向运动的概率较其他方向大，图像频谱多呈菱形分布，因此是目前综合性能较好的快速搜索算法。但是，在传统的DS算法中，如果单独采用小菱形搜索模式(small diamond search pattern，SDSP)可以减少运算复杂度，但是在快速运动或是不规则视频序列中搜索容易落入局部最优。若单独采用大菱形搜索模式(large diamond search pattern，LDSP)，虽然可以解决搜索落入局部最优的问题，但由于搜索点的增加使得运算量大幅增加。因此，本文在传统DS法的基础上，引入起始搜索点预测、自适应搜索模式选择和动态中止搜索算法，可提高运动估计运算速度且不降低估计精度。

1 传统菱形搜索算法

DS算法以搜索模板形状而得名，具有简单、鲁棒、高效的特点，是现有性能最优的快速搜索算法之一。其基本思想是利用搜索模板的形状和大小对运动估计算法速度及精度产生重要影响的特性。在搜索最优匹配点时，选择小的搜索模板可能会陷入局部最优，选择大的搜索模板则可能无法找到最优点。因此DS算法针对视频图像中运动矢量的基本规律，选用了两种形状大小的搜索模板。

它分为9点LDSP和5点SDSP，如图1(a)、(b)所示。DS算法考虑到实际视频序列中物体在水平和垂直两个方向运动的概率较其他方向大，且图像频谱多呈菱形分布。

图1 菱形搜索算法

搜索遵循先粗后精的原则，先用LDSP进行粗定位，避免陷入局部最优，然后使用SDSP搜索粗定位中最小绝对误差和(sum of absolute difference，SAD)值点的周围4个点，此时得到的SAD值最小点便是最优匹配点。DS算法搜索过程如下：开始阶段先重复使用LDSP，直到最佳匹配块落在大菱形中心。由于LDSP步长大，因而搜索范围广，可实现粗定位，使搜索不会陷于局部最小，当粗定位结束后，可认为最优点就在LDSP 周围8个点所围菱形区域中。然后再使用SDSP来实现最佳匹配块的准确定位，以不产生较大起伏，从而提高运动估计精度。

2 改进菱形搜索算法

2.1 起始搜索点预测和自适应搜索模式选择

图2 不同运动序列运动矢量分布特性图

一般情况下视频序列是柔和平滑的，其意味着全局最优运动矢量通常位于或者接近于搜索中心。图2给出了FS算法对6种不同运动类型的视频序列的全局最优运动矢量的分布概率，对于慢

速运动视频序列如：Akiyo、Coast-Guard和News，全局最优运动矢量几乎都分布在搜索窗中心位置，即全局最优运动矢量的零偏置特性。而对于中速和快速运动视频序列如：Mobile、Foreman和Football，全局最优运动矢量的位置与搜索窗中心的距离有所增加，即全局最优运动矢量的中心偏置特性。

在传统的DS算法中，如果单独采用SDSP可以减少运算复杂度，但是在快速运动或是不规则视频序列中搜索容易落入局部最优。而如果单独采用LDSP，虽然可以解决搜索落入局部最优的问题，但是由于搜索点的增加从而使得运算量大幅增加。为了提高视频的压缩效率，可根据当前块的运动快慢来决定搜索模式是采用 LDSP还是SDSP，如果为慢速运动序列可采用 SDSP，否则采用LDSP。这是由于相邻块之间具有很强的相关性，当前块的运动类型可以很容易的根据已编码块的运动类型进行估计。确定当前块的运动类型可以通过采用式(1)的中值函数 Median ｛｝，根据相邻块最小全局运动矢量计算阈值 TP进行判断，其中GMVmin()表示各相邻块 m的最小全局运动矢量；K为用于计算 TP的相邻块数量。若 TP值较小，则说明匹配块接近于搜索中心，反之则远离搜索起始中心。

运动估计的操作数可以通过式(2)进行计算，其中，l1和 l2表示当前块和参考块划分的行数和列数；S表示搜索窗范围内的搜索点数量；Sub、Abs和Add分别表示快匹配原则中绝对误差和SAD计算中减法、绝对值和加法的计算次数。

本文中，采用动态内部搜索中止算法(dynamic internal search stopping algorithm，DISS)减少式(2)中的Sub、Abs和Add操作，采用 DISS减少(2)中的搜索点数量S，即排除搜索窗中不会成为最佳匹配块的候选块。

2.2 动态内部搜索中止算法

DISS主要用于减少候选块运动估计中减法、绝对值和加法计算次数，即式(2)中］项的计算次数。为达到此目的，需要引入DISS阈值 T(DISS)(j)。首先，将当前帧中的当前块和参考帧中的候选块按行数分组，每组包含的行数为2l，其中l= 0,1,2,···,l14；然后，从第一组开始，计算当前块和候选块的SAD部分累加之和。DISS阈值 T(DISS)(j)的表达如式(3)所示，其中 SADmin表示搜索窗中已搜索块与当前块的最小SAD；j表示所累加组的序号数；P表示该组的像素数。

比较计算所得的 SAD部分累加之和与T(DISS)(j)的大小。若SAD部分累加之和小于T(DISS)(j)，则继续累加下一组的 SAD作为新的SAD部分累加之和，并计算相应的阈值 T(DISS)(j)，然后再进行比较。若 SAD部分累加之和大于T(DISS)(j)，则停止计算，然后对搜索窗中的下一候选块重复上述步骤，即候选块和当前块进行分组、累加SAD、比较SAD与相应 T(DISS)(j)的大小关系。

但在实际操作中如果用式(3)所计算的阈值与SAD部分累加之和进行比较，在算法执行的初始阶段容易出现错误的比较，这是由于参考帧和当前帧的参考宏块和当前宏块内部的灰度值是不均匀分布的，因此可能会出现第一组的SAD部分累加之和大于 T(DISS)(1)，而第一组和第二组两组的SAD 部分累加之和小于 T(DISS)(2)，在这种情况下候选块的匹配就出现了错误。为避免上述情况的发生，需要在计算式(3)的 T(DISS)(j)时，在等式右边加上控制参数φ，其表达式为式(4)：

参数φ选取的越大，则发生错误匹配的概率越小，从而得到最优全局运动矢量的概率越大，但是如果参数φ选取得过大，会使得运算的复杂度增大，削弱了DISS算法的作用。通过验证发现，并不是所有候选块都会出现上述错误匹配，其错误主要是由于SAD累加的初始组选择。由此可知，参数φ随着计算组数的增大而减小，因而在计算阈值 T(DISS)(j)时需要在式(3)中引入控制参数ω，参数ω的表达式为式(5)，其中N表示宏块所划分的总组数：

综上所述，阈值 T(DISS)(j)的计算表达式可由式(6)表示，即在初始组的阈值 T(DISS)(j)计算时控制参数ω需较小，以有效避免匹配错误的发生，随着计算组数的增加，控制参数ω逐渐变大，使得在 T(DISS)(j)计算中则表现为 T(DISS)(j)小于SAD部分累加之和的概率增大，从而有效保证了DISS算法的效率。

2.3 改进菱形搜索算法的步骤

改进DS算法具体的计算流程如图3所示。

图3 动态内部中止搜索算法流程图

具体改进后的DS算法的步骤如下：

步骤1. 计算搜索起始中心处当前块与候选块的绝对误差和 SAD，同时计算动态零运动预判阈值 T(DESS)(i)和自适应搜索模式选择阈值 TP，当前块与候选块绝对误差和 SAD小于外部阈值T(DESS)(i)，则搜索中止，并输出位于搜索起始中心的候选块为最优匹配块。

步骤2. 利用步骤1计算得到的 TP确定采用何种初始搜索模式，如果 TP＜1，则进入步骤3，否则进入步骤4。

步骤3. 在DESS和DISS技术的基础上，对SDSP中的4个搜索点逐一进行检查直到得到最小SAD，从而减少运动估计的计算操作。如果在SDSP中的所有搜索点都不是最佳匹配块，则检查最小SAD的点，若该点位于SDSP的中心，则停止搜索，否则将该点作为初始搜索中心，然后重复步骤3。

步骤4. 在DESS和DISS技术的基础上，对LDSP中的8个搜索点逐一计算，如果所有搜索点均不是最佳匹配块，则对将最小SAD点作为新的初始搜索中心重复步骤 4。否则，如果最小 SAD点位于初始搜索中心，则以该点为SDSP模式的中心点进行搜索。

3 测试实验及结果

本文在JM12.4的基础上进行了基于改进DS算法的视频序列测试实验。视频测试序列选择代表不同运动剧烈程度和不同格式大小的 4个标准序列：运行实验环境VC++6.0，实验采用QCIF格式的Akiyo、Coast-Guard测试序列和CIF格式的Foreman、Football测试序列，其中 Football、Coast-Guard为运动变化剧烈序列，Akiyo、Foreman为运动缓慢的序列。将本文算法与几种常见的运动估计算法比较，评价算法效率的指标包括峰值信噪比(peak signal noise ratio, PSNR)、码率(bitrate，BR)和运算时间(motion estimation time，MET)，MV搜索范围为16，QP为28。实验结果如表1所示。

从表1可以看出：

(1) 针对不同运动的剧烈程度和不同格式大小的所有序列，FS算法的PSNR值均高于其他5种算法，说明 FS算法的准确度最高。本文改进DS算法相对于 FS算法的 PSNR值只减小了0.06 dB，约0.155 6%，说明本文算法的准确度基本达到了最优水平。

表1 本文算法的视频序列测试实验结果

(2) 本文改进DS算法相对于FS算法对运动变化缓慢的Akiyo和Foreman的BR值减小明显，约 0.733 0%，说明其对运动变化缓慢的序列具有显著性。

(3) 本文改进DS算法适合各种运动类型的视频序列，特别适用于运动变化剧烈的序列，并且能够在PSNR值和BR值极其接近于FS算法的情况下，相比于FS算法，对所有序列的MET减少约95%，大大减少了运动估计时间。

4 结 论

(1) 本文在传统DS算法的基础上提出了一种改进DS算法，该算法主要是通过引入动态阈值，从起始搜索点开始预测、在DS模式和搜索中止算法方面进行优化，实现了根据当前块的运动快慢来决定采用LDSP还是SDSP的自适应搜索。

(2) FS算法的准确度最高，本文提出的改进DS算法相对于 FS算法的 PSNR值只减小了0.06 dB，约0.155 6%，说明本文算法的准确度基本达到了最优水平，同时，本文算法相对于FS算法对运动变化缓慢的Akiyo和Foreman的BR值减小明显，约 0.733 0%，说明本文算法对运动变化缓慢的序列具有显著性。

(3) 本文提出的自适应DS算法适合各种运动类型的视频序列，特别适用于运动变化剧烈的序列，并且能够在PSNR值和BR值极其接近于FS算法的情况下，相比于 FS算法，对所有序列的MET减少约95%，大大减少了运动估计时间。

[1] 田 波, 杨宜民, 蔡述庭. 一种基于视觉感知的H.264 码率控制算法[J]. 图学学报, 2014, 35(5)：762-767.

[2] 周 芳, 蒋建国, 王培珍. 一种改进的视频序列超分辨率重建算法及应用[J]. 工程图学学报, 2011, 32(1)：45-51.

[3] Joint Video Team of ITU-Tand150/IECJTCI. Draft ITU-T recommendation and final draft international standard of joint video specification [S/OL]. [2004-03-20]. http：//www.itu.int/home/index.html.

[4] 张淑芳, 李 华, 刘晓青, 等. 基于 H.264的复杂度-失真最优的运动估计算法[J]. 计算机工程, 2007, 33(9)： 228-230.

[5] 杨晓琴, 季晓勇. 基于H.264的快速运动估计算法[J].计算机工程与应用, 2011, 47(4)： 174-176.

[6] 李子印, 杨 齐. 基于运动信息自适应的快速运动估计算法[J]. 中国图象图形学报, 2012, 17(9)：1069-1074.

[7] 陈 虎, 张 萍, 程 建, 等. 一种双模式的运动估计算法[J]. 计算机应用研究, 2011, 28(2)： 746-748.

[8] 唐泽鹏, 秦 雷, 朱秀昌, 等. 运动估计算法分析[J].数字电视与数字视频, 2001, 14(10)： 16-19.

[9] Li Renxiang, Zeng Bing, Liu M L. A new three-step search algorithm for block motion estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1994, 4(4)： 438-442.

[10] Zhu Ce, Lin Xiao, Chau L P. Hexagon-based search pattern for fast block motion estimation [J]. IEEE Ransactions on Circuits and Systems for Video Technology, 2002, 12(5)： 349-355.

[11] Zhu Shan, Ma Kaikuang. A new diamond search algorithm for fast matching motion estimation [J]. IEEE Trans on Image Processing, 2000, 9(2)： 287-290.

[12] Cheung C H, Po L M. A Novel cross-diamond search algorithm for fast block motion estimation [J]. IEEE Ransactions on Circuits and Systems for Video Technology, 2002, 12(12)： 1168-1177.

Improved Diamond Motion Estimation Algorithm Based on Search Prediction and Threshold Decision

Liu Yan
(Department of Information Technology, Shanxi Professional College of Finance, Taiyuan Shanxi 030008, China)

To improve the compression efficiency of the video, a self-adaptive diamond search algorithm is put forward based on traditional diamond search algorithm. The algorithm is improved in the prediction of the beginning search spot, diamond search mode and search suspended algorithm by bringing in dynamic threshold. It realizes the self-adaptive search, which reduces the internal redundant SAD operation and skips all the irrelevant blocks in the search area. The experiment result shows that the self-adaptive diamond search algorithm suits all kinds of motional video sequence, especially those sequences changing poignantly in movement. Comparing to the FS algorithm, the improved algorithm decreases approximately 95% of the motion estimation time (MET) of all the sequences under the condition that the PSNR and the code rate value are very close to FS algorithm. The motion estimation time is greatly decreased.

video compression; H.264; motion estimation; diamond search; block matching

TP 391

A

2095-302X(2015)04-0576-05

2014-05-26；定稿日期：2014-12-27

刘 艳(1982–)，女，山西平陆人，讲师，硕士。主要研究方向为计算机应用。E-mail：shxliuyan0359@163.com