Tight convex relaxations for vector-valued labeling

• Verfasst von: Goldlücke, Bastian [VerfasserIn]
• Verfasst von: Strekalovskiy, Evgeny [VerfasserIn]
• Verfasst von: Cremers, Daniel [VerfasserIn]
• Titel: Tight convex relaxations for vector-valued labeling
• Verf.angabe: Bastian Goldluecke, Evgeny Strekalovskiy, and Daniel Cremers
• E-Jahr: 2013
• Jahr: August 22, 2013
• Umfang: 39 S.
• Fussnoten: Gesehen am 17.02.2020
• Titel Quelle: Enthalten in: Society for Industrial and Applied MathematicsSIAM journal on imaging sciences
• Ort Quelle: Philadelphia, Pa. : SIAM, 2008
• Jahr Quelle: 2013
• Band/Heft Quelle: 6(2013), 3, Seite 1626-1664
• ISSN Quelle: 1936-4954
• DOI: doi:10.1137/120862351
• Datenträger: Online-Ressource
• Sprache: eng
• K10plus-PPN: 1748490257

Abstract

Multilabel problems are of fundamental importance in computer vision and image analysis. Yet, finding global minima of the associated energies is typically a hard computational challenge. Recently, progress has been made by reverting to spatially continuous formulations of respective problems and solving the arising convex relaxation globally. In practice this leads to solutions which are either optimal or within an a posteriori bound of the optimum. Unfortunately, in previous methods, both run time and memory requirements scale linearly in the total number of labels, making these methods very inefficient and often not applicable to problems with higher dimensional label spaces. In this paper, we propose a reduction technique for the case that the label space is a continuous product space and the regularizer is separable, i.e., a sum of regularizers for each dimension of the label space. In typical real-world labeling problems, the resulting convex relaxation requires orders of magnitude less memory and computation time than previous methods. This enables us to apply it to large-scale problems like optic flow, stereo with occlusion detection, segmentation into a very large number of regions, and joint denoising and local noise estimation. Experiments show that despite the drastic gain in performance, we do not arrive at less accurate solutions than the original relaxation. Using the novel method, we can for the first time efficiently compute solutions to the optic flow functional which are within provable bounds (typically 5%) of the global optimum.