一種基于JMVC參考模型的運(yùn)動估計優(yōu)化算法*

袁梅冷1，2，楊張2，雷海軍2

(1.深圳職業(yè)技術(shù)學(xué)院計算機(jī)工程學(xué)院，廣東 深圳 518055；2.深圳大學(xué)計算機(jī)與軟件學(xué)院，廣東 深圳 518060)

摘要：運(yùn)動估計(ME)是視頻壓縮編碼中的關(guān)鍵技術(shù)，運(yùn)動估計算法對視頻質(zhì)量、編碼復(fù)雜度和碼率都有直接影響。TZSearch 算法是JMVC 參考實(shí)現(xiàn)中一種基于混合模板的快速搜索算法。通過提高搜索起點(diǎn)準(zhǔn)確度，采用基于視頻運(yùn)動特性的搜索策略，采取閾值設(shè)置和大小步長相結(jié)合等方法對算法進(jìn)行優(yōu)化。在多視點(diǎn)視頻編碼測試平臺JMVC 8.5中對多視點(diǎn)視頻序列BallRoom、Exit進(jìn)行測試。實(shí)驗(yàn)結(jié)果表明，與JVMC的TZSearch算法相比，在保證視頻重構(gòu)質(zhì)量和碼率增加很少的情況下，本算法編碼時間減少50%以上。

關(guān)鍵詞：運(yùn)動估計；編碼復(fù)雜度；塊匹配； TZSearch；閾值；JMVC

中圖分類號：TP393.4 文獻(xiàn)標(biāo)志碼：A

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

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

基金項(xiàng)目：國家自然科學(xué)基金-廣東聯(lián)合項(xiàng)目(U1301252)；深圳市戰(zhàn)略性新興產(chǎn)業(yè)發(fā)展專項(xiàng)資金資助項(xiàng)目(JCYJ20120613113419607)；校重點(diǎn)項(xiàng)目(2213k3190007)

作者簡介:

通信地址：518055 廣東省深圳市深圳職業(yè)技術(shù)學(xué)院計算機(jī)工程學(xué)院

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引言

運(yùn)動估計方法較多，比較經(jīng)典的有塊匹配法、相位相關(guān)法和像素遞歸法[1,2]。其中塊匹配法最為簡單有效，已被廣泛應(yīng)用于各種視頻編碼標(biāo)準(zhǔn)，比如H.263、MPEG-4和H.264等。全搜索法采用了塊匹配法，它的思想是在搜索窗內(nèi)通過蠻力搜索尋找最佳的匹配塊。全搜索法雖能找到最優(yōu)匹配塊，但卻要付出高計算復(fù)雜度、高時延作為代價[3]，這恰是實(shí)時視頻應(yīng)用的致命缺陷。因此，設(shè)計出一個良好的快速塊匹配算法來減少運(yùn)動估計的計算時間是不可或缺的。如何降低運(yùn)動估計計算復(fù)雜度、減少延時也是當(dāng)今學(xué)者關(guān)注的熱點(diǎn)之一。經(jīng)過20多年的發(fā)展，很多塊匹配運(yùn)動估計算法被提出，這些算法的發(fā)展大致可分為四個階段：全搜索階段、規(guī)定最大搜索步數(shù)的搜索階段、不限搜索步數(shù)的快速搜索階段和混合模板搜索階段。規(guī)定最大搜索步數(shù)的搜索階段較經(jīng)典的有三步搜索法(TSS)、新三步搜索法(NTSS)、四步搜索法(4SS)等；不限搜索步數(shù)的快速搜索階段有基于塊的梯度下降搜索法(BBGDS)、六邊形搜索法(HEXBS)以及鉆石搜索法(DS)等；混合模板搜索階段比較著名的有MVFAST、PMVFAST、UMHexagonS、EPZS等新的快速算法[2～4]。本文對JMVC運(yùn)動估計算法開展分析和研究，并在此基礎(chǔ)上提出了優(yōu)化算法。

