Optimizing kd-trees for scalable visual descriptor indexing

Abstract

In this paper, we attempt to scale up the kd-tree index-ing methods for large-scale vision applications, e.g., indexing a large number of SIFT features and other types of visual descriptors. To this end, we propose an effective approach to generate near-optimal binary space partitioning and need low time cost to access the nodes in the query stage. First, we relax the coordinate-axis-alignment constraint in partition axis selection used in conventional kd-trees, and form a partition axis with the great variance by combining a few coordinate axes in a binary manner for each node, which yields better space partitioning and requires almost the same time cost to visit internal nodes during the query stage thanks to cheap projection operations. Then, we introduce a simple but very effective scheme to guarantee the partition axis of e ach internal node is orthogonal to or parallel with those of its ancestors, which leads to efficient distance computation between a query point and the cell associated with each node and yields fast priority search. Compared with the conventional kd-trees, our approach takes a little more tree construction time, but obtains much better nearest neighbor search performance. Experimental results on large scale local patch indexing and image search with tiny images show that our approach outperforms the state-of-the-art kd-tree based indexing methods.

Download

Results

Performance Comparison 1 (a) Comparison of the precision against the query time between our approach and the conventional kd-tree in the single tree case. We compare them over the original data space and the preprocessed data points, rotated with PCA. It can be observed that our approach performs better. (b) Illustration of the multiple tree version of our approach. We show the precision comparison against the number of trees between our approach and the conven-tional kd-tree over the original data space and the preprocessed data points, rotated with PCA. It can be observed that our approach consistently performs better in the multiple tree case.   Performance Comparison 2 The query time comparison over the single tree case and the 5-tree case between our approach and the conventional kd-tree. We can see that our approach takes even less time than the conven-tional kd-tree when accessing the same number of leaf nodes.   Performance Comparison 3 Performance comparison over (a) recognition benchmark images, (b) notredame, and (c) tiny images.