Year:    2013

Numerical Mathematics: Theory, Methods and Applications, Vol. 6 (2013), Iss. 1 : pp. 169–198

Abstract

One of the classical optimization models for image segmentation is the well known Markov Random Fields (MRF) model. This model is a discrete optimization problem, which is shown here to formulate many continuous models used in image segmentation. In spite of the presence of MRF in the literature, the dominant perception has been that the model is not effective for image segmentation. We show here that the reason 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 methods cannot 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 the output thus obscuring what would be ideal choices of parameters and functions which are to be selected by users in each particular application context.
We describe here how MRF can model and solve efficiently several known continuous models for image segmentation and describe briefly a very efficient polynomial time algorithm, which is provably fastest possible, to solve optimally the MRF problem. The MRF algorithm is enhanced here compared to the algorithm in Hochbaum (2001) by allowing the set of assigned labels to be any discrete set. Other enhancements include dynamic features that permit adjustments to the input parameters and solves optimally for these changes with minimal computation time. Several new theoretical results on the properties of the algorithm are proved here and are demonstrated for images in the context of medical and biological imaging. An interactive implementation tool for MRF is described, and its performance and flexibility in practice are demonstrated via computational experiments.
We conclude that many continuous models common in image segmentation have discrete analogs to various special cases of MRF and as such are solved optimally and efficiently, 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 to a local minimum.