Image Denoising via Fast and Fuzzy Non-local Means Algorithm

1. Introduction

Image is an important way for humans to obtain and transmit information. Noise is an inevitable part of any imaging pipeline during acquisition, transmission, and recording, resulting in low image quality. Reasonably eliminating the noise and preferably reserving the structural and textural details by using the existing image denoising algorithm are difficult.

Many nonlinear filters, such as weight Gaussian filtering, mean filtering, and wavelet soft threshold denoising, have been introduced in the past few years. The implementation in existing hardware is easy. However, such filters can easily omit certain information of an image and cannot obtain favorable results. A series of novel denoising algorithms with effective performance, such as anisotropic filtering, weight bilateral filtering, non-local means (NLM), and block-matching 3D (BM3D), has been presented in recent years [1]. Among these outstanding methods, the NLM algorithm by Buades et al. [2] is a strongly efficient for image denoising and has great influence in the image processing field. Therefore, NLM has attracted considerable attention from numerous scholars.

Traditional denoising methods have obtained the final evaluation results in pixels, whereas the evaluated results of the NLM denoising algorithm are based on image patches. As structures of image patches have many similarities, the image structure information by image patch is utilized to estimate the real value of corresponding pixels. Therefore, the NLM shows enhanced denoising performance. This efficient denoising algorithm explicitly uses self-similarities in image patches.

The NLM is superior in denoising performance, but it still involves various problems, such as huge computational cost and difficult parameter selection. Achieving optimal denoising effect and practical engineering applications is difficult. Hence, different methods have been developed for patch similarity measures and important parameters by related optimization strategies. Investigation and analysis have shown that the major problem is the huge NLM computation in calculating the Euclidean distance on the basis of Gaussian kernel function. In addition, the Euclidean distance is used directly to measure the similarities between image patches, regardless of image edge and structure. NLM with Euclidean distance imposes a high computational complexity and seriously affects the denoising performance.

Relevant existing literatures are briefly summarized to solve this problem. The improved methods in [3] used L2 norm successive elimination and integral image that optionally calculate Euclidean distance to reduce the computational complexity. NLM with grey theory, which can reasonably remove noise and is efficient in capturing details, was introduced in [4] by computing the structural similarity via the grey relation of coefficients. May et al. [5] proposed a low-rank approximation for improving NLM operators to reduce runtime effectively.

In the present study, an improved NLM image denoising algorithm, which utilizes a fuzzy metric for visual features for measuring the dissimilarity between patches, is introduced to solve the inaccuracy of NLM measurement.

The remainder of this paper is organized as follows: Section 2 introduces the NLM algorithm. Section 3 elaborates the concept of fuzzy metric and constructs a visual similarity, which depicts an improved denoising algorithm of visual features, on the basis of the fuzzy metric. Section 4 reports the experimental results of the comparison of the proposed method with state-of-the-art methods. Finally, Section 5 provides the concluding remarks.

2. NLM Image Denoising Method

The basic NLM denoising algorithm is a weighted filter, which is a linear coefficient of the similarity of image patches in images. Let v and u be the observed noisy and clean images, respectively. i and j are the pixel indexes. The recovered values can be derived as the weighted average of all pixel values in the image.

NLM can be defined as follows:

where y(i) is the estimated intensity value at pixel i and [TeX:] $$S_{i}$$ is the search window of s × s around i. w(i, j) represents the weight function between the image patches around i and j, which is defined by

where [TeX:] $$\|\cdot\|_{2}^{2}$$ depicts the Euclidean distance, h is the bandwidth parameter controlled by the blur of Gaussian kernel function, and [TeX:] $$\mathrm{z}(i)=\sum_{j} w(i, j)$$ is a factor for normalization. p denotes the length of image patch. [TeX:] $$P_{i}$$ denotes the image patch around i with width , as illustrated in Eq. (3).

NLM denoising is an outstanding image denoising method [1]. However, this algorithm requires a large amount of computation. The main computation in the algorithm is W(i, j) . As a result, the computational complexity of the image size [TeX:] $$(m \times n) \text { is } O\left(m n p^{2} s^{2}\right).$$ Acceleration strategies have been utilized to reduce the computational complexity [3]. Most representative methods have adopted dimensionality reduction, but the process of dimension reduction requires considerable cost of product operation [5,6].

3. Visual Similarity Based on Fuzzy Metric

The NLM uses spatial correlation in the entire image on the basis of the similarity of each pixel and its neighborhood for noise removal. Reasonably selecting the similarity measure is an important key for obtaining the good performance of the NLM algorithm. Mahalanobis distance [7] was used to replace the Euclidean distance for measuring the similarity of image patches via singular value decomposition. However, singular value decomposition is a time-consuming operation.

