用于塊匹配運動估值的正方形-菱形搜索算法

1、_第25卷第7期2002年7月計算機學報CHINESEJ1COMPUTERSVol.25No.7July2002用于塊匹配運動估值的正方形-菱形搜索算法劉海峰郭寶龍馮宗哲(西安電子科技大學機電工程學院西安710071)摘要運動估值在視頻圖像編碼中占有重要地位,該文首先研究了運動估值中的經(jīng)典搜索算法并重點分析了菱形(DS)算法;然后設(shè)計了一種新的綜合模板(SDP),它體現(xiàn)了粗定位和準確定位并行處理的思想,在此基礎(chǔ)上提出了一種新的用于塊匹配的運動估值搜索算法正方形2菱形搜索(SDS)算法.最后通過實驗驗證了該算法的有效性.關(guān)鍵詞塊匹配,運動估值,菱形算法,正方形2菱形搜索算法中圖法分類號:TP39

2、1ASquare-DiamondSearchAlgorithmforBlockMotionEstimationLIUHai2FengGUOBao2LongFENGZong2Zhe(SchoolofMechan2ElectronicEngineering,XidianUniversity,Xian710071)AbstractThispaperfirstlyanalyzessometypicalsearchalgorithmsinmotionestimation,espe2ciallytheDiamondSearch(DS)algorithm.Itisfoundthatthesealgorith

3、msareallbasedonserialprocessingideas,sincetheirsearchstepscanonlybechangeddegressively,inotherwords,first.Secondly,coarselocationandsecondaccurateorientation,whichmakethesearchblindnessaimedatquestionsexistinginthesealgorithms,theauthorsdesignanewintegrativepatternSquareDiamondPattern(SDP),whichisco

4、mposedofadiamondandasquare.TheSDPcanreal2izecontent2basedsearchforfollowingthreepossibilitieswhenitperformsmatchingcomputation.Iftheminimumblockdistortion(MBD)pointinthemiddleofthepattern,itshowsthatimageisstillandcompletessearchbyonestep,iftheMBDpointisatoneofthediamondsfourcorners,itshowsthereissm

5、allmotionintheimage,iftheMBDpointisatoneofthesquaresfourcor2ners,itshowsthereislargemotionintheimage.Thenextstepofsearchwilladaptivelyusedif2.Therefore,SDPisbasedonparallelprocessingideaofferentpatternaccordingtomotiontypescoarselocationandaccurateorientationdeterminedbyitsstructure.Thirdly,authorsp

6、resentanewSquare2DiamondSearch(SDS)AlgorithmforblockmatchingmotionestimationwithSDP.Finally,theresultsofexperimentsshowthatnotonlythenewSDSismuchfasterthantradition2alalgorithms,butalsoitsPSNRandvisualqualityoftheretrievalimagesarebetterthanthoseofotheralgorithms,andasnearlygoodasthatofFS.Keywordsbl

7、ockmatching,motionestimation,diamondsearch,square2diamondsearchalgorithm(SDS)收稿日期:2001207216;修改稿收到日期:2002202228.本課題得到國家自然科學基金(69975015)資助.劉海峰,男,1978年生,碩士研究生,研究興趣包括數(shù)字圖像處理、圖像通信、神經(jīng)網(wǎng)絡(luò)、模式識別等.E2mail:liuwest;liuwest.郭寶龍,博士,教授,博士生導師,主要研究領(lǐng)域為神經(jīng)網(wǎng)絡(luò)與模式識別、智能信息處理、電路與系統(tǒng)、圖像處理、圖像通信等.馮宗哲,副教授,研究生導師,研究方向有電路與系統(tǒng)、神經(jīng)網(wǎng)絡(luò)、模式識別

8、等. 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved._中國科技論文在線748計算機學報2002年范圍內(nèi)構(gòu)成了誤差表面函數(shù),該函數(shù)的全局最小點1引言對于視頻序列圖像,由于相鄰的幀間存在很大的時間相關(guān)性,即時間冗余(temporalredundancy),所以通過減小這種時間冗余,可以提高視頻編碼效率.這方面一種有效方法是基于塊匹配的運動估值(MotionEstimation,ME),它目前已被許多視頻編碼標準所采納,例如MPEG21、MPEG22、MPEG24、1,2ITU2TH.261和H.263等

