一種基于UMHexagonS的運(yùn)動(dòng)估計(jì)優(yōu)化算法

郭少校, 譚 兮, 宗 亮

(1. 湖南工業(yè)大學(xué) 電氣與信息工程學(xué)院，湖南 株洲 412000；2. 湖南人文科技學(xué)院 通信與控制工程系，湖南 婁底 417000)

H.264/AVC[1]是由ITU-T和ISO/IEC聯(lián)合提出的新一代視頻編解碼標(biāo)準(zhǔn)，其高效的編碼性能和良好的網(wǎng)絡(luò)親和性，使其成為近年來視頻編解碼技術(shù)研究的熱點(diǎn)之一。

由于視頻序列中存在較大的冗余，消除這些冗余信息的一項(xiàng)重要技術(shù)就是運(yùn)動(dòng)估計(jì)與補(bǔ)償。H.264/AVC采用基于塊匹配(Block Matching Algorithm)的運(yùn)動(dòng)估計(jì)算法，在參考幀的搜索窗口內(nèi)按照一定的匹配準(zhǔn)則(如SAD)搜索最佳匹配塊，該匹配塊與當(dāng)前塊之間的位移為運(yùn)動(dòng)矢量，它們的差值為殘差。運(yùn)動(dòng)估計(jì)與補(bǔ)償越精確，最終得到的殘差值越小，最終需要編碼的比特?cái)?shù)就越少。

在基于塊匹配的運(yùn)動(dòng)估計(jì)算法中，全搜索算法(Full Search)的搜索精度最高，能夠找到全局最優(yōu)點(diǎn)，但是計(jì)算量太大，其運(yùn)動(dòng)估計(jì)部分占整個(gè)編碼運(yùn)算量的60%-80%，不適宜在實(shí)際中采用。為此，各國(guó)的學(xué)者們又提出了一些快速算法，這些快速算法的整體思想就是減少搜索點(diǎn)數(shù)，控制搜索步驟，如三步法[2](TSS)、四步法[3](FSS)、新三步法[4](NTSS)、菱形搜索法[5](DS)、六邊形搜索法[6](HEXBS)等等，但是這些算法在某種程度上易陷入局部最優(yōu)。非對(duì)稱十字型多層次六邊形格點(diǎn)搜索算法(UMHexagonS)[7]是一種優(yōu)秀的快速運(yùn)動(dòng)估計(jì)算法，已被H.264/AVC標(biāo)準(zhǔn)所采納。該算法在保持良好的率失真性能的前提下，相對(duì)于FS可節(jié)約70%左右的運(yùn)算量。

本文對(duì)UMHexagonS算法做出了三點(diǎn)改進(jìn)：在起始點(diǎn)預(yù)測(cè)之后進(jìn)行一次零運(yùn)動(dòng)塊判決；改進(jìn)5*5螺旋搜索，減少搜索點(diǎn)數(shù)；根據(jù)運(yùn)動(dòng)矢量的方向性優(yōu)化多層次六邊形搜索。

一 UMHexagonS算法分析

UMHexagonS算法的重要特性就是它的精確的起始點(diǎn)預(yù)測(cè)以及提前終止判決(Early Termination)。它是一種混合的搜索方法，主要步驟如下：

(一) 起始搜索點(diǎn)預(yù)測(cè)

由于物體運(yùn)動(dòng)的連續(xù)性，運(yùn)動(dòng)矢量在空域(相鄰塊之間)和時(shí)域(相鄰圖像或參考幀之間)都表現(xiàn)出極強(qiáng)的相關(guān)性。UMHexagonS 采用4種有效的運(yùn)動(dòng)矢量預(yù)測(cè)模式：中值預(yù)測(cè)(Median Prediction) ，上層塊預(yù)測(cè)(Uplayer Prediction)，相應(yīng)位置塊預(yù)測(cè)(Corresponding-block Prediction)，相鄰參考圖像預(yù)測(cè)(Neighboring Reference-picture Prediction)。

(二) 非對(duì)稱十字型搜索

由于自然圖像序列中，通常情況下物體做水平運(yùn)動(dòng)的比重要大于做垂直運(yùn)動(dòng)的比重，所以在水平方向取search_range個(gè)點(diǎn)，垂直方向上取search_range/2個(gè)點(diǎn)，如圖1中下三角組成的十字模板所示。搜索所得的最小開銷點(diǎn)，做為下一步的搜索中心。

圖1 UMHexagon算法示意圖

(三) 5*5方形全搜索

以上一步得到的最小開銷點(diǎn)為中心，構(gòu)造5*5的方形區(qū)域，如圖1中黑色圓點(diǎn)所構(gòu)成的區(qū)域，并做全搜索。

(四) 多層次六邊形搜索

