楊 虎，潘紅兵，，何書專，李 麗

(1.南京大學(xué)電子學(xué)院微電子設(shè)計研究所，江蘇南京210093;2.江蘇省光電信息功能材料重點實驗室，江蘇南京210093)

0 引言

H.264/AVC［1］是MPEG和ITU-T聯(lián)合制定的最新視頻編碼標(biāo)準(zhǔn)，其基本編碼框架和先前類似標(biāo)準(zhǔn)并沒有太大變化，但是編碼模塊的技術(shù)方案應(yīng)用了目前編碼的很多新技術(shù)，采用了非常高效和精確的運動估計預(yù)測方法，其編碼效率比以往的編碼標(biāo)準(zhǔn)H.261/H.263和MPEG-1/2/3均提高40%以上，獲得了較高的編碼質(zhì)量，但卻是以極大增加運算復(fù)雜度為代價的，一直成為實時應(yīng)用的瓶頸。

視頻編碼領(lǐng)域中最關(guān)鍵的技術(shù)是運動估計算法，其作用是在編碼過程中消除圖像幀間冗余度，目前已經(jīng)成為視頻壓縮研究領(lǐng)域的熱點。當(dāng)前，塊匹配算法因其易于硬件實現(xiàn)已經(jīng)廣泛應(yīng)用于各種視頻編碼標(biāo)準(zhǔn)，確定匹配塊的準(zhǔn)則是塊失真度。研究表明，運動估計算法模塊是整個編碼過程中最耗時的部分，為了降低運動估計算法復(fù)雜度，減少耗時，提升編碼效率，各國學(xué)者提出了很多運動估計快速算法［2］-［5］，包括新三步法 (NTSS)、鉆石搜索法 (DS)、六邊形模板搜索法 (HEXBS)以及十字-鉆石-六邊形搜索法 (CDHS)這些算法一定程度上能夠降低運動估計算法復(fù)雜度，同時保證了原有的視頻質(zhì)量，對運動緩慢和圖像尺寸較小的視頻序列可以取得較好的效果，但是在編碼運動劇烈和圖像尺寸較大的序列時，效果不太滿意，容易陷入局部最優(yōu)點，從而影響編碼質(zhì)量。

非對稱十字形多層次六邊形搜索算法 (UMHexagonS)［6］是清華大學(xué)提出的快速運動估計算法，已經(jīng)被H.264 JM參考模型所采納，其運算量只有全搜索算法(FS)的10%，同時保持了較好的率失真性能，避免了運動搜索過早陷入局部最優(yōu)點，而且能夠應(yīng)用于不同類型的視頻序列，獲得了與FS幾乎相同的運動估計效果。UMHexagonS雖然有效加快了運動估計的速度，但是仔細分析仍然存在很大的優(yōu)化空間，本文從早期結(jié)束閾值、混合搜索模板和宏塊類型模板對UMHexagonS算法進行了改進。

1 UMHexagonS算法特征與存在問題

1.1 精確預(yù)測初始搜索起點

UMHexagonS算法開始是確定搜索的初始運動矢量，其矢量集包括中值預(yù)測矢量、上層預(yù)測矢量、原點預(yù)測矢量、相鄰參考幀預(yù)測矢量和參考幀相同位置宏塊預(yù)測矢量。上述運動矢量集中能使拉格朗日代價函數(shù)最小的矢量作為最小的運動矢量，若不滿足搜索提前中止的條件，這個矢量即為下一步搜索的最佳搜索起點。UMHexagonS使用的起點預(yù)測有效利用了幀內(nèi)、幀間相鄰塊的運動矢量相關(guān)性，因此其篩選出的搜索點最能夠反映當(dāng)前搜索塊的運動趨勢，很好的提升搜索精度。

1.2 早期提前終止搜索策略

為了使運動估計算法在搜索速度和搜索質(zhì)量之間達到平衡，UMHexagonS算法中設(shè)計了一個適當(dāng)?shù)腅T閾值，在每一次不同的搜索步驟之后使用ET閾值判斷是否結(jié)束搜索:

(1) 初始搜索起點預(yù)測

(2) 非對稱大十字搜索

(3) 5x5正方形搜索

(4) 非均勻多層次16點六邊形搜索

每當(dāng)滿足ET結(jié)束條件時，搜索算法將會跳轉(zhuǎn)到局部精細搜索部分。上述的ET值由式 (1)決定，其大小與當(dāng)前塊大小、量化步長、量化系數(shù)QP和相鄰塊MCOST有關(guān)

