TY - JOUR
T1 - Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem
AU - Lellmann, Jan
AU - Lenzen, Frank
AU - Schnörr, Christoph
N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): KUK-I1-007-43
Acknowledgements: 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.
PY - 2012/11/9
Y1 - 2012/11/9
N2 - We consider a variational convex relaxation of a class of optimal partitioning and multiclass labeling problems, which has recently proven quite successful and can be seen as a continuous analogue of Linear Programming (LP) relaxation methods for finite-dimensional problems. While for the latter several optimality bounds are known, to our knowledge no such bounds exist in the infinite-dimensional setting. We provide such a bound by analyzing a probabilistic rounding method, showing that it is possible to obtain an integral solution of the original partitioning problem from a solution of the relaxed problem with an a priori upper bound on the objective. The approach has a natural interpretation as an approximate, multiclass variant of the celebrated coarea formula. © 2012 Springer Science+Business Media New York.
AB - We consider a variational convex relaxation of a class of optimal partitioning and multiclass labeling problems, which has recently proven quite successful and can be seen as a continuous analogue of Linear Programming (LP) relaxation methods for finite-dimensional problems. While for the latter several optimality bounds are known, to our knowledge no such bounds exist in the infinite-dimensional setting. We provide such a bound by analyzing a probabilistic rounding method, showing that it is possible to obtain an integral solution of the original partitioning problem from a solution of the relaxed problem with an a priori upper bound on the objective. The approach has a natural interpretation as an approximate, multiclass variant of the celebrated coarea formula. © 2012 Springer Science+Business Media New York.
UR - http://hdl.handle.net/10754/599097
UR - http://link.springer.com/10.1007/s10851-012-0390-7
UR - http://www.scopus.com/inward/record.url?scp=84883253548&partnerID=8YFLogxK
U2 - 10.1007/s10851-012-0390-7
DO - 10.1007/s10851-012-0390-7
M3 - Article
SN - 0924-9907
VL - 47
SP - 239
EP - 257
JO - Journal of Mathematical Imaging and Vision
JF - Journal of Mathematical Imaging and Vision
IS - 3
ER -