張正華，陸大偉，海愛成，陳 亮

（揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225009）

1 引言

H.264標(biāo)準(zhǔn)[1-3]作為新一代視頻編碼的標(biāo)準(zhǔn)，它的主要任務(wù)是在時(shí)域和空域上減少視頻的冗余信息，相應(yīng)的有幀間編碼技術(shù)[4-6]和幀內(nèi)編碼技術(shù)[7]。而運(yùn)動(dòng)估計(jì)是幀間編碼中的一項(xiàng)核心技術(shù)，它能有效的去除視頻序列的幀間時(shí)域冗余，從而提高編碼效率。研究快速有效的運(yùn)動(dòng)估計(jì)算法一直是幀間編碼領(lǐng)域的熱點(diǎn)問題，其中，全搜索算法（Full Search，F(xiàn)S）的精度最高，但是計(jì)算復(fù)雜度大，耗時(shí)長，導(dǎo)致很難進(jìn)行實(shí)際應(yīng)用，因此，研究者們提出了各種快速運(yùn)動(dòng)搜索算法，比較適用的有菱形搜索算法[8]（Diamond Search，DS）、六邊形搜索算法[9]（Hexagon Based Search，HEXBS）、基于塊的梯度下降搜索算法[10]（Block-based Gradient Descent Search，BBGDS）等等，這些快速算法通過使用不同的搜索模板和策略，減少了計(jì)算復(fù)雜度。因此，本文就如何減少平均搜索點(diǎn)數(shù)，從而減少計(jì)算復(fù)雜度，提出了一種混合運(yùn)動(dòng)搜索算法，采用三種搜索窗口：矩形搜索窗口、大菱形搜索窗口以及小六邊形搜索窗口，仿真結(jié)果表明，該算法可以有效減少平均運(yùn)動(dòng)搜索點(diǎn)數(shù)，提高編碼效率，同時(shí)能保證較好的編碼質(zhì)量。

2 塊匹配準(zhǔn)則

在基于塊的快速運(yùn)動(dòng)搜索算法中，需要使用塊匹配準(zhǔn)則來衡量兩個(gè)相匹配的像素塊之間的誤差，通常有3種塊匹配準(zhǔn)則：最小絕對(duì)差（Minimum Absolute Difference，MAD）、均方誤差和（Mean Square Error，MSE）和歸一化互相關(guān)函數(shù)（Normalized Cross Correlation Function，NCCF）。

實(shí)踐結(jié)果表明，采用以上3種塊匹配準(zhǔn)則中的任何一個(gè)，匹配結(jié)果都差不多，而采用MAD作為匹配準(zhǔn)則，不需要作乘法運(yùn)算，實(shí)現(xiàn)簡單，因此通常采用MAD作為匹配準(zhǔn)則。但是在實(shí)際應(yīng)用中，考慮到塊匹配的大小基本控制在16×16點(diǎn)像素之內(nèi)，對(duì)參考幀和當(dāng)前幀對(duì)應(yīng)像素的差值取絕對(duì)值后累加求和的數(shù)值，可以直接進(jìn)行比較；同時(shí)，對(duì)絕對(duì)差之和進(jìn)行除法運(yùn)算減低了計(jì)算的精度，所以本文采用MAD的變化形式絕對(duì)誤差和（Sum of Absolute Difference，SAD）作為判斷準(zhǔn)則，其表達(dá)式為

式中：（i，j）為位移矢量，若在某一個(gè)（i，j）處的 SAD（i，j）值最小，則該點(diǎn)為最佳匹配點(diǎn)；xk（m，n）和 xk-1（m+i，n+j）分別為第k幀和第k-1幀的像素值。

3 混合運(yùn)動(dòng)搜索算法

本文算法采用3種搜索窗口：矩形窗口、大菱形窗口和小六邊形窗口，如圖1所示。

圖1 3種搜索窗口

其中，矩形窗口，由3×3的點(diǎn)陣構(gòu)成，適用于各種視頻序列的初步搜索；大菱形窗口，它由外圍的8個(gè)點(diǎn)加上中心的1個(gè)點(diǎn)構(gòu)成，適用于一般運(yùn)動(dòng)的視頻序列的進(jìn)一步搜索；小六邊形窗口，它由外圍的4個(gè)點(diǎn)加上中心的1個(gè)點(diǎn)構(gòu)成，適用于運(yùn)動(dòng)劇烈的視頻序列的精確搜索。

終上所述，筆者提出的算法步驟如下：

1）以3×3矩形窗口為搜索窗口，檢測此窗口的8個(gè)點(diǎn)，外加中心點(diǎn)，若最佳匹配點(diǎn)位于中心，則跳到3），否則進(jìn)行下一步；

2）以上一步最佳匹配點(diǎn)為中心構(gòu)造一個(gè)大菱形窗口，檢測其9個(gè)點(diǎn)，若最佳匹配點(diǎn)位于中心，則進(jìn)行下一步，否則重復(fù)這一步；

3）以小六邊形窗口為搜索模板，檢測外圍的4個(gè)點(diǎn)，得到最佳目標(biāo)運(yùn)動(dòng)矢量。

算法示意圖如圖2所示。

圖2 混合搜索算法

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證所提算法的性能，進(jìn)行了一些實(shí)驗(yàn)，塊大小為16×16，仿真的視頻序列采用3種不同運(yùn)動(dòng)形式的foreman，carphone和 highway，分別取 100 幀，均為 QCIF格式。