算法中不同搜索步驟之后使用ET閾值都是相同的，可能出現(xiàn)一個問題，就是得到的小于ET的最小點不是一個最佳點，然而利用ET在搜索后面階段找到更好搜索點的可能性變得越來越小。以UMHexagons最后主要的搜索模板為例，從搜索中心到搜索窗口邊界，其包含了4個16個點六邊形搜索。如果一次六邊形搜索不能找到更好的搜索點，當(dāng)前的最優(yōu)點仍然需要從前面的搜索步驟中獲得，六邊形搜索將會繼續(xù)，這樣的話后面六邊形搜索中使用的ET將失效。文獻［7］實驗結(jié)果顯示在不同圖片尺寸和QP編碼條件下，六邊形搜索中ET的使用效率非常低 (ET效率的定義是搜索中途退出的次數(shù)/搜索總次數(shù))，可見在這一搜索步驟中ET幾乎沒有用。因此為了提高算法的搜索效率，必須在不同的搜索步驟中使用不同的ET閾值。

1.3 混合多層次搜索

UMHexagons是混合多層次搜索算法，其搜索過程可分為大范圍粗搜索、細搜索和精細搜索階段，其中粗搜索階段包含非對稱大十字模板、5x5正方形模板和非均勻多層次六邊形模板，細搜索階段使用正六邊形模板搜索，直到得到的最佳點位于正六邊形中心時，進入精細搜索階段，使用小鉆石模板搜索，當(dāng)搜索點位于小鉆石中心時即可得到最佳運動向量，搜索結(jié)束。

從算法的3個搜索過程可以看到，最壞情況下，粗搜索階段算法要搜索113個點 (非對稱十字24+正方形25+非均勻多層次六邊形64)，搜索點數(shù)過多，算法忽略了預(yù)測運動向量的方向性，過多的搜索了不必要的點;同時在細搜索階段使用的是相同的正六邊形模板，算法沒有考慮到不同宏塊使用不同的搜索模板以保證搜索速度和質(zhì)量的折中，因此有必要對原算法進行改進。

2 對UMHexagonS算法的改進

由以上分析UMHexagonS算法中存在的問題，對算法的改進如下。

2.1 提出一種新的自適應(yīng)ET閾值

根據(jù)文獻［7］設(shè)計了自適應(yīng)運動估計搜索早期結(jié)束策略，引入一種新的ET閾值，其ET閾值的大小由圖像的大小和量化參數(shù)兩個因素決定，以適應(yīng)不同的編碼條件。運動估計算法中需要的兩個閾值由以下式子決定

式 (2)中 Threshold代表 Threshold1和 Threshold2，ThdBase代表ThdBase1和ThdBase2。由于大多數(shù)情況下物體的運動是規(guī)律且緩慢的，相鄰塊預(yù)測得到的中值預(yù)測矢量很有可能是最佳的搜索點，搜索中值預(yù)測點之后使用Threshold1，若滿足條件，這時候可以認(rèn)為運動估計算法就找到了最優(yōu)點，可以結(jié)束整個搜索，極大節(jié)省搜索時間。每一步非均勻多層次六邊形搜索之后可以使用Threshold2，因為這是算法最耗時的部分，一旦當(dāng)前的MCOST小Threshold2，算法進入細搜索階段。ThdBase由最小QP和最小圖像尺寸設(shè)置，通常Thd1Base比Thd2Base小，因為假如滿足了Threshold1，就沒有必要再繼續(xù)進行運動估計搜索，而且一個小的Threshold能確保對搜索質(zhì)量影響最小。式 (3)M是閾值的調(diào)節(jié)因子，由兩個變量QP和圖像大小決定，目的是為了使閾值適應(yīng)不同的QP和視頻序列。M調(diào)節(jié)因子的原則是越大的閾值分配給盡量小的QP和大的圖像尺寸。式(4)MAX_QP是H.264/AVC使用的最大QP值，式 (5)MIN_WIDTH是測試序列中最小的圖像寬度，其中常數(shù)A和B由實驗確定。根據(jù)實驗測試的結(jié)果，各個參數(shù)的取值如下

Thd_Base中的7個值分別對應(yīng)從16x16到4x4七種宏塊大小，QP_factor的參數(shù)A在整像素搜索中設(shè)為0.9，分?jǐn)?shù)像素搜索中設(shè)為0.3，Scale_factor的參數(shù)B設(shè)為0.3。

2.2 粗搜索階段的模板改進

2.2.1 大十字模板和多層次六邊形模板改進

