UMHexagonS算法优化(AP1234)[白世军]

1、基于H.264/AVC视频编码运动估计算法的优化学科：控制科学与工程答辩人：白世军导 师：王煜 教授博导 副导师：吴晓军副教授副导师：吴晓军副教授哈尔滨工业大学深圳研究生院哈尔滨工业大学深圳研究生院2008年年12月月13日日论文题目：论文题目：答辩提纲 课题背景及研究任务 H.264/AVC编码器原理 UMHS算法描述及可优化点分析 基于UMHS算法的优化 实验结果与性能分析 总结及展望课题背景及研究任务(编码发展简史) 1984年CCITT发布了H.120(数字基群电视会议编码标准)建议 1988年CCITT通过了“px64Kbps(p = 1,2,3,30)”视频编码标准H.261建议，

2、被成为视频压缩编码的一个里程碑 1986年，ISO和CCITT成立了联合图象专家组（JPEG, Joint Photographic Experts Group),1992年通过了JPEG标准 1998年ISO/IEC成立了活动图象专家组(MPEG,Moving Picture Experts Group). 1991年公布了MPEG-1标准，码率为1.5Mbps,主要应用于家用VCD的视频压缩 1994年公布了MPEG-2标准,用于DVB、DVD、HDTV码率从4Mbps 、15Mbps.直到100Mbps分别用于不同档次和不同级别的视频压缩中课题背景及研究任务 1995年，ITU-T推出H

3、.263标准，用于低于64Kbps的低码率视频传输 1998年和2000年又分别公布了H.263+和H.263+等标准 1999年，ISO/IEC通过了MPEG4,它除了定义视频压缩标准为，还强调了多媒体通信的交互性和灵活性 2003年3月， ITU-T和ISO/IEC公布了H.264视频压缩标准，不仅显著提高了压缩比，而且具有良好的网络亲和性，加强了对IP网、移动网的误码和丢包的处理有人将H.264成为新一代的视频编码标准课题背景及研究任务(H.264标准的性能优势和计算复杂度)H.264的视频编码层采用了多种新技术，在相同的图像质量下，H.264所需码率约为MPEG-2的36%、H.263

4、的51%、MPEG-4的61%，极大的提高了压缩率，保证了图象质量。研究表明：H.264编码器由于采用了高精度运动矢量(Motion vector)，计算量迅速增长，运动估计消耗整个编码80左右时间，严重降低了编码的实时性。 因此，研究基于H.264的运动估计(Motion Estimation )快速算法，是H.264标准走向实时应用的关键，也是本文研究的重点。H.264/AVC编码器原理(图像的冗余) 视频序列图像在时间上存在很强的相关性，采用运动估计和运动补偿技术可以消除时间冗余以提高编码效率，这种技术广泛用于视频压缩的一些国际标准中，如H.261/263/264、MPEG-1/2/4。

5、H.264/AVC编码器原理H.264编码器前向编码通道反向解码通道(重构帧)本文研究对象本文研究对象H.264/AVC编码器原理（运动估计的定义） 基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。H.264/AVC编码器原理(运动估计的基本思想 )运动估计（Motion Estimation, ME):其表达方式是运动矢（Motion Vector, MV

