The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Shape indexing using approximate nearest-neighbour search in high-dimensional spaces
Abstract
Shape indexing is a way of making rapid associations between features detected in an image and object models that could have produced them. When model databases are large, the use of high-dimensional features is critical, due to the improved level of discrimination they can provide. Unfortunately, finding the nearest neighbour to a query point rapidly becomes inefficient as the dimensionality of the feature space increases. Past indexing methods have used hash tables for hypothesis recovery, but only in low-dimensional situations. In this paper we show that a new variant of the k-d tree search algorithm makes indexing in higher-dimensional spaces practical. This Best Bin First, or BBF search is an approximate algorithm which finds the nearest neighbour for a large fraction of the queries, and a very close neighbour in the remaining cases. The technique has been integrated into a fully developed recognition system, which is able to detect complex objects in real, cluttered scenes in just a few seconds.
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
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355745 · Cited by 2,813
Perceptual organization and visual recognition
(1985) · Computer Vision, Graphics, and Image Processing · doi:10.1016/0734-189x(85)90041-6 · Cited by 1,022
Perceptual Organization and Visual Recognition
Lowe, D. G. (1985) · The Kluwer International Series in Engineering and Computer Science · doi:10.1007/978-1-4613-2551-2 · Cited by 982
Self-citationFitting parameterized three-dimensional models to images
Lowe, D. G. (1991) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.134043 · Cited by 837
Self-citationGeometric Hashing: A General And Efficient Model-based Recognition Scheme
Lamdan, Y., & Wolfson, H. J. (2005) · [1988 Proceedings] Second International Conference on Computer Vision · doi:10.1109/ccv.1988.589995 · Cited by 775
Structural indexing: efficient 3-D object recognition
Stein, F., & Medioni, G. (1992) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.121785 · Cited by 488
Refinements to nearest-neighbor searching ink-dimensional trees
Sproull, R. F. (1991) · Algorithmica · doi:10.1007/bf01759061 · Cited by 349
Affine invariant model-based object recognition
Lamdan, Y., Schwartz, J. T., & Wolfson, H. J. (1990) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.62047 · Cited by 311
Space and time bounds on indexing 3D models from 2D images
Clemens, D. T., & Jacobs, D. W. (1991) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.99235 · Cited by 131
A Fast k Nearest Neighbor Finding Algorithm Based on the Ordered Partition
Kim, B. S., & Park, S. B. (1986) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1986.4767859 · Cited by 110
Cited by
Distinctive Image Features from Scale-Invariant Keypoints
Lowe, D. G. (2004) · International Journal of Computer Vision · doi:10.1023/b:visi.0000029664.99615.94 · Cited by 55,589
Self-citationObject recognition from local scale-invariant features
Lowe, D. G. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.790410 · Cited by 16,472
Self-citationSURF: Speeded Up Robust Features
Bay, H., Tuytelaars, T., & Van Gool, L. (2006) · Lecture Notes in Computer Science · doi:10.1007/11744023_32 · Cited by 14,955
Automatic Panoramic Image Stitching using Invariant Features
Brown, M., & Lowe, D. G. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-006-0002-3 · Cited by 2,665
Self-citationFAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION
(2009) · Proceedings of the Fourth International Conference on Computer Vision Theory and Applications · doi:10.5220/0001787803310340 · Cited by 2,640
Image Alignment and Stitching: A Tutorial
Szeliski, R. (2007) · Foundations and Trends in Computer Graphics and Vision · doi:10.1561/0600000009 · Cited by 1,593
Scalable Nearest Neighbor Algorithms for High Dimensional Data
Muja, M., & Lowe, D. G. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2321376 · Cited by 1,407
Self-citationShotton, J., Winn, J., Rother, C., & Criminisi, A. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-007-0109-1 · Cited by 1,026
Brown, & Lowe (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238630 · Cited by 934
Kernelized locality-sensitive hashing for scalable image search
Kulis, B., & Grauman, K. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459466 · Cited by 890
Visual simultaneous localization and mapping: a survey
Fuentes-Pacheco, J., Ruiz-Ascencio, J., & Rendón-Mancha, J. M. (2015) · Artificial Intelligence Review · doi:10.1007/s10462-012-9365-8 · Cited by 883
Large-Scale Image Retrieval with Attentive Deep Local Features
Noh, H., Araujo, A., Sim, J., Weyand, T., & Han, B. (2017) · 2017 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.374 · Cited by 847
An Evaluation of Popular Copy-Move Forgery Detection Approaches
Christlein, V., Riess, C., Jordan, J., Riess, C., & Angelopoulou, E. (2012) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2012.2218597 · Cited by 802
Fast pose estimation with parameter-sensitive hashing
Shakhnarovich, Viola, & Darrell (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238424 · Cited by 758
Keypoint recognition using randomized trees
Lepetit, V., & Fua, P. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.188 · Cited by 685
Optimised KD-trees for fast image descriptor matching
Silpa-Anan, C., & Hartley, R. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587638 · Cited by 677
City-Scale Location Recognition
Schindler, G., Brown, M., & Szeliski, R. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383150 · Cited by 626
Scale Invariant Feature Transform
Lindeberg, T. (2012) · Scholarpedia · doi:10.4249/scholarpedia.10491 · Cited by 621
Fast Keypoint Recognition Using Random Ferns
Ozuysal, M., Calonder, M., Lepetit, V., & Fua, P. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.23 · Cited by 595
Billinghurst, M., Clark, A., & Lee, G. (2015) · now publishers, Inc. eBooks · doi:10.1561/9781601989215 · Cited by 529
Monocular Model-Based 3D Tracking of Rigid Objects: A Survey
Lepetit, V., & Fua, P. (2005) · now publishers, Inc. eBooks · doi:10.1561/9781933019536 · Cited by 526
Monocular model-based 3D tracking of rigid objects: a survey
Lepetit, V., & Fua, P. (2005) · Foundations and Trends® in Computer Graphics and Vision · doi:10.1561/0600000001 · Cited by 484
Local feature view clustering for 3D object recognition
Lowe, D. G. (2005) · Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001 · doi:10.1109/cvpr.2001.990541 · Cited by 482
Self-citationEfficient shape matching using shape contexts
Mori, G., Belongie, S., & Malik, J. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.220 · Cited by 458
Detection of Copy-Move Forgery in Digital Images Using SIFT Algorithm
Huang, H., Guo, W., & Zhang, Y. (2008) · 2008 IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application · doi:10.1109/paciia.2008.240 · Cited by 426
Region Duplication Detection Using Image Feature Matching
Pan, X., & Lyu, S. (2010) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2010.2078506 · Cited by 421
Fast Keypoint Recognition in Ten Lines of Code
Ozuysal, M., Fua, P., & Lepetit, V. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383123 · Cited by 415
Unique shape context for 3d data description
Tombari, F., Salti, S., & Di Stefano, L. (2010) · Proceedings of the ACM workshop on 3D object retrieval · doi:10.1145/1877808.1877821 · Cited by 331
Kernelized Locality-Sensitive Hashing
Kulis, B., & Grauman, K. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.219 · Cited by 331
Energy-Based Geometric Multi-model Fitting
Isack, H., & Boykov, Y. (2012) · International Journal of Computer Vision · doi:10.1007/s11263-011-0474-7 · Cited by 318
Implicit Probabilistic Models of Human Motion for Synthesis and Tracking
Sidenbladh, H., Black, M. J., & Sigal, L. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47969-4_52 · Cited by 314
A Partial Intensity Invariant Feature Descriptor for Multimodal Retinal Image Registration
Chen, J., Tian, J., Lee, N., Zheng, J., Smith, R. T., & Laine, A. F. (2010) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2010.2042169 · Cited by 311
HERB: a home exploring robotic butler
Srinivasa, S. S., Ferguson, D., Helfrich, C. J., Berenson, D., Collet, A., Diankov, R., Gallagher, G., Hollinger, G., Kuffner, J., & Weghe, M. V. (2010) · Autonomous Robots · doi:10.1007/s10514-009-9160-9 · Cited by 306
A Linear Time Histogram Metric for Improved SIFT Matching
Pele, O., & Werman, M. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88690-7_37 · Cited by 305
Efficient structure from motion for large-scale UAV images: A review and a comparison of SfM tools
Jiang, S., Jiang, C., & Jiang, W. (2020) · ISPRS Journal of Photogrammetry and Remote Sensing · doi:10.1016/j.isprsjprs.2020.04.016 · Cited by 286
A comprehensive review of current local features for computer vision
Li, J., & Allinson, N. M. (2008) · Neurocomputing · doi:10.1016/j.neucom.2007.11.032 · Cited by 280
Fast image search for learned metrics
Jain, P., Kulis, B., & Grauman, K. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587841 · Cited by 279
Object recognition and full pose registration from a single image for robotic manipulation
Collet, A., Berenson, D., Srinivasa, S. S., & Ferguson, D. (2009) · 2009 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2009.5152739 · Cited by 275
Efficient search for approximate nearest neighbor in high dimensional spaces
Kushilevitz, E., Ostrovsky, R., & Rabani, Y. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276877 · Cited by 259
Fast Similarity Search for Learned Metrics
Kulis, B., Jain, P., & Grauman, K. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.151 · Cited by 256
A survey of methods for 3D histology reconstruction
Pichat, J., Iglesias, J. E., Yousry, T., Ourselin, S., & Modat, M. (2018) · Medical Image Analysis · doi:10.1016/j.media.2018.02.004 · Cited by 207
Grauman, K., & Leibe, B. (2011) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.2200/s00332ed1v01y201103aim011 · Cited by 126
Semantic-Enhanced Differentiable Search Index Inspired by Learning Strategies
Tang, Y., Zhang, R., Guo, J., Chen, J., Zhu, Z., Wang, S., Yin, D., & Cheng, X. (2023) · Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining · doi:10.1145/3580305.3599903 · Cited by 29
Metadata
- Authors
- Beis, J. S., & Lowe, D. G.
- Venue
- Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-22
- Pages
- 1000-1006
- ISSN
- 1063-6919 (ISSN-L)
- OpenAlex
- W2096077837
- Cited by
- 879
- References
- 11
- FWCI
- 7.24
- Type
- conference paper
- 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.