Global Binary Optimization on Graphs for Classification of High Dimensional Data
Abstract
This work develops a global minimization framework for segmentation of high dimensional data into two classes. It combines recent convex optimization methods from imaging 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. If constraints on the volume of the regions are incorporated, global minimizers cannot be guaranteed, but can often be obtained in practice and otherwise be closely approximated. Experiments on benchmark data sets show that our models produce segmentation results that are comparable with or outperform the state-of-the-art algorithms. In particular, we perform a thorough comparison to recent MBO and phase field methods, and show the advantage of the algorithms proposed in this paper.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 2014
- Accession Number
- ADA610270
Entities
People
- Andrea Bertozzi
- Egil Bae
- Ekaterina Merkurjev
- Xue-cheng Tai
Organizations
- University of California, Los Angeles