基于最優運動矢量預測過程的改進與優化

蔡 宜，周金治+

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

0 引 言

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

本文將在UmhexagonS算法以及相關文獻的基礎上，從以上3點進行優化和改進。

1 UmhexagonS算法原理

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

圖1 UmhexagonS算法搜索模型

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

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

(1)

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

(2)

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

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

2 UmhexagonS算法改進

2.1 搜索區域改進

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

(3)

(4)

圖2 前后參考幀預測矢量

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

圖3 大范圍模型區域劃分

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

2.2 運動情景提前分類策略

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

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

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

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

(5)

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

圖4 全局最優點與中心點距離的率失真表現

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

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

(6)

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

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

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

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

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

2.3 5×5螺旋搜索改進

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

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

圖6 5×5區域運動矢量分布概率

2.4 改進算法總結

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

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

3 實驗結果與分析

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

本文共選取了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分量峰值信噪比、輸出碼率、編碼時間、運動估計時間。在測試結果中，分別用△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種參考算法在編碼時間和運動估計時間中的數據，發現在緩慢運動情景下Full search最耗時，EPZS次之，UmhexagonS耗時最少；隨著運動情景劇烈程度的增加，EPZS算法的性能逐漸超越UmhexagonS算法。分析可知，UmhexagonS算法在劇烈運動情景下性能不及EPZS算法，但在微運動情景下性能強于EPZS算法。

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

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

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

4 結束語

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

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