選擇性計算的快速非局部均值圖像去噪

羅學剛，呂俊瑞，王華軍，楊 強

?

選擇性計算的快速非局部均值圖像去噪

羅學剛1,2，呂俊瑞2，王華軍1，楊 強1

(1. 攀枝花學院數學與計算機學院 四川攀枝花 617000; 2. 成都理工大學地球探測與信息技術教育部重點實驗室 成都 610059)

針對非局部均值(NLM)圖像去噪算法度量像素間的相似性計算強度高的問題，提出了一種選擇性計算的快速NLM去噪方法。在圖像塊像素灰度值向量空間距離計算時，利用L2范數逐次消元法，只需在圖像積分圖上通過少量加法運算即可剔除大量相似性低的像素點，有效地減少計算強度。根據圖像空間相關性強的特點，提出了基于patch測地線距離的動態(tài)調整搜索區(qū)域的方法。實驗結果表明，與其他經典算法相比，該方法獲得了較好的加速，也提升了NLM算法的去噪性能。

圖像去噪; 非局部均值; patch測地線; 選擇性計算; 逐次消元法

圖像在采集或傳輸過程中不可避免地受到噪聲污染，造成圖像質量的退化。這樣的圖像不僅影響視覺效果，而且還阻礙了圖像視頻編碼、識別、場景理解等計算機視覺應用。因此，圖像去噪一直是圖像處理中一個重要的研究課題。高效合理地去除噪聲，同時保留圖像原本的特性是去噪算法的關鍵。

針對圖像去噪，研究人員提出大量的算法。這些算法主要在空間域或頻率域上利用濾波技術重建圖像。以Gaussian濾波去噪為主的算法平滑效果好，但是邊緣輪廓以及圖像結構遭到破壞；另一方面，以各向異性濾波去噪為主的算法具有較好的保邊效果，但易引入階梯人造特征。文獻[1]提出了一種異于傳統(tǒng)去噪算法的新方法——非局部均值(non-local means，NLM)去噪算法，利用局部圖像塊(patch)冗余結構信息，將圖像中結構相似的像素采用加權平均來獲得去噪估計值。由于圖像塊比單個像素更好地表達圖像結構信息，在不損失圖像細節(jié)的情況下表現出優(yōu)良的去噪性能，故其性能優(yōu)于其他的經典去噪算法。NLM雖然性能優(yōu)越，但效率與參數需要進一步優(yōu)化。近年，很多學者對NLM提出了改進方法，這些方法主要集中在以下方面：1) 降低計算復雜度(K-SVD[2-3]、DCT[4]、Walsh-Hadamard投影[5]、主成分分析[6-7])。2) 優(yōu)化參數[8-12](平滑核參數、相似鄰域的尺寸和搜索區(qū)域的大小)，提高性能。3) 以NLM思想為基礎，融合其他算法以提升去噪性能[13-14]。

本文針對NLM算法存在的問題，提出以下改進：1) 針對算法計算復雜度高的問題，在搜索窗口內可能有很多不相似的塊，利用2范數逐次消元法，在圖像積分圖上通過剔除預測結構相似性低的圖像塊，避免大量的歐氏距離計算，有效地降低算法運行時間。2) 針對固定搜索窗口去噪性能的問題，利用圖像空間相關性強的特點以及剔除相似性低的圖像塊比率，提出基于Patch測地線距離尋找同質信息的動態(tài)調整搜索范圍的方法。從PNSR和SSIM數值和視覺上可以看出，邊緣去噪效果與經典的NLM算法相比有較好的提高，同時也節(jié)約時間開銷。

1 NLM去噪算法描述

一般加性噪聲圖像的去噪模型可表示為：

(1)

其中

2 選擇性計算及自適應搜索區(qū)域的NLM算法

由于經典的NLM算法的去噪效果好，大量文獻都希望通過降低計算復雜度來改進算法，以此達到推廣應用的目的，其中降低度量像素間的相似性計算量是主要的改進方向。文獻[2]提出利用K-SVD(singular value decomposition)分解技術降低維數從而減少計算量。文獻[4]在離散余弦變換的低頻系數子空間內度量像素間的相似性。文獻[5]利用Walsh-Hadamard變換的快速運算和能量集中特性，通過投影到低維子空間進行度量像素點之間的相似性，減少高維計算。文獻[6-7]通過主成分分析方法將圖像塊投影到低維子空間，并在該低維子空間中度量像素點之間的相似性。文獻[15]利用圖像塊的均值和方差聚類圖像塊避免權值低的圖像塊的歐氏距離計算。這些方法主要是通過變換在子空間里度量相似性，減少計算時間，但同時會影響去噪效果。

