3D Laser Point Cloud Data Index and Nearest Neighbor Query Method

LI Song; WU Nan; JIN Haipeng; ZHANG Liping; SUN Guanglu

doi:10.13203/j.whugis20230374

您当前的位置：

首页 >

文章列表页 >

3D Laser Point Cloud Data Index and Nearest Neighbor Query Method

Cartography and GIS | 更新时间：2026-11-05

- 3D Laser Point Cloud Data Index and Nearest Neighbor Query Method
- Geomatics and Information Science of Wuhan University Vol. 50, Issue 11, Pages: 2295-2302(2025)
- 作者机构：
  
  哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨，150080
- 作者简介：
- 基金信息：
- DOI：10.13203/j.whugis20230374
  CLC： P237
- Received：29 May 2024，
  
  Published：05 November 2025
- 稿件说明：
移动端阅览
李松,吴楠,靳海鹏，等.三维激光点云数据索引和近邻查询方法研究[J].武汉大学学报（信息科学版）,2025,50(11):2295-2302.

LI Song,WU Nan,JIN Haipeng,et al.3D Laser Point Cloud Data Index and Nearest Neighbor Query Method[J].Geomatics and Information Science of Wuhan University,2025,50(11):2295-2302.
李松,吴楠,靳海鹏，等.三维激光点云数据索引和近邻查询方法研究[J].武汉大学学报（信息科学版）,2025,50(11):2295-2302. DOI：10.13203/j.whugis20230374

LI Song,WU Nan,JIN Haipeng,et al.3D Laser Point Cloud Data Index and Nearest Neighbor Query Method[J].Geomatics and Information Science of Wuhan University,2025,50(11):2295-2302. DOI：10.13203/j.whugis20230374

摘要

为了解决激光点云数据分布不均匀和点云数据近邻查询效率较低的问题，提出了一种基于激光点云索引结构的近邻查询方法。基于Z曲线，该方法首先将激光点云数据信息传递到由局部KD树和局部八叉树组成的KD_ZoC索引结构中，在对激光点云数据进行划分时，根据节点的Z地址形成最小立方体，并进一步将空间划分为子空间。其次，为了实现数据的快速检索，采用局部KD树和局部八叉树的方式对叶子节点进行分组，并根据提出的八分圆域进一步减少数据点的数量。最后，将数据存储到链表中，并结合数据的Z地址实现高效的数据近邻查询。理论研究和实验结果表明，所提出的方法能有效地将激光点云下的近邻查询效率提高20%。此外，相比于传统查询方法，八分圆域划分方法能够有效地剪枝对查询结果无影响的数据点从而实现数据点的二次精炼。

Abstract

Objectives

In order to solve the problem of uneven distribution of laser point cloud data and low efficiency of point cloud data neighbor query

this paper proposes a neighbor query method based on laser point cloud index structure.

Methods

Based on the Z curve

the method first transfers the information of laser point cloud data to the KD_ZoC index structure composed of local KD tree and local octree. When the laser point cloud data is divided

the minimum cube is formed according to the Z address of the node

and the space is further divided into subspaces. Second

in order to achieve fast data retrieval

leaf nodes are grouped by local KD tree and local octree

and the number of data points is further reduced according to the proposed octant domain. Finally

the data is stored in the linked list

and the Z address of the data is combined to achieve efficient nearest neighbor query.

Results

This paper makes the following contributions: (1) Aiming at the problem that the single index structure is hard to effectively process laser point cloud data

this paper proposes a new index structure

the KD_ZoC index structure

based on the Z curve. It constructs a hybrid index structure of local octrees and local KD trees

and introduces threshold values for the data division of both components. This effectively reduces laser point cloud data

solving the problem of difficult data processing when the laser point cloud data volume is large. (2)To address the problem of comparing multi-dimensional data

this paper uses the Z curve for dimensionality reduction of point cloud data. It provides a specific conversion formula to transform the data into binary data

which is stored in the leaf nodes of the leaf octree. This effectively reduces the comparison time for nearest neighbor queries and saves storage space. (3)To improve the efficiency of nearest-neighbor queries for point cloud data

this paper proposes an octant circle neighborhood search method based on the KD_ZoC index structure. By utilizing symmetry for effective data reduction

it reduces computational time costs and presents an efficient nearest - neighbor query algorithm.

Conclusion

Theoretical research and experimental results show that the proposed method can effectively deal with the nearest neighbor query problem under the laser point cloud

and realize the efficient retrieval and management of data points.

关键词

Keywords

references

孙殿柱，刘健，李延瑞，等 . 三维散乱点云的Voronoi拓扑近邻点集查询算法［J］. 武汉大学学报（信息科学版）， 2011 ， 36 （ 1 ）： 86 - 91 .

SUN Dianzhu ， LIU Jian ， LI Yanrui ， et al . An Algorithm Inquiring Voronoi Topological Neighbors for 3D Scattered Point-Cloud ［J］. Geomatics and Information Science of Wuhan University ， 2011 ， 36 （ 1 ）： 86 - 91 .

张卉冉，董震，杨必胜，等 . 点云压缩研究进展与趋势［J］. 武汉大学学报（信息科学版）， 2023 ， 48 （ 2 ）： 192 - 205 .

ZHANG Huiran ， DONG Zhen ， YANG Bisheng ， et al . Progress and Perspectives of Point Cloud Compression ［J］. Geomatics and Information Science of Wuhan University ， 2023 ， 48 （ 2 ）： 192 - 205 .

KAMENCAY P ， SINKO M ， HUDEC R ， et al . Improved Feature Point Algorithm for 3D Point Cloud Registration ［C］// 2019 42nd International Conference on Telecommunications and Signal Processing （TSP）， Budapest， Hungary ， 2019 .

