Skip to main content
Open Access Publications from the University of California

UC Santa Cruz

UC Santa Cruz Electronic Theses and Dissertations bannerUC Santa Cruz

Graph-based Image Restoration


Digital photography has experienced great progress during the past decade. A lot of people are recording their moments via digital hand-held cameras. Pictures taken with digital cameras usually undergo some sort of degradation in the form of noise/blur depending on the camera hardware and environmental conditions in which the photos are taken. This leads to an ever-increasing demand for effective and effcient image enhancement algorithms to achieve high quality output images in digital photography systems. In this dissertation, a new graph-based framework is introduced for different image restoration applications. This framework is based on exploiting the existing self-similarity in images. We introduce a new definition of normalized graph Laplacian matrix for image processing. We use this new definition to develop effective enhancement algorithms for image deblurring, image denoising, and image sharpening.

First, we develop a regularization framework for image deblurring by constructing a new graph-based cost function. Minimizing the corresponding cost function yields effective outputs for different blur types including out-of-focus and motion blurs. Our proposed deblurring algorithm based on the new definition of normalized graph Laplacian provides performance and analysis advantages over previous methods. We have shown its effectiveness for several synthetic and real deblurring examples.

Second, we develop a new graph-based framework for image denoising. The proposed denoising method exploits the similarity information in images by constructing the similarity matrix which in turn is used to derive the corresponding graph Laplacian. A graph-based objective function with new data fidelity and smoothness terms is constructed and minimized. We also establish the relationship between our proposed regularized framework and two well-known iterative methods for improving the performance of kernel-based denoising methods; namely, diusion and boosting iterations.

We compare the performance of the proposed denoising method with that of NLM algorithm [11] and demonstrate that our proposed algorithm is able to enhance over NLM. Furthermore, we present a graph-based analysis framework for multi-layer image decomposition using diffusion and boosting iterations.

Third, we propose a new data-adaptive sharpening algorithm based on the notion of difference of smoothing operators. We provide an interpretation of our proposed sharpening method as the image-derived version of difference of Gaussians (DoG) operator broadly used in numerous image processing and computer graphics tasks [66, 121, 122].

Finally, we provide a theoretical study on the reported range of the eigenvalues of various definitions of normalized graph Laplacian for different graph structures. This sheds light on the existing ambiguity on the spectral range of such matrices in different applications.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View