TY - JOUR

T1 - A new extracting algorithm of k nearest neighbors searching for point clouds

AU - Li, Zisheng

AU - Ding, Guofu

AU - Li, Rong

AU - Qin, Sheng-feng

N1 - Published online 22-7-2014 ahead of print.

PY - 2014/11/1

Y1 - 2014/11/1

N2 - k Nearest neighbors (kNN) searching algorithm is widely used for finding k nearest neighbors for each point in a point cloud model for noise removal and surface curvature computation. When the number of points and their density in a point cloud model increase significantly, the efficiency of a kNN searching algorithm becomes critical to various applications, thus, a better kNN approach is needed. In order to improve the efficiency of a kNN searching algorithm, in this paper, a new strategy and the corresponding algorithm are developed for reducing the amount of target points in a given data set by extracting nearest neighbors before the search begins. The nearest neighbors of a reverse nearest neighborhood are proposed to use in extracting nearest points of a query point, avoiding repetitive Euclidean distance calculation in an extracting process for saving time and memories. For any point in the model, its initial nearest neighbors can be extracted from its reverse neighborhood using an inner product of two related vectors other than direct Euclidean distance calculations and comparisons. The initial neighbors can be its full or partial set of the all nearest neighbors. If it is a partial set, the rest can be obtained by using other fast searching algorithms, which can be integrated with the proposed approach. Experimental results show that integrating extracting algorithm proposed in this paper with other excellent algorithms provides a better performance by comparing to their performances alone.

AB - k Nearest neighbors (kNN) searching algorithm is widely used for finding k nearest neighbors for each point in a point cloud model for noise removal and surface curvature computation. When the number of points and their density in a point cloud model increase significantly, the efficiency of a kNN searching algorithm becomes critical to various applications, thus, a better kNN approach is needed. In order to improve the efficiency of a kNN searching algorithm, in this paper, a new strategy and the corresponding algorithm are developed for reducing the amount of target points in a given data set by extracting nearest neighbors before the search begins. The nearest neighbors of a reverse nearest neighborhood are proposed to use in extracting nearest points of a query point, avoiding repetitive Euclidean distance calculation in an extracting process for saving time and memories. For any point in the model, its initial nearest neighbors can be extracted from its reverse neighborhood using an inner product of two related vectors other than direct Euclidean distance calculations and comparisons. The initial neighbors can be its full or partial set of the all nearest neighbors. If it is a partial set, the rest can be obtained by using other fast searching algorithms, which can be integrated with the proposed approach. Experimental results show that integrating extracting algorithm proposed in this paper with other excellent algorithms provides a better performance by comparing to their performances alone.

KW - Distance comparison using vector inner product

KW - extracting algorithm

KW - kNN searching algorithm

KW - point clouds

U2 - 10.1016/j.patrec.2014.07.003

DO - 10.1016/j.patrec.2014.07.003

M3 - Article

SN - 0167-8655

VL - 49

SP - 162

EP - 170

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

ER -