基于方向自適應十字搜索的快速塊匹配運動估計算法

摘要：提出了一種方向自適應十字搜索算法，通過自適應地使用小十字模板、大十字模板和四種方向的T形模板，有效地減少了搜索點數，提高了搜索速度。實驗結果表明，該算法在保持與菱形搜索（DS）、正方形—菱形搜索（SDS）、十字—菱形搜索（CDS）和小十字—菱形搜索（SCDS）四種算法相同搜索精度的同時，速度上比DS、SDS、CDS和SCDS算法分別提高了74.65%、39.78%、42.44%和7.84%。

關鍵詞：塊匹配；運動估計；方向自適應十字搜索

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2007)05－0044－02

0引言

運動估計是視頻編碼中的核心技術，運動估計的好壞直接影響到編碼的效率和圖像恢復的質量。塊匹配運動估計算法（BMA）是消除視頻數據時間冗余最基本且最重要的方法。由于其具有簡單高效、額外開銷小、易于硬件實現等優點而被包括H.26x、MPEG－1，MPEG－2和MPEG－4在內的絕大多數視頻編碼標準所采用。塊匹配就是將每一幀圖像分成大小相同、互不重疊的子塊（宏塊），然后在參考幀中固定大小的搜索窗口內找到最佳匹配塊。按照一種塊損失度量準則找到的最佳匹配塊到當前塊的位移用運動矢量來描述。最佳匹配塊與當前塊之間的差值稱為殘差。預測得越準確，意味著殘差中的數值越小，編碼后的比特數也就越小。

全搜索（Full Search，FS）是BMA中最直接的實現方法，FS通過對搜索窗內的所有點進行搜索，可以達到最佳匹配，但是FS算法的計算量巨大。為了減少計算量，提高塊匹配速度，人們提出了許多快速的塊匹配算法，如三步搜索，新三步搜索、四步搜索、菱形搜索（Diamond Search，DS）[1，2]、正方形—菱形搜索（Square－Diamond Search，SDS）[3]、十字—菱形搜索（Cross－Diamond Search，CDS）[4]、小十字—菱形搜索（Small－Cross－Dia－mond Search，SCDS）[5]和風箏—十字—菱形搜索（Kite－Cross－Diamond Search， KCDS）[6]。由于運動矢量(MV)具有中心分布的特征，大多數MV分布在距離中心5×5的區域中，也就是說多數塊可以被認為是靜止的或者是準靜止的。在NTSS、FSS、DS、SDS、CDS、SCDS算法中，都對中心附近的點進行了重點搜索，以期望盡快找到運動矢量，中止搜索。SDS算法還提出了一種粗定位和細定位并行進行的思想[3]，這樣既能以最快的速度找到中心附近的運動矢量，同時也可以快速定位那些遠距離的運動矢量，避免陷入局部最優。

1方向自適應十字搜索算法

1．1搜索模板

根據前面的統計規律，本文提出的方向自適應十字搜索算法（OACS）使用了三種十字形模板，即小十字模板、大十字模板和T形模板（TSP）。其中TSP可以看成是十字形模板的一種變形，是特殊的十字形模板。為了便于敘述后面算法，在此定義三個點的概念，即中心點（CP）、鄰點（AP）和方向點（OP）。CP是模板的物理或者邏輯中心，其作用是指示搜索停止；AP是與CP相距為1的點，指示最佳匹配點就在附近，后面的搜索可以用SCSP來完成；方向點與中心點距離為2，它有兩個作用，即指示下一步搜索方向和進行粗定位。圖1(a)顯示了OACS算法用到的SCSP和LCSP；(b)～(e)分別顯示了四個方向的TSP，即U－TSP、D－TSP、L－TSP和R－TSP。

1．2OACS算法

根據視頻序列運動矢量分布的統計規律，先使用不帶OP的SCSP開始搜索。這樣對于大多數靜止塊來說可以一步結束，有效地減少搜索點數，提高搜索速度。然后計算SCSP四周的四個點，也就是LCSP的四個OP點。如果最小BDM點位于AP上，認為最佳匹配點就在附近，可以用SCSP完成后面的搜索；如果最小BDM點位于OP上，則根據這個方向點選擇一個與之相對應的合適的TSP繼續搜索。在用TSP搜索時，如果最小BDM點位于TSP的CP上，則搜索結束；如果位于TSP的AP上，則使用SCSP繼續搜索；如果位于TSP的OP上，則繼續用TSP搜索。該算法流程如圖2所示。

OACS算法的計算流程如下：

（1）以搜索區原點對應SCSP中心，在SCSP上五個點處分別進行匹配計算，找出最小BDM點。若最小BDM點位于SCSP的CP，則轉（5）；若最小BDM點位于SCSP的AP，則轉（2）。

（2）對LCSP最外邊的四個OP分別進行匹配計算。若最小BDM點位于LCSP的AP上，則轉（3）；若最小BDM點位于LCSP的OP上，則轉（4）。

