Accelerating kd-tree Searches for all k-nearest Neighbours
Loading...
Date
2013
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
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
Description
@inproceedings{:10.2312/conf/EG2013/short/037-040,
booktitle = {Eurographics 2013 - Short Papers},
editor = {M.- A. Otaduy and O. Sorkine},
title = {{Accelerating kd-tree Searches for all k-nearest Neighbours}},
author = {Merry, Bruce and Gain, James and Marais, Patrick},
year = {2013},
publisher = {The Eurographics Association},
ISSN = {1017-4656},
ISBN = {},
DOI = {/10.2312/conf/EG2013/short/037-040}
}