6、），研究的主要内容就是如何快速、有效的获得有足够精度的运动矢量(MV)H.264/AVC编码器原理H.264中定义的块匹配误差函数：(,)( , ()()J MVSAD s c MVMOTIONMOTIONR MVPMV其中SAD(绝对差值和)定义如下：,1,1( , () , ,16,84xyBBxyxyxySAD s c MVs x yc xMVyMVB Bors: 当前要进行编码的原始数据c: 是已编码重建的用于进行运动补偿的参考帧数据MV: 为侯选的运动矢量PMV:为中值预测矢量R(MV-PMV):代表运动矢量差分编码可能耗费的比特数H.264/AVC编码器原理(UMHSUMHS算法算

7、法)UMHSUMHS算法算法(本文研究的快速运动估计算法) UMHS算法全名叫“非对称十字型多层次六边形格点搜索算法”(Unsymmetrieal-CrossMuti-HexagonSeareh，UMHS)算法特点：可以在很大程度上提高预测的有效性和鲁棒性 ，相对于H.264中原有的快速全搜索算法可节约90% 搜索时间 UMHS算法描述及可优化点分析具体搜索方法的步骤：Step1:起始搜索点搜索（中值预测）Step2:不对称的十字交叉搜索Step3:非均匀多层次六边形格点搜索Step3-1:小矩形窗口全搜索Step3-2:扩展的多层次六边形16格点Step4:扩展的六边形搜索Step4-1:六

8、边形模式搜索Step4-2:基于小六边形(菱形)模式搜索UMHS算法描述及可优化点分析 (1)算法起始搜索点位置如何确立？(2)参考搜索窗口多大？(3)能否锁定搜索象限？(4)小六边形(菱形)搜索点数目是否可以减少？UMHS算法深入分析：UMHS算法描述及可优化点分析(AP1)(1)算法起始搜索点位置如何确立？中值预测中值预测的不足：由于不同的视频序列运动特征不一样，对不同的序列都把中值预测作为起始搜索窗口的起始点，而不是根据不同的序列所特有的运动特性动态的确定搜索窗口位置，不利于快速匹配和提高匹配精度时间和空间预测 (t-1)tUMHS算法描述及可优化点分析(AP1)参考帧中对应位置的块当前

9、块确定搜索中心点位置原则：根据col_mv和med_mv大小和是其夹角大小来确定Collocated blockCurrent block优化方法(AP1)：用动态搜索中心代替固定搜索中心(中值预测)UMHS算法描述及可优化点分析(AP1) (0,0)(2,2)(1)_0&_0 xycolmvcolmv(2)垂直运动（Vertical movement）(3)水平运动(4)相同的方向和速度运动(5)相同的方向不同的速度运动(6)其他情况(中值预测)XYUMHS算法描述及可优化点分析(AP2)(2)参考搜索窗口多大？UMHS 算法中采用了固定大小的参考搜索窗口，其大小为（2*search_ran

10、ge + 1）*（2*search_range + 1） 通过配置文件由search_range来设置，search_range = 16/32/48/64。 UMHS算法描述及可优化点分析(AP2)固定大小参考搜索窗口的不足：7种不同大小的块都在固定大小的参考窗口中搜索最佳匹配块是不科学的，根据“中心偏移特性”和“非中心偏移特性”理论，7种块大小不同而且运动矢量大小也不一样，比如对4*4小块势必会增加一些无用点的搜索；而对16*16的大块可能由于运动比较剧烈而在固定大小的窗口中无法找到最佳匹配的块.中心偏移特性news序列80以上的运动矢量分布在中心位置，且偏移比较小，大部分矢量分布在4，4

11、的范围内 .非中心偏移特性News_qcifUMHS算法描述及可优化点分析(AP2):_Bprpsd DSRfixed part dinamic part优化方法(AP2)：用动态搜索窗口代替固定大小窗口AP2动态搜索窗口(DSR)的计算 ()xxmvxdabs MVPuplayerMVPmedian()yymvydabs MVPuplayerMVPmedian:_max(,)Ddinamicpartmvxd mvyd:_(_)/8Cfixed partinput search range原算法固定大小搜索窗口动态搜索窗口大小定值搜索窗口大小BCD（2*search_range + 1）UMH

12、S算法描述及可优化点分析(AP3)(3)能否缩定搜索象限？分析:非均匀多层次六边形格搜索点数(a)：N1 = 16*4 = 64 扩展的六边形搜索，搜索点数(b)：N2 = 7 + 3*n + 4 (a)(b)UMHS算法描述及可优化点分析(AP3)优化(AP3)：利用运动矢量(med_mv)和运动矢量(col_mv)的夹角a大小了优化. a = 0 to 90a = 90 to 180a = 180 to 270 a = 270 to 360N1 = 16*4 = 64N2 = 7+3*n+4搜索点数变化N1 = 4*5 = 20 N2=7+2*n+4UMHS算法描述及可优化点分析(AP4)

13、(4)小六边形(菱形)搜索点数目是否可以减少？(a)(b)原算法不足：匹配精度有待提高，可以进一步优化UMHS算法描述及可优化点分析(AP4)(a)优化(AP4)：利用全局最小周围的单调失真特性，使得内部点搜索(inner search)只需要搜索一个特定方向的内部点(inner points)。MinSadGroup1, Group2,Group3, Group4, Group5, Group6, 其中Group2和Group5需要搜索三个点，如图a所示，Group1，Group3, Group5, Group6需要搜索两个点，如图b所示.UMHS算法描述及可优化点分析(AP4)优化效果：G

14、roup分组分别减少1或者2个搜寻点，所以大约减少了2*(4/6) + 1*(2/6) = 1.67个点，因为是每个搜索块都减少了大约1.67个点，所以一个frame就减少了相当多的搜寻点，自然其速度比六边形搜索算法快很多。而整个搜索算法的搜索总点数为 7 + 3*n + (2, 3) (b)UMHS算法描述及可优化点分析(软件实现流程)总结：对HUMS算法进行了AP1,AP2,AP3,AP4四个方面的优化，优化后的算法与原算法(HUMS)在总体流程上没有发生变化，只是在不同的搜索步骤中进行了优化，使得整个算法更加高效，自适应性更好，匹配速度和精度极大的提高，实时性更好 实验结果与性能分析(视

15、频质量的主观评定视频质量的主观评定)A:A:为原始图象为原始图象B:B:为编码解码为编码解码后的图象后的图象CCIR CCIR 五级评分等级五级评分等级评分等级评分等级高清晰度采用七级评分等级高清晰度采用七级评分等级评价评价7 7不能觉察任何图像损伤不能觉察任何图像损伤特别好特别好6 6刚能觉察有图像损伤刚能觉察有图像损伤相当好相当好优优5 5不同程度的觉察，轻度损伤不同程度的觉察，轻度损伤很好很好好好4 4有损伤，但不令人讨厌有损伤，但不令人讨厌好好稍差稍差3 3有令人讨厌损伤有令人讨厌损伤稍差稍差很差很差2 2损伤令人讨厌，但尚可忍受损伤令人讨厌，但尚可忍受很差很差劣劣1 1非常令人讨厌损

16、伤，无法观看非常令人讨厌损伤，无法观看劣劣主观评价分数标准主观评价分数标准 DSCQSDSCQS测试系统测试系统 源视频源视频序列序列视频视频编码器编码器视频视频解码器解码器显示显示BA实验结果与性能分析(视频质量的客观评定视频质量的客观评定)最常用的测试标准是峰值信号与噪声之比（PSNR）均方误差（MSE）:(i, j)为运动矢量(MV);(22 - 1)2为图像种最大可能的信号值平方;n为表示每个像素的比特数21010log (21) /nPSNRMSE一般讲，PSNR 愈高视频质量愈高；反之亦然21111( , )( , )(,)MNttxyMSE i jf x yfxi yjMN实验结

17、果与性能分析(测试平台及其配置)Intel(R) Pentium(R) D CPU 3.00GHz，512M内存。WindowsXP 2002+SP2。测试序列集为5个 QCIF(176*144)格式序列所有序列yuv4:2:0实验结果与性能分析（客观分析 ）(a)不同纹理复杂程度(b)不同运动剧烈程度选用原则实验结果与性能分析（客观分析 ）Mobile_qcif序列总结及展望（主观评价 ）(a)原始帧 右图(a)给出了news_qcif序列原始帧 ，(b)和(c)分别是UMHS算法和本文优化算法得到的解码帧。 总结及展望（主观评价 ）(b) UMHS解码帧 (c) 本文优化后解码帧 总结及展

18、望（结论）实验结果表明：与原UMHS搜索算法相比，优化后算法的优势还是很明显的 ，从客观视频质量评估标准来看，节省了运动估计(ME)时间(平均18.102%)，在保证视频性能相对高的前提下，大大降低了运算复杂度，提高了编码速度。从主观评价标准来看，算法在提高了编码速度的同时，可以较好地保持原有的率失真特性。综合评价指标:(1)图象质量高(PSNR大)(2)编码(运动估计)时间短(实时性好)(3)码率低(压缩比大，方便存储和传输)总结及展望（下一步计划）(1)研究帧内模式选择、码率控制、熵编码等方面的优化方法 (2)以H.264扩展档次和主要档次为研究重点，分析编码器中涉及到的主要技术，如加权预

19、测、SP帧与SI帧的编解码过程等等。(3)基于DSP的编解码软件实现. 在熟悉一款DSP(Ti C6000系列)芯片硬件架构和开发环境(CCS3.3)的基础上，完成H.264编解码器代码的移植和优化，即研究如何在DSP上实现H.264的实时编解码技术 总结及展望（下一步计划）攻读学位期间发表的学术论文 白世军，吴晓军. H.264/AVC频编码运动估计算法的优化. 电子学报.2008(09) (外审).感谢各位专家！感谢各位专家！补充材料(实例)(1)确定搜索起始点(MVEx,MVEy)(2search_range+1)(2search_range+1)，其中s=16/32/64最佳匹配块当前块当前块补充材料(UMHS算法搜索步骤