基于最優(yōu)運動矢量預(yù)測過程的改進與優(yōu)化

蔡 宜，周金治+

(1.西南科技大學 信息工程學院，四川 綿陽 621010； 2.西南科技大學 特殊環(huán)境機器人技術(shù)四川省重點實驗室，四川 綿陽 621010)

0 引 言

運動估計(motion estimation，ME)過程占據(jù)了視頻壓縮編碼總體時間的70%(單幀參考)～90%(5幀參考)[1,2]，其中龐大的運算量使得在實時視頻編碼過程中效果不佳，如果能減少ME的運算量將會顯著提高整體編碼效率。為解決上述問題，UmhexagonS算法[3]被H.264/AVC納入采用，相比以往算法，UmhexagonS算法在保證良好率失真的情況下節(jié)省了90%的運算量，但代價是需消耗相對較長的運動估計時間。文獻[4]給出了一種基于方向的UmhexagonS算法，通過方向劃分來確定搜索區(qū)域，縮減運動矢量搜索時間。文獻[5]中提出了一種交叉十字劃分，把搜索區(qū)域劃分為4個小區(qū)域，然而該方法設(shè)置的預(yù)測精度過低，仍存在搜索冗余，這里標記為問題1。文獻[6,7]中改進算法在劇烈運動情景中均節(jié)省了23.8%左右的運動估計時間，而在微運動情景中僅僅節(jié)省了7.4%左右，表明該算法在微運動情景下適應(yīng)能力較差，這里標記為問題2。文獻[8,9]均提到了動矢量具有中心偏置分布特性，然而后者在3×3區(qū)域改進算法中忽略了對中心點搜索，但中心點為最優(yōu)運動矢量點的概率高達45.49%，這里標記為問題3。

本文將在UmhexagonS算法以及相關(guān)文獻的基礎(chǔ)上，從以上3點進行優(yōu)化和改進。

1 UmhexagonS算法原理

UmhexagonS算法是一種混合運動矢量搜索算法，分為粗略搜索、細致搜索和精細搜索3個流程。算法基本流程如下：①聯(lián)合使用多種預(yù)測模型確定起始搜索點；②進行非對稱大十字搜索；③進行5×5矩形搜索；④進行擴展大六邊形搜索，在此環(huán)節(jié)中，需由里到外進行4輪擴展搜索；⑤進行小六邊形循環(huán)搜索，直到當前最優(yōu)匹配點為搜索模板中心為止；⑥進行小鉆石搜索，直到當前最優(yōu)匹配點為搜索模板中心為止，此時算法結(jié)束。搜索模型如圖1所示。

圖1 UmhexagonS算法搜索模型

上述每步中均是以前一步得到的最優(yōu)點為中心展開搜索；在步驟②～步驟③中均引入了判斷閾值來提前終止搜索策略。對當前模板的最佳運動匹配矢量進行率失真代價計算，然后與預(yù)設(shè)閾值T進行比較。當SAD>T2時，繼續(xù)執(zhí)行下一步搜索；當T1

J(MV,λMOTION)=SAD(s,c(MV))+λMOTION×
R(MV-PMV)

(1)

式中：SAD(sum of absoulute different)的計算公式如下

(2)

式中：s表示當前幀中[x,y]的像素值；MVx和MVy分別代表預(yù)測運動矢量的橫向分量和縱向分量；λMOTION為拉格朗日常數(shù)；R(MV-PMV)代表了運動矢量差分編碼可能損耗的比特數(shù)。由于當前運動矢量與預(yù)測運動矢量具有較強的相關(guān)性，所以SAD部分的預(yù)測特性完全可以反映整個匹配函數(shù)的預(yù)測特性，即J(MV,λMOTION)可以等效于SAD。