This section introduces the concept of fuzzy metrics and its broad range of examples. Then, fuzzy metrics is used to build visual similarity from the structure feature and luminance similarity of image patches.

3.1 Fuzzy Metric

Fuzzy geometry has recently become an active research area because of its broad range of examples. An example of a fuzzy metric M on a set X using continuous t-norms was introduced and studied by Morillas et al. [8] and Gregori et al. [9]. The fuzzy metric is adopted mainly due to the following two main advantages:

1. The outcome given by M is in the space [0,1], without considering the nature of the distance metric being calculated.

2. The M values are perfectly consistent in other fuzzy methods because the outcome obtained by M can be directly applied as a fuzzy certainty degree.

Assuming a continuous t-norm t as a binary operation, [TeX:] $$[0,1] \times[0,1] \rightarrow[0,1],$$ X is a nonempty set satisfying the following five requirements [TeX:] $$\left(R_{1} \text { to } R_{5}\right) \text { for all } x, y \in X . \Re$$ is a fuzzy set on [TeX:] $$X \times X,$$ where [TeX:] $$x, y, z \in X, t, c>0.$$

[TeX:] $$R_{1}: \Re(x, y, t)>0,$$

[TeX:] $$R_{2}: \Re(x, y, t)=1 \text { if and only if } x=y,$$

[TeX:] $$R_{3}: \Re(x, y, t)=\Re(y, x, t),$$

[TeX:] $$R_{4}: \Re(x, y, t) * \Re(y, z, c) \leq \mathfrak{R}(x, y, t+c),$$

[TeX:] $$R_{\mathrm{s}}: \Re(x, y,$$ [TeX:] $$):(0, \infty) \rightarrow[0,1] \text { is continuous. }$$

The value [TeX:] $$(\Re, *)$$ is a fuzzy metric of set X and [TeX:] $$(X, \Re, *)$$ denotes a space of fuzzy metric [9]. Fuzzy metrics provide a series of advantages to classical metrics and can be incorporated to handle problems with different branches. In particular, several successful applications of fuzzy metric-based image filtering have been introduced in [10,11].

Assuming [TeX:] $$X \in[a, b], G>|a|>0, \alpha>0 \text { and } l=1,2 \ldots n,$$ we define the fuzzy metric to two vectors, namely, [TeX:] $$\boldsymbol{x} \text { and } \boldsymbol{y}, \text { where } \boldsymbol{x}=\left(x_{1}, \ldots, x_{l}\right) \text { and } \boldsymbol{y}=\left(y_{1}, \ldots, y_{l}\right), t>0.$$

As a particular case of well-known fuzzy metrics, let [TeX:] $$\rho(t)$$ be an increasing continuous function, scope in [TeX:] $$[0,+\infty] . \text { If } \alpha>0,$$ the function M is defined by

[TeX:] $$M_{l}^{\alpha}(\boldsymbol{x}, \boldsymbol{y}, t)$$ is considered the degree of closeness between vectors (x, y) with respect to t, which is also called as the fuzzy metric. Vectors (x, y) are associated with the pixels in a squared neighborhood P of the noisy image. The pulse noise reduction filter to a color image in [8] that integrates fuzzy metric and fast similarity has high computing performance and good filtering effect.

3.2 Visual Feature Similarity

Although NLM has offered remarkably promising results, using the structural correlation for image patches and implementing the absence of structural information for the recovered image are unsuitable. In terms of structure and luminance intensity of image patches, this section introduces a similarity measure by visual features on the basis of the fuzzy metric for NLM weights.

Propositions of fuzzy metric depicted in Section 3.1 are combined to obtain the simplified fuzzy metric example that highlights the image edge and texture within a squared neighborhood. Such process aims to emphasize the significance of edge and texture information in the image.

If we take [TeX:] $$\alpha=1 \text { and } \rho(t)=t, \text { setting } \mathrm{y}_{i}=\bar{x}_{i}=\frac{1}{l} \sum_{j=1}^{l} x_{j},$$ then Eq. (4) is simplified as

The fuzzy metric of the image pixel is obtained using Eq. (5). The range of [TeX:] $$H_{x_{i}}$$ is [0, 1], and T is set to 255 corresponding to the grayscale image.

Luminance refers to the fundamental chromatic property of the human visual system. Spatial luminance contrast is a significant visual feature. Luminance contrast difference indicates the maximum and minimum difference of the luminance fuzzy metric of image patches, which is described as

Therefore, luminance contrast fuzzy metric can be expressed as

where [TeX:] $$L_{x_{i}}$$ is the luminance contrast difference for [TeX:] $$x_{i}, L_{x_{j}}$$ is the luminance contrast difference for [TeX:] $$x_{j},$$ and [TeX:] $$|.|$$ is an absolute value operator.