9、.即對應(yīng)著最佳運動矢量.由于這個誤差表面通常并不是單調(diào)的,所以搜索窗口太小,就容易陷入局部最優(yōu);而搜索窗口太大,又容易產(chǎn)生錯誤的搜索路徑.另外,統(tǒng)計數(shù)據(jù)表明,視頻圖像中進行運動估值時,最優(yōu)點通常在零矢量周圍(以搜索窗口中心為圓心,兩像素為半徑的圓內(nèi))8,如圖1所示.在塊匹配算法(Block2MatchingAlgorithm,BMA)中,首先將圖像分割成MN的宏塊MB(MacroBlock),并假設(shè)塊內(nèi)像素作相同的運動,且只作平移運動,然后用當前圖像的每一宏塊在上一幀的一定范圍內(nèi)搜索最優(yōu)匹配.最簡單而且可靠的搜索算法是全搜索或窮盡搜索法(FS),它對搜索范圍內(nèi)的每一個像素點處進行匹配運算以得到

10、一個最優(yōu)的運動矢量MV(MotionVector).但FS運算量太大,軟件實時性不好.后來人們相繼提出了許多快速搜索算法,例如三步法(TSS)3,四步法(FSS)4,二維對數(shù)法(TDL)5,基于塊的梯度下降法(BBGDS)6,交叉法(CS)7和菱形法(DS)8210,它基于這兩點事實,DS算法采用了兩種搜索模板,分別是有9個檢測點的大模板LDSP(LargeDi2amondSearchPattern)和有5個檢測點的小模板SDSP(SmallDiamondSearchPattern),如圖2和圖3所示.搜索時先用大模板LDSP在搜索區(qū)域中心及周圍8個點處進行匹配計算,當最小塊誤差MBD點(Mi

11、nimumBlockDistortion)(MAD值最小的點)出現(xiàn)在中心點處時,將大模板LDSP換為SD2SP,再進行匹配計算,這時5個點中的MBD即為最們通過不同的搜索模板和搜索方式,在速度上的確比FS提高了許多,但性能都比不上FS,因為這些快速算法減少了搜索點數(shù),因此,有必要尋找更加高效的(快速、準確)塊匹配運動估值算法.本文通過分析DS算法指出現(xiàn)有的快速搜索算法都是基于串行處理機制,并在DS搜索模板的基礎(chǔ)上,設(shè)計了使用大小模板并行處理的綜合模板,并提出了一種新的搜索算法正方形2菱形搜索算法(Square2DiamondSearch,SDS).最后的實驗結(jié)果表明,本文提出的SDS算法速度和

12、性能都明顯優(yōu)于.DS等算法,其運動估計的準確性與FS相當優(yōu)匹配點;否則,改變中心點位置,仍用LDSP重復計算.2DS算法8,9DS算法即菱形搜索(DiamondSearch)算法,是快速算法中性能最優(yōu)異的算法之一,最近該算法被MPEG24VM標準所接受10.2.1DS算法的思想搜索模板的形狀和大小不但影響整個算法的運行速度,而且也影響它的性能.塊匹配的誤差在搜索 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved._中國科技論文在線7期劉海峰等:用于塊匹配運動估值的正方形2菱形搜索算法7492.2對DS算

13、法的分析DS算法的特點在于它分析了視頻圖像中運動因.SDS算法在進行運動估值的匹配運算時,有3種可能的情況,下面以具體的搜索步驟來說明:Step1.以搜索區(qū)原點對應(yīng)SDP中心,在SDP上9個點矢量的基本規(guī)律,選用了兩種形狀的搜索模板LD2SP和SDSP.先用LDSP大范圍搜索,再用SDSP來處分別進行匹配計算,然后判斷找出MBD點,若MBD點位于中心,說明圖像是靜止的,SDS算法一步結(jié)束,進行Step4;若MBD點位于正方形4個頂點處,說明圖像的運動準確定位,所以它的性能優(yōu)于其它算法.但是,DS算法只是一種搜索策略的折衷處理,其性能上的缺陷表現(xiàn)在兩個方面:(1)對于運動稍微大一點的圖像,如果取

14、常用的7個像素點的搜索范圍,速度就比不上FSS,因為FSS8采用55的正方形搜索窗,它的覆蓋范圍比LDSP大;(2)對于保持靜止的圖像序列,即運動矢量為零矢量的情況,DS算法必須要依次計算LDSP和SDSP兩個模板的13個點,而理想情況是只需計算SDSP的5個點,即對于小運動搜索DS算法還有待改進.綜合分析DS及其它快速算法后可以發(fā)現(xiàn),它們都是基于串行處理思想的,即為了保證算法的效率和收斂性,搜索模板和搜索步長只能由大到小,先進行粗定位,然后再準確定位.這種串行搜索方式帶有盲目性,不能根據(jù)圖像的內(nèi)容(運動類型)作靈活處理,這對小運動來說是一種浪費,而且當?shù)谝徊降牟介L較大時還會誤導搜索方向,影響

15、搜索的速度和準確性.針對這些問題,本文提出了一種新的搜索算法正方形2菱形算法(Square2DiamondSearch),簡稱SDS算法,較好地解決了上面幾個問題,使得SDS在時間和性能上都優(yōu)于以往的快速運動估值較大,則進行Step2;若MBD點位于菱形4個頂點處,說明圖像的運動較小,則進行Step3;Step2.以上一次找到的MBD點作為中心點,進行與Step1相同的運算;Step3.以上一次的MBD點作為中心點,將SDP收縮為圖5所示的菱形模板DP(DiamondPattern),在5個點處分別計算,然后找出新的MBD點,若MBD點位于中心,則進行Step4;若MBD點位于周圍4個點處,則

16、重復Step3;Step4.將該中心點作為最佳匹配點,得到運動矢量;由此可以看出,SDS算法有如下特點:(1)SDS算法的搜索不需要經(jīng)歷模板由大到小的必然過程,有時一步即可完成搜索;(2)使用SDS算法,可以根據(jù)圖像中的運動類型(如上述3種情況),自適應(yīng)選擇下一步相應(yīng)的搜索模板,實現(xiàn)了基于內(nèi)容的搜索,從而得到較好的估值結(jié)果;(3)直觀地講,SDP是正方形和菱形兩種模板的組合,SDP綜合模板的運算可以看作是兩種不同模板并行運算的結(jié)果;(4)用SDP搜索時,正方形模板保持了大模板粗定位的特性,而菱形模板則有準確“聚焦”的特性,這從本質(zhì)上體現(xiàn)了SDP是粗定位和準確定位的并行實施;上述特點說明SDS算

17、法是基于并行處理的.SDS算法在搜索模板改變位置時,總有兩個重疊的算法.3SDS算法3.1SDS算法原理及描述SDS的模板是在DS的小模板基礎(chǔ)上,增加向四周延伸的正方形的4個頂點,形成一個新的綜合模板,稱為正方形菱形模板SDP(SquareDiamond.這也是該算法稱作SDS的原Pattern),如圖4所示點,所以當重復使用SDP時只需計算7個新的檢測點,重復使用DP時只要計算3個新的檢測點,這就提高了搜索效率.圖6給出了搜索過程中模板改變的3種情況. 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved

18、._中國科技論文在線750計算機學報2002年3.2SDS算法分析SDS算法在最低代價(最少檢測點)下引入了總共22個點,每一步檢測的新點數(shù)分別為9、7、3和3點.總之,SDS要比DS在速度上有所提高.大小模板并行處理的思想.運動較大時,可以持續(xù)用大步長來搜索,而同時保持了在局部范圍內(nèi)的“聚焦”特性,當真正遇到小運動時,又會靈活使用小步長的模板.例如零矢量的情況,SDS算法只需檢測9個點即可獲得運動矢量,而其它算法如TSS需要檢測25個點、FSS需要檢測17個點、DS也需要檢測13個點.按視頻圖像運動矢量的統(tǒng)計規(guī)律,假設(shè)最佳點就在圖1所示的圓內(nèi),對DS和SDS兩種算法需要檢測的點數(shù)進行比較,如

