1. 点云是什么

通过雷达、激光扫描、立体摄像机等三维测量设备获得的点云数据，具有数据量大、分布不均匀等特点。

点云数据主要是表征目标表面的海量点集合，并不具备传统实体网格数据的几何拓扑信息。点云处理中最核心的问题就是建立离散点间的拓扑结构，实现基于邻域关系的快速查找，变的很重要。

2. 点云索引分类及应用

划分空间的索引结构有：k-d tree，八叉树、四叉树、BSP树、KDB树，R树，R+树等；

利用kdtree【k-维树】和octree【八叉树】对海量点云进行高效压缩存储与管理，及基于邻域关系的快速搜索。

K近邻搜索操作的框架是基于FLANN（Fast Library For Approximate Nearest Neighbors）。

3. KdTree（K-维树）

在这里插入图片描述

KdTree 也称为K维树，用来组织表示K维空间中的点集合。
通常只在三个维度中处理，因此可称为3维k-d树。

KdTree、 Octree（八叉树），都是点云数据中索引的一种，为了快速索引以及无损的压缩点云而设计的。

Kd树有几种常用的搜素方法：

体素内近邻搜索（Neighbors with Voxel Search）它把查询点所在的体素中的其他点的索引作为查询结果返回；
K近邻搜索（K Nearest Neighbor Serach）；
半径内近邻搜索（Neighbor with Radius Search）

(1) 使用最近邻方法搜索kdTree

该示例演示了

1）创建kd树；
2）k近邻搜索，并输出每个点的k近邻点；
3）半径搜索python-pcl暂未实现。

TestCode : examples/official/kdtree/kdtree_search.py

# -*- coding: utf-8 -*-
# http://pointclouds.org/documentation/tutorials/kdtree_search.php#kdtree-searchimport numpy as np
import pcl
import randomdef main():cloud = pcl.PointCloud()# 构建点云数据points = np.zeros((1000, 3), dtype=np.float32)RAND_MAX = 1024for i in range(0, 1000):points[i][0] = 1024 * random.random() / (RAND_MAX + 1.0)points[i][1] = 1024 * random.random() / (RAND_MAX + 1.0)points[i][2] = 1024 * random.random() / (RAND_MAX + 1.0)cloud.from_array(points)# 生成k近邻树kdtree = cloud.make_kdtree_flann()# 构建一个 查询k近邻的初始点云searchPoint = pcl.PointCloud()searchPoints = np.zeros((1, 3), dtype=np.float32)searchPoints[0][0] = 1024 * random.random() / (RAND_MAX + 1.0)searchPoints[0][1] = 1024 * random.random() / (RAND_MAX + 1.0)searchPoints[0][2] = 1024 * random.random() / (RAND_MAX + 1.0)searchPoint.from_array(searchPoints)# K nearest neighbor search "K近邻搜索"K = 10  # 设置k近邻搜索 k的数量print('K nearest neighbor search at (' + str(searchPoint[0][0]) + ' ' + str(searchPoint[0][1]) + ' ' + str(searchPoint[0][2]) + ') with K=' + str(K))# 找到 searchPoint点 在指定点云中的 K 近邻[ind, sqdist] = kdtree.nearest_k_search_for_cloud(searchPoint, K)# 当k近邻搜索结果不为空时，遍历获取每个点的k近邻结果for i in range(0, ind.size):print('(' + str(cloud[ind[0][i]][0]) + ' ' + str(cloud[ind[0][i]][1]) + ' ' + str(cloud[ind[0][i]][2]) + ' (squared distance: ' + str(sqdist[0][i]) + ')')# Neighbors within radius search  "半径内近邻搜索"radius = 256.0 * random.random() / (RAND_MAX + 1.0)  # 设置半径内近邻搜索的半径值print('Neighbors within radius search at (' + str(searchPoint[0][0]) + ' ' + str(searchPoint[0][1]) + ' ' + str(searchPoint[0][2]) + ') with radius=' + str(radius))# NotImplement radiusSearch[ind, sqdist] = kdtree.radius_search_for_cloud(searchPoint, radius)print(ind.size, sqdist.size)for i in range(0, ind.size):print('(' + str(cloud[ind[0][i]][0]) + ' ' + str(cloud[ind[0][i]][1]) + ' ' + str(cloud[ind[0][i]][2]) + ' (squared distance: ' + str(sqdist[0][i]) + ')')if __name__ == "__main__":main()

(2) 用kdTree找到具体点或空间位置的k近邻

该示例演示了

1）创建kd树
2）找到点云1中距离点云2中每个点最近的k近邻
3）也可寻找离自身点云每个点的k近邻
TestCode : examples/official/kdtree/kdtree.py

# -*- coding: utf-8 -*-
from __future__ import print_functionimport numpy as np
import pcl#  点云1 中距离点云2中 最近的一个点及其距离 （也可搜索近邻多个）
#  也可找点云1中的k近邻 相应的还有（半径内近邻搜索）只是还未实现
def main():points_1 = np.array([[0, 0, 0],[1, 0, 0],[0, 1, 0],[1, 1, 0]], dtype=np.float32)points_2 = np.array([[0, 0, 0.2],[1, 0, 0],[0, 1, 0],[1.1, 1, 0.5]], dtype=np.float32)pc_1 = pcl.PointCloud()pc_1.from_array(points_1)pc_2 = pcl.PointCloud()pc_2.from_array(points_2)kd = pcl.KdTreeFLANN(pc_1)pc_1 = pcl.PointCloud(points_1)pc_2 = pcl.PointCloud(points_2)kd = pc_1.make_kdtree_flann()# 找到点云1中离点云2最近的一个点（就距离来说）# 可修改 找近邻数不为1 ，为2# 修改pc_2 为其自身，则是求自身每个点的近邻点indices, sqr_distances = kd.nearest_k_search_for_cloud(pc_2, 2)for i in range(pc_1.size):print('index of the closest point in pc_1 to point %d in pc_2 is %d'% (i, indices[i, 0]))print('the squared distance between these two points is %f'% sqr_distances[i, 0])if __name__ == "__main__":main()

4. Octree（八叉树）

八叉树是一种用于管理稀疏3D数据的树状数据结构，每个内部节点都正好有8个子节点。
八叉树结构通过循环递归的划分方法对大小为2n * 2n * 2n的三维空间的几何对象进行剖分，从而构成一个具有根节点的方向图。

八叉树的应用之一是点云压缩（Compression）。
八叉树也是一种索引方式，可以基于八叉树（Octrees）对点云进行空间划分和搜索操作。

在这里插入图片描述

(1) 使用八叉树进行空间分区和最近邻居搜索

该示例演示了

1）创建八叉树
2）找到一组点的K近邻
3）找到一组点的半径近邻
4）打印数据

TestCode : examples/official/octree/octree_search.py

(2) 使用八叉树来检测无序点云的空间变化

功能：打印出数据cloudB在cloudA的基础上新增的节点；
缺点：只能探测 cloudA基础上新增的点集,并不能探测cloudA上减少的点集合

该示例演示了

1）创建八叉树cloudA
2）转换八叉树缓存（重置八叉树并且保留之前的结构在内存中）
3）构建八叉树cloudB
4）打印数据cloudB在cloudA的基础上新增的节点；

TestCode : examples/official/octree/octree_change_detection.py