Open AccessGeneral Search Algorithms for Energy Minimization Problems
Author(s) -
Dmitrij Schlesinger
Publication year - 2009
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/978-3-642-03641-5_7
Subject(s) - minification , computer science , energy minimization , solver , relaxation (psychology) , heuristic , energy (signal processing) , algorithm , mathematical optimization , scheme (mathematics) , mathematics , artificial intelligence , psychology , social psychology , mathematical analysis , chemistry , statistics , computational chemistry
We describe a scheme for solving Energy Minimization problems, which is based on the A * algorithm accomplished with appropriately chosen LP-relaxations as heuristic functions. The proposed scheme is quite general and therefore can not be applied directly for real computer vision tasks. It is rather a framework, which allows to study some properties of Energy Minimization tasks and related LP-relaxations. However, it is possible to simplify it in such a way, that it can be used as a stop criterion for LP based iterative algorithms. Its main advantage is that it is exact --- i.e. it never produces a discrete solution that is not globally optimal. In practice it is often able to find the optimal discrete solution even if the used LP-solver does not reach the global optimum of the corresponding LP-relaxation. Consequently, for many Energy Minimization problems it is not necessary to solve the corresponding LP-relaxations exactly.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom