Multi-Label Markov Random Fields as an Efficient and Effective Tool for Image Segmentation,Total Variations and Regularization

One of the classical optimization models for image segmentation is the wellknown Markov Random Fields (MRF) model. This model is a discrete optimizationproblem, which is shown here to formulate many continuous models used in imagesegmentation. In spite of the presence of MRF in the literature, the dominant perceptionhas been that the model is not effective for image segmentation. We show here that thereason for the non-effectiveness is due to the lack of access to the optimal solution.Instead of solving optimally, heuristics have been engaged. Those heuristic methodscannot guarantee the quality of the solution nor the running time of the algorithm.Worse still, heuristics do not link directly the input functions and parameters to theoutput thus obscuring what would be ideal choices of parameters and functions whichare to be selected by users in each particular application context.We describe here how MRF can model and solve efficiently several known continuousmodels for image segmentation and describe briefly a very efficient polynomial timealgorithm, which is provably fastest possible, to solve optimally the MRF problem. TheMRF algorithm is enhanced here compared to the algorithm in Hochbaum (2001) byallowing the set of assigned labels to be any discrete set. Other enhancements includedynamic features that permit adjustments to the input parameters and solves optimallyfor these changes with minimal computation time. Several new theoretical results onthe properties of the algorithm are proved here and are demonstrated for images inthe context of medical and biological imaging. An interactive implementation tool forMRF is described, and its performance and flexibility in practice are demonstrated viacomputational experiments.We conclude that many continuous models common in image segmentation havediscrete analogs to various special cases of MRF and as such are solved optimally andefficiently, rather than with the use of continuous techniques, such as PDE methods, which restrict the type of functions used and furthermore, can only guarantee convergence toa local minimum.