李嘉浪，李華君，徐 慶

（天津大學計算機學院，天津 300072）

基于小波閾值的非局部均值去噪*

李嘉浪，李華君，徐 慶

（天津大學計算機學院，天津 300072）

非局部均值去噪算法充分利用了圖像的全局信息，因此比傳統(tǒng)的局部去噪算法有著更好的去噪效果。但是，非局部均值去噪算法計算時間復雜度較高，故利用小波閾值的方法對其進行改進，改進后使用非局部均值處理的數(shù)據(jù)量大幅減小。實驗表明，改進后的算法比非局部均值算法去噪效果基本持平，且運行速度更快。

非局部均值；小波閾值濾波；圖像去噪

1 引言

數(shù)字圖像在獲取和傳輸?shù)倪^程中容易受到噪聲的污染，被污染的圖像會影響圖像的進一步處理，對圖像的理解和識別帶來一定的困難。有效的去噪算法對后續(xù)的應用處理有著重要的意義。

圖像去噪處理方法一般分為三大類：第一類是空間域法，比較常用的方法有高斯濾波法［1］、中值濾波法［2］和雙 邊濾 波 法［3］。第 二 類 是 基于貝 葉 斯最大后驗概率推出的能量泛函模型。能量泛函包含兩部分：數(shù)據(jù)模型和先驗模型。比較常見的有馬爾可夫 隨 機場模 型［4］、熵 理 論［5］和幾何 模 型 方法［6］。第三類是變換域的處理方法，將圖像變換到頻率域中進行處理，比較常見的方法有傅里葉變換和小波變換［7］。其中由于小波處理的獨特優(yōu)越性，近年來成為了圖像處理的一個重要工具。

Buades A［8］針對空間域的加性噪聲提出了非局部均值NLM（Non-Local Means）去噪模型。該算法主要采用全局搜索的方法，充分利用圖像的冗余信息，得到圖像每一個像素的灰度值。算法使用了塊匹配的思想，從而增強了圖像匹配的魯棒性。由于該算法效果顯著，在近些年得到了廣泛的關注和改進。

Orchard J［9］提出將圖像先映射成一個低維度的矩陣，縮短運算時間，同時降維矩陣保留了原圖的主要特征。Tasdizen T［10］提出了基于主成份分析法的快速NLM去噪PNLM（PCA Non-LocalMeans）。先求出圖像塊的特征值和特征向量，將特征值按從高到低進行排列，然后取前六個特征值對應的特征向量，將圖像塊映射到這六個特征向量上。圖像塊降到一個低維度的矩陣，降低了時間復雜度；同時保留了圖像的主要信息，故去噪效果與原NLM效果基本持平。Vignesh R等［11］提出閾值法，當塊間距離超過閾值時，說明搜索塊和待處理塊的相關性較差，將其丟棄，以提高運算效率，同時加大相似塊的權重，改進去噪效果。Brox T等［12］提出先進行圖像分類，利用k均值算法將相近的像素劃為一類，NLM只在相近的類中進行計算，減少計算的時間。Van De Ville D等［13］將均方誤差作為目標函數(shù)，當均方誤差達到最小時相應的參數(shù)設置為NLM的最優(yōu)參數(shù)。Mahmoudi M［14］使用像素塊的平均值和梯度值作為評價像素塊相似的標準，對于不相似的像素塊及時丟棄。文獻［15］在NLM權重計算過程中用1范數(shù)代替2范數(shù)，從而使得邊緣更加清晰飽滿。Sun Z［16］對文獻［15］進行了改進，將兩個塊相似度的計算改為p范數(shù)（0＜p＜1）。

本文針對NLM時間復雜度較高的問題，提出將小波閾值和非局部均值去噪進行結合的方法，將圖像進行兩層小波分解。對于第二層的低頻部分L2進行保留，第二層的高頻部分使用小波閾值去噪。將處理后的第二層進行逆小波變換，得到第一層的低頻圖像L 1′。對L 1′進行改進的NLM處理，第一層的高頻部分用小波閾值處理，最后進行小波逆變換得出去噪后的圖像。利用小波特性，保留了圖像的紋理特征，得到較好的去噪效果，并提高了算法的運行速度。

2 非局部均值去噪算法

圖像噪聲模型可以寫為：

v（i）=u（i）+n（i） （1）

其中，u（i）代表著未被污染的圖像的像素值，n（i）代表著噪聲，v（i）代表著污染后圖像的像素值。

