張 凡， 唐作其， 張正平

(貴州大學 計算機科學與信息學院，貴州 貴陽 550025)

0 引言

H.264使用更加高效和精確的運動估計技術,但是其相當高的運算復雜度使其難以實現(xiàn)實時編碼的要求[1]。

運動估計是視頻編解碼的一個關鍵技術，其所耗費的代價占據(jù)了整個編碼過程中相當大的比重。諸多新的快速算法被提出來，有新三步法、四步法[2]、六邊形搜索[3]、鉆石搜索[4]。但是這些算法容易掉入局部最優(yōu)，故而也需要進一步的改進，在這些算法的基礎上,很多學者進行了進一步的優(yōu)化[5-6]。

H.264官方測試軟件JM采用了“非對稱十字型多層次六邊形格點搜索”(UMHexagonS)算法。相比于全搜索（FS，F(xiàn)ull Search）算法，該算法在保持較好的率失真性能的同時，可以節(jié)約90%以上的運算量，展現(xiàn)了良好的編碼效果，但是在進行搜索匹配的過程中仍然會偶爾落入局部最優(yōu)。改進后的優(yōu)化算法使用了動態(tài)搜索窗口，多層次六邊形提前終止策略，在碼率和圖象質量幾乎沒有改變的同時，一定程度上節(jié)省了運動估計時間，使編碼器的實時性得到了提高。

1 UMHexagonS算法介紹

如圖1所示，UMHexagonS算法步驟如下：①起始點預測；②非對稱十字的區(qū)域搜索；③5 5×的正方形全搜索；④多層次六邊形搜索；⑤小六邊形搜索；⑥小區(qū)域十字搜索。

并且，該算法在某些搜索步驟根據(jù)一定的判斷條件來調整搜索流程甚至提前終止算法。其搜索窗口的大小通過配置文件由參數(shù)search_range設置：

H.264標準中有7種分塊方法，最大塊為16 16×，最小塊為44×。7種不同大小的塊都在固定大小的參考窗口中搜索是不科學的，比如對44×塊會增加額外的搜索，而對16 16×的大塊可能由于運動比較劇烈而在固定大小的窗口中無法找到最佳匹配的塊，這是可以改進的一個點。其次，55×的全搜索所耗費代價太大，也是可以改進的地方。第三，在多層次六邊形搜索中，首先以search_range/4為半徑的六邊形進行搜索，然后以search_range/2進行搜索，直到搜索半徑為search_range，搜索結束。搜索需要搜索的點數(shù)為N=16×4=64，也可以進一步減少搜索點數(shù)。

圖1 UMHexgonS算法

2 優(yōu)化后的UMHexagonS算法

2.1 動態(tài)搜索窗口

對上述提到的搜索窗口的大小問題，引入動態(tài)搜索窗口[7]來解決。動態(tài)搜索窗口針對不同大小的當前塊每次動態(tài)新生成搜索窗口。由運動矢量的中值預測值（MVPmedian）和上層預測值（MVPuplayer）來計算動態(tài)搜索窗口（DSR）大小，如圖2所示。

A是固定搜索窗口大小,即input_search_range；B是動態(tài)窗口大小prpsd_DSR；C是實驗值，為fixed_part=(input_search_range)/8；D是dynamic_part，由式(3)計算。

動態(tài)搜索窗口由式(2)計算：

另外，如果當前塊是16×16，那么上層預測MVPuplayer不存在，此時搜索窗口的大小按文獻[8]的方法計算。

圖2 動態(tài)搜索窗口的計算

2.2 全搜索的優(yōu)化

六邊形搜索較全搜索算法減少了搜索點數(shù)，算法復雜度也有所降低，而信號信噪比并無很大差別，圖像質量變化不大。故而可用六邊形搜索算法代替全搜索算法，從而解決上述提出的全搜索優(yōu)化問題。

2.3 多層次六邊形搜索的優(yōu)化

對于多層次六邊形搜索，可以引入一個提前終止條件來減少搜索點數(shù)[9]。另外建立一變量pred_cost，將上一次搜索后的代價min_mcost賦值給pred_cost，下一次搜索時，如果滿足式(6)：

則跳出循環(huán)，其中percent=0.8，是經(jīng)過大量實驗后得出的經(jīng)驗值。此時min_mcost即為步驟④的最佳點。

3 實驗結果與分析

3.1 測試硬件及軟件

