稀疏統(tǒng)計(jì)二次Renyi 熵的運(yùn)動估計(jì)匹配準(zhǔn)則

鄧志超，汪同慶

(重慶大學(xué)光電技術(shù)及系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室，重慶 400044)

1 概述

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

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

2 QRE 匹配準(zhǔn)則

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

2.1 Renyi 熵

給定一個(gè)隨機(jī)變量e，它的Renyi 熵可以定義為:

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

在式(1)中，當(dāng)α→1 時(shí)，根據(jù)洛比達(dá)法則，α 次Renyi 熵就收斂為香農(nóng)熵。

當(dāng)α=2 時(shí)，隨機(jī)變量e 的Renyi 熵就成為二次Renyi 熵，即:

為了進(jìn)一步簡化匹配函數(shù)，選用式(3)作為匹配準(zhǔn)則，則有:

定義變量H，使得:

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

2.2 統(tǒng)計(jì)直方圖

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

(1)將殘差圖像塊作為樣本，統(tǒng)計(jì)各個(gè)組區(qū)間的頻數(shù)γi，0 ＜i ＜I。

(2)根據(jù)頻數(shù)求各個(gè)組區(qū)間的頻率fi:

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

根據(jù)各個(gè)組區(qū)間的頻率，匹配函數(shù)可以寫為:

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

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

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

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

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

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

2.3 常用匹配準(zhǔn)則

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

SAD 匹配準(zhǔn)則定義如下:

MSE 匹配準(zhǔn)則定義如下:

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

3 QRE 的稀疏統(tǒng)計(jì)

QRE 是通過細(xì)節(jié)反映數(shù)據(jù)大小波動的較好體現(xiàn)，用當(dāng)前塊與參考塊像素差值的二次Renyi 熵衡量前后改變情況，既能微觀地反映圖像誤差較大區(qū)域，即局部誤差顯著區(qū)域，又能宏觀地反映整體誤差情況。然而，與SAD 匹配準(zhǔn)則相比，QRE 的缺點(diǎn)在于需要進(jìn)行乘法運(yùn)算，需要耗費(fèi)更多的運(yùn)算資源，因此，對QRE 匹配準(zhǔn)則進(jìn)行優(yōu)化顯得很有必要。

3.1 統(tǒng)計(jì)直方圖區(qū)間的線性化

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

圖1 統(tǒng)計(jì)直方圖線性稀疏處理

3.2 統(tǒng)計(jì)直方圖區(qū)間的閾值分類

以上簡單稀疏處理從理論上來說可以減少乘法運(yùn)算量，但是隨著稀疏程度的增加，誤差會加劇。基于此，根據(jù)運(yùn)動矢量中心偏離特性［13］，殘差圖像的像素差值理論上將集中在中間區(qū)域，即零點(diǎn)附近區(qū)域。因此，結(jié)合以上稀疏處理的方法，可以設(shè)定一個(gè)閾值T0，將(-T0，T0)區(qū)域內(nèi)作輕度稀疏處理或不作稀疏處理，將其他區(qū)域作重度稀疏處理，如圖2 所示，即統(tǒng)計(jì)直方圖區(qū)間的閾值分類［14］稀疏處理。這樣不僅可以減少乘法運(yùn)算量，同時(shí)也解決了因?yàn)橄∈杌瘞淼恼`差加劇的問題。

圖2 統(tǒng)計(jì)直方圖閾值分類稀疏處理

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

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

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

實(shí)驗(yàn)將每幀圖像大小依據(jù)常用區(qū)分模式，分成為16 ×16 像素互不重疊的圖像塊，以第i-2 幀圖像作為第i 幀的參考幀，分別根據(jù)不同的匹配準(zhǔn)則來搜索最佳匹配塊，并對運(yùn)動估計(jì)后的每幀圖像進(jìn)行運(yùn)動補(bǔ)償，計(jì)算出補(bǔ)償幀與當(dāng)前幀的PSNR 值。

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

表1 視頻序列PSNR 值對比 dB

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

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

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

表2 統(tǒng)計(jì)直方圖線性稀疏處理結(jié)果

表3 統(tǒng)計(jì)直方圖閾值分類稀疏處理結(jié)果

5 結(jié)束語

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

［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，F(xiàn)inland:［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ì)的圖像塊稀疏收縮去噪算法［J］.計(jì)算機(jī)工程，2012，38(23):231-235.

［13］倪 偉，郭寶龍，丁貴廣.基于運(yùn)動矢量場和方向自適應(yīng)的快速運(yùn)動估計(jì)算法［J］.電子與信息學(xué)報(bào)，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.