Loading…
A fast all nearest neighbor algorithm for applications involving large point-clouds
Algorithms that use point-cloud models make heavy use of the neighborhoods of the points. These neighborhoods are used to compute the surface normals for each point, mollification, and noise removal. All of these primitive operations require the seemingly repetitive process of finding the k nearest...
Saved in:
Published in: | Computers & graphics 2007-04, Vol.31 (2), p.157-174 |
---|---|
Main Authors: | , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | Algorithms that use point-cloud models make heavy use of the neighborhoods of the points. These neighborhoods are used to compute the surface normals for each point, mollification, and noise removal. All of these primitive operations require the seemingly repetitive process of finding the
k nearest neighbors (
kNNs) of each point. These algorithms are primarily designed to run in main memory. However, rapid advances in scanning technologies have made available point-cloud models that are too large to fit in the main memory of a computer. This calls for more efficient methods of computing the
kNNs of a large collection of points many of which are already in close proximity. A fast
kNN algorithm is presented that makes use of the locality of successive points whose
k nearest neighbors are sought to reduce significantly the time needed to compute the neighborhood needed for the primitive operation as well as enable it to operate in an environment where the data is on disk. Results of experiments demonstrate an
order of magnitude improvement in the
time to perform the algorithm and
several orders of magnitude improvement in
work efficiency when compared with several prominent existing methods. |
---|---|
ISSN: | 0097-8493 1873-7684 |
DOI: | 10.1016/j.cag.2006.11.011 |