| Title | Tighter Relaxations for Higher-Order Models based on Generalized Roof Duality |
| Authors | Johan Fredriksson, Carl Olsson, Petter Strandmark, Fredrik Kahl |
| Alternative Location | http://dx.doi.org/10.1007/9..., Restricted Access |
| Publication | Lecture Notes in Computer Science (Computer Vision - ECCV 2012 : Workshops and Demonstrations, Proceedings of the 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012, Part III) |
| Year | 2012 |
| Volume | 7585 |
| Pages | 273 - 282 |
| Document type | Conference paper |
| Conference name | ECCV 2012 Workshop on Higher-Order Models and Global Constraints in Computer Vision |
| Conference Date | 2012-10-13 |
| Conference Location | Florence, Italy |
| Status | Published |
| Quality controlled | Yes |
| Language | eng |
| Publisher | Springer |
| Abstract English | 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. |
| Keywords | computer vision, roof duality, pseudoboolean optimization, |
| ISBN/ISSN/Other | ISSN: 1611-3349 (online) ISBN: 978-3-642-33884-7 (print) |
Questions: webmaster
Last update: 2013-04-11
Centre for Mathematical Sciences, Box 118, SE-22100, Lund. Telefon: +46 46-222 00 00 (vx)