Advanced Search
Article Contents
Article Contents

Non-local regularization of inverse problems

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 68U10, 94A08; Secondary: 49N45.


    \begin{equation} \\ \end{equation}
  • [1]

    A. Adams, N. Gelfand, J. Dolson and M. Levoy, Gaussian KD-trees for fast high-dimensional filtering, ACM Transactions on Graphics, 28, 2009.


    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.


    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.


    M. Avriel, "Nonlinear Programming: Analysis and Methods," Dover Publishing, 2003.


    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.


    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.


    M. Bertalmìo, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, In "Siggraph 2000," pages 417-424, 2000.


    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.


    A. Buades, B. Coll and J-M. Morel, "Image Enhancement By Non-local Reverse Heat Equation," Preprint CMLA 2006-22, 2006.


    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.


    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.


    A. Chambolle, An algorithm for total variation minimization and applications, Journal of Mathematical Imaging and Vision, 20 (2004), 89-97.


    T. Chan and J. Shen, Mathematical models for local nontexture inpaintings, SIAM J. Appl. Math, 62 (2002), 1019-1043.doi: 10.1137/S0036139900368844.


    P. G. Ciarlet, "Introduction to Numerical Linear Algebra and Optimisation," Cambridge University Press, Cambridge, 1989.


    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.


    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.


    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.


    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.


    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.


    D. Donoho, Compressed sensing, IEEE Transactions on Information Theory, 52 (2006), 1289-1306.doi: 10.1109/TIT.2006.871582.


    D. Donoho and I. Johnstone, Ideal spatial adaptation via wavelet shrinkage, Biometrika, 81 (1994), 425-455.doi: 10.1093/biomet/81.3.425.


    D. Donoho, Y. Tsaig, I. Drori and J-L. Starck, Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit, Preprint, 2006.


    M. Ebrahimi and E. R. Vrscay, Solving the inverse problem of image zooming using 'self examples', In "ICIAR07," pages 117-130, 2007.


    A. A. Efros and T. K. Leung, Texture synthesis by non-parametric sampling, In "Proc. of ICCV '99," page 1033. IEEE Computer Society, 1999.


    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.


    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.


    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.


    G. Facciolo, P. Arias, V. Caselles and G. Sapiro, "Exemplar-based Interpolation of Sparsely Sampled Images," IMA Preprint Series # 2264, 2009.


    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.


    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.


    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.


    G. Gilboa, J. Darbon, S. Osher and T. F. Chan, "Nonlocal Convex Functionals for Image Regularization," UCLA CAM Report 06-57, 2006.


    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.


    G. Gilboa and S. Osher, Nonlocal operators with applications to image processing, SIAM Multiscale Modeling & Simulation, 7 (2008), 1005-1028.


    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.


    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.


    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.


    F. Malgouyres and F. Guichard, Edge direction preserving image zooming: A mathematical and numerical analysis, SIAM Journal on Numer. An., 39 (2001), 1-37.


    S. Mallat, "A Wavelet Tour of Signal Processing," 3rd edition, Academic Press, San Diego, 2008.


    S. Masnou, Disocclusion: A variational approach using level lines, IEEE Trans. Image Processing, 11 (2002), 68-76.doi: 10.1109/83.982815.


    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.


    Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program. Ser. A, 103 (2005), 127-152.doi: 10.1007/s10107-004-0552-5.


    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.


    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.


    G. Peyré, Image processing with non-local spectral bases, SIAM Multiscale Modeling and Simulation, 7 (2008), 703-730.doi: 10.1137/07068881X.


    G. Peyré, Sparse modeling of textures, J. Math. Imaging Vis., 34 (2009), 17-31.doi: 10.1007/s10851-008-0120-3.


    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.


    G. Peyré, J. Fadili and J-L. Starck, Learning the morphological diversity, SIAM Journal on Imaging Sciences, to appear, 2010.


    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.


    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.


    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.


    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.


    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.


    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.


    C. Tomasi and R. Manduchi, Bilateral filtering for gray and color images, In "Proc. of ICCV '98," pages 839-846, 1998.


    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.


    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.


    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.


    L. P. Yaroslavsky, "Digital Picture Processing - An Introduction," Springer, Berlin, 1985.


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(212) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint