TY - JOUR

T1 - A sequence-based extension of mean-field annealing using the Forward/Backward algorithm application to image segmentation

AU - Miller, David J.

AU - Zhao, Qi

N1 - Funding Information:
Manuscript received March 11, 2002; revised February 26, 2003. This work was supported by the National Science Foundation under Grant NSF IIS-0082214. The associate editor coordinating the review of this paper and approving it for publication was Prof. Derong Liu.

PY - 2003/10

Y1 - 2003/10

N2 - Optimization based on mean-field theory, including mean-field annealing (MFA), is widely used for discrete optimization (label assignment) problems defined on the pixel sites of an image. One formulation of MFA is via maximum entropy, where one seeks the joint distribution over the (random) assignments subject to an average level of cost. MFA is obtained by assuming the assignments at each pixel are statistically independent, given the observed image. Alternatively, we make the less restrictive assumption of independent row labelings, i.e., unlike MFA, our method allows full expression of dependencies within a row. Stated another way, the independence assumption means that at each step, MFA [like iterated conditional modes (ICM) and highest confidence first (HCF)] optimizes over only one pixel, whereas our method jointly optimizes over an entire row, i.e., our method is less greedy. In principle, an MFA extension could be developed that explicitly re-estimates the row labeling distributions. However, such an approach is, in practice, utterly infeasible. Even so, we can indirectly implement this re-estimation, i.e., at each iteration, we re-estimate quantities that determine the row labeling distributions that would have been obtained had we updated the row labeling distributions directly. Conveniently, these quantities are the a posteriori site probabilities, re-estimable via the well-known Forward/Backward (F/B) Algorithm. Thus, our algorithm, which descends in the ME Lagrangian/free energy, consists of iterative application of F/B to the image rows (columns). At convergence, maximum a posteriori site labeling is performed. Our method was applied to segmentation of both real and synthetic noise-corrupted images. It achieved lower Markov random field model potentials and better segmentations compared with ICM, HCF, and, in high noise, standard MFA. It also improved on Pappas' method when substituted in for the standard Pappas labeling step (ICM).

AB - Optimization based on mean-field theory, including mean-field annealing (MFA), is widely used for discrete optimization (label assignment) problems defined on the pixel sites of an image. One formulation of MFA is via maximum entropy, where one seeks the joint distribution over the (random) assignments subject to an average level of cost. MFA is obtained by assuming the assignments at each pixel are statistically independent, given the observed image. Alternatively, we make the less restrictive assumption of independent row labelings, i.e., unlike MFA, our method allows full expression of dependencies within a row. Stated another way, the independence assumption means that at each step, MFA [like iterated conditional modes (ICM) and highest confidence first (HCF)] optimizes over only one pixel, whereas our method jointly optimizes over an entire row, i.e., our method is less greedy. In principle, an MFA extension could be developed that explicitly re-estimates the row labeling distributions. However, such an approach is, in practice, utterly infeasible. Even so, we can indirectly implement this re-estimation, i.e., at each iteration, we re-estimate quantities that determine the row labeling distributions that would have been obtained had we updated the row labeling distributions directly. Conveniently, these quantities are the a posteriori site probabilities, re-estimable via the well-known Forward/Backward (F/B) Algorithm. Thus, our algorithm, which descends in the ME Lagrangian/free energy, consists of iterative application of F/B to the image rows (columns). At convergence, maximum a posteriori site labeling is performed. Our method was applied to segmentation of both real and synthetic noise-corrupted images. It achieved lower Markov random field model potentials and better segmentations compared with ICM, HCF, and, in high noise, standard MFA. It also improved on Pappas' method when substituted in for the standard Pappas labeling step (ICM).

UR - http://www.scopus.com/inward/record.url?scp=0141954070&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0141954070&partnerID=8YFLogxK

U2 - 10.1109/TSP.2003.816770

DO - 10.1109/TSP.2003.816770

M3 - Article

AN - SCOPUS:0141954070

SN - 1053-587X

VL - 51

SP - 2692

EP - 2705

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

IS - 10

ER -