一種基于HEVC視頻編碼的快速運動估計方法

韓從道， 許士芳

（上海應用技術學院電子與電氣工程學院，上海 201418）

一種基于HEVC視頻編碼的快速運動估計方法

韓從道， 許士芳

（上海應用技術學院電子與電氣工程學院，上海 201418）

運動估計是影響下一代視頻編碼標準高效率視頻編碼（HEVC）性能的關鍵因素，它通常利用當前幀的圖像塊在多重參考幀中對應的搜索窗口中尋找最佳匹配塊來完成的.針對HEVC編碼標準提出了一種快速的運動估計方法快速分級搜索（FHS）.首先，根據多個備用的運動矢量確定起始搜索點的位置，以起點為中心，執行搜索半徑依次擴大的三圈鉆石搜索，如果執行了內部兩圈鉆石搜索，最佳匹配點仍位于起點，則提前終止搜索.否則，根據最佳匹配點在內圈、中圈和外圈菱形邊緣的情況，提出了不同的后續搜索策略.測試結果表明，提出的快速運動估計算法相對HM14.0提供的算法，平均搜索較少的點數，同時對編碼后視頻的質量只造成輕微的損失.

運動估計；匹配塊；鉆石搜索；六邊形搜索；多重參考幀

高效率視頻編碼（HEVC）是由國際電信聯盟遠程通信標準化組織（ITU-T）和國際標準化組織（ISO）及國際電工委員會（IEC）共同組建的視頻編碼聯合協作組推出的下一代視頻編碼標準，它相對于H.264標準具有無可比擬的優勢［1］.它在數字視頻壓縮和傳輸、智能電視、高清電視領域有著良好的應用前景.在相同的視頻壓縮質量下，HEVC所產生的碼流比特率可以節約50%左右［2］，壓縮效率得到進一步提高.

運動估計在編碼過程中大概占據了一半的編碼時間和運算復雜度［3］，如何尋找快速高效的運動估計算法一直是視頻編碼領域所研究的一個熱點問題.HEVC是將每幀按編碼單元（CU）為基本單位進行編碼的，每個CU是最大尺寸64×64至最小尺寸8×8不等的方形塊.CU按照四元樹結構進行組織，并且每個CU按照預測方式劃分成不同尺寸的預測單元PU［4］.假設CU的尺寸是2N×2N，那么每個PU可能的尺寸有2N×2N、2N×N、N×2N、N ×N、2N×nU、2N×nD、n L×2N、nR×2N，其中N表示常數4、8、16、32、64.2N×2N是未劃分的PU尺寸，2N×N、N×2N、N×N是對稱劃分后的PU尺寸，2N×n U、2N×nD、n L×2N、nR×2N是非對稱劃分后的PU尺寸［5］，nU和nD是處于上、下兩個部分PU的垂直寬度，而n L和n R是處于左、右兩個部分PU的水平寬度.對于2N×2N的CU，可以沿水平方向將其分割成2N×（N／2）和2N×（3N／2）的2個PU，處于上方的PU尺寸表示為2N× n U，處于下方的PU尺寸表示為2N×n D.類似地，2N×2N的CU也可沿垂直方向將其分割成（N／2）×2N和（3N／2）×2N的2個PU，處于左、右兩邊的PU尺寸分別表示為n L×2N和nR×2N.同時，運動補償亮度塊的最小尺寸只能為8×4或4×8.

確定最優的運動矢量，HEVC繼承了H.264視頻編碼標準中的代價函數的方法.代價函數采用一個基于率失真（RD）模型的拉格朗日函數［6］，通常如下表示：

式中：J是代價函數；第1項是當前圖像塊與參考幀中匹配圖像塊之間失真，用兩個圖像塊對應位置各像素亮度差的絕對值之和來表示，記成SAD；λMOTION是拉格朗日乘法因子；當前塊候選的運動矢量MVcandidate與預測的運動矢量PMV之間的差記為MVD；函數R表示編碼MVD所需要的比特數.

最優的運動矢量對應于取得最小代價函數的運動矢量［7］，可表示為：

1 發展與現狀

