Informatics and Applications
2017, Volume 11, Issue 3, pp 51-59
ON EFFICIENCY OF THE HIERARCHICAL ALGORITHM FOR SEARCHING APPROXIMATE NEAREST NEIGHBOR IN A GIVEN SET OF IMAGES
- M.M. Lange
- S.N. Ganebnykh
- A.M. Lange
Abstract
The efficiency of the hierarchical algorithm for searching approximate nearest neighbor in a given set of images subject to an unwarranted error about the nearest image is investigated. The algorithm uses a space of quad pyramidal image representations as well as a guided search strategy in successive representation levels of increasing resolution. The efficiency is studied in terms of both an empirical distribution of search errors and computational complexity of the hierarchical algorithm relative to the exhaustive search. The above characteristics are obtained for two applications, namely, search for approximate nearest image in a set of hand-written digits from the MNIST data base and gridding a given noisy image in an aerospace digital map from the Google maps network service.
[+] References (15)
- Datta, R., D. Joshi, J. Li, and J. Wang. 2008. Image retrieval: Ideas, influences, and trends of the new age. ACM Comput. Surv. 40(2):1—60.
- Friedman, J., J. Bentley, and R. Finkel. 1977. An algorithm for finding best matches in logarithmic expected time. ACMT. Math. Software 3(3):209—226.
- Cleary, J. Analysis of an algorithm for finding nearest neighbors in Euclidean space. 1979. ACM T. Math. Software 5(2):183—192.
- Soleymani, M., andS. Morgera. 1987. An efficient nearest neighbor search method. IEEE T. Commun. 35(6):677— 679.
- Arya, S., D. Mount, N. Netanyahu, R. Silverman, and A. Wu. 1998. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. ACM 45(6):891—923.
- Andoni, À., and P. Indyk. 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1):117—122.
- Lange, M. M., S. N. Ganebnykh, andA. M. Lange. 2016. Algorithm of approximate search for the nearest digital array in a hierarchical data set. Machine Learning Data Analysis 2(1):6—16.
- Rosenfeld, A. 1980. Quadtrees and pyramids for pattern recognition and image analysis. 5th Conference (International) on Pattern Recognition Proceedings. 802—811.
- Jackins, C., and S. Tanimoto. 1983. Quadtrees, octtrees, and K-trees: A generalized approach to recursive decomposition of Euclidean space. IEEE T. Pattern Anal. 5(5):533—539.
- Samet, H. 1984. The quadtree and related hierarchical data structures. Comput. Surv. 16(2):187—260.
- Lange, M.M., and N.A. Novikov. 2012. Predstavlenie dannykh s mnogourovnevym razresheniem dlya bystroy koordinatnoy privyazki izobrazheniy [Multiresolution data representation for fast image gridding]. Sb. tr. nauch.- tekhnich. konf. “Tekhnicheskoe zrenie v sistemakh upravleniya [Scientific-Technical Conference “Computing Vision in Control Systems” Proceedings]. Moscow: IKI RAN. 242-249.
- MNIST database. Available at: http://yann.lecun.com/ exdb/mnist/index.html (accessed January 10, 2017).
- Network service Google Maps. Available at: http:// www.maps.google.com (accessed January 10, 2017).
- Cormen, T., C. Leiserson, R. Rivest, and C. Stein. 2009. Introduction to algorithms. 3rd ed. MIT Press. 1312 p.
- Algorithm for searching approximate nearest neighbor. Available at: http://sourceforge.net/projects/edivis/ files/ (accessed January 10, 2017).
[+] About this article
Title
ON EFFICIENCY OF THE HIERARCHICAL ALGORITHM FOR SEARCHING APPROXIMATE NEAREST NEIGHBOR IN A GIVEN SET OF IMAGES
Journal
Informatics and Applications
2017, Volume 11, Issue 3, pp 51-59
Cover Date
2017-09-30
DOI
10.14357/19922264170306
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
image; quad pyramidal representation; digital map; nearest neighbor; approximate nearest neighbor; search error; empirical distribution; computational complexity
Authors
M.M. Lange  , S.N. Ganebnykh , and A.M. Lange
Author Affiliations
Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|