基于矢量预测的快速运动估计搜索算法

　　文章编号 :1671 - 637 Ⅹ(2008) 0420017204 基于矢量预测的快速运动估计搜索算法 迟 　茜 , 　何明一 (西北工业大学电子信息学院 ,西安 　710072) 摘 　　　要 : 　基于 H. 264 视频编码标准的编解码过程中 ,运动估计的时间大概要占总编码时间 的 70 %(1 个参考帧)到 90 %(5 个参考帧) 。对于 H. 264 标准的新特点 ,传统的全搜索算法的精度 高 ,但计算量太大 ,不能应用于实时处理 ;经典的菱形等算法搜索模式简单 ,易于实现 ,但容易陷入 局部无穷小。采用了一种基于运动矢量预测的快速运动估计搜索算法。该方法首先利用运动矢量 的时、空间相关性得到预测矢量 ,然后利用非对称十字型搜索确定运动估计的起始点 ,最后采用经 典的菱形算法进行运动估计。实验结果表明 ,相比 UMHexagonS 快速搜索算法 ,该算法能够在码率 增加不超过 1 % ,信噪比下降不超过 0. 1 dB 的情况下 ,运动估计速度有较大提高。 关 　键 　词 : 　视频编码 ; 　H. 264 ; 　矢量预测 ; 　运动估计 中图分类号 : 　V271. 4 ; 　TN919. 81 文献标识码 : 　A A fast motion estimation search algorithm based on vector prediction CHI Qian , 　HE Ming2yi ( Institute of Electronics and Information , Northwestern Polytechnical University , Xi’an 710072 , China) Abstract : 　Motion Estimation (ME) can consume 70 %(1 reference frame) to 90 %(5 reference frames) of en2 coding time of the H. 264. Traditional full2search algorithm of inter coding has high precision ,but the computa2 tion cost is so large that it can not be used for real2time processing. Classical Diamond Search (DS) algorithm is simple ,but is likely to be trapped into a local minimum. We used a quick search algorithm based on motion vector prediction. This algorithm utilizes the temporal and spacial correlation of the motion vector for obtaining the predictive vector ,then uses unsymmetrical2cross search to determinate a starting point for motion estima2 tion ;and uses diamond search algorithm at last to end up the motion estimation. The experimentation result show that :compared with UMHexagonS ,the algorithm can increase motion estimating speed greatly with an in2 crease of coding rate no more than 1 % bite2rate and descending of SNR no more 0. 1 dB. Key words : 　video encoding ; 　H. 264 ; 　vector prediction ; 　motion estimation 0 　引言 H. 264 是新一代视频压缩编码标准 ,相对于以 前的视频编码标准最大的不同是它支持16 ×16到 4 ×4的树状块分割模式 (如图 1 所示) 、1Π4 像素搜索 精度以及多参考帧的运动估计和补偿 ,从而改善了 预测误差 , 极大地提高编码效率 , 但是其编码效率 收稿日期 :2007201211 　　　修回日期 :2007201229 作者简介 :迟 　茜 (1981 - ) ,女 ,山东聊城人 ,硕士生 ,研究方 向为信息与信号处理。 的提高是以增加编码算法复杂度为代价的 ,因此 ,研 究实时实现的运动估计快速算法一直是这一领域的 重要课题。 许多学者对块匹配运动估计 (BMME , Block2 Matching Motion Estimation) 搜索算法进行了大量研 究。其中全搜索算法 (FS ,Full Search) 是 BMME 最直 接的实现方法 ,它通过对搜索窗内的所有点进行搜 索 ,可以达到最佳匹配 ,但是 FS 算法的计算量巨大 , 不利于实时实现 ,尤其是在视频电话、会议电视、无 线通信等实时视频通信应用中。因此 ,出现了大量 的快速运动估计算法 ,大部分主要是通过减少搜索 第 15 卷第 4 期 2008 年 4 月 　　　　　　　　　　　　　 电光与控制 Electronics Optics & Control 　　　　　　　　　　　　　　　　 Vol. 15 　No. 4 Apr. 2008 点来实现的。如传统的二维对数法[1 ] 、三步法[2 ] 、十 字法[3 ] 、四步法[4 ] 、菱形法[5 ] (DS ,Diamond Search)等 , 这些算法搜索模式简单 ,易于实现 ,但容易陷入局部 无穷小 ;近来一些新的方法具有更好的搜索性能 ,如 MVFAST[6 ] (Motion Vector Field Adaptive Search Tech2 nique ) , PMVFAST[7 ] ( Predictive MVFAST) , UMHe2 xagonS[8 ] ( Unsymmetrical2cross Multi2Hexagon2grid Search) 等 ,但是它们的搜索模板比较复杂 ,对于 H. 264树状分块特点 ,每一个 16 ×16 的宏块 (Mac2 roBlock ,MB)要遍历每一种模式来进行运动估计 ,那 么要进行 41 次 ,每帧 QCIF 图像有 99 个宏块 ,算法 复杂度将可想而知 ,所以它们并不完全适合 H. 264 编码标准的特点。 图 1 　宏块及子宏块分割 针对 H. 264 标准的树状分块特点 ,本文利用运 动矢量的时、空间相关性进行运动矢量预测 ,然后进 行非对称十字形搜索以得到较精确的起始点 ,避免 下一步的搜索陷入局部无穷小 ,最后采用简单易行 的菱形算法进行运动估计。 1 　运动矢量预测 在视频序列中 ,视频对象的运动具有连续的运 动特征 ,因此描述视频序列运动特征的模块的运动 矢量间也存在时间和空间上的相关性 ,所以每个块 的运动矢量都可以从邻近的先前的编码块的运动矢 量中进行预测得到 ,而当前运动矢量和预测运动矢 量的差值被编码和传输。 1. 1 　误差匹配函数 运动搜索的目的就是在搜索窗内寻找与当前块 最匹配的数据块 ,首先建立误差匹配函数。H. 264 标准采用 SAD(绝对误差和) 匹配函数为基础 ,同时 考虑运动矢量编码比特的影响 ,建立运动矢量编码 的运动搜索匹配准则[9 ] 。匹配误差函数如下 : 　　J ( MV ,λMOTION) = SAD ( s ,c ( MV) ) +λMOTION × R ( MV - PMV) (1) 其中 : SAD ( s , c ( MV) ) = ∑ B x , By x = 1 , y = 1 | s [ x , y ] - c[ x - MVx , y - MYy ] | ,λMOTION = 0. 85 ×2 ( Q- 12)Π3 , s 是当 前进行编码的原始数据 ,而 c 是已经编码重建的用 于进行运动补偿的参考帧图像 ; MV 为候选的运动 矢量 ,λMOTION为拉格朗日常数 , Q 为量化参数 ; PMV 为中值预测矢量 ; R ( MV - PMV) 代表了运动矢量 差分编码可能耗费的比特数。 1. 2 　矢量预测 根据 JVT - G016[10 ] 的提案 ,在本文的算法中选 择了其中 3 种不同的方法用来预测候选起始点 ,并 最终选择误差匹配最小的点作为下一步搜索的起始 点。3 种方法描述如下 : 1) 对应点运动矢量。对应点运动矢量是指相 邻帧对应位置的运动矢量。由于在视频序列中很大 一部分宏块是趋于运动矢量等于 (0 ,0) 的低速运动 矢量 ,因此就可以把对应点作为候选预测矢量 ,记作 ( Epred c x , Epred c y ) , E 为当前块。 2) 中值运动矢量。中值运动矢量是根据相邻 块的运动向量的平均值来预测当前块的运动向量。 相对当前块 E 来说 ,相邻块包括左边块 A 、上边块 B 、左上边块 D 或者右上边块 C ,如图 2 所示。 图 2 　当前块与邻近块的关系 当前块的候选预测矢量按式 (2) 、(3)计算 : 　　Epred median x = median ( Amv x , Bmv x , Cmv x ) (2) 　　Epred median y = median ( Amv y , Bmv y , Cmv y ) (3) 如果预测的运动矢量是在边界 ,则将这个预测 运动矢量定义为 :当 A 块在图片或块组 ( GOB , Group of Blocks)边界的外面时 ,就用对应点矢量代替 ;当 C 块在图片或 GOB 边界的外面时 ,则用 D 块的运动 矢量代替 ;当 B 块和 C 块都在外面时 ,就用第 3 块 的运动矢量代替。 3) 上层块运动矢量。编码每个分块的运动矢 量需要大量比特位 ,特别是在选择小尺寸的时候 ,相 邻块的运动矢量通常高度相关 ,本文选择模式 1 到 7 的分等级的搜索次序作为本算法的预测模式搜索 次序 ,上层块的运动矢量 (如模式 5、模式 6 是模式 7 的上层块 ,模式 4 是模式 5 或模式 6 的上层块等) 将 81 　　　　　　　　电光与控制 　　　　　　　　　　　　　　　　　　　　　第 15 卷 被用作下层的一个候选预测。此时当前块的候选运 动矢量记作 : ( Epred up x , Epred up y ) 。 因此对于模式 1 ,对应点矢量、中间预测矢量、 左相邻块运动矢量上相邻块运动矢量和右上相邻块 运动矢量都可以作为它的候选预测 ;对于其他模式 来说 ,中间预测、对应点矢量和其上层运动矢量可作 为它的候选预测。经过矢量预测 ,将搜索区域设置 在整个搜索窗口中最小匹配误差点的周围 ,可以有 效地改进运动搜索的性能。 2 　搜索策略 算法引用文献 [ 8 ]中的非对称十字形模式作为 本文搜索算法的开始 ,再选用大菱形 (LDSP) 和小菱 形 (SDSP)搜索算法。下面是搜索算法的详细步骤 : 1) 非对称十字形搜索。一般的视频序列经过 上一步的矢量预测后 ,可以得到比较精确的搜索起 始点 ,从而快速找到匹配点 ,像文献 [ 11 ]中的算法 , 但是对于一些像 mobile. cif ,coastguard. qcif 视频序列 中含有多个不同运动方向的运动对象 ,如果一个宏 块中包含两个运动对象 ,预测可能就会不准确。所 以这里引用非对称十字形作为本文搜索算法的开 始 ,如图 3 所示 ,它是建立在自然图像序列在水平方 向的运动要比垂直方向的运动更加普遍的条件下 的。通过非对称十字型搜索可以得到更精确的搜索 起始点。对于一些有重大垂直运动的特殊序列 ,可 以将垂直方向的搜索半径扩大 ,本文使用的搜索半 径是 16。 图 3 　非对称十字形搜索 以预测矢量为中心进行搜索 ,在这一步中找到 的最小匹配误差值位置将作为下一步的搜索中心。 2) 大菱形搜索。以上一步得到的最小误差匹 配位置作为搜索中心点 ,搜索其周围的 8 个点 ,如图 4a ,如果中心位置得到了最小误差匹配值 ,则转到第 4)步 ,否则转到第 3)步。 3) 大菱形再次搜索。大菱形中心移到上一步 得到的最小误差匹配位置 ,搜索新增的 3 个点或 5 个点 ,如图 5 所示 ,如果最小误差匹配点在中心位 置 ,则转到第 3)步 ,否则循环这一步。 4) 小菱形搜索。转换大菱形到小菱形 ,以上一 步得到的最小误差匹配位置为中心 ,搜索其周围的 4 个点 ,如图 4b ,得到的最小误差处就是最佳运动矢 量 ,搜索结束。 图 4 　大菱形搜索和小菱形搜索 图 5 　大菱形搜索再次搜索 3 　试验结果及其分析 3. 1 　试验结果 试验的测试环境为 :CPU 为 P1. 8 GHz ,内存 512 M ,操作系统 Microsoft Windows XP。本算法是在 H. 264参考模型 JM84 的 baseline 平台上实现的。为 验证本文算法的效果 ,对 3 个具有不同运动程度的 QCIF 视频序列的连续 100 帧图像进行了编码测试。 其中 salesman 序列背景简单 ,局部运动较大 ;foreman 序列属于中等运动 ;coastguard 序列运动较复杂。量 化参数选择 28 ,参考帧选择 1 和 5 (用 R 表示) ,下面 是试验时统一的设置 :编码时搜索范围为 16 ; IPPPP 格式 ;每秒帧率为 30 ;用了哈达码变换 ;熵编码方法 为 CABAC ;使用率失真优化模式判定 ;不使用码率 控制。 测试序列分别用 UMHexagonS 快速算法和本文 算法进行编码。测试结果如表 1、表 2 所示 ,其中表 1 是两种方法在运动估计速度和码率方面的比较 , 表 2 是两种方法在信噪比方面的比较。 91第 4 期 　　　　　　　　　　　　　　迟 　茜等 : 　基于矢量预测的快速运动估计搜索算法 表 1 　不同搜索算法下搜索时间和比特率的比较 (参考帧分别为 1 和 5) 测试序列 UMHexagonS 快速算法 平均运动 估计时间Π(ms·帧 - 1) 码率Π(kbit·s - 1) 本文算法平均运动估计时间Π(ms·帧 - 1) 码率Π(kbit·s - 1)运动估计时间提高率Π% Salesman Foreman coastguard R = 1 37. 85 56. 94 31. 77 57. 05 16. 06 R = 5 160. 94 57. 39 160. 78 57. 42 0. 09 R = 1 66. 61 113. 29 40. 62 113. 56 39. 02 R = 5 289. 04 108. 39 238. 92 108. 76 17. 34 R = 1 83. 17 248. 59 45. 40 249. 91 45. 41 R = 5 436. 27 245. 66 310. 62 244. 73 28. 80 表 2 　不同搜索算法下的信噪比比较(参考帧分别为 1和 5) 测试序列 UMHexagonS 快速算法 SNRY SNRU SNRV 本文算法 SNRY SNRU SNRV Salesman Foreman coastguard R = 1 35. 57 39. 60 40. 17 35. 57 39. 62 40. 19 R = 5 35. 50 39. 60 40. 13 35. 57 39. 60 40. 15 R = 1 35. 38 38. 97 40. 67 35. 35 38. 99 40. 63 R = 5 35. 68 39. 06 40. 74 35. 71 39. 05 40. 73 R = 1 33. 93 43. 05 44. 04 33. 93 43. 12 44. 05 R = 5 34. 01 43. 21 44. 05 34. 02 43. 28 44. 08 3. 2 　结果比较及分析 从试验结果中可以看出 ,相比于 UMHexagonS 算 法 ,本文算法具有以下特点 : 1) 搜索模型简单 ,算法复杂度低 ,运动估计速度 快。UMHexagonS算法是一种混合、分等级的运动搜索 方法 ,它较好地解决了局部最优问题 ,并大大提高了编 码速度 ,是目前快速算法的典型代表。但是由于它采 用了 4 种模式进行分级搜索 ,并且为了减少搜索点 ,还 采用了搜索中止等策略 ,这使得算法复杂度大大增加。 本文算法仅仅采用了两种简单的搜索模板进行运动估 计 ,从表 1 的实验结果看出 ,在码率增加不超过 1 %的 情况下 ,运动估计速度最高有 45. 41 %的提高 ,而且越 复杂的图像序列提高得越多。 2) 较好地保持原有的率失真特性。从表 2 的 实验结果可以看出 ,亮度 Y 分量信噪比 ( SNRY ) 下降 不超过 0. 03 dB ,色度 U 分量信噪比 ( SNRU ) 下降不 超过0. 01 dB ,色度 V 分量信噪比 ( SNRV ) 下降不超 过 0. 04 dB ,大部分信噪比是有所提高的 ,所以本文 算法较好地保持了原有的率失真特性。 4 　结束语 本文采用了一种基于矢量预测的快速运动估计 搜索算法 ,实验表明 ,与 UMHexagonS 快速算法相比 , 本文提出的算法在较好地保持了原有的率失真特性 的情况下 ,运动估计速度至少与其相当 (最快提高 45. 41 %) ,并且采用了相对简单的搜索模板 ,大大降 低了算法的复杂度。 针对 H. 264 标准的新特点 ,在运动估计领域还 存在以下问题值得研究 :由于宏块树状分割模式的 特点 ,如何将模式选择与搜索方法有效地结合起来 以提高编码性能需要进一步研究 ;另外 ,如何根据图 像特点 ,快速地选择参考帧也是进一步研究的重点。 参考文献 : [1 ] 　JAIN J ,JAIN A. Displacement measurement and its applica2 tion in inter2frame image coding[J ] . IEEE Trans. Commun , 1981 ,29 (12) :179921808. [2 ] 　KOGA T ,LINUMA K,HIRANO A ,et al. Motion compensated interframe coding for video conferencing [ C ]ΠΠProc. of Nat. Telecommunications Conf. New Orleans : [ s. n. ] ,1981 : G5. 3. 12G5. 3. 5. [3 ] 　GHANBARI M. The cross2search algorithm for motion estima2 tion[J ] . IEEE Trans. Circuit Syst. Video Technical ,1990 ,38 (7) :9502953. [4 ] 　PO L M ,MA W C. A novel four2step search algorithm for fast block motion estimation [J ] . IEEE Trans. Circuit Syst. Video Technol ,1996 ,6 (3) :3132317. [5 ] 　ZHU Shan ,MA Kai2kuang. A new diamond search algorithm for fast block matching motion estimation [J ] . IEEE Trans. Circuit Syst. Video Technol ,2000 ,9 (2) :2872290. [6 ] 　HOSUR P I ,MA K K. Motion vector field adaptive fast mo2 tion estimation [ C ]ΠΠCommunications and Signal Processing ( ICICS’99) ,Singapore ,Dec. 7210 ,1999. [7 ] 　TOURAPIS A M ,AU O C ,LIOU M L. Predictive motion vec2 tor field adaptive search technique ( PMVFAST) : enhancing block2based motion estimation[ C]ΠΠVCIP ,2001 :8832892. [ 8 ] 　CHEN Zhi2bo , ZHOU Peng , HE Yun. Fast integer pel and fractional pel motion estimation for JVT ,JVT2F017[ C]ΠΠJoint Video Team (JVT) of ISOΠIEC MPEG & ITU2T VCEG,6th Meeting : Awaji ,Island ,JP ,5213 December ,2002. [9 ] 　毕厚杰. 新一代视频压缩编码标准 —H. 264ΠAVC[ S] . 北 京 :北京人民邮电出版社 ,2005. [10 ] 　CHEN Zhi2bo ,ZHOU Peng ,HE Yun. Fast motion estimation for JVT ,JVT2G016. doc [ C ]ΠΠJoint Video Team (JVT) of ISOΠIEC MPEG & ITU2T VCEG, 7th Meeting : PattayaII , Tailand ,7214 March ,2003. [11 ] 　范志慰 ,何加铭 ,郁梅. 基于 H. 264 的帧间预测快速算 法[J ] . 中国图像图形学报 ,2005 ,10 (11) :136021363. 02 　　　　　　　　电光与控制 　　　　　　　　　　　　　　　　　　　　　第 15 卷