 Optoelectronics 光电子, 2011, 1, 16-20 http://dx.doi.org/10.12677/oe.2011.12004 Published Online December 2011 (http://www.hanspub.org/journal/oe) Copyright © 2011 Hanspub OE Optimization of Motion Estimation Algorithm in H.264 Video Encoder* Qindi Guo, Changgui Long School of Computer and Communication Engineering, Tianjin University of Technology, Engineering Research Center of Communication Devices Ministry of Education, Tianjin Email: guopengost@126.com Received: Sep. 20th, 2011; revised: Oct. 16th, 2011; accepted: Nov. 2nd, 2011. Abstract: Structural Motion estimation is the key technology of Video coding, The UMHexagonS algorithm of H.264 encoder has a good overall performance, while its computation is still relatively large to meet the requirement of real-time encoding. In this paper, based on the complexity of image motion in MVFAST algorithm, an improved UMHexagonS algorithm is proposed. Based on ROS (region of support), by setting search range separately in the four directions of horizontal and vertical, a dynamic search window was established to covering the best match point using a smaller search window; Further according to the image motion complexity, the selection strategy of initial search template was optimized , which directly reduce the computation of low and middle complexity of motion video sequence. Experiments show that, compared to UMHexagonS algorithm, our optimized algorithm can save about 24.53% ME time but almost has no change in the reconstructed picture quality and bitrate; and ME time is 6.24% lesser than compared algorithm as well as enhance the real-time performance of the encoder. Keywords: H.264; Umhexagons; Motion Estimation; Motion Complexity; MVFAST H.264 视频编码器中运动估计算法的优化* 郭亲弟，龙长贵 天津理工大学计算机与通信工程学院，通信器件教育部工程研究中心，天津 Email: guopengost@126.com 收稿日期：2011 年9月20 日；修回日期：2011年10 月16 日；录用日期：2011 年11月2日 摘 要：运动估计是视频编码的关键技术，H.264 编码器中的运动估计采用 UMHexagonS 算法，具有 良好的综合性能，但其运算量仍比较大，难以满足实时编码的要求。本文基于MVFAST 算法图像运动 复杂度，提出了一种 UMHexagonS 的改进算法。依据 ROS(支撑域)，通过在水平垂直的四个方向上分 别设置搜索范围，建立了非搜索中心对称的动态窗口，用更小的搜索范围覆盖了最佳匹配点，进一步 减小了搜索点数；进一步根据图像运动复杂度，优化了起始搜索模板的选择策略，直接减少了中等和 低等运动复杂度视频序列的计算量。实验表明，与 UMHexagonS 算法相比，改进后的算法在获得几乎 同等重建图像质量和码率的同时，运动估计时间平均节省了 24.53%；与对照文献相比算法节省了 6.24%，有效的提高了编码器的实时性。 关键词：H.264；UMHexagonS；运动估计；运动复杂度；MVFAST 1. 引言 运动估计是视频编码的关键技术，能够有效减小 视频序列的时间冗余，其算法性能直接影响着视频编 码的质量和效率。H.264 编码器[1]中的运动估计采用非 对称十字型多层次六边形格点搜索算法[2](UMHexa gonS)，它结合了搜索中心预测、混合搜索模板、提前 终止等技术，具有良好的综合性能。但其运算量还比 较大，难以满足实时编码的要求。为减少运算量，人 *基金项目：2010 年天津市科技创新专项资金项目(10FDZDGX 00400)。  郭亲弟 等 视频编码器中运动估计算法的优化 17 H.264 们从不同技术方面优化了该算法。文献[3]利用全零块 判决来提前终止搜索，文献[4]利用自适应阈值改进算 法搜索策略，文献[5]使用动态搜索窗口优化搜索区域， 文献[6]根据运动矢量的时域相关性简化了六边形搜索 模板，减少了搜索点数。本文则主要从搜索窗口和搜 索模板两个方面对 UMHexagonS 算法进行改进，可更 有效的减小运算量。 对于搜索窗口，本文充分利用视频运动在时域上 的连续性[7]，在以当前宏块空域相邻宏块运动矢量[8] 为支撑域(ROS)的基础上[9,10]，添加了与当前宏块有强 相关性的前一帧相同位置宏块的运动矢量，并依据 ROS，建立了非搜索中心对称的动态窗口，用更小的 搜索范围覆盖了最佳匹配点，减小了搜索点数。 对于搜索模板，本文利用 MPEG-4 编码器的 MVFAST 算法中根据运动复杂度选择搜索模板的思 想，结合 UMHexagonS 算法中多种模板形式的良好性 能，自适应的选择大菱形、六边形和小菱形模板作为 起始搜索模板，直接减少了中低等运动复杂度视频序 列的运算量。 两种改进的结合能够有效的减少 UMHexagonS 算 法的运算量，提高算法的鲁棒性。对不同运动复杂度 的视频序列实验表明，与 UMHexagonS 算法相比，改 进后的算法在获得几乎同等重建图像质量和码率的同 时，运动估计时间平均节省了24.53%，比 文 献 [6]相比 算法节省了 6.24%，有效地提高了编码器的实时性。 2. UMHexagonS算法分析 UMHexgons 算法是以块匹配为基础的运动估计 算法，采用多种模板的搜索策略，通过五个步骤实现： 步骤 1：预测搜索过程的起始搜索点 步骤 2：非对称的十字交叉搜索 步骤 3：非均匀多层次六边形格点搜索 此步骤分为：5 × 5 全搜索与非对称大六边形格网 搜索。 1) 5 × 5全搜索：以上一步搜索点为中心进行 5 × 5 的整像素全搜索。 2) 多层六边形搜索：六边形搜索由内至外逐层展 开，选出的最佳匹配块位置作为下一步搜索的起始位置。 步骤 4：小六边形搜索 以上一步中的最优点为中心进行小六边形搜索， 直到最优点处在六边形的中心点。 步骤 5：菱形搜索 以上一步的最优搜索点为起始中心进行步长为 1 的小菱形搜索，直到最优点处在菱形的中心。 该算法对宏块的 7种(H.264 编码支持 7种宏块， 其块大小是 16 × 16, 16 × 8, 8 × 16, 8 × 8, 8 × 4, 4 × 8 和4 × 4)不同分割尺寸都采用了相同大小的搜索窗口， 对4 × 4小块势必会增加一些无用点的搜索；而对 16 × 16 的大块可能由于运动比较剧烈而在固定大小的窗 口中无法找到最佳匹配的块，对此文献[6]建立了以最 佳预测点为中心的正方形搜索窗口，没有在水平垂直 四个方向上分别设置搜索范围，还存在对一些无用点 的搜索，我们把这个标记为问题一。 另外，该算法对不同运动复杂度的视频图像，都 采用相同的起始模板开始搜索，即步骤 2中的模板， 这样对于中等和低等运动复杂度的视频序列势必会存 在一些无用点的搜索，我们把这个标记为问题二。 3. UMHexagonS算法的优化 为解决问题一和二，本文利用当前宏块的时空强 相关性建立 ROS，通过分析 ROS 中运动矢量的绝对 变化量判断当前宏块的运动复杂度，根据运动复杂度 建立动态搜索窗口。 建立 ROS 为 00123 ,,,,VMVMVMVMVV4 ，其中 及下文各式中 , iii M Vxy，i = 0, 1, 2, 3, 4。分别表 示当前宏块(0, 0)处及其空域左、上、右上宏块和时域 上相邻参考帧相同位置宏块的运动矢量。 Figure 1. Motion vectors in ROS 图1. ROS中的运动矢量 Copyright © 2011 Hanspub OE  郭亲弟 等 视频编码器中运动估计算法的优化 H.264 18 3.1. 动态搜索窗口 针对问题一，本文依据当前宏块的运动复杂度， 自适应的选择起始搜索模板对运动矢量进行搜索。运 动的复杂度与运动矢量相关，运动矢量越大则复杂度 越大，运动矢量越小则复杂度越小。利用式(1)计算运 动复杂度： ,0,1,2,3, ii C=maxx -x+y -yi=4 (1) 其中， 01234 ,mean, ,,,(xy)MV MVMV MVV。设 定两个阈值,将C分成三个区段，代表 3种不同的运动 复杂度，用式(2)表示： 1 12 2 1 2 3 CC CPXC <CC C>C ，低复杂度 ，中等复杂度 ，高复杂度 其中，CPX具体详细地放映了运动估计矢量在空 域的一致性以及在时域中前一参考帧和当前帧同位置 运动矢量有相同的值。文献[11]通过大量的实验得到了 能够很好判断当前宏块运动复杂度的阈值设置，本文 参考文献[11]选取阈值 C1 = 1，C2 = 4。根据视频运动的 复杂度，可将物体运动分为 低频运动 块(低复杂度)，中 频运动快(中等复杂度)，高频运动快(高复杂度)。低频 运动块由于运动幅度较小，其残差块 所含 数据较少，采 用较大窗口的搜索模式。中频运动块很难确定为哪一 种，所以需要 7种窗口搜索模式。高频运动块由于运动 幅度大，残差块所含数据多，采用小窗口的搜索模式。 3.2. 搜索模板 根据视频运动的特性，物体在水平和垂直方向上 具有更大的运动概率，为了更好的适应相应类型的模 板，将六边形的搜索模板进行改进。在搜索的过程中 采用水平六边形和垂直六边形以及正六边形搜索模 板。搜索模板如下图 2。 针对不同的模式，采用不同的搜索模板。16 × 8 和8 × 4模式采用水平六边形搜索模式。8 × 16和4 × 8 模式采用垂直六边形搜索模板。16 × 16，8 × 8 和4 × 4 模式采用正六边形搜索模板。 根据上面对 UMHexagonS 算法的优化改进算法的 流程：如图3(b)，首先计算运动复杂度 C的值。依据 运动复杂度，分别采用不同搜索窗口，当C < C1 时， (1)水平六边形 (2)正六边形 (3)垂直六边形 Figure 2. Template search 图2 模板搜索 (a)UMHexagons 算法 (b)改进后算法 Figure 3. Search process 图3. 搜索流程 进行大窗口搜索模式简化搜索过程，提高运算速 度，选用16 × 16，16 × 8 和8 × 16 模式进行搜索，然 后进行小菱形搜索。当 C > C2 时，先进行非对称十字 交叉搜索，然后进行模式判别，依据不同搜索模式， 分别采用水平六边形模板、正六边形模板、垂直六边 形模板进行搜索。 最后用小菱形搜索结束搜索。当C在两者之间直 接进行模式判别来选择合适搜索模板，最后进行小菱 形搜索。优化前后的流程图如图 3所示。 Copyright © 2011 Hanspub OE  郭亲弟 等 视频编码器中运动估计算法的优化 19 H.264 4. 实验结果及分析 为了验证算法的性能，本文将C语言实现的算法 集成到 H.264 的标准参考软件JM 中进行测试。以FS 和UMHexagonS 算法为比较对象，选择 8个具有代表 性的 CIF格式国际标准测试序列进行测试。实验所用 PC 机的硬件配置为：Intel(R) Pentium(R) D CPU 1.80 GHz，1 G 内存，操作系统为 WindowsXP2002 + SP3。 J M 配置为：编码序列前 100 帧，块大小为16 × 16 像 素，最大搜索范围为 ±16像素，匹配准则为 SAD 准 则。实验结果主要以亮度PSNR 值，码率和运动估计 时间三个参数进行比较。PSNR值指峰值信噪比，用 来评价重建图像质量。码率能够反映不同算法对编码 系统整体压缩比的影响。运动估计时间直观的反映了 不同算法的运算量。 表1中“Mother”、“News”、“Container”为运动复 杂度低的序列，“Highway”、“Foreman”为运动复杂度 中等的序列，“Coastguard”、“Football”、“Mobile”为运 动复杂度高的序列。UMH表示 UMHexgons 原算法， DR 表示在 UMHexgons 原算法中加入了动态搜索窗口 算法，AP 表示在UMHexagonS 算法中建立自适应搜 索模板的算法，(DR, AP)表示在 UMHexagonS 算法中 建立动态搜索窗口和自适应搜索模板算法，ΔP，ΔB 和ΔT分别表示与 UMHexagonS 相比 PSNR 的变化值、 比特率的变化量和运动估计时间的变化百分比。 从表 1可以看出，AP 算法与 UMHexagonS 几乎 保持了相同的重建图像质量，但运动估计时间平均节 省了 17.31%，且对复杂度高的运动序列，运动估计速 度有更大程度的提升。与文献[6]中的动态范围算法节 省的运动估计时间相比，平均多节省了 2.69% ，说 明 本文的 AP 算法能够以更小的计算量找到最优运动矢 量。AP 算法与 UMHexagonS 相比，PSNR 值平均损 失了 0.0018，但运动估计时间平均节省了18.01%。表 明这两种优化算法都提高了 UMHexagonS算法的运动 估计速度。 表2中的结果为文献[6]的算法与本文算法分别与 全搜索(FS)和UMHexagonS 算法相比各性能指标改变 的相对值。 从表 2可以看出，本文算法的特点如下：1) 基本 保持了重建图象质量。与FS 相比，亮度信号的 PSNR 性能平均损失了0.0086 dB，最大损失不超过 0.013 dB，与 UMHexagonS 算法相比，亮度信号的PSNR 性 能平均损失了0.0016 dB，最大损失不超过 0.004 dB； 2) 比特率的增加很少。与 FS 相比，平均值为0.826 Kb/s，与 UMHexagonS 相比，平均值为 0.786 Kb/s； 3) 运动估计耗时明显下降。与 FS 相比，运动估计时 间平均下降了287.72%；与 UMHexagonS 相比，运动 估计时间平均下降了 24.53%。与文献[6]的算法相比， 本文算法损失的重建图像质量非常小，增加的比特率 较小，但运动估计时间多节省了 6.24%。 Table1. Performance comparison of different improved algorithm 表1. 不同改进算法的性能比较 Test sequenceAlgorithmΔP (dB) ΔB (Kb/s) ΔT (%) UMH 0 0 0 DR –0.001 –0.01 –13.67 AP –0.002 –0.09 –16.19 Mother DR、AP –0.002 –0.11 –18.81 UMH 0 0 0 DR 0 +0.01 –14.57 AP –0.001 –0.3 –17.28 News DR、AP –0.003 –0.32 –20.19 UMH 0 0 0 DR –0.001 +0.02 –17.82 AP –0.002 +0.45 – 17.76 Container DR、AP –0.002 +0.46 –20.19 UMH 0 0 0 DR 0 –2.28 –13.73 AP –0.002 +1.62 –17.55 Highway DR、AP –0.001 +1.77 –18.27 UM`H 0 0 0 DR –0.001 –0.01 –12.26 AP –0.004 –0.26 –18.55 Foreman DR、AP –0.004 –0.27 –20.22 UMH 0 0 0 DR 0 +0.01 –21.43 AP +0.001 +0.97 –18.72 Football DR、AP +0.003 +0.99 –26.95 UMH 0 0 0 DR +0.001 +0.56 –16.81 AP +0.002 +1.50 –25.19 Coastguard DR、AP +0.003 +1.48 –25.62 UMH 0 0 0 DR +0.002 –0.02 –28.19 AP –0.003 +1.26 –12.83 Mobile DR、AP –0.002 +1.27 –38.36 Copyright © 2011 Hanspub OE  郭亲弟 等 H.264 视频编码器中运动估计算法的优化 Copyright © 2011 Hanspub OE 20 Table 2. Performance comparison of different algorithms 表2. 不同算法的性能比较 algorithm in [6] algorithm in this paper Test sequence algorithm ΔP (dB) ΔB (Kb/s) ΔT (%) ΔP (dB) ΔB (Kb/s) ΔT (%) FS +0.01 +2.19 –235.38 –0.006 +1.64 –374.35 Mobile UMHexagonS +0.01 +0.58 –28.23 –0.002 +1.27 –38.36 FS +0.04 +4.69 –214.52 –0.011 +0.02 –275.93 Coastguard UMHexagonS +0.01 +0.58 –22.76 –0.002 +1.48 –25.62 FS +0.03 –0.01 –291.93 –0.012 +0.40 –240.44 News UMHexagonS –0.02 +0.21 –13.13 –0.003 –0.32 –20.19 FS +0.03 +3.56 –171.04 –0.013 +1.08 –253.59 Foreman UMHexagonS +0.02 +0.74 –11.80 –0.004 –0.27 –20.22 FS 0 +4.70 –265.48 –0.001 +0.99 –294.30 Highway UMHexagonS 0 +1.19 –15.54 +0.003 +1.77 –18.27 由以上分析可知，优化后的算法获得了较高的运 动估计速度，这是以损失重建图像质量和提高码率为 代价的，但是这种代价始终维持在较低的水平(都小于 l％)，对视频编码器的实际应用基本不会造成影响。 5. 结论 本文对 UMHexagonS 算法进行了改进，利用视频 图像中运动矢量时空域的高度相关性，建立了动态的 搜索范围，通过判断宏块的运动复杂度，自适应的选 择起始搜索模板。在获得保持重建图像质量和码率的 同时，运动估计时间平均节省了 24.53%，提高了编码 器的实时性，具有很好的实用价值和意义。 6. 致谢 此刻我对资助者或支持者、提供指导和帮助者、 给予转载和引用权的资料、图片、文献、研究思想和 设想的所有者，表示感谢。 参考文献 (References) [1] T. Wiegand, G. Sullivan, G. Bjontegaard, et al. Overview of the H.264/AVC video coding standard. IEEE Transactions on Cir- cuits and Systems for Video, 2003, 13(7): 560-576. [2] B. C. Zhi, Z. Peng and H. Yun. Fast integer pel and fractional pel motion estimation for JVT. JVT 6th Meeting, Document JVT- F017, Awaji, 5-13 December 2002. [3] Y. Cheng, K. Dai and Z. Y. Wang. A new zero block detection method for H.264/AVC. Journal of Computer Research and De- velopment, 2005, 42(10): 1758-1762. [4] W. Wei, Z. X. Hou. A fast motion estimation algorithm with adaptive threshold. Journal of Optoelectronics·Laser, 2008, 19(9): 1254-1257. [5] X. Z. Xu, Y. He. Modification of dynamic search range for JVT. JVT-Q088, 17th Meeting on Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 14-21 October 2005, USA. [6] X. J. Wu, S. J. Bai and W. T. Lu. Optimization on motion esti- mation algorithm based on H.264. Journals of Electronic, 2009, 37(11): 2541-2145. [7] J.-Y. Nan, J.-S. Seo, et al. New fast search algorithm for block matching motion estimation using temporal and spatial cor- relation or motion vector. IEEE Trans on Consumer Electronics, 2000, 46(4): 934-942. [8] Y. Q. Zhang, S. Zafar. Predictive block-matching motion estima- tion for TV Coding. IEEE Transactions on Broadcasting, 1991, 37(3): 102-105. [9] P. I. Hosur, K.-K. Ma. Motion vector field adaptive fast motion estimation. Second International Conference on Information, Communications and Signal Processing (ICICS’99), Singapore, 7-10 December 1999. [10] A. M. Tourapis, O. C. Au and M. L. Liou. Predictive motion vector field adaptive search technique (PMVFAST). ISO/IEC JTC1/ SC29/WG11 M5866, Noordwijkerhout, March 2000. [11] I. Ahmad, W. G. Zheng. A fast adaptive motion estimation algorithms. IEEE Trans Circuits and Syst Video Technol, 2006, 16: 420-438. |