Saeid Nooshabadi (SAS/ECE), professor of electrical and computer engineering, is co-author of the article, “High-dimensional image descriptor matching using highly parallel KD-tree construction and approximate nearest neighbor search,” to be published in the October 2019 issue of the Journal of Parallel and Distributed Computing, which is published by Elsevier. The article is co-authored by Michigan Tech Computer Science department doctoral candidate Linjia Hu.
Abstract: To overcome the high computational cost associated with the high-dimensional digital image descriptor matching, this paper presents a set of integrated parallel algorithms for the construction of K-dimensional tree (KD-tree) and P approximate nearest neighbor search (P-ANNS) on the modern massively parallel architectures (MPA). To improve the runtime performance of the P-ANNS, we propose an efficient sliding window for a parallel buffered P-ANNS on KD-tree to mitigate the high cost of global memory accesses. When applied to high dimensional real-world image descriptor datasets, the proposed KD-tree construction and the buffered P-ANNS algorithms are of comparable matching quality to the traditional sequential counterparts on CPU, while outperforming their serial CPU counterparts by speedup factors of up to 17 and 163, respectively. The algorithms are also studied for the performance impact factors to obtain the optimal runtime configurations for various datasets. Moreover, we verify the features of the parallel algorithms on typical 3D image matching scenarios. With the classical local image descriptor signature of histograms of orientations (SHOT) datasets, the parallel KD-tree construction and image descriptor matching can achieve up to 11 and 138-fold speedups, respectively.
Citation: Hu, L., & Nooshabadi, S. (2019). High-dimensional image descriptor matching using highly parallel KD-tree construction and approximate nearest neighbor search. Journal of Parallel and Distributed Computing, 132, 127-140. http://dx.doi.org/10.1016/j.jpdc.2019.06.003
MTU Digital Commons link: https://digitalcommons.mtu.edu/michigantech-p/145/