XU Jianlou()， HAO Yan( )

School of Mathematics and Statistics，Henan University of Science and Technology，Luoyang471023，China

Abstract：The nonlocal means(NLM)has been widely used in image processing.In this paper，we introduce a modified weight function for NLM denoising，which will compute the nonlocal similarities among the pre-processing pixel patches instead of the commonly used similarity measure based on noisy observations.By the law of large number，the norm for the pre-processing pixel patches is closer to the norm of the original clean pixel patches，so the proposed weight functions are more optimized and the selected similar patches are more accurate.Experimental results indicate the proposed algorithm achieves better restored results compared to the classical NLM’s method.

Key words：image denoising；nonlocal means(NLM)；weight；patch similarity

Introduction

Image denoising is a basic inverse problem in image processing. The goal is to recover the true image from the noisy measurement.

During the past few years， there are many methods for image denoising， such as total variational method[1]， which assumes that the reconstructed image belongs to the smooth bounded function space and the optimal solution is obtained by solving an energy functional model. However， the method can not preserve some tiny structures and texture. In order to improve the phenomenon， some nonlocal methods are studied[2-13]. Nonlocal image representations utilize the nonlocal similarity between two patches to estimate each pixel by the weighted average of many pixels in the image， and the weights are respectively evaluated according to pair-wise similarity between two patches， which have been proved very successfully for noise removal. Inspired by the appearance of NLM denoising， Gilboa and Osher[14]introduced some nonlocal operators and proposed a nonlocal total variational model to better recover textures. They adapted the celebrated Chambolle’s projection algorithm[15]to optimize a discretization of this model. In recent years， nonlocal variational models[16-17]have been widely used to restore images， because of their capability to utilize the information from many pixels having a similar neighborhood. Using the similarities between columns and rows， Zhangetal.[18]presented a two-directional nonlocal variational model for image denoising. For these nonlocal variational models， in the discrete version， each pixel is associated with a patch， and local differences for two pixels are replaced by differences between their corresponding similar patches. Using these patch-based differences in the energy encourages repetitive behavior in the reconstructed image， these nonlocal models can recover the clean image while removing random noise.

Another methods are based on space between sparse and representation， for example, K-SVD algorithm[19]supposes each image patch can be represented sparesly as a linear combination of atoms taken from the overcomplete dictionary. Zhangetal.[20]presented an adaptive shrinkage algorithm based on locally learned principle component analysis basis for image denoising. By combining the nonlocal similarity and the sparsity， Dabovetal.[21]presented a block matching 3D (BM3D) filtering algorithm for image denoising.

Since the appearance of NLM denoising， many advanced nonlocal image restoration algorithms have been developed[3-13]. Because the NLM method needs to compute a large number of block distances， the speed is very slow. To improve the speed of operation， Mahmoudi and Sapiro[3]studied the fast image and video denoising algorithm； the authors in Refs.[4-6] gave the different fast NLM calculation respectively. Ville and Kocher[7]used the Stein’s unbiased risk estimate (SURE) to control the mean square error for image denoising and thus selected the optimal smoothing factor for the exponential kernel of the weight function. Ni and Gao[8]proposed a Bayesian NLM framework for Synthetic Aperture Radar (SAR) image denoising. The image super-resolution using NLM were studied in Ref.[9-10]. different weight updating methods were proposed in Refs.[11-12]. Zeng and Lu[13]put forward the region based NLM.

In this paper， we mainly focus on NLM. A new weight is derived for NLM denoising， which computes the nonlocal similarities between the pre-processing pixel patches instead of the commonly used similarity measure based on noisy observations. By the law of large number， the norm for the pre-processing pixels patches is closer to the norm of the original clean pixels patches， so the obtained weight functions are more optimization and the selected similar patches are more accurate.

In the rest of this paper， the new method will be given in section 1. Section 2 will give some numerical results to test the proposed method. Finally， some conclusions are given in section 3.

1 Proposed Method

In NLM algorithms， each pixel is estimated by the weighted average of all pixels in the image， and the weights are evaluated according to similarity between two corresponding patches. That is， given a discrete noisy imagef={f(p)|p∈I}， wheref(p) denotes the gray value ofp，Idenotes the image domain size， and the restored image is

(1)

where，ω(p，q) is the similarity weight which is defined as

(2)

Equation (2) is obtained by computing the Euclidean distance of two noisy pixels patches. Hhowever， the distance satisfies

np-nq〉.

(3)

Equation (3) shows that for two large pixels patches， there is a larger space between the noisy pixels patches and corresponding clean pixels patches. To be exact，with the law of large numbers[2]， the expectation of the Euclidean distance satisfies

(4)

whereσ2is the noisy image variance. As shown in Eq.(4)， with the noisy level becoming larger， the error between the norm of the noisy image patches and the corresponding clean image patches will become larger. So if we directly use the patches distance of noisy images to obtain the similarity weight through Eq. (2) for given pixels， a large difference is generated between two norms. Then the selected similar patches are not accurate and obtained similarity weights are not very accurate too. Eventually， the restored results by Eq. (1) will not be the best.

