On the Foundations of Relaxation Labeling Processes
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.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
Optimization by Vector Space Methods
(1970) · Students Quarterly Journal · doi:10.1049/sqj.1970.0088 · Cited by 6,024 · see citing works
An Introduction to Variational Inequalities and Their Applications
Kinderlehrer, D. S., & Stampacchia, G. (2000) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719451 · Cited by 4,499 · see citing works
The psychology of computer vision
Rosenfeld, A. (1976) · Artificial Intelligence · doi:10.1016/0004-3702(76)90008-4 · Cited by 3,015 · see citing works
The Interpretation of Visual Motion
Ullman, S. (1979) · The MIT Press eBooks · doi:10.7551/mitpress/3877.001.0001 · Cited by 1,648 · see citing works
Scene Labeling by Relaxation Operations
Rosenfeld, A., Hummel, R. A., & Zucker, S. W. (1976) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1976.4309519 · Cited by 1,402 · see citing works
Self-citationUnderstanding Line drawings of Scenes with Shadows
Waltz, D. L. (1975) · Cited by 917 · see citing works
Dynamical Systems: Stability Theory and Applications
Bhatia, N. P., & Szegö, G. P. (1967) · Lecture notes in mathematics · doi:10.1007/bfb0080630 · Cited by 318 · see citing works
The Consistent Labeling Problem: Part I
Haralick, R. M., & Shapiro, L. G. (1979) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1979.4766903 · Cited by 285 · see citing works
An Application of Relaxation Labeling to Line and Curve Enhancement
Zucker, Hummel, & Rosenfeld (1977) · IEEE Transactions on Computers · doi:10.1109/tc.1977.1674848 · Cited by 220 · see citing works
A New Probabilistic Relaxation Scheme
Peleg, B. (1980) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1980.4767035 · Cited by 185 · see citing works
Improving Consistency and Reducing Ambiguity in Stochastic Labeling: An Optimization Approach
Faugeras, O. D., & Berthod, M.-A. (1981) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1981.4767127 · Cited by 181 · see citing works
Cooperating processes for low-level vision: A survey
Davis, L. S., & Rosenfeld, A. (1981) · Artificial Intelligence · doi:10.1016/0004-3702(81)90026-6 · Cited by 154 · see citing works
Relaxation and constrained optimization by local processes
Ullman, S. (1979) · Computer Graphics and Image Processing · doi:10.1016/0146-664x(79)90045-5 · Cited by 123 · see citing works
Programming by Refinement, as Exemplified by the SETL Representation Sublanguage
Dewar, R., Grand, A., Liu, S.-C., et al. (1979) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357062.357064 · Cited by 107 · see citing works
Relaxation and its Role in Vision
Hinton, G. E. (1977) · ERA · Cited by 64 · see citing works
Studies in Linear and Non-Linear Programming
Krickeberg, K., Arrow, K. J., Hurwicz, L., et al. (1960) · Econometrica · doi:10.2307/1907579 · Cited by 45 · see citing works
Using Context in the Global Recognition of a Set of Objects: An Optimization Approach.
Berthod, M.-A., & Faugeras, O. D. (1980) · IFIP Congress · Cited by 11 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949 · see citing works
DeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123 · see citing works
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988 · see citing works
Collective Classification in Network Data
Sen, P., Namata, G., Bilgic, M., Getoor, L., Gallagher, B., & Eliassi‐Rad, T. (2008) · AI Magazine · doi:10.1609/aimag.v29i3.2157 · Cited by 3,293 · see citing works
A graduated assignment algorithm for graph matching
Gold, S., & Rangarajan, A. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.491619 · Cited by 1,090 · see citing works
Optical flow using spatiotemporal filters
Heeger, D. J. (1988) · International Journal of Computer Vision · doi:10.1007/bf00133568 · Cited by 534 · see citing works
Ontology Matching: A Machine Learning Approach
Doan, A., Madhavan, J., Domingos, P., & Halevy, A. (2004) · Handbook on Ontologies · doi:10.1007/978-3-540-24750-0_19 · Cited by 477 · see citing works
- Authors
- Hummel, R. A., & Zucker, S. W.
- Affiliations
- Courant Institute of Mathematical Sciences (US)
- McGill University (CA)
- ORCID
- Zucker, Steven W.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 1983-05
- Volume
- PAMI-5
- Issue
- 3
- Pages
- 267-287
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2107792892
- Cited by
- 885
- References
- 17
- Citations by year
- 2026: 2 · 2025: 3 · 2024: 2 · 2023: 4 · 2022: 6 · 2021: 5 · 2020: 7 · 2019: 7 · 2018: 7 · 2017: 11 · 2016: 8 · 2015: 10 · 2014: 18 · 2013: 10 · 2012: 13
- FWCI
- 55.07
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- PubMed (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Medical Image Segmentation Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Digital Image Processing Techniques
- Physical Sciences › Computer Science › Computer Networks and Communications › Constraint Satisfaction and Optimization
- Keywords
- relaxation labeling, label assignment, constraint satisfaction, variational inequalities, relaxation operator, local convergence, noise reduction, ambiguity reduction
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