UmhexagonS算法利用起始點搜索預(yù)測和提前終止預(yù)測等策略使得MET(motion estimation time)得到縮減，并且保證率失真基本不變。然而，MET的縮減是以較高的計算復(fù)雜度為前提。若取默認的16×16搜索范圍，那么在最壞情況下要搜索多達272個點，且對每個點進行匹配誤差計算，這里的計算量是非常龐大的。

2 UmhexagonS算法改進

2.1 搜索區(qū)域改進

針對問題1，研究表明當前塊的運動矢量和參考幀中預(yù)測運動矢量具有高度的相關(guān)性，因此可以通過兩者對最優(yōu)預(yù)測矢量的落入范圍進行預(yù)測。假設(shè)預(yù)測精度滿足規(guī)定的條件，那么最佳預(yù)測矢量必然是落入該范圍的，此時只用搜索該區(qū)域。

(3)

(4)

圖2 前后參考幀預(yù)測矢量

根據(jù)θ即可確定搜索范圍：①當θ∈[0,45°)或θ∈[-45°,0°)時，對應(yīng)搜索區(qū)域1或8；②當θ∈[45°,90°)或θ∈[-90°,-45°)時，對應(yīng)搜索區(qū)域2或7；③當θ∈[90°,135°)或θ∈[-135°,-90°)時，對應(yīng)搜索區(qū)域3或6；④當θ∈[135°,180°)或θ∈[-180°,-135°)時，對應(yīng)搜索區(qū)域4或5，如圖3所示。

圖3 大范圍模型區(qū)域劃分

區(qū)域劃分策略將大范圍搜索模板細化為8個區(qū)域，θ的值會將定位到特定的搜索區(qū)域。相比較UmhexagonS算法，改進后算法的搜索面積縮小到1/8，相比較文獻[5]的十字劃分，改進后算法的搜索面積縮小到1/4。

2.2 運動情景提前分類策略

UmhexagonS算法中引入的非對稱大十字搜索和擴展大六邊形搜索很大程度上優(yōu)化了對劇烈運動情景的預(yù)測效果。然而在微運動情景下，最優(yōu)點通常都積聚在搜索中心點附近，如果仍使用大范圍搜索模型會存在搜索冗余，降低效率。

針對問題2，文獻[10]提出了一種自適應(yīng)的模型切換算法，作者給出了一個基于EDR(error descent rate)模型的內(nèi)容分類器。然而作者僅僅選取了中心點附近的4個點進行采樣，其采樣范圍容易陷入局部最優(yōu)。

依據(jù)單峰值誤差面假設(shè)，當前塊率失真往往隨著與全局最優(yōu)點距離的縮小而單調(diào)遞減[11]。通常全局最優(yōu)點與其周圍像素點的關(guān)系比遠處像素點的關(guān)系要密切很多，越是靠近全局最優(yōu)點，其率失真代價越小，越是遠離全局最優(yōu)點，其率失真代價越大。依據(jù)這一性質(zhì)，我們可以重新設(shè)定搜索策略，當為微運動情景時，采用局部小范圍模型搜索；當為劇烈運動情景時，采用大范圍模型搜索。

圖4給出了最優(yōu)點距離搜索中心越來越遠的4種情況，取坡度比值分別為

(5)

其中，L1最靠近搜索中心點，坡度比最大；L4最遠離搜索中心點，坡度比最小。由此我們可以通過計算搜索中心點與鄰近點的坡度來估計最優(yōu)點與搜索中心的距離。當坡度比值越大，最優(yōu)點距離搜索中心越近；當坡度比值越小，最優(yōu)點距離搜索中心越遠。

圖4 全局最優(yōu)點與中心點距離的率失真表現(xiàn)

經(jīng)過起始點預(yù)測后得到的當前最優(yōu)點是全局最優(yōu)點的概率非常大，那么將以當前起始預(yù)測點為中心，對其周圍相鄰點進行率失真代價計算(步長為一個像素)。圖5中，點A是經(jīng)過起始點搜索后得到的，率失真代價為DA，若測得此時周圍鄰近點DB為最小，那么搜索中心點與最鄰像素點率失真差值為|DB-DA|。由之前討論出的結(jié)論可知，即當|DB-DA|越大時，最優(yōu)點離搜索點中心越近；當|DB-DA|越小時，最優(yōu)點離搜索點中心越遠。這里利用EDR模型，通過三步迭代搜索進行運動情景分類，每次搜索步長均為一個像素

