A New K Nearest Neighbours Algorithm Using Cell Grids for 3D Scattered Point Cloud

Authors

  • Jianhui Zhao Wuhan University
  • Chengjiang Long Wuhan University
  • Shuping Xiong Ulsan National Institute of Science and Technology
  • Cheng Liu Wuhan University
  • Zhiyong Yuan Wuhan University

DOI:

https://doi.org/10.5755/j01.eee.20.1.3926

Keywords:

K nearest neighbours, search algorithm, 3D point cloud, cell grids

Abstract

In this paper, we propose one novel and efficient K nearest neighbours search algorithm based on 3D uniform cell grids. First, a simple min-max box is used to store all the points and a twice division strategy is adopted to determine the edge length of basic grids. Then we limit the search space for each grid with certain query points to control the amount of distance calculations under a suitable level. And the computational cost of sorting operations is reduced effectively through avoiding the unnecessary calculations, with the help of properly determined subspaces and sphere spaces for points. Compared with existing related algorithms, our method can search for the K nearest neighbours accurately and quickly, and it has many possible applications in the fields using 3D scattered point clouds.

DOI: http://dx.doi.org/10.5755/j01.eee.20.1.3926

Downloads

Published

2014-01-12

How to Cite

Zhao, J., Long, C., Xiong, S., Liu, C., & Yuan, Z. (2014). A New K Nearest Neighbours Algorithm Using Cell Grids for 3D Scattered Point Cloud. Elektronika Ir Elektrotechnika, 20(1), 81-87. https://doi.org/10.5755/j01.eee.20.1.3926

Issue

Vol. 20 No. 1 (2014)

Section

SYSTEM ENGINEERING, COMPUTER TECHNOLOGY

License

The copyright for the paper in this journal is retained by the author(s) with the first publication right granted to the journal. The authors agree to the Creative Commons Attribution 4.0 (CC BY 4.0) agreement under which the paper in the Journal is licensed.

By virtue of their appearance in this open access journal, papers are free to use with proper attribution in educational and other non-commercial settings with an acknowledgement of the initial publication in the journal.