DocumentCode :
253794
Title :
Maximum Persistency in Energy Minimization
Author :
Shekhovtsov, Alexander
Author_Institution :
Graz Univ. of Technol., Graz, Austria
fYear :
2014
fDate :
23-28 June 2014
Firstpage :
1162
Lastpage :
1169
Abstract :
We consider discrete pairwise energy minimization problem (weighted constraint satisfaction, max-sum labeling) and methods that identify a globally optimal partial assignment of variables. When finding a complete optimal assignment is intractable, determining optimal values for a part of variables is an interesting possibility. Existing methods are based on different sufficient conditions. We propose a new sufficient condition for partial optimality which is: (1) verifiable in polynomial time (2) invariant to reparametrization of the problem and permutation of labels and (3) includes many existing sufficient conditions as special cases. %It is derived by using a relaxation technique coherent with the relaxation for energy minimization. We pose the problem of finding the maximum optimal partial assignment identifiable by the new sufficient condition. A polynomial method is proposed which is guaranteed to assign same or larger part of variables %find the same or larger part of optimal assignment than several existing approaches. The core of the method is a specially constructed linear program that identifies persistent assignments in an arbitrary multi-label setting.
Keywords :
computational complexity; graph theory; minimisation; polynomials; globally optimal partial assignment; max-sum labeling; pairwise energy minimization problem; partial optimality; persistent assignments identification; polynomial method; polynomial time; relaxation technique; reparametrization invariance; sufficient conditions; variables assignment; weighted constraint satisfaction; Complexity theory; Conferences; Labeling; Minimization; Polynomials; Programming; Vectors; energy minimization; max-sum; partial optimality; persistency; wcsp;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Vision and Pattern Recognition (CVPR), 2014 IEEE Conference on
Conference_Location :
Columbus, OH
Type :
conf
DOI :
10.1109/CVPR.2014.152
Filename :
6909548
Link To Document :
بازگشت