基于時空預測向量相關性的運動估計算法

王佳利，姜 珊，雙 凱

(中國石油大學(北京)地球物理與信息工程學院，北京 102249)

基于時空預測向量相關性的運動估計算法

王佳利，姜 珊，雙 凱

(中國石油大學(北京)地球物理與信息工程學院，北京 102249)

針對UMHexagonS算法體現出來的問題，利用時間預測向量和空間預測向量的位置映射關系，提出了一種新的運動估計算法——基于時空預測向量相關性的運動估計算法。該算法首先在小范圍得到最優點后，繼續利用預測矢量的時空方向相關性進行特定方向的擴展搜索，避免了提前落入局部最優點，并減少了搜索點數，從而提高了搜索質量。實驗結果表明，與UMHexagonS算法相比，該算法在保持碼率基本不變的情況下，能有效地減少運動估計時間，并且能一定程度地提高單幀的峰值信噪比。

視頻壓縮；運動估計；預測矢量相關性；時空預測向量

1 引言

隨著多媒體技術的飛速發展，視頻傳輸、視頻點播等需求越來越多，而這些需求的技術支撐都是建立在高效的視頻壓縮技術之上的。H.264[1]作為當前視頻領域廣泛使用的壓縮標準，是由國際電聯(ITU-T)和國際標準化組織(ISO)聯合提出的。H.264在運動估計部分也采用了基于塊的運動估計算法，但就是將編碼幀分成不同大小的塊，這些塊在參考幀中規定的位置進行搜索，然后利用計算的絕對差值和(SAD)來判斷是否可取，最后保存運動矢量(MV)和殘差等數據，達到壓縮大量數據的目的。當前比較成熟的運動估計快速算法有三步搜索法TSS(Three Steps Search)、對數搜索法TDLS(Two-Dimensional Logarithmic Search)、共軛方向搜索法CDS(Conjugate Direction Search)[2]、四步搜索法FSS(Four Steps Search)[3]、菱形搜索法DS(Diamond Search)[4]、MVFAST(Motive Vector Field Adaptive Search Technique)算法、PMVFAST(Predictive Motion Vector Field Adaptive Search Technique)算法[5]、EPZS(Enhanced Predictive Zonal Search)[6]以及非對稱十字多層六邊形搜索UMHexagonS(Unsymmetrical cross Multi Hexagon Search)算法[7,8]等。其中，UMHexagonS算法采用多種不同的搜索模板，能適用于運動劇烈程度不同的場景，提高了運動估計的魯棒性。但是，該算法搜索復雜度很高，特別是非對稱六邊形搜索需要搜索大量的不相關點，大大加重了處理器的負擔，不適用于實時性的場合。本文針對以上問題，利用時間預測向量(當前塊對應參考幀中相同位置塊的預測MVpre)和空間預測向量(當前塊周圍宏塊的中值預測向量MVmedian)的位置映射關系，提出了一種在小范圍得到最優點后，繼續利用相關向量的方向性進行擴展搜索的新方法。

2 非對稱十字多層六邊形搜索(UMHexagonS)算法分析

運動估計中效果最好的算法是全搜索算法，具有最高的精度，但搜索的時間長、運算量大，根本不可能實現實時應用。UMHexagonS是JM(Joint Model)[9]采用的快速算法，該算法相對于全搜索算法能降低90%的搜索運算量，并依然能保持很好的止失真性能，現已經被大多數廠商采用。

該算法的基本流程是：

首先對初始預測搜索點進行單點和上下左右四點的搜索，判斷最優點SAD與閾值關系，選擇跳出或繼續進行如圖1中Step-1的非對稱十字搜索；接下來進行螺旋搜索，按圖1 Step-2所示的25點正方形搜索；下面是在搜索范圍內以四為步長，執行如圖1中Step-3所示的超六邊形模板搜索；最后用多圈的小六邊形和小菱形模板(圖1 Step-4)搜索得到最終的預測向量。

Figure 1 UMHexagonS search template圖1 UMHexagonS搜索模板

從上述UMHexagonS算法流程可以看到，該算法相比DS、TSS和EPZS等算法能很好地避免落入局部最優點，提高了算法的魯棒性。但是，我們也看到了Step-3和Step-4搜索的點數較多，特別是Step-3中的超六邊形搜索具有一定的盲目性，只是不斷地擴大全局搜索的范圍，用增加搜索點數來換取精度的提高。Step-1搜索后的最優點并非就一定是實際的最優點，因為該算法假設最優點的搜索平面是單調性的，即搜索點的SAD越低，那么該點就離理想最優點越近，而實際上的極值分布只是在小范圍內是單調的。針對上述問題，下面利用初始預測向量的時間空間相關性提出一種新的運動估計算法。