19、表1所示,從表中可以看出SDS總比DS少14個搜索點.表1比較DS和SDS在零矢量周圍的搜索算法DS最佳點位置中心點13SDS算法和DS算法一樣,沒有限制搜索的步處半徑為1處1316半徑為2處18數(shù),而且搜索范圍不必固定,所以使用起來非常靈活,同時SDS算法的收斂性是可以保證的.由于MPEG標準中對運動矢量編碼時字長有限制,也即限制了最大搜索范圍,所以在算法中我們也加入了邊界條件的約束.文獻8舉了一個用DS算法搜索到運動矢量(-4,-2)的例子,如圖7所示,搜索共有5步,使用了四次LDSP和一次SDSP,總共搜索了24個點.圖8是用SDS算法搜索到同樣點的可能路徑.可以看出,SDS算法有四步,

20、用了兩次SDP和兩次DP,4實驗分析下面用搜索時間和搜索準確性兩個測度來驗證.實驗采用CIF(CommonIntermediateSDS的性能Format)標準灰度化序列圖像,宏塊大小為1616,搜索范圍為1515,即7個像素點,匹配準則為SAD,即求和絕對誤差(theSumofAbsoluteDiffer2ence),其定義為MNkSAD(i,j)=fm=1n=1k-1(m,n)-(1)f(m+i,n+j)式(1)中,(i,j)為位移矢量,fk和fk-1分別為當前幀和上一幀的灰度值,MN為宏塊的大小. 1995-2004 Tsinghua Tongfang Optical Disc Co.,

21、 Ltd. All rights reserved._中國科技論文在線7期劉海峰等:用于塊匹配運動估值的正方形2菱形搜索算法7514.1搜索時間搜索時間是這樣測定的:分別在Tennis,Sales2man和MissAmerica序列中選3個宏塊,各代表大運動、中等運動和小運動,然后分別用7種算法進行運動估計.實驗是在P866、256M內(nèi)存的PC機上進行的,用VisualC+6.0編程實現(xiàn),為了時間測試的準確性,每個算法的運動估計都循環(huán)了10000次,相當于25幀352288圖像總的運動估值計算量,如此連續(xù)測試3幀.結(jié)果如表2所示,對每一類運動“1”、“2”、“3”表示連續(xù)3幀依次進行的運動估計

22、.(時間單位:msMV單位:像素)CS7219729917617611031DS661(0,0)1112(0,4)()1261(6,2)1262(-3,2)()671(2,0)842(1,1)()SDS460(0,0)1092(0,4)()1261(4,1)1272(5,2)()621(1,0)791(1,1)()表2搜索時間測試結(jié)果序列12Tennis12Salesman1MissAmerica2算法FS8602(0,0)9674(0,4)()11186(4,1)10796(5,2)()8252(1,0)9423(1,1)()TSS1342(0,0)1322(0,5)()1342(7,3)1

23、422(3,1)()1372(1,0)1362(1,1)()FSS1792(0,0)1161(0,4)()1322(4,1)1332(5,2)()1532(1,0)1643(1,1)()TDL1202(0,0)1332(0,4)()1662(6,2)1602(4,2)()1242(1,0)1242(1,1)()(0,0)(0,4)()(4,0)(6,2)()(1,0)(1,1)()從表2中可以看出:(1)FS得到的運動矢量可以看作是最佳值,但時間消耗的確太大,最長時間為13590ms;(2)對Tennis序列,除TDL外,其余算法都有誤差,SDS對(0,0)ME用時僅為460ms,幾乎是FS的