非局部均值去噪中目標像素點的估計值是由圖像中所有的像素點加權平均得到的，權重的大小是由兩個以像素點為中心的像素塊的相似度來決定的：

其中，z（i）的作用是實現(xiàn)權重的歸一化，i是目標像素點，j是圖像中所有的像素點。像素i和像素j的相似度依賴于灰度級矩陣P（i）和P（j）的相似度，P（i）是指以i為中心的n×n的像素矩陣塊，n一般取7。P（i）和P（j）的相似度通過高斯加權歐式距離‖P（i）—P（j）‖2來表示。h為濾波參數(shù)，控制指數(shù)函數(shù)的衰減速度，即權重的衰減速度。

在遍歷了所有的像素點后得出了圖像中所有像素點對于目標像素點的權重，最后將所有像素點進行加權均值即可得到目標像素點的像素值：

其中，u（i）代表著i點的預測像素值，u（j）代表原始圖像在j點的像素值。

3 小波閾值去噪

小波閾值去噪是小波去噪中比較有代表性的一種方法。小波去噪的實質是一個函數(shù)逼近問題：即根據(jù)衡量準則，如何在由小波母函數(shù)伸縮和平移展成的函數(shù)空間中，區(qū)分出信號和噪聲，尋找對原信號的最佳逼近。小波閾值收縮去噪利用了小波變換中多分辨特性對特定信號的“集中能力”，即如果一個信號的能量集中于少數(shù)小波系數(shù)，那么這些系數(shù)值必然大于能量分散的噪聲小波系數(shù)值。

小波閾值收縮法中，最為重要的是選擇閾值和閾值函數(shù)。閾值太小，去噪后圖像仍有噪聲；相反，閾值太大，重要的圖像特征將被濾掉，引起失真。直觀上講，對于給定的小波系數(shù)，噪聲越大，閾值就越大。所以，大多數(shù)閾值選擇過程是針對一組小波系數(shù)，根據(jù)其統(tǒng)計特性，計算出閾值。

本文小波閾值的選取主要采用的是Bayes shrink法，該計算公式如下：

其中分母表示圖像的信號方差估計，分子表示噪聲的信號方差估計。當小波系數(shù)小于閾值時，說明信號受噪聲的影響較大，故置為0；當小波系數(shù)大于閾值時，說明信號受噪聲的影響較小，所以進行保留。

假設小波系數(shù)是 wj，k，變換后的 小波系數(shù)為w'j，k，u為小波閾值，軟閾值和硬閾值函數(shù)表示如下：

軟閾值法：

硬閾值法：

4 基于小波閾值的非局部均值去噪

圖像在采集、轉換和傳輸過程中受到成像設備和外部環(huán)境的干擾而產(chǎn)生噪聲，這些噪聲有一定的共同點，即在一定的頻段會表現(xiàn)出一定的特征。小波變換是一種窗口大小固定但其形狀可改變、時間窗和頻率窗都可改變的時頻局部化分析方法。經(jīng)小波變換后圖像的大部分能量多集中在趨勢變換系數(shù)而不是波動系數(shù)。圖像經(jīng)小波變換后在低頻部分具有較高的頻率分辨率和較低的時間分辨率，在高頻部分具有較高的時間分辨率和較低的頻率分辨率。這種特性使得小波變換具有對信號的自適應性，能較好地分析處理信號的局部特性。

圖像和噪聲經(jīng)過小波變換后表現(xiàn)出不同的統(tǒng)計特征，圖像本身的能量主要集中在低頻，與幅值較大的小波系數(shù)對應。噪聲主要分散在小波變換后的高頻部分，與幅值較小的小波系數(shù)相對應。故改進算法主要將圖像進行多分辨率分解，在低頻部分用改進的NLM進行去噪處理，而在高頻部分則采用小波硬閾值的方法進行處理。

其步驟可總結如下：

（1）對一幅含有噪聲的圖像，進行二維小波分解。分解為低頻圖像L1和高頻的細節(jié)信息圖像H 1。

高頻的細節(jié)信息又包含了三個部分：水平細節(jié)信息、垂直細節(jié)信息和對角細節(jié)信息。

（2）使用Bayes shrink法對高頻圖像H 1進行小波閾值去噪，得到H 1′。

（3）對L 1進行小波分解，分解為低頻圖像L2和高頻圖像H 2。