EDR=D最小鄰點/D中心點

(6)

圖5 搜索中心點與周圍鄰點

(1)以起始搜索點A為中心點對鄰域搜索，若測得點B為最小鄰點，此時EDR=DB/DA。當EDR≥1時，表明此時已經(jīng)局部最小，直接終止搜索；當EDR

(2)以點B為中心點，若測得點C為最小鄰點，此時EDR=DC/DB。當EDR

(3)以點C為中心點，重復(fù)以上操作，當T≤EDR<1時，當前為劇烈運動情景。這里的閾值T依據(jù)參考文獻設(shè)置為0.9。

改進后的算法直接分類出3種不同強度的運動情景。當為劇烈運動，仍然從非對稱大十字搜索模型開始依次搜索；當為中等劇烈運動情景，直接從小六邊形開始搜索；當為微運動情景，直接從小鉆石開始搜索。

2.3 5×5螺旋搜索改進

通過對大量自然運動序列分析，現(xiàn)實世界中大多數(shù)圖像序列的塊運動場通常是平滑、緩慢的，主要以水平運動為主。

經(jīng)實驗驗證，約有85.39%的運動矢量非均勻的分布在5×5區(qū)域內(nèi)，而其中分布在3×3區(qū)域的概率高達71.79%。由此可知，運動矢量的中心偏置性同樣體現(xiàn)在了5×5小范圍模板中，即搜索模板中心的運動矢量分布密度遠大于邊緣區(qū)域。針對問題3，本文采取了由內(nèi)向外擴展的搜索順序，如圖6(a)所示，在3×3區(qū)域中D點的概率低至2.78%；5×5邊緣地區(qū)(D+E+F)分布概率低至10.6%，故均予以忽略。首先對中心3×3小十字形進行搜索，然后再向水平方向擴展進行5×5大十字搜索，如圖6(b)所示。對比原算法，改進后的5×5模板只需搜索概率最大的9個點(占5×5全局的87.52%)，相比之下減少了16個點；相比文獻[9]，本文算法在增加了搜索中心點的情況下仍比其少搜索5個點，且搜索區(qū)域的最優(yōu)運動矢量分布概率比其高34.84%。

圖6 5×5區(qū)域運動矢量分布概率

2.4 改進算法總結(jié)

綜上所述，本文改進后算法流程如下：①確定起始搜索點；②進行運動情景分類，若為微運動情景直接跳轉(zhuǎn)到⑦開始執(zhí)行，若為中等劇烈運動情景直接跳轉(zhuǎn)到⑥開始執(zhí)行，若為劇烈運動情景則進行下一步；③計算當前MVC、MVPRE，進行非對稱大十字模型1/8區(qū)域搜索；④進行改進后5×5螺旋搜索；⑤計算當前MVC、MVPRE，進行大六邊形1/8區(qū)域搜索；⑥以前一步獲得的最優(yōu)點為搜索中心進行小六邊形循環(huán)搜索，直到當最優(yōu)匹配點為搜索模板中心為止；⑦以前一步獲得的最優(yōu)點為搜索中心進行小鉆石搜索，直到當最優(yōu)匹配點為搜索模板中心為止，此時算法結(jié)束。算法流程如圖7所示。

圖7 改進后算法總體流程框架

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

將本文改進后算法在官方參考軟件JM12.2模型中進行測試，測試PC配置為Pentium(R) Dual-Core CPU E6300@2.80 Hz，4 G內(nèi)存，操作系統(tǒng)Windows 7。開發(fā)環(huán)境為Visual Studio 2015。encoder.cfg主要參數(shù)設(shè)置如下：編碼幀數(shù)為100；幀率為30；QP=28；搜索范圍為16；參考幀數(shù)為5，其余均為默認設(shè)置。

