文獻標識碼: A
文章編號： 0258-7998(2012)02-0134-04
H.264是新一代視頻壓縮編碼標準[1]，運動估計是視頻壓縮編碼中的一個關鍵部分。在H.264整個編碼過程中，運動估計在編碼時間中占據了相當大的比例,因此，縮短運動估計時間是一個非常重要的環節。為了減少運動估計的時間，近年來國內外學者針對運動估計提出了很多經典的搜索算法,如全局搜索算法（FS）、三步搜索算法（TSS）、新三步搜索算法（NTSS）、四步搜索算法（FSS）、菱形搜索算法（DS）、六邊形搜索算法（HS）、非對稱十字型多層次六邊形搜索算法(UMHexagonS)[2-3]。其中，UMHexagonS算法結合了其他算法的部分優點，在保證較好的率失真性能情況下，與FS算法比較，節省了90%以上的運算量。雖然如此，但對該算法的分析發現，UMHexagonS還存在一些不足，搜索點數較多，搜索范圍較大，運算復雜度高，增長了編碼時間，影響了編碼效率。為了解決以上問題，本文提出了以下改進方案：
(1)設定閾值，在搜索過程中SAD值達到滿意的情況下提前終止搜索。
(2)采用高精度的起始點預測，得到起始點的最佳預測運動矢量。
(3)采用搜索模塊象限區域分割法，在原算法的基礎上減少了一半以上的搜索點數。
1 UMHexagonS算法介紹
(1)起始搜索點的預測：利用高精度的起始點預測，計算得出預測運動矢量MVpred。
(2)非對稱十字型模板搜索，如圖1(a)所示。
(3)螺旋模板搜索，以步驟(2)搜索的匹配點作為搜索中心，搜索坐標[-2,2]正方形區域內的25個候選點，類似于全局搜索，如圖1(b)所示。
(4)大六邊形多層次模板搜索，如圖1(c)所示。
(5)以步驟(4)搜索的匹配點作為搜索中心，進行中小六邊形模板搜索，如圖1(d)所示。
(6)小菱形模板反復搜索，如圖1(e)所示，搜索得到最佳的匹配點。
2 UMHexagonS算法的改進方案
2.1 起始搜索點的預測
起始搜索點的預測包括空間域預測方式和時間域兩種預測方式。其中空間域預測方式包括運動矢量中值預測MP和上層塊模式運動矢量預測UP;時間域預測方式包括前幀對應塊運動矢量預測CP和時間域的鄰近參考幀運動矢量預測NRP。根據運動矢量中心偏移特性[4]，原點也被設為一個候選點預測，稱為原點預測ZP。在基于塊匹配算法的運動估計中，宏塊分為7種塊模式，即16×16、16×8、8×16、8×8、8×4、4×8及4×4。由于同種預測方法針對不同的宏塊，起始點的預測精度不一樣，因此本文結合MP、UP、CP、NRP這四種方式采用了一種混合時空域預測方式[5]進行起始點的預測， 針對不同的宏塊模式采用不同的預測方式， 可使起始點的預測精度更高。
2.2 搜索模塊象限區域分割法
由上述UMHexagonS搜索過程得知，該搜索算法在搜索過程中，搜索的候選點數較多，可以通過一些改進的方法減少搜索點數。本文采用了搜索模塊象限區域分割法，根據參考文獻[6]中得知預測運動矢量和最佳運動矢量落入某同一象限的平均概率在95%以上，準確度很高。因此，利用混合時空域起點預測方法，可找到起始點的運動矢量方向，由于起點運動矢量方向和最佳運動矢量方向所落入的象限范圍基本一致，所以在后面的搜索階段只需要在一個約定的象限區域內進行搜索，其他3/4的區域都不用搜索，這樣可以大大減少搜索點數和節省搜索時間。
如圖2所示,整個宏塊可劃分為4個象限區域，分別是A1、A2、A3、A4,如果將當前宏塊運動估計的起始點的最佳預測運動矢量記為MVpred(pred_x,pred_y)，則通過該運動向量計算得出：
(1)
由式(1)可判斷得出預測運動矢量方向落入在哪個象限內：
If: sinθ>0 && cosθ>0 MVpred∈A1
If: sinθ>0 && cosθ<0 MVpred∈A2
If: sinθ<0 && cosθ<0 MVpred∈A3
If: sinθ<0 && cosθ>0 MVpred∈A4
由圖2給出的4種不同的運動矢量所屬象限的劃分,以及式(1)和式(2)的判斷，得知對原UMHexagonS算法的非對稱十字型模板搜索、螺旋模板搜索、大六邊形模板搜索，六邊形模板搜索和菱形模板搜索進行象限區域劃分，如圖3所示。
圖3 改進后的搜索模塊
以16×16搜索范圍為例,只搜索一個象限區域，從圖3(a)可以看出，原搜索算法需要搜索24個候選點，優化改進后，搜索點數只有原搜索算法的一半，將該改進后的搜索方法記為P1。圖3(b)中，原搜索算法需要搜索25個候選點，改進模板后只需要搜索9個點，將該改進后的搜索方法記為P2。圖3(c)中，原搜索算法需要搜索64個候選點，改進后只需要搜索20個點，將該改進后的搜索方法記為P3。圖3(d)中，原搜索算法需要搜索6個候選點，改進后只需要搜索2個點，將該改進后的搜索方法記為P4。圖3(e)原搜索算法需要搜索4個候選點，改進后只需要搜索2個點，將該改進后的搜索方法記為P5。優化及改進后的各種搜索模塊平均節省了一半以上的搜索點數，因此，采用搜索模板象限區域分割法可以大大減少搜索點數。
2.3 搜索提前終止策略
提前終止搜索策略的方法是設定閾值，在保證率失真的情況下，設定合理的閾值T可以較好地節省搜索時間。在H.264標準中采用塊匹配準則方式計算搜索點的最小絕對差值和(SAD)，如果SAD值小于或等于設定的閾值T，則提前結束搜索。由于宏塊支持7種分塊模式，各種塊模式的平均SAD值各有不同，為了減少計算量，可以根據不同塊模式的需要，設定7個不同的閾值。
2.4 算法改進的具體流程
(1)首先，進行混合時空域起始搜索點的預測，判斷該起始點SAD值，如果小于閾值T，則轉入步驟(7)，否則，轉入步驟(2)。
(2)通過式(1)和式(2)計算后得到預測運動矢量方向落入所屬的象限區域，并采用P1的方法進行搜索，判斷各候選點SAD值，如果小于閾值T，則轉入步驟(7)，否則，轉入步驟(3)。
(3)以步驟(2)最小候選點為中心，在預測的象限區域內采用P2的方法進行搜索，判斷各候選點SAD值，如果小于閾值T，則轉入步驟(7)，否則，轉入步驟(4)。
(4)在預測的象限區域內采用P3的方法進行搜索，判斷各候選點SAD值，如果小于閾值T，則轉入步驟(7)，否則，轉入步驟(5)。
(5)以步驟(4)最小候選點為中心，在預測的象限區域內采用P4的方法進行反復搜索，判斷各候選點SAD值，如果小于閾值T，則轉入步驟(7)，否則，轉入步驟(6)。
(6)在預測的象限區域內采用P5的方法進行反復搜索。
(7)找到最佳匹配點，結束搜索。
算法改進后具體流程如圖4所示。
圖4 UMHexagonS算法改進流程圖
3 仿真實驗結果與分析
3.1 仿真實驗平臺與配置
為了測試改進后的算法，本文在VC++6.0的平臺上，將H.264標準測試JM10.2[7]集成到平臺上進行了算法改進后的測試。實驗所用PC機的硬件配置如下：Windows XP，CPU 2.80 GHz，內存為2 GB。選用的測試序列集為5個176×144的QCIF格式序列，所有序列都為Yuv4:2:0。采用baseline編碼，編碼器主要參數配置為FramesToBeEncoded=100，FrameRate=30.0，UseHadamard=1，SearchRange=16，NumberReferenceFrames=5,其他參數為默認值。
3.2 實驗結果與分析
算法改進前、后仿真實驗數據對照如表1所示。
算法改進前、后實驗數據對比及變化如表2所示。
從表2的實驗數據中可以發現，改進后的算法與原算法相比，PSNR值的變化不超過0.01dB，誤碼率的增加率最大不超過1.2%，然而運動估計時間卻減少了14%~38%。其中，對于運動比較緩慢的序列news和akiyo而言，搜索速度提高了14.24%和18.19%，對于中度運動foreman序列，提高了28.86%，對于劇烈運動的序列coastguard和mobile而言，提高了38.88%和38.67%。從而可以看出，改進后的算法相對于原算法，搜索速度隨運動序列劇烈強度的增加而提高。因此，本文算法在保證編碼性能的基礎上，可以大幅地減少原算法的運動估計時間，整體上提高編碼效率。
本文通過對運動估計UMHexagonS進行了分析和研究，針對該算法提出了一些改進，通過混合時空域高精度的起始點預測，引入預測運動矢量方向性判別搜索區域從而降低搜索點數，設定閾值提前終止搜索。從實驗結果可以發現，本文算法在PSNR和碼率與原算法相近的情況下，運動估計時間得到大幅降低。因此，本文的改進算法與原算法相比，具有明顯的優勢。
參考文獻
[1] WIEGAND T, SULIVAN G J, LUTHRA A. Draft ITU-Trecommendation H.264 and final draft international standard 14496-10 AVC[R]. JVT of ISO/IEC JTC1/SC29/WG11 and ITU-T SG16/Q.6,Doc.JVT G050r1, Geneva, Switzerland,May 2003.
[2] Yang Peng,He Yuwen, Yang Shiqiang. An unsymmetrical-cross multi-resolution motion search aigorithm for Mpeg4-Avcm. 264 coding[R]. IEEE International Conference on Multimedia and Expo(ICME),2004:531-534.
[3] Yang Peng, Wu Hua, Yang Shiqiang. Fast motion estimation algorithm for H.264[J]. Journal of Tsinghua University (Science and Technology),2005,45(4):527-531.
[4] 李會宗,陳雷霆,盧光輝,等.基于起點預測的不連續十字形快速搜索算法[J].計算機應用究，2008，25(10):
2929-2931.
[5] Zhou Wei, Duan Zhemin,Hu Hongqi.Fast motion estimation algorithm for H.264/AVC based on centered prediction[J].Journal of Systems Engineering and Electronics.2010,21(6):1103-1110.
[6] 李桂菊,劉剛,梁靜秋.H.264快速運動估計算法的改進[J].光學精密工程.2010,18(11):2489-2496.
[7] JVT Reference Software of H.264.http://iphome.hhi.de/suehring/tml/.