下面為部分配置語言：

#define XX 144

#define YY 176

#define OPEN_FILE “E：\視頻信號(hào)處理 \test1_dec.yuv”

#define REF_FILE “E：\視頻信號(hào)處理\foreman_qcif.yuv”

#define BLOCK_HEIGTH 16

#define BLOCK_WIDTH 16

#define MAX_MOTION 16

const int SEARCH_RANGE=MAX_MOTION*2+1；

const int X=XX/BLOCK_HEIGTH；

const int Y=YY/BLOCK_WIDTH；

在上述定義中，規(guī)定了輸入序列的格式、塊的寬度和高度以及搜索的范圍，其中，OPEN_FILE是用H.264標(biāo)準(zhǔn)測試軟件JM12.4編碼時(shí)產(chǎn)生的重建序列，REF_FILE為原始序列。

仿真結(jié)果如表1所示，其中COST代表平均所搜點(diǎn)數(shù)，PSNR為匹配圖像與原始圖像的峰值信噪比。

表1 仿真結(jié)果

經(jīng)計(jì)算，本文算法的平均搜索點(diǎn)數(shù)約為FS的1/86，并比DS與HS少搜索1個(gè)點(diǎn)左右，僅比BBGDS多搜索1個(gè)點(diǎn)左右；同時(shí)平均峰值信噪比要比DS高出約0.02 dB，比HS高出約0.11 dB，僅比BBGDS低約0.02 dB。這些結(jié)果表明本文算法在降低平均搜索點(diǎn)數(shù)，從而降低計(jì)算復(fù)雜度方面取得了良好的效果，同時(shí)能夠保證較好的率失真性能。

在Matlab中分別畫出3種輸入視頻序列foreman，carphone和 highway在 DS，HS，BBGGS以及本文算法 4種快速算法下的結(jié)果，如圖3～5所示。可見，本文算法在搜索點(diǎn)數(shù)和PSNR兩方面都要要優(yōu)于DS算法和HS算法，并在圖像質(zhì)量上與BBGDS算法相當(dāng)。

圖3 foreman序列實(shí)驗(yàn)結(jié)果

圖4 carphone序列實(shí)驗(yàn)結(jié)果

圖5 highway序列實(shí)驗(yàn)結(jié)果

5 小結(jié)

針對(duì)減少運(yùn)動(dòng)搜索算法的計(jì)算復(fù)雜度，筆者提出了一種混合搜索算法，仿真結(jié)果表明，對(duì)于各種不同運(yùn)動(dòng)特征的輸入視頻序列，本文算法均取得了良好的效果，與FS相比，極大地減少了運(yùn)動(dòng)搜索點(diǎn)數(shù)，提高了編碼效率，并優(yōu)于現(xiàn)有的優(yōu)秀算法DS和HS，且在保持率失真性能上和BBGDS相當(dāng)。也就是說本文算法在減低計(jì)算復(fù)雜度以及保證運(yùn)動(dòng)搜索的準(zhǔn)確性方面具有一定的貢獻(xiàn)。

當(dāng)然在一些編碼性能要求更高的場合以及惡劣的無線信道，如何進(jìn)一步降低計(jì)算復(fù)雜度，提高編碼效率，保持較好的編碼質(zhì)量，尚需以后進(jìn)一步研究。

[1]JVT of ISO/IEC MPEG and ITU-T VCEG.ITU-T Rec.H.264|ISO/IEC 14496-10 AVC.Draft ITU-T recommendation and final draft international standard of joint video specification[S].2005.

[2]WIEGAND T，SULLIVAN G J，BJONTEGAARD G，et al.Overview of the H.264/AVC video coding standard[J].IEEE Trans.CSVT，2003，13（7）：560-576.

[3]RICHARDSON I E G.H.264 and MPEG-4 video compression[M].New York：John Wiley&Sons Ltd.，2003：85-97.

[4]SHEN Li-quan，LIU Zhi，ZHANG Zhao-yang，et al.Fast inter mode decision using spatial property of motion field[J].IEEE Trans.Multim，2008，10（6）：1208-1214.

[5]陸大偉，張正華，海愛成.基于H.264的P幀模式選擇算法優(yōu)化[J].揚(yáng)州大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，12（3）：43-46.

[6]ZHANG Zheng-hua，HU Zhen，HAIAi-cheng，et al.Performance study of error resilience with multiple reference frames in H.264/AVC in conditions of low Bit-rate[J].Proc.9th International Conference on Electronic Measurement&Instruments：Vol.3.Beijing：IEEE Press，2009：298-301.

[7]桑亞林，張正華，陸大偉.低碼率無線視頻傳輸中的幀內(nèi)刷新技術(shù)[J].揚(yáng)州大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，11（3）：35-39.

[8]ZHU S，MA K K.A new diamond search algorithm for fast block matching motion estimation.IEEE Trans.Image Processing，2000，9（2）：287-290.

[9]TOURAPISA M，SHEN G，LIOU M L，et al.A new predictive diamond search algorithm for block based motion estimation[C]//Proceedings of SPIE Vol.4067.[S.l.]：SPIE Press，2000：1365-1373.

[10]LIU L K，F(xiàn)EIG E.A block-based gradient descent search algorithm for block motion estimation in video coding[J].IEEE Trans.CASYT，1996，6（4）：419-422.