由于L1中噪聲部分和圖像信息混合在一起，并沒有較為明顯的區(qū)分。因此需要進行分解，需要分解的層數(shù)與圖像質量和特性有關。通過實驗得出分解到二層的時候處理效果已經(jīng)達到處理要求。

（4）使用Bayes shrink法對高頻圖像H 2進行小波閾值去噪，得到H 2′。

第二次分解后的低頻部分L2主要含有圖像的整體信息，故不作任何處理；高頻部分 H 2含有圖像細節(jié)和噪聲，使用小波硬閾值法進行噪聲的過濾，得到H 2′。

（5）通過小波逆變換對L 2和H 2'進行重構。

（6）對（5）重構得到的低頻圖像使用改進的NLM去噪算法，得到圖像L 1′。對NLM算法進行改進，即用每一迭代得出的新像素值取代對應原圖的原始像素值，在下一次迭代時使用上一次迭代更新后的圖像像素值，使得信息的提取更加準確。

具體步驟如下：

①對于L 1′中的每一個像素點i，計算圖像所有像素值的權重w（i，j），權重的計算如下：

其中，P'（i）、P'（j）分別為更新后圖像L 1′中以i和j為中心的像素塊。

其中，w（i，j）為公式（7）中得到的各個像素點的權重，u'（j）為更新后圖像L 1′中第j個像素點的像素值。

②更新L 1′中第i個像素點的像素值為u（i）。

（7）通過小波逆變換對H 1'和L1'進行重構，得到最終的輸出圖像。具體算法的流程如圖1所示。

Figure 1 Denoising processing圖1 去噪流程圖

5 實驗仿真結果

將改進后的NLM去噪和原始的NLM、小波閾值去噪以及PNLM進行比較。測試的圖像采用國際標準RGB測試圖像House和Pepper，大小是256×256像素。評價標準為峰值信噪比PSNR （Peak Signal to Noise Ratio）。添加的噪聲為高斯白噪聲，方差為30～50。實驗結果見表1。

由表1可以看出，基于小波閾值的NLM去噪算法與原始的 NLM去噪算法相比，在σ較小時PSNR略有不及，但在σ比較大的時候，PSNR有略微反超。與小波閾值去噪算法相比，PSNR的提高比較明顯。

圖2為表1所列方法的處理結果圖，實驗中的噪聲量σ為30。改進后的去噪算法的PSNR與NLM以及PNLM在處理效果的指標上基本持平。但是從肉眼觀察來說，更符合人眼的視覺標準，且色彩更加飽和，邊緣更加清晰。相比NLM原算法，基于小波閾值的NLM充分考慮了時間復雜度問題，使得NLM處理的數(shù)據(jù)量降低為原來的1/4。設圖像尺寸為m×m，鄰域圖像尺寸塊為n×n，權重的搜索窗口限定在t×t，其原始NLM計算的時間復雜度為O（m2·n2·t2），計算時間復雜度很大。基于小波閾值的非局部去噪算法將圖像進行了兩層小波分解，NLM算法主要在第一層的低頻圖像進行迭代。第一層的低頻圖像是原始圖像的1/4大小，權重的搜索窗口限定為1/2t×1/2t，鄰域尺寸不變，故在小波閾值分解后NLM處理的時間復雜度為O（1/16·m2·n2· t2）。

Table 1 PSNR comparison between the wavelet shreshold NLM and other methods表1 基于小波閾值非局部去噪與其它方法的峰值信噪比PSNR結果對比

Figure 2 Results of different denoised methods圖2 不同方法對House的去噪結果圖

將基于小波閾值的非局部均值去噪算法與原始的NLM、小波閾值去噪以及PNLM運行時間進行比較，實驗結果見表2。由于本文所提出的算法分為二維小波分解、小波閾值去噪以及 NLM去噪，其中小波分解以及小波閾值去噪需占用一定時間，故實際的執(zhí)行時間未達到原算法的1/16。以上的測試是在主頻為Intel Core Duo 2.53 GHz、1 GB內存的計算機上得出的。

Table 2 Execution time comparison between the wavelet shreshold NLM and other methods表2 基于小波閾值的非局部均值去噪與其它方法的執(zhí)行時間對比 s

6 結束語

本文提出了一種基于小波閾值的快速非局部均值去噪算法。該算法對圖像進行了兩層小波分解。對于第一層和第二層的高頻部分使用小波閾值去噪，對于逆變換后第一層的低頻圖像使用改進的NLM去噪。通過實驗證實了基于小波閾值的NLM算法，在去除噪聲的同時更好地保持了圖像的邊緣信息，且相較其他NLM改進算法運行的時間大幅降低。