本文的思路與文獻[15]具有一定的相似，利用選擇性計算歐氏距離降低運行時間。通過逐次消元法判定剔除相似性低的圖像塊。文獻[15]需要計算圖像塊的均值和方差并聚類，本文的方法僅需簡單的加法運算，從而大幅度地降低了計算量。

2.1 基于逐次消元法的加速策略

逐次消元法[16]本質上是一種利用范數不等式淘汰冗余點的快速全局搜索算法，減少平均絕對差(mean absolute difference，MAD)和計算量，有效地降低算法復雜性，同時可以提供與全搜索算法相同的結果。逐次消元法在視頻目標運動估計等應用中取得良好的效果。

表示以(，)為中心的圖像塊像素灰度值的向量，(,)表示搜素窗口內的以(,)為中心的圖像塊像素灰度值的向量。首先考慮L1范數相似度度量方式應用不等式，其中=，=(,)，，。

(2)

式(2)中的高斯加權計算可以忽略。在搜索窗口中可能有很多不相似的圖像塊，在去噪估計時，這些圖像塊對應的像素分配的權重越小越好。由于NLM算法使用指數形式的權重函數，當不相似的圖像塊較多時，這些小的權重值總和將較大，這對去噪過程將產生不利影響。因此，本文的NLM算法不再用搜索窗口中所有的像素點，而是在搜索窗口中選取個權值最高的圖像塊對應像素點進行加權去噪，一般設置為，為閾值。假設坐標為(,)的像素點為當前第個候選參與坐標為(,)的像素點去噪估計點，有：

(6)

(7)

通過式(5)、式(6)對原圖像每個像素一次訪問便可計算出圖像積分圖，用式(7)可以快速計算出圖1中窗口的像素值和。

圖1 計算窗口S(x, y)的積分示意圖

積分圖創(chuàng)建以后，只需要進行7次加法和1次除法運算，可以得出逐次消元法淘汰冗余點的條件。由于需要尋找前個權值高的像素點，在極端情況下，如果每次檢查點都滿足式(3)，那么采用逐次消元法并不能降低其計算量。為了減少該情況發(fā)生，在計算圖像塊間距離前，先對搜索窗口內所有圖像塊與以(,)點構成的圖像塊以均值為度量進行類聚，選出個與(,)點均值最近的像素點，作為起始選擇點。圖像塊的均值利用積分圖可以在初始時一次性計算得到，因此，時間復雜度并不會增加太多。

2.2 動態(tài)搜索區(qū)域

傳統(tǒng)的NLM算法為了減少計算量，搜索范圍由整個圖像區(qū)域壓縮到中心像素周圍一定大小的區(qū)域，稱為搜索窗口。固定搜索窗口對像素之間的結構信息有較好的保留，然而沒有考慮到圖像的同質信息，不能充分利用相似性高的像素點。由于同質信息能較好地反映圖像的相似信息，對去噪更有利。根據圖像的同質信息，動態(tài)調整搜索窗口，獲得每個像素點的自適應搜索區(qū)域，去噪效果將更加理想。針對該問題，本文提出一種基于Patch測地線(patch geodesic path，PatchGP)距離尋找同質信息動態(tài)調整搜索窗口的方法。

文獻[18]提出以近似估計PatchGP為圖像塊之間相似性的NLM去噪，對邊緣信息去噪效果好以及圖像細節(jié)保留較完整，但對低頻噪聲去除不夠理想，平滑區(qū)域易出現塊狀斑跡。由于PatchGP既可以反映圖像相似結構，又能利用測地線距離找到同質信息。因此，本文根據PatchGP為線索搜尋同質信息來動態(tài)調整搜索窗口的方向與大小。

在圖像中的圖像塊和的PatchGP定義為：

(8)

a. 標準圖像Barbara b. 手臂部分

圖2 PatchGP調整搜索范圍

