Theshold Dynamics for Statistical Density Estimation and Graph Clustering
Tijana Kostić · eScholarship (California Digital Library) · 2013
In 1992 Merriman, Bence and Osher proposed a computationally inexpensive thresholddynamics algorithm for the approximation of the motion by mean curvature. Since itsintroduction, numerous generalizations of the algorithm have been made, and the algorithmhas been successfully used in a wide variety of computer vision applications, such as imagesegmentation, image inpainting, surface reconstruction etc.. The main focus of this workare the extensions of the original algorithm as well as multiple new applications such asprobability density estimation and graph segmentation.Part I discusses a threshold dynamics segmentation algorithm for estimating a probabil-ity density based on discrete point data. Since point data may represent certain activities,such as crime, this method can be successfully used for detecting regions of high activity, aswell as locating the region where activities generally occur. To achieve the goal of accuratelylocating such regions, a binary segmentation version of the well-known Maximum Penal-ized Likelihood Estimation (MPLE) model is designed. The method is applied to differentcomputational examples, including one with actual residential burglary data from the SanFernando Valley.In Part II we present an adaptation of the classic Merriman-Bence-Osher (MBO) schemeutilizing a fully or semi nonlocal graph Laplacian for solving a wide range of learning problemsin data clustering and image processing. Combining ideas from L1 compressive sensing, imageprocessing and graph methods, the diffuse interface model based on the Ginzburg-Landaufunctional was recently introduced to the graph community for solving problems in dataclassification. Here, we propose an algorithm for graph-based methods and also make use offast numerical solvers for finding eigenvalues and eigenvectors of the graph Laplacian. Todemonstrate the performance of our model, various computational examples are presented,which proves that the method is successful on images with texture and repetitive structuredue to its nonlocal nature. A wide range of applications is discussed, including data labeling,image segmentation and image inpainting, which demonstrates the versatility of the proposedalgorithm. The success of this algorithm also raises an important theoretical question: isit possible to define an analog of the motion by mean curvature of surfaces on graphs, andwhat properties would such notion possess.