以上一步所得的最小開銷點(diǎn)為中心，構(gòu)造由16個(gè)點(diǎn)構(gòu)成的六邊形模板，由內(nèi)到外依次擴(kuò)展(1到search_range/4)，如圖1中小方形點(diǎn)組成六邊形所示。

(五) 擴(kuò)展的六邊形搜索和菱形搜索

執(zhí)行六邊形和菱形搜索，搜索模板如圖1中由上三角組成的六邊形以及由黑色的方形點(diǎn)組成的菱形所示。

二 基于UMHexagonS的優(yōu)化方法

根據(jù)UMHexagonS算法的特點(diǎn)，本文在三個(gè)方面做出了優(yōu)化，包括：提前引入零運(yùn)動(dòng)塊判決；改進(jìn)的5*5方形全搜索；優(yōu)化的多層次六邊形格點(diǎn)搜索。

(一)提前引入零運(yùn)動(dòng)塊判決

本步驟改進(jìn)的依據(jù)是現(xiàn)實(shí)中的大部分視頻序列都具有靜止或變化緩慢的背景。

在原UMHexagonS算法中，首先要根據(jù)塊大小Bsize[blocktype]，預(yù)測(cè)絕對(duì)誤差和Pred_SAD, AlphaSec[blocktype]和AlphaThird[blocktype]來計(jì)算調(diào)整因子β的值：

-AlphaSec[blocktype]

(3-1)

-AlphaThird[blocktype]

然后計(jì)算預(yù)測(cè)點(diǎn)的mcost和SAD值，并和最小開銷min_mcost比較，取最小值，更新最佳預(yù)測(cè)位置；接著又做了一個(gè)菱形搜索，尋找最小開銷點(diǎn)；然后根據(jù)其它條件做判斷，最后由Early Termination判斷是否要跳轉(zhuǎn)到擴(kuò)展的六邊形搜索，或者小菱形搜索，或是非對(duì)稱十字搜索和多層次六邊形搜索。

由于求調(diào)整因子β需要進(jìn)行浮點(diǎn)數(shù)運(yùn)算，占用系統(tǒng)內(nèi)存開銷比較大；同時(shí)對(duì)于具有靜止或變化緩慢的背景的視頻序列，預(yù)測(cè)的起始點(diǎn)已經(jīng)足夠精確，而在經(jīng)過如此繁瑣的計(jì)算之后才進(jìn)行判決，浪費(fèi)了大量的計(jì)算時(shí)間。

針對(duì)這點(diǎn)不足，我們?cè)谟?jì)算β之前加入零運(yùn)動(dòng)塊判決，取固定閾值[8]T=512，如果當(dāng)前塊和參考幀中預(yù)測(cè)塊的SAD值小于512，則預(yù)測(cè)運(yùn)動(dòng)矢量即為整像素搜索的最終結(jié)果，同時(shí)返回最小開銷。

(二)改進(jìn)的5*5方形全搜索

原UMHexagonS算法在做完非對(duì)稱十字形搜索之后，以其所得到的具有最小開銷的點(diǎn)為中心，構(gòu)造一個(gè)5*5的方形模板(如圖1中黑色圓點(diǎn)組成的搜索區(qū)域所示)，執(zhí)行螺旋形的全搜索，共需搜索24個(gè)點(diǎn)。

圖2 改進(jìn)后的搜索模板

(三)優(yōu)化多層次六邊形格點(diǎn)搜索

在多層次六邊形格點(diǎn)搜索這一步驟，原算法依次搜索4個(gè)六邊形的16個(gè)點(diǎn)，并未考慮實(shí)際視頻序列中物體運(yùn)動(dòng)的方向性。本文把原六邊形的16個(gè)點(diǎn)劃分為4個(gè)區(qū)域，如圖1中所示：

FIRSTQUARTER

SECONDQUARTER

THIRDQUARTER

FOURTHQUARTER。

每個(gè)區(qū)域5個(gè)點(diǎn)(部分點(diǎn)同時(shí)劃分到兩個(gè)區(qū)域)，根據(jù)預(yù)測(cè)運(yùn)動(dòng)矢量和參考幀中相同位置塊的運(yùn)動(dòng)矢量，預(yù)測(cè)出物體的運(yùn)動(dòng)趨勢(shì)，來判斷搜索哪一區(qū)域的點(diǎn)。

由于多層次六邊形搜索是在5*5方形搜索之后，假設(shè)5*5方形搜索得到的運(yùn)動(dòng)矢量為MVpred=(MVpred_x,MVpred_y)，參考幀中相應(yīng)塊的運(yùn)動(dòng)矢量為MVref=(MVref_x,MVref_y)，搜索流程如圖3所示。

采用本文優(yōu)化過的六邊形格點(diǎn)搜索，在搜索每個(gè)六邊形時(shí)，減少了原來2/3的搜索點(diǎn)數(shù)。由于預(yù)測(cè)出了物體的大致運(yùn)動(dòng)趨勢(shì)，保證了搜索區(qū)域所得到的最小開銷點(diǎn)是全局最優(yōu)的，這樣也就保持了良好的率失真性能，PSNR幾乎沒有下降。

