摘 要：根據視頻序列最優運動矢量的分布特性，提出了一種新型快速搜索" title="快速搜索">快速搜索算法。仿真表明，該算法在不改變重建圖像質量的條件下，大幅減小了搜索點數，提高了搜索效率。
關鍵詞：H.264? 運動估計? 搜索算法? SCSP? 閾值? 中值預測
?
?
??? 在H.264標準中，提高運動估計算法效率的主要技術可以歸納為三類：一是起始搜索點的選擇，二是更高效的塊匹配準則，三是減少搜索點數的搜索策略。其中，效率最高、使用最多的是第三類[1]。
??? 目前，塊匹配運動估計算法中搜索精度最高的是全搜索法FS(Full Search Method)[2]，但它計算量大，不適合實時應用。為此，人們提出了許多快速運動估計算法，如交叉法CSA(Cross Search Algorithm)[3]、菱形法DS(Diamond Search)[4]、六邊形法HSP(Hexagon Search Pattern_)等。
1 經典搜索算法分析
1.1 交叉法
??? 交叉法CSA是在二維對數法TDL和三步法TSS基礎上，為進一步減少計算量而發展起來的快速搜索算法。其搜索策略是：從原點開始，以最大搜索長度的一半為步長，以“×”字形分布的5個點構成每次搜索的點群，搜索計算得到MBD(Minimum Block Distortion)點，以該MBD點為中心點" title="中心點">中心點，步長減半，繼續做“×”字形搜索，直至步長為1，之后根據MBD點的位置，分別做“+”字形或“×”字形搜索，從而獲得全局最優運動矢量，如圖1所示。
?
1.2 菱形搜索" title="菱形搜索">菱形搜索法
??? 菱形搜索法DS采用2種搜索模板，分別為大菱形搜索模板LDSP（Large Diamond Search Pattern）和小菱形搜索模板SDSP（Small Diamond Search Pattern）。LDSP需計算9個搜索點的SAD（Sum of Absolute Difference）值，而SDSP只需計算5個搜索點的SAD值。其搜索策略是：先以預測的起始搜索點為中心點，計算LDSP中9個點的SAD值，如果MBD點不為中心點，則重復LDSP直至MBD點為中心點，之后轉入SDSP，計算5個點的SAD值，SAD值最小點對應的運動矢量為全局最優運動矢量，如圖2所示。
?
?
1.3 六邊形搜索算法
??? 六邊形搜索算法是對菱形搜索法的改進，它將DS算法中的LDSP改為六邊形，而SDSP仍然保留, 如圖3所示。
?
?
1.4 優缺點分析
??? 現有搜索算法大都采用大、小兩種搜索模板，且先采用大的搜索模板，再轉向小的搜索模板。但在實際應用中，視頻圖像的大部分區域沒有發生變化或變化甚微，因此，當運動矢量很小或為零時，會造成極大的搜索冗余，降低了搜索效率。
2 新型快速搜索算法
??? 在眾多視頻圖像中，相鄰幀之間通常都具有極強的相關性，在運動平緩區域，這種相關性更加明顯。由于視頻對象的運動具有連續性，因此在描述視頻序列運動特征的宏塊" title="宏塊">宏塊(或宏塊分割、亞宏塊分割)運動矢量之間，也必然存在時空域的相關性，而相鄰塊間運動矢量的相關性就更強。統計數據表明，在諸多圖像序列中，如視頻會議、視頻電話等，80%以上塊的最優運動矢量分布在一個區域圓中，圓心為搜索窗口中心，半徑為2個像素，如圖4所示?；诖朔植继匦裕疚奶岢鲆环N新型搜索模板，即小交叉形搜索模板SCSP(Small Cross Search Pattern)，其搜索策略與交叉法CSA類似，不同之處是搜索步長固定為1個像素，如圖5所示。
?
?
2.1 搜索模板的自適應選擇
??? 搜索模板自適應選擇的基本思想是：根據當前塊(即預測塊)運動矢量的大小，對搜索模板進行動態改變，對于運動矢量較小的區域，即運動平緩區域，采用SCSP搜索模板；而對于運動矢量較大的區域，即運動劇烈區域，采用LHDSP（Large Hexagon Diamond Search Pattern）搜索模板。
??? 多次測試foreman、football、bridge、highway、temple等序列后，本文取T=2為閾值，當運動矢量小于T時，判定當前塊為靜止塊或準靜止塊，即采用SCSP搜索模板；當運動矢量大于T時，判定當前塊為運動塊，即采用LHDSP搜索模板。
2.2 當前塊運動矢量的獲得
??? 獲得當前塊運動矢量的示意圖如圖6所示[5]。首先，設E為當前宏塊，其運動矢量為MVP。如果E的左側多于一個塊，令E左側最上方塊（圖中為A塊）的運動矢量為MVA，同理，可以得到E正上方最左側塊（圖中為B塊)的運動矢量為MVB、E右上方最左側塊(圖中為C塊)的運動矢量為MVC，采用運動矢量中值預測法可得：MVP=(|MVA|+|MVB|+|MVC|+1)/3。而當前塊位于當前幀邊緣時有三種情況：
??? (1)當前塊位于當前幀最右邊，MVP=(|MVA|+|MVB|+1)/2。
??? (2)當前塊位于當前幀最左邊，MVP=(|MVB|+|MVC|+1)/2。
??? (3)當前塊位于當前幀最上邊，MVP=MVA。如果右上角宏塊不可用，可用左上角宏塊的MV代替。
?
?
2.3 搜索策略
??? (1)確定起始搜索點后，比較當前塊的預測運動矢量MVP與閾值T的大小。
??? (2)如果MVP≥T，則轉移到第3步，否則，跳轉到第4步。
??? (3)采用六邊形法搜索：首先使用HSP模板搜索，計算7個點的SAD值，如果MBD點不為中心點，則重復HSP直至MBD點為中心點，之后轉入SDSP模板搜索，計算5個點的SAD值， SAD值最小點對應的運動矢量即為全局最優運動矢量。
??? (4)采用小交叉法搜索：使用SCSP模板搜索，計算5個點的SAD值，如果MBD點不為中心點，則重復SCSP直至MBD點為中心點，該點對應的運動矢量即為全局最優運動矢量。
3 系統仿真" title="系統仿真">系統仿真與結果分析
??? 為驗證新算法的搜索性能，并與FS、DS進行對比分析，本文從搜索點數、峰值信噪比PSNR(YUV分量)和壓縮比等三個方面進行系統仿真。其中，測試平臺為JM8.2，測試長度為90幀，量化參數分別為QP=5、QP=29，測試序列采用具有很強代表性的bridge.cif(小運動序列)和football.cif(大運動序列)。另外，FS的搜索范圍設置在±16之間。
??? 三種搜索算法的性能比較如表1所示，其中，Y代表亮度分量，U、V代表色度分量。當測試序列為小運動序列時，系統仿真得到的搜索點數如圖7所示；而測試序列為大運動序列時，系統仿真得到的搜索點數如圖8所示。
?
?
??? 由表1可以看出，在重建圖像質量基本相同的條件下，FS算法的平均搜索點數要遠遠大于DS算法和新算法，因此，在圖7和圖8中沒有畫出FS算法的搜索點數。
?
?
??? 分析仿真結果，可以得到如下結論：
?? (1)新算法、DS算法與FS算法相比，在PSNR值基本保持不變的條件下，大幅度減少了搜索點數，而新算法又明顯優于DS算法，特別是在運動平緩區域，表現更加突出；
?? (2)不同的QP值對壓縮比影響較大，QP越大，壓縮比越高，從而更有利于實時通信；
?? (3)不同的QP值對搜索點數影響不大，但對PSNR值影響巨大，QP越大，PSNR越小，從而重建圖像的質量也就越差。
??? 本文基于最優運動矢量的分布特性，設計了一種小交叉形搜索模板，同時根據預測值與閾值的比較結果可知，自適應選擇搜索模板，使搜索算法的性能得到進一步提高。仿真結果表明，新算法大幅度減少了搜索點數，提高了H.264的編、解碼速度，促進了H.264的實時性應用。
參考文獻
[1] 唐良瑞.圖像處理實用技術[M].北京：化學工業出版社，2002.
[2] 丁貴廣.Visual C++6.0 數字圖像編碼[M].北京：機械工業出版社，2004.
[3] GHANBARI M.The cross-search algorithm for motion estimation[J].IEEE Trans-Communication.1990，38(7)：950-953.
[4] ZHU S，MA K K.A new diamond search algorithm for fast?block matching motion estimation[J].IEEE Trans-Image? Processing.2000，9(2)：287-290.
[5] 畢厚杰.新一代視頻壓縮標準H.264/AVC[M].北京：人民郵電出版社，2005.