To reduce the error and overcome the disadvantage of the NLM’s method， the distance of noisy image patches should be close to the distance of the corresponding clean image patches. So the Gaussian kernel function is firstly used to smooth the noisy image in this paper， and then the similarity weight will be computed using the smoothed image,i.e.， the modified similarity weight is computed by

(5)

Then the restored image is

(6)

As shown in Eq. (5)， the noise standard deviation for the pre-processing smoothed image is smaller than the original noise image. So the expectation for the smoothed image is closer to the original clean image. Then the found similar blocks are more accurate.

The detailed algorithm is as follows.

Algorithm: improved weight function for NLM image denoising.

Step 1 Input initial noise imagef.

Step 4 Compute (5) to find similar weight.

Step 5 Output the restored image by Eq. (6).

2 Numerical Experiments

In this section， we compare the proposed algorithm with the NLM’s method[2]and BM3D[21]. Lena， Cameraman， Peppers， House，etc. are taken as the tested images. The noise standard deviations are 30， 40， 50 respectively. The results are evaluated by measuring the peak signal-to-noise ratio (PSNR) and the structure similarity(SSIM). In the following experiments， the size of patches is 5×5， these similar patches are grouped in the search window of size 11×11. Note that the restored results are related to the sizes of the block and search window， increasing their size， the obtained results will be better. However， the computational complexity increases. For the decay filtering parameterh， taking Toys as an example，and the noise standard deviations are 30 and 50 respectively.The curves of PSNR withhare shown in Fig. 1， whereXaxis indicates several times ofσ.

(a)

(b)

Fig. 1 Curves of PSNR with the decay filtering parameterhfor Toys image：(a) toys image with the noise standard deviation 30； (b) toys image with the noise standard deviation 50

Figure 1 shows that whenh=4σ， the proposed method can obtain the better results， soh=4σis chosed in these experiments. The restored results are in Table 1 with the best results highlighted in bold font.

Table 1 Restored results for different algorithm

The results in Table 1 display PSNR value for the proposed algorithm averagely exceeds about 0.5 dB over NLM and the average SSIM value is about 0.774 4 over the NLM’s 0.738 9. So the proposed method obtains the better results than those using NLM’s method. Although BM3D obtains the best results, it needs a lot of patches computing. To make a visual comparison of the restoration images，we take Lena as an example with three different noise levels， the restored results are shown in Fig. 2，F(xiàn)ig. 3 and Fig. 4， respectively.

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 2 Denoising results with the noise standard derivation 30： (a) clean image (b) noise image； (c) testored result by NLM， (PSNR，SSIM)=(27.645 4， 0.776 4)； (d) restored result by the proposed method， (PSNR，SSIM)=(28.139 3， 0.804 1)； (e) residual image in NLM， norm=7 203； (f) rsidual image in the proposed method， norm=7 406

Figures 2(a)， 3(a) and 4(a) are the clean images； Figures 2(b)， Fig. 3(b) and Fig. 4(b) are three different noisy images； Figures 2(c)， 3(c) and 4(c) are the restored results using NLM’s method； Figures 2(d)， 3(d) and 4(d) are the restored results by the proposed method. From Lena’s hat in Fig. 2(c) and 2(d) respectively， we can see that the proposed method contains more tiny structures than NLM’s method. To see clearly these tiny structures， we give the residual images in Figs. 2-4，which obtained by letting the observed noisy images minus the corresponding reconstructed images. These residual images show that there are more tiny structures removed using NLM’s method than the proposed method. In addition， for quantitative comparison， we compute the norm of the each residual image for different noise level. The results are shown in Figs. 2-4 respectively， and the data obtained by the proposed method are bigger than those using the NLM’s method. This shows that there are more noise removed by the proposed method than those using NLM’s method.

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 3 Denoising results with the noise standard derivation 40： (a) clean image (b) noise image (c) restored result by NLM， (PSNR， SSIM)=(26.155 4， 0.716 5) (d) restored result by the proposed method， (PSNR， SSIM)=(26.755 4， 0.756 0) (e) residual image in NLM， norm=9 581 (f) residual image in the proposed method， norm=9 837

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 4 Denoising results with the noise standard derivation 50： (a) clean image (b) noise image (c) restored result by NLM， (PSNR， SSIM)=(25.011 1， 0.659 5)； (d) restored result by the proposed method， (PSNR， SSIM)=(25.633 1， 0.710 5) (e) residual image in NLM， norm=11 935； (f) residual image in the proposed method， norm=12 278.

3 Conclusions

In this paper， we propose a denoising algorithm by an improved similarity weight，which computed by use of the norm of pre-processing pixels patches instead of the commonly noisy pixels patches. By the law of large number， the norm for the pre-processing pixels patches is closer to the norm of the original clean pixels patches， so the obtained weight functions are more optimization and the selected similar patches are more accurate. Experimental results indicate that the proposed algorithm achieves higher restored results compared with the classical NLM’s method.