基于H.264的一种混合运动搜索算法
2010-03-14张正华陆大伟海爱成
张正华，陆大伟，海爱成，陈 亮
（扬州大学 信息工程学院，江苏 扬州 225009）
1 引言
H.264标准[1-3]作为新一代视频编码的标准，它的主要任务是在时域和空域上减少视频的冗余信息，相应的有帧间编码技术[4-6]和帧内编码技术[7]。而运动估计是帧间编码中的一项核心技术，它能有效的去除视频序列的帧间时域冗余，从而提高编码效率。研究快速有效的运动估计算法一直是帧间编码领域的热点问题，其中，全搜索算法（Full Search，FS）的精度最高，但是计算复杂度大，耗时长，导致很难进行实际应用，因此，研究者们提出了各种快速运动搜索算法，比较适用的有菱形搜索算法[8]（Diamond Search，DS）、六边形搜索算法[9]（Hexagon Based Search，HEXBS）、基于块的梯度下降搜索算法[10]（Block-based Gradient Descent Search，BBGDS）等等，这些快速算法通过使用不同的搜索模板和策略，减少了计算复杂度。因此，本文就如何减少平均搜索点数，从而减少计算复杂度，提出了一种混合运动搜索算法，采用三种搜索窗口：矩形搜索窗口、大菱形搜索窗口以及小六边形搜索窗口，仿真结果表明，该算法可以有效减少平均运动搜索点数，提高编码效率，同时能保证较好的编码质量。
2 块匹配准则
在基于块的快速运动搜索算法中，需要使用块匹配准则来衡量两个相匹配的像素块之间的误差，通常有3种块匹配准则：最小绝对差（Minimum Absolute Difference，MAD）、均方误差和（Mean Square Error，MSE）和归一化互相关函数（Normalized Cross Correlation Function，NCCF）。
实践结果表明，采用以上3种块匹配准则中的任何一个，匹配结果都差不多，而采用MAD作为匹配准则，不需要作乘法运算，实现简单，因此通常采用MAD作为匹配准则。但是在实际应用中，考虑到块匹配的大小基本控制在16×16点像素之内，对参考帧和当前帧对应像素的差值取绝对值后累加求和的数值，可以直接进行比较；同时，对绝对差之和进行除法运算减低了计算的精度，所以本文采用MAD的变化形式绝对误差和（Sum of Absolute Difference，SAD）作为判断准则，其表达式为
式中：（i，j）为位移矢量，若在某一个（i，j）处的 SAD（i，j）值最小，则该点为最佳匹配点；xk（m，n）和 xk-1（m+i，n+j）分别为第k帧和第k-1帧的像素值。
3 混合运动搜索算法
本文算法采用3种搜索窗口：矩形窗口、大菱形窗口和小六边形窗口，如图1所示。
图1 3种搜索窗口
其中，矩形窗口，由3×3的点阵构成，适用于各种视频序列的初步搜索；大菱形窗口，它由外围的8个点加上中心的1个点构成，适用于一般运动的视频序列的进一步搜索；小六边形窗口，它由外围的4个点加上中心的1个点构成，适用于运动剧烈的视频序列的精确搜索。
终上所述，笔者提出的算法步骤如下：
1）以3×3矩形窗口为搜索窗口，检测此窗口的8个点，外加中心点，若最佳匹配点位于中心，则跳到3），否则进行下一步；
2）以上一步最佳匹配点为中心构造一个大菱形窗口，检测其9个点，若最佳匹配点位于中心，则进行下一步，否则重复这一步；
3）以小六边形窗口为搜索模板，检测外围的4个点，得到最佳目标运动矢量。
算法示意图如图2所示。
图2 混合搜索算法
4 实验结果与分析
为了验证所提算法的性能，进行了一些实验，块大小为16×16，仿真的视频序列采用3种不同运动形式的foreman，carphone和 highway，分别取 100 帧，均为 QCIF格式。
下面为部分配置语言：
#define XX 144
#define YY 176
#define OPEN_FILE “E：\视频信号处理 \test1_dec.yuv”
#define REF_FILE “E：\视频信号处理\foreman_qcif.yuv”
#define BLOCK_HEIGTH 16
#define BLOCK_WIDTH 16
#define MAX_MOTION 16
const int SEARCH_RANGE=MAX_MOTION*2+1；
const int X=XX/BLOCK_HEIGTH；
const int Y=YY/BLOCK_WIDTH；
在上述定义中，规定了输入序列的格式、块的宽度和高度以及搜索的范围，其中，OPEN_FILE是用H.264标准测试软件JM12.4编码时产生的重建序列，REF_FILE为原始序列。
仿真结果如表1所示，其中COST代表平均所搜点数，PSNR为匹配图像与原始图像的峰值信噪比。
表1 仿真结果
经计算，本文算法的平均搜索点数约为FS的1/86，并比DS与HS少搜索1个点左右，仅比BBGDS多搜索1个点左右；同时平均峰值信噪比要比DS高出约0.02 dB，比HS高出约0.11 dB，仅比BBGDS低约0.02 dB。这些结果表明本文算法在降低平均搜索点数，从而降低计算复杂度方面取得了良好的效果，同时能够保证较好的率失真性能。
在Matlab中分别画出3种输入视频序列foreman，carphone和 highway在 DS，HS，BBGGS以及本文算法 4种快速算法下的结果，如图3～5所示。可见，本文算法在搜索点数和PSNR两方面都要要优于DS算法和HS算法，并在图像质量上与BBGDS算法相当。
图3 foreman序列实验结果
图4 carphone序列实验结果
图5 highway序列实验结果
5 小结
针对减少运动搜索算法的计算复杂度，笔者提出了一种混合搜索算法，仿真结果表明，对于各种不同运动特征的输入视频序列，本文算法均取得了良好的效果，与FS相比，极大地减少了运动搜索点数，提高了编码效率，并优于现有的优秀算法DS和HS，且在保持率失真性能上和BBGDS相当。也就是说本文算法在减低计算复杂度以及保证运动搜索的准确性方面具有一定的贡献。
当然在一些编码性能要求更高的场合以及恶劣的无线信道，如何进一步降低计算复杂度，提高编码效率，保持较好的编码质量，尚需以后进一步研究。
[1]JVT of ISO/IEC MPEG and ITU-T VCEG.ITU-T Rec.H.264|ISO/IEC 14496-10 AVC.Draft ITU-T recommendation and final draft international standard of joint video specification[S].2005.
[2]WIEGAND T，SULLIVAN G J，BJONTEGAARD G，et al.Overview of the H.264/AVC video coding standard[J].IEEE Trans.CSVT，2003，13（7）：560-576.
[3]RICHARDSON I E G.H.264 and MPEG-4 video compression[M].New York：John Wiley&Sons Ltd.，2003：85-97.
[4]SHEN Li-quan，LIU Zhi，ZHANG Zhao-yang，et al.Fast inter mode decision using spatial property of motion field[J].IEEE Trans.Multim，2008，10（6）：1208-1214.
[5]陆大伟，张正华，海爱成.基于H.264的P帧模式选择算法优化[J].扬州大学学报：自然科学版，2009，12（3）：43-46.
[6]ZHANG Zheng-hua，HU Zhen，HAIAi-cheng，et al.Performance study of error resilience with multiple reference frames in H.264/AVC in conditions of low Bit-rate[J].Proc.9th International Conference on Electronic Measurement&Instruments：Vol.3.Beijing：IEEE Press，2009：298-301.
[7]桑亚林，张正华，陆大伟.低码率无线视频传输中的帧内刷新技术[J].扬州大学学报：自然科学版，2008，11（3）：35-39.
[8]ZHU S，MA K K.A new diamond search algorithm for fast block matching motion estimation.IEEE Trans.Image Processing，2000，9（2）：287-290.
[9]TOURAPISA M，SHEN G，LIOU M L，et al.A new predictive diamond search algorithm for block based motion estimation[C]//Proceedings of SPIE Vol.4067.[S.l.]：SPIE Press，2000：1365-1373.
[10]LIU L K，FEIG E.A block-based gradient descent search algorithm for block motion estimation in video coding[J].IEEE Trans.CASYT，1996，6（4）：419-422.