圖2b所示為圖2a標準圖像Barbara的手臂部分，圖像塊與1、2、3相比，1、3與結構更相似。在搜索窗口里，3被漏掉，沒有充分利用圖像結構冗余的特點尋找到同質區(qū)域。采用以中心像素的區(qū)域計算相似度，然后在區(qū)域邊緣像素和中心像素使用式(8)的計算相似度，采用式(10)得到最小PatchGP的邊緣點，以該邊緣點為邊緣中心向外擴展區(qū)域，再次計算區(qū)域與中心像素的圖像塊的相似度，并將區(qū)域合并到區(qū)域中，用式(9)的權值替換比率控制迭代執(zhí)行次數。為了控制圖像塊引起的噪聲，當替換比率大于，才能再次增加搜索范圍，有：

像素點(,)的鄰域搜索范圍確定流程如下：

1) 初始化。以(,)中心點的(2+1)×(2+1)搜索區(qū)域；利用逐次消元法，計算區(qū)域與中心像素點之間的相似度矩陣。

2) 用式(10)找到PatchGP最小的邊緣點，以該邊緣點為矩形邊中心擴展大小為(2+1)×(2+1)的區(qū)域，，利用逐次消元法計算區(qū)域與中心像素點之間的相似度矩陣，并計算替換比率。

4) 最終區(qū)域為(,)的鄰域搜索范圍，并得到與中心點的相似度。

3 實驗結果與分析

本文采用4個標準的圖像Lena、Pepper、Barbara和Baboon，并加入多個取值的標準差的零均值高斯白噪聲。在實驗中，本文的方法分別與K-SVD- NLM[2]、DCT-NLM[4]、FM-PatchGP[18]、cNLM[19]和BM-3D[20]共5種基于塊相似性的去噪算法從速度和性能兩方面做定性比較與分析。其中，cNLM代表經典優(yōu)化參數的NLM算法，DCT-NLM代表變換子空間去噪法、FM-PatchGP、K-SVD-NLM、BM-3D代表去噪性能最佳的方法。為了比較的公平，所有比較算法的搜索窗口和圖像塊大小參考文獻[15]分別設置為21×21和7×7。本文的算法參數設置，，初始搜索窗口為11×11，擴展窗口為9×9，圖像塊大小為7×7，=0.7×。

為了驗證本文的方法加速和自適應搜索范圍的有效性，本文的算法和DCT-NLM均使用C++語言編程實現，cNLM和K-SVD-NLM源代碼來自文獻[19]，FM-PatchGP和BM-3D源代碼來自作者網站，測試環(huán)境為visual C++ 2008、Dell Inspiron、Core i3、2 GB內存。采用PSNR(peak signal-to-noise ratio)和SSIM(structural similarity index)兩個指標對去噪結果進行定量比較。SSIM是一種以度量兩幅圖像間的結構性失真來評估圖像質量評價度量的新指標，取值范圍[0～1]，其值越大越接近，當圖像完全一致時，SSIM為1。

a. Lena

b. Pepper

c. Barbara

d. Baboon

圖3 改進算法與K-SVD-NLM、DCT-NLM、FM-PatchGP、cNLM和BM-3D用PSNR指標的比較

a. Lena

b. Pepper

c. Barbara

d. Baboon

圖4 改進算法與K-SVD-NLM、DCT-NLM、FM-PatchGP、cNLM和BM-3D用SSIM指標的比較

從PSNR、SSIM兩個指標數值上可得，本文的算法都比cNLM算法有較大的提高。本文的算法雖然當較小時，PSNR值略低于DCT-NLM和FM-PatchGP，接近BM-3D，且高于K-SVD-NLM。但隨著增大時，圖像Lena、Pepper和Barbara的PSNR值和SSIM值均不同程度地超過了其他5種算法。同時隨著噪聲水平的增加，該算法性能下降較緩慢。該算法具有良好的性能指標值，調整搜索區(qū)域的改進NLM算法通過尋找同質信息，有效地阻止了噪聲信息的干擾，增強了去噪能力。

a. 原圖 b. Proposed

c. DCT-NLM d. cNLM

e. K-SVD-NLM f. BM-3D

g. FM-PatchGP

圖5 6種算法去噪細節(jié)對比(=25)

由于圖3d的測試圖像Baboon存在細膩且不規(guī)則的紋理，本文的算法降低了自適應搜索區(qū)域能力，退化為較小固定搜索窗口的NLM且噪聲干擾無法辨別，導致PSNR數值下降較快，性能略低于cNLM，但圖4d說明圖像整體結構保留較好，同樣由于不規(guī)則細膩的紋理導致PatchGP不夠準確，FM-PatchGP的PSNR和SSIM值都下降較快。

