Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem

Jan Lellmann, Frank Lenzen, Christoph Schnörr

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


We consider a variational convex relaxation of a class of optimal partitioning and multiclass labeling problems, which has recently proven quite successful and can be seen as a continuous analogue of Linear Programming (LP) relaxation methods for finite-dimensional problems. While for the latter several optimality bounds are known, to our knowledge no such bounds exist in the infinite-dimensional setting. We provide such a bound by analyzing a probabilistic rounding method, showing that it is possible to obtain an integral solution of the original partitioning problem from a solution of the relaxed problem with an a priori upper bound on the objective. The approach has a natural interpretation as an approximate, multiclass variant of the celebrated coarea formula. © 2012 Springer Science+Business Media New York.
Original languageEnglish (US)
Pages (from-to)239-257
Number of pages19
JournalJournal of Mathematical Imaging and Vision
Issue number3
StatePublished - Nov 9 2012
Externally publishedYes


Dive into the research topics of 'Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem'. Together they form a unique fingerprint.

Cite this