［1］ Lindenbaum M，F(xiàn)ischer M，Bruckstein A.On Gabor's contribution to image enhancement［J］.Pattern Recognition，1994，27（1）：1-8.

［2］ Ahmad M O，Sundararajan D.A fast algorithm for two dimensional median filtering［J］.IEEE Transactions on Circuits and Systems，1987，34（11）：1364-1374.

［3］ Tomasi C，Manduchi R.Bilateral filtering for gray and color images［C］∥Proc of the 6th International Conference on Computer Vision，1998：839-846.

［4］ Bremaud P.Markov chains：Gibbs fields，Monte Carlo simulation，and queues［M］.Berlin：Springer，1999.

［5］ Arias P，Caselles V，Sapiro G.A variational framework for non-local image inpainting［C］∥Proc of the 7th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition，2009：345-358.

［6］ Rudin L，Osher S，F(xiàn)ateni E.Nonlinear total variation based noise removal algorithms［J］.Physica D，1992，60（1-4）：259-268.

［7］ Chang S G，Yu B，Vetterli M.Adaptive wavelet thresholdingfor image denoising and compression［J］.IEEE Transactions on，Image Processing，2000，9（9）：1532-1546.

［8］ Buades A，Coll B，Morel J M.A non-local algorithm for image denoising［C］∥Proc of IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2005：60-65.

［9］ Orchard J，Ebrahimi M，Wong A.Efficient non-local means denoising using the SVD［C］∥Proc of the 15th IEEE International Conference on Image Processing，2008：1732-1735.

［10］ Tasdizen T.Principal components for non-local means image denoising［C］∥Proc of the 15th IEEE International Conference on Image Processing，2008：1728-1731.

［11］ Vignesh R，Oh B T，Kuo C C J.Fast non-local means （NLM）computation with probabilistic early termination［J］.IEEE Signal Processing Letters，2010，17（3）：277-280.

［12］ Brox T，Kleinschmidt O，Cremers D.Efficient nonlocal means for denoising of textural patterns［J］.IEEE Transactions on Image Processing，2008，17（7）：1083-1092.

［13］ 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.

［14］ Mahmoudi M，Sapiro G.Fast image and video denoising via nonlocal means of similar neighborhoods［J］.IEEE Signal Processing Letters，2005，12（12）：839-842.

［15］ Chaudhury K N，Singer A.Non-local Euclidean medians［J］.

IEEE Signal Processing Letters，2012，19（11）：745-748.［16］ Sun Z，Chen S.Analysis of non-local Euclidean medians and its improvement［J］.IEEE Signal Processing Letters，2013，20（8）：303-306.

李嘉浪（1988），女，山西臨縣人，碩士生，研究方向為計算機圖像處理。E-mail：542617751@qq.com

LI Jia-lang，born in 1988，MS candidate，her research interest includes computer image processing.

李華君（1989 ），女，湖南吉首人，碩士生，研究方向為計算機圖形可視化。E-mail：411617428@qq.com

LI Hua-jun，born in 1989，MS candidate，her research interest includes computer graphic visualization.

徐慶（1969 ），男，天津人，博士，教授，研究方向為計算機圖形學。E-mail：qingxu@tju.edu.cn

XU Qing，born in 1969，PhD，professor，his research interest includes computer graphics.

Non-local means denoising based on wavelet threshold

LI Jia-lang，LI Hua-jun，XU Qing
（School of Computer Science，Tianjin University，Tianjin 300072，China）

The non-local means denoising algorithm can use the globe information of the picture，therefore it has better denoising effect than other traditional algorithms.However，since its time complexity is high，we put forth a new non-local means denoising algorithm based on wavelet threshold filter，which use much less data than the traditional non-local means.Experimental results show that compared to the traditional non-local means，the denoising effect of our algorithm is basically the same，but the running speed is faster.

non-local means；wavelet threshold filter；image denoising

TP317.4

A

10.3969/j.issn.1007-130X.2015.08.019

1007-130X（2015）08-1546-05

2014-04-08；

2014-07-12

國家自然科學基金資助項目（U1333110）

通信地址：300072天津市天津大學計算機學院

Address：School of Computer Science，Tianjin University，Tianjin 300072，Tianjin，P.R.China