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 · cited 2×
“Sharvit et al. [39] and Kimia et al. [20] found the optimal pairwise assignment of shock graph nodes using the graduated assignment approach [17], where the similarity between each pair of nodes is defined based on the geometry of the shock segments linking them.”
BackgroundMethodThe 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
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
Skeleton Pruning by Contour Partitioning with Discrete Curve Evolution
Bai, X., Latecki, L., & Liu, W.-Y. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.59 · Cited by 425
A survey of content based 3D shape retrieval methods
Tangelder, J. W. H., & Veltkamp, R. C. (2004) · Proceedings Shape Modeling Applications, 2004. · doi:10.1109/smi.2004.1314502 · Cited by 409
A Stochastic Grammar of Images
Zhu, S.-C., & Mumford, D. (2006) · now publishers, Inc. eBooks · doi:10.1561/9781601980618 · Cited by 395
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
“More recent work has expanded the scope of graph based algorithms using shock graphs [181], [210], [211], [212], [213], [214], [215].”
BackgroundPath Similarity Skeleton Graph Matching
Bai, X., & Latecki, L. J. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.70769 · Cited by 343
GRAPH MATCHING AND LEARNING IN PATTERN RECOGNITION IN THE LAST 10 YEARS
FOGGIA, P., PERCANNELLA, G., & VENTO, M. (2014) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001414500013 · Cited by 337
A Stochastic Grammar of Images
Zhu, S.-C., & Mumford, D. (2006) · Foundations and Trends® in Computer Graphics and Vision · doi:10.1561/0600000018 · Cited by 332
From Images to Shape Models for Object Detection
Ferrari, V., Jurie, F., & Schmid, C. (2010) · International Journal of Computer Vision · doi:10.1007/s11263-009-0270-9 · Cited by 295
Learning Context-Sensitive Shape Similarity by Graph Transduction
Bai, X., Yang, X., Latecki, L. J., Liu, W., & Tu, Z. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.85 · Cited by 280
Shape retrieval using triangle-area representation and dynamic space warping
Alajlan, N., El Rube, I., Kamel, M. S., & Freeman, G. (2007) · Pattern Recognition · doi:10.1016/j.patcog.2006.12.005 · Cited by 279
Retrieving articulated 3-D models using medial surfaces
Siddiqi, K., Zhang, J., Macrini, D., Shokoufandeh, A., Bouix, S., & Dickinson, S. (2008) · Machine Vision and Applications · doi:10.1007/s00138-007-0097-8 · Cited by 256
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.