基于結構相似度的快速運動估計算法

摘要：基于人眼視覺系統和視覺域抽取的結構信息高度相關的原理，提出了一種基于結構相似度的快速運動估計算法(FMEBS)。該算法針對H.264率失真優化算法存在的不足，引入基于結構相似度的圖像質量衡量標準，對失真度的表示進行修正，并采用快速的模式選擇算法和有效的搜索模板。實驗表明，在獲得相近重建圖像質量的前提下，FMEBS算法較之全搜索算法可節省約2.7%的比特率和91.2%用于運動估計的時間，較之UMHexagonS算法可節省約1.9%的比特率和35.6%的時間。

關鍵詞：H.264；率失真優化；結構相似度；運動估計

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2007)11-0306-03

新一代視頻壓縮標準H.264/AVC[1，2]，由于采用了一系列先進的編解碼技術，如幀內預測、整數變換、高精度運動估計算法、基于上下文的自適應二進制算術編碼(CABAC)、多參考幀運動估計等，在壓縮效果和對不同網絡的適應性等方面都取得了明顯的進步。與以往的標準相比，在相同編碼質量下，H.264可以節約大約50%的碼率。H.264/AVC采用多種塊模式的幀間預測，通過率失真優化算法（RDO）確定最優的匹配模式。率失真優化算法采用誤差平方和(SSD)來表示重建圖像與原始圖像之間的失真度，然而，這種對各圖像相應點的差值運算并不能完全符合人眼視覺系統（HVS）特性，準確地給出主觀的視頻質量值[3，4]；同樣，采用峰值信噪比（PSNR）來測量視頻圖像的質量也具有局限性。另外，通過RDO選擇最優塊模式需對所有的七種模式進行全搜索，這種方法在提高準確率的同時使得處理時間線性上升，計算復雜度大大增加。

本文針對以上提出的兩點不足，基于HVS與視覺域抽取的結構信息高度相關的特點，提出了一種新的運動估計方法。在視頻圖像質量的評價方面，引入一種新的基于結構相似度（SSIM）的圖像質量標準來衡量重建圖像與原始圖像的相似程度，取代了傳統的SSD及PSNR。在塊模式判定方面，根據運動矢量自身的特性，提出了簡單有效的快速模式判斷算法，有效地減少了宏塊的候選模式；同時，采用高效的搜索模板和搜索策略自適應地對各模式進行快速搜索。實驗結果顯示在保證重建圖像質量的前提下，該算法兼具快速與低比特率兩方面性能的優勢，更利于實時應用。



1基于結構相似度的快速運動估計算法（FMEBS）

1．1基于結構相似度的RDO算法

H.264采用多種塊模式的幀間預測，在可選的宏塊類型中遍歷每種可用塊模式，計算出每種模式下的編碼比特數，相應地重建圖像失真度，根據公式：

計算拉格朗日函數值J，即率失真開銷，經過比較，選取最小值下的塊模式MODE作為宏塊的最終編碼模式。其中：QP為宏塊的量化參數；s、c分別表示原始圖像和重建圖像的像素值；R（s，c，MODE|QP）表示在特定QP和MODE下當前宏塊的編碼輸出比特數；D（s，c，MODE|QP）為重建圖像與原始圖像之間的誤差平方和，表示圖像失真度。

然而，HVS是一個復雜和高度非線性的系統，SSD這種基于圖像相應點差值的類線性運算方法具有多種局限性[3]，如圖像質量定義的準確性、超閾值性及認知相關性等問題，并不能與HVS相適應，準確地衡量圖像的質量。它的廣泛使用源于其低計算復雜度以及清晰的物理意義，且HVS的復雜性進一步加大了尋找一種準確的圖像評價標準將其取代的難度。所以，采用SSD作為失真度的率失真優化算法同樣不能準確選擇最佳塊模式，有效節省比特率。

為解決該問題，文獻[3，4]基于HVS與視覺域抽取的結構信息高度相關的特點，提出了一種新的圖像質量衡量標準，并經分析得到以結構信息的變化為衡量，能最為近似地反映圖像失真的結論。首先，該方法采用結構信息的變化來判斷圖像質量下降的程度，從整體視覺感覺上符合人們的主觀評價標準。其次，通過自上而下對整個HVS虛擬函數的模擬，一方面避免了超閾值問題；另一方面也在一定程度上減少了認知相關性的影響。再次，它采用對兩幅圖像的結構信息直接進行比較而不是進行差值計算的方法，一定程度上避免了圖像復雜度與其相關問題。

