Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
; ; and
organization
publishing date
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
0302-9743
1611-3349
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-01-07 04:46:13
@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         = {{0302-9743}},
  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}},
}