Abstract
Truncated convex models (TCM) are a special case of
pairwise random fields that have been widely used in computer vision. However, by restricting the order of the potentials to be at most two, they fail to capture useful image statistics. We propose a natural generalization of TCM
to high-order random fields, which we call truncated maxof-convex models (TMCM). The energy function of TMCM
consists of two types of potentials: (i) unary potential,
which has no restriction on its form; and (ii) clique potential, which is the sum of the m largest truncated convex distances over all label pairs in a clique. The use of
a convex distance function encourages smoothness, while
truncation permits discontinuities in the labeling. By using m > 1, TMCM provides robustness towards errors in
the definition of the cliques. To minimize the energy function of a TMCM over all possible labelings, we design an
efficient st-MINCUT based range expansion algorithm. We
prove the accuracy of our algorithm by establishing strong
multiplicative bounds for several special cases of interest.
Using standard real data sets, we demonstrate the benefit
of our high-order TMCM over pairwise TCM, as well as
the benefit of our range expansion algorithm over other stMINCUT based approaches