圍繞提高編碼速度、降低運算復雜度的課題，很多快速的運動估計算法被提出.Pan等［7］針對HEVC中的測試區域（TZ）搜索提出了一種早期終止算法，基于使用大CU和小CU得到的不同的最佳點，分別使用鉆石搜索或六邊形搜索來早期終止TZ搜索.Yang等［8］提出了一種基于方向搜索的快速運動方法.它首先以起始點為中心，搜索其周圍8個點，如果具有最小率失真代價的點仍位于中心，則停止搜索.否則，根據處于邊緣的最優點位置方向，不斷補充新的相鄰三點，直到新產生的最優點位置不再發生改變為止.最后，在可能的水平或垂直方向軸上，尋找大位移的運動矢量，從所有可能的候選點中，找到具有最小RD值的運動矢量.

Kibeya等［3］對TZ算法進行了改進，提出了用直線鉆石模式、小鉆石模式或水平鉆石模式取代光柵掃描算法的模型.但是，這種單純的小鉆石搜索容易導致陷入局部最優的情形.Purnachand等［4］采用半徑不斷擴大的水平和垂直六邊形以及旋轉的六邊形來代替鉆石搜索方案，并采用一個自適應的閾值來提前終止搜索.但是，當最優點離起始搜索中心較遠時，最優點的位置精度會下降.

HEVC編碼軟件采用的運動估計方法是一種快速的TZ搜索，它首先從幾個候選的運動矢量中挑選一個作為搜索的起點.然后以該點為中心，進行距離每次翻倍擴大（從1到64）的多圈鉆石或正方形搜索.為了提高搜索效率，一般選取鉆石形搜索.如果經過連續三圈搜索，最優點的位置未發生變化，則退出當前的多圈搜索.如果最優點仍位于起始點，則提前結束搜索.如果最優點離起始點的距離為1，則再搜索最優點附近的兩點，然后退出.如果最優點離起始點的距離超過5，則還需進行光柵式網格搜索.以新的最優點為起點，進行精細搜索，直到最優點位置不再發生改變.這種方法對于大位移的運動矢量，由于要采用光柵網格搜索，導致搜索的點數過多，影響編碼性能.

本文在TZ快速搜索方法的基礎上，提出了一種分級搜索的策略，同時，避免了高成本的柵格搜索.首先，確定始搜索點的位置.然后，以該點為中心，執行搜索距離依次擴大的三圈鉆石搜索，如果內部兩圈鉆石搜索執行完后，最佳匹配點位于起點，則提前結束搜索.否則根據最佳匹配點在內圈、中圈和外圈菱形邊緣的情形，采用不同的后續搜索模式.

2 測試區域TZ搜索

在HEVC編碼中，采用基于測試區域TZ的搜索.它既包含了以往H.264編碼方案中常用的鉆石搜索，又有覆蓋范圍廣的光柵網狀搜索，其基本算法可分為4個部分.

2.1 起始搜索點的確定

HEVC中采用兩個候選的運動矢量.一個是預測的運動矢量，它是當前PU左邊、上方和右上方3個PU的運動矢量的中值.另一個是零運動矢量（0，0），記為MVzero，從這兩個運動矢量中選出具有最小RD代價的作為起始搜索點MVstart，那么MVstart一定是由預測的運動矢量和零運動矢量所構成的集合中的元素，如下式所示：

搜索限定在以起始坐標為（0，0）點，水平和垂直方向各為［-64，64］的區間范圍里.

預測的運動矢量通常記為pmv，而當前PU實際的運動矢量記作mv，兩者之間的差記作Δmv，運動搜索可以看成確定Δmv的過程，則

2.2 距離擴大的鉆石搜索

以起始搜索點為中心，進行搜索距離不斷翻倍（從1～64）的鉆石搜索，如圖1所示.

圖1 搜索距離為1～64的鉆石組模型Fig.1 The diamond group model with search distance from 1 to 64

從最內圈到最外圈的鉆石形的搜索距離依次為1，2，…，64，由于搜索距離為64的鉆石形過大，故最外圈鉆石形作了簡略表示.以起點為中心，由內圈往外圈依次搜索，不斷更新搜索到的最優點位置.如果經過連續3圈，最優點的位置未發生改變，表明最優點位置穩定，則退出鉆石組搜索.隨著搜索往外圈推進，各點之間的間距較大，影響搜索的精度.在最差情形下，最多搜索除起點外的64個點.

2.3 柵格搜索

