Scene Labeling by Relaxation Operations
The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Abstract
Given a set of objects in a scene whose identifications are ambiguous, it is often possible to use relationships among the objects to reduce or eliminate the ambiguity. A striking example of this approach was given by Waltz [13]. This paper formulates the ambiguity-reduction process in terms of iterated parallel operations (i.e., relaxation operations) performed on an array of (object, identification) data. Several different models of the process are developed, convergence properties of these models are established, and simple examples are given.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Bramble, J. H., & Varga, R. S. (1963) · Mathematics of Computation · doi:10.2307/2003862 · Cited by 4,091
The psychology of computer vision
Rosenfeld, A. (1976) · Artificial Intelligence · doi:10.1016/0004-3702(76)90008-4 · Cited by 2,966
Self-citationClowes, M. B. (1971) · Artificial Intelligence · doi:10.1016/0004-3702(71)90005-1 · Cited by 675
Generating Semantic Descriptions From Drawings of Scenes With Shadows
Waltz, D. L. (1972) · Defense Technical Information Center (DTIC) · Cited by 441
Segmentation processes in visual perception: A cooperative neural model.
Dev, P. (1974) · Cited by 19
Cited by
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
(1988) · Cited by 16,582
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
On the Statistical Analysis of Dirty Pictures
Besag, J. (1986) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1986.tb01412.x · Cited by 4,191
A review on image segmentation techniques
Pal, N. R., & Pal, S. K. (1993) · Pattern Recognition · doi:10.1016/0031-3203(93)90135-j · Cited by 3,708
Fuzzy logic = computing with words
Zadeh, L. A. (1996) · IEEE Transactions on Fuzzy Systems · doi:10.1109/91.493904 · Cited by 3,227
The psychology of computer vision
Rosenfeld, A. (1976) · Artificial Intelligence · doi:10.1016/0004-3702(76)90008-4 · Cited by 2,966
Self-citationFusion, propagation, and structuring in belief networks
Pearl, J. (1986) · Artificial Intelligence · doi:10.1016/0004-3702(86)90072-x · Cited by 2,127
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
Freeman, W. T., Pasztor, E. C., & Carmichael, O. T. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026501619075 · Cited by 1,459
Marr, D., & Poggio, T. (1976) · Science · doi:10.1126/science.968482 · Cited by 1,377
THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION
CONTE, D., FOGGIA, P., SANSONE, C., & VENTO, M. (2004) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001404003228 · Cited by 1,370
Zhang, Z., Deriche, R., Faugeras, O., & Luong, Q.-T. (1995) · Artificial Intelligence · doi:10.1016/0004-3702(95)00022-4 · Cited by 1,367
Techniques for automatically correcting words in text
Kukich, K. (1992) · ACM Computing Surveys · doi:10.1145/146370.146380 · Cited by 1,257
Is vision continuous with cognition?: The case for cognitive impenetrability of visual perception
Pylyshyn, Z. (1999) · Behavioral and Brain Sciences · doi:10.1017/s0140525x99002022 · Cited by 1,243
A survey on image segmentation
Fu, K. S., & Mui, J. K. (1981) · Pattern Recognition · doi:10.1016/0031-3203(81)90028-5 · Cited by 1,203
Yuille, A. L., & Rangarajan, A. (2003) · Neural Computation · doi:10.1162/08997660360581958 · Cited by 1,151
“…Sia −1) gives us an update rule (compare example 1), St+1ia = Stiae (−1/γ ){∑jbCijabStjb+θia}∑ c Stice (−1/γ ){∑jbCijbcStbj+θic} , (3.6) which, by expanding the exponential by a Taylor series, gives the equations for relaxation labeling (Rosenfeld et al., 1976; see Rangarajan, 2000, for details).”
BackgroundMethodInfluentialA 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
“The most successful of these methods use some form of relaxation labeling [6, 7, 8, 9, 10, 11, 12, 13].”
BackgroundZadeh, L. A. (1999) · IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications · doi:10.1109/81.739259 · Cited by 1,039
Zadeh, L. (1999) · Logic, Thought and Action · doi:10.1007/1-4020-3167-x_23 · Cited by 1,026
Readings in Distributed Artificial Intelligence
(1988) · Elsevier eBooks · doi:10.1016/c2013-0-07700-6 · Cited by 986
Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images*
Geman, S., & Geman, D. (1993) · Journal of Applied Statistics · doi:10.1080/02664769300000058 · Cited by 983
Getoor, L., & Diehl, C. P. (2005) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1117454.1117456 · Cited by 973
Historical review of OCR research and development
Mori, S., Suen, C. Y., & Yamamoto, K. (1992) · Proceedings of the IEEE · doi:10.1109/5.156468 · Cited by 892
On the Foundations of Relaxation Labeling Processes
Hummel, R. A., & Zucker, S. W. (1983) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1983.4767390 · Cited by 885
Self-citationStructure from stereo-a review
Dhond, U. R., & Aggarwal, J. K. (1989) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/21.44067 · Cited by 867
Bajcsy, R. (1988) · Proceedings of the IEEE · doi:10.1109/5.5968 · Cited by 830
The Representation, Recognition, and Locating of 3-D Objects
Faugeras, O. D., & Hebert, M. (1986) · The International Journal of Robotics Research · doi:10.1177/027836498600500302 · Cited by 795
A Perspective on Range Finding Techniques for Computer Vision
Jarvis, R. A. (1983) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1983.4767365 · Cited by 782
Müller-Gärtner, H. W., Links, J. M., Prince, J. L., Bryan, R. N., McVeigh, E., Leal, J. P., Davatzikos, C., & Frost, J. J. (1992) · Journal of Cerebral Blood Flow & Metabolism · doi:10.1038/jcbfm.1992.81 · Cited by 756
Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
GEMAN, S., & GEMAN, D. (1987) · Readings in Computer Vision · doi:10.1016/b978-0-08-051581-6.50057-x · Cited by 750
Minutia Cylinder-Code: A New Representation and Matching Technique for Fingerprint Recognition
Cappelli, R., Ferrara, M., & Maltoni, D. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.52 · Cited by 637
Semiring-based constraint satisfaction and optimization
Bistarelli, S., Montanari, U., & Rossi, F. (1997) · Journal of the ACM · doi:10.1145/256303.256306 · Cited by 630
Partial constraint satisfaction
Freuder, E. C., & Wallace, R. J. (1992) · Artificial Intelligence · doi:10.1016/0004-3702(92)90004-h · Cited by 614
Getoor, L. (2006) · Advanced Information and Knowledge Processing · doi:10.1007/1-84628-284-5_7 · Cited by 612
Perceptual Structures and Distributed Motor Control
Arbib, M. A. (1981) · Comprehensive Physiology · doi:10.1002/cphy.cp010233 · Cited by 568
Structural Descriptions and Inexact Matching
Shapiro, L. G., & Haralick, R. M. (1981) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1981.4767144 · Cited by 544
Synthesizing constraint expressions
Freuder, E. C. (1978) · Communications of the ACM · doi:10.1145/359642.359654 · Cited by 538
Structural matching in computer vision using probabilistic relaxation
Christmas, W. J., Kittler, J., & Petrou, M. (1995) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.400565 · Cited by 495
Trace inference, curvature consistency, and curve detection
Parent, P., & Zucker, S. W. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.31445 · Cited by 484
Self-citationPMF: A Stereo Correspondence Algorithm Using a Disparity Gradient Limit
Pollard, S. B., Mayhew, J. E. W., & Frisby, J. P. (1985) · Perception · doi:10.1068/p140449 · Cited by 473
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.791245 · Cited by 470
Classification in Networked Data: A Toolkit and a Univariate Case Study
(2007) · Journal of Machine Learning Research · doi:10.5555/1248659.1248693 · Cited by 452
Web page classification: Features and algorithms
Qi, X., & Davison, B. D. (2009) · ACM Computing Surveys · doi:10.1145/1459352.1459357 · Cited by 435
Kheradmandi, N., & Mehranfar, V. (2022) · Construction and Building Materials · doi:10.1016/j.conbuildmat.2021.126162 · Cited by 426
Matching hierarchical structures using association graphs
Pelillo, M., Siddiqi, K., & Zucker, S. W. (1999) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.809105 · Cited by 394
Self-citationTopic sentiment analysis in twitter: a graph-based hashtag sentiment classification approach
Wang, X., Wei, F., Liu, X., Zhou, M., & Zhang, M. (2011) · Proceedings of the 20th ACM international conference on Information and knowledge management · doi:10.1145/2063576.2063726 · Cited by 393
Kumar, S., & Hebert, M. (2006) · International Journal of Computer Vision · doi:10.1007/s11263-006-7007-9 · Cited by 392
Image Analysis Using Multigrid Relaxation Methods
Terzopoulos, D. (1986) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1986.4767767 · Cited by 370
Edge and line oriented contour detection: State of the art
Papari, G., & Petkov, N. (2011) · Image and Vision Computing · doi:10.1016/j.imavis.2010.08.009 · Cited by 357
Ballard, D. H., Hinton, G. E., & Sejnowski, T. J. (1983) · Nature · doi:10.1038/306021a0 · Cited by 356
Freeman, W. T., & Pasztor, E. C. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.790414 · Cited by 345
A Linear Programming Approach to Max-Sum Problem: A Review
Werner, T. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1036 · Cited by 342
On the Role of Structure in Vision
Witkin, A. P., & Tenenbaum, J. M. (1983) · Human and Machine Vision · doi:10.1016/b978-0-12-084320-6.50022-0 · Cited by 330
Structural matching by discrete relaxation
Wilson, R. C., & Hancock, E. R. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.601251 · Cited by 311
Creating connected representations of cortical gray matter for functional MRI visualization
Teo, P. C., Sapiro, G., & Wandell, B. A. (1997) · IEEE Transactions on Medical Imaging · doi:10.1109/42.650881 · Cited by 310
Functionally Accurate, Cooperative Distributed Systems
Lesser, V. R., & Corkill, D. D. (1981) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1981.4308581 · Cited by 308
A robust automatic crack detection method from noisy concrete surfaces
Fujita, Y., & Hamamoto, Y. (2011) · Machine Vision and Applications · doi:10.1007/s00138-009-0244-5 · Cited by 306
Bayesian modeling of uncertainty in low-level vision
Szeliski, R. (1990) · International Journal of Computer Vision · doi:10.1007/bf00126502 · Cited by 303
Machine interpretation of line drawings
(1987) · Computer Vision, Graphics, and Image Processing · doi:10.1016/s0734-189x(87)80119-6 · Cited by 298
Surfaces from stereo: integrating feature matching, disparity estimation, and contour detection
Hoff, W., & Ahuja, N. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.16709 · Cited by 298
Robust point matching for nonrigid shapes by preserving local neighborhood structures
Zheng, Y., & Doermann, D. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.81 · Cited by 296
A segmentation system based on thresholding
Kohler, R. (1981) · Computer Graphics and Image Processing · doi:10.1016/s0146-664x(81)80015-9 · Cited by 287
Dubois, D., Fargier, H., & Prade, H. (1996) · Applied Intelligence · doi:10.1007/bf00132735 · Cited by 287
Clustering Methodologies in Exploratory Data Analysis
Dubes, R., & Jain, A. K. (1980) · Advances in Computers · doi:10.1016/s0065-2458(08)60034-0 · Cited by 286
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
Selection of scale-invariant parts for object class recognition
Dorko, & Schmid (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238407 · Cited by 282
Partial volume tissue classification of multichannel magnetic resonance images-a mixel model
Choi, H. S., Haynor, D. R., & Kim, Y. (1991) · IEEE Transactions on Medical Imaging · doi:10.1109/42.97590 · Cited by 282
Neurolinguistics must be computational
Arbib, M. A., & Caplan, D. (1979) · Behavioral and Brain Sciences · doi:10.1017/s0140525x0006369x · Cited by 275
The theory and practice of Bayesian image labeling
Chou, P. B., & Brown, C. M. (1990) · International Journal of Computer Vision · doi:10.1007/bf00054995 · Cited by 272
Dreschler, L., & Nagel, H.-H. (1982) · Computer Graphics and Image Processing · doi:10.1016/0146-664x(82)90081-8 · Cited by 271
Shape Matching Using Relaxation Techniques
Davis, L. S. (1979) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1979.4766876 · Cited by 264
Hierarchical Neural Networks for Image Interpretation
Behnke, S. (2003) · Lecture Notes in Computer Science · doi:10.1007/b11963 · Cited by 225
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
Texture segmentation using Voronoi polygons
Tuceryan, M., & Jain, A. K. (1990) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.44407 · Cited by 202
On Copositive Programming and Standard Quadratic Optimization Problems
Bomze, I. M., Dür, M., de Klerk, E., Roos, C., Quist, A. J., & Terlaky, T. (2000) · Journal of Global Optimization · doi:10.1023/a:1026583532263 · Cited by 196
“to solve certain labeling problems arising in the 3-D interpretation of ambiguous line drawings [25, 41, 44 ].”
BackgroundImproving Consistency and Reducing Ambiguity in Stochastic Labeling: An Optimization Approach
Faugeras, O. D., & Berthod, M. (1981) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1981.4767127 · Cited by 181
“VI. APPLICATIONS A. Toy Triangle Example Let us apply our algorithm to the toy triangle example [1].”
BackgroundMethodInfluentialDeformation‐Driven Shape Correspondence
Zhang, H., Sheffer, A., Cohen‐Or, D., Zhou, Q., Van Kaick, O., & Tagliasacchi, A. (2008) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2008.01283.x · Cited by 167
On Standard Quadratic Optimization Problems
Bomze, I. M. (1998) · Journal of Global Optimization · doi:10.1023/a:1008369322970 · Cited by 159
“to solve certain labeling problems arising in the 3-D interpretation of ambiguous line drawings [34, 48, 52].”
Background
Metadata
- Authors
- Rosenfeld, A., Hummel, R. A., & Zucker, S. W.
- Venue
- IEEE Transactions on Systems, Man, and Cybernetics
- Published
- 1976-06
- Volume
- SMC-6
- Issue
- 6
- Pages
- 420-433
- ISSN
- 0018-9472 (ISSN-L)
- 2168-2909
- OpenAlex
- W1979622972
- Cited by
- 1,399
- References
- 5
- FWCI
- 49.68
- Type
- journal article
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.