基于DS-CDS的改进运动估计算法及实验

刘 艳

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

基于DS-CDS的改进运动估计算法及实验

刘 艳

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

为了提高视频的压缩效率，在菱形搜索算法和十字菱形搜索算法的基础上，结合实际运动图像中的运动向量以水平方向向量为主的特点，提出了一种利用偏水平十字模板搜索与偏向双菱形模板搜索相结合的改进搜索算法。为检验本文改进算法的效果进行了对比实验，结果表明：本文提出的基于偏水平十字及偏向双菱形搜索法适合各种运动类型的视频序列，更适用于运动变化剧烈的序列，并且能够在PSNR值和BR值接近最优水平时，大大减少运动估计时间，相比于FS算法，对QCIF格式图像的运动估计时间减少约95%，对CIF格式图像的运动估计时间减小约94%。

视频压缩；H.264；运动估计；菱形搜索算法；十字菱形搜索算法

H.264是ITU-T的联合视频组开发的一个新的数字视频编码标准，因压缩比和网络亲和性好而被广泛使用，但是，H.264标准与其他标准相比需要消耗更多的时间和资源[1-2]。运动估计算法决定了视频压缩的性能和速度，是视频压缩编码系统中的关键环节，因此寻求更高效的运动估计算法成了节省编码时间和资源，提高编码质量的重中之重[3-4]。针对运动估计运算速度的问题，国内外学者对此进行了大量的研究，提出了许多简单高效的运动估计新算法。通常，快速算法分为两类：基于全局的运动估计算法和基于模板的运动估计算法[5-6]。基于全局的运动估计算法是精度最优算法，主要通过全局搜索来寻找全局最优匹配点，其运算复杂、运算量大，但是其估计精度是所有算法中最高的。比较经典的基于模板运动估计算法主要有新三步搜索算法(new three step search, NTSS)、菱形搜索算法(diamond search, DS)和十字菱形搜索算法(cross diamond search, CDS)等，因其匹配速度快、准确率高、残差值小而被广泛使用[7-10]。由于传统搜索算法的模板是规则对称的，所以其在搜索时无论是在水平还是垂直方向搜索上也是规则对称的，而实际运动图像中的运动向量以水平方向向量为主，其水平运动比垂直方向运动剧烈。CDS算法与现实图像运动矢量的分布对接效率较高，DS算法由于充分考虑到实际视频序列中物体在水平和垂直两个方向运动的概率较其他方向大，图像频谱多呈菱形分布，是目前综合性能较好的快速搜索算法。

因此，为了提高视频的压缩效率，本文在DS算法和CDS算法的基础上，结合实际运动图像中的运动向量以水平方向向量为主的特点，提出了一种利用偏水平十字模板搜索与偏向双菱形模板搜索相结合的改进搜索算法。本文改进算法可以根据运动向量的特点来减少模板的搜索点数，达到提高视频压缩效率，节省运动估计时间的目的。

1 DS与CDS算法性能分析

1.1 DS算法

DS算法是性能比较优异的算法之一，它充分考虑到实际视频序列中物体在水平和垂直两个方向运动的概率较其他方向大，图像频谱多呈菱形分布，所以DS的模板为菱形状，它分为9点大菱形模板(large diamond search pattern, LDSP)和5点小菱形模板(small diamond search pattern, SDSP)，如图 1所示。它遵循先粗后精的搜索原则，先用LDSP模板进行粗定位，避免陷入局部最优，然后使用SDSP模板搜索粗定位中最小绝对差值和(the minimum sum of absolute difference, SAD)点的周围4个点，此时得到的SAD值最小点便是最优匹配点。

具体步骤如下：

(1) 以搜索窗口的坐标原点为搜索中心，检查LDSP模板上的9个点，若最小SAD点是中心点则转至步骤(3)；若最小SAD点不在中心点则转至步骤(2)继续搜索。

(2) 以上一步搜索到的SAD最小点为搜索中心，构造另一个LDSP进行匹配，如果新得到的最小SAD值点是中心点则转至步骤(3)；若最小SAD点不在中心点则继续步骤(2)直至匹配点到达搜索窗的边缘即停止搜索。

(3) 以上一步搜索到的SAD最小点为搜索中心，按采用SDSP进行精匹配；此时搜索到的SAD最小的点即为最优匹配点，该点相对原点的位移即是运动矢量。

图1 菱形搜索算法

1.2 CDS算法

CDS算法是在菱形搜索算法的基础上进行了改进，同样遵循先粗后精的搜索原则，十字型较之菱形与现实图像运动矢量的分布对接效率更高。CDS算法的模板为十字菱形状，它分为9点大十字菱形模板(large cross diamond search pattern, LCDSP)和5点小十字菱形模板(small cross diamond search pattern, SCDSP)，如图2所示。

