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

An MBO scheme on graphs for classification and image processing

  • Author(s): Merkurjev, E
  • Kostić, T
  • Bertozzi, AL
  • et al.

Published Web Location

https://doi.org/10.1137/120886935
Abstract

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 Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View