《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 嵌入式技術(shù) > 設(shè)計應(yīng)用 > 基于H.264的運動估計搜索算法的改進
基于H.264的運動估計搜索算法的改進
電子技術(shù)應(yīng)用第02期
林 永， 楊印根， 楊 柳， 許大姐
江西師范大學(xué) 計算機信息工程學(xué)院， 江西 南昌330022
摘要： 針對UMHexagonS算法的運算量大、耗時長、復(fù)雜度較高等問題，提出了改進方案，采用混合時空域起點預(yù)測，提高起始點的預(yù)測精度；為搜索模塊設(shè)定閾值，提前終止搜索；在整個搜索過程中，提出了一種搜索模塊象限區(qū)域分割法，有效地減少了搜索點數(shù)。實驗結(jié)果表明，改進后的算法在保證信噪比和控制誤碼率的情況下，比原算法減少了14%~38%的運動估計時間。
中圖分類號: TP391.41
文獻標(biāo)識碼: A
文章編號： 0258-7998(2012)02-0134-04
Improvement of motion estimation search algorithm based on H.264
Lin Yong, Yang Yin′gen, Yang Liu, Xu Dajie
College of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, China
Abstract： As UMHexagonS algorithm has the disadvantages of big computation, time consuming and high complexity, this paper proposes some schemes of improvement, which mainly includes three aspects. Firstly, use spatio-temporal initial point prediction to improve the forecast accuracy of the initial point; Secondly, set threshold for the search module to terminate search; Thirdly, put forward a search module quadrant regional segmentation method in the whole search process, effectively reducing the searching points. Through the experimental results show that the improved algorithm can in guarantee SNR and bit-error rates than the original algorithm, reduce 14%~38% of the motion estimation time.
Key words : motion estimation;UMHexagonS;spatio-temporal;quadrant segmentation;threshold

    H.264是新一代視頻壓縮編碼標(biāo)準(zhǔn)[1]，運動估計是視頻壓縮編碼中的一個關(guān)鍵部分。在H.264整個編碼過程中，運動估計在編碼時間中占據(jù)了相當(dāng)大的比例,因此，縮短運動估計時間是一個非常重要的環(huán)節(jié)。為了減少運動估計的時間，近年來國內(nèi)外學(xué)者針對運動估計提出了很多經(jīng)典的搜索算法,如全局搜索算法（FS）、三步搜索算法（TSS）、新三步搜索算法（NTSS）、四步搜索算法（FSS）、菱形搜索算法（DS）、六邊形搜索算法（HS）、非對稱十字型多層次六邊形搜索算法(UMHexagonS)[2-3]。其中，UMHexagonS算法結(jié)合了其他算法的部分優(yōu)點，在保證較好的率失真性能情況下，與FS算法比較，節(jié)省了90%以上的運算量。雖然如此，但對該算法的分析發(fā)現(xiàn)，UMHexagonS還存在一些不足，搜索點數(shù)較多，搜索范圍較大，運算復(fù)雜度高，增長了編碼時間，影響了編碼效率。為了解決以上問題，本文提出了以下改進方案：

　　(1)設(shè)定閾值，在搜索過程中SAD值達到滿意的情況下提前終止搜索。
　　(2)采用高精度的起始點預(yù)測，得到起始點的最佳預(yù)測運動矢量。
　　(3)采用搜索模塊象限區(qū)域分割法，在原算法的基礎(chǔ)上減少了一半以上的搜索點數(shù)。
1 UMHexagonS算法介紹
    (1)起始搜索點的預(yù)測：利用高精度的起始點預(yù)測，計算得出預(yù)測運動矢量MVpred。
　　(2)非對稱十字型模板搜索，如圖1(a)所示。
　　(3)螺旋模板搜索，以步驟(2)搜索的匹配點作為搜索中心，搜索坐標(biāo)[-2,2]正方形區(qū)域內(nèi)的25個候選點，類似于全局搜索，如圖1(b)所示。
　　(4)大六邊形多層次模板搜索，如圖1(c)所示。
　　(5)以步驟(4)搜索的匹配點作為搜索中心，進行中小六邊形模板搜索，如圖1(d)所示。
　　(6)小菱形模板反復(fù)搜索，如圖1(e)所示，搜索得到最佳的匹配點。


