Extending Continuous Cuts: Anisotropic Metrics and Expansion Moves

Carl Olsson, Martin Byröd, Niels Christian Overgaard, Fredrik Kahl

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

19 Citations (SciVal)


The concept of graph cuts is by now a standard method for all sorts of low level vision problems. Its popularity is largely due to the fact that globally or near globally optimal solutions can be computed using efficient max flow algorithms. On the other hand it has been observed that this method may suffer from metrication errors. Recent work has begun studying continuous versions of graph cuts, which give smaller metrication errors. Another advantage is that continuous cuts are straightforward to parallelize. In this paper we extend the class of functionals that can be optimized in the continuous setting to include anisotropic TV-norms. We show that there is a so called coarea formula for these functionals making it possible to minimize them by solving a convex problem. We also show that the concept of α-expansion moves can be reformulated to fit the continuous formulation, and we derive approximation bounds in analogy with the discrete case. A continuous version of the Potts model for multi-class segmentation problems is presented, and it is shown how to obtain provably good solutions using continuous α-expansions.
Original languageEnglish
Title of host publicationProceedings of 2009 IEEE 12th International Conference on Computer Vision (ICCV)
PublisherIEEE - Institute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Print)978-1-4244-4419-9
Publication statusPublished - 2009
EventIEEE International Conference on Computer Vision (ICCV), 2009 - Kyoto, Japan
Duration: 2009 Sep 272009 Oct 4


ConferenceIEEE International Conference on Computer Vision (ICCV), 2009

Subject classification (UKÄ)

  • Computer Vision and Robotics (Autonomous Systems)
  • Mathematics


Dive into the research topics of 'Extending Continuous Cuts: Anisotropic Metrics and Expansion Moves'. Together they form a unique fingerprint.

Cite this