Sökning: onr:"swepub:oai:lup.lub.lu.se:edc225e6-2f9b-41f9-b0c9-630389f1491b" >
Generalized Roof Du...
Generalized Roof Duality for Pseudo-Boolean Optimization
-
- Kahl, Fredrik (författare)
- Lund University,Lunds universitet,Matematik LTH,Matematikcentrum,Institutioner vid LTH,Lunds Tekniska Högskola,Mathematics (Faculty of Engineering),Centre for Mathematical Sciences,Departments at LTH,Faculty of Engineering, LTH
-
- Strandmark, Petter (författare)
- Lund University,Lunds universitet,Matematik LTH,Matematikcentrum,Institutioner vid LTH,Lunds Tekniska Högskola,Mathematics (Faculty of Engineering),Centre for Mathematical Sciences,Departments at LTH,Faculty of Engineering, LTH
-
(creator_code:org_t)
- 2011
- 2011
- Engelska 8 s.
-
Ingår i: IEEE International Conference on Computer Vision (ICCV). ; , s. 255-262
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- The number of applications in computer vision that model higher-order interactions has exploded over the last few years. The standard technique for solving such problems is to reduce the higher-order objective function to a quadratic pseudo-boolean function, and then use roof duality for obtaining a lower bound. Roof duality works by constructing the tightest possible lower-bounding submodular function, and instead of optimizing the original objective function, the relaxation is minimized. We generalize this idea to polynomials of higher degree, where quadratic roof duality appears as a special case. Optimal relaxations are defined to be the ones that give the maximum lower bound. We demonstrate that important properties such as persistency still hold and how the relaxations can be efficiently constructed for general cubic and quartic pseudo-boolean functions. From a practical point of view, we show that our relaxations perform better than state-of-the-art for a wide range of problems, both in terms of lower bounds and in the number of assigned variables.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datorseende och robotik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Vision and Robotics (hsv//eng)
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)