2TZSearch算法分析與優(yōu)化

2.1TZSearch算法分析

TZSearch算法是一種基于塊匹配的混合模板快速搜索算法，是JMVC參考實(shí)現(xiàn)中默認(rèn)的快速搜索算法，其搜索模型包括八點(diǎn)方形搜索、八點(diǎn)鉆石形搜索、星形搜索、光柵搜索和兩點(diǎn)搜索等[5]。TZSearch算法在實(shí)際多視點(diǎn)視頻編碼應(yīng)用中存在不足之處，主要表現(xiàn)在：

(1) 在搜索起點(diǎn)預(yù)測矢量集合中，考慮的相關(guān)矢量過少，未對當(dāng)前編碼宏塊的中值預(yù)測矢量和零向量的相鄰位置矢量進(jìn)行完全評估，實(shí)際上這些相鄰塊的運(yùn)動矢量很可能是和當(dāng)前編碼宏塊運(yùn)動矢量一致的。

(2)在搜索過程中未引入閾值設(shè)置提前終止搜索。和單視點(diǎn)一樣，多視點(diǎn)視頻編碼的運(yùn)動矢量/視差矢量也存在中心偏置特性，即在當(dāng)前搜索點(diǎn)的周圍小區(qū)域內(nèi)搜索到最優(yōu)點(diǎn)的概率最大，很多情況在前面三輪搜索內(nèi)就能找到最優(yōu)匹配點(diǎn)。而在粗略搜索步驟中的八點(diǎn)鉆石模型搜索中，匹配搜索固定為七輪，在找到最優(yōu)點(diǎn)后仍然繼續(xù)后面幾輪的搜索，沒有及時中斷搜索過程，這樣會增加編碼復(fù)雜度和浪費(fèi)資源，影響編碼的實(shí)時性。

(3)在搜索策略上，TZSearch算法默認(rèn)采用統(tǒng)一的搜索模型，都是先八點(diǎn)鉆石搜索，然后光柵搜索/兩點(diǎn)搜索，最后循環(huán)八點(diǎn)鉆石搜索。沒有根據(jù)視頻內(nèi)容和運(yùn)動特性選擇不同的搜索模型，未對視頻序列運(yùn)動劇烈程度進(jìn)行預(yù)判，存在較多不必要的搜索，導(dǎo)致編碼時間長，編碼效率不高。

(4)在搜索模型的選取上，精細(xì)搜索和細(xì)化搜索步驟中采用的稠密光柵搜索和八點(diǎn)鉆石搜索，時間消耗相當(dāng)大，不適于視頻編碼的實(shí)時應(yīng)用。

2.2TZSearch算法的優(yōu)化

TZSearch算法中統(tǒng)一的搜索策略與搜索模型的應(yīng)用導(dǎo)致編碼時間過長，編碼效率不高，阻礙了視頻編碼的實(shí)時應(yīng)用。本文通過擴(kuò)充優(yōu)化搜索起點(diǎn)預(yù)測集合、采用基于視頻運(yùn)動特性的搜索策略和搜索模型、引入搜索提前終止閾值設(shè)置等方法對算法進(jìn)行優(yōu)化，算法流程如圖1所示。算法優(yōu)化策略如下：

(1)擴(kuò)充搜索起點(diǎn)預(yù)測集合，提高搜索起點(diǎn)準(zhǔn)確度。

如果在搜索起始就采用準(zhǔn)確的起始點(diǎn)預(yù)測，便能更準(zhǔn)確更迅速地匹配到最優(yōu)運(yùn)動矢量，從而大幅度減少計算時間，提高編碼性能。因此，在預(yù)測矢量集合中除了包含中值預(yù)測矢量、(0,0) 位置矢量、參考幀對應(yīng)宏塊的左上和右上位置宏塊的矢量外，新增中值預(yù)測矢量空間鄰近宏塊的運(yùn)動矢量和零向量周圍鄰近塊的運(yùn)動矢量。即預(yù)測矢量集合S由S1與S2的并集組成。S1如式(1)所示：