3 基于時空預測向量相關性的運動估計算法(CSTPS)

如上文所述，傳統的運動估計搜索算法首先找到潛在的初始搜索點，然后利用一定的搜索方法，分別在不同初始點的周圍進行搜索。這些算法在初始點之間的搜索是獨立的，然而很多時候基于時間和基于空間的預測初始點具有很強的相關性，如果能有效地利用這種相關性來減少搜索的點數、提高搜索的精度，對提高運動估計算法的效率是很有幫助的。本文接下來提出的CSTPS(Correlation of Spatial and Temporal Prediction Vector Search)算法，就是一種利用時空預測向量的相關性，按照圖2所示的四種搜索模板進行搜索的新的運動估計算法。

Figure 2 CSTPS search template圖2 CSTPS搜索模板

3.1 初始預測點搜索

運動搜索的第一步關鍵是要找到準確的初始預測點。當前待預測宏塊位置MVpic，中值預測向量MVmedian，對應于參考幀中與當前塊相同位置的宏塊的預測向量MVpre、上層宏塊預測向量MVuplayer[6](如公式(1))。以上四個初始預測向量與結果預測向量有很高的相關性，所以本文采用以上預測初始點進行第一步預測。

CSTPS算法首先分別對上述四個預測向量進行初始預測：將每個預測運動矢量和它上下左右四點組成起始搜索矢量組合(如公式(2))，在該組合中搜索最佳預測起點。

S1={MVi|MVi=

MVpic,MVmedian,MVpre,MVuplayer}

(1)

S2={MVj|MVj=(MVi.x±1,MVi.y),

(MVi,x,MVi.y±1)}

(2)

H.264 中定義的匹配誤差函數如下：

J(MV,λMOTION)=SAD(s,c(MV))+

λMOTION×R(MV-PMV)

(3)

其中SAD計算公式如公式(4)所示:

c[x-MVx,y-MVy]|,Bx,By=16,8, or 4

(4)

其中，s是當前進行編碼的原始數據，而c是已經編碼重建的用于進行運動補償的參考幀的數據。MV為候選的運動矢量，λMOTION為拉格朗日常數，PMV為中值預測矢量，R(MV-PMV)代表了運動矢量差分編碼可能耗費的比特數。由于在接下來的四種匹配誤差預測方式中，匹配誤差中的λMOTION×R(MV-PMV)部分通常很接近而抵消，SAD部分的預測特性基本上可以反映整個匹配函數的預測特性，因此J(MV，λMOTION)可近似用SAD來表示。本文提前終止搜索的標準也使用SAD閾值。

接下來對當前的最優點進行非對稱的十字模板搜索(圖2 Step-1)。因為自然界中的物體在水平和垂直方向的運動性遠遠高于其他方向，利用非對稱的十字搜索模板，可以較大概率提前獲取最優搜索點。

3.2 多層菱形模板搜索

經過非對稱的十字模板搜索后，得到當前最優點，接下來利用多層的基于菱形的模板進行搜索，該多層模板如圖3所示。在不同層間轉換時，進行閾值比較判斷是否可以提前退出搜索。運動矢量分布是由香港城市大學Lam Chi-wai提出的[10]，通過對六個不同測試序列使用全搜索方法和MAD匹配，得到平均運動矢量分布概率表。分析得出71.796%左右的運動矢量分布在當前最優點周圍半徑為2的范圍內，而85.388%左右的運動矢量分布在如圖2 Step-2所示的范圍內。這樣在當前最優點的周圍進行多層的菱形模板(如圖3)搜索時，能以很大概率得到準確的預測點。不同層間轉換時加入了提前終止判斷，在搜索過程中遇到相對最優點時，提前退出搜索，有效地減少了搜索點數，提高了搜索效率。

Figure 3 Step-2 search template in CSTPS圖3 CSTPS的Step-2搜索模板

3.3 基于預測向量相關性搜索

下面利用基于時間和空間預測向量的相關性來繼續搜索。這里提到的相關性主要包括兩種情況：首先是MVmedian和MVpre映射到同一時空二維平面的絕對距離相關性；其次是MVmedian和MVpre相對于當前最優點的空間象限分布相關性。