图2 十字菱形搜索算法

具体步骤如下：

(1) 以搜索窗口的坐标原点为搜索中心，使用LCDSP模板作为当前模板进行搜索，若最小 SAD点是LCDSP中心点，说明图像是静止的，算法结束。

(2) 若最小SAD点在LCDSP中小十字的位置上，说明图像的运动矢量较小，则反复按照SCDSP的模板交叉搜索，此时搜索到的 SAD最小的点即为最优匹配点。

(3) 若最小SAD点在LCDSP中大十字的位置上，说明图像的运动矢量较大，则反复按照LCDSP的模板交叉搜索，此时搜索到的 SAD最小的点即为最优匹配点。

CDS算法可以根据图像的运动变换大小不同，自动选择下一步搜索的模板，做到搜索与具体的内容相关，搜索效果较理想。但是，无论DS算法还是CDS算法的搜索模板都是对称的，其在搜索时无论是在水平还是垂直方向搜索都是规则对称的。而实际运动图像中的运动向量不是规则对称的，往往以水平方向向量为主，在水平方向运动比垂直方向运动更剧烈。

2 运动估计改进算法

为了提高视频的压缩效率，本文在DS算法和CDS算法的基础上，结合实际运动图像中的运动向量以水平方向向量为主的特点，提出了一种利用偏水平十字模板搜索与偏向双菱形模板搜索相结合的改进搜索算法。首先从水平搜索方向出发，利用偏水平十字模板来初步确定搜索位置，然后利用偏向双菱形模板局部寻优，确定当前最优匹配点，若当前最优匹配点是全局最优匹配点则停止搜索，若不是，则继续寻优匹配，最后通过比较所有候选点的SAD值来确定全局最优匹配点。

2.1 搜索模板设计

在CDS算法的十字菱形模板和DS算法的菱形模板的基础上设计了一种偏水平十字模板和一种偏向双菱形模板，偏水平十字模板是结合实际运动图像中的运动向量以水平方向向量为主的特点将规则完全对称的十字菱形模板垂直方向上的点进行删减，以减少模板的搜索点数。偏向双菱形模板将菱形模板中5点SDSP进行水平方向组合和垂直方向组合，得到了9点偏向双菱形模板，既继承了DS对实际视频序列的水平和垂直方向的大概率估计，又得到了单一方向向量主导的自适应选择。偏水平十字及偏向双菱形搜索算法模板如图3所示。

图3 偏水平十字及偏向双菱形搜索算法

2.2 最优匹配准则

最优匹配准则是判定当前最优匹配点是否是全局最优匹配点，当前匹配块是否是全局最佳匹配块的准则，匹配准则的定义直接决定了编码效率和匹配精度。本算法用绝对差值和 SAD来作为快匹配准则，如式(1)：

其中，M、N分别为模板水平和垂直像素数，fk(m,n)为第k帧像素点(m,n)值，fk-1(m+i,n+j)为第k-1帧像素点(m+i,n+j)的亮度值，(i,j)为点(m,n)的偏移量。

SAD点值最小时的点即为最优的匹配点，此时的(i,j)是该模板的最佳运动矢量。

运动估计的计算如式(2)：

其中，1l和2l表示当前块和参考块划分的行数和列数；S表示搜索窗范围内的搜索点数量；Sub，Abs和Add分别表示快匹配原则中绝对误差和SAD计算中减法、绝对值和加法的计算次数。

2.3 搜索策略设计

本文改进算法流程图如图4所示。

具体步骤如下：

(1) 以搜索窗口的坐标原点为搜索中心，使用偏十字水平模板作为当前模板进行搜索，若最小SAD点是模板中心点，说明图像是静止的，搜索结束；若最小SAD点不在中心点则转至步骤(2)继续搜索。

(2) 最小 SAD点不在中心则根据运动矢量的指向来选用偏水平双菱形模板还是偏垂直双菱形模板，若当前最佳匹配点在模板中心或者偏中心的位置上则转至步骤(3)；若当前最佳匹配点在模板的边缘上则转至步骤(4)。

(3) 若当前最佳匹配点在模板中心或者偏中心的位置上，则对位于模板中心的上一点与位于模板中心的下一点进行块匹配误差计算，再和当前最佳匹配点进行比较，SAD值最小的点即为最佳匹配点，算法结束。

