Skip to main content
Open Access Publications from the University of California


UCLA Previously Published Works bannerUCLA

An MBO Scheme on Graphs for Classification and Image Processing

Published Web Location

In this paper we present a computationally efficient algorithm utilizing a fully or seminonlocal graph Laplacian for solving a wide range of learning problems in binary data classification and image processing. In their recent work [Multiscale Model. Simul., 10 (2012), pp. 1090--1118], Bertozzi and Flenner introduced a graph-based diffuse interface model utilizing the Ginzburg--Landau functional for solving problems in data classification. Here, we propose an adaptation of the classic numerical Merriman--Bence--Osher (MBO) scheme for minimizing graph-based diffuse interface functionals, like those originally proposed by Bertozzi and Flenner. We also make use of fast numerical solvers for finding eigenvalues and eigenvectors of the graph Laplacian. Various computational examples are presented to demonstrate the performance of our algorithm, which is successful on images with texture and repetitive structure due to its nonlocal nature. The results show that our method is multiple times more efficient than other well-known nonlocal models. © 2013 Society for Industrial and Applied Mathematics.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View