Data structures such as -D trees and hierarchical -means trees perform very well in approximate nearest neighbour matching, but are only marginally more effective than linear search when performing exact matching in high-dimensional image descriptor data. This paper presents several improvements to linear search that allows it to outperform existing methods and recommends two approaches to exact matching. The first method reduces the number of operations by evaluating the distance measure in order of significance of the query dimensions and terminating when the partial distance exceeds the search threshold. This method does not require preprocessing and significantly outperforms existing methods. The second method improves query speed further by presorting the data using a data structure called -D sort. The order information is used as a priority queue to reduce the time taken to find the exact match and to restrict the range of data searched. Construction of the -D sort structure is very simple to implement, does not require any parameter tuning, and requires significantly less time than the best-performing tree structure, and data can be added to the structure relatively efficiently. 1. Introduction The nearest neighbour matching ( NN) problem is encountered in many applications of computer science. It is the problem of finding the points in a database nearest to a given query point. The complexity of a simple linear search is proportional to , where is the number of database entries and is the number of data dimensions. Many attempts have been made to reduce the search time by implementing data storage and indexing structures so that the minimum number of data points has to be compared to the query point. Unfortunately, these methods are only effective in low dimensions or when using approximate nearest neighbour matching [1, 2]. Where an exact solution is required in dimensions greater than 20, linear search is only a fraction slower than the best existing search structure. This paper proposes methods for improving the performance of linear search for the purpose of exact nearest neighbour matching using typical visual descriptors, such as the scale invariant feature transform (SIFT) [3, 4]. Many modern visual descriptors, such as gradient location and orientation histogram (GLOH) [5], are based on SIFT and have very similar characteristics from a search perspective. First, it is shown that simple modifications to the linear algorithm can allow it to outperform all existing search structures, without the need for any data preprocessing. Secondly, by
References
[1]
S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu, “An optimal algorithm for approximate nearest neighbor searching in fixed dimensions,” Journal of the ACM, vol. 45, no. 6, pp. 891–923, 1998.
[2]
M. Muja and D. G. Lowe, “Fast approximate nearest neighbors with automatic algorithm configuration,” in Proceedings of the International Conference on Computer Vision Theory and Applications (VISAPP'09), pp. 331–340, February 2009.
[3]
D. G. Lowe, “Object recognition from local scale-invariant features,” in Proceedings of the 7th IEEE International Conference on Computer Vision (ICCV'99), vol. 2, pp. 1150–1157, Kerkyra, Greece, September 1999.
[4]
D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004.
[5]
K. Mikolajczyk and C. Schmid, “A performance evaluation of local descriptors,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 10, pp. 1615–1630, 2005.
[6]
M. J. Huiskes and M. S. Lew, “The MIR Flickr retrieval evaluation,” in Proceedings of the 1st ACM International Conference on Multimedia Information Retrieval (MIR'08), pp. 39–43, August 2008.
[7]
J. H. Friedman, J. L. Bentley, and R. A. Finkel, “An algorithm for finding best matches in logarithmic expected time,” ACM Transactions on Mathematical Software, vol. 3, no. 3, pp. 209–226, 1977.
[8]
K. Fukunaga and P. M. Narendra, “A branch and bound algorithm for computing k-nearest neighbors,” IEEE Transactions on Computers, vol. 24, no. 7, pp. 750–753, 1975.
[9]
S. Brin, “Near neighbor search in large metric spaces.,” in Proceedings of the 21th International Conference on Very Large Data Bases (VLDB'95), pp. 574–584, 1995.
[10]
M. Houle, H. Kriegel, P. Kr？ger, E. Schubert, and A. Zimek, Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?vol. 6187 of Lecture Notes in Computer Science, Springer, Berlin, Germany, 2010.
[11]
D. Nistér and H. Stewénius, “Scalable recognition with a vocabulary tree,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06), vol. 2, pp. 2161–2168, June 2006.
[12]
J. S. Beis and D. G. Lowe, “Shape indexing using approximate nearest-neighbour search in high-dimensional spaces,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1000–1006, June 1997.
[13]
M. Aly, P. Welinder, M. Munich, and P. Perona, “Scaling object recognition: benchmark of current state of the art techniques,” in Proceedings of the 12th IEEE International Conference on Computer Vision Workshops (ICCV Workshops'09), pp. 2117–2124, Kyoto, Japan, October 2009.
[14]
L. Paulevé, H. Jégou, and L. Amsaleg, “Locality sensitive hashing: a comparison of hash function types and querying mechanisms,” Pattern Recognition Letters, vol. 31, no. 11, pp. 1348–1358, 2010.
[15]
J. Matas, O. Chum, M. Urban, and T. Pajdla, “Robust wide baseline stereo from maximally stable extremal regions,” in Proceedings of the British Machine Vision Conference, vol. 1, pp. 384–393, 2002.
[16]
C. D. Bei and R. M. Gray, “An improvement of the minimum distortion encoding algorithm for vector quantization,” IEEE Transactions on Communications, vol. 33, no. 10, pp. 1132–1133, 1985.
[17]
R. Lakemond, C. Fookes, and S. Sridharan, “Negative determinant of hessian features,” in Proceedings of the International Conference on Digital Image Computing: Techniques and Applications, pp. 530–535, Queensland, Australia, December 2011.
[18]
R. Lakemond, D. N. R. McKinnon, C. Fookes, and S. Sridharan, “A feature clustering algorithm for scale-space analysis of image structures,” in Proceedings of the International Conference on Signal Processing and Communication Systems, pp. 186–192, Gold Coast, Australia, December 2007.
