File Exchange

image thumbnail


version 1.0 (86.8 KB) by Dominique Zosso
A minimal surface criterion and its linearized version (Dirichlet criterion) for graph partitioning


Updated 07 Nov 2016

View License

We consider a geometric approach to graph partitioning based on the graph Beltrami energy, a discrete version of a functional that appears in classical minimal surface problems. More specifically, the optimality criterion is given by the sum of the minimal Beltrami energies of the partition components. We adapt primal-dual convex optimization methods to solve for the minimal Beltrami energy for each component of a given partition. A rearrangement algorithm is proposed to find the graph partition to minimize a relaxed version of the objective.
We also provide efficient code to solve the much faster, linearized minimal surface criterion instead (Dirichlet energy).

The toolbox includes a simple five-moons test data set (dbmoon.mat) and example code to reproduce the five-moons example.

The code is immediately based on the following two papers (to referred to as documentation and to be cited as reference):

[1] Dominique Zosso, Braxton Osting, "A minimal surface criterion for graph partitioning", Inverse Problems and Imaging 10(4):1149-1180, 2016.

and its linearized, faster version :

[2] Dominique Zosso, Braxton Osting, Stanley J. Osher, "A Dirichlet Energy Criterion for Graph-Based Image Segmentation", 2015 IEEE ICDM Workshop.

Cite As

Dominique Zosso (2020). MinimalSurfacePartitioning (, MATLAB Central File Exchange. Retrieved .

Comments and Ratings (1)

MATLAB Release Compatibility
Created with R2016a
Compatible with any release
Platform Compatibility
Windows macOS Linux