Entropy minimization for convex relaxation approaches
Souiai M, Oswald MR, Kee Y, Kim J, Pollefeys M, Cremers D (2015)
Publication Type: Conference contribution
Publication year: 2015
Publisher: Institute of Electrical and Electronics Engineers Inc.
Book Volume: 2015 International Conference on Computer Vision, ICCV 2015
Pages Range: 1778-1786
Conference Proceedings Title: Proceedings of the IEEE International Conference on Computer Vision
Event location: Santiago, CHL
ISBN: 9781467383912
Abstract
Despite their enormous success in solving hard combinatorial problems, convex relaxation approaches often suffer from the fact that the computed solutions are far from binary and that subsequent heuristic binarization may substantially degrade the quality of computed solutions. In this paper, we propose a novel relaxation technique which incorporates the entropy of the objective variable as a measure of relaxation tightness. We show both theoretically and experimentally that augmenting the objective function with an entropy term gives rise to more binary solutions and consequently solutions with a substantially tighter optimality gap. We use difference of convex function (DC) programming as an efficient and provably convergent solver for the arising convex-concave minimization problem. We evaluate this approach on three prominent non-convex computer vision challenges: multi-label inpainting, image segmentation and spatio-temporal multi-view reconstruction. These experiments show that our approach consistently yields better solutions with respect to the original integral optimization problem.
Involved external institutions
Technische Universität München (TUM)
Germany (DE)
Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich
Switzerland (CH)
Korea Advanced Institute of Science and Technology (KAIST)
Korea, Republic of (KR)
Germany (DE)
Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich
Switzerland (CH)
Korea Advanced Institute of Science and Technology (KAIST)
Korea, Republic of (KR)
How to cite
APA:
Souiai, M., Oswald, M.R., Kee, Y., Kim, J., Pollefeys, M., & Cremers, D. (2015). Entropy minimization for convex relaxation approaches. In Proceedings of the IEEE International Conference on Computer Vision (pp. 1778-1786). Santiago, CHL: Institute of Electrical and Electronics Engineers Inc..
MLA:
Souiai, Mohamed, et al. "Entropy minimization for convex relaxation approaches." Proceedings of the 15th IEEE International Conference on Computer Vision, ICCV 2015, Santiago, CHL Institute of Electrical and Electronics Engineers Inc., 2015. 1778-1786.
BibTeX: Download