Fractional-order Sparse Representation for Image Denoising

Ⅰ. INTRODUCTION

Image denoising is one of the most important research subjects in image processing due to its fundamental role in a number of applications, such as medical imaging, remote sensing, surveillance and entertainment. Generally, the observed noisy image $\boldsymbol{y}$ can be formulated as $\boldsymbol{y=x+n}$ , where $\boldsymbol{x}$ is the clean image and $\boldsymbol{n}$ is an additive white Gaussian noise with zero-mean and standard deviation $\sigma$ . In the past decades, extensive studies have been conducted to develop various image denoising approaches, such as total variation (TV) regularization [1], non-local means (NLM) algorithm [2] and block-matching and 3D (BM3D) filtering algorithm [3]. Although classical approaches are effective in removing noise artifacts, the TV regularization tend to over-smooth images due to the piecewise constant assumption and the computational complexity of the BM3D is extremely high. As an alternative, sparse representation-based models have recently led to promising results [4]-[7].

Sparse representation-based models assume that an image $\boldsymbol{x}$ can be represented as $\boldsymbol{x}\thickapprox D{\boldsymbol \alpha}$ , where $D\in \mathbb{R}^{n\times m}$ is an over-complete dictionary and most entries of the sparse coefficients $\alpha$ are zero or close to zero. The sparse decomposition of $\boldsymbol{x}$ can be obtained by solving an $l_0$ -minimization problem, i.e., $\boldsymbol{\alpha}= \arg\min_{\alpha}\Vert{\boldsymbol{\alpha}}\Vert_0$ , s.t. $\Vert{\boldsymbol{x}-D{\boldsymbol \alpha}}\Vert_2\leq\varepsilon$ , where $\Vert\cdot\Vert_0$ is a pseudo norm and $\varepsilon$ is a small constant. Since $l_0$ -minimization is a NP (none-deterministic polynomial)-hard combinatorial optimization problem, it is often relaxed to $l_1$ -minimization. The $l_1$ -norm based model can be solved efficiently by convex optimization techniques, formulated as $\{\boldsymbol{\alpha},{D}\}= \arg\min_{\alpha}\{\Vert{\boldsymbol{x}-{D}{\boldsymbol \alpha}}\Vert^2_2 + \lambda\Vert{\boldsymbol{\alpha}}\Vert_1\}$ , where $\lambda$ denotes the regularization parameter. Many efficient $l_1$ -minimization techniques have been proposed, such as iterative thresholding algorithms [8], [9], Bregman split algorithms [10], [11] and so on.

Dictionary learning is a key problem of sparse representation-based models. Comparing with analytically designed dictionaries (e.g., the wavelet/curvelet dictionary), dictionaries learned from example image can greatly improve the denoising performance because they can better characterize the image structures [12]-[16]. For example, [16] estimated the sparse coefficients by exploiting nonlocal self-similarity in the observed image. Recently, most conventional sparse representation-based models concentrate on learning the adaptive dictionary directly from the noisy image itself instead of from the external image database. The main advantages are that the self-structural information is exploited and the trained dictionary is adaptive to the image of interest. However, the training samples extracted directly from the observed image are inevitably corrupted by noise. Thus, accurate sparse coefficients and optimal dictionary cannot be obtained efficiently in the noisy sample space. Consequently, the performance and efficiency of conventional sparse representation-based models are limited.

In this paper, we propose a fractional-order sparse representation (FSR) model to obtain better estimations for both the sparse coefficients and the dictionary. First, we cluster external training image patches into multiple groups to explore image self-similarity. Then we calculate the singular values for each clean/noisy patch pair in the wavelet domain and learn the uniform fractional-order parameters for each cluster. To deal with the noisy image, a novel sample space is constructed using adaptive fractional-order parameters in the wavelet domain. In this way, we can obtain more accurate sparse coefficients and dictionary for image denoising. Comparing with several state-of-the-art sparse representation-based models [4], [16] and the BM3D algorithm [3], our proposed FSR model clearly performs better in terms of both denoising performance and computational efficiency.

Ⅱ. BACKGROUND AND RELATED WORK

A Sparse Representation-based Denoising Model

Given the dictionary $D_{\boldsymbol{x}}$ , an image patch $\boldsymbol{x}_i= {R}_i\boldsymbol{x}$ , extracted from the clean image $\boldsymbol{x}$ at the location $i$ , can be sparsely represented by solving the non-convex $l_1$ -optimization:

Then, the target image $\boldsymbol{x}$ can be constructed by averaging each image patch $\boldsymbol{x}_i$ with a straightforward least-square solution in [12]:

The conventional sparse representation (SR) denoising models recover $\boldsymbol{x}$ from noisy image $\boldsymbol{y}$ by solving the following minimization problem:

Then, by adding auxiliary variable $\boldsymbol{x}_i={D}_{{\boldsymbol{y}}}\boldsymbol{\alpha}_{{\boldsymbol{y}}, i}$ , the denoised image $\widehat{\boldsymbol{x}}$ is reconstructed with a closed-form solution in [17]:

B Fractional-order Technique

