A New Operator Extracting Image Patch Based on EPLL

1. Introduction

Image restoration is an inverse problem. The purpose is to use a priori knowledge of degenerate graph to restore the degraded image, so that the image can reflect the objective content more truly and effectively.

Assume an image is degraded by an additive white Gaussian noise N. Given the formula Y = X + N, we have to restore the image X by learning some prior knowledge about other general natural images. Because of the huge complexity of the whole image, the whole image prior is hard to learn. In recent years, so many image restoration methods have been modeled by dividing the whole image into a massive of overlapped patches with low dimensional, which are easier to study.

Regularization methods and Bayesian methods are powerful tools to solve image restoration problems, the former usually take advantages of image neighborhood properties, such as smoothness and continuity. Classical models include total variation (TV) algorithm [1,2] and Mumford-Shan model [3]. In TV model, the regular term is structured by minimizing the gradient. The balance between the regular term and the fidelity term is unstable, so an adaptive parameter selection method [4,5] is proposed. Then, Yang and Jacob [6] and Yan et al. [7] proposed the non-local regularization method, which considered nonlocal similarity through an image window and got a better result with a clearer edge. However, blurred phenomena often occur in image detail and texture, which are likely to result in the loss of important information. The reason is the smoothness constraint of local prior models, so Bayesian methods are becoming more and more popular.

Usually there is a likelihood among patches and it is easier to model, so patch priors are available. Popular Bayesian methods include the sparse model [8-11], which uses low-rank representation to build the regular term; Roth proposed an analysis model as fields of experts (FoE) [12,13], which effectively overcame the shortcomings of the previous Markov random field model due to its low order property by using the high-order neighborhood system. In the context of image denoising, it has been proved that denoising every patch separately and finally summarizing the results with a simple mean method are effective. Early on, Zoran and Weiss [14] proposed the Expected Patch Log Likelihood (EPLL) algorithm based on patch, which built a cost function based on the cumulative likelihood and solved by using an alternative optimization method called “Half Quadratic Splitting” [15]. Similar to above method, Yu et al. [16] and Aguerrebere et al. [17] proposed piecewise linear estimation (PLE), which used maximum a posteriori (MAP) probability framework and maximum expectation algorithm to realize image restoration. To improve the learning ability of the model on the edge and other directional image structures, Wang proposed Stein’s unbiased risk estimator (SURE) algorithm [18,19], which provided an indication of the accuracy of a given estimator. According to scale invariance, Panyan and Elad [20] proposed multi-scale Expected Patch Log Likelihood (MSEPLL) algorithm, which imposed the very same prior on different scale patches extracted from the target image. Afterwards, an image denoising method based on Student’s-t Mixture Model [21,22] is proposed, it has a better robustness due to its heavy tails. Apparently, finite mixture model relies on priors, and the key to priors is patch clustering. It is hard to implement matrix clustering because of the complex structure information. Usually image patches are transformed into vector form by an operator. So how to make the vector closer to the matrix is very important.

Considering that the adjacent pixels always have close relationships not only in the whole image but also in image patches. However, traditional operators [23-27] usually ignore the importance of continuous pixels when transforming the matrix into a vector. In this paper, we learn the rule of traditional operator and propose a new operator which can describe the image matrix more accurately. We compare the traditional operator with the proposed one in image denoising based on EPLL, and get better results in both visual effect and the value of peak signal-to-noise ratio (PSNR).

This paper is organized as follows: Section 2 reviews the EPLL algorithm. Section 3 introduces the proposed new operator. In Section 4, we present experimental results. Section 5 summarizes this paper.

2. Expected Patch Log Likelihood

In this section, we review EPLL [14] and present the improved operator rely on this method. Given a corrupted image y = Hx + n, where x is the clean image, H is the noninvertible linear operator and 􀝊 is the additive noise. To solve the inverse problem, we would like to restore x by solving the MAP problem

