What is optimized in tight convex relaxations for multi-label problems

In this work we present a unified view onMarkov random fields and recently proposed continuous tight convex relax-ations for multi-label assignment in the image plane. These relaxations are far less biased towards the grid geometry than Markov random fields. It turns out that the continu-ous methods are non-linear extensions of the local polytope MRF relaxation. In view of this result a better understand-ing of these tight convex relaxations in the discrete setting is obtained. Further, a wider range of optimization methods is now applicable to find a minimizer of the tight formula-tion. We propose two methods to improve the efficiency of minimization. One uses a weaker, but more efficient con-tinuously inspired approach as initialization and gradually refines the energy where it is necessary. The other one refor-mulates the dual energy enabling smooth approximations to be used for efficient optimization. We demonstrate the utility of our proposed minimization schemes in numerical experi-ments. 1