In recent years, the fractional-order technique has been widely used in image denoising [18], texture enhancement [19], image reconstruction [20], face representation [21], and other applications. Reference [18] proposed a fractional-varying-order differential-based method for image denoising. This method varied the gradient of images to suppress the blocky effect. Moreover, it retained more texture details than the integral order partial differential denoising model due to the fractional differential amplitude frequency. Reference [19] presented a fractional differential-based method for multi-scale texture enhancement. This method could nonlinearly enhance complex texture details, which has been proven superior to traditional integral-based algorithms. Reference [20] incorporated fractional derivatives and edge detection in a method called fractional-order partial differential-based image reconstruction. The fractional derivative has been demonstrated to be superior to the integer derivative. In face representation, [21] proposed a fractional-order embedding canonical correlation analysis to reduce the dimensionality of multi-view data. This method constructed the fractional-order both within-set and between-set scatter matrices to alleviate the deviation of the eigenvalues and singular values in the corresponding sample covariance matrices. We can conclude that the fractional-order technique targets at a more general framework of nonlinear and flexible data processing mode. Therefore, we introduce the fractional-order technique into the sparse representation model to obtain more accurate sparse coefficients and dictionary.

Ⅲ. MODELING OF FRACTIONAL-ORDER SPARSE REPRESENTATION

A Motivation

For effective image denoising, the dictionary ${D}_{{\boldsymbol{y}}}$ and the sparse coefficients $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ obtained by solving the minimization problem in (3) are respectively expected to be as close as possible to the ${D}_{{\boldsymbol{x}}}$ and the $\boldsymbol{\alpha}_{{\boldsymbol{x}}}$ obtained by (1). However, due to the noise in the observed image, ${D}_{{\boldsymbol{y}}}$ and $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ will deviate from their true values. Thus, both ${D}_{{\boldsymbol{y}}}$ and $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ cannot be considered as good approximations, and would directly decrease the quality of the denoised image. To further illustrate these difference, we define the deviation degree of the dictionary ${D}_{{\boldsymbol{y}}}$ as Dev $({D}_{{\boldsymbol{x}}}, {D}_{{\boldsymbol{y}}})$ and the deviation degree of the sparse coefficients $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ as Dev $(\boldsymbol{\alpha}_{{\boldsymbol{x}}}, \boldsymbol{\alpha}_{{\boldsymbol{y}}})$ .

Definition 1: Suppose ${D}_{{\boldsymbol{x}}}=\{\boldsymbol{d}_{{\boldsymbol{x}}, 1}, \boldsymbol{d}_{{\boldsymbol{x}}, 2}, \ldots, \boldsymbol{d}_{{\boldsymbol{x}}, m}\}$ is an over-complete dictionary containing $m$ dictionary atoms learned from the original image $\boldsymbol{{\boldsymbol{x}}}$ , and ${D}_{{\boldsymbol{y}}}=\{\boldsymbol{d}_{{\boldsymbol{y}}, 1}, \boldsymbol{d}_{{\boldsymbol{y}}, 2}, \ldots, \boldsymbol{d}_{{\boldsymbol{y}}, m}\}$ is an over-complete dictionary containing $m$ dictionary atoms learned from the noisy image $\boldsymbol{y}$ . Then, the deviation degree of the dictionary ${D}_{{\boldsymbol{y}}}$ is defined as:

where Dev $({D}_{{\boldsymbol{x}}}, {D}_{{\boldsymbol{y}}})$ denotes the deviation degree vector of the dictionary ${D}_{{\boldsymbol{y}}}$ , $\boldsymbol{dev}_i$ denotes the $i$ th deviated element referring to the $i$ th dictionary atom $\boldsymbol{d}_{{\boldsymbol{y}}, i}$ , and $\boldsymbol{d}_{{\boldsymbol{x}}, j}\cdot\boldsymbol{d}_{{\boldsymbol{y}}, i}$ denotes the inner product of $\boldsymbol{d}_{{\boldsymbol{x}}, j}$ and $\boldsymbol{d}_{{\boldsymbol{y}}, i}$ . The definition of Dev $({D}_{{\boldsymbol{x}}}, {D}_{{\boldsymbol{y}}})$ describes the ability that the dictionary ${D}_{{\boldsymbol{y}}}$ express the noisy image $\boldsymbol{y}$ . When the Dev $({D}_{{\boldsymbol{x}}}, {D}_{{\boldsymbol{y}}})$ is zero, the ${D}_{{\boldsymbol{y}}}$ is as the same as the ${D}_{{\boldsymbol{x}}}$ and the noise can be restrained effectively.

Definition 2: Suppose that $\boldsymbol{\alpha}_{{\boldsymbol{x}}}$ is the sparse coefficients of the clean image patch and $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ is the sparse coefficients of the noise image patch. Then, the deviation degree of the sparse coefficients $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ is defined as:

where $\Vert\cdot\Vert_F$ denotes the Frobenius norm. The definition of Dev $(\boldsymbol{\alpha}_{{\boldsymbol{x}}}, \boldsymbol{\alpha}_{{\boldsymbol{y}}})$ describes the similarity between $\boldsymbol{\alpha}_{{\boldsymbol{x}}}$ and $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ . As the Dev $(\boldsymbol{\alpha}_{{\boldsymbol{x}}}, \boldsymbol{\alpha}_{{\boldsymbol{y}}})$ is close to zero, the sparse coefficients $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ is similar to its corresponding true value $\boldsymbol{\alpha}_{{\boldsymbol{x}}}$ .

