一种基于JMVC参考模型的运动估计优化算法

一种基于JMVC参考模型的运动估计优化算法*

袁梅冷1，2，杨张2，雷海军2

(1.深圳职业技术学院计算机工程学院，广东 深圳 518055；2.深圳大学计算机与软件学院，广东 深圳 518060)

摘要：运动估计(ME)是视频压缩编码中的关键技术，运动估计算法对视频质量、编码复杂度和码率都有直接影响。TZSearch 算法是JMVC 参考实现中一种基于混合模板的快速搜索算法。通过提高搜索起点准确度，采用基于视频运动特性的搜索策略，采取阈值设置和大小步长相结合等方法对算法进行优化。在多视点视频编码测试平台JMVC 8.5中对多视点视频序列BallRoom、Exit进行测试。实验结果表明，与JVMC的TZSearch算法相比，在保证视频重构质量和码率增加很少的情况下，本算法编码时间减少50%以上。

关键词：运动估计；编码复杂度；块匹配； TZSearch；阈值；JMVC

中图分类号：TP393.4 文献标志码：A

doi:10.3969/j.issn.1007-130X.2015.06.026

收稿日期：*2014-03-23;修回日期：2014-09-16

基金项目：国家自然科学基金-广东联合项目(U1301252)；深圳市战略性新兴产业发展专项资金资助项目(JCYJ20120613113419607)；校重点项目(2213k3190007)

作者简介:

通信地址：518055 广东省深圳市深圳职业技术学院计算机工程学院

Address:School of Computer Engineering,Shenzhen Polytechnic,Shenzhen 518055,Guangdong,P.R.China

AmotionestimationoptimizationalgorithmbasedonJMVCreferencemodel

YUANMei-leng1，2,YANGZhang2,LEI Hai-jun2

(1.SchoolofComputerEngineering,ShenzhenPolytechnic,Shenzhen518055;

2.CollegeofComputerandSoftwareEngineering,ShenzhenUniversity,Shenzhen518060,China)

Abstract:Motion estimation is a key technique of video compression, which has an important impact on video quality,coding complexity and code rate.The TZSearch algorithm is a fast search algorithm based on hybrid template in the reference implementation of JMVC.We propose an optimization algorithm to improve the accuracy of the start search point by adopting the search strategies based on video motion characteristics and by setting the threshold according to the step size.Experiments through multi-view video test sequences of Ball-Room and Exit show that the proposed algorithm can reduce at least 50% encoding time compared with the original TZSearch algorithm while maintaining the reconstruction quality of the video with little increase of the code rate.

Keywords:motionestimation；codingcomplexity；blockmatching；TZSearch；thresholdvalue；JMVC

1引言

运动估计方法较多，比较经典的有块匹配法、相位相关法和像素递归法[1,2]。其中块匹配法最为简单有效，已被广泛应用于各种视频编码标准，比如H.263、MPEG-4和H.264等。全搜索法采用了块匹配法，它的思想是在搜索窗内通过蛮力搜索寻找最佳的匹配块。全搜索法虽能找到最优匹配块，但却要付出高计算复杂度、高时延作为代价[3]，这恰是实时视频应用的致命缺陷。因此，设计出一个良好的快速块匹配算法来减少运动估计的计算时间是不可或缺的。如何降低运动估计计算复杂度、减少延时也是当今学者关注的热点之一。经过20多年的发展，很多块匹配运动估计算法被提出，这些算法的发展大致可分为四个阶段：全搜索阶段、规定最大搜索步数的搜索阶段、不限搜索步数的快速搜索阶段和混合模板搜索阶段。规定最大搜索步数的搜索阶段较经典的有三步搜索法(TSS)、新三步搜索法(NTSS)、四步搜索法(4SS)等；不限搜索步数的快速搜索阶段有基于块的梯度下降搜索法(BBGDS)、六边形搜索法(HEXBS)以及钻石搜索法(DS)等；混合模板搜索阶段比较著名的有MVFAST、PMVFAST、UMHexagonS、EPZS等新的快速算法[2～4]。本文对JMVC运动估计算法开展分析和研究，并在此基础上提出了优化算法。

2TZSearch算法分析与优化

2.1TZSearch算法分析

TZSearch算法是一种基于块匹配的混合模板快速搜索算法，是JMVC参考实现中默认的快速搜索算法，其搜索模型包括八点方形搜索、八点钻石形搜索、星形搜索、光栅搜索和两点搜索等[5]。TZSearch算法在实际多视点视频编码应用中存在不足之处，主要表现在：

(1) 在搜索起点预测矢量集合中，考虑的相关矢量过少，未对当前编码宏块的中值预测矢量和零向量的相邻位置矢量进行完全评估，实际上这些相邻块的运动矢量很可能是和当前编码宏块运动矢量一致的。

