A General Framework for Regularized, Similaritybased Image Restoration 

Abstract 

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 graphbased 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 semidefinite, 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. 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 noncommercial 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 

References 

[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. 490530,
2005.  
[2] P. Milanfar, "A tour of modern image filtering," IEEE, Signal Processing Magazine, vol. 30, no. 1, pp. 106128, 2013.  
[3] R. Sinkhorn and P. Knopp, "Concerning nonnegative matrices and doubly stochastic matrices," Pacific J. Math, vol. 21, no. 2, pp. 343348, 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. 17151728, 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 hyperlaplacian priors," NIPS, pp. 10331041, 2009.  
[7] Q. Shan, J. Jia, and A. Agarwala, "Highquality motion deblurring from a single image," ACM Transactions on Graphics (SIGGRAPH), vol. 27, no. 3, pp. 73:173:10, Aug. 2008.  
[8] P. A. Knight and D. Ruiz, "A fast algorithm for matrix balancing,"
IMA J. Numer. Anal., vol. 33, pp. 10291047, 2013.  
[9] K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, "Image denoising
by sparse 3D transformdomain collaborative filtering," IEEE Trans.
Image Process., vol. 16, no. 8, pp. 20802095, Aug. 2007.  
[10] Focus Magic software 