(4) 若当前最佳匹配点在模板的边缘上，且当前最佳匹配点处在相对于模板中心或者偏中心的水平方向上，则选用偏水平双菱形模板搜索；若当前最佳匹配点在模板的边缘上，且当前最佳匹配点处在相对于模板中心或者偏中心的垂直方向上，则选用偏垂直双菱形模板搜索。得到的最佳匹配点位于在模板中心或者偏中心的位置上则转至步骤(3)；若在模板的边缘上则转至步骤(4)。

图4 本文改进算法流程图

3 实验与结果分析

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

表1 各种算法的峰值信噪比PSNR比较

从表1可以看出，FS算法的PSNR值均高于其他4种算法，说明FS算法的准确度最高，但是，本文改进算、FS算法、DS算法、CDS算法基本处于同一水平，差异可以忽略，说明本文改进算法的精确度基本达到了最优水平。同时，还可以看出NTSS算法对CIF格式测试序列上具有不适应性。

表2 各种算法的码率BR比较

从表2可以看出，本文改进算法对运动变化剧烈的Football和Coast-Guard序列的BR值提高明显，说明本文改进算法对运动变化剧烈的序列具有显著性。

表3 各种算法的运动估计时间MET比较

从表3可以看出，针对不同运动剧烈程度和不同格式大小的所有序列均满足：本文改进算法的MET＜CDS算法＜DS算法＜FS算法，本文改进算法极大地节省了运动估计时间。同时还可以看出，各算法对QCIF大小的图像的运动估计时间均小于CIF大小的图像的运动估计时间，本文改进算法相比于FS搜索法对QCIF大小的图像的运动估计时间减少约95%，对CIF大小的图像的运动估计时间减少约94%。

综上所述，本文提出的基于偏水平十字及偏向双菱形搜索法适合各种运动类型的视频序列，更适用于运动变化剧烈的序列，且能够在PSNR值和BR值接近最优水平时，还能大大减少了运动估计时间。

4 结 论

(1) 本文在DS算法和CDS算法的基础上，结合实际运动图像中的运动向量以水平方向向量为主的特点，提出了一种利用偏水平十字模板搜索与偏向双菱形模板搜索相结合的改进搜索算法。首先从水平搜索方向出发，利用偏水平十字模板来初步确定搜索位置，然后利用偏向双菱形模板局部寻优，确定当前最优匹配点；若当前最优匹配点是全局最优匹配点则停止搜索，若不是，则继续寻优匹配，最后通过比较所有候选点的 SAD值来确定全局最优匹配点。

(2) 在本文改进算法中，偏水平十字模板是结合实际运动图像中的运动向量以水平方向向量为主特点，将规则完全对称的 CDS算法模板垂直方向上的点进行删减，以减少模板的搜索点数。偏向双菱形模板是将DS算法模板中5点SDSP进行水平方向组合和垂直方向组合，得到了9点偏向双菱形模板，既继承了DS算法对实际视频序列的水平和垂直方向的大概率估计，又得到了单一方向向量主导的自适应选择。

(3) 实验结果表明：本文提出的基于偏水平十字及偏向双菱形搜索法适合各种运动类型的视频序列，特别适用于运动变化剧烈的序列，并且能够在PSNR值和BR值接近最优水平时，还能大大减少了运动估计时间，相比于FS算法，对QCIF及CIF格式图像的运动估计时间分别减少约95%和94%。

[1] 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.

[2] 王 磊, 廖 怡, 朱忠博, 等. H.264编码器设计与运动估计算法优化[J]. 微计算机信息, 2007, 32(3): 155-156.

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

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

[5] 朱凯迪, 陈一民, 谭志鹏, 等. H.264运动估计算法研究[J].计算机工程, 2011, 37(19): 286-288.

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

[7] Li Renxiang, Zeng Bing, Liou 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.

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

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

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

Improvement of Motion Estimation Algorithm and Experiment Based on DS-CDS

Liu Yan

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

To improve the compression efficiency of the video, based on diamond search algorithm and cross diamond search algorithm, combined with the feature that motion vector was mainly focused on horizontal direction vector in actual motion images, the thesis put forward an improved search algorithm which combined partial to horizontal cross template search with biased toward double diamond template search. Comparative experiments were conducted to test the effect of improved algorithm. The result of the performance contrast experiment shows that the thesis′s improved algorithm suits all kinds of motional video sequences, especially those sequences changing poignantly in movement. Under the condition that the PSNR and the BR value are very close to the optimal level, compared to the FS algorithm, the improved algorithm decreases approximately 95% of the motion estimation time of the QCIF pictures, and decreases about 94% of the motion estimation time of the CIF pictures, thus decreases greatly the motion estimation time.

video compression; H.264; motion estimation; diamond search algorithm; cross diamond search algorithm

TP 391

A

2095-302X(2015)03-0457-05

2014-05-26；定稿日期：2015-01-14

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