To show the deviation degrees, we conducted experiments using the Lena image. We added Gaussian white noise ( $\sigma=$ 20) to the original image $\boldsymbol{x}$ to obtain the noisy image $\boldsymbol{y}$ . For fair comparison, both $\boldsymbol{\alpha}_{{\boldsymbol{x}}}$ and $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ were obtained using fixed discrete cosine transform (DCT) bases. Figs. 1(a) and 1(b) plot the distributions of Dev $({D}_{{\boldsymbol{x}}}, {D}_{{\boldsymbol{y}}})$ and Dev $(\boldsymbol{\alpha}_{{\boldsymbol{x}}}, \boldsymbol{\alpha}_{{\boldsymbol{y}}})$ , respectively.

Figure  1.  Distributions of Dev $({D}_{{\boldsymbol{x}}}, {D}_{{\boldsymbol{y}}})$ and Dev $(\boldsymbol{\alpha}_{{\boldsymbol{x}}}, \boldsymbol{\alpha}_{{\boldsymbol{y}}})$ when the Lena image is noisy ( $\sigma = 20$ ).

DownLoad: Full-Size Img PowerPoint

Note that most deviation degrees of dictionary atoms are over 0.1 and the highest value is about 0.71. As shown in Fig. 1(b), more than 80 % of Dev $(\boldsymbol{\alpha}_{{\boldsymbol{x}}}, \boldsymbol{\alpha}_{{\boldsymbol{y}}})$ concentrated in 0.05-0.12. Hence the accurate $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ and optimal ${D}_{{\boldsymbol{y}}}$ cannot be obtained from the noisy image by the SR models. The definitions of Dev $({D}_{{\boldsymbol{x}}}, {D}_{{\boldsymbol{y}}})$ and Dev $(\boldsymbol{\alpha}_{{\boldsymbol{x}}}, \boldsymbol{\alpha}_{{\boldsymbol{y}}})$ indicate that it is possible to further improve the denoising performance by improving the accuracy of both $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ and ${D}_{{\boldsymbol{y}}}$ . However, it is difficult to directly improve the accuracy of $\boldsymbol{\alpha}_{{\boldsymbol{y}}}$ and ${D}_{{\boldsymbol{y}}}$ in the observed sample space due to noise disturbance. To address this problem, we construct a novel sample space by correcting singular values utilizing the cluster-based fractional-order technique with adaptive parameters in the wavelet domain.

B Fractional-order Sparse Representation Model

The FSR model involves the training phase and the denoising phase:

In the training phase, we learn the fractional-order parameters from external image database including four steps:

Step 1: We cluster the training image patches into $K$ clusters (typically $K$ =10) using $K$ -means algorithm and decompose those patches into frequency sub-patches by the discrete Haar wavelet transform;

Step 2: We calculate singular values for each patch;

Step 3: The fractional-order parameter ${{\boldsymbol{\eta}}}_{ij}$ of each patch is obtained given the clean/noisy patch pairs;

Step 4: We compute the uniform fractional-order parameter $\boldsymbol{\eta}_{i}$ for each training patch group with similar textures.

In the denoising phase, the noisy image is first decomposed into Haar wavelet images. Then the fractional-order parameter is employed to construct the novel fractional-order sample space, and the denoised image is reconstructed by sparse coefficients and dictionary. The flowchart of the FSR model is shown in Fig. 2.

Figure  2.  Flowchart of the proposed FSR model.

DownLoad: Full-Size Img PowerPoint

1) Deviation Degree of Singular Values: For an image patch $\boldsymbol{x}_{i}$ , we have the singular value decomposition (SVD) [22] as $\boldsymbol{x}_i={P}_{i}{\it\Lambda}_{i}{Q}_{i}$ , where ${P}_{i}$ and ${Q}_{i}$ are the left and right singular matrices, respectively, ${\it\Lambda}_{i}={\rm diag}\{s_{i, 1}, s_{i, 2}, \ldots, s_{i, \sqrt{n}}\}$ is a singular value matrix, and $s_{i, 1}\geq s_{i, 2}\geq \cdots\geq s_{i, \sqrt{n}}$ are the descending order singular values. The singular values can be interpreted as the variance estimation and they expose the geometric structure of the image. Hence, the singular values represent the intrinsic and algebraic properties containing illumination, noise and texture. Due to the disturbance of noise, the singular values obtained from the noisy image deviate from their true values. Similarly, we can define the deviation degree of singular values as Dev $({\it\Lambda}_{{\boldsymbol{x}}}, {\it\Lambda}_{{\boldsymbol{y}}})$ .

