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