通过雷达、激光扫描、立体摄像机等三维测量设备获得的点云数据，具有数据量大、分布不均匀等特点。
点云数据主要是表征目标表面的海量点集合，并不具备传统实体网格数据的几何拓扑信息。点云处理中最核心的问题就是建立离散点间的拓扑结构，实现基于邻域关系的快速查找，变的很重要。
划分空间的索引结构有：k-d tree，八叉树、四叉树、BSP树、KDB树，R树，R+树等；
利用kdtree【k-维树】和octree【八叉树】 对海量点云进行高效压缩存储与管理，及基于邻域关系的快速搜索。
K近邻搜索操作的框架是基于FLANN（Fast Library For Approximate Nearest Neighbors）。
KdTree 也称为K维树，用来组织表示K维空间中的点集合。 通常只在三个维度中处理，因此可称为3维k-d树。
KdTree、 Octree（八叉树），都是点云数据中索引的一种，为了快速索引以及无损的压缩点云而设计的。
Kd树有几种常用的搜素方法：
体素内近邻搜索 （Neighbors with Voxel Search） 它把查询点所在的体素中的其他点的索引作为查询结果返回；K近邻搜索（K Nearest Neighbor Serach）；半径内近邻搜索（Neighbor with Radius Search）该示例演示了
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-search import numpy as np import pcl import random def main(): cloud = pcl.PointCloud() # 构建点云数据 points = np.zeros((1000, 3), dtype=np.float32) RAND_MAX = 1024 for 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()该示例演示了
1）创建kd树2）找到点云1中距离点云2中每个点最近的k近邻3）也可寻找离自身点云每个点的k近邻 TestCode : examples/official/kdtree/kdtree.py # -*- coding: utf-8 -*- from __future__ import print_function import 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()八叉树是一种用于管理稀疏3D数据的树状数据结构，每个内部节点都正好有8个子节点。 八叉树结构通过循环递归的划分方法对大小为2n * 2n * 2n的三维空间的几何对象进行剖分，从而构成一个具有根节点的方向图。
八叉树的应用之一是点云压缩（Compression）。 八叉树也是一种索引方式，可以基于八叉树（Octrees）对点云进行空间划分和搜索操作。
该示例演示了
1）创建八叉树2）找到一组点的K近邻3）找到一组点的半径近邻4）打印数据TestCode : examples/official/octree/octree_search.py
功能： 打印出数据cloudB在cloudA的基础上新增的节点； 缺点：只能探测 cloudA基础上新增的点集,并不能探测cloudA上减少的点集合
该示例演示了
1）创建八叉树cloudA2）转换八叉树缓存（重置八叉树并且保留之前的结构在内存中）3）构建八叉树cloudB4）打印数据cloudB在cloudA的基础上新增的节点；TestCode : examples/official/octree/octree_change_detection.py
kdTree支持 xyz、xyzi的 K近邻搜索，不支持半径近邻搜索 Octree支持 xyz的K近邻搜索，半径近邻搜索；不支持xyzi；
如下图，更清晰一些：
KdTreeOctreexyz xyzi xyz xyzi K近邻搜索支持支持支持不支持半径近邻搜索不支持不支持支持不支持