稀疏統計二次Renyi 熵的運動估計匹配準則

鄧志超，汪同慶

(重慶大學光電技術及系統教育部重點實驗室，重慶 400044)

1 概述

在數字視頻壓縮編碼領域，已經先后形成了H.261，MPEG -1，MPEG -2，H.263，MPEG -4，H.264/AVC等一系列視頻編碼標準［1-2］，然而由于編碼標準的復雜度越來越高，這就對編碼時間提出了更高的要求。基于此，運動估計［3］作為視頻編碼的核心技術就顯得尤為重要。塊匹配［4］運動估計算法由于原理簡單和易于軟硬件實現而被廣泛應用，其中匹配準則和搜索模式作為塊匹配運動估計的兩大重要因素一直是人們研究的熱點［5］。匹配準則通常是描述當前圖像塊與參考圖像塊之間近似程度的函數，通過分析，運動估計的準確性很大程度上依賴于塊匹配過程中選用的匹配準則，一個能夠快速精確地描述塊匹配程度的匹配準則將會極大地改善算法性能，所以對匹配準則的研究與改進具有十分重要的意義。盡管如此，以往的研究重點都集中在搜索模式上，對匹配準則卻沒有得到有效的關注，大部分直接采用傳統匹配準則如絕對誤差和函數(Sum of Absolute Difference，SAD)和均方誤差函數(Mean Square Error，MSE)作為搜索模式的匹配準則［6］。

