Abstract
Many computer vision tasks rely on correspondence between features. SIFT and related descriptors represent features as high-dimensional vectors, which are used to compute a distance between features for matching. Calculating these distances is expensive in large datasets, so approximate nearest neighbour (ANN) approaches are used.
ANN schemes that can be efficiently parallelised have been proposed, some of which divide up high-dimensional vectors into lower-dimensional subspaces. However, the feature descriptors computed by SIFT and similar methods are not computed in a homogeneous manner. There are clear statistical patterns within and between the components of feature vectors, and in this work we show that these patterns can have a strong effect on approximate nearest neighbor searching algorithms that are based on space subdivision.