一種基于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.