《几种快速运动搜索算法在H_264中的实现及分析_王正宁.docx》由会员分享，可在线阅读，更多相关《几种快速运动搜索算法在H_264中的实现及分析_王正宁.docx（4页珍藏版）》请在三一文库上搜索。
1、第 24 卷第 9 期计算机应用Vol. 24 No. 92004 年 9 月Computer ApplicationsSept. 2004文章编号: 1001- 9081( 2004) 09- 0091- 03几种快速运动搜索算法在H . 264 中的实现及分析王正宁, 彭强, 诸昌钤( 西南交通大学计算机与通信工程学院, 四川成都 610031)( znw ang3 tom. com )摘 要: 运动搜索是基于块的运动补偿的视频编码的核心技术。介绍了视频编码中几种快速运动搜索算法, 并结合 H. 264 的多参考帧预测、多种宏块类型划分和片结构的特点, 对各算法进行了仿真实验并给出了各算法
2、在H . 264 编码标准中的测试结果。关键词: 视频; H . 264; 运动搜索中图分类号: TP37文献标识码: AImplementation and analysis of fast search algorithmsfor block motion estimation in H. 264 test modelWANG Zheng- ning, PENG Qiang, ZHU Chang- qian(School of Comp uter & Communication Engineer ing, Southwest Jiaotong Univer sity , Chengdu S
3、 ichuan 610031 , China)Abstract: Motion estimation is a key technique in motion compensated video coding standards. We introduced some fast search algorithms. Combined with the features of multiple reference frames, multiple block types and slice structure in H. 264, we gave a simulation of each alg
4、orithm in H. 264 test model. Simulation ex periments show the performance of each algorithm.Key words: video coding; H. 264; mot ion estimation ( M E)H. 264 1 是 IT U- T 和 M PEG 联合制定的最新的视频编码标准, 主要面向因特网和无线环境的视频传输。在运动搜索方面, H. 264 标准引入了多参考帧的概念, 并且对宏块的划分达到了七种类型。在这两个方面与 H. 263 标准相比编码复杂程度要高出 4 5 倍, 但同时得到了最
5、大的压缩比。由于视频传输对实时性要求很高, 而运动搜索是编码中最耗时间的一个环节, 因此快速准确的运动搜索算法是保证传输实时性的主要手段。现在人们已经提出不少优秀的快速运动搜索算法, 如二维对数法 2 、钻石搜索算法 3 、运动向量快速自适应搜索技术 4 和可预测的运动向量场自适应搜索技术 4 等。二维对数法( T w o Dimension L ogarithm, T DL ) 的基本思想是通过快速搜索来跟踪最小 SAD 点。从运动向量( 0, 0) 开始 , 以十字形分部的五个点构成每次搜索的点群, 求出 SA D 最小点。若 SAD 最小点出现在十字形点群的边缘点, 则下次搜索以该点为新
6、的搜索中心点建立搜索点群, 而搜索步长不变; 若 SA D 最小的点出现在搜索点群的中心, 则以该点建立新的十字搜索点群, 但搜索步长减半。若新的搜索中心位于搜索区域的边缘, 则搜索步长也减半。当搜索步长为 1 时, 进行最后一次搜索并终止。1. 2 钻石搜索算法图 2 钻石搜索模板钻石搜索( Diamond Search, DS) 算法用到两个搜索模板, 如图 2 所示。大钻石搜索模板包含 9 个候选搜索点; 小钻石模板包含 5 个候选搜索点。开始阶段重复使用大钻石搜索模板, 直图 1二维对数法搜索过程到最佳匹配块落在大钻石模板的中心, 然后以该点为中心建立1常用的几种快速搜索算法小钻石搜索
7、模板, 并进一步确定最佳匹配块的位置。与二维对数法不同的是, 该搜索模板中除了对水平和竖直方向进行搜索1. 1二维对数法外, 还对左上、右上、左下、右下四个方向进行搜索。收稿日期: 2004- 03- 18; 修订日期: 2004- 05- 20作者简介: 王正宁( 1977- ) , 男, 湖北武汉人, 硕士研究生, 主要研究方向: 视频压缩与传输; 彭强( 1962 - ) , 男, 四川成都人, 副教授, 主要研究方向: 图像压缩编码、多媒体压缩与传输、智能交通; 诸昌钤( 1938- ) , 男, 浙江杭州人, 教授, 博士生导师, 主要研究方向: 交通信息工程及控制、虚拟现实、多媒体
8、.92计算机应用2004 年1. 3 运动向量场自适应搜索技术运动向量场自适应搜索技术 ( M otion Vecto r F ield A daptiv e Sear ch T echnique, M V FAST ) 是被 M P EG4 采用的快速搜索算法。它通过利用支持区域( Region Of Support, ROS, 由当前块的左、上、右上相邻块组成) 中的相邻宏块的运动信息来预测当前宏块的运动剧烈程度( 运动向量各方向距离的和与规定阈值的比较结果) , 并确定搜索中心, 最后通过大小钻石搜索模板搜索最佳匹配块。采用哪种搜索模板是依据当前宏块的运动剧烈程度, 如果当前宏块的运动剧
9、烈程度为高或低, 则认为它与 ROS 中的宏块相对运动剧烈程度不大, 采用小钻石搜索模板; 如果运动剧烈程度为中等, 则采用大钻石搜索模板。搜索中心由当前块的运动剧烈程度来决定, 当运动剧烈程度为低或中时, 搜索中心为原点; 否则, 选取 ROS 中 SAD 值最小的块的运动向量作为搜索中心。当搜索中心和搜索模板确定之后, 就采用钻石搜索的方法进行搜索找到最佳匹配块。与钻石搜索不同的是, M VFAST 除了利用 ROS 中的信息进行预测外, 还根据经验得出了一个预先判零的阈值 T = 512, 如果在( 0, 0) 搜索点处的SAD 值小于 T , 则认为运动向量为( 0, 0) , 并停止
10、搜索。并且当 T = 0 时这一阈值条件就被关闭了。1. 4 可预测的运动向量场自适应搜索技术图 3参考块示意图可预测的运动向量场自适应搜索技术( Predictive M otio n Vector F ield Adaptive Search T echnique, PM V FAST ) 本着/ 见好就收0 的原则, 综合使用了阈值停止准则、A PDZS 搜索算法的时间空间预测和 M VF AST 的大小钻石搜索模板。算法分为三步:1) 使用相邻块( 左, 上, 右上) 的运动向量并根据中值算法求出当前块的预测运动向量 PM V , 并且每次取各个相邻块的最小 SA D 值自适应地设定为
11、当前搜索的阈值 T 1 , 然后由 PM V 算出当前块的 SAD 值, 再根据停止搜索的准则判断是否停止搜索。预测所用的参考块( refBlock) 是指前一帧中与当前块位置相同的块( 图 3) 。如果 PM V = M V r ef , SA D = SA D ref 或SA D T 1, 则停止搜索。2) 以当前块的可能运动向量( 左, 上, 右上块的运动向量, 参考块的运动向量和( 0, 0) 向量) 作为预测向量计算 SAD值, 从中找出/ 最好的0 运动向量 M V best , 并算出相应的 M inSA D 。如果 M V best = M V r ef 且 M inSA D
12、SA Dr ef , 或 M inSA D T 1, 则停止搜索。3) 对取得最小SAD 值的运动向量根据 M VFA ST 中的搜索模板完成局部搜索。当得到的中值运动向量位于搜索窗口的中心时会用到另一个阈值 T 2 ( 算法中定义: T 2 = T 1 + 256) , 同时 T 2 可以被看成当前块的 SAD 值的另一个预测值。如果 T 2 足够小( 小于某一个值 K ) , 则当前块的 SAD 值也可能非常小。在这种情况下, 运动向量有可能在围绕搜索中心的某个小区域内找到, 因此采用小钻石搜索模板将会非常有效; 否则, 就采用大钻石搜索模板。图 4 PM VFAST 算法的搜索过程2 各
13、算法在 H. 264 中的实现由于 H. 264 与以前的视频编码相比有了多参考帧预测和多达 7 种类型的宏块划分和增强抗错性能的片结构。针对这些特性, 要在H. 264 中实现上述各算法必须作相应的调整。由于 M VFAST 算法中定义的支持区域中的块全部是宏块, 为了支持H. 264 的多种块类型, 须将支持区域定义为相邻块组成的区域。对于 M VFAST 和 PMVFAST , 每种块类型预先判零阈值 T , T 1 和 T 2 都要根据当前块尺寸与宏块的比例作相应的调整。另外, 由于片结构规定不同片序号内的块不能作为参考块, 因此各算法在对每个块进行运动搜索时都必须判断当前块所在的宏块
14、与参考块所在的宏块的片序号是否一致。为了不失一般性, 本文中测试的所有算法均采用绝对误差和作为块的匹配准则:MNSA D( i, j ) = E E| f k( m, n) - f k- 1( m + i , n + j ) |( 1)m= 1 n= 1其中, ( i , j ) 为位移矢量。若在某一个( i , j ) =( dx ,dy) 处 SA D ( i , j ) 达到最小, 则该点就是要找的最优匹配点。f k 和 f k- 1 分别为当前帧和参考帧中对应象素亮度值。3 实验结果表 1各算法性能统计视频序列 搜索算法 平均搜索点亮度 PSNR比特率/ dB/ kbps全搜索 ISS
15、99035. 75135. 36ForemanDS14. 935. 70138. 15TDL17. 235. 63138. 38( QC IF)M VFAS T11. 435. 25141. 29PM VFAST8. 535. 39143. 73全搜索 ISS99037. 3085. 82SuzieDS12. 637. 2886. 78TDL13. 537. 2590. 88( QC IF)M VFAS T9. 337. 0393. 29PM VFAST7. 437. 1698. 88在 H. 264 测试模型 JM- 7. 0 5 的基础上实现了上述各快速运动搜索算法, 并以 for ema
16、n 和 suzie 两个视频序列对各算法对进行了仿真实验。测试模型的参数设置为: 无跳帧, 无 B帧 , 无率失真优化, 多参考帧数目为 2, 启用所有块类型, 其他参数不变。实验统计了各种算法在整象素搜索过程中每个块的平均搜索点数、重建帧的亮度平均 PSN R 及视频流比特率。第 9 期王正宁等: 几种快速运动搜索算法在 H. 264 中的实现及分析93表 1 显示了统计结果, ISS 指的是 JM- 7. 0 中的整象素螺旋搜索( Integer Spiral Sear ch) 算法, 它是全搜索算法。从表 1 可以看出, 各快速搜索算法的平均搜索点数比全搜索都极大地降低了, 并且重建帧的
17、亮度 PSNR 值减小得并不多, foreman 和 suzie 序列的亮度 PSNR 值最大最小值分别为0. 5dB 和0. 27 dB。图 5 显示了重建帧中的运动向量场的平滑性。由于最后两种搜索算法充分利用了周围相邻块的运动特性, 故能够非常好地体现出块与块之间的运动一致性。图 5 为全搜索与 PM VFA T 在 8 8 的块类型下的运动向量场。从中可以看出利用相邻块的运动信息进行预测得到的运动向量场比全搜索得到的运动向量场要平滑许多, 这一点不仅有助于下一帧的快速预测, 而且从视觉观察也可以发现这个运动向量场更真实地反映了物体的实际运动, 并能一定程度上减轻图像的斑块效应。图 6 为
18、各算法对 suzie 序列编码的时间统计( 具体时间取决于计算机性能, 但各算法的时间比例是不变的) , 从中可以看出在编码速度方面 PM V FAST 算法最快。图 54 结论大大提高, 这点有助于实现视频的实时传输。通过相邻块的运动向量来预测当前块的运动向量并进行搜索, 得到的运动向量场比全搜索的更加平滑, 更真实地反映了物体的实际运动。各搜索算法对 suzie 序列的编码时间统计表现了各自的搜索速度。图 6各算法对 Suzie 序列的编码时间比较参考文献: 1 ITU-T/ SG16/ Q . 6. Doc JVT-G050, Non-Final Draft of FinalDraft
19、International Standard ( FDIS ) ofJoint VideoSpecification( ITU-T Rec H. 264 ISO/ IEC 14496- 10AVC) S ,2003. 2Wang Y, Ostermann J , Zhang Y-Q . Video Processing and Com-munication M . 北京: 清华大学出版社, 2002. 3Zhu S, M a K-K . A New Diamond Search Algorithm for FastBlock-M atching M otion Estimation J .IE
20、EE Transactions onImage Processing, 2000, 9( 5) : 287- 290.本文结合 H. 264 的特点, 用 JM- 7. 0 实验仿真了各快速 4ISO / IECJTC 1/ S C29 / WG1 1N3 67 5, Optimizaton M odel, Version运动搜索算法并统计了各算法的执行结果。实验结果表明各2. 0 S , 2000.快速搜索算法除了传输比特率比全搜索算法略有增加外, 不 5JVT T estmodel( JM 7 . 0 ) EB / OL . http : / / bs . hhi . de/ sueh仅恢
21、复图像的质量与全搜索算法的非常接近, 而且搜索速度ring, 2004.( 上接第 81 页)从图 4 可以看到: 单纯使用路由优化方案比使用基本 M IP 方案时 T CP 性能还要差, 这是由于路由优化方案仅能够恢复部分丢失分组, M H 接收到的分组有空洞而造成的结果 6 。当部分分组丢失后, 以后到达的报文不但会触发 T CP 的快速重传机制从而导致 T CP 性能下降, 而且还有可能触发错误的快速重传从而引起 T CP 吞吐量的抖动, 这种抖动对于实时数据的传输是不能忍受的。而本文所提方案引进了分组缓存机制, 使 M H 跨域切换时的分组丢失量为零, 从而使 T CP 性能有了较大的
22、提高。3 小结无线技术的快速发展促进了对 M H 小范围切换技术的研究, 近年来提出了许多 micro- M IP 协议 , 但对 MH 的跨子网切换问题以及由 MH 跨子网切换引起的 micr o- M IP 与 M IP 协议融合的问题研究较少, 这成为制约 Al-l IP 网络体系结构形成和 A l-l I P 网络性能的重要因素。针对该问题, 本文提出了一种新的 micro- M IP 与 M IP 相互融合的方案, 新方案在M IP 中引入了分组缓存与路由优化相结合的方法使 MH 跨子网切换时的性能得到了提高, 同时能够使带有路由优化的 M IP 协议与各 micro-M IP 协议
23、很好地融合。本文所提方案对IET F 所提的 M IP 协议未作任何修改, 而且也不像将端到端的连接分成两段的方案那样破坏原有的 T CP 语义, 实现相对简单, 为提高 All- IP 移动通信网的性能和 MH 的 Q oS 保证提供了新思路。为进一步提高 A l-l I P 移动通信网的性能, 在后续研究中还应进一步考虑 MH 切换时分组乱序到达和重复分组对 T CP 性能的影响, 而且在对 M I P 技术改进的同时还要进一步改进 T CP 协议本身的拥塞控制机制, 使之能同时为移动网络和固定网络提供更好的支持。参考文献 1Perk ins C, Johnson D. Route Opt
24、imization in M obile IP EB/ OL . http: / / w ww . ietf . org/ ids. by. w g/ mobileip_draft , 2001 - 09. 2 苏晓萍. 微移动 IP 协议的工作原理 J . 计算机工程与应用, 2004, 40( 1) : 176- 178. 3 余旭涛, 徐平平, 毕光国, 等. 微观移动 IP 协议综述 J . 移动通信, 2002, ( 4) : 27- 30. 4Perkins C , Wang KY . Optimized Smooth Handoffs in M obile IP A . Proceeding of T he Fourth IEEE Sym posium on Computers and Communications C , 1999. 5 nS- 2 EB/ OL . http: / / w w w . isi . edu/ nsnam/ ns/ nsbuild. html, 2003- 11. 6 苏晓萍. 提高移动计算环境下平滑切换机制的数据传输性能 J . 计算机应用与软件, 2003, 20( 10) : 67- 69.