Non-local regularization of inverse problems

Gabriel Peyré; Sébastien Bougleux; Laurent Cohen

doi:10.3934/ipi.2011.5.511

Article Contents

2011, Volume 5, Issue 2: 511-530. Doi: 10.3934/ipi.2011.5.511

This issue Previous Article Recovering conductivity at the boundary in three-dimensional electrical impedance tomography Next Article

Non-local regularization of inverse problems

1.
Ceremade, Université Paris-Dauphine, 75775 Paris Cedex 16
2.
GREYC, Université de Caen, 14050 Caen Cedex

Received: September 30, 2009

Revised: August 31, 2010

Published: April 2011

Abstract Related Papers Cited by

Abstract

This article proposes a new framework to regularize imaging linear inverse problems using an adaptive non-local energy. A non-local graph is optimized to match the structures of the image to recover. This allows a better reconstruction of geometric edges and textures present in natural images. A fast algorithm computes iteratively both the solution of the regularization process and the non-local graph adapted to this solution. The graph adaptation is efficient to solve inverse problems with randomized measurements such as inpainting random pixels or compressive sensing recovery. Our non-local regularization gives state-of-the-art results for this class of inverse problems. On more challenging problems such as image super-resolution, our method gives results comparable to sparse regularization in a translation invariant wavelet frame.

Keywords:

Mathematics Subject Classification: Primary: 68U10, 94A08; Secondary: 49N45.

Citation:

Related Papers

Cited by

References