(2)在搜索过程中未引入阈值设置提前终止搜索。和单视点一样，多视点视频编码的运动矢量/视差矢量也存在中心偏置特性，即在当前搜索点的周围小区域内搜索到最优点的概率最大，很多情况在前面三轮搜索内就能找到最优匹配点。而在粗略搜索步骤中的八点钻石模型搜索中，匹配搜索固定为七轮，在找到最优点后仍然继续后面几轮的搜索，没有及时中断搜索过程，这样会增加编码复杂度和浪费资源，影响编码的实时性。

(3)在搜索策略上，TZSearch算法默认采用统一的搜索模型，都是先八点钻石搜索，然后光栅搜索/两点搜索，最后循环八点钻石搜索。没有根据视频内容和运动特性选择不同的搜索模型，未对视频序列运动剧烈程度进行预判，存在较多不必要的搜索，导致编码时间长，编码效率不高。

(4)在搜索模型的选取上，精细搜索和细化搜索步骤中采用的稠密光栅搜索和八点钻石搜索，时间消耗相当大，不适于视频编码的实时应用。

2.2TZSearch算法的优化

TZSearch算法中统一的搜索策略与搜索模型的应用导致编码时间过长，编码效率不高，阻碍了视频编码的实时应用。本文通过扩充优化搜索起点预测集合、采用基于视频运动特性的搜索策略和搜索模型、引入搜索提前终止阈值设置等方法对算法进行优化，算法流程如图1所示。算法优化策略如下：

(1)扩充搜索起点预测集合，提高搜索起点准确度。

如果在搜索起始就采用准确的起始点预测，便能更准确更迅速地匹配到最优运动矢量，从而大幅度减少计算时间，提高编码性能。因此，在预测矢量集合中除了包含中值预测矢量、(0,0) 位置矢量、参考帧对应宏块的左上和右上位置宏块的矢量外，新增中值预测矢量空间邻近宏块的运动矢量和零向量周围邻近块的运动矢量。即预测矢量集合S由S1与S2的并集组成。S1如式(1)所示：

(1)

其中，MVpred_MP为中值预测矢量，MVLeft为左方预测矢量，MVUp为上方预测矢量，MVRU为右上方预测矢量。将中值矢量和零矢量的左方、右方、上方和下方四点也加入到S1中的函数计算,如(2)所示：

(2)

预测矢量集合S2由中值预测矢量MVpred_MP和零向量(0,0)的函数计算式的并集组成，如式(3)所示：

(3)

(4)

最佳搜索起点矢量MVmin根据式(5)计算得出：

(5)

(2)采用基于视频运动特性的搜索模型和搜索策略。

最优匹配点的分布情况和视频序列的运动特性息息相关，运动平缓的视频，最优点出现在搜索中心点邻近的小区域内；而运动剧烈的视频，最优点出现在距离搜索中心较远的区域。搜索策略应根据视频运动状况做及时调整。如最佳搜索起点在(0,0) 位置矢量，即iStartX=0和iStartY=0，则判断为静止宏块，直接结束搜索;否则,继续下一步粗略搜索。

Figure 1　Flowchart of the optimizaed algorithm 图1　优化的算法流程图

在相关文献中已经证实与钻石模型相比，六边形搜索模型具有更优良的性能，复杂度也低，在细化搜索过程中可以考虑使用六边形代替钻石模型进行搜索。稠密的光栅搜索是TZSearch 算法中最为耗时的环节，它要在搜索区域内进行等步长的水平和垂直光栅扫描搜索。为了减少扫描时间，可考虑在视频只做水平运动时做水平光栅搜索，在视频只做垂直运动时做垂直光栅搜索，若视频做斜线运动，则进行2倍步长的八边形搜索扩展搜索。八边形搜索的搜索速度要比光栅搜索快很多，这样既保证了搜索的精度，又提高了搜索速度。

(3)在搜索过程中引入阈值。

相关研究证实，宏块最优点80%以上是分布在半径为 4 的区域内，所以在搜索最佳匹配点的过程中，需要设定一些合适的阈值策略，避免找到最佳匹配点后仍进行一些不必要的搜索，通过提前中止搜索方式来减少运动估计的计算量。

3实验仿真

3.1仿真环境配置

实验采用由MERL机构提供的经典视频序列Ballroom和Exit，并将该优化算法和JMVC参考TZSearch算法、文献[6]快速算法进行比较分析。测试条件配置如表1所示。本节采用的多视点视频编码公共测试平台的版本号为JMVC8.5[7]，实验平台为Windows8 64位操作系统，主机配置为：内存4GB(3.88GB可用)，Intel(R)Core(TM)i3-3227UCPU@1.90GHz。

Table 1　 Configure table of test conditions

3.2实验结果及分析

表2给出了本文改进的TZSearch算法与JMVC参考TZSearch算法、文献[6]快速算法的编码时间、码率、峰值信噪比比较。表中ΔT表示新算法与JMVC参考算法的编码时间的变化百分比，ΔB表示新算法与JMVC参考算法的平均比特率的变化，ΔPSNR表示新算法与JMVC参考算法的平均峰值信噪比的变化，“+”表示提升，“-”表示降低。

从表2实验数据可知，本文改进的TZSearch算法与JMVC参考TZSearch算法相比，Ballroom测试序列的编码时间减少幅度为56.92%和62.25%，平均为60.61%，峰值信噪比平均下降0.022 4dB，比特率平均增加1.41%；Exit序列编码时间减少幅度为58.9%和62.78%，平均为61.45%，比特率平均增加1.86%，峰值信噪比平均下降0.002 31dB。本文改进的TZSearch算法与文献[6]相比：Ballroom测试序列的编码时间平均减少了4.87%，比特率平均减少了0.17%，峰值信噪比平均提高了0.005 5dB；Exit测试序列的编码时间平均减少了7.81%，平均比特率保持不变，峰值信噪比平均提高了0.002 5dB。

图2和图3分别是JMVC、文献[6]和本文算法的率失真性能比较和复杂度比较。

Figure 2　Comparison of rate distortion 图2　率失真曲线对比

Figure 3　Comparison of complexity 图3　复杂度对比

从图中很容易得知，本文算法、文献[6]和JMVC三种算法的率失真曲线图几乎重合，表明三者

Table 2　 Comparison of experimental results among JMVC, literature[6 ] and the proposed algorithm

的图像质量基本一样，本文算法的编码复杂度也得到了较明显改善，优于文献[6]。对于Ballroom和Exit测试序列它的编码时间减少了50%以上，大大降低了编码的复杂度。

4结束语

本文对JMVC中参考快速算法TZSearch进行了分析，针对其不足提出了优化算法，并对优化算法进行了实验仿真。最后对优化算法和原始算法，以及文献[6]算法进行了比较分析。实验结果表明：本文算法具有优良的率失真性能，在保证了重建视频质量和输出码率基本不变的前提下，使运动估计时间有了明显的降低，大大减少了编码的复杂度，提高了实时性能。

参考文献:

[1]ChenZ,ZhouP,HeY.FastintegerandfractionalPelmotionestimationforJVT[C]//ProcofJVT-F017,2002:5-13.

[2]PengTao.ResearchandimprovementofmotionestimationalgorithmbasedonH.264[D].Xi’an:XidianUniversity,2012.(inChinese)

[3]WuYue-ming.Researchonmotionestimationalgorithminvideocompression[D].Nanjing:NanjingUniversityofPostsandTelecommunications,2013.(inChinese)

[4]ShiChun-ying.Researchandimprovementofmotionestimationtechnology[D].Chengdu:ElectronicScienceandTechnologyUniversity, 2010.(inChinese)

[5]YangZhong-hua.Analysisandoptimizationofmultiviewvideocodingalgorithm[D].Xiamen:HuaqiaoUniversity,2011.(inChinese)

[6]LeiHai-jun,YangHui,YangZhang,etal.Fastmodedecisionalgorithminmulti-viewvideocoding[J].JournalofChineseSystems,2013,34(5):1176-1180.(inChinese)

[7]JMVC8.5,cvs-d:pserver:jvtuser@garcon.ient.rwth-aachen.de:/cvs/jvtcheckoutjmvc.

参考文献：附中文

[2]彭涛. 基于H.264的运动估计搜索算法的研究与改进[D].西安:西安电子科技大学,2012.

[3]吴跃明. 视频压缩中运动估计算法的研究[D].南京:南京邮电大学,2013.

[4]石春莺.H.264运动估计技术研究与改进[D].成都：电子科技大学，2010.

[5]杨中华.多视点视频编码算法分析与优化[D].厦门：华侨大学，2011.

[6]雷海军,杨辉,杨张,等. 多视点视频编码混合快速搜索算法

[J]. 小型微型计算机系统,2013,34(5):1176-1180.

袁梅冷(1974-),女,湖南隆回人，硕士，副教授，研究方向为视频与图形处理，电子商务技术。E-mail:mlyuan@szpt.edu.cn

YUANMei-leng,bornin1974,MS,associateprofessor,herresearchinterestsincludevideoandgraphicsprocessing,electroniccommercetechnology.

杨张(1984-),女,四川南部人，博士，助理研究员，研究方向为信息处理。E-mail:yangzhang@szpt.edu.cn

YANGZhang,bornin1984,PhD,assistantresearcher,herresearchinterestincludesinformationprocessing.

雷海军(1968-),男,湖南郴州人，博士后,副教授,CCF会员(E200023566M),研究方向为图像处理和高性能计算。E-mail:Lhj@szu.edu.cn

LEIHai-jun,bornin1968,postdoctor，associateprofessor,CCFmember(E200023566M),hisresearchinterestsincludeimageprocessing,andhighperformancecomputing.