A structure fuzzy metric of the spatial structure closeness between image patches is proposed. [TeX:] $$S F\left(x_{i}, x_{j}\right)$$ is given by

to measure the similarity between the vectors [TeX:] $$\left(x_{i}, x_{j}\right).$$

Finally, the proposed visual feature similarity uses a novel fuzzy metric that describes the distance criteria of luminance and structure, as defined by

where [TeX:] $$\alpha \text { and } \beta$$ are two parameters given by the predesigned values. On this basis, fuzzy metric D measures the similarity between patches by synchronously considering the similarity between the luminance component and structure neighborhood of the patches. As previously stated, [TeX:] $$D\left(x_{i}, x_{j}\right)$$ provides the similarity between [TeX:] $$x_{i} \text { and } x_{j},$$ which will be high only if the two similarities are high.

3.3 NLM Using Visual Feature Similarity Based on Fuzzy Metric

A similarity weight method based on fuzzy metric is applicable for our purposes by using smooth kernel functions and enhances the similarity coefficients. To obtain the accurate similarity of image patches, the improved estimation of NLM image denoising algorithm can be reformed as

where [TeX:] $$w(y(i), \psi)$$ denotes the weight between square patches centered at pixels [TeX:] $$i \text { and } \psi$$ within a squared neighborhood p and satisfies [TeX:] $$0 \leq w(y(i), \psi) \leq 1.$$

The experiments in [4] showed that the Gaussian kernel function has minimal influence in improving the NLM performance. The result will be poor for a large search area. Meanwhile, controlling the bandwidth parameter h of the Gaussian kernel is difficult. Calculating the square root of a matrix is excessively expensive. Instead of Gaussian kernel function, a smoothing kernel function is used to avoid the instability caused by the uncontrolled parameter h to reduce the amount of computation.

[TeX:] $$K_{F l a t}$$ is a smoothing kernel function. Average value of the neighborhood similarity based on the fuzzy metric is used as the threshold of [TeX:] $$K_{F l a t}$$ to prevent the small similarity value of patches in weight allocation.

where [TeX:] $$\overline{D(y(\iota), \psi)}$$ is the average value of the fuzzy metric of neighborhoods. Image patches with small similarity weights are discarded.

3.4 Runtime Analysis

In this section, we conduct a complexity analysis for evaluating efficiency. The proposed algorithm contains two parts of runtime, a fuzzy metric of the pixel, and the visual feature similarity weight. Suppose the number of image pixels is N. The complexity of the fuzzy metric of the pixel is of a linear complexity O(N).

The calculation of H step requires 2N division, 2N comparison, and N summation operations for the entire image. The division is time consuming. In practice, we use a table lookup to improve performance. For grayscale images, the numerator and denominator of Eq. (5) will be limited to [TeX:] $$[t, t+255].$$ The query matrix was constructed by enumerating all possible points in [0,255]; thus, division operation is replaced by checking the lookup table.

The integral image in [3] is applied for summation operations. Visual feature similarity weight between image patches only requires constant two max–min operations, three summations, three subtractions, one comparison, and two multiplications, regardless of the patch size. Therefore, the algorithm efficiency is dramatically improved.

4. Experimental Results

4.1 Experimental Setting and Parameters

Magnetic resonance imaging (MRI) image and three publicly tested images (Barbara, Pepper, and Lena) corrupted with an additive white Gaussian noise with zero mean and variance are selected for experiments to demonstrate the effectiveness of the improved method. Two important performance metrics are introduced to analyze the performance of the proposed method, the NLM method, and several improved methods, such as structural similarity index (SSIM) and peak signal-to-noise ratio (PSNR).

The FF-NLM method is compared with the original NLM, LG-NLM [12] (a feature-based NLM method for image denoising), BM3D [13,14] (a prominent denoising method), and LR-NLM [5] (an NLM denoising method with improved performances and computational times).

Optimum values of the parameters must be selected to enhance the effectiveness of FF-NLM method. After the simulation, we establish that the best value selection of parameter [TeX:] $$(\alpha, \beta)$$ is (1,1). Search area R and patch size B are crucial parameters influencing the performance of the denoising method. Search area R is set to [TeX:] $$21 * 21$$ on the basis of a study [13] to obtain high performance in terms of efficiency and denoising effect. Hence, in our experiments, search range R is 21. The larger the patch is, the more plentiful the image edge and texture are. However, the patch is too large, resulting in less similar image patches, which leads to a low weight accuracy. The experiment images corrupted with standard deviations [TeX:] $$\sigma=\{5,15,25,45\}$$ are evaluated using SSIM to acquire the optimal patch size. When B = 3, 5, 7, and 9, the denoising performance is increased. However, when B = 11, 13, and 15, the PSNR values decrease slightly as the patch size increases. Therefore, the optimal value of patch size B is 9.