Definition 3: Suppose ${\it\Lambda}_{{\boldsymbol{x}}}={\rm diag}\{s_{{\boldsymbol{x}}, 1}, s_{{\boldsymbol{x}}, 2}, \ldots, s_{{\boldsymbol{x}}, \sqrt{n}}\}$ denotes the singular value matrix of the original image patch, and ${\it\Lambda}_{{\boldsymbol{y}}}={\rm diag}\{s_{{\boldsymbol{y}}, 1}, s_{{\boldsymbol{y}}, 2}, \ldots, s_{{\boldsymbol{y}}, \sqrt{n}}\}$ denotes the singular value matrix of the noise image patch. Then, the deviation degree of the singular values is defined as:

To show the deviation degree of the singular values, we plotted the distribution of Dev $({\it\Lambda}_{{\boldsymbol{x}}}, {\it\Lambda}_{{\boldsymbol{y}}})$ in Fig. 3, where ${\it\Lambda}_{{\boldsymbol{y}}}$ was computed from the noisy Lena image ( $\sigma =20$ ). As observed in Fig. 3, it is evident that the singular values differ greatly from their true values and most Dev $({\it\Lambda}_{{\boldsymbol{x}}}, {\it\Lambda}_{{\boldsymbol{y}}})$ are over 4. Recently, this deviation has been demonstrated to have a negative effect on classification systems [21]. Motivated by the above situation, we re-estimate the singular values using fractional-order techniques.

Figure  3.  Deviation degree of singular values.

DownLoad: Full-Size Img PowerPoint

2) Multi-scale Decomposition: As mentioned above, due to disturbance of noise, the singular values deviate from their true values. The denoised image would involve unexpected perturbations when the singular values are directly obtained from the noisy image space. As illustrated in Fig. 4, the re-estimated image Fig. 4(c) is directly reconstructed using the corresponding singular values obtained from the original Lena image Fig. 4(a). Although the extrinsic disturbance (noise) is restrained (e.g., Fig. 4(b)), other new disturbances are involved. Because the extrinsic factor (noise) can be largely isolated from the intrinsic factor (texture) in the frequency sub-spaces, the re-estimated sample space can avoid these unexpected perturbations. Thus, it is necessary to correct the singular values of noisy image patches in the wavelet domain.

Figure  4.  Comparison of experimental results.

DownLoad: Full-Size Img PowerPoint

3) Fractional-order Parameter Learning: Since the proposed FSR model involves the fractional-order technique, the key problem is that how to choose the fractional-order parameter $\boldsymbol{\eta}$ . In this paper, we first cluster the training image patches into $K$ groups using the $K$ -means clustering method. For each patch in the $i$ th cluster, we calculate the fractional-order by $\boldsymbol{\eta}_{ij} = \arg\min {\rm Dev}({\it\Lambda}_{{\boldsymbol{x}}}, {\it\Lambda}_{{\boldsymbol{y}}})$ . Then the uniform fractional-order parameter $\boldsymbol{\eta}_{i}$ for each training group is obtained by $\boldsymbol{\eta}_{i} = \arg\min_{\boldsymbol{\eta}_{i}} \sum{ \| \boldsymbol{\eta}_{i} - \boldsymbol{\eta}_{ij} \|^2_F}$ . Furthermore, the cluster number $K$ (typically $K$ =10) is determined by a series of experiments. We utilize the cross-validation method to determine the parameter $K$ with optimal peak signal to noise ratio (PSNR) of the denoised image. Fig. 5 plots the distribution of PSNR average results over five typical images (e.g., Lena/Barbara/Boat/House/Pepper). We can see that there is little improvement of the image denoising performance over all noise levels as the cluster number increases. Therefore, we cluster the samples into 10 groups in terms of the effectiveness and efficiency.

Figure  5.  Comparison of PSNRs with various cluster numbers and various noise levels.

DownLoad: Full-Size Img PowerPoint

4) Fractional-order Image Denoising: With the trained fractional-order parameters, we denoise the image in the novel fractional-order sample space. Now, we define the fractional-order patch as follows:

Definition 4: Suppose $\boldsymbol{\eta} = \{ \boldsymbol{\eta}_{1}, \boldsymbol{\eta}_{2}, \ldots, \boldsymbol{\eta}_{\sqrt{n}}\}$ is a fractional-order parameter, and each fractional element $\boldsymbol{\eta}_{k}$ satisfies $0 \leq \boldsymbol{\eta}_{k} \leq 1$ . Then, the fractional-order patch $\boldsymbol{y}^{\boldsymbol{\eta}}_i$ is referred to as:

where ${P}_{i}$ and ${Q}_{i}$ are respectively the left and right singular matrices of the noisy patch $\boldsymbol{y}_i$ , and ${{\it\Lambda}}^{\boldsymbol{\eta}}_{i}$ denotes the fractional-order singular value matrix. In Definition 4, it is obvious that the decomposition in (8) subsume the thin SVD as a special case when $\boldsymbol{\eta} = \{1, 1, \ldots, 1\}$ . Based on Definition 4, the following properties are observed:

Property 1: The rank of $\boldsymbol{y}^{\boldsymbol{\eta}}_i$ is equal to the rank of $\boldsymbol{y}_i$ , i.e., rank $(\boldsymbol{y}^{\boldsymbol{\eta}}_i)$ = rank $(\boldsymbol{y}_i)$ .

