《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 嵌入式技術(shù) > 設(shè)計(jì)應(yīng)用 > 基于H.264的運(yùn)動估計(jì)搜索算法的改進(jìn)
基于H.264的運(yùn)動估計(jì)搜索算法的改進(jìn)
電子技術(shù)應(yīng)用第02期
林 永， 楊印根， 楊 柳， 許大姐
江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院， 江西 南昌330022
摘要： 針對UMHexagonS算法的運(yùn)算量大、耗時長、復(fù)雜度較高等問題，提出了改進(jìn)方案，采用混合時空域起點(diǎn)預(yù)測，提高起始點(diǎn)的預(yù)測精度；為搜索模塊設(shè)定閾值，提前終止搜索；在整個搜索過程中，提出了一種搜索模塊象限區(qū)域分割法，有效地減少了搜索點(diǎn)數(shù)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法在保證信噪比和控制誤碼率的情況下，比原算法減少了14%~38%的運(yùn)動估計(jì)時間。
中圖分類號: TP391.41
文獻(xiàn)標(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]，運(yùn)動估計(jì)是視頻壓縮編碼中的一個關(guān)鍵部分。在H.264整個編碼過程中，運(yùn)動估計(jì)在編碼時間中占據(jù)了相當(dāng)大的比例,因此，縮短運(yùn)動估計(jì)時間是一個非常重要的環(huán)節(jié)。為了減少運(yùn)動估計(jì)的時間，近年來國內(nèi)外學(xué)者針對運(yùn)動估計(jì)提出了很多經(jīng)典的搜索算法,如全局搜索算法（FS）、三步搜索算法（TSS）、新三步搜索算法（NTSS）、四步搜索算法（FSS）、菱形搜索算法（DS）、六邊形搜索算法（HS）、非對稱十字型多層次六邊形搜索算法(UMHexagonS)[2-3]。其中，UMHexagonS算法結(jié)合了其他算法的部分優(yōu)點(diǎn)，在保證較好的率失真性能情況下，與FS算法比較，節(jié)省了90%以上的運(yùn)算量。雖然如此，但對該算法的分析發(fā)現(xiàn)，UMHexagonS還存在一些不足，搜索點(diǎn)數(shù)較多，搜索范圍較大，運(yùn)算復(fù)雜度高，增長了編碼時間，影響了編碼效率。為了解決以上問題，本文提出了以下改進(jìn)方案：

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


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

 


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

圖3 改進(jìn)后的搜索模塊


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

圖4 UMHexagonS算法改進(jìn)流程圖


3 仿真實(shí)驗(yàn)結(jié)果與分析
3.1 仿真實(shí)驗(yàn)平臺與配置
　　為了測試改進(jìn)后的算法，本文在VC++6.0的平臺上，將H.264標(biāo)準(zhǔn)測試JM10.2[7]集成到平臺上進(jìn)行了算法改進(jìn)后的測試。實(shí)驗(yàn)所用PC機(jī)的硬件配置如下：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 實(shí)驗(yàn)結(jié)果與分析
    算法改進(jìn)前、后仿真實(shí)驗(yàn)數(shù)據(jù)對照如表1所示。
    算法改進(jìn)前、后實(shí)驗(yàn)數(shù)據(jù)對比及變化如表2所示。


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