A convex relaxation approach for computing minimal partitions

Thomas Pock, Antonin Chambolle, Daniel Cremers, Horst Bischof

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

222 Scopus citations

Abstract

In this work we propose a convex relaxation approach for computing minimal partitions. Our approach is based on rewriting the minimal partition problem (also known as Potts model) in terms of a primal dual Total Variation functional. We show that the Potts prior can be incorporated by means of convex constraints on the dual variables. For minimization we propose an efficient primal dual projected gradient algorithm which also allows a fast implementation on parallel hardware. Although our approach does not guarantee to find global minimizers of the Potts model we can give a tight bound on the energy between the computed solution and the true minimizer. Furthermore we show that our relaxation approach dominates recently proposed relaxations. As a consequence, our approach allows to compute solutions closer to the true minimizer. For many practical problems we even find the global minimizer. We demonstrate the excellent performance of our approach on several multi-label image segmentation and stereo problems.

Original languageEnglish
Title of host publication2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, CVPR Workshops 2009
PublisherIEEE Computer Society
Pages810-817
Number of pages8
ISBN (Print)9781424439935
DOIs
StatePublished - 2009
Externally publishedYes
Event2009 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2009 - Miami, FL, United States
Duration: 20 Jun 200925 Jun 2009

Publication series

Name2009 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2009

Conference

Conference2009 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2009
Country/TerritoryUnited States
CityMiami, FL
Period20/06/0925/06/09

Fingerprint

Dive into the research topics of 'A convex relaxation approach for computing minimal partitions'. Together they form a unique fingerprint.

Cite this