Compact Relaxations for MAP Inference in Pairwise MRFs with Piecewise Linear Priors
This work addresses computational efficiency for label assignment in computer vision, but it is incremental as it builds on existing LP relaxation methods.
The paper tackles the problem of approximate MAP inference in pairwise MRFs with piecewise linear priors by constructing compact linear programming relaxations, reducing the size complexity from O(L^2) to O(LK) per pairwise clique while maintaining equivalence to standard relaxations.
Label assignment problems with large state spaces are important tasks especially in computer vision. Often the pairwise interaction (or smoothness prior) between labels assigned at adjacent nodes (or pixels) can be described as a function of the label difference. Exact inference in such labeling tasks is still difficult, and therefore approximate inference methods based on a linear programming (LP) relaxation are commonly used in practice. In this work we study how compact linear programs can be constructed for general piecwise linear smoothness priors. The number of unknowns is O(LK) per pairwise clique in terms of the state space size $L$ and the number of linear segments K. This compares to an O(L^2) size complexity of the standard LP relaxation if the piecewise linear structure is ignored. Our compact construction and the standard LP relaxation are equivalent and lead to the same (approximate) label assignment.