LabVIEW三维点云K邻域

在逆向工程中，点云阶段的处理包括聚类分析、点云去噪平滑、点云三角网格重建等操作都需要基于点云K邻域的计算，点云K邻域的计算在逆向工程中至关重要。三维点云和两维图像的邻域有明显区别，二维图像像素之间都有严格的拓扑关系，三维点云没有严格拓扑关系，但可以借助两维图像思想，为三维点云建立“体素”，如下图所示，P点的K邻域代表的是以P点位球心，半径内的点的集合，构成P点的邻域，K代表的是P邻域内最近的几个点。

在构建三维点云的体素拓扑关系时，目前有均匀网格法、OcTree八叉树法、KDTree法等，我这里主要介绍均匀网格法和OcTree八叉树法。

1. 建立均匀立方格的三维点云拓扑结构

根据点云的长宽高及立方体的边长，初始化计算需要建立的三维立方体数据结构，立方体我们抽象为LabVIEW里面的簇，每个立方体里面有20-50个点云，在簇里面包含点云数组，如下图所示：

有些同学是不太注意内存的优化，当数据量大的话，严重影响运行效率。在这个结构中，我存储的是三维点云的二维DBL数组，100万个这样的结构还是占用不少内存空间的，优化成储存点云索引的I32一维数组，大大节省内存空间，如下图所示：

1. 点云插入数据结构

每个点计算在拓扑关系的位置，然后根据位置插入，代码如下：

1. 种子点的K邻域

给定种子点，获取该点在三维拓扑结构中的位置索引，根据索引值计算邻域26个索引值，并读出26个立方体的点云，该点云集合就是种子点的邻域值，如下图所示，以红点位种子点的13邻域集合，绿色点。

2、基于OCTree的八叉树数据拓扑结构

可以发现在均匀网格拓扑数据结构中，会有很多中空的无效空间被初始化，对于数据量较大的表面轮廓点云来说，均匀网格拓扑数据结构很多空间被浪费。OCTree数据结构很好的解决了这个问题，有点的地方迭代分割下去，没有点的地方停止分割，在我的一篇文章《LabVIEW OcTree(八叉树数据容器)》中介绍过这个方法。我拿一个点云为例子看下分割效果，如下图所示。

基于OCTree的K邻域方法相对比较好理解，OCTree的特点就是每一层具有8个同类如下图所示；

种子点所在立方体父类的8个子节点中的点云根据距离排序，截取K个值，既种子点的K邻域。读出子类中点云的方法：