nips nips2009 nips2009-93 nips2009-93-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dilip Krishnan, Rob Fergus
Abstract: The heavy-tailed distribution of gradients in natural scenes have proven effective priors for a range of problems such as denoising, deblurring and super-resolution. α These distributions are well modeled by a hyper-Laplacian p(x) ∝ e−k|x| , typically with 0.5 ≤ α ≤ 0.8. However, the use of sparse distributions makes the problem non-convex and impractically slow to solve for multi-megapixel images. In this paper we describe a deconvolution approach that is several orders of magnitude faster than existing techniques that use hyper-Laplacian priors. We adopt an alternating minimization scheme where one of the two phases is a non-convex problem that is separable over pixels. This per-pixel sub-problem may be solved with a lookup table (LUT). Alternatively, for two specific values of α, 1/2 and 2/3 an analytic solution can be found, by finding the roots of a cubic and quartic polynomial, respectively. Our approach (using either LUTs or analytic formulae) is able to deconvolve a 1 megapixel image in less than ∼3 seconds, achieving comparable quality to existing methods such as iteratively reweighted least squares (IRLS) that take ∼20 minutes. Furthermore, our method is quite general and can easily be extended to related image processing problems, beyond the deconvolution application demonstrated. 1
[1] R. Chartrand. Fast algorithms for nonconvex compressive sensing: Mri reconstruction from very few data. In IEEE International Symposium on Biomedical Imaging (ISBI), 2009.
[2] R. Chartrand and V. Staneva. Restricted isometry properties and nonconvex compressive sensing. Inverse Problems, 24:1–14, 2008.
[3] R. Fergus, B. Singh, A. Hertzmann, S. T. Roweis, and W. Freeman. Removing camera shake from a single photograph. ACM TOG (Proc. SIGGRAPH), 25:787–794, 2006.
[4] D. Field. What is the goal of sensory coding? Neural Computation, 6:559–601, 1994.
[5] D. Geman and G. Reynolds. Constrained restoration and recovery of discontinuities. PAMI, 14(3):367–383, 1992.
[6] D. Geman and C. Yang. Nonlinear image recovery with half-quadratic regularization. PAMI, 4:932–946, 1995.
[7] N. Joshi, L. Zitnick, R. Szeliski, and D. Kriegman. Image deblurring and denoising using color priors. In CVPR, 2009.
[8] D. Krishnan and R. Fergus. Fast image deconvolution using hyper-laplacian priors, supplementary material. NYU Tech. Rep. 2009, 2009.
[9] A. Levin. Blind motion deblurring using image statistics. In NIPS, 2006.
[10] A. Levin, R. Fergus, F. Durand, and W. Freeman. Image and depth from a conventional camera with a coded aperture. ACM TOG (Proc. SIGGRAPH), 26(3):70, 2007.
[11] A. Levin and Y. Weiss. User assisted separation of reflections from a single image using a sparsity prior. PAMI, 29(9):1647–1654, Sept 2007.
[12] A. Levin, Y. Weiss, F. Durand, and W. T. Freeman. Understanding and evaluating blind deconvolution algorithms. In CVPR, 2009.
[13] S. Osindero, M. Welling, and G. Hinton. Topographic product models applied to natural scene statistics. Neural Computation, 1995.
[14] J. Portilla, V. Strela, M. J. Wainwright, and E. P. Simoncelli. Image denoising using a scale mixture of Gaussians in the wavelet domain. IEEE TIP, 12(11):1338–1351, November 2003.
[15] W. Richardson. Bayesian-based iterative method of image restoration. 62:55–59, 1972.
[16] S. Roth and M. J. Black. Fields of Experts: A Framework for Learning Image Priors. In CVPR, volume 2, pages 860–867, 2005.
[17] L. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Physica D, 60:259–268, 1992.
[18] E. Simoncelli and E. H. Adelson. Noise removal via bayesian wavelet coring. In ICIP, pages 379–382, 1996.
[19] C. V. Stewart. Robust parameter estimation in computer vision. SIAM Reviews, 41(3):513–537, Sept. 1999.
[20] M. F. Tappen, B. C. Russell, and W. T. Freeman. Exploiting the sparse derivative prior for super-resolution and image demosaicing. In SCTV, 2003.
[21] M. Wainwright and S. Simoncelli. Scale mixtures of gaussians and teh statistics of natural images. In NIPS, pages 855–861, 1999.
[22] Y. Wang, J. Yang, W. Yin, and Y. Zhang. A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sciences, 1(3):248–272, 2008.
[23] E. W. Weisstein. Cubic formula. http://mathworld.wolfram.com/ CubicFormula.html.
[24] E. W. Weisstein. Quartic equation. http://mathworld.wolfram.com/ QuarticEquation.html.
[25] M. Welling, G. Hinton, and S. Osindero. Learning sparse topographic representations with products of student-t distributions. In NIPS, 2002.
[26] S. Wright, R. Nowak, and M. Figueredo. Sparse reconstruction by separable approximation. IEEE Trans. Signal Processing, page To appear, 2009. 9