4.2 Experimental Comparison and Performance Analysis

Our method and LG-NLM were performed in MATLAB 2015b, and the source programs of NLM, LRNLM, and BM3D were obtained in the author’s website. Fig. 1 shows the results of different denoising methods on noise MRI images with the same parameters.

Fig. 1(b)–1(f) show that our method obtains the best PSNR in dB, compared with other methods. Fig. 2(b) presents the detail of the image in Fig. 2(a) after zooming. Fig. 2(c)–2(f) exhibit the denoising results of different methods, including LG-NLM, BM3D, and LR-NLM. Our method can effectively obtain noise suppression, texture preservation, and clearer details than other methods. For example, recovered results of the lady’s headscarf are hardly possible to achieve due to texture details, as demonstrated in Fig. 2(d)– 2(f). Moreover, many artifacts are visible near the headscarf. The recovered results of LG-NLM and LRNLM methods are inclined to contain more blocking artifacts than those of other methods. Our method demonstrates clearer detail preservation and edge sharpness than the traditional NLM methods. The reason is that the proposed method with fuzzy metric has the best quality, and it can lower the artifacts by measuring the subtle changes in the image structure.

Two vital performance evaluation indexes (PSNR and SSIM) [15] are computed on Barbara, Pepper, Lena, and MRI slice images with different standard deviations [TeX:] $$(\sigma=10,30, \text { and } 50)$$ to demonstrate the superiority of our proposed method. Tables 1 and 2 show the numerical results. The first PSNR of denoising methods is shown in bold. In light of PSNR, the best results are obtained using the proposed method.

The numbers in the SSIM metric represent the difference between the traditional and FF-NLM methods (Table 2). In Table 2, the overall PSNR and SSIM of LR-NLM and LG-NLM are good, but the performance of SSIM value drops significantly. LG-NLM and LR-NLM based on Euclidean distance have less interference resistance in the case of strong noise.

As the image texture of Barbara and Lena is rich, the proposed algorithm and BM3D have high denoising capability. However, under a high noise level, the performance of BM3D significantly decreases, and that of our proposed algorithm is maintained well. The proposed algorithm can efficiently obtain the image structure information through the visual features of a fuzzy metric and reduce the influence of noise on similarity weighting.

Residual noise (RN) refers to the difference between the denoised and noisy images. Useful information of the image is taken into the RN brought by denoising methods. Hence, the RN is also a subjective quality evaluation of the quantity of information in the RN. Figs. 3 and 4 display the comparisons of RN images of Lena and Pepper with noise, respectively, obtained by different test methods. The fewer the reserved structural information in the RN image, the finer the performance. RN images obtained by BM3D and LG-NLM methods include more structural information than other test methods. Several image structures of the Pepper image with noise are seriously lost with the LG-NLM and BM3D methods. RN images obtained by NLM, BM3D, LR-NLM, and LG-NLM reserve distinct structural information in the head zone of the Lena image. However, structural information disappears in the RN images in Fig. 4(b). The RN image of our proposed method retains minimum structural information of the images in Figs. 3 and 4. The reason is that measure similarity index is developed using fuzzy metrics and smooth kernel functions, which can efficiently retain image structures.

We conducted simulations in a notepad with Intel Core i5, M460 @2.53 GHZ of CPU, and 4 GB memory using MATLAB 2016a to validate the proposed FF-NLM method. Table 3 shows the comparison of average running times of four images with different sizes of this proposed method with BM3D, LGNLM, LR-NLM, and NLM. Table 3 shows that FF-NLM in an image size of 128 × 128 requires more complexity than LG-NLM and LR-NLM. Although LG-NLM takes the least time, its extraction feature causes the image details to be lost seriously.

As the image increases, fuzzy metric and similarity weight effectively eliminate low-weight patches. The computational complexity of the proposed method is significantly reduced.

5. Conclusions

A novel fuzzy NLM algorithm for Gaussian denoising was proposed. The NLM method based on a novel patch similarity measure was developed. This method was adopted to measure the similarity of structure and luminance between image patches with a fuzzy metric. Kernel function was used to calculate the weights and filter image patches with low weights from experiment results to reduce computational time by adopting the threshold. A comparison using three public test images and an MRI image slice showed that the proposed method has better visual quality and PSNR and SSIM metrics than existing methods. Therefore, our proposed method is competitive.

Acknowledgement

This study was funded by Innovation Foundation (Believe in Engineering) of Sichuan Province of China (No. 2019088).