Tight convex relaxations for vector-valued labeling

Goldluecke B, Strekalovskiy E, Cremers D (2013)

Publication Type: Journal article

Publication year: 2013

Journal

Siam Journal on Imaging Sciences Society for Industrial and Applied Mathematics

Book Volume: 6

Pages Range: 1626-1664

Journal Issue: 3

DOI: 10.1137/120862351

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. © by SIAM.

Involved external institutions

Ruprecht-Karls-Universität Heidelberg DE Germany (DE) Technische Universität München (TUM) DE Germany (DE)

How to cite

APA:

Goldluecke, B., Strekalovskiy, E., & Cremers, D. (2013). Tight convex relaxations for vector-valued labeling. Siam Journal on Imaging Sciences, 6(3), 1626-1664. https://dx.doi.org/10.1137/120862351

MLA:

Goldluecke, Bastian, Evgeny Strekalovskiy, and Daniel Cremers. "Tight convex relaxations for vector-valued labeling." Siam Journal on Imaging Sciences 6.3 (2013): 1626-1664.

BibTeX: Download