根據(jù)文獻［8］利用當(dāng)前塊的運動矢量和前一幀與當(dāng)前塊的相同位置塊運動矢量可以減少運動估計搜索點數(shù)，用current_MV表示當(dāng)前塊運動矢量，previous_MV表示前一幀運動矢量，求出兩個運動矢量的夾角，計算方法如下

若兩個矢量都不為0，根據(jù)式 (8)計算出其夾角θ，否則仍然按照改進前算法計算，由式 (8)可知，current_MV是隨著搜索中心的改變而變化，而previous_MV在每次塊搜索中的大小是不變的。

根據(jù)參考文獻［9］提出的對搜索模板的劃分方式，對非對稱大十字和多層次六邊形進行劃分，如圖1所示，與水平方向成45度角互相垂直的兩根直線把搜索區(qū)域分為4個部分，根據(jù)式 (8)計算出的θ決定將在哪個搜索區(qū)域繼續(xù)尋找最佳運動向量，只要預(yù)測向量的精度足夠高，就可在該區(qū)域找到最佳點，因此可以節(jié)省大量的搜索點，如圖2可知，采用如此劃分之后，非對稱大十字搜索點數(shù)由之前的24點降為8點或4點，而多層次六邊形由原來64點降為20點或12點，極大的減少了搜索點數(shù)，可以有效提升搜索速度。

由式 (8)的θ，確定相應(yīng)的搜索區(qū)域，確定的方式如下:

當(dāng) θ∈ (0，45°］∪ (315°，360°］時:在 (a)(e)區(qū)域搜索;

當(dāng)θ∈(45°，135°］時:在 (b)(f)區(qū)域搜索;

當(dāng)θ∈(135°，225°］時:在 (c)(g)區(qū)域搜索;

當(dāng)θ∈(225°，315°］時:在 (d)(h)區(qū)域搜索。

2.2.2 5x5方形搜索模板改進

根據(jù)文獻［10］可知，搜索過程中正方形模板里每個點成為最佳點的概率是不一樣的，因此沒有必要對每個點進行搜索，只保留成為最佳點概率高的點，其它點可以棄掉，減少搜索點數(shù)。由于這一步是小范圍搜索，因此可忽略其矢量的方向性，采用菱形—正方形模板替代之，由圖3可知搜索的點數(shù)由25點減少到9點，同時還保持了搜索各個方向上點數(shù)的均勻。

圖3 菱形—正方形搜索模板

2.3 細搜索階段算法改進

由上面階段得到的運動估計向量，進入細搜索階段，對于16x16到4x4七種搜索模式，若都采用同一種搜索模板，則必會增加搜索時間。為了平衡搜索精度和搜索速度，針對不同的搜索模式采用不同的模板［11］，在保持搜索精度的前提下，提升搜索速度。

(1)若塊類型為16x16、8x8時，搜索時仍用正六邊形模板，如圖4(a)所示。

(2)若塊類型為16x8、8x4時，搜索時使用扁平六邊形模板，如圖4(b)所示。

(3)若塊類型為8x16、4x8時，搜索時使用豎直六邊形模板，如圖4(c)所示。

(4)若塊類型為4x4時，搜索時使用小鉆石模板，如圖5所示。

當(dāng)?shù)玫降倪\動向量中心在模板中心時，上述每一種模式對應(yīng)的模板搜索結(jié)束，進入精細搜索階段。

2.4 精細搜索階段改進

圖4 六邊形搜索模板

為了保證運動搜索的精度，精細搜索階段仍然采用原算法圖5的小鉆石搜索，不過注意，若是模式4x4的搜索，則跳過精細搜索階段，因為細搜索階段得到的點已經(jīng)是最佳運動向量點，其他模式的搜索直到最佳點在模板中心時結(jié)束。

圖5 小鉆石模板

3 實驗結(jié)果與分析

首先，UMHexagons改進的算法在H.264標(biāo)準(zhǔn)測試平臺JM10.1中實現(xiàn)。測試PC硬件為Intel(R)Pentium(R)D CPU 2.81GHz，2GB內(nèi)存。操作系統(tǒng)為 Microsoft Windows XP Professional 2002，Service Pack3。編碼器配置采用JM10.1的基本類，實驗的主要編碼參數(shù)見表1。

表1 主要的編碼參數(shù)

為了測試改進算法的性能，采用不同運動類型的標(biāo)準(zhǔn)測試視頻序列，見表2。

表2 待測試序列

表3 運動時間比較數(shù)據(jù)

由表3可知，對于運動緩慢的測試序列，改進算法運動估計時間減少不多，因為在這類序列中主要是靜止塊和運動緩慢的塊，搜索過程大部分在新的ET Threshold1閾值判斷階段就結(jié)束了，所以在算法中使用的模板區(qū)域劃分和改進模板沒有起到作用。但是對于中等運動和運動劇烈測試序列，搜索的速度顯著上升，尤其是運動劇烈序列，改進算法的速度提升在25%以上，主要是因為進入了混合搜索階段后，改進的算法大大減少了搜索點數(shù)，發(fā)揮了極大的作用。通過實驗表4可以看到，改進算法的PSNR平均只改變了0.02dB，最大只改變了0.03dB，壓縮算法對圖片質(zhì)量的影響可忽略不計，同時，碼率變化很小，平均值增加了1.30%，最大增加不超過2.07%。因此可以看到，對于不同類型的標(biāo)準(zhǔn)測試視頻序列，改進的算法有效提升了運動估計的速度，同時保持了原算法的率失真性能，對圖像質(zhì)量的影響非常小。見表5。

表4 亮度信號峰值信噪比 (PSNR)比較數(shù)據(jù)

表5 碼率比較數(shù)據(jù)

4 結(jié)束語

文章對H.264快速運動估計算法UMHexagonS的特點進行了分析，研究了算法中存在的問題并作了改進，引入了新的ET閾值，更好的發(fā)揮了算法中提前結(jié)束搜索的功能，同時應(yīng)用了預(yù)測運動向量的方向偏置性，極大的減少了搜索點，加快了搜索速度，而且針對不同的宏塊，應(yīng)用不同的搜索模板，提高了搜索精度。實驗的結(jié)果表明，對于不同類型的測試序列，在保證碼率和圖像質(zhì)量的前提下，編碼效率得到了有效的改進，提升了編碼器的實時性。

［1］BI Houjie，WANGJian.H.264/AVCvideo compression video coding for next generation multimedia［M］.2et nd.Beijing:Posts＆Telecom Press，2009:51-76(in Chinese).［畢厚杰，王健.新一代視頻壓縮編碼標(biāo)準(zhǔn)—H.264/AVC［M］.2版.北京:人民郵電出版社，2009:51-76.］

［2］Suh JW，Cho J，Jeong J.Model-based quarter-pixel motion estimation with low computational complexity ［J］.Electronics Letters，2009，45(12):618-620.

［3］Sarwer M G，WU Q M J.Adaptive variable block-size early motion estimation termination algorithm for H.264 /AVC video coding standard［J］.IEEE Trans on Circuits and Systems for Video Technology，2009，19(8):1196-1201.

［4］ISMAIL Y，McNEELY J，SHAABAN M，et al.A generalized fast motion estimation algorithm using external and internal stop search techniques for H.264 video coding standard［C］//Proc of IEEE International Symposium on Circuits and Systems.Seattle，WA，2008:3574-3577.

［5］WU Xiaomin，XU Weizhang，ZHU Nanhao，et al.A fast motion estimation algorithm for H.264［C］//Proceedings of International Conference on Signal Acquisition and Processing.Bangalore，India:IEEE Press，2010:112-116.

［6］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.

［7］XU Xiaozhong，HE Yun.Improvements on fast motion estimoton strategy for H.264/AVC ［J］.IEEE Transactions on Circuits and System for Video Technology，2008，18(3):285-293.

［8］Thambiduarai P，Ezhilarasan M，Ramachanfran D.Efficient motion estimation algorithm for advanced video coding［C］.Coference on Computational Intelligence and Multimedia Application.Sivakasi，Tamilnadu，India，2007:47-52.

［9］LI Guiju，LIU Gang，LIANG Jingqiu.Improvement of fast motion estimation algorithm used in H.264 ［J］.Optics and Precision Engineering，2010，18(11):2489-2496(in Chinese).［李桂菊，劉剛，梁靜秋.H.264快速運動估計算法的改進 ［J］光學(xué)精密工程，2010，18(11):2489-2496.］

［10］DING Y，SONG X H，YAN S H，et al.Improvements of UMHexagonS algorithm based on fast motion estimation［J］.Data Acquisition ＆ Processing，2009，24(5):660-663.

［11］DUAN Qingqing，SONGXuerui.Fast Motion Estimation Algorithm in H.264/AVC ［J］.Computer Engineering，2008，34(16):244-246(in Chinese).［段青青，宋學(xué)瑞.一種H.264/AVC中的快速運動估計算法［J］.計算機工程，2008，34(16):244-246.］