Discrete and Continuous Models for Partitioning Problems

Jan Lellmann, Björn Lellmann, Florian Widmann, Christoph Schnörr

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


Recently, variational relaxation techniques for approximating solutions of partitioning problems on continuous image domains have received considerable attention, since they introduce significantly less artifacts than established graph cut-based techniques. This work is concerned with the sources of such artifacts. We discuss the importance of differentiating between artifacts caused by discretization and those caused by relaxation and provide supporting numerical examples. Moreover, we consider in depth the consequences of a recent theoretical result concerning the optimality of solutions obtained using a particular relaxation method. Since the employed regularizer is quite tight, the considered relaxation generally involves a large computational cost. We propose a method to significantly reduce these costs in a fully automatic way for a large class of metrics including tree metrics, thus generalizing a method recently proposed by Strekalovskiy and Cremers (IEEE conference on computer vision and pattern recognition, pp. 1905-1911, 2011). © 2013 Springer Science+Business Media New York.
Original languageEnglish (US)
Pages (from-to)241-269
Number of pages29
JournalInternational Journal of Computer Vision
Issue number3
StatePublished - Apr 11 2013
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): KUK-I1- 007-43
Acknowledgements: The second and third author were supported by Engineering and Physical Sciences Research Council (EPSRC)-Project EP/H016317/1. This publication is partly based on work supported by Award No. KUK-I1- 007-43, made by King Abdullah University of Science and Technology (KAUST).
This publication acknowledges KAUST support, but has no KAUST affiliated authors.


Dive into the research topics of 'Discrete and Continuous Models for Partitioning Problems'. Together they form a unique fingerprint.

Cite this