H.264視頻壓縮快速運(yùn)動(dòng)估計(jì)算法UMHexagons改進(jìn)

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

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

0 引言

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

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

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

1 UMHexagonS算法特征與存在問(wèn)題

1.1 精確預(yù)測(cè)初始搜索起點(diǎn)

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

1.2 早期提前終止搜索策略

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

(1) 初始搜索起點(diǎn)預(yù)測(cè)

(2) 非對(duì)稱大十字搜索

(3) 5x5正方形搜索

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

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

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

1.3 混合多層次搜索

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

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

2 對(duì)UMHexagonS算法的改進(jìn)

由以上分析UMHexagonS算法中存在的問(wèn)題，對(duì)算法的改進(jìn)如下。

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

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

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

Thd_Base中的7個(gè)值分別對(duì)應(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 粗搜索階段的模板改進(jìn)

2.2.1 大十字模板和多層次六邊形模板改進(jìn)

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

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

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

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

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

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

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

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

2.2.2 5x5方形搜索模板改進(jìn)

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

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

2.3 細(xì)搜索階段算法改進(jìn)

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

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

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

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

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

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

2.4 精細(xì)搜索階段改進(jìn)

圖4 六邊形搜索模板

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

圖5 小鉆石模板

3 實(shí)驗(yàn)結(jié)果與分析

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

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

為了測(cè)試改進(jìn)算法的性能，采用不同運(yùn)動(dòng)類型的標(biāo)準(zhǔn)測(cè)試視頻序列，見(jiàn)表2。

表2 待測(cè)試序列

表3 運(yùn)動(dòng)時(shí)間比較數(shù)據(jù)

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

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

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

4 結(jié)束語(yǔ)

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

［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快速運(yùn)動(dòng)估計(jì)算法的改進(jìn) ［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中的快速運(yùn)動(dòng)估計(jì)算法［J］.計(jì)算機(jī)工程，2008，34(16):244-246.］