針對傳統匹配準則描述塊匹配精度不高的不足，本文提出一種稀疏統計二次Renyi 熵［7-8］(Quadratic Renyi's Entropy，QRE)的運動估計匹配準則。該準則發揮了二次Renyi 熵在評價殘差圖像的剩余信息量較為準確的優勢，在計算QRE 時引入統計直方圖來計算概率密度函數，并結合基于梯度的圖像質量評價和運動矢量中心偏離特性，對直方圖的統計進行稀疏化。實驗采用了全搜索算法作為搜索模式［9］，分別對SAD，MSE 和QRE 匹配準則進行了對比分析，并針對QRE 匹配準則需要進行乘法運算的不足，進一步將QRE 中引入的統計直方圖進行稀疏優化，并將稀疏前后的峰值信噪比［10］和乘法運算量進行了對比。

2 QRE 匹配準則

1948 年，克勞德·香農提出了用來表示信息內容大小的信息熵，即香農熵［8］。用香農熵來表示幀間運動估計中殘差圖像塊的信息量是最為準確的。數學家Renyi 又提出了意義更為廣泛的Renyi 熵。在不知道概率密度函數的前提下，可以通過非參數法即帶核函數的Parzen 窗來估計連續變量的二次Renyi 熵。本文為了簡化匹配函數，提高運算效率，也引入了二次Renyi 熵。如果能夠保證當前圖像塊與參考幀圖像塊相減之后，得到的殘差圖像塊的二次Renyi 熵最小，那么這兩個圖像塊的內容最接近，經過編碼之后的信息冗余也就越少。

2.1 Renyi 熵

給定一個隨機變量e，它的Renyi 熵可以定義為:

其中，f(e)為變量e 的概率密度函數。

在式(1)中，當α→1 時，根據洛比達法則，α 次Renyi 熵就收斂為香農熵。

當α=2 時，隨機變量e 的Renyi 熵就成為二次Renyi 熵，即:

為了進一步簡化匹配函數，選用式(3)作為匹配準則，則有:

定義變量H，使得:

其中，變量e 對應的是殘差圖像塊中任意像素點的亮度值或色度值。當變量e 滿足式(5)時，殘差圖像塊的二次Renyi 熵就最小，當前圖像塊與參考圖像塊就是最佳匹配塊。

2.2 統計直方圖

由于殘差圖像塊每個像素點亮度與色度的取值都是有限個離散值，其概率密度函數也是離散的。為了有效地計算式(7)所表示的匹配函數，引入了統計直方圖。如果視頻圖像的各個分量有I 個不同的取值，那么可以構造出組數為I 的統計直方圖。構造統計直方圖并求得匹配函數值的具體步驟如下:

(1)將殘差圖像塊作為樣本，統計各個組區間的頻數γi，0 ＜i ＜I。

(2)根據頻數求各個組區間的頻率fi:

(3)將每個組區間的頻率代入式(5)可得到匹配函數值。

根據各個組區間的頻率，匹配函數可以寫為:

基于二次Renyi 熵的快速搜索算法整體流程如下:

(1)確定圖像塊分割的大小和搜索窗口大小，開始菱形搜索算法。

(2)將當前圖像塊與參考圖像塊相減，得到殘差圖像塊。

(3)針對殘差圖像塊色彩空間的每個分量，構造統計直方圖并根據式(7)求得基于二次Renyi 熵的匹配函數值。

(4)將當前得到的值與保存的最小匹配函數值比較，如果小于則將當前值保存。或者當前值小于某一閾值時，結束搜索，完成當前圖像塊的匹配。

(5)判斷是否完成搜索任務。如果完成，結束當前圖像塊的匹配搜索;否則重復步驟(1)。

2.3 常用匹配準則

為了更為清晰地體現出所提出匹配準則的不同之處，以便作對比，下面將對幾種常用的匹配準則作簡要介紹。

SAD 匹配準則定義如下:

MSE 匹配準則定義如下:

上述兩式中，(p，q)表示運動向量;D(x，y)表示當前圖像塊;DR(x，y)表示參考幀中的圖像塊;M，N分別表示圖像塊的寬度與高度;(x，y)表示運動向量。當SAD(p，q)或者MSE(p，q)取得最小值時即為最優匹配運動向量(p，q)。SAD 匹配準則由于不需要作乘法運算，實現簡單方便，因此使用廣泛。

3 QRE 的稀疏統計

QRE 是通過細節反映數據大小波動的較好體現，用當前塊與參考塊像素差值的二次Renyi 熵衡量前后改變情況，既能微觀地反映圖像誤差較大區域，即局部誤差顯著區域，又能宏觀地反映整體誤差情況。然而，與SAD 匹配準則相比，QRE 的缺點在于需要進行乘法運算，需要耗費更多的運算資源，因此，對QRE 匹配準則進行優化顯得很有必要。

3.1 統計直方圖區間的線性化

為了在乘法運算量上得到改進，結合人眼在實際觀察中基于梯度的圖像質量評價方法［11］，可以對統計直方圖中各個區間作進一步的稀疏處理［12］，如圖1 所示。區間可設置為2，4，8，2n等，即統計直方圖區間的線性化，當然稀疏程度要限定在一定的范圍內以確保圖像梯度結構評價方法的有效性。由于灰度圖像的像素值分布在區間(0，255)，因此殘差圖像灰度圖像的像素值必將分布在區間(-255，255)，每當進行一次區間稀疏處理，必將減少與之相應的乘法運算量。

圖1 統計直方圖線性稀疏處理

3.2 統計直方圖區間的閾值分類

以上簡單稀疏處理從理論上來說可以減少乘法運算量，但是隨著稀疏程度的增加，誤差會加劇。基于此，根據運動矢量中心偏離特性［13］，殘差圖像的像素差值理論上將集中在中間區域，即零點附近區域。因此，結合以上稀疏處理的方法，可以設定一個閾值T0，將(-T0，T0)區域內作輕度稀疏處理或不作稀疏處理，將其他區域作重度稀疏處理，如圖2 所示，即統計直方圖區間的閾值分類［14］稀疏處理。這樣不僅可以減少乘法運算量，同時也解決了因為稀疏化帶來的誤差加劇的問題。

圖2 統計直方圖閾值分類稀疏處理

4 實驗結果與分析

本文的實驗工作平臺參數如下:處理器為Intel Pentium4 2.40 GHz，內存2 GB，操作系統為Ubuntu 10.04(系統內核:Linux 2.6.32-45-generic)，編譯環境為GNU/GCC4.3，代碼編輯環境為Vim+Cscope。

為了全面地比較各種匹配函數之間的性能差異，選取了5 組在運動幅度、運動方向和運動物體數量與大小上各不相同的測試視頻序列作為實驗數據對象，即flower，container，coastguard，bus 和football，分辨率均為CIF(352 ×288 像素)。這5 組視頻序列都存在著不同物體不同的運動方式，其中，flower 序列主要表現為水平運動，主要有相機的移動與人物的行走，運動物體較小，運動幅度較大;container 序列主要表現的也是水平運動，但運動物體較大，運動幅度較小，主要是大貨輪的運動;coastguard 序列主要體現在水平方向上海岸警衛汽艇和游艇兩者的運動，汽艇運動幅度較大，游艇運動幅度較小;bus 序列主要體現為水平方向上的汽車移動，且運動幅度相對較大;football 序列主要表現為垂直與水平方向上的劇烈運動，能夠更好地測試匹配準則對于復雜運動的適應能力。同時由于標準視頻序列中缺少在垂直方向上運動變化，因此本文拍攝了2 段視頻，這2 段視頻序列的特點是圖像中存在垂直方向上的不同幅度的運動，自拍2 較自拍1 運動幅度大。

實驗將每幀圖像大小依據常用區分模式，分成為16 ×16 像素互不重疊的圖像塊，以第i-2 幀圖像作為第i 幀的參考幀，分別根據不同的匹配準則來搜索最佳匹配塊，并對運動估計后的每幀圖像進行運動補償，計算出補償幀與當前幀的PSNR 值。

為了描述整體的匹配效果，表1 給出了在相同的輸出碼率情況下，各個視頻前30 幀圖像在不同的匹配準則下的平均PSNR 值，搜索方式為全搜索。PSNR 值越大，表示匹配精度就越高，完成運動估計的效果也就越好。匹配準則選取SAD，MSE，QRE 作為對比，ΔPSNR 表示與SAD 匹配準則的PSNR 值之差。

表1 視頻序列PSNR 值對比 dB

從實驗結果可以看出，針對以上各種運動方式的視頻序列，采用不同的匹配準則所得到的結果存在差異。從整體匹配效果來看，QRE 匹配準則所得到的平均PSNR 值最高，效果明顯優于SAD 與QRE匹配準則，驗證了第2 節的理論。對于container 和自拍1 視頻序列，可以看出，QRE 準則對于運動幅度小的情況優勢不明顯，從其他視頻序列看，QRE 對于水平、垂直或其他方向運動幅度大的視頻序列，優勢較為明顯。

表2 考察了統計直方圖線形稀疏處理后運動估計的效果，在稀疏處理的過程中，分別將區間寬度設置為2 的整數倍，直至ΔPSNR 值為負數(ΔPSNR 表示與SAD 匹配準則的PSNR 值之差)，即運動估計效果劣于SAD 準則，同時對各種情況下乘法計算量減少的百分比作了統計。從得到的數據結果來看，隨著稀疏化程度的增強，乘法運算量急劇下降，但PSNR 值也隨之下降，與前文的理論分析結果相符。

表3 考察了統計直方圖閾值分類稀疏處理后運動估計的效果，在稀疏處理的過程中，通過對實驗對象標準視頻序列和自拍兩組序列的綜合評定，設定閾值為16，分別將閾值區間內與閾值區間以外區域的區間寬度設置為4 和32，這樣閾值區間內外分別有8 個和30 個區間，總共38 個區間，相對線性化稀疏處理方法，總體上在保證PSNR 值高于SAD 匹配準則的基礎上，使得乘法運算量進一步減少，減少量可以達到80%以上。對于container 視頻序列，由于其運動物體大，運動幅度較小，可以看出，基于QRE匹配準則對運動幅度大的視頻序列效果明顯。

表2 統計直方圖線性稀疏處理結果

表3 統計直方圖閾值分類稀疏處理結果

5 結束語

本文將二次Renyi 熵引入到運動估計匹配準則中，并采用稀疏統計的方法對直方圖的進行統計，提出了一種稀疏統計二次Renyi 熵的運動估計匹配準則。從匹配乘法運算量和匹配效果出發，依據基于梯度的圖像質量評價和運動矢量中心偏離特性，通過對統計直方圖每個區間的線性全局稀疏、線性區域化稀疏以及非線性閾值化稀疏，不斷完善匹配準則的匹配方式。實驗結果表明，該匹配準則對運動劇烈視頻序列的運動估計效果明顯，恢復的圖像質量優于SAD 匹配準則。從實驗的數據來看，稀疏區間的大小和閾值的設定決定了匹配的效果，下一步工作需要對稀疏區間的大小和整個區間的閾值設定作進一步研究。

［1］Vani R，Sangeetha M.Survey on H.64 Standard［M］.Berlin，Germany:Springer，2012.

［2］Richardson I E.The H.264 Advanced Video Compression Standard［M］.［S.l.］:John Wiley ＆ Sons，2011.

［3］Dhamande C S，Bhalge P A.Overview of Motion Estimation in Video Compression［J］.International Journal of Scientific ＆ Engineering Research，2013，4(6):116-120.

［4］Barjatya A.BlockMatching Algorithms for Motion Estimation［J］.IEEE Transactions Evolution Computation，2004，8(3):225-239.

［5］HuangYuwen，Chen Chingye，Cai Chenhan，et al.Survey on Block Matching Motion Estimation Algorithms and Architectures with New Results［J］.Journal of VLSI Signal Processing，2006，42(3):297-320.

［6］YuFei，Hui Mei，Han Wei，et al.The Application of Improved Block-matching Method and Block Search Method for the Image Motion Estimation［J］.Optics Communications，2010，283(23):4619-4625.

［7］Ramachandran G，Krishnan V，Wu Dapeng，et al.A Model-based Adaptive Motion Estimation Scheme Using Renyi's Entroy for Wireless Video［J］.Journal of Visual Communication and Image Representation，2005，16:432-449.

［8］ErdogmusD，Principe J C.Comparion of Entropy and Mean Square Error Criterion in Adaptive System Training Using Higher Order Statistics［C］//Proc.of International Workshop on Independent Component Analysis and Signal Separation.Helsinki，Finland:［s.n.］，2000:75-80.

［9］Luo Jun，Peng Jiaxin.An Unsymmetrical Diamond Search Algorithm for H.264/AVC Motion Estimation［C］//Proc.of Conference on Image and Graphics Technologies.Berlin，Germany:［s.n.］，2013:54-65.

［10］Hore A，Ziou D.Image Quality Metrics:PSNR vs.SSIM［C］//Proc.of the 20th International Conference on Pattern Recognition.Istanbul，Turkey:［s.n.］，2010:2366-2369.

［11］Zhou Wang，Bovik A C，Simoncelli E P.Image Quality Assessment:From Error Visibility to Structual Similarity［J］.IEEE Transactions on Image Processing，2004，13(4):600-612.

［12］崔 琛，沙正虎，李 莉，等.基于SURE 估計的圖像塊稀疏收縮去噪算法［J］.計算機工程，2012，38(23):231-235.

［13］倪 偉，郭寶龍，丁貴廣.基于運動矢量場和方向自適應的快速運動估計算法［J］.電子與信息學報，2006，28(12):2277-2282.

［14］Nafis U K，Arya K V，Pattanaik M.Histogram Statistics Based Variance Controlled Adaptive Threshold in Anisotropic Diffusion for Low Contrast Image Enhancement［J］.Signal Processing，2013，93 (6):1684-1693.