基于H.264的一種混合運動搜索算法

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

（揚州大學 信息工程學院，江蘇 揚州 225009）

1 引言

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

2 塊匹配準則

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

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

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

3 混合運動搜索算法

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

圖1 3種搜索窗口

其中，矩形窗口，由3×3的點陣構成，適用于各種視頻序列的初步搜索；大菱形窗口，它由外圍的8個點加上中心的1個點構成，適用于一般運動的視頻序列的進一步搜索；小六邊形窗口，它由外圍的4個點加上中心的1個點構成，適用于運動劇烈的視頻序列的精確搜索。

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

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

2）以上一步最佳匹配點為中心構造一個大菱形窗口，檢測其9個點，若最佳匹配點位于中心，則進行下一步，否則重復這一步；

3）以小六邊形窗口為搜索模板，檢測外圍的4個點，得到最佳目標運動矢量。

算法示意圖如圖2所示。

圖2 混合搜索算法

4 實驗結果與分析

為了驗證所提算法的性能，進行了一些實驗，塊大小為16×16，仿真的視頻序列采用3種不同運動形式的foreman，carphone和 highway，分別取 100 幀，均為 QCIF格式。

下面為部分配置語言：

#define XX 144

#define YY 176

#define OPEN_FILE “E：\視頻信號處理 \test1_dec.yuv”

#define REF_FILE “E：\視頻信號處理\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；

在上述定義中，規定了輸入序列的格式、塊的寬度和高度以及搜索的范圍，其中，OPEN_FILE是用H.264標準測試軟件JM12.4編碼時產生的重建序列，REF_FILE為原始序列。

仿真結果如表1所示，其中COST代表平均所搜點數，PSNR為匹配圖像與原始圖像的峰值信噪比。

表1 仿真結果

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

在Matlab中分別畫出3種輸入視頻序列foreman，carphone和 highway在 DS，HS，BBGGS以及本文算法 4種快速算法下的結果，如圖3～5所示。可見，本文算法在搜索點數和PSNR兩方面都要要優于DS算法和HS算法，并在圖像質量上與BBGDS算法相當。

圖3 foreman序列實驗結果

圖4 carphone序列實驗結果

圖5 highway序列實驗結果

5 小結

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

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

[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幀模式選擇算法優化[J].揚州大學學報：自然科學版，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]桑亞林，張正華，陸大偉.低碼率無線視頻傳輸中的幀內刷新技術[J].揚州大學學報：自然科學版，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，FEIG E.A block-based gradient descent search algorithm for block motion estimation in video coding[J].IEEE Trans.CASYT，1996，6（4）：419-422.