This article is cited in 2 papers

On efficiency of the hierarchical algorithm for searching approximate nearest neighbor in a given set of images

M. M. Lange, S. Ganebnykh, A. M. Lange

Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

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.

Keywords: image; quad pyramidal representation; digital map; nearest neighbor; approximate nearest neighbor; search error; empirical distribution; computational complexity.

Received: 13.12.2016

DOI: 10.14357/19922264170306

Bibliographic databases:

•