UCLA

In 1992 Merriman, Bence and Osher proposed a computationally inexpensive threshold

dynamics algorithm for the approximation of the motion by mean curvature. Since its

introduction, numerous generalizations of the algorithm have been made, and the algorithm

has been successfully used in a wide variety of computer vision applications, such as image

segmentation, image inpainting, surface reconstruction etc.. The main focus of this work

are the extensions of the original algorithm as well as multiple new applications such as

probability 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, as

well as locating the region where activities generally occur. To achieve the goal of accurately

locating such regions, a binary segmentation version of the well-known Maximum Penal-

ized Likelihood Estimation (MPLE) model is designed. The method is applied to different

computational examples, including one with actual residential burglary data from the San

Fernando Valley.

In Part II we present an adaptation of the classic Merriman-Bence-Osher (MBO) scheme

utilizing a fully or semi nonlocal graph Laplacian for solving a wide range of learning problems

in data clustering and image processing. Combining ideas from L1 compressive sensing, image

processing and graph methods, the diffuse interface model based on the Ginzburg-Landau

functional was recently introduced to the graph community for solving problems in data

classification. Here, we propose an algorithm for graph-based methods and also make use of

fast numerical solvers for finding eigenvalues and eigenvectors of the graph Laplacian. To

demonstrate the performance of our model, various computational examples are presented,

which proves that the method is successful on images with texture and repetitive structure

due 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 proposed

algorithm. The success of this algorithm also raises an important theoretical question: is

it possible to define an analog of the motion by mean curvature of surfaces on graphs, and

what properties would such notion possess.