如果搜索得到的最優點位于中心點，則提前結束整個搜索過程.如果最優點位于離中心距離為1的小菱形上，則補充搜索與最優點對角相鄰的兩個點，然后結束全部搜索.圖2示出了當最優點位于小鉆石上方需補充搜索的兩點情形，以空心點表示.如果上述兩種情形都沒有滿足，則將最優點離起始點的距離存入變量uiBest Distance.

圖2 當最優點位于小鉆石上方需補充搜索的兩點位置Fig.2 The location of two points which are needed to search additionally when the best point is on the top of the small diamond

如果uiBest Distance超過光柵間隔值iRaster通常設置為5），則啟動光柵掃描搜索，并將uiBestDistance的值置為iRaster.搜索在整個測試區域TZ進行.搜索從測試區域的左上角位置開始，逐行掃描，點與點之間的水平和垂直間距為iRaster.由于水平方向的區間范圍為［-64，64］，故一行需要掃描Floor［（64+64）／5］+1=26個點，搜索完整個測試區域TZ需要26×26=676個點，可見光柵掃描的運算成本很高.圖3列出了光柵掃描的示意圖.

圖3 光柵掃描示意圖Fig.3 The diagrammatic sketch of raster scan

2.4 搜索的精細化

循環執行下面的搜索，直到uiBest Distance為零，或者最優點位于最內圈的小鉆石上為止.

步驟1 以當前得到的最優點作為新的中心，執行如圖1搜索距離不斷擴大的鉆石組搜索.

步驟2 判斷是否滿足退出循環的條件.

退出上述循環后，如果最優點位于最內圈的小鉆石上，則補充搜索與最優點對角相鄰的兩點.將最后得到的最優點作為搜索得到的運動矢量，返回給主程序.可以看出，對于存在大運動幅度的視頻，運動矢量的幅值普遍較大，執行鉆石組和光柵搜索所消耗的運算量是巨大的.

3 快速分級搜索（FHS）方法

在運動估計過程中，既要提高運動搜索的速度，又要考慮到搜索得到運動矢量的精度.本文提出的快速分級搜索（FHS）方法主要分3個部分，起始搜索點的確定仍采用2.1節的方法.

3.1 精簡的鉆石組搜索

多圈鉆石組搜索會出現各圈之間距離較大以及搜索點稀疏分布的情形.在開始階段，FHS以起始點為中心，從內往外執行三圈鉆石搜索，如圖4所示.如果執行內部兩圈后，最優點位于中心點，則提前退出，整個搜索過程結束.

圖4 以起點為中心進行的三圈鉆石搜索Fig.4 Three circle diamond searches centered on the starting point

3.2 分級的搜索模式

如果令精簡的鉆石組搜索搜得最佳匹配點P位于圈數round（P）上，則后續的搜索模式可表示為：

當最優點位于最內圈小菱形時，表明當前PU的運動強度較弱，則補充搜索與之對角相鄰的兩點，如圖2所示，然后結束全部搜索.

如果最優點位于中圈菱形時，表明當前PU可能具有中等運動強度，則循環地執行中圈鉆石搜索，并不斷調整搜索中心到當前最優點位置，直到最優點位置不再改變為止.最后，以獲得的最優點為中心，執行一次距離為1的小菱形搜索.類似地，如果最優點位于小菱形上，再補充搜索兩點.圖5舉例說明了這種搜索的過程.

圖5 具有中等運動強度PU的運動搜索過程舉例Fig.5 The example of motion search process for PUs with medium motion intensity

在圖5中，假設起始中心點的坐標是（0，0），x方向往右、y方向往下為坐標增大方向.在執行第1次中菱形搜索后，最優點位置變成（0，2）.因此，第2次搜索以當前最優點（0，2）為中心進行.由于有些點已經搜索過，本次只需再搜索5個新點，得新最優點坐標為（1，3）.類似地，第3、4次搜索得到的最優點位置為（2，4），由于連續兩次最優點的位置未發生變化，故以（2，4）為中心進行一次小菱形搜索，圖中以序號5標出.第5次搜索得到的最優點坐標為（3，4）.最后，檢查與（3，4）對角相鄰未搜索過的兩點（4，3）和（4，5），發現（3，4）點比（4，3）和（4，5）具有更小的RD代價值.所以，搜索得到的最終運動矢量為（3，4）.

