Variational and PDE-Based Methods for Big Data Analysis, Classification and Image Processing Using Graphs.

摘要

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 hyper-spectral 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.