Property 2: $\| \boldsymbol{y}^{\boldsymbol{\eta}}_i - \boldsymbol{y}_i \|^2_F = \sum_{m=1}^{\sqrt{n}} ( s^{{\boldsymbol{\eta}}_m}_m- s_m)^2$ , where $\| \cdot \|_F$ denotes the Frobenius norm.

Property 1 shows the basic characteristics of the novel fractional-order sample. Property 2 reveals that the space distance between $\boldsymbol{y}^{\boldsymbol{\eta}}_i$ and $\boldsymbol{y}_i$ can be controlled by adjusting the fractional-order parameter $\boldsymbol{\eta}$ .

After constructing fractional-order patches, we build a novel sparse representation-based model for image denoising. The proposed fractional-order image denoising phase is an iterative algorithm that alternates between fractional-order sample space construction and dictionary learning. In the fractional-order sample space construction stage, the noisy image is first decomposed into different frequency sub-spaces by the discrete Haar wavelet transform with 2 levels. For a noisy patch, we calculate the distance between it and all clustering centers of groups. Then we construct the fractional-order patch using the corresponding fractional-order parameter of the nearest patch group. In the sparse coding and dictionary learning stage, we calculate sparse coefficients for fractional-order patches and update dictionary atoms. Finally, the denoised image can be reconstructed by overlapping image patches. Therefore, the proposed algorithm can be summarized in Algorithm 1.

Ⅳ. EXPERIMENTAL RESULTS AND ANALYSIS

To demonstrate the superior performance of the proposed FSR model, in this section, we presented extensive experiment results on five typical images with simple and complex textures with various noise levels. We compared the proposed FSR model with three current state-of-the-art image denoising approaches: the conventional sparse representation (SR) denoising model [4], nonlocally centralized sparse representation (NCSR) denoising model [16] and the BM3D image denoising with shaped-adaptive principal component analysis (SAPCA-BM3D) algorithm [3] (it is an enhanced version of BM3D denoising in which local spatial adaptation is achieved by shaped-adaptive principal component analysis (PCA)).

Algorithm 1 Fractional-order Image Denoising

Input: Noisy image $\boldsymbol{y}$ . Output: Denoised image ${\widehat{\boldsymbol{x}}}^{(t+1)}$ . Initialization: Set ${\widehat{\boldsymbol{x}}}^{(0)} = \boldsymbol{y}$ , ${D}^{(0)} = \rm{{DCT}}$ dictionary. while not converge do 1. Construct novel fractional-order sample space. 1) Decompose the noisy image into frequency sub-spaces using the discrete Haar wavelet transform. 2) Construct the novel fractional-order sample space using adaptive fractional-order parameters. 2. Sparse coding and dictionary learning. 1) Calculate sparse coefficient for each fractional-order patch. 2) Update atom $d_l, ~l=1, 2, \ldots, k$ by a) Find the set of patches: $\omega_l = \{ (i, j) |\boldsymbol{\alpha}_{ij}(l) \neq 0 \}$ and calculate the error matrix by $\boldsymbol E_{l} = \{ \boldsymbol{e}^l_{ij} | \boldsymbol{e}^l_{ij} =({\widehat{\boldsymbol{x}}}^{(t+1)}_{ij})^{\boldsymbol{\eta}_i} - \sum_{m \neq l} d_m \boldsymbol{\alpha}_{ij}(m) \}_{ (i, j) \in \omega_l }$ b) Update the dictionary atom and the coefficient values. 3. If $\|{\widehat{\boldsymbol{x}}}^{(t+1)} -{\widehat{\boldsymbol{x}}}^{(t)}\|^2_2\leq\varepsilon$ , break. end while

 | Show Table

DownLoad: CSV

In the proposed FSR model, 40 000 overlapping image patches of size 8 $\times$ 8 were directly extracted from noisy images and were clustered into 10 groups. The fraction-order patches in each cluster were constructed using their corresponding fraction-order parameters in the discrete Haar wavelet domain. Then we trained a redundant dictionary of size 64 $\times$ 256 based on the initial DCT dictionary. Finally, the denoised patches were averaged using the Lagrange multiplier $\lambda = 30 / \sigma$ , as described in (4). The SR denoising model trained a dictionary based on the 40 000 image patches of size 8 $\times$ 8 extracted from the noisy images using the same parameters as those of the proposed FSR model. The NCSR denoising model clustered patches into 70 groups and computed the sparse coefficients using iterative shrinkage algorithm (parameters details in [16]). The SAPCA-BM3D algorithm was applied to the noisy image using a shape-adaptive transform basis. In this method, similar blocks were found in a 25 $\times$ 25 local neighborhood using block matching with the maximum $d$ -distance $\tau$ = 2500. In the collaborative filtering stage, PCA was employed as part of the 3D transform.

A Comparison of Denoising Performance

To demonstrate the denoising performance of the proposed FSR model, we performed a set of experiments on five typical images: Lena, Barbara, Boat, House and Pepper. The experiments were performed 10 times, and the average results were reported for five noise levels $\sigma$ = 5, 10, 20, 35, 50. We evaluated the quality of the denoised images using the popular PSNR (in dB) and structural similarity index measurement (SSIM).