如圖4a所示，當MVmedian和MVpre距離很近時(如公式(5)，其中MVpre.x代表MVpre相對于當前宏塊位置的橫坐標，其它變量類似)，那么可以肯定它們之間的相關性很高，這樣最優搜索點很可能就在兩個預測MV相關區域的周圍，而且當距離MVmedian的半徑不超過4個像素時，則需重點對這個區域進行搜索。

這時，若非對稱十字模板預搜索后得到最優點的SAD高于閾值，那該最優點很可能是局部極值點。嘗試直接舍去，而圍繞MVmedian繼續進行三圈(因為初始點預測時已經搜索了MVmedian點和其周圍四點)的菱形模板搜索。每次更換模板的時候要對上次模板搜索后的點進行SAD閾值比較，判斷是否提前退出搜索。

|MVpre.z-MVmedian.x|+|MVpre.y-MVmedian.y|<4

(5)

DIRTX=MVpre.x-MVmedian.x

(6)

DIRTY=MVpre.y-MVmedian.y

(7)

SELECTION=

(8)

利用DIRTX和DIRTY的正負值來計算MVpre相對于MVmedian的象限位置。例如，當DIRTX>0和DIRTY≤0時(如圖4b所示)，MVpre相對MVmedian在第四象限，這時就采用模板圖2 Step-3中的上三角搜索點進行搜索。其他象限的情況類似(如公式(8))，只是將模板圖2 Step-3中的上三角搜索點相對原點旋轉到不同象限。

Figure 4 MV correlation chart圖4 MV相關性圖

如果MVmedian和MVpre距離很遠(如圖5a所示)，則它們的相關性較低。這時候就要加大搜索的復雜度來換取圖像效果。當MVmedian和MVpre的位置相對于在多層菱形模板搜索后得到的最優點在同一象限時(以當前最優點為中心劃分平面為四個象限)(如圖5b所示)，那么就繼續對該象限進行三層的5點單象限搜索(如模板圖2 Step-3中所有搜索點所示)，共計15個點。當MVmedian和MVpre相對于在多層菱形模板搜索后得到的最優點不在同一象限時(如圖5c所示)，那么就要分別對MVmedian和MVpre所在的象限進行三層的5點單象限搜索(如模板圖2 Step-3中所有搜索點所示)，共計30個點。

Figure 5 Examples of MV quadrant distribution圖5 MV象限分布圖例

算法的最后一步采用在搜索范圍內進行六邊形搜索[11]。按照圖2 Step-4，對當前的最優點進行窮盡的六邊形搜索，然后用小菱形模板反復搜索，一直到最優點是小菱形的中點，該點就是最終的運動矢量。

3.4 基于時空預測向量相關性算法流程圖

本文對CSTPS算法的驗證是基于JM18測試模型的，編寫了新的CSTPS運動估計算法模塊，并且在開始的配置文件中加入該算法選項，而其它基于H.264標準的軟件模塊保持不變。圖6是新編寫模塊的算法流程圖。

Figure 6 CSTPS flowchart圖6 CSTPS流程圖

4 實驗驗證

本文實驗在PC機上進行，硬件具體參數如下：Intel Core i3-2350 @ 2.30 GHz，3 GB內存，32位Windows 7 旗艦版，Microsoft Visual Studio 2010。實驗參考視頻測試模型：JM18.0 VC版；實驗選取的參照算法是UMHexagonS；六個官方測試視頻序列highway_cif.yuv、hall_cif.yuv、foreman_cif.yuv、mobile_qcif.yuv、foreman_qcif.yuv、silent_qcif.yuv；編碼器的主要參數如表1所示。

Table 1 Encoder parameters

表2是參考序列在僅改變估計算法而其他參數不變的情況下得到的PSNR、Bitrate、MEtime對比數據。表格和圖標中用UMHEX代表UMHexagonS，用CSTPS代表本文提出的算法。

Table 2 Comparison of the data

從表2中可以看到CSTPS算法相對于UMHEX算法，PSNR的提高在0.01～0.03 dB不等，碼率的變化在-0.28%～0.26%，MEtime甚至可以減少5%～15%。

圖7是針對不同序列的兩種算法的MEtime時間的對比，可以從圖中直觀地看到CSTPS算法對每個序列MEtime都有一定程度的減少，特別對foreman序列最高有15%的下降。

圖8是用兩種算法對mobile_qcif.yuv，在QT=25情況下，選取200幀的逐幀MEtime對比圖。可以看到,CSTPS算法的單幀MEtime相對于UMHEX算法普遍有一定的降低，而不是局部幀的突變，說明CSTPS算法的效率提高具有普遍性。

Figure 7 Comparison of the MEtime圖7 MEtime對比

