蒋丽峰

（福建工程学院信息科学与工程学院，福建 福州 350108）

基于H.264的改进运动估计算法及其性能对比实验研究

蒋丽峰

（福建工程学院信息科学与工程学院，福建 福州 350108）

为提高视频压缩效率，在传统搜索算法的基础上，结合实际运动图像中的运动向量，以水平方向向量为主要特点，提出一种利用偏水平十字模板搜索与偏向双菱形模板搜索相结合的改进搜索算法。该改进算法可以根据运动向量的特点来减少模板的搜索点数，达到提高视频压缩效率、节省运动估计时间的目的。性能对比实验结果表明：该改进算法适合各种运动类型的视频序列，尤其适用于运动变化剧烈的序列，并且能够在PSNR值和码率值极其接近FS算法的情况下，对QCIF格式图像的运动估计时间（MET）减少约95%，对CIF格式图像的运动估计时间（MET）减小约94.5%，大大减少运动估计时间。

视频压缩；H.264标准；运动估计；快速搜索算法

0　引　言

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

因此，为了提高视频的压缩效率，本文在菱形搜索算法（DS）和十字菱形搜索算法（CDS）的基础上，结合实际运动图像中的运动向量以水平方向为主的特点，提出了一种利用偏水平十字模板搜索与偏向双菱形模板搜索相结合的改进搜索算法。

1　菱形与十字菱形搜索算法性能分析

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

图1　菱形搜索算法

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

图2　十字菱形搜索算法

菱形搜索算法（DS）充分考虑了实际视频序列中物体在水平和垂直两个方向运动的概率较其他方向大，图像频谱多呈菱形分布的特点，而十字菱形搜索算法（CDS）与现实图像运动矢量的分布对接效率更高，这两种算法是目前综合性能较好的快速搜索算法。这两种搜索算法也因其匹配速度快准确率高残差值小而被广泛使用。

2　运动估计新算法

为了提高视频的压缩效率，本文首先从水平搜索方向出发，利用偏水平十字模板来初步确定搜索位置，然后利用偏向双菱形模板局部寻优，确定当前最优匹配点，若当前最优匹配点是全局最优匹配点则停止搜索，否则继续寻优匹配，最后通过比较所有候选点的SAD值（差的绝对值的和）来确定全局最优匹配点。

2.1搜索模板设计

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

2.2最优匹配准则

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

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

SAD最小时的点即为最优的匹配点。

运动估计的计算操作数可以通过下式计算：

式中：l1、l2——当前块和参考块划分的行数和列数；

S——搜索窗范围内的搜索点数量；

Sub、Abs、Add——快匹配原则中绝对误差和

SAD计算中减法、绝对值和加法的计算次数。

2.3搜索策略设计

算法流程图如图4所示。

图4　本文改进算法流程图

具体步骤如下：

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

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

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

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

3　对比实验与结果分析

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

从表1可以看出，针对不同运动剧烈程度和不同格式大小的所有序列，FS算法的PSNR值均高于其他4种算法的PSNR值，说明FS算法的准确度最高。本文改进算法相对于FS算法的PSNR值平均只减小了0.033dB，其影响基本可以忽略。说明本文改进算法的准确度基本达到了最优水平。

从表2可以看出，本文改进算法和十字菱形搜索算法（CDS）对运动变化剧烈的Football和Coast-Guard序列的码率提高明显，在1.5%～2.5%之间。说明本文改进算法和十字菱形搜索算法（CDS）对运动变化剧烈的序列具有显著性。

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

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

表2　各算法的码率BR比较

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

综上所述，本文提出的基于偏水平十字及偏向双菱形搜索法适合各种运动类型的视频序列，特别适用于运动变化剧烈的序列，并且能够在PSNR值和码率值极其接近于FS算法的情况下，大大减少运动估计时间。

4　结束语

1）本文在传统搜索算法的基础上，结合实际运动图像中的运动向量以水平方向向量为主的特点，提出了一种利用偏水平十字模板搜索与偏向双菱形模板搜索相结合的改进搜索算法。

2）FS算法的准确度最高，本文改进算法相对于FS算法的PSNR值平均只减小了0.033dB，其影响基本可以忽略。说明本文改进算法的准确度基本达到了最优水平。本文改进算法对运动变化剧烈的Football和Coast-Guard序列的码率提高明显，在1.5%～2.5%之间，本文算法对运动变化剧烈的序列具有显著性。

3）本文提出的基于偏水平十字及偏向双菱形搜索算法适合各种运动类型的视频序列，特别适用于运动变化剧烈的序列，并且能够在PSNR值和码率值极其接近于FS算法的情况下，对QCIF格式图像的运动估计时间（MET）减少约95%，对CIF格式图像的运动估计时间（MET）减小约94.5%，大大减少了运动估计时间。

[1]王磊，廖怡，朱忠博，等.H.264编码器设计与运动估计算法优化[J].微计算机信息，2007，32（3）：155-156.

[2]朱凯迪，陈一民，谭志鹏，等.H.264运动估计算法研究[J].计算机工程，2011，37（9）：286-288.

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

[4]Li R，Zeng B，Liu M L.A new three-step search algorithm for block motion estimation[J].IEEE Trans Circuits Syst Video Technol，1994，4（4）：438-442.

[5]Zhu S，Ma K K.A new diamond search algorithm for fast matching motion estimation[J].IEEE Trans on Image Processing，2000，9（2）：287-290.

[6]Cheung C H，Po L M.A novel cross-diamond search algorithm for fast block motion estimation[J].IEEE Trans Circuits Syst Video Technol，2002，12（12）：1168-1177.

[7]Babu R V，Ramakrishnan K R.Video object segmentation：Acompressed domain approach[J].IEEE Transactions on Circuits and Systems for Video Technology，2004，14（4）：462-474.

[8]Zeng W，Du J，Gao W，et al.Robust moving object segmentation on H.264/AVC compressed video using the block-based MRF model[J].Real-time Imaging，2005，11（4）：290-299.

Research on improved motion estimation algorithm and its performance comparison experiment based on H.264

JIANG Lifeng
（School of Information Science and Engineering，Fujian University of Technology，Fuzhou 350108，China）

Toimprove video compression efficiency，this paper，basedontraditional search algorithms and the motion vector that is chiefly moving in the horizontal direction in actual motion images，has put forward an improved search algorithm，which is a combination of partial to horizontal cross template searching and biased double-diamond template searching.In accordance with the feature of the motion vector，the number of searching spots can be reduced so as to increase the video compression efficiency and shorten the motion estimation time.The performance contrast experiment shows that this improved algorithm suits all types of motional video sequences，especially those changing drastically in movement.Under the condition that the value of PSNR and code rate is very close to FS algorithm，it can decrease around 95%of the motion estimation time(MET)of QCIF pictures and about 94.5%of the MET of CIF pictures respectively compared to the FS algorithm.

video compression；H.264 standard；motion estimation；fast search algorithm

A

1674-5124（2015）12-0128-04

10.11857/j.issn.1674-5124.2015.12.031

2015-05-27；

2015-06-18

福建省教育厅A类项目（JA13219）

蒋丽峰（1979-），女，湖南娄底市人，硕士，研究方向为计算智能和人工智能。