Gentle ICM energy minimization for Markov random fields with smoothness-based priors

Coordinate descent, also known as iterated conditional mode (ICM) algorithm, is a simple approach for minimizing the energy defined by a Markov random field. Unfortunately, the ICM is very sensitive to the initial values and usually only finds a poor local minimum of the energy. A few modifications of the ICM algorithm are discussed here that ensure a more 'gentle' descent during the first iterations of the algorithm and that lead to substantial performance improvements. It is demonstrated that the modified ICM can be competitive to other optimization algorithms on a set of vision problems such as stereo depth estimation, image segmentation, image denoising and inpainting.