A continuous relaxation labeling algorithm for Markov random fields

A probabilistic relaxation algorithm is described for labelling the vertices of a Markov random field (MRF) defined on a finite graph. The proposed algorithm has two features which make it attractive. First, the multilinear structure of the relaxation operator allows simple, necessary, and sufficient convergence conditions to be derived. The second advantage is local optimality. Given a class of MRF’s indexed by a parameter c, such that when c=0 the vertices are independent, it is shown that the estimates of the a posteriori probabilities generated by the algorithm differ from the true values by terms that are at least second order in c.