GOJCIC Z ， ZHOU C F ， WEGNER J D ， et al . The Perfect Match： 3D Point Cloud Matching with Smoothed Densities ［C］// 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition （CVPR）， Long Beach， CA， USA， 2019 .

AOKI Y ， GOFORTH H ， SRIVATSAN R A ， et al . PointNetLK： Robust & Efficient Point Cloud Registration Using PointNet ［C］// 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition （CVPR）， Long Beach， CA， USA， 2019 .

伍济钢，马佳康，杨康，等 . 基于改进ICP的复杂机械零件测量点云配准方法［J］. 光电子·激光， 2023 ， 34 （ 6 ）： 620 - 627 .

WU Jigang ， MA Jiakang ， YANG Kang ， et al . Measurement Point Cloud Registration Method for Complex Mechanical Parts Based on Improved ICP ［J］. Journal of Optoelectronics·Laser ， 2023 ， 34 （ 6 ）： 620 - 627 .

LI M J ， YIN D . A Fast Segmentation Method of Sparse Point Clouds ［C］// 2017 29th Chinese Control and Decision Conference （CCDC）， Chongqing， China ， 2017 .

JIANG H B ， JIAO Q S . TLS Point Cloud Segmentation Based on Points Features ［C］// 2017 IEEE International Geoscience and Remote Sensing Symposium （IGARSS）， Fort Worth， TX， USA， 2017 .

TCHAPMI L ， CHOY C ， ARMENI I ， et al . SEGCloud： Semantic Segmentation of 3D Point Clouds ［C］// 2017 International Conference on 3D Vision （3DV）， Qingdao， China ， 2017 .

ROVERI R ， RAHMANN L ， ÖZTIRELI A C ， et al . A Network Architecture for Point Cloud Classification via Automatic Depth Images Generation ［C］// 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition ， Salt Lake City， UT， USA， 2018 .

王渊 . 车载激光点云数据增强与语义分割［J］. 武汉大学学报（信息科学版）， 2024 ， 49 （ 10 ）： 1973 .

WANG Yuan . Data Enhancement and Semantic Segmentation of Mobile Laser Scanning Point Cloud ［J］. Geomatics and Information Science of Wuhan University ， 2024 ， 49 （ 10 ）： 1973 .

杨丽娟，崔钰琳，杨紫骞，等 . 基于点云空间分布特征的多级索引结构［J］. 激光与红外， 2023 ， 53 （ 1 ）： 137 - 145 .

YANG Lijuan ， CUI Yulin ， YANG Ziqian ， et al . Multi-Level Index Structure Based on Spatial Distribution Characteristics of Point Cloud ［J］. Laser & Infrared ， 2023 ， 53 （ 1 ）： 137 - 145 .

MIN L ， YUN M . Study on Point Cloud Management Strategy Based on Octree-Like Index ［J］. Laser & Optoelectronics Progress ， 2020 ， 57 （ 14 ）： 141025 .

SU H ， JAMPANI V ， SUN D Q ， et al . SPLATNet： Sparse Lattice Networks for Point Cloud Processing ［C］// 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition ， Salt Lake City， UT， USA， 2018 .

丛阳滋 . 联合多源点云的激光雷达三维建图与更新［J］. 武汉大学学报（信息科学版）， 2024 ， 49 （ 10 ）： 1972 .

CONG Yangzi . LiDAR-Based 3D Mapping and Update Leveraging Heterogeneous Point Clouds ［J］. Geomatics and Information Science of Wuhan University ， 2024 ， 49 （ 10 ）： 1972 .

OGAYAR-ANGUITA C J ， LÓPEZ-RUIZ A ， RUEDA-RUIZ A J ， et al . Nested Spatial Data Structures for Optimal Indexing of LiDAR Data ［J］. ISPRS Journal of Photogrammetry and Remote Sensing ， 2023 ， 195 ： 287 - 297 .

WANG Z C ， WAN S ， WEI L . Local Geometry-Based Intra Prediction for Octree-Structured Geometry Coding of Point Clouds ［J］. IEEE Transactions on Circuits and Systems for Video Technology ， 2023 ， 33 （ 2 ）： 886 - 896 .

ZHANG D F ， WANG Y ， LIU Z L ， et al . Improving NoSQL Storage Schema Based on Z-Curve for Spatial Vector Data ［J］. IEEE Access ， 2019 ， 7 ： 78817 - 78829 .

张蕊，李广云，王力，等 . 车载LiDAR点云混合索引新方法［J］. 武汉大学学报（信息科学版）， 2018 ， 43 （ 7 ）： 993 - 999 .

ZHANG Rui ， LI Guangyun ， WANG Li ， et al . A New Method of Hybrid Index for Mobile LiDAR Point Cloud Data ［J］. Geomatics and Information Science of Wuhan University ， 2018 ， 43 （ 7 ）： 993 - 999 .

郑志 . 基于亚米级立体卫星影像的三维地形智能提取［J］. 武汉大学学报（信息科学版）， 2025 ， 50 （ 3 ）： 616 .

ZHENG Zhi . Intelligent Extraction of 3D Terrain Based on Sub-Meter Satellite Stereos ［J］. Geomatics and Information Science of Wuhan University ， 2025 ， 50 （ 3 ）： 616 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Three-State Fusion Support Problem of Marine Geographic Information for Ship Navigation

Development and Prospects of Spaceborne Greenhouse Gas LiDAR Technology

Research Progress in Spatiotemporal Modeling， Analysis， and Prediction of Urban Activity Flows in Built Environment

Tectonic Geodesy： Research Advancements， Opportunities， and Challenges

A Review of Multi-scale Geospatial Data Updating Methods

Related Author

No data

Related Institution

No data

AI问答

⁰