PDF  PubReader

Zhang* , Jiang* , Zheng** , Wang*** , and Xie*: A New Operator Extracting Image Patch Based on EPLL

Jianwei Zhang* , Tao Jiang* , Yuhui Zheng** , Jin Wang*** and Jiacen Xie*

A New Operator Extracting Image Patch Based on EPLL

Abstract: Multivariate finite mixture model is becoming more and more popular in image processing. Performing image denoising from image patches to the whole image has been widely studied and applied. However, there remains a problem that the structure information is always ignored when transforming the patch into the vector form. In this paper, we study the operator which extracts patches from image and then transforms them to the vector form. Then, we find that some pixels which should be continuous in the image patches are discontinuous in the vector. Due to the poor anti-noise and the loss of structure information, we propose a new operator which may keep more information when extracting image patches. We compare the new operator with the old one by performing image denoising in Expected Patch Log Likelihood (EPLL) method, and we obtain better results in both visual effect and the value of PSNR.

Keywords: Expected Patch Log Likelihood , Image Denoising , Patch Priors , Structure Information

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

[TeX:] $$\text{max} _ { x } P ( x | y ) = \text{max} _ { x } P ( y | x ) P ( x )$$

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

[TeX:] $$E P L L ( x ) = \ln p ( x ) = \sum _ { i } p \left( P _ { i } x \right)$$

