Merry, Bruce and Gain, James and Marais, Patrick (2013) Accelerating kd-tree Searches for all k-nearest Neighbours, Proceedings of 34th Annual Conference of the European Association for Computer Graphics (Eurographics 2013), 6-10 May 2013, Girona, Spain.
![[img]](http://pubs.cs.uct.ac.za/style/images/fileicons/application_pdf.png) |
PDF
kd-backtrack.pdf Download (135kB) |
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: | Conference paper |
|---|---|
| Additional Information: | The definitive version is available at http://diglib.eg.org/ |
| Uncontrolled Keywords: | kd-tree, nearest neighbours |
| Subjects: | Computing methodologies > Computer graphics |
| Alternate Locations: | http://diglib.eg.org/EG/DL/conf/EG2013/short/037-040.pdf.abstract.pdf;internal&action=action.digitallibrary.ShowPaperAbstract |
| Date Deposited: | 30 Oct 2013 |
| Last Modified: | 10 Oct 2019 15:33 |
| URI: | http://pubs.cs.uct.ac.za/id/eprint/853 |
Actions (login required)
 |
View Item |