一種基于UMHexagonS的運動估計優化算法

郭少校, 譚 兮, 宗 亮

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

H.264/AVC[1]是由ITU-T和ISO/IEC聯合提出的新一代視頻編解碼標準，其高效的編碼性能和良好的網絡親和性，使其成為近年來視頻編解碼技術研究的熱點之一。

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

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

本文對UMHexagonS算法做出了三點改進：在起始點預測之后進行一次零運動塊判決；改進5*5螺旋搜索，減少搜索點數；根據運動矢量的方向性優化多層次六邊形搜索。

一 UMHexagonS算法分析

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

(一) 起始搜索點預測

由于物體運動的連續性，運動矢量在空域(相鄰塊之間)和時域(相鄰圖像或參考幀之間)都表現出極強的相關性。UMHexagonS 采用4種有效的運動矢量預測模式：中值預測(Median Prediction) ，上層塊預測(Uplayer Prediction)，相應位置塊預測(Corresponding-block Prediction)，相鄰參考圖像預測(Neighboring Reference-picture Prediction)。

(二) 非對稱十字型搜索

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

圖1 UMHexagon算法示意圖

(三) 5*5方形全搜索

以上一步得到的最小開銷點為中心，構造5*5的方形區域，如圖1中黑色圓點所構成的區域，并做全搜索。

(四) 多層次六邊形搜索

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

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

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

二 基于UMHexagonS的優化方法

根據UMHexagonS算法的特點，本文在三個方面做出了優化，包括：提前引入零運動塊判決；改進的5*5方形全搜索；優化的多層次六邊形格點搜索。

(一)提前引入零運動塊判決

本步驟改進的依據是現實中的大部分視頻序列都具有靜止或變化緩慢的背景。

在原UMHexagonS算法中，首先要根據塊大小Bsize[blocktype]，預測絕對誤差和Pred_SAD, AlphaSec[blocktype]和AlphaThird[blocktype]來計算調整因子β的值：

-AlphaSec[blocktype]

(3-1)

-AlphaThird[blocktype]

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

由于求調整因子β需要進行浮點數運算，占用系統內存開銷比較大；同時對于具有靜止或變化緩慢的背景的視頻序列，預測的起始點已經足夠精確，而在經過如此繁瑣的計算之后才進行判決，浪費了大量的計算時間。

針對這點不足，我們在計算β之前加入零運動塊判決，取固定閾值[8]T=512，如果當前塊和參考幀中預測塊的SAD值小于512，則預測運動矢量即為整像素搜索的最終結果，同時返回最小開銷。

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

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

圖2 改進后的搜索模板

(三)優化多層次六邊形格點搜索

在多層次六邊形格點搜索這一步驟，原算法依次搜索4個六邊形的16個點，并未考慮實際視頻序列中物體運動的方向性。本文把原六邊形的16個點劃分為4個區域，如圖1中所示：

FIRSTQUARTER

SECONDQUARTER

THIRDQUARTER

FOURTHQUARTER。

每個區域5個點(部分點同時劃分到兩個區域)，根據預測運動矢量和參考幀中相同位置塊的運動矢量，預測出物體的運動趨勢，來判斷搜索哪一區域的點。

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

采用本文優化過的六邊形格點搜索，在搜索每個六邊形時，減少了原來2/3的搜索點數。由于預測出了物體的大致運動趨勢，保證了搜索區域所得到的最小開銷點是全局最優的，這樣也就保持了良好的率失真性能，PSNR幾乎沒有下降。

圖3 優化的多層次六邊形搜索步驟

三 仿真及實驗結果

本文采用H.264/AVC的標準測試代碼JM86，編碼配置參數如下： IntraPeriod=0， FrameSkip=1，NumberBFrames=1，FrameToBeEncoded=0，FrameRate=30,SearchRange=16，NumberReferenceFrames=10，編碼序列IP…P。PC機配置如下：Inter(R) Core(TM) i3，2.53GHz，2G內存，Window7操作系統。對5個QCIF格式的標準序列進行測試：具有復雜運動的序列mobile、coastguard和foreman；簡單頭肩運動序列akiyo和salesman。

表1 原算法、FS以及優化算法的碼率與運動估計時間比較

表2 原算法、FS以及優化算法的信噪比比較

表1是對改進算法前后碼率、運動估計時間的比較。通過對比可以發現，改進后的算法在保持碼率幾乎不變的情況下，有效節省運動估計時間。對復雜運動序列，可節省運動估計時間達16%，對簡單運動序列，可節省運動估計時間20%以上。表2是對改進算法前后的信噪比所做的比較。對比發現，改進后算法對視頻序列的信噪比影響較小，有效保持了原有視頻的質量。

綜合以上結果，可發現本文優化后的算法在保證視頻質量和碼率穩定的前提下，可有效減少運動估計時間。

四 結論

本文通過對H.264/AVC中UMHexagon算法的分析與研究，從三個方面提出了改進或優化方法，通過實驗對比可以發現，對各種不同運動情況的視頻序列，改進后的算法均可在保持信噪比和碼率幾乎不變的情況下，有效減少運動估計時間，從而提高H.264/AVC編碼器的性能。

注釋：

①此處節省率是優化算法相對于FS的節省百分比。

②此處改善率是優化算法相對于原始算法改善百分比。

參考文獻：

[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.