Editing Image segmentation (section)

==== Optimization algorithms ====
Each optimization algorithm is an adaptation of models from a variety of fields and they are set apart by their unique cost functions. The common trait of cost functions is to penalize change in pixel value as well as difference in pixel label when compared to labels of neighboring pixels.

===== Iterated conditional modes/gradient descent =====

The [[iterated conditional modes]] (ICM) algorithm tries to reconstruct the ideal labeling scheme by changing the values of each pixel over each iteration and evaluating the energy of the new labeling scheme using the cost function given below,

:<math> \alpha(1-\delta(\ell_i-\ell_{\text{initial }i})+ \beta \Sigma_{q \in N(i)}(1 - \delta(\ell_i,\ell_{q(i)})). </math>

where {{mvar|&alpha;}} is the penalty for change in pixel label and {{mvar|&beta;}} is the penalty for difference in label between
neighboring pixels and chosen pixel. Here <math>N(i)</math> is neighborhood of pixel i and {{mvar|&delta;}} is the Kronecker delta function. A major issue with ICM is that, similar to gradient descent, it has a tendency to rest over local maxima and thus not obtain a globally optimal labeling scheme.

===== Simulated annealing (SA) =====

Derived as an analogue of annealing in metallurgy, [[simulated annealing]] (SA) uses change in pixel label over iterations and estimates the difference in energy of each newly formed graph to the initial data. If the newly formed graph is more profitable, in terms of low energy cost, given by:

: <math>\Delta U = U^\text{new} - U^\text{old}</math>

:<math>
\ell_i =
\begin{cases}
\ell^\text{new}_i, & \text{if } \Delta U \leq 0 ,\\
\ell^\text{new}_i, & \text{if } \Delta U > 0 \text{ and } \delta < e^{-\Delta U / T},
\ell^\text{old}_i
\end{cases}
 </math>

the algorithm selects the newly formed graph. Simulated annealing requires the input of temperature schedules which directly affects the speed of convergence of the system, as well as energy threshold for minimization to occur.

===== Alternative algorithms =====

A range of other methods exist for solving simple as well as higher order MRFs. They include Maximization of Posterior Marginal, Multi-scale MAP estimation,<ref>A. Bouman and M. Shapiro (2002): "A multiscale Random field model for Bayesian image segmentation", IEEE Transactions on Image Processing, pp. 162–177, Vol. 3.</ref> Multiple Resolution segmentation<ref>J. Liu and Y. H. Yang (1994): "[https://ieeexplore.ieee.org/abstract/document/297949/ Multiresolution color image segmentation]", IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 689–700, Vol. 16.</ref> and more. Apart from likelihood estimates, graph-cut using maximum flow<ref>S. Vicente, V. Kolmogorov and C. Rother (2008): "[http://www0.cs.ucl.ac.uk/staff/s.vicente/papers/connectedGC-CVPR08-TR.pdf Graph cut based image segmentation with connectivity priors]", CVPR</ref> and other highly constrained graph based methods<ref>Corso, Z. Tu, and A. Yuille (2008): "MRF Labelling with Graph-Shifts Algorithm", Proceedings of International workshop on combinatorial Image Analysis</ref><ref>B. J. Frey and D. MacKayan (1997): "[http://papers.nips.cc/paper/1467-a-revolution-belief-propagation-in-graphs-with-cycles.pdf A Revolution: Belief propagation in Graphs with Cycles]", Proceedings of Neural Information Processing Systems (NIPS)</ref> exist for solving MRFs.