The DOI matches its Crossref record; 53 of the 53 references it cites were found in a registry or an index.
Matching hierarchical structures using association graphs
Abstract
It is well-known that the problem of matching two relational structures can be posed as an equivalent problem of finding a maximal clique in a (derived) "association graph." However, it is not clear how to apply this approach to computer vision problems where the graphs are hierarchically organized, i.e., are trees, since maximal cliques are not constrained to preserve the partial order. We provide a solution to the problem of matching two trees by constructing the association graph using the graph-theoretic concept of connectivity. We prove that, in the new formulation, there is a one-to-one correspondence between maximal cliques and maximal subtree isomorphisms. This allows us to cast the tree matching problem as an indefinite quadratic program using the Motzkin-Straus theorem, and we use "replicator" dynamical systems developed in theoretical biology to solve it. Such continuous solutions to discrete problems are attractive because they can motivate analog and biological implementations. The framework is also extended to the matching of attributed trees by using weighted association graphs. We illustrate the power of the approach by matching articulated and deformed shapes described by shock trees.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
(1979) · Cited by 43,841
The genetical theory of natural selection
Fisher, R. A. (1930) · doi:10.5962/bhl.title.27468 · Cited by 17,617
Harary, F. (1969) · Cited by 10,739
“Neural” computation of decisions in optimization problems
Hopfield, J. J., & Tank, D. W. (1985) · Biological Cybernetics · doi:10.1007/bf00339943 · Cited by 6,031
Ballard, D. H., & Brown, C. M. (1982) · Cited by 5,303
Harary, F. (1969) · doi:10.21236/ad0705364 · Cited by 4,861
An introduction to population genetics theory
Crow, J. F., & Kimura, M. (1970) · Medical Entomology and Zoology · Cited by 4,223
An Introduction to Population Genetics Theory
J., A., Crow, J. F., & Kimura, M. (1971) · Population (French Edition) · doi:10.2307/1529706 · Cited by 3,474
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
(2011) · SpringerReference · doi:10.1007/springerreference_60360 · Cited by 2,855
The design and analysis of spatial data structures
Samet, H. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,380
Representation and recognition of the spatial organization of three-dimensional shapes
Marr, D., & Nishihara, H. K. (1978) · Proceedings of the Royal Society of London. Series B. Biological Sciences · doi:10.1098/rspb.1978.0020 · Cited by 2,158
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,399
Self-citationThe theory of evolution and dynamical systems
Hofbauer, J. (1988) · Cited by 1,301
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_1 · Cited by 1,148
Self-citationA 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
Baum, L. E., & Eagon, J. A. (1967) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1967-11751-8 · Cited by 1,036
The theory of evolution and dynamical systems
Fontana, W. (1989) · Mathematical Biosciences · doi:10.1016/0025-5564(89)90089-8 · Cited by 890
An analogue approach to the travelling salesman problem using an elastic net method
Durbin, R., & Willshaw, D. (1987) · Nature · doi:10.1038/326689a0 · Cited by 797
Shock Graphs and Shape Matching
Siddiqi, K., Shokoufandeh, A., Dickinson, S. J., & Zucker, S. W. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008102926703 · Cited by 756
Self-citationMaxima for Graphs and a New Proof of a Theorem of Turán
Motzkin, T. S., & Straus, E. G. (1965) · Canadian Journal of Mathematics · doi:10.4153/cjm-1965-053-6 · Cited by 710
Kimia, B. B., Tannenbaum, A. R., & Zucker, S. W. (1995) · International Journal of Computer Vision · doi:10.1007/bf01451741 · Cited by 543
Self-citationVan Damme, E. (1994) · European Economic Review · doi:10.1016/0014-2921(94)90121-x · Cited by 419
Recognising and Locating Partially Visible Objects: The Local-Feature-Focus Method
Bolles, R. C., & Cain, R. A. (1983) · Robot Vision · doi:10.1007/978-3-662-09771-7_4 · Cited by 383
Recognizing and Locating Partially Visible Objects: The Local-Feature-Focus Method
Bolles, R. C., & Cain, R. A. (1982) · The International Journal of Robotics Research · doi:10.1177/027836498200100304 · Cited by 382
Comparing multiple RNA secondary structures using tree comparisons
Shapiro, B. A., & Zhang, K. (1990) · Bioinformatics · doi:10.1093/bioinformatics/6.4.309 · Cited by 319
Application of statistical mechanics to NP-complete problems in combinatorial optimisation
Fu, Y., & Anderson, P. W. (1986) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/19/9/033 · Cited by 317
FORMS: A flexible object recognition and modelling system
Zhu, S., & Yuille, A. (1996) · International Journal of Computer Vision · doi:10.1007/bf00208719 · Cited by 277
Replicator Equations, Maximal Cliques, and Graph Isomorphism
Pelillo, M. (1999) · Neural Computation · doi:10.1162/089976699300016034 · Cited by 166
Self-citationOn Standard Quadratic Optimization Problems
Bomze, I. M. (1998) · Journal of Global Optimization · doi:10.1023/a:1008369322970 · Cited by 159
Continuous Characterizations of the Maximum Clique Problem
Gibbons, L., Hearn, D. W., Pardalos, P. M., & Ramana, M. V. (1997) · Mathematics of Operations Research · doi:10.1287/moor.22.3.754 · Cited by 155
A system for approximate tree matching
Wang, J. T.-L., Zhang, K., Jeong, K., & Shasha, D. E. (1994) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.298173 · Cited by 152
The invisible hand algorithm: Solving the assignment problem with statistical physics
Kosowsky, J. J., & Yuille, A. (1994) · Neural Networks · doi:10.1016/0893-6080(94)90081-7 · Cited by 151
Toward a computational theory of shape: An overview
Kimia, B. B., Tannenbaum, A., & Zucker, S. W. (1990) · Lecture notes in computer science · doi:10.1007/bfb0014889 · Cited by 147
Self-citationA versatile system for computer-controlled assembly
Ambler, A. P., Barrow, H. G., Brown, C. M., Burstall, R. M., & Popplestone, R. J. (1975) · Artificial Intelligence · doi:10.1016/0004-3702(75)90006-5 · Cited by 128
A versatile computer-controlled assembly system
Ambler, A. P., Barrow, H. G., Brown, C. M., Burstall, R. H., & Popplestone, R. J. (1973) · International Joint Conference on Artificial Intelligence · Cited by 123
Exact and approximate algorithms for unordered tree matching
Shasha, D. E., Wang, J. T.-L., Zhang, K., & Shih, F. Y. (1994) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/21.286387 · Cited by 116
Dynamics of games and genes: Discrete versus continuous time
Losert, V., & Akin, E. (1983) · Journal of Mathematical Biology · doi:10.1007/bf00305762 · Cited by 113
Hierarchical decomposition and axial shape description
Rom, H., & Medioni, G. G. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.254054 · Cited by 113
Evolution equations for continuous-scale morphology
Brockett, R. W., & Maragos, P. A. (1992) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.1992.226260 · Cited by 108
Approximating the maximum weight clique using replicator dynamics
Stix, V., Pelillo, M., & Bomze, I. M. (2000) · IEEE Transactions on Neural Networks · doi:10.1109/72.883403 · Cited by 107
Self-citationThe Dynamics of Nonlinear Relaxation Labeling Processes
Pelillo, M. (1997) · Journal of Mathematical Imaging and Vision · doi:10.1023/a:1008255111261 · Cited by 106
Self-citationNeural Networks for Optimization Problems with Inequality Constraints: The Knapsack Problem
Ohlsson, M., Peterson, C., & Söderberg, B. (1993) · Neural Computation · doi:10.1162/neco.1993.5.2.331 · Cited by 95
Approximating maximum clique with a Hopfield network
Jagota, A. (1995) · IEEE Transactions on Neural Networks · doi:10.1109/72.377977 · Cited by 92
Hanson, A. R., Riseman, E. M., & Nagin, P. A. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767510 · Cited by 56
Miller, D. A., & Zucker, S. W. (1999) · Neural Computation · doi:10.1162/089976699300016782 · Cited by 54
Self-citationA Tree-Matching Algorithm Based on Node Splitting and Merging
Lu, S.-Y. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767511 · Cited by 54
Kaleem Siddiqi, A., Kimia, B. B., Tannenbaum, A., & Zucker, S. W. (1999) · Image and Vision Computing · doi:10.1016/s0262-8856(98)00130-9 · Cited by 52
Self-citationContinuous Approaches to Discrete Optimization Problems
Pardalos, P. M. (1996) · Springer eBooks · doi:10.1007/978-1-4899-0289-4_22 · Cited by 51
A Lagrangian relaxation network for graph matching
Rangarajan, A., & Mjolsness, E. (1996) · IEEE Transactions on Neural Networks · doi:10.1109/72.548165 · Cited by 49
Continuous Approaches for Solving Discrete Optimization Problems
Pardalos, P. M., Prokopyev, O. A., & Busygin, S. (2006) · Kluwer Academic Publishers eBooks · doi:10.1007/0-387-32942-0_2 · Cited by 47
A unifying framework for relational structure matching
Pelillo, M. (2002) · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · doi:10.1109/icpr.1998.711944 · Cited by 37
Self-citationEfficient Simplex-Like Methods for Equilibria of Nonsymmetric Analog Networks
Miller, D. A., & Zucker, S. W. (1992) · Neural Computation · doi:10.1162/neco.1992.4.2.167 · Cited by 28
Self-citation
Cited by
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
Shock Graphs and Shape Matching
Siddiqi, K., Shokoufandeh, A., Dickinson, S. J., & Zucker, S. W. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008102926703 · Cited by 756
Self-citationRecognition of shapes by editing their shock graphs
Sebastian, T. B., Klein, P. N., & Kimia, B. B. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1273924 · Cited by 727
Maximum common subgraph isomorphism algorithms for the matching of chemical structures
Raymond, J. W., & Willett, P. (2002) · Journal of Computer-Aided Molecular Design · doi:10.1023/a:1021271615909 · Cited by 424
50 Years of object recognition: Directions forward
Andreopoulos, A., & Tsotsos, J. K. (2013) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2013.04.005 · Cited by 347
Metadata
- Authors
- Pelillo, M., Siddiqi, K., & Zucker, S. W.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 1999
- Volume
- 21
- Issue
- 11
- Pages
- 1105-1120
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2118782734
- Cited by
- 394
- References
- 53
- FWCI
- 30.37
- 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.