摘 要：根據視頻序列最優(yōu)運動矢量的分布特性,，提出了一種新型快速搜索" 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基礎上,，為進一步減少計算量而發(fā)展起來的快速搜索算法。其搜索策略是：從原點開始,，以最大搜索長度的一半為步長,，以“×”字形分布的5個點構成每次搜索的點群，搜索計算得到MBD(Minimum Block Distortion)點,，以該MBD點為中心點" title="中心點">中心點,，步長減半，繼續(xù)做“×”字形搜索,，直至步長為1,，之后根據MBD點的位置，分別做“+”字形或“×”字形搜索,，從而獲得全局最優(yōu)運動矢量,，如圖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值最小點對應的運動矢量為全局最優(yōu)運動矢量,，如圖2所示,。
?
?
1.3 六邊形搜索算法
??? 六邊形搜索算法是對菱形搜索法的改進，它將DS算法中的LDSP改為六邊形,，而SDSP仍然保留, 如圖3所示,。
?
?
1.4 優(yōu)缺點分析
??? 現(xiàn)有搜索算法大都采用大、小兩種搜索模板,，且先采用大的搜索模板,，再轉向小的搜索模板。但在實際應用中,，視頻圖像的大部分區(qū)域沒有發(fā)生變化或變化甚微,，因此，當運動矢量很小或為零時,，會造成極大的搜索冗余,，降低了搜索效率。
2 新型快速搜索算法
??? 在眾多視頻圖像中,，相鄰幀之間通常都具有極強的相關性,，在運動平緩區(qū)域，這種相關性更加明顯,。由于視頻對象的運動具有連續(xù)性,，因此在描述視頻序列運動特征的宏塊" title="宏塊">宏塊(或宏塊分割、亞宏塊分割)運動矢量之間,，也必然存在時空域的相關性,，而相鄰塊間運動矢量的相關性就更強。統(tǒng)計數據表明,，在諸多圖像序列中,，如視頻會議、視頻電話等,，80%以上塊的最優(yōu)運動矢量分布在一個區(qū)域圓中,，圓心為搜索窗口中心，半徑為2個像素,，如圖4所示,。基于此分布特性,，本文提出一種新型搜索模板,，即小交叉形搜索模板SCSP(Small Cross Search Pattern)，其搜索策略與交叉法CSA類似,，不同之處是搜索步長固定為1個像素,，如圖5所示,。
?
?
2.1 搜索模板的自適應選擇
??? 搜索模板自適應選擇的基本思想是：根據當前塊(即預測塊)運動矢量的大小，對搜索模板進行動態(tài)改變,，對于運動矢量較小的區(qū)域,，即運動平緩區(qū)域，采用SCSP搜索模板,；而對于運動矢量較大的區(qū)域,，即運動劇烈區(qū)域，采用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值最小點對應的運動矢量即為全局最優(yōu)運動矢量,。
??? (4)采用小交叉法搜索：使用SCSP模板搜索，計算5個點的SAD值,，如果MBD點不為中心點,，則重復SCSP直至MBD點為中心點，該點對應的運動矢量即為全局最優(yōu)運動矢量,。
3 系統(tǒng)仿真" title="系統(tǒng)仿真">系統(tǒng)仿真與結果分析
??? 為驗證新算法的搜索性能,，并與FS、DS進行對比分析,，本文從搜索點數,、峰值信噪比PSNR(YUV分量)和壓縮比等三個方面進行系統(tǒng)仿真。其中,，測試平臺為JM8.2,，測試長度為90幀，量化參數分別為QP=5,、QP=29,，測試序列采用具有很強代表性的bridge.cif(小運動序列)和football.cif(大運動序列)。另外,，F(xiàn)S的搜索范圍設置在±16之間,。
??? 三種搜索算法的性能比較如表1所示，其中,，Y代表亮度分量,，U、V代表色度分量,。當測試序列為小運動序列時,，系統(tǒng)仿真得到的搜索點數如圖7所示；而測試序列為大運動序列時，系統(tǒng)仿真得到的搜索點數如圖8所示,。
?
?
??? 由表1可以看出,，在重建圖像質量基本相同的條件下，F(xiàn)S算法的平均搜索點數要遠遠大于DS算法和新算法,，因此,，在圖7和圖8中沒有畫出FS算法的搜索點數。
?
?
??? 分析仿真結果,，可以得到如下結論：
?? (1)新算法,、DS算法與FS算法相比，在PSNR值基本保持不變的條件下,，大幅度減少了搜索點數,，而新算法又明顯優(yōu)于DS算法，特別是在運動平緩區(qū)域,，表現(xiàn)更加突出,；
?? (2)不同的QP值對壓縮比影響較大，QP越大,，壓縮比越高,，從而更有利于實時通信；
?? (3)不同的QP值對搜索點數影響不大,，但對PSNR值影響巨大,，QP越大,，PSNR越小,，從而重建圖像的質量也就越差。
??? 本文基于最優(yōu)運動矢量的分布特性,，設計了一種小交叉形搜索模板,，同時根據預測值與閾值的比較結果可知，自適應選擇搜索模板,，使搜索算法的性能得到進一步提高,。仿真結果表明，新算法大幅度減少了搜索點數,，提高了H.264的編,、解碼速度，促進了H.264的實時性應用,。
參考文獻
[1] 唐良瑞.圖像處理實用技術[M].北京：化學工業(yè)出版社,，2002.
[2] 丁貴廣.Visual C++6.0 數字圖像編碼[M].北京：機械工業(yè)出版社，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.