本文引入該圖像質量評價標準——結構相似度（SSIM），它通過對圖像三個方面信息的比較來計算結構信息的變化，較之傳統的圖像質量衡量方法，可以更準確地量測圖像的失真度[4]。SSIM定義為

如表1~3中數據所示，在獲得相近重建圖像質量的前提下，FMEBS算法較之全搜索算法可節省約2.7%的比特率和91.2%用于運動估計的時間，較之UMHexagonS可節省1．9%的比特率和35.6%的時間。

為了更直觀地比較采用各算法所得重建圖像的圖像質量，在圖2中給出了foreman第62幀原始圖像及QP=30時采用FS、UMHexagonS和FMEBS算法所得的重建圖像。從圖中可以看到，通過FMEBS所得到的重建圖像與FS、UMHexagonS算法得到的非常相近，并在QP相對較大的情況下仍與原圖像差異很小。同時，比特率相對于其他兩種算法不同程度的下降說明引入SSIM來衡量失真度，可以使修正后的RDO算法選擇最佳的匹配塊，這樣殘差用于編碼的比特數也更低了。而運動估計時間的大幅度降低是由于FMEBS充分考慮了運動矢量的方向特性，采用了快速的模式選擇算法和方向性菱形搜索模板，去除了模式選擇及搜索過程中的冗余。

同時也注意到，引入的SSIM的計算復雜度要高于傳統的SSD，而RDO本身便具有高計算復雜度，這樣必將浪費部分編碼時間。如何以SSIM為衡量來簡便快捷地直接選擇最佳匹配塊，從而取代高計算量的RDO算法，將是筆者下一步工作的重點。

3結束語

根據HVS的特點，針對H.264率失真優化算法中存在的不足，本文采取了一種基于結構相似度（SSIM）的快速運動估計算法，它采用SSIM作為視頻圖像質量的衡量標準，從而對RDO算法中失真度的表示進行了修正；同時采用快速的模式選擇算法有效地排除了宏塊的候選冗余模式，并針對宏塊模式類型選擇相應的搜索模板進行搜索。通過改進得到的FMEBS兼有低比特率和低運動估計時間的特點，更符合實際應用中實時性的要求。實驗結果表明該算法與全搜索算法及UMHexagonS算法相比，既保證了編碼質量，又節省了比特率，并大大提高了運動估計的速度，減少了編碼時間，是一種綜合性能優良的快速運動估計算法。

參考文獻：

［1］ITU－T ISO/IEC.H.264－ISO/IEC 14496－10 AVC，Advanced video coding for generic audio visual services [S].

[2]WILEGAND T，SULLIVAN G J，BJONTEGAARD G，et al.Overview of the H.264 video coding standard[J].IEEE Trans on Circuits and Systems for Video Technology，2003，13(7):560-576.

[3]WANG Z，BOVIK A C，LU Li－gang.Why is image quality assessment so difficult[C]//Proc of IEEE Int Conf on Acoustics，Speech， and Signal Processing.Orlando: [s.n.]，2002:3313-3316.

[4]WANG Zhou，BOVIK A C，SHEIKH H R，et al.Image quality assessment:from error visibility to structural similarity[J].IEEE Trans onImage Processing，2004，13(4):600-612.

[5]WILEGAND T，GIROD B.Lagrangian multiplier selection in hybrid video coder control[C]// Proc of International Conferance on Image Processing.Berlin:Springer－Verlag，2001.

[6]SULLIVAN G J，WIEGAND T.Rate－distortion optimization for video compression[J].IEEE Signal Processing Magazine，1999，15(6):74-90.

[7]CHEN Zhi－bo，ZHOU Peng，HE Yun，et al.JVT－G016， fast motion estimation for JVT[S].[S.l.]:Joint Video Team，2003.

[8]向友君，郭寶龍.基于起點預測的快速運動估計算法[J].西安電子科技大學學報，2003，30(3):386-390.

[9]JIA Hong－jun，ZHANG Li.Directional diamond search pattern for fast block motion estimation[J].IEEE Electronics Letters，2003，39(22):1581－1583.

[10]JVT.JM90[EB/OL].(2005).http://iphome.hhi.de/suehring/tml/do wnload/old_jm/jm90.zip.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”