2 UMHexagonS算法的改進方案
2.1 起始搜索點的預(yù)測
　    起始搜索點的預(yù)測包括空間域預(yù)測方式和時間域兩種預(yù)測方式。其中空間域預(yù)測方式包括運動矢量中值預(yù)測MP和上層塊模式運動矢量預(yù)測UP;時間域預(yù)測方式包括前幀對應(yīng)塊運動矢量預(yù)測CP和時間域的鄰近參考幀運動矢量預(yù)測NRP。根據(jù)運動矢量中心偏移特性[4]，原點也被設(shè)為一個候選點預(yù)測，稱為原點預(yù)測ZP。在基于塊匹配算法的運動估計中，宏塊分為7種塊模式，即16×16、16×8、8×16、8×8、8×4、4×8及4×4。由于同種預(yù)測方法針對不同的宏塊，起始點的預(yù)測精度不一樣，因此本文結(jié)合MP、UP、CP、NRP這四種方式采用了一種混合時空域預(yù)測方式[5]進行起始點的預(yù)測， 針對不同的宏塊模式采用不同的預(yù)測方式， 可使起始點的預(yù)測精度更高。

 


2.2 搜索模塊象限區(qū)域分割法
　    由上述UMHexagonS搜索過程得知，該搜索算法在搜索過程中，搜索的候選點數(shù)較多，可以通過一些改進的方法減少搜索點數(shù)。本文采用了搜索模塊象限區(qū)域分割法，根據(jù)參考文獻[6]中得知預(yù)測運動矢量和最佳運動矢量落入某同一象限的平均概率在95%以上，準(zhǔn)確度很高。因此，利用混合時空域起點預(yù)測方法，可找到起始點的運動矢量方向，由于起點運動矢量方向和最佳運動矢量方向所落入的象限范圍基本一致，所以在后面的搜索階段只需要在一個約定的象限區(qū)域內(nèi)進行搜索，其他3/4的區(qū)域都不用搜索，這樣可以大大減少搜索點數(shù)和節(jié)省搜索時間。
    如圖2所示,整個宏塊可劃分為4個象限區(qū)域，分別是A1、A2、A3、A4,如果將當(dāng)前宏塊運動估計的起始點的最佳預(yù)測運動矢量記為MVpred(pred_x,pred_y)，則通過該運動向量計算得出：
                           (1)
       由式(1)可判斷得出預(yù)測運動矢量方向落入在哪個象限內(nèi)：
       If: sinθ>0 && cosθ>0   MVpred∈A1
       If: sin&theta;>0 && cos&theta;<0   MVpred&isin;A2
       If: sin&theta;<0 && cos&theta;<0   MVpred&isin;A3
       If: sin&theta;<0 && cos&theta;>0   MVpred&isin;A4
　    由圖2給出的4種不同的運動矢量所屬象限的劃分,以及式(1)和式(2)的判斷，得知對原UMHexagonS算法的非對稱十字型模板搜索、螺旋模板搜索、大六邊形模板搜索，六邊形模板搜索和菱形模板搜索進行象限區(qū)域劃分，如圖3所示。

圖3 改進后的搜索模塊


    以16&times;16搜索范圍為例,只搜索一個象限區(qū)域，從圖3(a)可以看出，原搜索算法需要搜索24個候選點，優(yōu)化改進后，搜索點數(shù)只有原搜索算法的一半，將該改進后的搜索方法記為P1。圖3(b)中，原搜索算法需要搜索25個候選點，改進模板后只需要搜索9個點，將該改進后的搜索方法記為P2。圖3(c)中，原搜索算法需要搜索64個候選點，改進后只需要搜索20個點，將該改進后的搜索方法記為P3。圖3(d)中，原搜索算法需要搜索6個候選點，改進后只需要搜索2個點，將該改進后的搜索方法記為P4。圖3(e)原搜索算法需要搜索4個候選點，改進后只需要搜索2個點，將該改進后的搜索方法記為P5。優(yōu)化及改進后的各種搜索模塊平均節(jié)省了一半以上的搜索點數(shù)，因此，采用搜索模板象限區(qū)域分割法可以大大減少搜索點數(shù)。
2.3 搜索提前終止策略
    提前終止搜索策略的方法是設(shè)定閾值，在保證率失真的情況下，設(shè)定合理的閾值T可以較好地節(jié)省搜索時間。在H.264標(biāo)準(zhǔn)中采用塊匹配準(zhǔn)則方式計算搜索點的最小絕對差值和(SAD)，如果SAD值小于或等于設(shè)定的閾值T，則提前結(jié)束搜索。由于宏塊支持7種分塊模式，各種塊模式的平均SAD值各有不同，為了減少計算量，可以根據(jù)不同塊模式的需要，設(shè)定7個不同的閾值。
2.4 算法改進的具體流程
　    (1)首先，進行混合時空域起始搜索點的預(yù)測，判斷該起始點SAD值，如果小于閾值T，則轉(zhuǎn)入步驟(7)，否則，轉(zhuǎn)入步驟(2)。
　    (2)通過式(1)和式(2)計算后得到預(yù)測運動矢量方向落入所屬的象限區(qū)域，并采用P1的方法進行搜索，判斷各候選點SAD值，如果小于閾值T，則轉(zhuǎn)入步驟(7)，否則，轉(zhuǎn)入步驟(3)。
　    (3)以步驟(2)最小候選點為中心，在預(yù)測的象限區(qū)域內(nèi)采用P2的方法進行搜索，判斷各候選點SAD值，如果小于閾值T，則轉(zhuǎn)入步驟(7)，否則，轉(zhuǎn)入步驟(4)。
　    (4)在預(yù)測的象限區(qū)域內(nèi)采用P3的方法進行搜索，判斷各候選點SAD值，如果小于閾值T，則轉(zhuǎn)入步驟(7)，否則，轉(zhuǎn)入步驟(5)。
    (5)以步驟(4)最小候選點為中心，在預(yù)測的象限區(qū)域內(nèi)采用P4的方法進行反復(fù)搜索，判斷各候選點SAD值，如果小于閾值T，則轉(zhuǎn)入步驟(7)，否則，轉(zhuǎn)入步驟(6)。
　    (6)在預(yù)測的象限區(qū)域內(nèi)采用P5的方法進行反復(fù)搜索。
　    (7)找到最佳匹配點，結(jié)束搜索。
　    算法改進后具體流程如圖4所示。

圖4 UMHexagonS算法改進流程圖


3 仿真實驗結(jié)果與分析
3.1 仿真實驗平臺與配置
　　為了測試改進后的算法，本文在VC++6.0的平臺上，將H.264標(biāo)準(zhǔn)測試JM10.2[7]集成到平臺上進行了算法改進后的測試。實驗所用PC機的硬件配置如下：Windows XP，CPU 2.80 GHz，內(nèi)存為2 GB。選用的測試序列集為5個176&times;144的QCIF格式序列，所有序列都為Yuv4:2:0。采用baseline編碼，編碼器主要參數(shù)配置為FramesToBeEncoded=100，F(xiàn)rameRate=30.0，UseHadamard=1，SearchRange=16，NumberReferenceFrames=5,其他參數(shù)為默認(rèn)值。
3.2 實驗結(jié)果與分析
    算法改進前、后仿真實驗數(shù)據(jù)對照如表1所示。
    算法改進前、后實驗數(shù)據(jù)對比及變化如表2所示。


    從表2的實驗數(shù)據(jù)中可以發(fā)現(xiàn)，改進后的算法與原算法相比，PSNR值的變化不超過0.01dB，誤碼率的增加率最大不超過1.2%，然而運動估計時間卻減少了14%~38%。其中，對于運動比較緩慢的序列news和akiyo而言，搜索速度提高了14.24%和18.19%，對于中度運動foreman序列，提高了28.86%，對于劇烈運動的序列coastguard和mobile而言，提高了38.88%和38.67%。從而可以看出，改進后的算法相對于原算法，搜索速度隨運動序列劇烈強度的增加而提高。因此，本文算法在保證編碼性能的基礎(chǔ)上，可以大幅地減少原算法的運動估計時間，整體上提高編碼效率。
    本文通過對運動估計UMHexagonS進行了分析和研究，針對該算法提出了一些改進，通過混合時空域高精度的起始點預(yù)測，引入預(yù)測運動矢量方向性判別搜索區(qū)域從而降低搜索點數(shù)，設(shè)定閾值提前終止搜索。從實驗結(jié)果可以發(fā)現(xiàn)，本文算法在PSNR和碼率與原算法相近的情況下，運動估計時間得到大幅降低。因此，本文的改進算法與原算法相比，具有明顯的優(yōu)勢。
參考文獻
[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] 李會宗,陳雷霆,盧光輝,等.基于起點預(yù)測的不連續(xù)十字形快速搜索算法[J].計算機應(yīng)用究，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].光學(xué)精密工程.2010,18(11):2489-2496.
[7] JVT Reference Software of H.264.http://iphome.hhi.de/suehring/tml/.

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。