24、120,對(0,7)的估計差了一個像素;(3)對Salesman序列,其它算法的準確性都很差,只有CS過了圖像編碼和解碼的部分),然后逐幀計算出PSNR.將所有146幀的PSNR求平均值,結(jié)果如表3所示.表3PSNR比較算法FSTSSFSSTDLCSDSSDSPSNRav(dB)36.4235.1336.0136.0534.3136.1236.32在速度上有一定優(yōu)勢,而SDS不但ME最準確,速度也較快;(4)對MissAmerica序列,ME準確性都一樣,但SDS在速度上表現(xiàn)了其優(yōu)越性.這些實驗數(shù)據(jù)表明:以FS的運動估值結(jié)果為標準,SDS算法總體上比其它算法都快,而且性能與FS相當.4.2準確

25、性比較比較方法:僅選取MissUSA序列,直接用各個算法得到的運動矢量,由上一幀恢復出當前幀圖像(注:這里專門測試運動估值的效果,所以過程中跳表3中FS的平均PSNR最高,達到36.42dB,說明效果最好;CS最低,僅為34.31,SDS為36.32,高于DS、FSS和TDL等,僅次于FS算法0.10dB.圖9直觀地顯示了不同算法對相同序列(MissAmerican)計算產(chǎn)生的PSNR,圖9(a)清楚地顯示出SDS的性能與FS十分接近,而優(yōu)于DS.圖9(b)顯示出SDS比FSS、CS及TSS等其它算法的性能提高很多. 1995-2004 Tsinghua Tongfang Optical Di

26、sc Co., Ltd. All rights reserved._中國科技論文在線752計算機學報32002年實驗結(jié)果表明:SDS算法不論在搜索時間還是搜索的準確性方面都優(yōu)于現(xiàn)有的快速算法.LiR,ZengB,LiouML.Anewthree2stepsearchalgorithmforblockmotionestimation.IEEETransCircuitsSystemsforVideoTechnology,1994,4(4):438-4425結(jié)論本文依據(jù)并行處理思想,設(shè)計了一種大小模板并存的綜合模板SDP,提出了一種新的用于塊匹配的正方形2菱形搜索算法SDS.實驗結(jié)果表明,SDS在時

27、間和性能上都優(yōu)于以往的快速運動估值算法.SDP體現(xiàn)了一定的生物視覺的特性,例如,人眼視網(wǎng)膜上神經(jīng)元感受器的排列也是中央密(稱中央凹),兩邊稀少,同時可以實現(xiàn)聚焦和大范圍搜索的工作.這說明視覺系統(tǒng)中具有這種并行處理的規(guī)律.下一步我們將系統(tǒng)研究并行模板的結(jié)構(gòu),探索并行處理的原理.參考文獻1VideoCodingforLowBitrateCommunication.1995.2SpecialIssueonMPEG24.IEEETransCircuitsSystemsforVideoTechnology,1997,7(2)International4PoML,MaCW.Anovelfour2steps

28、earchalgorithmforfastblockmotionestimation.IEEETransCircuitsSystemsforVideoTechnology,19966(6):313-3175JainJ,JainA.Displacementmeasurementanditsapplicationininterframeimagecoding.1981,29(12):1799-1808IEEETransCommunication,6LKLiu,EFeig.Ablock2basedgradientdescentsearchalgo2rithmforblockmotionestimat

29、ioninvideocoding.IEEETransCircuitsSystemsforVideoTechnology,1996,6(8):419-42378GhanbariM.Thecross2searchalgorithmformotionestima2tion.IEEETransCommunication,1990,38(7):950-953ZhuS,MaKK.Anewdiamondsearchalgorithmforfastblock2matchingmotionestimation.IEEETransImageProcess2ing,2000,9(2):287-2909ThamYJ,

30、RanganathS,RanganathMetal.Anovelunre2strictedcenter2biaseddiamondsearchalgorithmforblockmo2tionestimation.IEEETransCircuitsSystemsforVideoTech2nology,1998,8(8):369-37710TourapisMA,ShenGetal.Anewpredictivediamondsearchalgorithmforblockbasedmotionestimation.1765-1773In:ProcVisualCommunicationsandImageProceedings,Australia,2000,3:TelecommunicationUnion,ITU2TRecommendationH.263