Massive parallelization of approximate nearest neighbor search on KD-tree for high-dimensional image descriptor matching

To overcome the high computing cost associated with high-dimensional digital image descriptor matching, this paper presents a massively parallel approximate nearest neighbor search (ANNS) on K-dimensional tree (RD-tree) on the modern massively parallel architectures (MPA). The proposed algorithm is of comparable quality to traditional sequential counterpart on central processing unit (CPU). However, it achieves a high speedup factor of 121 when applied to high-dimensional real-world image descriptor datasets. The algorithm is also studied for factors that impact its performance to obtain the optimal runtime configurations for various datasets. The performance of the proposed parallel ANNS algorithm is also verified on typical 3D image matching scenarios. With the classical local image descriptor signature of histograms of orientations (SHOT), the parallel image descriptor matching can achieve speedup of up to 128. Our implementation will potentially benefit realtime image descriptor matching in high dimensions. (C) 2017 Elsevier Inc. All rights reserved.