Accelerating kd-tree searches for all k-nearest neighbours

Merry, Bruce and Gain, James and Marais, Patrick (2013) Accelerating kd-tree searches for all k-nearest neighbours, CS13-01-00, Department of Computer Science, University of Cape Town.

[img] PDF
kd-backtrack-techrep.pdf

Download (294kB)

Abstract

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.

Item Type: Technical report
Additional Information: This is an extended version of a short paper to be presented at Eurographics 2013.
Uncontrolled Keywords: kd-tree, all nearest neighbours
Subjects: Computing methodologies > Computer graphics
Date Deposited: 12 Feb 2013
Last Modified: 10 Oct 2019 15:33
URI: http://pubs.cs.uct.ac.za/id/eprint/847

Actions (login required)

View Item View Item