UCLA

We present several graph-based algorithms for image processing and classification of high- dimensional data. The first (semi-supervised) method uses a graph adaptation of the classical numerical Merriman-Bence-Osher (MBO) scheme, and can be extended to the multiclass case via the Gibbs simplex. We show examples of the application of the algorithm in the areas of image inpainting (both binary and grayscale), image segmentation and classification on benchmark data sets. We have also applied this algorithm to the problem of object detection using hyperspectral video sequences as a data set. In addition, a second related model is introduced. It uses a diffuse interface model based on the Ginzburg-Landau functional, related to total variation compressed sensing and image processing. A multiclass extension is introduced using the Gibbs simplex, with the functional’s double-well potential modified to handle the multiclass case. The version minimizes the functional using a convex splitting numerical scheme. In our computations, we make use of fast numerical solvers for finding the eigenvectors and eigenvalues of the graph Laplacian, and take advantage of the sparsity of the matrix. Experiments on benchmark data sets show that our models produce results that are comparable with or outperform the state-of-the-art algorithms. The second (semi-supervised) method develops a global minimization framework for binary classification of high-dimensional data. It combines recent convex optimization methods for image processing with recent graph based variational models for data segmentation. Two convex splitting algorithms are proposed, where graph-based PDE techniques are used to solve some of the subproblems. It is shown that global minimizers can be guaranteed for semi-supervised segmentation with two regions. If constraints on the volume of the regions are incorporated, global minimizers cannot be guaranteed, but can often be obtained in practice and otherwise be closely approximated. We perform a thorough comparison to recent MBO (Merriman-Bence-Osher) and phase field methods, and show the advantage of the proposed algorithms. Lastly, we present the current work (unsupervised method) related to normalized cuts. The method uses a clever alternative to the normalized cut to solve the binary classification problem. In particular, we work with the Ginzburg-Landau functional. In addition, we use a generalized graphical framework, so several different graph Laplacians are tested and their results are compared.