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