Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

Continuous Multiclass Labeling Approaches and Algorithms

Lellmann, Jan ; Schnörr, Christoph

[thumbnail of manuscript_preprint.pdf]
PDF, German
Download (3MB) | Terms of use

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the DOI, URN or the persistent URL below, as we can guarantee their long-time accessibility.


We study convex relaxations of the image labeling problem on a continuous domain with regularizers based on metric interaction potentials. The generic framework ensures existence of minimizers and covers a wide range of relaxations of the originally combinatorial problem. We focus on two specific relaxations that differ in flexibility and simplicity – one can be used to tightly relax any metric interaction potential, while the other one only covers Euclidean metrics but requires less computational effort. For solving the nonsmooth discretized problem, we propose a globally convergent Douglas-Rachford scheme, and show that a sequence of dual iterates can be recovered in order to provide a posteriori optimality bounds. In a quantitative comparison to two other first-order methods, the approach shows competitive performance on synthetical and real-world images. By combining the method with an improved binarization technique for nonstandard potentials, we were able to routinely recover discrete solutions within 1%–5% of the global optimum for the combinatorial image labeling problem.

Document type: Other
Series Name: IWR-Preprints
Date Deposited: 24 Feb 2010 12:01
Date: 2010
Faculties / Institutes: Service facilities > Interdisciplinary Center for Scientific Computing
DDC-classification: 510 Mathematics
Controlled Keywords: Kombinatorische Optimierung, Konvexe Optimierung, Nichtglatte Optimierung, Bildsegmentierung, Funktion von beschränkter Variation
Uncontrolled Keywords: Konvexe Relaxation , SattelpunktproblemContinuous Cut , Convex Relaxation , Saddle Point Problem
About | FAQ | Contact | Imprint |
OA-LogoDINI certificate 2013Logo der Open-Archives-Initiative