The PSNR results are listed in Table Ⅰ. As seen in Table Ⅰ, the proposed FSR model obtains excellent denoising performance, and 72 % PSNR results are the best among four comparison approaches. Although the SAPCA-BM3D algorithm obtains 20 % of the best PSNR results, the approach is very time-consuming as described in Section Ⅳ-B. Note that, with little disturb of the noise, most textures are preserved at the lowest noise level $\sigma$ = 5. For the smooth Pepper image, the SAPCA-BM3D algorithm can sufficiently exploit the self-similarities of patches. Hence, the SAPCA-BM3D result (38.30 dB) is superior to sparse representation-based results, i.e., the SR result (37.79 dB), the NCSR result (38.06 dB) and the proposed FSR result (37.78 dB).

Table  Ⅰ.  AVERAGE DENOISING RESULTS (PSNR IN DB) FOR VARIOUS NOISY LEVELS, OBTAINED BY THE SAPCA-BM3D, SR, NCSR AND FSR MODEL. THE BEST RESULT IS HIGHLIGHTED.

Method	$\sigma$	PSNR (dB)
		Lena (5122)	Barbara (5122)	Boat (5122)	House (2562)	Pepper (5122)
SAPCA-BM3D	5	38.86	38.38	37.50	40.13	$\boldsymbol{38.30}$
	10	36.07	35.07	34.10	37.06	34.94
	20	33.20	31.97	31.02	$\boldsymbol{34.03}$	31.61
	35	30.55	$\boldsymbol{28.97}$	28.42	31.36	28.51
	50	$\boldsymbol{29.07}$	$\boldsymbol{27.51}$	26.89	29.53	26.94
SR	5	38.61	38.27	37.18	39.65	37.79
	10	35.56	34.65	33.73	36.26	34.84
	20	32.36	30.92	30.42	33.33	32.29
	35	29.59	27.69	27.61	30.41	29.94
	50	27.83	25.42	25.93	28.03	27.99
NCSR	5	38.70	38.36	37.35	39.91	38.06
	10	35.81	34.98	33.90	36.80	34.66
	20	32.92	31.72	30.74	33.97	31.26
	35	30.56	28.69	28.14	$\boldsymbol{31.49}$	28.30
	50	28.89	27.10	26.60	$\boldsymbol{29.63}$	26.53
FSR	5	$\boldsymbol{40.55}$	$\boldsymbol{39.86}$	$\boldsymbol{37.57}$	$\boldsymbol{41.19}$	37.78
	10	$\boldsymbol{37.13}$	$\boldsymbol{36.82}$	$\boldsymbol{35.68}$	$\boldsymbol{37.12}$	$\boldsymbol{36.38}$
	20	$\boldsymbol{33.61}$	$\boldsymbol{32.56}$	$\boldsymbol{32.53}$	33.69	$\boldsymbol{33.98}$
	35	$\boldsymbol{30.78}$	28.65	$\boldsymbol{29.67}$	31.00	$\boldsymbol{31.46}$
	50	28.93	26.40	$\boldsymbol{27.87}$	29.11	$\boldsymbol{29.69}$

 | Show Table

DownLoad: CSV

To better visualize the experimental comparison, Fig. 6(a) presents the average PSNR results over all test images for each noise level. Note that the FSR model leads to the best denoising performance on all noise levels. Although the FSR does not exploit image self-similarities as the SAPCA-BM3D algorithm does, the FSR outperforms SAPCA-BM3D by 0.96 dB. The FSR model outperforms other two sparse representation-based models: the SR model by up to 1.35 dB and the NCSR model by up to 1.0 dB, respectively. Furthermore, the NCSR model performs almost the same as the SAPCA-BM3D algorithm. In terms of the PSNR standard deviation, as depicted in Fig. 6(b), the FSR model improves the robustness for four out of five noise levels. Due to the weak capacity of the FSR model for the smooth Pepper image, the FSR model falls behind other three models at the low noise level $\sigma$ = 5.

Figure  6.  Comparison of the average and the standard deviations of PSNR on various noise standard deviations.

DownLoad: Full-Size Img PowerPoint

For further evaluation of the denoising performance, we calculated the SSIM results of the denoised images. Table Ⅱ shows that 56 % of the SSIM results obtained by our proposed FSR model are higher than those obtained by other three approaches. Note that, for the smooth Pepper image, the average SSIM result is 0.87 for the SAPCA-BM3D algorithm, 0.84 for the SR model, 0.88 for the NCSR model and 0.85 for the FSR model. Thus, for a smooth image, the NCSR model achieves a better result than other two sparse representation models (e.g., SR/FSR). However, the proposed FSR model outperforms best in most cases.

Table  Ⅱ.  AVERAGE DENOISING RESULTS (SSIM) FOR VARIOUS NOISY LEVELS, OBTAINED BY THE SAPCA-BM3D, SR, NCSR AND FSR MODEL. THE BEST RESULT IS HIGHLIGHTED.

Method	$\sigma$	SSIMs
		Lena (5122)	Barbara (5122)	Boat (5122)	House (2562)	Pepper (5122)
