基于H.264/AVC的運動估計算法研究

許曉中

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

1 引言

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

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

下面基于這3種算法對若干關鍵問題進行研究分析，指出這些算法各自的特點及不足，最后給出運動估計算法設計的幾條基本原則。

2 快速運動估計算法簡介

2.1 UMHS算法

UMHS主要分為3個部分：

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

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

3）局部優化搜索：基于小六邊形的擴展搜索和基于小菱形的擴展搜索，依次在上一步驟中的最佳搜索點展開，作為最后的局部優化。

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

圖1 UMHS算法流程圖

2.2 簡化的UMHS算法

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

2.3 EPZS算法

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

3 快速運動估計算法比較研究

3.1 性能表現

采用文獻[6]中的測試序列和條件對3種方法進行比較測試，實驗結果如表1所示。

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

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

3.2 搜索點數與搜索時間

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

表2 4種算法的搜索點數及搜索時間比較

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

3.3 搜索模式設計

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

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

在實際設計中，需要考慮到時間算法平臺對并行計算的支持程度，以在搜索模式的并行性以及搜索點數的最優性上尋找一個折中。

3.4 提前截止設計

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

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