Figure 8 Frame by frame MEtime comparison圖8 逐幀MEtime對比

5 結束語

本文研究了當前H.264采用的運動估計算法UMHexagonS，針對該算法的缺點，提出了一種全新的基于時空預測向量相關性進行搜索的運動估計算法CSTPS。經過實驗驗證，本文提出的算法在很好地保持了運動估計的準確性和圖像質量的基礎上，有效降低了運動估計的時間，減少了搜索的點數，說明本文提出的CSTPS算法相對于現有算法，可以有效提高H.264的實時性。本文的算法是在PC機上驗證的，接下來的工作是將算法優化，實現該算法在DSP上的實時應用。

[1] JVTG050.TRE commendation and final draft international standard of joint video specification[S].ITU-T Rec H.264/ISO/IEC14496-10,2003.

[2] Cheung C, Po L M. A novel cross-diamond search algorithm for fast block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2003,12(12):1168-1177.

[3] Po L M, Ma W C. A novel four step search algorithm for fast block motion estimation[J]. IEEE Transactions on Circuits and System for Video Technology,1996,6(3):313-317.

[4] Tham J Y, Ranganath S, Kassim A A. A novel unrestricted center-biased diamond search algorithm for block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology,1998, 8(4):369-377.

[5] Tourapis A M, Au O C, Liou M L. Predictive motion vector field adaptive search technique(PMVFAST)-enhancing block based motion estimation[C]∥Proc of Visual Communications and Image Processing, 2001:883-892.

[6] Tourapis A. Enhanced predictive zonal search for single and multiple frame motion estimation[C]∥Proc of Visual Communications and Image Processing, 2002:1069-1079.

[7] Chen Zhi-bo, Zhou Peng, He Yun. Fast motion estimation for JVT[C]∥Proc of the 7th Meeting of ISO/IEC, JTCI/SC29/WG11 and ITU-T SG16 Q.6,2003:1.

[8] Chen Z, Xu J, He Y, et al. Fast integer-pel and fractional-pel motion estimation for H.264/AVC[J].Journal of Visual Communication and Image Representation, 2006,17(2):264-290.

[9] JM18.0. Reference software of H.264[EB/OL].[2012-04-01].http://iphome.hhi.de/suehring/tml/.

[10] Lam Chi-wai, Po Lai-man.Cheung Chun Ho. A novel kite-cross-diamond search algorithm for fast block matching motion estimation[C]∥Proc of the 2004 International Symposium on Circuits and Systems, 2004:Ⅲ-729-Ⅲ-732.

[11] 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):345-355.

WANG Jia-li,born in 1986,MS,his research interest includes information and communication engineering.

姜珊(1967-),女,北京人，碩士，副教授，研究方向為信息與通信工程。E-mail:jiangshan701@163.com

JIANG Shan,born in 1967,MS,associate professor,her research interest includes information and communication engineering.

雙凱(1956-),男,北京人，博士，教授，研究方向為信息與通信工程。E-mail:Shuangkai815@163.com

SHUANG Kai,born in 1956,PhD,professor,his research interest includes information and communication engineering.

A motion estimation algorithm based on the correlation of spatial-temporal prediction vector

WANG Jia-li,JIANG Shan,SHUANG Kai
(College of Geophysics and Information Engineering,China University of Petroleum(Beijing ),Beijing 102249)

Using the mapping relationship of the temporal prediction vector and the spatial prediction vector, a new motion estimation algorithm is proposed to solve the shortcoming of UMHexagonS algorithm. In order to avoid the early fall into the local advantages, reduce the search points and improve search quality, it gets the most advantage of the algorithm on a small scale and continues to expand the search for a specific direction of using the directional prediction vector. The experimental results show that, compared with UMHexagonS algorithm, the new algorithm can generally improve the single frame peak signal-to-noise ratio and effectively reduce the time of motion estimation in case of almost the same bit rate.

video compression;motion estimation;correlation of prediction vector;spatial and temporal prediction vector

2012-09-04;

2012-12-20

國家自然科學基金資助項目(61072074)

1007-130X(2014)03-0502-06

TN919.8

A

10.3969/j.issn.1007-130X.2014.03.022

王佳利(1986-),男,山西大同人，碩士，研究方向為信息與通信工程。E-mail:solovirocalla@gmail.com

通信地址：037000 山西省大同市西環路恒園魏都6號樓3單元

Address:Unit 3,Building 6,Hengyuanweidu,Xihuan Rd,Datong 037000,Shanxi,P.R.China