基于時空預(yù)測向量相關(guān)性的運(yùn)動估計算法

王佳利，姜 珊，雙 凱

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

基于時空預(yù)測向量相關(guān)性的運(yùn)動估計算法

王佳利，姜 珊，雙 凱

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

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

視頻壓縮；運(yùn)動估計；預(yù)測矢量相關(guān)性；時空預(yù)測向量

1 引言

隨著多媒體技術(shù)的飛速發(fā)展，視頻傳輸、視頻點(diǎn)播等需求越來越多，而這些需求的技術(shù)支撐都是建立在高效的視頻壓縮技術(shù)之上的。H.264[1]作為當(dāng)前視頻領(lǐng)域廣泛使用的壓縮標(biāo)準(zhǔn)，是由國際電聯(lián)(ITU-T)和國際標(biāo)準(zhǔn)化組織(ISO)聯(lián)合提出的。H.264在運(yùn)動估計部分也采用了基于塊的運(yùn)動估計算法，但就是將編碼幀分成不同大小的塊，這些塊在參考幀中規(guī)定的位置進(jìn)行搜索，然后利用計算的絕對差值和(SAD)來判斷是否可取，最后保存運(yùn)動矢量(MV)和殘差等數(shù)據(jù)，達(dá)到壓縮大量數(shù)據(jù)的目的。當(dāng)前比較成熟的運(yùn)動估計快速算法有三步搜索法TSS(Three Steps Search)、對數(shù)搜索法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算法采用多種不同的搜索模板，能適用于運(yùn)動劇烈程度不同的場景，提高了運(yùn)動估計的魯棒性。但是，該算法搜索復(fù)雜度很高，特別是非對稱六邊形搜索需要搜索大量的不相關(guān)點(diǎn)，大大加重了處理器的負(fù)擔(dān)，不適用于實(shí)時性的場合。本文針對以上問題，利用時間預(yù)測向量(當(dāng)前塊對應(yīng)參考幀中相同位置塊的預(yù)測MVpre)和空間預(yù)測向量(當(dāng)前塊周圍宏塊的中值預(yù)測向量MVmedian)的位置映射關(guān)系，提出了一種在小范圍得到最優(yōu)點(diǎn)后，繼續(xù)利用相關(guān)向量的方向性進(jìn)行擴(kuò)展搜索的新方法。

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

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

該算法的基本流程是：

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

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

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

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

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

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

3.1 初始預(yù)測點(diǎn)搜索

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

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

S1={MVi|MVi=

MVpic,MVmedian,MVpre,MVuplayer}

(1)

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

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

(2)

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

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是當(dāng)前進(jìn)行編碼的原始數(shù)據(jù)，而c是已經(jīng)編碼重建的用于進(jìn)行運(yùn)動補(bǔ)償?shù)膮⒖紟臄?shù)據(jù)。MV為候選的運(yùn)動矢量，λMOTION為拉格朗日常數(shù)，PMV為中值預(yù)測矢量，R(MV-PMV)代表了運(yùn)動矢量差分編碼可能耗費(fèi)的比特數(shù)。由于在接下來的四種匹配誤差預(yù)測方式中，匹配誤差中的λMOTION×R(MV-PMV)部分通常很接近而抵消，SAD部分的預(yù)測特性基本上可以反映整個匹配函數(shù)的預(yù)測特性，因此J(MV，λMOTION)可近似用SAD來表示。本文提前終止搜索的標(biāo)準(zhǔn)也使用SAD閾值。

接下來對當(dāng)前的最優(yōu)點(diǎn)進(jìn)行非對稱的十字模板搜索(圖2 Step-1)。因?yàn)樽匀唤缰械奈矬w在水平和垂直方向的運(yùn)動性遠(yuǎn)遠(yuǎn)高于其他方向，利用非對稱的十字搜索模板，可以較大概率提前獲取最優(yōu)搜索點(diǎn)。

3.2 多層菱形模板搜索

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

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

3.3 基于預(yù)測向量相關(guān)性搜索

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

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

這時，若非對稱十字模板預(yù)搜索后得到最優(yōu)點(diǎn)的SAD高于閾值，那該最優(yōu)點(diǎn)很可能是局部極值點(diǎn)。嘗試直接舍去，而圍繞MVmedian繼續(xù)進(jìn)行三圈(因?yàn)槌跏键c(diǎn)預(yù)測時已經(jīng)搜索了MVmedian點(diǎn)和其周圍四點(diǎn))的菱形模板搜索。每次更換模板的時候要對上次模板搜索后的點(diǎn)進(jìn)行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的正負(fù)值來計算MVpre相對于MVmedian的象限位置。例如，當(dāng)DIRTX>0和DIRTY≤0時(如圖4b所示)，MVpre相對MVmedian在第四象限，這時就采用模板圖2 Step-3中的上三角搜索點(diǎn)進(jìn)行搜索。其他象限的情況類似(如公式(8))，只是將模板圖2 Step-3中的上三角搜索點(diǎn)相對原點(diǎn)旋轉(zhuǎn)到不同象限。

Figure 4 MV correlation chart圖4 MV相關(guān)性圖

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

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

算法的最后一步采用在搜索范圍內(nèi)進(jìn)行六邊形搜索[11]。按照圖2 Step-4，對當(dāng)前的最優(yōu)點(diǎn)進(jìn)行窮盡的六邊形搜索，然后用小菱形模板反復(fù)搜索，一直到最優(yōu)點(diǎn)是小菱形的中點(diǎn)，該點(diǎn)就是最終的運(yùn)動矢量。

3.4 基于時空預(yù)測向量相關(guān)性算法流程圖

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

Figure 6 CSTPS flowchart圖6 CSTPS流程圖

4 實(shí)驗(yàn)驗(yàn)證

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

Table 1 Encoder parameters

表2是參考序列在僅改變估計算法而其他參數(shù)不變的情況下得到的PSNR、Bitrate、MEtime對比數(shù)據(jù)。表格和圖標(biāo)中用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 結(jié)束語

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

[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-),女,北京人，碩士，副教授，研究方向?yàn)樾畔⑴c通信工程。E-mail:jiangshan701@163.com

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

雙凱(1956-),男,北京人，博士，教授，研究方向?yàn)樾畔⑴c通信工程。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

國家自然科學(xué)基金資助項(xiàng)目(61072074)

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

TN919.8

A

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

王佳利(1986-),男,山西大同人，碩士，研究方向?yàn)樾畔⑴c通信工程。E-mail:solovirocalla@gmail.com

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

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