(1)

其中，MVpred_MP為中值預(yù)測矢量，MVLeft為左方預(yù)測矢量，MVUp為上方預(yù)測矢量，MVRU為右上方預(yù)測矢量。將中值矢量和零矢量的左方、右方、上方和下方四點(diǎn)也加入到S1中的函數(shù)計算,如(2)所示：

(2)

預(yù)測矢量集合S2由中值預(yù)測矢量MVpred_MP和零向量(0,0)的函數(shù)計算式的并集組成，如式(3)所示：

(3)

(4)

最佳搜索起點(diǎn)矢量MVmin根據(jù)式(5)計算得出：

(5)

(2)采用基于視頻運(yùn)動特性的搜索模型和搜索策略。

最優(yōu)匹配點(diǎn)的分布情況和視頻序列的運(yùn)動特性息息相關(guān)，運(yùn)動平緩的視頻，最優(yōu)點(diǎn)出現(xiàn)在搜索中心點(diǎn)鄰近的小區(qū)域內(nèi)；而運(yùn)動劇烈的視頻，最優(yōu)點(diǎn)出現(xiàn)在距離搜索中心較遠(yuǎn)的區(qū)域。搜索策略應(yīng)根據(jù)視頻運(yùn)動狀況做及時調(diào)整。如最佳搜索起點(diǎn)在(0,0) 位置矢量，即iStartX=0和iStartY=0，則判斷為靜止宏塊，直接結(jié)束搜索;否則,繼續(xù)下一步粗略搜索。

Figure 1　Flowchart of the optimizaed algorithm 圖1　優(yōu)化的算法流程圖

在相關(guān)文獻(xiàn)中已經(jīng)證實(shí)與鉆石模型相比，六邊形搜索模型具有更優(yōu)良的性能，復(fù)雜度也低，在細(xì)化搜索過程中可以考慮使用六邊形代替鉆石模型進(jìn)行搜索。稠密的光柵搜索是TZSearch 算法中最為耗時的環(huán)節(jié)，它要在搜索區(qū)域內(nèi)進(jìn)行等步長的水平和垂直光柵掃描搜索。為了減少掃描時間，可考慮在視頻只做水平運(yùn)動時做水平光柵搜索，在視頻只做垂直運(yùn)動時做垂直光柵搜索，若視頻做斜線運(yùn)動，則進(jìn)行2倍步長的八邊形搜索擴(kuò)展搜索。八邊形搜索的搜索速度要比光柵搜索快很多，這樣既保證了搜索的精度，又提高了搜索速度。

(3)在搜索過程中引入閾值。

相關(guān)研究證實(shí)，宏塊最優(yōu)點(diǎn)80%以上是分布在半徑為 4 的區(qū)域內(nèi)，所以在搜索最佳匹配點(diǎn)的過程中，需要設(shè)定一些合適的閾值策略，避免找到最佳匹配點(diǎn)后仍進(jìn)行一些不必要的搜索，通過提前中止搜索方式來減少運(yùn)動估計的計算量。

3實(shí)驗(yàn)仿真

3.1仿真環(huán)境配置

實(shí)驗(yàn)采用由MERL機(jī)構(gòu)提供的經(jīng)典視頻序列Ballroom和Exit，并將該優(yōu)化算法和JMVC參考TZSearch算法、文獻(xiàn)[6]快速算法進(jìn)行比較分析。測試條件配置如表1所示。本節(jié)采用的多視點(diǎn)視頻編碼公共測試平臺的版本號為JMVC8.5[7]，實(shí)驗(yàn)平臺為Windows8 64位操作系統(tǒng)，主機(jī)配置為：內(nèi)存4GB(3.88GB可用)，Intel(R)Core(TM)i3-3227UCPU@1.90GHz。

Table 1　 Configure table of test conditions

