On the dynamics of relaxation labeling processes

Relaxation labeling processes are parallel iterative procedures heuristically developed to solve certain constraint satisfaction problems, which have long become a standard technique in computer vision and pattern recognition. This paper shows that, despite its heuristic nature, relaxation labeling is indeed intimately related with a well-established theory of consistency. It is shown that, when a certain symmetry condition is met, the algorithm possesses a Liapunov function which turns out to be (the negative of) a well-known consistency measure. This follows almost immediately from a powerful result of Baum and Eagon developed in the context of Markov chain theory. Moreover, it is seen that most of the essential properties of the model are retained when the symmetry restriction is relaxed. The analysis provided in this paper contributes to strengthen the recognized relationship between relaxation labeling and certain neural network models and permits to point out some interesting differences. Moreover, it paves the way for a number of novel applications of relaxation processes