A General Framework for Regularized, Similarity-based Image Restoration

Amin Kheradmand and Peyman Milanfar


Any image can be represented as a function defined on a weighted graph, in which the underlying structure of the image is encoded in kernel similarity and associated Laplacian matrices. In this paper, we develop an iterative graph-based framework for image restoration based on a new definition of the normalized graph Laplacian. We propose a cost function which consists of a new data fidelity term and a regularization term derived from the specific definition of the normalized graph Laplacian. The normalizing coefficients used in the definition of the Laplacian and the associated regularization term are obtained using fast symmetry preserving matrix balancing. This results in some desired spectral properties for the normalized Laplacian such as being symmetric, positive semi-definite, and returning zero vector when applied to a constant image. Our algorithm comprises of outer and inner iterations, where in each outer iteration, the similarity weights are recomputed using the previous estimate and the updated objective function is minimized using inner Conjugate Gradient (CG) iterations. This procedure improves the performance of the algorithm for image deblurring, where we do not have access to a good initial estimate of the underlying image. Moreover, the specific form of the cost function allows us to render the spectral analysis for the solutions of the corresponding linear equations. Also, the proposed approach is general in the sense that we have shown its effectiveness for different restoration problems including deblurring, denoising, and sharpening. Experimental results verify the effectiveness of the proposed algorithm on both synthetic and real examples.

  • Overview
  • Experimental Results
  • MATLAB Code
  • See more details and examples in the following papers:


    Overview of the proposed method


    Deblurring examples



    Sharpening examples



    MATLAB Code

    This software is provided for non-commercial research purposes only. Use at your own risk. No warranty is implied by this distribution. Copyright © 2014 by University of California.
    Download - File updated: Oct 30 2014



    [1] A. Buades, B. Coll, and J. M. Morel, "A Review of Image Denoising Methods, with a New One," Multiscale Modeling and Simulation, vol. 4, no. 2, pp. 490-530, 2005.
    [2] P. Milanfar, "A tour of modern image filtering," IEEE, Signal Processing Magazine, vol. 30, no. 1, pp. 106-128, 2013.
    [3] R. Sinkhorn and P. Knopp, "Concerning nonnegative matrices and doubly stochastic matrices," Pacific J. Math, vol. 21, no. 2, pp. 343-348, 1967.
    [4] A. Danielyan, V. Katkovnik, and K. Egiazarian, "BM3D frames and variational image deblurring," IEEE Transactions on Image Processing, vol. 21, no. 4, pp. 1715-1728, April 2012.
    [5] S. Cho and S. Lee, "Fast motion deblurring," ACM Transactions on Graphics (SIGGRAPH ASIA), vol. 28, no. 5, p. article no. 145, 2009.
    [6] D. Krishnan and R. Fergus, "Fast image deconvolution using hyper-laplacian priors," NIPS, pp. 1033-1041, 2009.
    [7] Q. Shan, J. Jia, and A. Agarwala, "High-quality motion deblurring from a single image," ACM Transactions on Graphics (SIGGRAPH), vol. 27, no. 3, pp. 73:1-73:10, Aug. 2008.
    [8] P. A. Knight and D. Ruiz, "A fast algorithm for matrix balancing," IMA J. Numer. Anal., vol. 33, pp. 1029-1047, 2013.
    [9] K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, "Image denoising by sparse 3-D transform-domain collaborative filtering," IEEE Trans. Image Process., vol. 16, no. 8, pp. 2080-2095, Aug. 2007.
    [10] Focus Magic software