如果最優點位于圖4的外圈菱形時，當前PU的運動強度可能很大，因此選用搜索半徑廣和效率高的六邊形模式［9］.以外圈菱形上的最優點為中心進行六邊形搜索，通過反復更新搜索中心的位置，不斷執行六邊形搜索，直到最優點位于六邊形中心為止.最后，以最優點為中心，執行一次正方形搜索.圖6舉例說明了該搜索的過程.

在圖6中，假設六邊形的中心點坐標為（0，0），執行完第1次六邊形搜索后，最優點出現在（1，2）處，以該點為中心，執行第2次六邊形搜索，本次只需搜索3個新點.類似第2次搜索得到的最優點為（3，2），而第3、4次搜索得到的最優點都為（5，2）.這表明用六邊形進行的粗搜索結果已經穩定，故以（5，2）為中心進行一次短距離的正方形精細搜索，確定全局最優點的位置.經搜索得到點（6，3）具有全局最小的RD代價值，從而確定出最終的運動矢量.

完整的快速分級搜索FHS算法的流程如圖7所示.

圖6 具有較高運動強度PU的運動搜索過程舉例Fig.6 The example of motion search process for PUs with higher motion intensity

圖7 快速分級搜索FHS算法流程圖Fig.7 The flow chart for fast hierarchical search algorithm FHS

3.3 FHS方法的特點

首先，FHS方法確立了早期搜索退出機制，只要經過內部兩圈菱形搜索，最優點仍在起始點，就可滿足退出的條件，節約了搜索的運算資源.其次，根據最優點在三圈不同菱形上的位置，初步判定當前PU的運動強度.對于不同的強度，選用不同的后續搜索方案.對于中、高運動強度的PU，移動的菱形或六邊形搜索都可進行遠距離運動矢量的搜尋，后者具有更高的效率.

4 實驗與仿真

提出的算法FHS在HEVC參考軟件HM14.0平臺上進行仿真.本文采用6個包含了不同運動程度的視頻序列進行測試.視頻的畫面尺寸是416× 240，搜索區域的窗口是［-64，64］.實驗中采用的編碼幀結構是IPPPP….本文將FHS算法與HM14.0標準軟件中提供的快速算法TZSearch進行比較.

對于不同的視頻序列，各取200幀進行測試.對于不同的運動估計算法，采用平均每次塊匹配所需搜索的點數NSP來衡量搜索的效率.將編碼壓縮后的結果再解碼得到的視頻與壓縮之前的原始視頻進行對比，并計算每幅圖像幀的平均峰值信噪比PSNR，這是評價編碼后壓縮視頻質量的重要指標.

4.1 平均每次搜索點數NSP

編碼重建幀的視頻質量與量化參數QP有關，QP越大，重建的視頻質量越粗糙，許多圖像細節因量化而消失.為了盡可能多的保存細節，本文選用量化參數QP為32進行測試.經統計得到6個序列的測試結果，如表1所示.

表1 QP為32時平均每次塊匹配搜索的點數NSPTab.1 The average number of search points NSP for each block matching when QP equals 32

圖8所示為兩者不同算法的Flowervase序列每幀平均NSP值對比曲線.可以看到，不同序列TZSearch搜索的NSP值相差較大，對于運動平緩的序列如BQSquare，NSP值較小.同時，TZSearch算法求得的各幀平均NSP隨視頻畫面中對象的運動程度起伏不定.而對于運動劇烈的視頻，如賽馬序列RaceHores，平均NSP值達到180.5，主要原因是由于大運動矢量的存在，TZSearch經常執行圖1中的多圈菱形搜索和圖3的光柵搜索，而一次光柵搜索需計算676個點的RD代價值.

圖8 QP為32時Flowervase序列各幀平均NSP比較Fig.8 The average NSP comparison of each frame for sequence Flowervase when QP equals 32

FHS方法的結果相對比較穩定.一方面，由于在多數情況下，實際的運動矢量mv和預測的運動矢量pmv比較接近，因而Δmv較小，而F HS對于小運動矢量采用了兩圈菱形早期退出機制和補充搜索兩點的方法，搜索的成本較小.對于運動程度中等或較高的PU，則采用了移動的中菱形或六邊形，可以快速到達最優匹配點附近，因此，整體消耗的搜索點數不多.

4.2 平均峰值信噪比PSNR

兩種方法每幀平均PSNR性能的比較歸納在表2中，總體PSNR的計算是基于像素的亮度Y和色度U、V分量進行的，可用下式表示［10］：

由表2可知，兩種方法編碼后重建幀的質量僅有較小的差別.FHS方法的平均PSNR值比TZSearch方法只有微小的下降.

表2 QP為32時平均每幀峰值信噪比PSNR（d B）Tab.2 The average peak signal to noise ratio for each f rame when QP equals 32

5 結 語

本文針對HEVC中運算耗時的運動估計問題提出了一種快速的分級搜索方法.首先根據鄰近塊的運動信息確定起始搜索點.為了提高搜索效率，對于小的運動矢量，采用早期退出或補充搜索與當前最優點對角相鄰兩點的方法.對于中、高運動強度的圖像塊，分別采用移動的中菱形和六邊形搜索，快速到達最優點附近位置.最后，采用精細的小菱形或正方形確定出全局最優點.實驗結果表明，FHS與HEVC的TZSearch方法相比，編碼后重建幀的質量沒有明顯的下降，但平均每次搜索的點數顯著減少，降低了編碼的運算復雜度.

［1］ Ohm J R，Sullivan G J，Schwarz H，et al.Comparison of the coding efficiency of video coding standards—including high efficiency video coding（HEVC）［J］. IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1669-1684.

［2］ Sullivan G J，Ohm J R，Han W J，et al.Overview of the high efficiency video coding（HEVC）standard［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1649-1668.

［3］ Kibeya H，Belghith F，Loukil H，et al.TZSearch pattern search improvement for HEVC motion estimation modules［C］／／1st International Conference on Advanced Technologies for Signal and Image Processing.New York：IEEE，2014：95-99.

［4］ Purnachand N，Alves L N，Navarro A.Fast motion estimation algorithm for HEVC［C］／／2012 IEEE Second International Conference on Consumer Electronics.New York：IEEE，2012：34-37.

［5］ Bossen F，Bross B，Suhring K，et al.HEVC complexity and implementation analysis［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1685-1696.

［6］ Helle P，Oudin S，Bross B，et al.Block merging for quadtree-based partitioning in HEVC［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1720-1731.

［7］ Pan Z，Zhang Y，Kwong S，et al.Early termination for TZSearch in HEVC motion estimation［C］／／The 38th International Conference on Acoustics，Speech，and Signal Processing.New York：IEEE，2012：1389-1393.

［8］ Yang S，Jiang J，Yang H.Fast motion estimation for HEVC with directional search［J］.ElectronicsLetters，2014，50（9）：673-675.

［9］ Zhu C，Lin X，Chau L P.Hexagon-based search pattern for fast block motion estimation［J］.IEEE Transactions on Circuits and Systems for Video Technology，2002，12（5）：349-355.

［10］ Yu L，Fu G，Men A，et al.A novel motion compensated prediction framework using weighted AMVP prediction for HEVC［C］／／2013 Visual Communications and Image Processing.New York：IEEE，2013：1-6.

（編輯 俞紅衛）

A Fast Approach to Motion Estimation Based on HEVC Video Coding

H AN Cong-dao， XU Shi-fang
（School of Electrical and Electronic Engineering，Shanghai Institute of Technology，Shanghai 201418，China）

Motion estimation is a critical factor which affects the coding efficiency of next video coding standard HEVC.It is usually performed by searching the best matched block of current frame image block in corresponding search windows of multiple reference frames.A fast motion estimation approach FHS was proposed for HEVC coding standard.Firstly，the position of initial search point was determined on the basis of multiple available motion vectors.Centered with the starting point，three circle diamond searches were performed with the expansion of search radius.The searches would terminate if the best matched point was still situated at the starting point when the two inner circle diamond searches were finished. Otherwise different successive search strategies were put forward based on the cases that the best matched point situated at the edge of inner，middle or outer circle diamond.The test results showed the proposed fast algorithm could attain less average search points compared to that afforded by H M14.0，meanwhile，it only did slight damage on the quality of coded video.

motion estimation；matched block；diamond search；hexagon search；multiple reference frames

TN 919.81

A

1671-7333（2015）01-0079-07

10.3969／j.issn.1671-7333.2015.01.014

2014-08-29

上海應用技術學院引進人才基金資助項目（YJ2012-5）

韓從道（1971-），男，講師，博士，主要研究方向為視頻編碼與信號處理.E-mail：hancongdao＠163.com