許曉中

(清華大學(xué) 電子工程系，北京 100084)

1 引言

由聯(lián)合視頻專家組JVT（Joint Video Team）提出的國際標(biāo)準(zhǔn)H.264/AVC[1]，是目前壓縮效率最高的視頻編碼標(biāo)準(zhǔn)。在該標(biāo)準(zhǔn)提供的眾多編碼工具中，運(yùn)動估計(jì)是其中的一項(xiàng)關(guān)鍵技術(shù)，它能夠有效地降低幀間預(yù)測編碼產(chǎn)生的誤差。在提高編碼效率的同時實(shí)現(xiàn)運(yùn)動估計(jì)算法，也帶來了很大的計(jì)算復(fù)雜度。以全搜索算法（遍歷所有可能的匹配位置）為例，對一個宏塊（16×16的亮度樣本矩陣）進(jìn)行整像素運(yùn)動估計(jì)，如果采用5個參考幀和±32的搜索窗，需要進(jìn)行（32×2+1）×（32×2+1）×（1+2+2+4+8+8+16）×5=866 125次塊匹配操作。運(yùn)動估計(jì)的計(jì)算量，構(gòu)成了編碼器的主要計(jì)算復(fù)雜度，也是實(shí)現(xiàn)實(shí)時編碼器的主要瓶頸。

為了解決編碼器計(jì)算復(fù)雜度過高的問題，許多快速運(yùn)動估計(jì)算法被提出，在保持全搜索算法的高編碼效率的同時，大大降低了原有算法所需的計(jì)算量。評價一個快速運(yùn)動估計(jì)算法，需要同時考慮兩方面的性能：一方面是相對于全搜索算法的搜索質(zhì)量，一般由編碼的PSNR值來衡量；另一方面是相對于全搜索算法的時間節(jié)省。H.264/AVC的參考軟件JM中，采用了3種可選的的快速運(yùn)動估計(jì)方法，分別是UMHS[2-3]，SUMHS（簡化的UMHS）[4]以及EPZS算法[5]。在給定的測試條件下，它們相對于全搜索算法，能達(dá)到平均PSNR損失小于0.1 dB，同時節(jié)省了約90%的運(yùn)動估計(jì)時間。

下面基于這3種算法對若干關(guān)鍵問題進(jìn)行研究分析，指出這些算法各自的特點(diǎn)及不足，最后給出運(yùn)動估計(jì)算法設(shè)計(jì)的幾條基本原則。

2 快速運(yùn)動估計(jì)算法簡介

2.1 UMHS算法

UMHS主要分為3個部分：

1）起始搜索點(diǎn)預(yù)測：空域中值MV預(yù)測，上層塊預(yù)測，臨近參考圖像預(yù)測，還有（0，0）位置，這些運(yùn)動矢量預(yù)測點(diǎn)作為搜索起始點(diǎn)，被用來預(yù)測當(dāng)前塊的運(yùn)動矢量。之后的搜索模式，將以最佳的起始預(yù)測點(diǎn)為中心展開。

2）全局搜索模式：以最佳起始預(yù)測點(diǎn)為中心，非對稱十字型搜索，5×5矩形搜索和多重六邊形網(wǎng)格搜索依次被采用。上一個搜索模式結(jié)束后得到的最佳匹配點(diǎn)，將作為下一個搜索模式的搜索中心。

3）局部優(yōu)化搜索：基于小六邊形的擴(kuò)展搜索和基于小菱形的擴(kuò)展搜索，依次在上一步驟中的最佳搜索點(diǎn)展開，作為最后的局部優(yōu)化。

4）提前截止策略：進(jìn)行運(yùn)動估計(jì)后得到的大部分最佳運(yùn)動矢量，它們的實(shí)際位置等同或者相當(dāng)接近于起始預(yù)測點(diǎn)，這說明大部分的搜索工作實(shí)際上并不是必要的。所以，在運(yùn)動估計(jì)過程中，引入一個合適的中途退出機(jī)制十分有意義。如圖1所示，在算法的各個主要搜索部分后均有提前截止的閾值判斷，如果當(dāng)前最佳匹配結(jié)果滿足設(shè)定閾值，則搜索提前結(jié)束。

圖1 UMHS算法流程圖

2.2 簡化的UMHS算法

該算法僅采用中值MV預(yù)測，并省略了5×5的矩形搜索模式；提前截止算法也使用簡單的常數(shù)閾值判斷。因此，相對于原算法，簡化算法在搜索速度上有明顯提升。

2.3 EPZS算法

與UMHS相似，EPZS采用了多個MV預(yù)測點(diǎn)作為起始搜索點(diǎn)，但其固定搜索模式只有一個十字型搜索，接下來就進(jìn)行局部迭代搜索，該搜索根據(jù)先前得到的信息，可以動態(tài)調(diào)整搜索模式。EPZS的提前截止閾值設(shè)計(jì)采用臨近塊匹配殘差的預(yù)測值與常數(shù)閾值相結(jié)合的方式進(jìn)行。

3 快速運(yùn)動估計(jì)算法比較研究

3.1 性能表現(xiàn)

采用文獻(xiàn)[6]中的測試序列和條件對3種方法進(jìn)行比較測試，實(shí)驗(yàn)結(jié)果如表1所示。