圖3 優(yōu)化的多層次六邊形搜索步驟

三 仿真及實(shí)驗(yàn)結(jié)果

本文采用H.264/AVC的標(biāo)準(zhǔn)測(cè)試代碼JM86，編碼配置參數(shù)如下： IntraPeriod=0， FrameSkip=1，NumberBFrames=1，F(xiàn)rameToBeEncoded=0，F(xiàn)rameRate=30,SearchRange=16，NumberReferenceFrames=10，編碼序列IP…P。PC機(jī)配置如下：Inter(R) Core(TM) i3，2.53GHz，2G內(nèi)存，Window7操作系統(tǒng)。對(duì)5個(gè)QCIF格式的標(biāo)準(zhǔn)序列進(jìn)行測(cè)試：具有復(fù)雜運(yùn)動(dòng)的序列mobile、coastguard和foreman；簡(jiǎn)單頭肩運(yùn)動(dòng)序列akiyo和salesman。

表1 原算法、FS以及優(yōu)化算法的碼率與運(yùn)動(dòng)估計(jì)時(shí)間比較

表2 原算法、FS以及優(yōu)化算法的信噪比比較

表1是對(duì)改進(jìn)算法前后碼率、運(yùn)動(dòng)估計(jì)時(shí)間的比較。通過對(duì)比可以發(fā)現(xiàn)，改進(jìn)后的算法在保持碼率幾乎不變的情況下，有效節(jié)省運(yùn)動(dòng)估計(jì)時(shí)間。對(duì)復(fù)雜運(yùn)動(dòng)序列，可節(jié)省運(yùn)動(dòng)估計(jì)時(shí)間達(dá)16%，對(duì)簡(jiǎn)單運(yùn)動(dòng)序列，可節(jié)省運(yùn)動(dòng)估計(jì)時(shí)間20%以上。表2是對(duì)改進(jìn)算法前后的信噪比所做的比較。對(duì)比發(fā)現(xiàn)，改進(jìn)后算法對(duì)視頻序列的信噪比影響較小，有效保持了原有視頻的質(zhì)量。

綜合以上結(jié)果，可發(fā)現(xiàn)本文優(yōu)化后的算法在保證視頻質(zhì)量和碼率穩(wěn)定的前提下，可有效減少運(yùn)動(dòng)估計(jì)時(shí)間。

四 結(jié)論

本文通過對(duì)H.264/AVC中UMHexagon算法的分析與研究，從三個(gè)方面提出了改進(jìn)或優(yōu)化方法，通過實(shí)驗(yàn)對(duì)比可以發(fā)現(xiàn)，對(duì)各種不同運(yùn)動(dòng)情況的視頻序列，改進(jìn)后的算法均可在保持信噪比和碼率幾乎不變的情況下，有效減少運(yùn)動(dòng)估計(jì)時(shí)間，從而提高H.264/AVC編碼器的性能。

注釋：

①此處節(jié)省率是優(yōu)化算法相對(duì)于FS的節(jié)省百分比。

②此處改善率是優(yōu)化算法相對(duì)于原始算法改善百分比。

參考文獻(xiàn)：

[1]Draft ITU-T recommendation and final draft of Video Specification (ITU-T Rec. h.264|ISO/IEC 14496-10 AVC)[S]. JVT-G050rl.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Geneva, Mar.2003.

[2]Zhibo Chen, Jianfeng Xu, Yun He, et al. Fast integer-pel and fractional-pel motion estimation for H.264/AVC [J]. Vis.Commun.Image R, 2006(17):264-290.

[3]KOGA T, IINUMA K, HIRANO A, et al. Motion-compensated inter frame coding for video conferencing[M]. IEEE 1981 National Telecommunications Conference, Innovative Telecommunications-Key to the Future, 1981:531-535.

[4]PO L M, MA W C. A novel four-step search algorithm for fast block motion estimation [J]. IEEE Trans on Circuits and System for Video Technology, 1996, 6(2):313-317.

[5]LI R X, ZENG B, LIOU M L. A new three-step search algorithm for block motion estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1994, 4(4):438-442.

[6]ZHU S, MA K K. A new diamond search algorithm for fast block matching motion estimation [J]. IEEE Trans-Image Processing, 2000, 9(2):287-290.

[7]ZHU C, LIN X, CHAU L, et al. Hexagon-based search pattern for fast block motion estimation [J]. IEEE Trans on Circuits and System for Video Technology, 2002, 9(11):349-355.

[8]YAO N, MA K K. Adaptive rood pattern search for fast block-matching motion estimation [J]. IEEE Trans on Circuits and System for Video Technology, 2002, 11(12):1442-1449.