Numer. Math. Theor. Meth. Appl., 6 (2013), pp. 169-198.
Published online: 2013-06
Cited by
- BibTex
- RIS
- TXT
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.
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.