從表1中列出的數(shù)據(jù)可以看出，3種方法相對于FFS運(yùn)動搜索運(yùn)算時間節(jié)省超過90%，大大降低了編碼器的計(jì)算復(fù)雜度，其中簡化的UMHS（SUMHS）算法在速度上優(yōu)于另外2種算法；另一方面，在對FFS算法的性能保持上，SUMHS算法應(yīng)用于不規(guī)則運(yùn)動序列時，存在較大性能損失。

表1 3種快速算法相對于快速全搜索（FFS）算法的性能比較

3.2 搜索點(diǎn)數(shù)與搜索時間

構(gòu)成運(yùn)動估計(jì)時間開銷的操作中，除了已經(jīng)知道的海量塊匹配操作外，對于不同算法而言，還存在例如內(nèi)存讀寫、程序判斷跳轉(zhuǎn)等其他開銷，把這部分開銷統(tǒng)一稱為額外運(yùn)動估計(jì)時間開銷，用以區(qū)分塊匹配產(chǎn)生的開銷。額外時間開銷的比例越大，對整體運(yùn)動估計(jì)時間的影響也就越大，因此，在給定平臺上設(shè)計(jì)運(yùn)動估計(jì)算法時，需要盡可能的降低額外開銷與塊匹配開銷的比率。

表2 4種算法的搜索點(diǎn)數(shù)及搜索時間比較

3種快速算法比較來看，UMHS算法額外開銷比率最小，而EPZS最大，其原因在下個小節(jié)中繼續(xù)討論。

3.3 搜索模式設(shè)計(jì)

在單個CPU的軟件平臺上，各個搜索點(diǎn)之間的關(guān)系時順序進(jìn)行的，即上一個搜索點(diǎn)操作結(jié)束后，進(jìn)行下一個搜索點(diǎn)的塊匹配運(yùn)算。實(shí)際上，在一個給定的搜索模式中，各個搜索點(diǎn)的位置只由搜索模式的中心來決定，因此它們相互之間是獨(dú)立的。在支持并行計(jì)算的平臺上，這些相互獨(dú)立的搜索點(diǎn)可以同時進(jìn)行操作，從而進(jìn)一步加快運(yùn)動搜索速度。

基于這樣的設(shè)計(jì)理念，UMHS算法給出了一系列可以并行計(jì)算的“固定”搜索模式，其特點(diǎn)是大量相對獨(dú)立的搜索點(diǎn)覆蓋搜索窗內(nèi)。因此，就總的搜索點(diǎn)個數(shù)而言，該算法是最多的。與之相反，EPZS算法通過對上一個搜索點(diǎn)結(jié)束后所獲得的信息（例如運(yùn)動矢量大小和方向、塊匹配殘差大小等）進(jìn)行判斷，進(jìn)而動態(tài)的調(diào)整后續(xù)的搜索模式，從而達(dá)到盡可能節(jié)省搜索點(diǎn)個數(shù)的目的。因此，EPZS算法產(chǎn)生了較高的額外時間開銷率，其串行的結(jié)構(gòu)也不利于進(jìn)一步并行加速。

在實(shí)際設(shè)計(jì)中，需要考慮到時間算法平臺對并行計(jì)算的支持程度，以在搜索模式的并行性以及搜索點(diǎn)數(shù)的最優(yōu)性上尋找一個折中。

3.4 提前截止設(shè)計(jì)

總體來說，提前截止都是由閾值來決定的，比較當(dāng)前搜索的結(jié)果和給定的閾值，如果滿足則提前退出搜索過程。最簡單的閾值設(shè)計(jì)為常數(shù)閾值，是基于經(jīng)驗(yàn)設(shè)定一個常數(shù)閾值，該方法被SUMHS算法采用；第2種方法是通過相鄰塊最后得到的匹配殘差值，對當(dāng)前塊進(jìn)行預(yù)測，UMHS和EPZS算法都采用了這種方式；第3種方式是考慮到編碼參數(shù)（例如圖像尺寸等）對運(yùn)動估計(jì)的影響，將這些參數(shù)引入閾值設(shè)計(jì)中來，從而達(dá)到在不同編碼條件下均能高效提前截止的目的。在UMHS中，編碼量化參數(shù)和圖像尺寸被提前截止閾值設(shè)計(jì)所考慮。

[1]ITU-T and ISO/IEC JTC1.ITU-TRecommendation H.264-ISO/IEC 14496-10 AVC，Advanced video coding for generic audiovisual services[S].2003.

[2]CHEN Zhibo，XU Jianfeng，HE Yun，et al.Fast integer-pel and fractional-pelmotion estimation for H.264/AVC[J].Journal of Visual Communication and Image Representation，2006，17（2）：264-290.

[3]XU Xiaozhong，HE Yun.Improvements on fast motion estimation strategy for H.264/AVC[J],IEEE Trans.Circuits and Systems for Video Technology，2008，18（3）：285-293.

[4]YI Xiaoquan，ZHANG Jun，LING N，et al.Improved and simplified fastmotion estimation for JM.JVT-P021[R].[S.l.]：JVT，2005.

[5]TOURAPISA M，CHEONG H Y，TOPIWALA P.FastME in the JM reference software.JVT-P026[R].[S.l.]：JVT，2005.

[6]SULLIVAN G，BJONTEGAARDG.Recommended simulation common conditions for H.26L coding efficiency experiments on low-resolution progressive-scan sourcematerial.VCEG-N81[R].[S.l.]：ITU-TQ6/16 VCEG，2001.