where Pi is an operator which extracts the i’th patch from the image, and p(Pix 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

[TeX:] $$\min _ { x } \frac { \lambda } { 2 } \| H x - y \| _ { 2 } ^ { 2 } - \sum _ { i } \ln p \left( P _ { i } x \right)$$

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

[TeX:] $$f \left( x , \left\{ z _ { i } \right\} | y \right) = \frac { \lambda } { 2 } \| H x - y \| _ { 2 } ^ { 2 } + \sum _ { i } \left( \frac { \beta } { 2 } \left\| P _ { i } x - z _ { i } \right\| _ { 2 } ^ { 2 } - \ln p \left( z _ { i } \right) \right)$$

As β tends to infinity, we obtain that {zi} is equal to Pix 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 zi, 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:

[TeX:] $$\frac { \beta } { 2 } \left\| P _ { i } x - z _ { i } \right\| _ { 2 } ^ { 2 } - \ln p \left( z _ { i } \right)$$

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

[TeX:] $$p \left( z _ { i } \right) = \sum _ { k = 1 } ^ { K } \pi _ { k } N \left( z _ { i } | \mu _ { k } , \Sigma _ { k } \right)$$

To minimize Eq. (5), we choose the component which owns the highest conditional mixing weights kmax = maxkp(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 kmax-th component:

[TeX:] $$z _ { i } = \left( \Sigma _ { k _ { m a x } } + \frac { 1 } { \beta } I \right) ^ { - 1 } \left( \Sigma _ { k _ { m a x } } y + \frac { 1 } { \beta } I \mu _ { k m a x } \right)$$

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

[TeX:] $$x = \left( \lambda H ^ { T } H + \beta \sum _ { j } P _ { j } ^ { T } P _ { j } \right) ^ { - 1 } \left( \lambda H ^ { T } y + \beta \sum _ { j } P _ { j } ^ { T } z _ { j } \right)$$

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]:

[TeX:] $$E P L L ( x ) = \sum _ { i } \ln p \left( P _ { i } x \right)$$

where Pi 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 (m2 * 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 Pi is considered to make sure that the patch vector can describe the patch continuously.

Matrix A is extracted from an image as (l1,l2,...,lp),li is column vector and p is the patch size. Original Pi turns A to a column vector A1 as (l1,l2,...,lp),. Clearly, in vector A1, 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 A2 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 li. 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

4.1 Learning with a Gaussian Mixture Prior

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.

4.2 Image Denoising

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.

Table 1.

Average PSNR (dB) for the task of denoising on 8 images
EPLL New operator based on EPLL
σ = 30 30.14 30.31
σ = 40 29.37 29.52
σ = 50 28.38 28.51

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.


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


Jianwei Zhang

He received the Ph.D. degree in the Nanjing University of Science and Technology, China in 2006. Now he is a Professor at the College of Math and Statistics, Nanjing University of Information Science and Technology. His research interests cover pattern recognition, artificial intelligence, and remote sensing information processing.


Tao Jiang

He received the B.S. degree in information and computation science from Nanjing University of Information Science and Technology (NUIST), China in 2011. Now, he is a postgraduate in the College of Math and Statistics, NUIST. His research interests cover image processing and pattern recognition.


Yuhui Zheng

He received the Ph.D. degree in the Nanjing University of Science and Technology, China in 2009. Now, he is an associate professor in the School of Computer and Software, Nanjing University of Information Science and technology. His research interests cover image processing, pattern recognition, and remote sensing information system.


Jin Wang

He received the B.S. and M.S. degree from Nanjing University of Posts and Telecommunications, China in 2002 and 2005, respectively. He received Ph.D. degree from Kyung Hee University Korea in 2010. Now, he is a professor in the School of Computer & Communication Engineering, Changsha University of Science & Technology. His research interests mainly include routing algorithm design, performance evaluation and optimization for wireless ad hoc and sensor networks. He is a Member of IEEE and ACM.


Jiacen Xie

She received the B.S. degree in information and computation science from Nanjing University of Information Science and Technology (NUIST), China in 2011. Now, she is a postgraduate in the College of Math and Statistics, NUIST. Her research interests cover image processing and pattern recognition.


  • 1 A. Beck, M. Teboulle, "Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems," IEEE Transactions on Image Processing, 2009, vol. 18, no. 11, pp. 2419-2434. doi:[[[10.1109/TIP.2009.2028250]]]
  • 2 W. Zuo, D. Meng, L. Zhang, X. Feng, D. Zhang, "A generalized iterated shrinkage algorithm for non-convex sparse coding," in Proceedings of IEEE International Conference on Computer Vision, Sydney, Australia, 2013;pp. 217-224. doi:[[[10.1109/ICCV.2013.34]]]
  • 3 M. Jung, X. Bresson, T. Chan, L. Vese, "Nonlocal Mumford-Shah regularizers for color image restoration," IEEE Transactions on Image Processing, 2011, vol. 20, no. 6, pp. 1583-1598. doi:[[[10.1109/TIP.2010.2092433]]]
  • 4 Y. Zheng, K. Ma, Q. Yu, J. Zhang, J. Wang, "Regularization parameter selection for total variation model based on local spectral response," Journal of Information Processing Systems, 2017, vol. 13, no. 5, pp. 1168-1182. doi:[[[10.3745/JIPS.02.0072]]]
  • 5 Y. Zheng, B. Jeon, J. Zhang, Y. Chen, "Adaptively determining regularization parameters in non-local total variation regularization for image denoising," Electronics Letters, 2015, vol. 5, no. 2, pp. 144-145. doi:[[[10.1049/el.2014.3494]]]
  • 6 Z. Yang, M. Jacob, "Nonlocal regularization of inverse problems: a unified variational framework," IEEE Transactions on Image Processing, 2013, vol. 22, no. 8, pp. 3192-3203. doi:[[[10.1109/TIP.2012.2216278]]]
  • 7 R. Yan, L. Shao, Y. Liu, "Nonlocal hierarchical dictionary learning using wavelets for image denoising," IEEE Transactions on Image Processing, 2013, vol. 22, no. 12, pp. 4689-4698. doi:[[[10.1109/TIP.2013.2277813]]]
  • 8 L. Sun, B. Jeon, Y. Zheng, Z. Wu, "Hyperspectral image restoration using low-rank representation on spectral difference image," IEEE Geoscience and Remote Sensing Letters, 2017, vol. 14, no. 7, pp. 1151-1155. doi:[[[10.1109/LGRS.2017.2701805]]]
  • 9 J. Han, R. Quan, D. Zhang, F. Nie, "Robust object co-segmentation using background prior," IEEE Transactions on Image Processing, 2018, vol. 27, no. 4, pp. 1639-1651. doi:[[[10.1109/TIP.2017.2781424]]]
  • 10 F. Xiao, W. Liu, Z. Li, L. Chen, R. Wang, "Noise-tolerant wireless sensor networks localization via multinorms regularized matrix Completion," IEEE Transactions on Vehicular Technology, 2018, vol. 67, no. 3, pp. 2409-2419. doi:[[[10.1109/TVT.2017.2771805]]]
  • 11 J. Hughes, M. Rockmore, Y. Wang, "Bayesian learning of sparse multiscale image representation," IEEE Transactions on Image Processing, 2013, vol. 22, no. 12, pp. 4972-4983. doi:[[[10.1109/TIP.2013.2280188]]]
  • 12 S. Roth, M. J. Black., "Fields of experts," S. Roth and M. J. Black. International Journal of Computer Visionarticle no. 205, 2009, vol. 82, no. article 205. doi:[[[10.1007/s11263-008-0197-6]]]
  • 13 S. Roth, M. J. Black, "Fields of experts: a framework for learning image priors," in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Diego, CA, 2005;pp. 860-867. doi:[[[10.1109/CVPR.2005.160]]]
  • 14 D. Zoran, Y. Weiss, "From learning models of natural image patches to whole image restoration," in Proceedings of IEEE International Conference on Computer Vision, Barcelona, Spain, 2011;pp. 479-486. doi:[[[10.1109/ICCV.2011.6126278]]]
  • 15 D. Geman, C. Yang, "Nonlinear image recovery with half-quadratic regularization," IEEE Transactions on Image Processing, 1995, vol. 4, no. 7, pp. 932-946. doi:[[[10.1109/83.392335]]]
  • 16 G. Yu, G. Sapiro, S. Mallat, "Solving inverse problems with piecewise linear estimators: from Gaussian mixture models to structured sparsity," IEEE Transactions on Image Processing, 2012, vol. 21, no. 5, pp. 2481-2499. doi:[[[10.1109/TIP.2011.2176743]]]
  • 17 C. Aguerrebere, A. Almansa, Y. Gousseau, J. Delon, "Single shot high dynamic range imaging using piecewise linear estimators," in Proceedings of IEEE International Conference on Computational Photography, Santa Clara, CA, 2014;pp. 1-10. doi:[[[10.1109/ICCPHOT.2014.6831807]]]
  • 18 Y. Q. Wang, J. M. Morel, "SURE guided Gaussian mixture image denoising," SIAM Journal of Imaging Sciences, 2013, vol. 6, no. 2, pp. 999-1034. doi:[[[10.1137/120901131]]]
  • 19 R. Zhang, C. A. Bouman, J. B. Thibault, K. D. Sauer, "Gaussian mixture Markov random field for image denoising and reconstruction," in Proceedings of IEEE Global Conference on Signal and Information Processing, Austin, TX, 2014;pp. 1089-1092. doi:[[[10.1109/GlobalSIP.2013.6737083]]]
  • 20 V. Papyan, M. Elad, "Multi-scale patch-based image restoration," IEEE Transactions on Image Processing, 2016, vol. 25, no. 1, pp. 249-261. doi:[[[10.1109/TIP.2015.2499698]]]
  • 21 Y. Zheng, X. Zhou, B. Jeon, J. Shen, H. Zhang, "Multi-scale patch prior learning for image denoising using Student’s-t mixture model," Journal of Internet Technology, 2017, vol. 18, no. 7, pp. 1553-1560. doi:[[[10.6138/JIT.2017.18.7.20161120]]]
  • 22 Y. Zheng, B. Jeon, L. Sun, J. Zhang, and H. Zhang, IEEE Transactions on Circuits and Systems for Video Technology, 2017., https://doi.org/10.1109/TCSVT.2017.2724940
  • 23 B. Ophir, M. Lustig, M. Elad, "Multi-scale dictionary learning using wavelets," IEEE Journal of Selected Topics in Signal Processing, 2011, vol. 5, no. 5, pp. 1014-1024. doi:[[[10.1109/JSTSP.2011.2155032]]]
  • 24 X. Lu, Y. Yuan, P. Yan, "Alternatively constrained dictionary learning for image superresolution," IEEE Transactions on Cybernetics, 2014, vol. 44, no. 3, pp. 366-377. doi:[[[10.1109/TCYB.2013.2256347]]]
  • 25 F. Xiao, Z. Wang, N. Ye, R. Wang, X. Li, "One more tag enables fine-grained RFID localization and tracking," IEEE/ACM Transactions on Networking, 2018, vol. 26, no. 1, pp. 161-174. doi:[[[10.1109/TNET.2017.2766526]]]
  • 26 J. Han, D. Zhang, G. Cheng, N. Liu, D. Xu, "Advanced deep-learning techniques for salient and category-specific object detection: a survey," IEEE Signal Processing Magazine, 2018, vol. 35, no. 1, pp. 84-100. doi:[[[10.1109/MSP.2017.2749125]]]
  • 27 M. Golipour, H. Ghassemian, F. Mirzapour, "Integrating hierarchical segmentation maps with MRF prior for classification of hyperspectral images in a Bayesian framework," IEEE Transactions on Geoscience and Remote Sensing, 2016, vol. 54, no. 2, pp. 805-816. doi:[[[10.1109/TGRS.2015.2466657]]]