圖5所示為Barbara圖像部分細節(jié)原圖以及6種算法去噪后的對比圖(=25)。圖5a包含了左上角的平滑區(qū)域和頭巾部分的紋理邊緣區(qū)域。對比可見，除了FM-PatchGP，其他的5種算法都可以較好地保留圖像的結構與細節(jié)。cNLM、K-SVD-NLM和BM-3D算法去噪結果的平滑區(qū)域部分不同程度出現明顯的偽影。本文的算法將結構相似性和同質信息相結合動態(tài)調整搜索窗口，有效地去除了噪聲干擾，較好地利用了圖像冗余相似性，其邊緣區(qū)更整齊，圖像結構信息保留較完整。由于選取相似性最接近的個像素點，對于平滑區(qū)域，該算法的去噪能力也明顯強于cNLM，避免了偽影現象。與DCT-NLM算法相比，本文的算法對圖像的邊界細節(jié)紋理信息保留得稍好，圖像細節(jié)更清晰。

表1 本文的算法與比較算法不同圖像大小的平均耗時比較 單位：s

逐次消元法剔除相似性低的圖像點和優(yōu)化的搜索窗口都有效地降低了計算復雜度。表1記錄了本文的算法與K-SVD-NLM、DCT-NLM、FM-PatchGP、cNLM和BM-3D對本文測試的4幅圖像的平均耗時比較。從表中可以看出，對于大小為128′128和256′256的圖像，FM-PatchGP耗時最少，但其去噪性能較低以及圖像細節(jié)丟失嚴重。對于大小為512′512和1 024′768的圖像，由于本文的算法使用逐次消元法剔除像素點，圖像越大，相似度低的像素點被丟棄得越多。該算法計算量增幅較小，與其他幾種算法相比，具有良好的加速效果。

綜上分析，從總體性能指標來看，本文的算法具有一定的優(yōu)勢。同時，該方法也存在如下兩點不足：1) 不太適應含有較多的細膩且不規(guī)則的紋理圖像。2) 從去噪指標和運行時間比較看，對于噪聲<20和低于256′256大小的圖像，該算法的整體性能略低于DCT-NLM算法。

4 結 論

NLM算法具有較好的去噪性能，但存在運行效率低的問題，本文利用L2范數的逐次消元法和積分圖，有效地降低了像素間相似性計算強度，并根據圖像空間相關性強的特點，提出一種基于Patch測地線距離尋找同質信息的自適應調整搜索窗口的方法。在實驗中，本文的算法與當前性能最佳的5個基于圖像塊去噪算法相比，從PSNR、SSIM兩個指標和運行時間比較上可知，該方法不但獲得了較好的加速，而且去噪效果也有一定的提升。

[1] BUADES A, COLL B, MOREL J M. A review of image denoising algorithms, with a new one[J]. Multiscale Modeling & Simulation, 2005, 4(2): 490-530.

[2] ELAD M, AHARON M. Image denoising via sparse and redundant representations over learned dictionaries[J]. IEEE Transactions on Image Processing, 2006, 15(12): 3736- 3745.

[3] ORCHARD J, EBRAHIMI M, WONG A. Efficient nonlocal-means denoising using the SVD[C]//Proceedings of IEEE International Conference on Image Processing. San Diego, California: IEEE Signal Processing Society, 2008: 1732-1735.

[4] 胡金蓉, 蒲亦非, 張意, 等. DCT子空間的非局部均值去噪算法[J]. 計算機輔助設計與圖形學學報，2012, 24(1): 89-96.

