TY - GEN
T1 - Improved KNN algorithm for scattered point cloud
AU - Li, Dongxia
AU - Wang, Aimin
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/9/29
Y1 - 2017/9/29
N2 - Aiming at the k-nearest neighbors algorithm for scatter point cloud data, an improve method has been proposed based on dimension reduction and sorting. In the improved algorithm, the main directions of point cloud data need to be solved according to PCA (Principal Components Analysis) to analyze the spatial distribution of point cloud data. After that, rotate the main directions to coincide with the X, Y, Z axis, sort the point cloud data in the three coordinate axis and find the position of query point. Then extract neighbor points in the three sorted point cloud data set in proportion respectively and calculate the distance between the query point and neighbors. Finally, sorting the distance, the first k points searched is the k-nearest neighbors. The algorithm improved in this paper reduces greatly the times of point to point distance calculation, where k-nearest neighbors are able to be obtained only after three times sorting and a small amount of calculation. Simultaneously, it improves the efficiency of KNN algorithm, which saves a lot of time to solve the normal vector of point cloud, reconstruct surface or other operations. The experimental result shows the effectiveness of the improved KNN algorithm.
AB - Aiming at the k-nearest neighbors algorithm for scatter point cloud data, an improve method has been proposed based on dimension reduction and sorting. In the improved algorithm, the main directions of point cloud data need to be solved according to PCA (Principal Components Analysis) to analyze the spatial distribution of point cloud data. After that, rotate the main directions to coincide with the X, Y, Z axis, sort the point cloud data in the three coordinate axis and find the position of query point. Then extract neighbor points in the three sorted point cloud data set in proportion respectively and calculate the distance between the query point and neighbors. Finally, sorting the distance, the first k points searched is the k-nearest neighbors. The algorithm improved in this paper reduces greatly the times of point to point distance calculation, where k-nearest neighbors are able to be obtained only after three times sorting and a small amount of calculation. Simultaneously, it improves the efficiency of KNN algorithm, which saves a lot of time to solve the normal vector of point cloud, reconstruct surface or other operations. The experimental result shows the effectiveness of the improved KNN algorithm.
KW - Dimension reduction and sorting
KW - K-nearest neighbors
KW - PCA
KW - Scattered point cloud
UR - http://www.scopus.com/inward/record.url?scp=85034591711&partnerID=8YFLogxK
U2 - 10.1109/IAEAC.2017.8054336
DO - 10.1109/IAEAC.2017.8054336
M3 - Conference contribution
AN - SCOPUS:85034591711
T3 - Proceedings of 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference, IAEAC 2017
SP - 1865
EP - 1869
BT - Proceedings of 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference, IAEAC 2017
A2 - Xu, Bing
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2nd IEEE Advanced Information Technology, Electronic and Automation Control Conference, IAEAC 2017
Y2 - 25 March 2017 through 26 March 2017
ER -