本文共選取了6種運動強度情景不同的YUV(4∶2∶0)測試序列，分辨率均為176×144。緩慢運動序列：akiyo_qcif，news_cif；中等劇烈運動序列：foreman_qcif，coastguard_qcif；劇烈運動序列：mobile_qcif，football_cif。在測試過程中，測試項PSNR/dB、BR/(kb/s)、ENT/s、MET/s分別代表：Y分量峰值信噪比、輸出碼率、編碼時間、運動估計時間。在測試結(jié)果中，分別用△PSNR(Y)/dB、△Br/%、△MET/%來表征算法性能，計算公式為

ΔPSNR(Y)=PSNR(Y)mod-PSNR(Y)ref

(7)

(8)

(9)

其中，下標mod代表本文改進后算法值，下標ref代表對比算法的值。

表1對6組測試序列分別進行4類算法測試，其中SCUMH代表本文改進后算法。通過分析Full search、UmhexagonS、EPZS這3種參考算法在編碼時間和運動估計時間中的數(shù)據(jù)，發(fā)現(xiàn)在緩慢運動情景下Full search最耗時，EPZS次之，UmhexagonS耗時最少；隨著運動情景劇烈程度的增加，EPZS算法的性能逐漸超越UmhexagonS算法。分析可知，UmhexagonS算法在劇烈運動情景下性能不及EPZS算法，但在微運動情景下性能強于EPZS算法。

依據(jù)表2，改進后算法在劇烈運動情景下MET平均減少了40.53%；在中等劇烈運動情景下平均減少了32.86%；在微運動情景下平均減少了27.05%。對比參考文獻[7]，改進算法在劇烈運動情景下，MET進一步縮減了19.27%；在中等劇烈運動情景下縮減了15.17%；在微運動情景下縮減了19.45%。由以上數(shù)據(jù)可知，改進后算法不僅能極大減少劇烈運動的估計時間，在微運動情景下減少的MET也相當可觀。在劇烈運動情景下，針對問題1提出的區(qū)域劃分策略，縮小搜索面積，節(jié)省了在劇烈運動情景下的搜索時間；在微運動情況下，針對問題2提出的提前情景分類策略，自適應(yīng)地選擇搜索模型，提高了微運動情景下的搜索效率。同時，5×5搜索模型也改進效果明顯。

圖8，圖9分別表示了兩組不同運動強度測試序列的性能，由圖可知，改進后算法在微運動、劇烈運動情景下均縮減了一定比例的運動估計時間，且隨著編碼幀數(shù)的增加，縮減比例也增加；同時，改進算法在率失真方面與UmhexagonS、EPZS算法基本一致，說明本算法保持了與原算法同樣的率失真性能。

圖9 Akiyo與Football在3種算法上率失真對比

4 結(jié)束語

本文以UmhexagonS算法在預(yù)測最優(yōu)運動矢量過程中仍存在較長運動估計時間的問題展開。通過對比現(xiàn)有算法，提出了一種包含運動情景提前分類、大范圍模型區(qū)域劃分、5×5搜索順序改進的3種改進策略的SCUMH算法。實驗結(jié)果表明，對比UmhexagonS算法，在保證PSNR與碼率基本不變的前提下，SCUMH算法不僅在劇烈運動情景中縮減了大量的運動估計時間，且在微運動情景下縮減時間也相當可觀，可適應(yīng)各種復(fù)雜多變的運動情景。

另外，SCUMH算法仍存在需要完善的地方：①本文采取的時間域預(yù)測方式(前后參考幀預(yù)測)可改進為在空間域的預(yù)測，因為在運動矢量預(yù)測過程中后者更為精確；②EDR運動情景分類模型過于粗糙，無法準確表示出中心點與周圍鄰點的偏離程度。