一種自適應(yīng)十字—方形運動估計快速算法
2009-01-01 00:00:00王莉莉黃曉革甘濤
計算機(jī)應(yīng)用研究 2009年2期
（電子科技大學(xué) 電子工程學(xué)院， 成都 610054）
摘 要：為了減少視頻編碼的運算量，提出了一種新的自適應(yīng)十字—方形運動估計搜索算法（ACSS），根據(jù)不同的搜索模式給出了三個提前退出門限以及提前退出技術(shù)的快速運動估計算法，它體現(xiàn)了粗定位和準(zhǔn)定位的并行處理思想。仿真結(jié)果表明在不降低信噪比和碼率的情況下，ACSS算法的計算復(fù)雜度有明顯的改善，可廣泛用于各編碼標(biāo)準(zhǔn)，提高編碼的速度和效率。
關(guān)鍵詞：H.264標(biāo)準(zhǔn)；塊匹配；自適應(yīng)十字—方形搜索；運動估計
中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A
文章編號：10013695(2009)02054003
Adaptive crosssquare algorithm for fast motion estimation
WANG Lili，HUANG Xiaoge，GAN Tao
(School of Electronic Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)
Abstract:In order to reduce the computation，this paper proposed a new adaptive crosssquare search algorithm for motion estimation(ACSS). Meanwhile，incorporated three early termination criteria into the motion estimation process according to multiple motion estimation modes.The new algorithm ACSS was based on two schemes: rough location and accurate orientation. With the similar PSNR and bit rate， the result of emulation indicates the computational complexity of the crosssquare algorithm is reduced significantly. It can be widely used in general video coding standards to develop the speed and efficient of video coding.
Key words:H.264 standard; blockmatching; adaptive crosssquare search; motion estimation
0 引言
運動估計和運動補償技術(shù)可以有效降低圖像序列在時域方向上的冗余性，其中塊匹配算法因具有算法簡單、便于硬件實現(xiàn)等優(yōu)點被許多國際標(biāo)準(zhǔn)所采納。最直接的塊匹配算法是全搜索（FS）法，其精度最高，但計算復(fù)雜度高，軟硬件實現(xiàn)困難。
為降低運動估計的運算量，三步法（TSS）[1]、新三步法（NTSS）[2]、四步法（FSS）[3]、菱形搜索法（DS）[4]和六邊形搜索法（HEXBS）[5]等很多快速搜索算法被提出以提高運動估計的速度。這些算法利用運動矢量的中心偏置分布特性來設(shè)計搜索模板和搜索策略，提高了匹配速度，但搜索精度仍待進(jìn)一步改善。
近年來，新的快速運動估計算法不斷涌現(xiàn)，大都充分利用了運動矢量的時空相關(guān)性、傾向水平垂直方向的非對稱模板、靈活有效的終止準(zhǔn)則。典型的算法有運動矢量場自適應(yīng)快速搜索法(MVFAST)[6]、增強預(yù)測區(qū)域搜索法(EPZS)[7]、自適應(yīng)十字模式搜索法(ARPS)[8]、非對稱十字多層六邊形搜索法(UMHexagonS)[9]，它們代表著當(dāng)今快速運動估計算法研究領(lǐng)域的最新成果。其中MVFAST被MPEG4列為編碼器優(yōu)化的核心算法，UMHexagonS和EPZS 則先后被H.264[10]的驗證模型所采納。
本文在分析運動矢量和絕對誤差和（SAD）的空間分布特性的基礎(chǔ)上，綜合采用了多參考運動矢量預(yù)測、終止準(zhǔn)則、多搜索模板等一系列技術(shù)，設(shè)計了一種新的自適應(yīng)運動估計算法，并在H.264參考代碼JM 10.2中驗證了本算法的優(yōu)越性。值得注意的是，該算法并不是專門針對H.264設(shè)計的運動估計算法，它可以廣泛用于所有壓縮編碼標(biāo)準(zhǔn)。
1 ACSS算法
1.1 預(yù)測搜索起點
序列圖像的運動矢量在空間和時間上具有很強的相關(guān)性，特別是屬于同一對象的塊運動保持一致的可能性更大。這時若根據(jù)鄰塊的運動矢量來預(yù)測搜索起點，會使中心偏移更加集中。這種方法被很多快速算法所采用，本算法也是從預(yù)測點開始搜索。
如圖1所示，編碼過程中宏塊按掃描順序編碼，同一幀圖像中與當(dāng)前塊相鄰的已編碼塊共有四個。O為當(dāng)前編碼塊，A、B、C、D為四個已編碼鄰塊，分別位于當(dāng)前塊的左方、上方、右上方和左上方，其運動矢量分別記為MVA、MVB、MVC、MVD，前一幀相同位置塊E的運動矢量MVE也可以用于預(yù)測。另外，記
MVP=median(MVA，MVB，MVC)(1)
當(dāng)MVC不存在時，用MVD代替。
本文選擇中心點 (0，0)、MVP、MVA、MVB、MVC、MVE六個運動矢量預(yù)測搜索起點，這些運動矢量是最容易挑選的，也不會顯著增加計算量。不選擇MVD的原因是：MVD與MVA、MVB相關(guān)性很大，在MVA、MVB作預(yù)測的前提下，MVD使用與否對搜索結(jié)果影響不大。
分別計算這六個運動矢量所指的塊對應(yīng)的塊失真度，度量失真的指標(biāo)常采用SAD。設(shè)得到的塊失真度分別為SADP、SADO、SADA、SADB、SADC、SADE，則搜索起點為
Vs=arg{min(SADP，SADO，SADA，SADB，SADC，SADE)}(2)
即具有最小SAD值的運動矢量為當(dāng)前塊的搜索起始點。
1.2 宏塊分類
圖像中不同區(qū)域的運動劇烈程度往往不同，為了兼顧各種運動序列的搜索精度和搜索速度，本文采用大、小兩種類型模板(圖2)。大模板用于快速跟蹤物體的運動方向；小模塊用于精細(xì)局部搜索，確定最終的運動矢量。
由于大多數(shù)塊的最佳運動矢量非?？拷A(yù)測起點，如果每個塊均采用先大模板再小模板的搜索方式，則難以使算法發(fā)揮最大的效率。本文首先對圖像塊的運動進(jìn)行預(yù)測分類，然后針對不同的運動類型選擇不同的搜索模式。
分類方法同樣考慮了運動矢量的相關(guān)性，記
L=max(|mv1x-mv2x|+|mv1y-mv2y|)
mv1，mv2∈{MVA，MVB，MVC，MVE}(3)
即L為預(yù)測矢量間的最大街區(qū)距離，L越大，預(yù)測矢量的分布越分散，塊的運動就越復(fù)雜，因此L可以作為搜索模式選擇的依據(jù)。
a)如果L<4，說明圖像塊的運動為靜態(tài)和慢速運動，只需在預(yù)測后的搜索起點附近作小步長的密集搜索，即選擇小模式反復(fù)搜索。
b)如果L≥4，說明圖像塊的運動幅度可能較大，應(yīng)該采用大步長模板搜索，否則容易陷入局部最優(yōu)值。
1.3 搜索模板
一般說來，模板的形狀和大小對快速運動估計算法的搜索速度和預(yù)測精度都有著非常重要的影響。目前，絕大多數(shù)的快速運動估計算法都是以菱形模板或改進(jìn)模板為主[4，6，7]，如圖2所示。本文對其搜索方式進(jìn)行了一定的改進(jìn)。
在菱形算法中采用兩種搜索模板，分別是有九個搜索點的大模板LDSP(large diamond search pattern)和有五個搜索點的小模板SDSP(small diamond search pattern)。搜索時先用LDSP計算。
當(dāng)最小塊誤差(minimum block distortion，MBD)點不出現(xiàn)在中心處時，以MBD點為新的中心用LDSP模板搜索；否則，使用SDSP模板匹配，這時五個點中的MBD即為最優(yōu)匹配點。
可見，LDSP搜索最佳點所在區(qū)域時，廣度搜索和梯度下降搜索同時進(jìn)行，即同等地對待搜索區(qū)域的各部分，造成較大的搜索冗余，影響了算法的搜索速度。如圖2(a)所示，本文將LDSP的九個搜索點分為兩部分：五個點的十字模板和四個點的方形模板。實際序列中水平和垂直方向上的運動最為常見，因而可以采用先搜索十字模板，后搜索方形模板的策略。修正的LDSP方式如下：
a)先搜索LDSP中的十字模板，如果MBD點不在中心點，以MBD點為新的中心，跳到步驟a）；
b)搜索LDSP中的方形模板，如果MBD點不在中心點，以MBD點為新的中心，跳到步驟a）；
c)結(jié)束LDSP搜索步驟。
可見，改進(jìn)算法利用運動矢量的方向性，每次大模板搜索只需要計算五或九個點，進(jìn)一步降低了計算復(fù)雜度。
1.4 終止準(zhǔn)則
實際中絕大多數(shù)序列的運動都很小，它們的運動矢量通常高度集中分布在搜索窗的中心位置附近。如果能夠找到一個合適的閾值T，在進(jìn)行一定數(shù)目的搜索點后，若SADp小于該閾值，則直接終止搜索過程，可以大幅度降低算法的計算時間。
閾值的選擇在很大程度上依賴于視頻編碼的具體環(huán)境(如運動類型、碼率等)。ARPS采用了固定閾值(對宏塊T1＝512)，不具有普遍性； UMHexagonS算法引入了QP對閾值的影響因子，計算過程復(fù)雜。
本文采用了三種門限值T1、T2、T3，分別用于不同搜索階段的終止判斷?？紤]算法的魯棒性和計算方便，閾值也充分利用了鄰塊的相關(guān)性：
Tstabile=max(SADi|MVi=(0，0))
Tmobile=min(SADi|MVi≠(0，0))
MVi∈{MVA，MVB，MVC，MVE}(4)
即根據(jù)運動矢量將鄰塊分為靜止塊和運動塊兩類，取靜止塊的SAD最大值為Tstabile，運動塊的SAD最小值為Tmobile，則閾值Ti（i=1，2，3）取值為
T1=min(Tstabile，Tmobile)
T2=mean(Tstabile，Tmobile)
T3=max(Tstabile，Tmobile)(5)
可見，T1≤T2≤T3。在檢測零運動矢量后，T1用于判斷當(dāng)前塊是否是靜止塊；在檢測完六個預(yù)測矢量后，T2用于判斷是否提前結(jié)束搜索；T3則在大小模板搜索過程中使用。
1.5 ACSS算法流程
本文算法的詳細(xì)流程如下：
a)初始化。根據(jù)式(4)(5)確定門限T1，T2，T3。
b)檢測零運動矢量，如果SADmin＜T1，跳到步驟g)。
c)檢測MVP、MVA、MVB、MVC、MVE，如果SADmin＜T2，跳到步驟g)。
d)根據(jù)式(3)判斷當(dāng)前塊的類型，如果為劇烈運動塊，跳到步驟e)；否則跳到步驟f)。
e)反復(fù)使用改進(jìn)的LDSP搜索方式，每次大模板匹配后，如果SADmin＜T3，跳到步驟g)；當(dāng)MBD位于中心點時，跳到步驟f)。
f)反復(fù)使用SDSP搜索方式，每次小模板匹配后，如果SADmin＜T3，跳到步驟g)；當(dāng)MBD位于中心點時，跳到步驟g)。
g)算法結(jié)束，得到最優(yōu)運動矢量。
2 實驗結(jié)果
為驗證本文算法的性能，在JM 10.2中對FS、UMHexagonS、EPZS進(jìn)行了計算機(jī)仿真實驗。選取CIF格式akiyo、container、foreman、mobile、flower五種標(biāo)準(zhǔn)序列，每種序列編碼前100幀，Baseline級，單參考幀，量化系數(shù)QP為28，最大搜索范圍16像素。實驗結(jié)果如表1所示。
其中：NCC為標(biāo)準(zhǔn)化的計算復(fù)雜度(normalized computational cost，NCC)：
NCC=mode[Npts(mode)×W(mode)]/（NMODE×Nref）(6)
式中，Npts(mode)表示mode模式下總的搜索點數(shù)，NMODE為總的編碼模式數(shù)；NMODE＝7；Nref為總的參考幀數(shù)量，在本實驗中Nref＝1；W(mode)為不同模式下對搜索點數(shù)的權(quán)重值。當(dāng)編碼為16×16模式時，W(mode)＝1；16×8或8×16模式時，W(mode)＝1/2；8×8模式時，W(mode)＝1/4；8×4或4×8模式時，W(mode)＝1/8；4×4模式時，W(mode)＝1/16。
從PSNR和碼率兩個指標(biāo)來看，對于各種序列，四種算法的運行結(jié)果都非常接近，這也說明了本文算法的高效性。在計算復(fù)雜度方面， 該算法在各種序列中的NCC值都是最小的，分別約為UMHexagonS算法的16%~33%、EPZS算法的30%~50%，說明本算法是其中搜索速度最快的算法。
3 結(jié)束語
本文提出了新的快速運動估計算法，綜合采用了預(yù)測搜索起點、終止準(zhǔn)則、自適應(yīng)搜索模板相結(jié)合等技術(shù)。該算法形式簡單、易于實現(xiàn)，在算法復(fù)雜度和準(zhǔn)確性上都優(yōu)于以往的快速運動估計算法，對于實時視頻壓縮領(lǐng)域具有廣闊的應(yīng)用前景。
參考文獻(xiàn)：
［1］
KOGA T， LINUMA K，HIRANO A，et al.Motion compensated interframe coding for video conferencing[C]//Proc of National Telecommunications Conference.1981：G5.3.1G5.3.5.
[2]LI Renxiang，ZENG Bing，LIOU M L.A new threestep search algorithm for block motion estimation[J].Trans on Circuits and Systems for Video Technology，1994，4(4):438442.
[3]PO Laiman，MA W C.A novel fourstep search algorithm for fast block motion estimation[J].Trans on Circuits and Systems for Video Technology，1996，6(3):313317.
[4]THAM J Y，RANGANATH S，RANGANATH M，et al.A novel unrestricted centerbiased diamond search algorithm for block motion estimation[J].Trans on Circuits and Systems for Video Technology，1998，8(4):369377.
[5]ZHU Ce，LIN Xiao，CHAU L P.Hexagonbased search pattern for fast block motion estimation[J].IEEE Trans on Image Processing，2000，9(2):287290.
[6]MA Kaikuang，HOSUR P I.ISO/IEC JTC1/SC29/WG11，Performance report of motion vector field adaptive search technique(MVFAST)[S].2000.
[7]YI Xiaoquan，ZHANG Jun，LING N，et al.Fast ME in the JM reference software，JVTP026[R].2005.
[8]NIE Yao，MA Kaikuang.Adaptive rood pattern search for fast blockmatching motion estimation[J].IEEE Trans on Image Proces-sing，2002，11(12):14421449.
[9]CHEN Zhibo，ZHOU Peng，HE Yun，et al.Fast integer and fractional pel motion estimation for JVT，JVTF017[R].2002.
[10]Joint Video Team.ISO/IEC 1449610 AVC and ITUT rec.H.264，draft ITUT recommendation and final draft international standard of joint video specification[S].2003.