首先將改進算法用C語言實現(xiàn)，并將其集成到測試軟件JM中.實驗所用計算機的硬件配置如：Intel(R)Pentium(R)D CPU 3.00 GHz處理器,512 M內(nèi)存.操作系統(tǒng)為WindowsXP 2002+SP2.測試序列集為5個QCIF(176 144×)格式序列,所有序列格式都為Yuv4:2:0.編碼器配置文件選用JM10.1的基本類（encoder_baseline.cfg）。實驗中的編碼參數(shù)如：FramesToBeEncoded=100，F(xiàn)rameRate=30，Use_Hadamard=1，search_range=16，NumberReference Frames=5。其他參數(shù)為默認設置。

3.2 測試結果與分析

測試中原算法UMHexagonS用UMHS表示，優(yōu)化UMHexagonS算法后的算法用UMHS-AD表示，并且選擇5個標準測試序列用以測試，它們代表了不同特點的運動類型。實驗數(shù)據(jù)見表1、表2，從實驗結果可以看出，改進的算法UMHS-AD比原算法UMHS平均節(jié)省了8.512%的編碼時間，和15.56%的運動估計時間,并且基本保持了原有視頻質量.峰值信噪比(PSNR，Peak Signal to Noise Ratio)最大提高0.01 dB或最大下降0.02 dB。

表1 測試結果比較

表2 不同搜索算法性能比較

從表2可以看出，優(yōu)化后的算法UMHS-AD針對各種的標準測試序列均能保持較好的性能?？梢缘贸?點結論：①與FS算法比較，平均損失了0.01 dB亮度信號的PSNR，但是最大損失不大于0.02 dB;與增強預測區(qū)域搜索（EPZS，Enhanced Predictive Zonal Search）算法比較，平均損失了0.02 dB亮度信號的PSNR，最大損失不大于0.05 dB，重建視頻的質量與原有圖象質量基本持平；②與FS算法比較，比特率有了極微小的增加，平均值為2.43%，與EPZS比較，平均值為0.83%，基本保持了編碼效率；③編碼和運動估計部分的耗時有一定的下降，與FS比較，運動估計速度大概為FS的3倍左右，與EPZS比較，運動估計時間有12%左右的下降.UMHS-AD與FS和EPZS相比，在重建圖象質量和碼率變化不大的情況下，實時性有了一定的提高。

4 結語

H.264相對已有的編解碼標準能夠有效的提高編碼效率，但是其運動估計模塊的算法也變的相當復雜，使得編碼器計算量有了很大的增加。優(yōu)化算法建立在對運動估計UMHexagonS算法進行分析的基礎上，用動態(tài)自適應搜索窗口替換固定搜索窗口，用六邊形搜索代替了原算法的螺旋搜索，并且在進行多層次六邊形搜索時引入了提前終止條件，一定程度上降低了搜索點數(shù)，由實驗結果可以看出，該算法在保證圖像重建質量的基礎上，能夠有效地減少H.264運動估計模塊的時間消耗.使得編碼器的實時性有了較好的提高。

[1]WIEGAND T, SULLIVAN G J, LUTHRA A.Overview of the H.264/AVC Video Coding Standard[J].IEEE Transactions on Circuits and System for Video Technology,2003,13(07):560-576.

[2]POLAMAN C.A Novel Four Search Algorithm for Block Motion Estimation[J].IEEETransactions on Circuits and Systems for Video Technology,1996,6(03):313-317.

[3]ZHU C,LIN X,CHAU L P. Hexagon based Searh Pattern for Fast Block Motion Estimation[J]. IEEE Transactions on Circuits and System for Video Technology,2002,12(05):349-355.

[4]THAM J Y,RANGANATH S,KASSIM A A.A Novel Unrestricted Center-biased Diamond Search Algorithm for Block Motion Estimation[J]. IEEE Transactions on Circuits and System for Video Technology,1998,8(04):369-377.

[5]李白萍,陳方飛.H.264中一種新型算法的研究[J].通信技術,2009,42(12):43-45.

[6]王艷營. 基于節(jié)點交叉搜索的可變形塊匹配運動估計算法[J].通信技術,2008,41(06):314-318.

[7]XU X Z,HE Y.Modification of Dynamic Search Range for JVT[S]. USA:[s.n.],2002.

[8]CHEN Z X,SONG Y,IKENAGA T, et al.A Dynamic Search Range Algorithm for Variable Block Size Motion Estimation in H.264/AVC Information[C]. Singapore:[s.n.], 2007:1-4.

[9]鄭振東,王沛,應駿.H.264 JM模型中運動估計算法及改進方案[J].中國圖像圖形學報,2007,12(10):1798-1801.