HU Jin-rong, PU Yi-fei, ZHANG Yi, et al. Nonlocal-means denoising algorithm based on DCT subspace[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(1): 89-96.

[5] 張志, 王潤生. 基于Walsh-Hadamard投影的快速Nonlocal- means圖像去噪[J]. 宇航學報, 2011, 32(2): 380- 387.

ZHANG Zhi, WANG Run-sheng. Fast nonlocal-means image denoising method based on Walsh-Hadamard Pro- jection[J]. Journal of Astronautics, 2011, 32(2): 380-387.

[6] TASDIZEN T. Principal components for nonlocal-means image denoising[C]//Proceedings of IEEE International Conference on Image Processing. San Diego, California: IEEE Signal Processing Society, 2008: 1728-1731.

[7] ZHANG L, DONG W, ZHANG D, et al. Two-stage image denoising by principal component analysis with local pixel grouping[J]. Pattern Recognition, 2010(43): 1531-1549.

[8] VAN DE VILLE D, KOCHER M. Nonlocal means with dimensionality reduction and SURE-based parameter selection[J]. IEEE Transactions on Image Processing, 2011, 20(9): 2683-2690.

[9] VAN D E VILLE D, KOCHER M. SURE-based nonlocal-means[J]. Signal Processing Letters, 2009, 16(11): 973-976.

[10] SALMON J. On two parameters for denoising with nonlocal-means[J]. Signal Processing Letters, 2010, 17(3): 269-272.

[11] 王志明, 張麗. 自適應的快速非局部圖像去噪算法[J]. 中國圖象圖形學報, 2009, 14(4): 669-675.

WANG Zhi-ming, ZHANG Li.Adaptive fast nonlocal image denoising algorithm[J]. Journal of Image and Graphics, 2009, 14(4): 669-675.

[12] LIU Y L, WANG J, CHEN X, et al. A robust and fast nonlocal-means algorithm for image denoising[J]. Journal of Computer Science and Technology, 2008, 23(2): 270- 279.

[13] FENG C S, MING L, WEI Z, et al. Edge preserving image denoising with a closed form solution[J]. Pattern Recognition, 2013, 46(3): 976-988.

[14] CHEN Q, SUN Q, XIA D. Homogeneity similarity based image denoising[J]. Pattern Recognition, 2010, 43(12): 4089-4100.

[15] MATHEW A T. Robust estimation approach for nonlocal-means denoising based on structurally similar patches[J]. International Journal of Open Problems in Computer Science and Mathematics, 2009, 2(2): 311-331.

[16] WANG H S, MERSEREAU R M. Fast algorithms for the estimation of motion vectors[J]. IEEE Transactions on Image Processing, 1999, 8(3): 435-438.

[17] VIOLA P, JONES M J. Robust real-time face detection[J]. International Journal of Computer Vision, 2004, 57(2): 137-154.

[18] CHEN X, KANG S B, YANG J, et al. Fast patch-based denoising using approximated patch geodesic paths[C]// IEEE Conference on Computer Vision and Pattern Recognition.Portland, OR: IEEE Signal Processing Society, 2013: 4321-4328.

[19] DABOV K, FOI A, KATKOVNIK K O, et al. Image denoi- sing by sparse 3D transform domain collaborative filtering[J]. IEEE Transactions on Image Proscessing, 2007, 16(8): 2080-2095.

[20] WANG Z, BOVIK A C, SHEIKH E P. Image quality assessrment: Form error visibility to structural similarity[J]. IEEE Transactions on Image Proscessing, 2004, 13(4): 600-612.

編 輯 黃 莘

Fast Nonlocal Means Image Denoising Algorithm Using Selective Calculation

LUO Xue-gang1, 2, Lü Jun-rui2, WANG Hua-jun1, and YANG Qiang1

(1. School of Mathematics and Computer Science, Panzhihua University Panzhihua Sichuan 617000; 2. Key Lab of Earth Exploration & Information Techniques of Ministry of Education, Chengdu University of Technology Chengdu 610059)

A fast nonlocal means (NLM) image denoising method with selective calculation is proposed to solve the problem thatthe computational cost of similarity weights is high. By using L2 Norm successive elimination, a large number of pixels of low similarity van be rejected through a small amount of additive operations on integral image, and the massive calculation on measuring similarity can be effectively reduced. According to spatial coherence in the image domain, an approach for adaptive search area based on patch geodesic distance is proposed. Experimental results demonstrate that the proposed method, compared with the state-of-the-art algorithms, can not only accelerate the nonlocal means algorithm, but also elevate the image quality.

image denoising; nonlocal means; patch geodesic path; selective calculation; successive elimination

TP391

A

10.3969/j.issn.1001-0548.2015.01.014

2013-09-16;

2014-07-23

國家自然科學基金青年科學基金(61202195/F020502)；四川省教育廳科研基金(13ZB0212)

羅學剛(1983-)，男，博士生，主要從事圖像處理、計算機視覺等方面的研究.