Tighter Relaxations for Higher-Order Models based on Generalized Roof Duality
(2012) ECCV 2012 Workshop on Higher-Order Models and Global Constraints in Computer Vision 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:
https://lup.lub.lu.se/record/3327302
- author
- Fredriksson, Johan LU ; Olsson, Carl LU ; Strandmark, Petter LU and Kahl, Fredrik LU
- organization
- publishing date
- 2012
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- computer vision, roof duality, pseudoboolean optimization
- host publication
- 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
- conference location
- Florence, Italy
- conference dates
- 2012-10-13
- 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
- additional info
- The ECCV 2012 Workshop on Higher-Order Models and Global Constraints in Computer Vision was held in conjunction with the 12th European Conference on Computer Vision (ECCV 2012), which took place at Florence, Italy, 7-13 October 2012.
- id
- a54541c7-c97a-41c1-bb62-303808a6d650 (old id 3327302)
- date added to LUP
- 2016-04-01 10:56:32
- date last changed
- 2024-10-07 17:05:44
@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}}, keywords = {{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}}, doi = {{10.1007/978-3-642-33885-4_28}}, volume = {{7585}}, year = {{2012}}, }