Advanced

Tighter Relaxations for Higher-Order Models based on Generalized Roof Duality

Fredriksson, Johan LU ; Olsson, Carl LU ; Strandmark, Petter LU and Kahl, Fredrik LU (2012) ECCV 2012 Workshop on Higher-Order Models and Global Constraints in Computer Vision In Lecture Notes in Computer Science (Computer Vision - ECCV 2012. Workshops and Demonstrations, Florence, Italy, October 7-13, 2012, Proceedings, Part III) 7585. p.273-282
Abstract
Many problems in computer vision can be turned into a large-scale boolean optimization problem, which is in general NP-hard. In this paper, we further develop one of the most successful approaches, namely roof duality, for approximately solving such problems for higher-order models. Two new methods that can be applied independently or in combination are investigated. The first one is based on constructing relaxations using generators of the submodular function cone. In the second method, it is shown that the roof dual bound can be applied in an iterated way in order to obtain a tighter relaxation. We also provide experimental results that demonstrate better performance with respect to the state-of-the-art, both in terms of improved bounds... (More)
Many problems in computer vision can be turned into a large-scale boolean optimization problem, which is in general NP-hard. In this paper, we further develop one of the most successful approaches, namely roof duality, for approximately solving such problems for higher-order models. Two new methods that can be applied independently or in combination are investigated. The first one is based on constructing relaxations using generators of the submodular function cone. In the second method, it is shown that the roof dual bound can be applied in an iterated way in order to obtain a tighter relaxation. We also provide experimental results that demonstrate better performance with respect to the state-of-the-art, both in terms of improved bounds and the number of optimally assigned variables. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
computer vision, roof duality, pseudoboolean optimization
in
Lecture Notes in Computer Science (Computer Vision - ECCV 2012. Workshops and Demonstrations, Florence, Italy, October 7-13, 2012, Proceedings, Part III)
volume
7585
pages
10 pages
publisher
Springer
conference name
ECCV 2012 Workshop on Higher-Order Models and Global Constraints in Computer Vision
external identifiers
  • scopus:84867705310
ISSN
1611-3349
0302-9743
ISBN
978-3-642-33885-4
978-3-642-33884-7 (print)
DOI
10.1007/978-3-642-33885-4_28
language
English
LU publication?
yes
id
a54541c7-c97a-41c1-bb62-303808a6d650 (old id 3327302)
date added to LUP
2013-02-12 17:58:51
date last changed
2017-01-01 04:01:45
@inproceedings{a54541c7-c97a-41c1-bb62-303808a6d650,
  abstract     = {Many problems in computer vision can be turned into a large-scale boolean optimization problem, which is in general NP-hard. In this paper, we further develop one of the most successful approaches, namely roof duality, for approximately solving such problems for higher-order models. Two new methods that can be applied independently or in combination are investigated. The first one is based on constructing relaxations using generators of the submodular function cone. In the second method, it is shown that the roof dual bound can be applied in an iterated way in order to obtain a tighter relaxation. We also provide experimental results that demonstrate better performance with respect to the state-of-the-art, both in terms of improved bounds and the number of optimally assigned variables.},
  author       = {Fredriksson, Johan and Olsson, Carl and Strandmark, Petter and Kahl, Fredrik},
  booktitle    = {Lecture Notes in Computer Science (Computer Vision - ECCV 2012. Workshops and Demonstrations, Florence, Italy, October 7-13, 2012, Proceedings, Part III)},
  isbn         = {978-3-642-33885-4},
  issn         = {1611-3349},
  keyword      = {computer vision,roof duality,pseudoboolean optimization},
  language     = {eng},
  pages        = {273--282},
  publisher    = {Springer},
  title        = {Tighter Relaxations for Higher-Order Models based on Generalized Roof Duality},
  url          = {http://dx.doi.org/10.1007/978-3-642-33885-4_28},
  volume       = {7585},
  year         = {2012},
}