On the Foundations of Relaxation Labeling Processes
- 1 May 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. PAMI-5 (3), 267-287
- https://doi.org/10.1109/tpami.1983.4767390
Abstract
A large class of problems can be formulated in terms of the assignment of labels to objects. Frequently, processes are needed which reduce ambiguity and noise, and select the best label among several possible choices. Relaxation labeling processes are just such a class of algorithms. They are based on the parallel use of local constraints between labels. This paper develops a theory to characterize the goal of relaxation labeling. The theory is founded on a definition of con-sistency in labelings, extending the notion of constraint satisfaction. In certain restricted circumstances, an explicit functional exists that can be maximized to guide the search for consistent labelings. This functional is used to derive a new relaxation labeling operator. When the restrictions are not satisfied, the theory relies on variational cal-culus. It is shown that the problem of finding consistent labelings is equivalent to solving a variational inequality. A procedure nearly identical to the relaxation operator derived under restricted circum-stances serves in the more general setting. Further, a local convergence result is established for this operator. The standard relaxation labeling formulas are shown to approximate our new operator, which leads us to conjecture that successful applications of the standard methods are explainable by the theory developed here. Observations about con-vergence and generalizations to higher order compatibility relations are described.This publication has 10 references indexed in Scilit:
- Cooperating processes for low-level vision: A surveyArtificial Intelligence, 1981
- Improving Consistency and Reducing Ambiguity in Stochastic Labeling: An Optimization ApproachIEEE Transactions on Pattern Analysis and Machine Intelligence, 1981
- A New Probabilistic Relaxation SchemeIEEE Transactions on Pattern Analysis and Machine Intelligence, 1980
- Relaxation and constrained optimization by local processesComputer Graphics and Image Processing, 1979
- The Consistent Labeling Problem: Part IIEEE Transactions on Pattern Analysis and Machine Intelligence, 1979
- Programming by Refinement, as Exemplified by the SETL Representation SublanguageACM Transactions on Programming Languages and Systems, 1979
- The Interpretation of Visual MotionPublished by MIT Press ,1979
- An Application of Relaxation Labeling to Line and Curve EnhancementIEEE Transactions on Computers, 1977
- Scene Labeling by Relaxation OperationsIEEE Transactions on Systems, Man, and Cybernetics, 1976
- Dynamical Systems: Stability Theory and ApplicationsLecture Notes in Mathematics, 1967