Accelerating kd-tree Searches for all k-nearest Neighbours
Merry, Bruce, James Gain and Patrick Marais (2013) Accelerating kd-tree Searches for all k-nearest Neighbours. In Proceedings 34th Annual Conference of the European Association for Computer Graphics (Eurographics 2013), Girona, Spain.
Finding the k nearest neighbours of each point in a point cloud forms an integral part of many point-cloud processing tasks. One common approach is to build a kd-tree over the points and then iteratively query the k nearest neighbors of each point. We introduce a simple modification to these queries to exploit the coherence between successive points; no changes are required to the kd-tree data structure. The path from the root to the appropriate leaf is updated incrementally, and backtracking is done bottom-up. We show that this can reduce the time to compute the neighbourhood graph of a 3D point cloud by over 10%, and by up to 24% when k = 1. The gains scale with the depth of the kd-tree, and the method is suitable for parallel implementation.
|EPrint Type:||Conference Paper|
|Keywords:||kd-tree, nearest neighbours|
|Subjects:||I Computing Methodologies: I.3 COMPUTER GRAPHICS|
|Deposited By:||Merry, Bruce|
|Deposited On:||30 October 2013|