The DOI matches its Crossref record; 37 of the 37 references it cites were found in a registry or an index.
Recognition of shapes by editing their shock graphs
Abstract
This paper presents a novel framework for the recognition of objects based on their silhouettes. The main idea is to measure the distance between two shapes as the minimum extent of deformation necessary for one shape to match the other. Since the space of deformations is very high-dimensional, three steps are taken to make the search practical: 1) define an equivalence class for shapes based on shock-graph topology, 2) define an equivalence class for deformation paths based on shock-graph transitions, and 3) avoid complexity-increasing deformation paths by moving toward shock-graph degeneracy. Despite these steps, which tremendously reduce the search requirement, there still remain numerous deformation paths to consider. To that end, we employ an edit-distance algorithm for shock graphs that finds the optimal deformation path in polynomial time. The proposed approach gives intuitive correspondences for a variety of shapes and is robust in the presence of a wide range of visual transformations. The recognition rates on two distinct databases of 99 and 216 shapes each indicate highly successful within category matches (100 percent in top three matches), which render the framework potentially usable in a range of shape-based recognition applications.
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
Shape matching and object recognition using shape contexts
Belongie, S., Malik, J., & Puzicha, J. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.993558 · Cited by 6,306
Wiley Series in Probability and Statistics
(2008) · Wiley series in probability and statistics · doi:10.1002/series1345 · Cited by 4,217
The String-to-String Correction Problem
Wagner, R. A., & Fischer, M. J. (1974) · Journal of the ACM · doi:10.1145/321796.321811 · Cited by 3,032
Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
Zhang, K., & Shasha, D. (1989) · SIAM Journal on Computing · doi:10.1137/0218082 · Cited by 1,310
Biological shape and visual science (part I)
Blum, H. (1973) · Journal of Theoretical Biology · doi:10.1016/0022-5193(73)90175-6 · Cited by 1,159
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
The Tree-to-Tree Correction Problem
Tai, K.-C. (1979) · Journal of the ACM · doi:10.1145/322139.322143 · Cited by 865
Shape descriptors for non-rigid shapes with a single closed contour
Latecki, L. J., Lakamper, R., & Eckhardt, T. (2002) · Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No.PR00662) · doi:10.1109/cvpr.2000.855850 · Cited by 833
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
A graph distance metric based on the maximal common subgraph
Bunke, H., & Shearer, K. (1998) · Pattern Recognition Letters · doi:10.1016/s0167-8655(97)00179-7 · Cited by 754
On a relation between graph edit distance and maximum common subgraph
Bunke, H. (1997) · Pattern Recognition Letters · doi:10.1016/s0167-8655(97)00060-3 · Cited by 530
HYPER: A New Approach for the Recognition and Positioning of Two-Dimensional Objects
Ayache, N., & Faugeras, O. D. (1986) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1986.4767751 · Cited by 492
A new algorithm for non-rigid point matching
Chui, H., & Rangarajan, A. (2002) · Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No.PR00662) · doi:10.1109/cvpr.2000.854733 · Cited by 440
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
Sebastian, T. B., Klein, P. N., & Kimia, B. B. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1159951 · Cited by 374
Self-citationKendall, D. G., Carne, T. K., & Barden, D. (1999) · Cited by 365
(1999) · Wiley Series in Probability and Statistics · doi:10.1002/9780470317006 · Cited by 325
Computing the Edit-Distance Between Unrooted Ordered Trees
Klein, P. N. (1998) · Lecture notes in computer science · doi:10.1007/3-540-68530-8_8 · Cited by 288
Self-citationFORMS: A flexible object recognition and modelling system
Zhu, S., & Yuille, A. (1996) · International Journal of Computer Vision · doi:10.1007/bf00208719 · Cited by 277
Symmetry-Based Indexing of Image Databases
Sharvit, D., Chan, J., Tek, H., & Kimia, B. B. (1998) · Journal of Visual Communication and Image Representation · doi:10.1006/jvci.1998.0396 · Cited by 251
Self-citationGdalyahu, Y., & Weinshall, D. (1999) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.817410 · Cited by 236
Belongie, & Malik (2000) · 2000 Proceedings Workshop on Content-based Access of Image and Video Libraries · doi:10.1109/ivl.2000.853834 · Cited by 232
3D object recognition using shape similiarity-based aspect graph
Cyr, C. M., & Kimia, B. B. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937526 · Cited by 218
Self-citationDetermining the similarity of deformable shapes
Basri, R., Costa, L., Geiger, D., & Jacobs, D. (1998) · Vision Research · doi:10.1016/s0042-6989(98)00043-1 · Cited by 217
Tracking points on deformable objects using curvature information
Cohen, I., Ayache, N., & Sulger, P. (1992) · Lecture Notes in Computer Science · doi:10.1007/3-540-55426-2_51 · Cited by 195
Myers, R., Wison, R. C., & Hancock, E. R. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.862201 · Cited by 171
Recognition of shapes by editing shock graphs
(2001) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2001.937602 · Cited by 145
Shape-based nonrigid correspondence with application to heart motion analysis
Tagare, H. D. (1999) · IEEE Transactions on Medical Imaging · doi:10.1109/42.790457 · Cited by 85
A tree-edit-distance algorithm for comparing simple, closed shapes
Klein, P. N., Tirthapura, S., Sharvit, D., & Kimia, B. B. (2000) · doi:10.5555/338219.338628 · Cited by 84
Self-citationComputing approximate tree edit distance using relaxation labeling
Torsello, A., & Hancock, E. R. (2003) · Pattern Recognition Letters · doi:10.1016/s0167-8655(02)00255-6 · Cited by 73
Metric-based shape retrieval in large databases
Sebastian, T. B., & Kimia, B. B. (2003) · Object recognition supported by user interaction for service robots · doi:10.1109/icpr.2002.1047852 · Cited by 58
Self-citationShape matching using edit-distance: an implementation
Klein, P. N., Sebastian, T. B., & Kimia, B. B. (2001) · doi:10.5555/365411.365779 · Cited by 56
Self-citationKaleem 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-citationMatching free trees, maximal cliques, and monotone game dynamics
Pelillo, M. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2002.1046176 · Cited by 50
Alignment-Based Recognition of Shape Outlines
Sebastian, T. B., Klein, P. N., & Kimia, B. B. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45129-3_56 · Cited by 42
Self-citationSymmetry Maps of Free-Form Curve Segments via Wave Propagation
Tek, H., & Kimia, B. B. (2003) · International Journal of Computer Vision · doi:10.1023/a:1023753317008 · Cited by 36
Self-citationSymmetry maps of free-form curve segments via wave propagation
Tek, H., & Kimia, B. B. (1999) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.1999.791243 · Cited by 25
Self-citation
Cited by
Content-based multimedia information retrieval: State of the art and challenges
Lew, M. S., Sebe, N., Djeraba, C., & Jain, R. (2006) · ACM Transactions on Multimedia Computing, Communications, and Applications · doi:10.1145/1126004.1126005 · Cited by 1,528
Shape Classification Using the Inner-Distance
Ling, H., & Jacobs, D. W. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.41 · Cited by 1,069
A survey of graph edit distance
Gao, X., Xiao, B., Tao, D., & Li, X. (2010) · Pattern Analysis and Applications · doi:10.1007/s10044-008-0141-y · Cited by 704
A Survey of Shape Feature Extraction Techniques
Mingqiang, Y., Kidiyo, K., & Joseph, R. (2008) · Pattern Recognition Techniques, Technology and Applications · doi:10.5772/6237 · Cited by 674
A Survey on Shape Correspondence
van Kaick, O., Zhang, H., Hamarneh, G., & Cohen‐Or, D. (2011) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2011.01884.x · Cited by 606
Metadata
- Authors
- Sebastian, T. B., Klein, P. N., & Kimia, B. B.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2004-05
- Volume
- 26
- Issue
- 5
- Pages
- 550-571
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2114766304
- Cited by
- 727
- References
- 37
- FWCI
- 43.48
- 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.