An Inference Algorithm for Multi-Label MRF-MAP Problems with Clique Size 100

摘要

In this paper, we propose an algorithm for optimal solutions to submodular higher-order multi-label MRF-MAP energy functions which can handle practical computer vision problems with up to 16 labels and cliques of size 100. The algorithm uses a transformation which transforms a multi-label problem to a 2-label problem on a much larger clique. Earlier algorithms based on this transformation could not handle problems larger than 16 labels on cliques of size 4. The proposed algorithm optimizes the resultant 2-label problem using the submodular polyhedron based Min Norm Point algorithm. The task is challenging because the state space of the transformed problem has a very large number of invalid states. For polyhedral based algorithms the presence of invalid states poses a challenge as apart from numerical instability, the transformation also increases the dimension of the polyhedral space making the straightforward use of known algorithms impractical. The approach reported in this paper allows us to bypass the large costs associated with invalid configurations, resulting in a stable, practical, optimal and efficient inference algorithm that, in our experiments, gives high-quality outputs on problems like pixel-wise object segmentation and stereo matching.