Nonlocal Variational Methods in Image and Data Processing

In this dissertation, two nonlocal variational models for image and data processing are presented: nonlocal total variation (NLTV) for unsupervised hyperspectral image classification, and low dimensional manifold model (LDMM) for general image and data processing problems. Both models utilize the nonlocal patch-based structures in natural images and data, and modern optimization techniques are used to solve the corresponding variational problems. The proposed algorithms achieve state-of-the-art results on various image and data processing problems, in particular unsupervised hyperspectral image classification and image or data interpolation.First, a graph-based nonlocal total variation method is proposed for unsupervised classification of hyperspectral images (HSI). The variational problem is solved by the primal-dual hybrid gradient (PDHG) algorithm. By squaring the labeling function and using a stable simplex clustering routine, an unsupervised clustering method with random initialization can be implemented. The effectiveness of the proposed algorithm is illustrated on both synthetic and real-world HSI, and numerical results show that the proposed algorithm outperforms other standard unsupervised clustering methods such as spherical K-means, nonnegative matrix factorization (NMF), and the graph-based Merriman-Bence-Osher (MBO) scheme.Next, we present a novel low dimensional manifold model for general image processing problems. LDMM is based on the fact that the patch manifolds of many natural images have low dimensional structures. Based on this observation, the dimension of the patch manifold is used as a regularization to recover the image. The key step in LDMM is to solve a Laplace-Beltrami equation over a point cloud, and it is tackled by the point integral method (PIM). The point integral method enforces the sample point constraints correctly and yields better results than the standard graph Laplacian. LDMM can be used for various image processing problems, and it achieves state-of-the-art results for image inpainting from random subsampling.Lastly, we present an alternative way to solve the Laplace-Beltrami equation in LDMM. Although the point integral method correctly enforces the sample point constraints and achieves excellent results for image inpainting, the resulting linear system is on the patch domain, and hundreds of linear systems need to be solved each iteration. This causes LDMM to be computationally infeasible for large images and high dimensional data. An alternative way is to discretize the Laplace-Beltrami operator with the weighted graph Laplacian (WGL). After such discretization, we only need to solve one symmetric sparse linear system per iteration of manifold update for image inpainting. Moreover, semi-local patches that in- corporate coordinate information of the patches are used in the weight update, which leads to a faster convergence of LDMM. Numerical experiments on normal image, hyperspectral image, and high dimensional scientific data interpolation demonstrate the effectiveness of the algorithm