The Potts Model with Different Piecewise Constant Representations and Fast Algorithms: A Survey

Markov random fields (MRF) and the Potts model have many applications in different areas. Especially, conditional random fields (CRF) and Potts model have been used in connection with classifiers. In this work, we focus on the Potts model and use image segmentation and data classification as examples to show some new techniques and fast algorithms for this model. We survey different piecewise constant representation techniques. Many of these representations can be interpreted as min-cut and max-flow problems on some special graphs. We will concentrate especially on the continuous setting and formulate continuous min-cut and max-flow models. When the min-cut/max-flow models are discretized, they give corresponding discrete min-cut/max-flow models on grids. Using these connections, we are able to turn the non-convex Potts model into some simple convex minimization problems with solutions that can be obtained by properly designed fast algorithms. In this survey, we will start by introducing some widely studied variational segmentation models and the classical level-set approaches to solve them. Then, we will describe three different piecewise constant representations for the general Potts model and their corresponding convex relaxations and fast algorithms. In the end, we will also generalize the method to a graph setting for high-dimensional data classifications. This survey presents the different techniques and algorithms in an integrated and self-contained manner.