SAPCA-BM3D	5	0.94	0.96	0.93	0.95	0.95
	10	0.91	0.94	0.88	0.92	0.92
	20	0.87	0.90	0.82	0.87	0.88
	35	0.82	0.84	0.75	0.83	0.83
	50	$\boldsymbol{0.79}$	0.79	0.70	0.81	0.79
SR	5	0.95	0.96	0.93	0.96	0.93
	10	0.91	0.94	0.88	0.91	0.88
	20	0.86	0.88	0.80	0.86	0.84
	35	0.81	0.79	0.72	0.82	0.80
	50	0.76	0.71	0.66	0.77	0.76
NCSR	5	0.95	0.94	$\boldsymbol{0.94}$	0.96	$\boldsymbol{0.95}$
	10	0.92	0.94	0.88	0.92	$\boldsymbol{0.92}$
	20	0.87	0.90	0.81	$\boldsymbol{0.87}$	$\boldsymbol{0.88}$
	35	$\boldsymbol{0.83}$	0.85	0.74	$\boldsymbol{0.84}$	$\boldsymbol{0.84}$
	50	0.72	0.78	0.69	$\boldsymbol{0.82}$	$\boldsymbol{0.79}$
FSR	5	$\boldsymbol{0.96}$	$\boldsymbol{0.97}$	0.93	$\boldsymbol{0.97}$	0.91
	10	$\boldsymbol{0.93}$	$\boldsymbol{0.95}$	$\boldsymbol{0.91}$	$\boldsymbol{0.92}$	0.90
	20	$\boldsymbol{0.87}$	$\boldsymbol{0.92}$	$\boldsymbol{0.86}$	0.86	0.86
	35	0.80	$\boldsymbol{0.85}$	$\boldsymbol{0.78}$	0.83	0.80
	50	0.73	$\boldsymbol{0.79}$	$\boldsymbol{0.72}$	0.78	0.77

 | Show Table

DownLoad: CSV

Figs. 7(a) and 7(b) show the visual comparison of the average SSIM and their standard deviation. Fig. 7(a) shows that the FSR is slightly better than other three methods for low and moderate noise levels ( $\sigma$ = 5, 10, 20). Because the SAPCA-BM3D algorithm and NCSR model utilize the structural similarity among numerous similar image patches, the corresponding results are superior to the FSR results at the high noise levels ( $\sigma$ = 35, 50). In terms of the SSIM standard deviation, as depicted in Fig. 7(b), the proposed FSR model improves the robustness except at the low noise level ( $\sigma$ = 5).

Figure  7.  Comparison of the average and the standard deviations of SSIM for various noise standard deviations.

DownLoad: Full-Size Img PowerPoint

Figs. 8-10 illustrate the visual comparison of denoised results for three typical images (Pepper, Boat and Barbara) at moderate noise levels ( $\sigma$ = 20). Figs. 8(a)-8(e) show the denoised images, and Figs. 8(g)-8(j) show the corresponding noisy components. It can be observed from Fig. 8 that the FSR model delivers the best visual quality. The SAPCA-BM3D and SR methods tend to suffer from noticeable artifacts around the smooth areas, as shown in Fig. 9. Furthermore, for regions with complex textures, the superiority of the FSR model is visually justified by Fig. 10.

Figure  8.  Denoising performance comparison on the Pepper image with moderate noise corruption. (a) Noisy image ( $\sigma$ = 20); denoised images by (b) SAPCA-BM3D (PSNR = 31.61 dB, SSIM = 0.88); (c) SR (PSNR = 32.29 dB, SSIM=0.84); (d) NCSR (PSNR = 31.26 dB, SSIM = 0.88); (e) FSR (PSNR = 33.98 dB, SSIM = 0.86); (f) real noisy component; corresponding noisy components by (g) SAPCA-BM3D; (h) SR; (i) NCSR; (j) FSR.

DownLoad: Full-Size Img PowerPoint

Figure  9.  Denoising performance comparison on the Boat image with moderate noise corruption ( $\sigma$ = 20). (a) Original image; denoised images by (b) SAPCA-BM3D (PSNR = 31.02 dB, SSIM = 0.82); (c) SR (PSNR = 30.42 dB, SSIM = 0.80); (d) NCSR (PSNR = 30.74 dB, SSIM = 0.81); (e) FSR (PSNR = 32.53 dB, SSIM = 0.86).

DownLoad: Full-Size Img PowerPoint

Figure  10.  Denoising performance comparison on the Barbara image with moderate noise corruption ( $\sigma$ = 20). (a) Original image; denoised images by (b) SAPCA-BM3D (PSNR = 31.97 dB, SSIM = 0.90); (c) SR (PSNR = 30.92 dB, SSIM = 0.88); (d) NCSR (PSNR = 31.72 dB, SSIM = 0.90); (e) FSR (PSNR = 32.56 dB, SSIM = 0.92).

DownLoad: Full-Size Img PowerPoint

Thus, the FSR model can both preserve the sharpness of edges and suppress undesirable artifacts. Based on the above discussion in this sub-section, we can conclude that the FSR model improves the denoising performance and robustness in terms of the PSNR and SSIM.

B Comparison of Computational Efficiency

In this section, we discussed the computational cost of our FSR model in comparison to the SAPCA-BM3D algorithm and the sparse representation-based models (e.g., SR, NCSR). To make a fair comparison, the FSR model and the sparse representation-based models used the same stopping scalar controlling the convergence of the iterative. All the experiments were implemented on a personal computer (Intel i7-4790 CPU, 3.60 GHz, 16 GB RAM) with MATLAB 8.3 on 64-bit Windows 8. The experiments were repeated 10 times, and the results were reported with the average running time values for different noise levels $\sigma$ = 5, 10, 20, 35, 50.

The computational cost of the proposed FSR model with comparison to other competing methods is reported in Table Ⅲ. We can see that the SAPCA-BM3D algorithm and the NCSR model are time-consuming. For the SAPCA-BM3D algorithm, there is little difference in running time among the five noise levels. Note that the running time is directly proportional to the size of the image: 331.55 s for the House image of size 256 $\times$ 256 and 1329.63 s for the Lena image of size 512 $\times$ 512 at $\sigma$ = 5. And the NCSR model requires more time for image denoising when the noise level increases. By contrast, the running time for both FSR and SR model declines with the increasing of noise, because the seriously corruption of noisy images at heavy noise levels $\sigma$ = 35, 50, these models can only learn few image texture details during the dictionary learning stage and converge quickly. The FSR model is more than 100 times faster than the SAPCA-BM3D and is over 30 times faster than other sparse representation-based models. Consequently, the running time of the FSR model is significantly reduced, and the FSR model exhibits the best computational efficiency among the four approaches.

Table  Ⅲ.  TIME CONSUMPTION RESULTS (IN SECONDS) FOR VARIOUS NOISY LEVELS OBTAINED BY THE SAPCA-BM3D, SR, NCSR AND FSR MODEL. THE LAST COLUMN PRESENTS THE AVERAGE RUNNING TIME RESULTS OVER ALL TEST IMAGES. THE BEST RESULT IS HIGHLIGHTED.

Method	$\sigma$	Running time ( $s$ )
		Lena (5122)	Barbara (5122)	Boat (5122)	House (2562)	Pepper (5122)	Average
SAPCA-BM3D	5	1329.63	1403.72	1375.73	331.55	1355.65	966.88
	10	1331.62	1352.91	1387.30	332.89	1354.90	961.60
	20	1334.86	1348.03	1377.07	333.39	1353.00	961.06
	35	1339.29	1355.45	1384.13	338.13	1357.21	968.20
	50	1318.81	1336.48	1386.97	341.64	1330.25	960.69
SR	5	48.20	99.43	84.30	51.97	52.94	67.37
	10	16.82	29.42	25.68	17.14	16.05	21.02
	20	6.76	9.62	9.54	6.21	6.38	7.70
	35	3.50	4.29	4.60	2.88	3.24	3.70
	50	2.78	2.54	2.79	1.77	2.08	2.39
NCSR	5	677.65	687.39	699.47	154.73	674.60	578.77
	10	650.09	676.66	645.27	150.54	653.84	555.28
	20	859.17	804.57	755.78	189.36	797.76	681.33
	35	1859.78	1643.56	1598.92	424.71	1728.76	1451.15
	50	1891.67	1708.95	1757.39	431.92	1769.44	1511.87
FSR	5	$\boldsymbol{12.88}$	$\boldsymbol{23.88}$	$\boldsymbol{23.17}$	$\boldsymbol{10.41}$	$\boldsymbol{13.73}$	$\boldsymbol{16.81}$
	10	$\boldsymbol{4.34}$	$\boldsymbol{6.35}$	$\boldsymbol{6.74}$	$\boldsymbol{3.72}$	$\boldsymbol{4.27}$	$\boldsymbol{5.08}$
	20	$\boldsymbol{2.66}$	$\boldsymbol{3.17}$	$\boldsymbol{2.59}$	$\boldsymbol{1.81}$	$\boldsymbol{2.48}$	$\boldsymbol{2.54}$
	35	$\boldsymbol{2.28}$	$\boldsymbol{2.42}$	$\boldsymbol{2.41}$	$\boldsymbol{1.65}$	$\boldsymbol{2.01}$	$\boldsymbol{2.15}$
	50	$\boldsymbol{2.14}$	$\boldsymbol{2.15}$	$\boldsymbol{2.20}$	$\boldsymbol{1.26}$	$\boldsymbol{1.54}$	$\boldsymbol{1.86}$

 | Show Table

DownLoad: CSV

Ⅴ. CONCLUSION

To obtain more accurate sparse coefficients and optimal dictionary, we presented a new model for image denoising called the fractional-order sparse representation (FSR) model. The proposed FSR model has been evaluated on the basis of five typical images with various noise levels. A series experimental results show that, in most cases, the FSR model significantly outperforms the SAPCA-BM3D and other two sparse representation-based models (e.g., SR, NCSR). Furthermore, the FSR model performs with remarkable computational efficiency. Therefore, we can conclude that the proposed FSR model achieves state-of-the-art performance in terms of both denoising effectiveness and computational efficiency. However, the fractional-order parameters are learned from external images database. It remains unclear how to set fractional-order parameters automatically, which is out of scope of this paper and will lead to our future work.