eprintid: 10460
rev_number: 15
eprint_status: archive
userid: 1
dir: disk0/00/01/04/60
datestamp: 2010-02-24 12:01:18
lastmod: 2016-01-14 04:31:18
status_changed: 2012-08-15 08:52:56
type: report
metadata_visibility: show
creators_name: Lellmann, Jan
creators_name: Schnörr, Christoph
title: Continuous Multiclass Labeling Approaches and Algorithms
ispublished: pub
subjects: ddc-510
divisions: i-708000
keywords: Konvexe Relaxation , SattelpunktproblemContinuous Cut , Convex Relaxation , Saddle Point Problem
cterms_swd: Kombinatorische Optimierung
cterms_swd: Konvexe Optimierung
cterms_swd: Nichtglatte Optimierung
cterms_swd: Bildsegmentierung
cterms_swd: Funktion von beschränkter Variation
abstract: 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.
abstract_translated_lang: eng
date: 2010
date_type: published
id_scheme: DOI
id_number: 10.11588/heidok.00010460
ppn_swb: 1649182430
own_urn: urn:nbn:de:bsz:16-opus-104603
language: ger
bibsort: LELLMANNJACONTINUOUS2010
full_text_status: public
series: IWR-Preprints
citation:   Lellmann, Jan ; Schnörr, Christoph  (2010) Continuous Multiclass Labeling Approaches and Algorithms.  [Other]     
document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/10460/1/manuscript_preprint.pdf