（3）以上一次的最小BDM點作為中心點，以SCSP作為模板進行搜索，找出新的最小BDM點。若最小BDM點位于SCSP的CP，則轉（5）；若最小BDM點位于SCSP的AP，則重復（3）；若模板的點超出搜索范圍，則該點無效。

（4）以上一次的最小BDM點作為中心點，并根據上一次的最小BDM點所確定的方向選擇一個TSP進行搜索，找出新的最小BDM點。若最小BDM點位于TSP的CP，則轉（5）；若最小BDM點位于TSP的AP，則轉（3）；若最小BDM點位于TSP的OP，則重復（4）；若模板的點超出搜索范圍，則該點無效。

（5）將該中心點作為最佳匹配點，得到運動矢量。

2實驗結果和分析

OACS算法是在H.264/AVC參考模型JM 7.3上實現并與其他算法進行比較的。實驗選擇了八個具有廣泛代表性的標準測試序列，即Salesman、Carphone、Miss American、Grandmother（QCIF，176×144，150幀）、Foreman（CIF，352×288，100幀）、Flower Garden、Table Tennis和Football（SIF，352×240，100幀）。其中，Miss America、Grandmother為小運動或幾乎靜止序列、Carphone、Foreman、Salesman為中等運動序列、Football和Table Tennis為大運動序列、Flower Garden則包含了較多的細節與鏡頭平移。采用的幀率為30Hz，CABAC熵編碼，搜索范圍是±16點，單幀參考，使用全部七種塊進行匹配。編碼后的序列除首幀外，其余各幀均為P幀，即采用IPPP…的方式，各幀量化參數（QP）均為28。為便于比較，還在JM 7.3上實現了其余幾個經典算法，即DS、SDS、CDS和SCDS。

表1是OACS算法與其他算法在平均搜索點數（Average Searching Points， ASP）的比較結果。其中加速倍數都是與FS算法相比較得到的。ASP可以作為衡量算法速度的依據。從表1中可以看出，OACS算法的速度是最快的，是FS的150倍以上。與其他幾種算法相比，在速度上OACS比DS、SDS、CDS和SCDS分別提高了74.65%、39.78%、42.44%和7.84%。

表2是亮度分量的峰值信噪比（Peak Signal－to－Noise Ratio， PSNR）的比較結果。括號中的數據是與FS算法的PSNR的差值。從表2可以看出，無論視頻序列是小運動、大運動和鏡頭平移，OACS算法的亮度分量PSNR與FS算法相比，最大損失僅為0.08 dB，平均損失0.029 dB，其損失可以忽略不計。與其他幾種算法相比，它們的亮度分量PSNR幾乎是相同的。

3結束語

在分析了幾種經典的塊匹配算法的基礎上，結合現實世界中視頻序列的統計規律，本文提出了一種方向自適應十字搜索算法。開始搜索時使用（SCSP），這種模板對于那些在中心附近靜止塊或者準靜止塊很有效，文獻[7]中使用了類似的初始化搜索模板；再使用大十字模板（LCSP）以確定下一步搜索方向，同時進行粗定位，避免陷入局部最優；然后，或者使用SCSP完成后續搜索，或者根據上一步確定的方向，自適應地使用一種TSP繼續朝著最小BDM點可能的方向去搜索。同時TSP本身也包含了一種并行搜索的思想，因為它既包含了用來粗定位和指示方向的點，也包含了用來細定位的相鄰點。實驗表明，OACS較之其他的BMAs有著更少的搜索點數，同時保持了相當的搜索精度。

參考文獻：

［1］THAM J Y，RANGANATH S，RANGANATH M，et al. A novel unrestricted center－based diamond search algorithm for block motion estimation[J].IEEE Trans. Circuits System for Video Technology，1998，8(4):369－377.

[2]ZHU Shan，MA Kaikuang. A new diamond search algorithm for fast block matching motion estimation[J].IEEE Trans. Image Proces－sing，2000，9(2):287－290.

[3]劉海峰，郭寶龍，馮宗哲.用于塊匹配運動估值的正方形—菱形搜索算法[J]. 計算機學報，2002，25(7):747－752.

[4]CHEUNG C H，PO L M. A novel cross－diamond search algorithm for fast block motion estimation[J].IEEE Trans. Circuits System for Video Technology，2002，12(12):1168－1177.

[5]CHEUNG C H，PO L M. A novel small－cross－diamond search algorithm for fast video coding and video conferencing applications:proc.of IEEE ICIP[C].[S.l.]:[s.n.]，2002:681－684.

[6]LAM C W，PO L M，CHEUNG C H. A novel kite－cross－diamond search algorithm for fast block matching motion estimation:IEEE International Symposium on Circuits and Systems[C].[S.l.]:[s.n.]，2004:729－732.

[7]NIE Yao，MA Kaikuang.Adaptive rood pattern search for fast block－matching motion estimation[J].IEEE Trans. Image Processing，2002，11(12):1442－1449.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”