where P(x) is a global prior. For a whole image, the statistical distribution is too complicated to study. The EPLL [14] gives the way to denoise the image from patches to the whole image. In prior learning, we usually assume that patches obey the Gaussian mixture distribution. By using expectation maximization (EM) algorithm, we get the parameters of the prior distribution

where P_i is an operator which extracts the i’th patch from the image, and p(P_ix is the likelihood of the i’th patch under the prior. Considering the minimum mean square error, we combine it with the EPLL.

Then, we obtain

where λ is a regular parameter. To solve the problem, we can use Half Quadratic Splitting [2] by introducing a set of auxiliary variables {z_i} that should be equal to P_ix, yielding the following cost function:

As β tends to infinity, we obtain that {z_i} is equal to P_ix and the solutions of Eq. (4), and Eq. (3) are similar. It has been practiced by Zoran and Weiss [14] that Eq. (4) can be optimized in an iterative manner. Assuming x is fixed, we minimize Eq. (4) respect to z_i, and it is equivalent to solve a MAP problem of estimating the most similar patch under the prior. This is equal to minimizing the following equation:

It is necessary to mention that the local prior used in EPLL [14] is a GMM model defined as

To minimize Eq. (5), we choose the component which owns the highest conditional mixing weights k_max = max_kp(k|y) under the given noisy patch y. Then Eq. (5) is equal to the least squares problem and has a Wiener filter solution for the k_max-th component:

The next step is solving x with the given {z_i}. It is easy to take the derivative of Eq. (4) respect to vector x. We obtain the solution

Repeat the two steps for several iterations and we need to set a value of β at each iteration. Then increase β so that we can improve the cost function. Usually there are two approaches to choose the value of β, first one is to optimize the value through a set of training images. The other one we used here is to try to estimate β from the current image by using the noise estimation method in [9].

3. Proposed Operator Extracting Image Patches

It is known that the key of EPLL is patch learning and patch denoising, but the structure information on image patch is more important. In this section, a new operator extracting patches from the image would be presented. We review the framework of EPLL [14]:

where P_i is an operator which extracts the i’th patch from the image. The rule of the operator usually turns the patch matrix (m * m) to a column vector (m² * 1). In the process of the operation, a column vector of the patch matrix is always followed by the next column vector. However, continuity of spatial structure is very important for images. The above method would lead to several discontinuity points. To avoid this problem, a new rule of P_i is considered to make sure that the patch vector can describe the patch continuously.

Matrix A is extracted from an image as (l₁,l₂,...,l_p),l_i is column vector and p is the patch size. Original P_i turns A to a column vector A¹ as (l₁,l₂,...,l_p),. Clearly, in vector A¹, there always be p − 1 pairs of points are close to each other, but they have no connection in matrix A. In EPLL algorithm [27], the connection between adjoining elements is pressed when calculating the covariance matrix. So there may be some big single noise accidentally especially when dealing with heavy noise. To improve this, we propose the new operator turning A to A² as [TeX:] $$\left( l _ { 1 } \overline { l } _ { 2 } , \ldots l _ { p - 1 } \overline { l } _ { p } \right) , \text { where } \overline { l _ { i } }$$ represents the reverse order of column vector l_i. It can make sure that all elements are continuous both in vector form and in matrix form.

Fig. 1.

An example of image patch vectorization. (a) The original image. (b) The set of image patch under the original operator. (c) One of the patch vector extracted by the original operator. (d) The set of image patch under the proposed operator. (e) One of the patch vector extracted by the proposed operator.

From Fig. 1, we can see that the old operator leads to a lot of discontinuous changes among adjacent pixels, especially, on the basis of Fig. 1(c). However, the proposed operator extracts image patch more continuously. Pixels change continuously in Fig. 1(e).

4. Experimental Results

We train the natural images in a similar way mentioned in [14]. By assuming that classic image priors can be seen as a special case of Gaussian Mixture Model (GMM) [7], we can learn the means and covariance matrices. We extract the image patches by using the proposed operator. Then we get thousands of patches in vector form, which are easy to learn by using EM algorithm.

To compare the effect of the new operator with the original one, the library of images, the parameters and the EM code are same as in EPLL. Because we use the new operator to extract image patches, we obtain a different GMM prior.

Under the known prior, we perform denoising model using the new operator. We use additive white Gaussian noise to corrupt the image, and then we extract the i’th image patch and transform it into column vector form with the new operator. Perform step 1 in Section 2 and calculate the Function 7, then put the solution into Function 8. We repeat five times with an increasing value of β. Considering that patches extracted from images are overlapping, we calculate the mean of each pixel appearing in overlapping patches. In addition, we set λ to be related to the standard deviation of noise [TeX:] $$\left( \approx \frac { 1 } { \sigma ^ { 2 } } \right)$$, and set β = [1 4 8 16 32] as EPLL [14]. set

Fig. 2.

Denoising result for Lena corrupted with a noise standard deviation σ = 30. (a) EPLL PSNR = 30.66. (b) Proposed operator based on EPLL PSNR = 30.85.

We perform denoising on lots of images with different noise standard deviations. As the original operator may lead to some accidental errors, the proposed operator may avoid them. Apparently, in Fig. 2, we can see that the proposed method reduces a lot of white noise especially near to the corner and the edge. In Figs. 3 and 4, we can also find that the proposed operator in this paper has good results in denoising. What’s more, the operator can be used whenever extracting image patches is indeed. The rule of the proposed operator differs from the original one, but it doesn’t impact the main framework of the algorithm. Instead, to a certain extent, the new operator improves both the patch priors and the denoising model in keeping the structure information of image patches.

Fig. 3.

Denoising result for the image Cameraman corrupted with a noise standard deviation σ = 50. (a) Original image. (b) EPLL PSNR = 25.96. (c) Proposed operator based on EPLL PSNR = 26.16. (d) Residual plot of EPLL. (e) Residual plot of proposed operator based on EPLL.

Fig. 4.

Denoising result for House corrupted with a noise standard deviation σ = 40. (a) Original image. (b) EPLL PSNR = 29.93. (c) Proposed operator based on EPLL PSNR = 30.05. (d) Residual plot of EPLL. (e) Residual plot of proposed operator based on EPLL.

Not only from the visual effect, but also from the value of PSNR we can see the improvement of the proposed operator. Table 1 shows the PSNR for the task of denoising on 8 images, and we can see that the proposed operator based on EPLL is a little better than the original EPLL on average.

Comparing the iterative process, it can be seen in Fig. 5 that in each iteration the proposed operator performs better than the original one. It can be proved that the proposed operator always has a better effect in clustering task, even when solving the MAP problem.

Fig. 5.

PSNR for denoising task of image Lena in each iteration with the noise standard deviation σ = 40.

5. Conclusion

Image priors are of utmost importance in image denoising task. An example of such priors is the GMM, and it has been practiced by a lot of multivariate finite mixture models. For the EPLL algorithm, it models a whole image by characterizing its overlapped patches and forcing every patch extracted from the image to be like to a given prior. In this paper, we propose a new operator which can keep the continuity of pixel’s gradient, so that more structure information of image patches is retained. We show the difference between the new operator and the original one via an example of image patches. Many breakpoints are missing and we get a more continuous vector. We compare the new operator with the original one on the task of image denoising. Our method shows a clear improvement in both visual effect and numerical value. Besides, the new operator we proposed in this paper can be applied to the most of scenarios in translating matrix into vector form.

As we all know, there is an essential difference between a matrix and a vector. How to learn priors by the matrix form is the key. Although our method in this paper has a few limitations, we keep learning more about matrix properties and try to present a method on matrix clustering which may keep more structure information about patches in the future.

Acknowledgement

This paper is partly supported by the National Natural Science Foundation of China (Grant No. 61672293).