3.2實(shí)驗(yàn)結(jié)果及分析

表2給出了本文改進(jìn)的TZSearch算法與JMVC參考TZSearch算法、文獻(xiàn)[6]快速算法的編碼時間、碼率、峰值信噪比比較。表中ΔT表示新算法與JMVC參考算法的編碼時間的變化百分比，ΔB表示新算法與JMVC參考算法的平均比特率的變化，ΔPSNR表示新算法與JMVC參考算法的平均峰值信噪比的變化，“+”表示提升，“-”表示降低。

從表2實(shí)驗(yàn)數(shù)據(jù)可知，本文改進(jìn)的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。本文改進(jìn)的TZSearch算法與文獻(xiàn)[6]相比：Ballroom測試序列的編碼時間平均減少了4.87%，比特率平均減少了0.17%，峰值信噪比平均提高了0.005 5dB；Exit測試序列的編碼時間平均減少了7.81%，平均比特率保持不變，峰值信噪比平均提高了0.002 5dB。

圖2和圖3分別是JMVC、文獻(xiàn)[6]和本文算法的率失真性能比較和復(fù)雜度比較。

Figure 2　Comparison of rate distortion 圖2　率失真曲線對比

Figure 3　Comparison of complexity 圖3　復(fù)雜度對比

從圖中很容易得知，本文算法、文獻(xiàn)[6]和JMVC三種算法的率失真曲線圖幾乎重合，表明三者

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

的圖像質(zhì)量基本一樣，本文算法的編碼復(fù)雜度也得到了較明顯改善，優(yōu)于文獻(xiàn)[6]。對于Ballroom和Exit測試序列它的編碼時間減少了50%以上，大大降低了編碼的復(fù)雜度。

4結(jié)束語

本文對JMVC中參考快速算法TZSearch進(jìn)行了分析，針對其不足提出了優(yōu)化算法，并對優(yōu)化算法進(jìn)行了實(shí)驗(yàn)仿真。最后對優(yōu)化算法和原始算法，以及文獻(xiàn)[6]算法進(jìn)行了比較分析。實(shí)驗(yàn)結(jié)果表明：本文算法具有優(yōu)良的率失真性能，在保證了重建視頻質(zhì)量和輸出碼率基本不變的前提下，使運(yùn)動估計時間有了明顯的降低，大大減少了編碼的復(fù)雜度，提高了實(shí)時性能。

參考文獻(xiàn):

[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.

參考文獻(xiàn)：附中文

[2]彭濤. 基于H.264的運(yùn)動估計搜索算法的研究與改進(jìn)[D].西安:西安電子科技大學(xué),2012.

[3]吳躍明. 視頻壓縮中運(yùn)動估計算法的研究[D].南京:南京郵電大學(xué),2013.

[4]石春鶯.H.264運(yùn)動估計技術(shù)研究與改進(jìn)[D].成都：電子科技大學(xué)，2010.

[5]楊中華.多視點(diǎn)視頻編碼算法分析與優(yōu)化[D].廈門：華僑大學(xué)，2011.

[6]雷海軍,楊輝,楊張,等. 多視點(diǎn)視頻編碼混合快速搜索算法

[J]. 小型微型計算機(jī)系統(tǒng),2013,34(5):1176-1180.

袁梅冷(1974-),女,湖南隆回人，碩士，副教授，研究方向?yàn)橐曨l與圖形處理，電子商務(wù)技術(shù)。E-mail:mlyuan@szpt.edu.cn

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

楊張(1984-),女,四川南部人，博士，助理研究員，研究方向?yàn)樾畔⑻幚?。E-mail:yangzhang@szpt.edu.cn

YANGZhang,bornin1984,PhD,assistantresearcher,herresearchinterestincludesinformationprocessing.

雷海軍(1968-),男,湖南郴州人，博士后,副教授,CCF會員(E200023566M),研究方向?yàn)閳D像處理和高性能計算。E-mail:Lhj@szu.edu.cn

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