Graph regularization for inverse problems in imaging

This thesis explores graph-based regularization techniques for inverse problems in imaging and vision. Broadly speaking, the inverse problems we consider fall under one of two categories: image restoration, and surface reconstruction. The problem of image de-noising and de-blurring falls under the category of image restoration, while the problem of estimating optical flow or disparity falls under the category of surface reconstruction. In image restoration problems, the challenge is usually to smooth the image while preserving its features and texture at the same time, a seeming antithesis between the two competing goals. In surface reconstruction problems, the challenge is instead to reconstruct some piece-wise smooth representation of the underlying scene. In any case, we can use graphs to represent connections between pixels whose intensity values or motion vectors are related. Essentially, a graph defines an adaptive averaging filter whose filter kernel at a pixel is determined by the connection between the corresponding vertex and its neighbors on the graph. Traditionally, inverse problems are formulated using the Bayesian framework, the calculus of variations, or partial differential equations. However, all problems must be solved numerically using a digital computer, so they are ultimately discretised regardless of the original continuous-domain framework used to formulate them. Since graphs are algebraic constructs, we need not restrict ourselves to a grid-like topology. Formulating some given inverse problem directly on a graph is equivalent to defining an adaptive averaging filter for a given image. Later, we see that graphs are generally more useful if they are dense, i.e., there are many connections between pixels, and dynamic, i.e., the graph changes continually. The concepts of dense and dynamic graphs relate respectively to the idea of non-local operators and iteratively re-weighted optimization. An important aspect of graph Laplacians is that the graph edges can be densified to improve the noise-filtering and edge-preserving behavior. Two important examples of dense graphs considered are ones constructed using progressively larger box or Gaussian kernels, which, due to their well-known Fourier transforms, allowed us to analytically derive the spectra of the corresponding Laplacians