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

　　(1)設(shè)定閾值，在搜索過程中SAD值達(dá)到滿意的情況下提前終止搜索。
　　(2)采用高精度的起始點(diǎn)預(yù)測(cè)，得到起始點(diǎn)的最佳預(yù)測(cè)運(yùn)動(dòng)矢量。
　　(3)采用搜索模塊象限區(qū)域分割法，在原算法的基礎(chǔ)上減少了一半以上的搜索點(diǎn)數(shù)。
1 UMHexagonS算法介紹
    (1)起始搜索點(diǎn)的預(yù)測(cè)：利用高精度的起始點(diǎn)預(yù)測(cè)，計(jì)算得出預(yù)測(cè)運(yùn)動(dòng)矢量MVpred。
　　(2)非對(duì)稱十字型模板搜索，如圖1(a)所示。
　　(3)螺旋模板搜索，以步驟(2)搜索的匹配點(diǎn)作為搜索中心，搜索坐標(biāo)[-2,2]正方形區(qū)域內(nèi)的25個(gè)候選點(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ù)測(cè)
　    起始搜索點(diǎn)的預(yù)測(cè)包括空間域預(yù)測(cè)方式和時(shí)間域兩種預(yù)測(cè)方式。其中空間域預(yù)測(cè)方式包括運(yùn)動(dòng)矢量中值預(yù)測(cè)MP和上層塊模式運(yùn)動(dòng)矢量預(yù)測(cè)UP;時(shí)間域預(yù)測(cè)方式包括前幀對(duì)應(yīng)塊運(yùn)動(dòng)矢量預(yù)測(cè)CP和時(shí)間域的鄰近參考幀運(yùn)動(dòng)矢量預(yù)測(cè)NRP。根據(jù)運(yùn)動(dòng)矢量中心偏移特性[4]，原點(diǎn)也被設(shè)為一個(gè)候選點(diǎn)預(yù)測(cè)，稱為原點(diǎn)預(yù)測(cè)ZP。在基于塊匹配算法的運(yùn)動(dòng)估計(jì)中，宏塊分為7種塊模式，即16×16、16×8、8×16、8×8、8×4、4×8及4×4。由于同種預(yù)測(cè)方法針對(duì)不同的宏塊，起始點(diǎn)的預(yù)測(cè)精度不一樣，因此本文結(jié)合MP、UP、CP、NRP這四種方式采用了一種混合時(shí)空域預(yù)測(cè)方式[5]進(jìn)行起始點(diǎn)的預(yù)測(cè)， 針對(duì)不同的宏塊模式采用不同的預(yù)測(cè)方式， 可使起始點(diǎn)的預(yù)測(cè)精度更高。

 


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

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


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


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