A survey and comparison of discrete and continuous multi-label optimization approaches for the Potts model

We present a survey and a comparison of a variety of algorithms that have been proposed over the years to minimize multi-label optimization problems based on the Potts model. Discrete approaches based on Markov Random Fields as well as continuous optimization approaches based on partial differential equations can be applied to the task. In contrast to the case of binary labeling, the multi-label problem is known to be NP hard and thus one can only expect near-optimal solutions. In this paper, we carry out a theoretical comparison and an experimental analysis of existing approaches with respect to accuracy, optimality and runtime, aimed at bringing out the advantages and short-comings of the respective algorithms. Systematic quantitative comparison is done on the Graz interactive image segmentation benchmark. This paper thereby generalizes a previous experimental comparison (Klodt et al. 2008) from the binary to the multi-label case.