[1]	A. Adams, N. Gelfand, J. Dolson and M. Levoy, Gaussian KD-trees for fast high-dimensional filtering, ACM Transactions on Graphics, 28, 2009.
[2]	J.-F. Aujol, Some first-order algorithms for total variation based image restoration, J. Math. Imaging Vis., 34 (2009), 307-327.doi: 10.1007/s10851-009-0149-y.
[3]	J.-F. Aujol, S. Ladjal and S. Masnou, Exemplar-based inpainting from a variational point of view, SIAM Journal on Mathematical Analysis, 42 (2010), 1246-1285.doi: 10.1137/080743883.
[4]	M. Avriel, "Nonlinear Programming: Analysis and Methods," Dover Publishing, 2003.
[5]	C. Ballester, M. Bertalmìo, V. Caselles, G. Sapiro and J. Verdera, Filling-in by joint interpolation of vector fields and gray levels, IEEE Trans. Image Processing, 10 (2001), 1200-1211.doi: 10.1109/83.935036.
[6]	J. Bect, L. Blanc Féraud, G. Aubert and A. Chambolle, A $\l_1$-unified variational framework for image restoration, In "Proc. of ECCV04," pages Vol IV, 1-13. Springer-Verlag, 2004.
[7]	M. Bertalmìo, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, In "Siggraph 2000," pages 417-424, 2000.
[8]	A. Buades, B. Coll and J. M. Morel, A review of image denoising algorithms, with a new one, Multiscale Modeling and Simulation, 4 (2005), 490-530.doi: 10.1137/040616024.
[9]	A. Buades, B. Coll and J-M. Morel, "Image Enhancement By Non-local Reverse Heat Equation," Preprint CMLA 2006-22, 2006.
[10]	A. Buades, B. Coll, J-M. Morel and C. Sbert, Self similarity driven demosaicking, IEEE Trans. Image Proc., 18 (2009), 1192-1202.doi: 10.1109/TIP.2009.2017171.
[11]	E. Candès and T. Tao, Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, 52 (2006), 5406-5425.doi: 10.1109/TIT.2006.885507.
[12]	A. Chambolle, An algorithm for total variation minimization and applications, Journal of Mathematical Imaging and Vision, 20 (2004), 89-97.
[13]	T. Chan and J. Shen, Mathematical models for local nontexture inpaintings, SIAM J. Appl. Math, 62 (2002), 1019-1043.doi: 10.1137/S0036139900368844.
[14]	P. G. Ciarlet, "Introduction to Numerical Linear Algebra and Optimisation," Cambridge University Press, Cambridge, 1989.
[15]	R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner and S. W. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, Proc. of the Nat. Ac. of Science, 102 (2005), 7426-7431.doi: 10.1073/pnas.0500334102.
[16]	P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Modeling & Simulation, 4 (2005), 1168-1200.doi: 10.1137/050626090.
[17]	A. Criminisi, P. Pérez and K. Toyama, Region filling and object removal by exemplar-based image inpainting, IEEE Transactions on Image Processing, 13 (2004), 1200-1212.doi: 10.1109/TIP.2004.833105.
[18]	D. Datsenko and M. Elad, Example-based single image super-resolution: A global map approach with outlier rejection, Journal of Mult. System and Sig. Proc., 18 (2007), 103-121.doi: 10.1007/s11045-007-0018-z.
[19]	I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), 1413-1541.doi: 10.1002/cpa.20042.
[20]	D. Donoho, Compressed sensing, IEEE Transactions on Information Theory, 52 (2006), 1289-1306.doi: 10.1109/TIT.2006.871582.
[21]	D. Donoho and I. Johnstone, Ideal spatial adaptation via wavelet shrinkage, Biometrika, 81 (1994), 425-455.doi: 10.1093/biomet/81.3.425.
[22]	D. Donoho, Y. Tsaig, I. Drori and J-L. Starck, Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit, Preprint, 2006.
[23]	M. Ebrahimi and E. R. Vrscay, Solving the inverse problem of image zooming using 'self examples', In "ICIAR07," pages 117-130, 2007.
[24]	A. A. Efros and T. K. Leung, Texture synthesis by non-parametric sampling, In "Proc. of ICCV '99," page 1033. IEEE Computer Society, 1999.
[25]	M. Elad and M. Aharon, Image denoising via sparse and redundant representations over learned dictionaries, IEEE Trans. on Image Processing, 15 (2006), 3736-3745.doi: 10.1109/TIP.2006.881969.
[26]	M. Elad, J.-L Starck, D. Donoho and P. Querre, Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Journal on Applied and Computational Harmonic Analysis, 19 (2005), 340-358.doi: 10.1016/j.acha.2005.03.005.
[27]	A. Elmoataz, O. Lezoray and S. Bougleux, Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing, IEEE Tr. on Image Processing, 17 (2008), 1047-1060.doi: 10.1109/TIP.2008.924284.
[28]	G. Facciolo, P. Arias, V. Caselles and G. Sapiro, "Exemplar-based Interpolation of Sparsely Sampled Images," IMA Preprint Series # 2264, 2009.
[29]	M. J. Fadili, J.-L. Starck and F. Murtagh, Inpainting and zooming using sparse representations, The Computer Journal, 52 (2009), 64-79.doi: 10.1093/comjnl/bxm055.
[30]	S. Farsiu, D. Robinson, M. Elad and P. Milanfar, Advances and challenges in super-resolution, Int. Journal of Imaging Sys. and Tech., 14 (2004), 47-57.doi: 10.1002/ima.20007.
[31]	W. T. Freeman, T. R. Jones and E. C. Pasztor, Example-based super-resolution, IEEE Computer Graphics and Applications, 22 (2002), 56-65.doi: 10.1109/38.988747.
[32]	G. Gilboa, J. Darbon, S. Osher and T. F. Chan, "Nonlocal Convex Functionals for Image Regularization," UCLA CAM Report 06-57, 2006.
[33]	G. Gilboa and S. Osher, Nonlocal linear image regularization and supervised segmentation, SIAM Multiscale Modeling and Simulation, 6 (2007), 595-630.doi: 10.1137/060669358.
[34]	G. Gilboa and S. Osher, Nonlocal operators with applications to image processing, SIAM Multiscale Modeling & Simulation, 7 (2008), 1005-1028.
[35]	S. Kindermann, S. Osher and P. W. Jones, Deblurring and denoising of images by nonlocal functionals, SIAM Mult. Model. and Simul., 4 (2005), 1091-1115.doi: 10.1137/050622249.
[36]	M. Mahmoudi and G. Sapiro, Fast image and video denoising via nonlocal means of similar neighborhoods, IEEE Signal Processing Letters, 12 (2005), 839-842.doi: 10.1109/LSP.2005.859509.
[37]	J. Mairal, M. Elad and G. Sapiro, Sparse representation for color image restoration, IEEE Trans. Image Proc., 17 (2008), 53-69.doi: 10.1109/TIP.2007.911828.
[38]	F. Malgouyres and F. Guichard, Edge direction preserving image zooming: A mathematical and numerical analysis, SIAM Journal on Numer. An., 39 (2001), 1-37.
[39]	S. Mallat, "A Wavelet Tour of Signal Processing," 3^rd edition, Academic Press, San Diego, 2008.
[40]	S. Masnou, Disocclusion: A variational approach using level lines, IEEE Trans. Image Processing, 11 (2002), 68-76.doi: 10.1109/83.982815.
[41]	M. Mignotte, A non-local regularization strategy for image deconvolution, Pattern Recognition Letters, 29 (2008), 2206-2212.doi: 10.1016/j.patrec.2008.08.004.
[42]	Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program. Ser. A, 103 (2005), 127-152.doi: 10.1007/s10107-004-0552-5.
[43]	B. A. Olshausen and D. J. Field, Emergence of simple-cell receptive-field properties by learning a sparse code for natural images, Nature, 381 (1996), 607-609.doi: 10.1038/381607a0.
[44]	S. C. Park, M. K. Park and M. G. Kang, Super-resolution image reconstruction: A technical overview, IEEE Signal Processing Magazine, 20 (2003), 21-36.doi: 10.1109/MSP.2003.1203207.
[45]	G. Peyré, Image processing with non-local spectral bases, SIAM Multiscale Modeling and Simulation, 7 (2008), 703-730.doi: 10.1137/07068881X.
[46]	G. Peyré, Sparse modeling of textures, J. Math. Imaging Vis., 34 (2009), 17-31.doi: 10.1007/s10851-008-0120-3.
[47]	G. Peyré, S. Bougleux and L. D. Cohen, Non-local regularization of inverse problems, In "D. A. Forsyth, P. H. S. Torr and A. Zisserman, editors, ECCV'08," volume 5304 of "Lecture Notes in Computer Science," pages 57-68. Springer, 2008.
[48]	G. Peyré, J. Fadili and J-L. Starck, Learning the morphological diversity, SIAM Journal on Imaging Sciences, to appear, 2010.
[49]	M. Rudelson and R. Vershynin, On sparse reconstruction from fourier and gaussian measurements, Commun. on Pure and Appl. Math., 61 (2008), 1025-1045.doi: 10.1002/cpa.20227.
[50]	L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[51]	J. Shanks, Computation of the fast walsh-fourier transform, IEEE Transactions on Computers, C-18 (1969), 457-459.doi: 10.1109/T-C.1969.222685.
[52]	S. M. Smith and J. M. Brady, SUSAN - a new approach to low level image processing, International Journal of Computer Vision, 23 (1997), 45-78.doi: 10.1023/A:1007963824710.
[53]	A. Spira, R. Kimmel and N. Sochen, A short time beltrami kernel for smoothing images and manifolds, IEEE Trans. Image Processing, 16 (2007), 1628-1636.doi: 10.1109/TIP.2007.894253.
[54]	A. D. Szlam, M. Maggioni and R. R. Coifman, Regularization on graphs with function-adapted diffusion processes, Journal of Machine Learning Research, 9 (2008), 1711-1739.
[55]	C. Tomasi and R. Manduchi, Bilateral filtering for gray and color images, In "Proc. of ICCV '98," pages 839-846, 1998.
[56]	D. Tschumperlé and R. Deriche, Vector-valued image regularization with PDEs: Acommon framework for different applications, IEEE Trans. Pattern Anal. Mach. Intell, 27 (2005), 506-517.doi: 10.1109/TPAMI.2005.87.
[57]	P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109 (2001), 475-494.doi: 10.1023/A:1017501703105.
[58]	L-Y. Wei and M. Levoy, Fast texture synthesis using tree-structured vector quantization, In "Proc. of SIGGRAPH '00," pages 479-488, ACM Press/Addison-Wesley Publishing Co., 2000.
[59]	L. P. Yaroslavsky, "Digital Picture Processing - An Introduction," Springer, Berlin, 1985.
[60]	X. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM Journal on Imaging Sciences, 3 (2010), 253-276.doi: 10.1137/090746379.
[61]	D. Zhou and B. Scholkopf, Regularization on discrete spaces, In "W. G. Kropatsch, R. Sablatnig and A. Hanbury, editors, German Pattern Recognition Symposium," volume 3663, pages 361-368, Springer, 2005.