open3d中的kd树详解

k-d树是一种点云划分方法，其基本思路是，对方差最差的维度进行二分分割，从而得到两个子集，再对这两个子集进行相同的操作，直到所有子集的元素个数低于设定值。

考虑到大部分使用open3d的都不算是初级用户，故而先介绍open3d中提供的接口，而后对kd树的原理进行说明。

open3d实现

import open3d as o3d
pcd = o3d.io.read_point_cloud('rabbit.pcd')
# 通过点云创建kd树
kdt = o3d.geometry.KDTreeFlann(pcd)

kd树，和其他树一样，有一个重要的功能就是提高索引速度，将原本的$O(n)$复杂度降低到类似$O(\ln n)$的水平。KDTreeFlann针对索引半径、索引范围，主要提供了三种索引方式

# 通过距离和最大点数来索引
search_hybrid_vector_3d(query, radius, max_nn)
# 通过点数索引
search_knn_vector_3d(self, query, knn)
# 通过半径索引
search_radius_vector_3d(self, query, radius)
# 综合索引方法， search_param为专门为kd树提供的参数对象
search_vector_3d(self, query, search_param)

对于这四种3d方法，都有一个与之对应的xd版本，可以用于更高或者更低维度的kd-tree的索引。

下面演示一下knn和半径搜索的方法

pcd.paint_uniform_color([0.5, 0.5, 0.5])
k, idx, _ = kdt.search_knn_vector_3d(pcd.points[250], 200)
for i in idx:
    pcd.colors[i] = [0, 0, 1]

pcd.colors[250] = [1,0,0]

得到结果如下

搜索返回的参数中，k即搜索到的点数，idx为点的序号。由于knn方法指定了搜索个数为200，故k=200。相比之下，radius方法返回的点数数目就不这么确定了

pcd.paint_uniform_color([0.5, 0.5, 0.5])
k, idx, _ = kdt.search_radius_vector_3d(pcd.points[250], 0.2)
for i in idx:
    pcd.colors[i] = [0, 0, 1]

pcd.colors[250] = [1,0,0]

最终得到k=8，由于点数过少，所以下面的图单独把兔耳朵放大

原理

考虑到演示方便，所以用二维空间中的数据来做一点说明，假设现有六个数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，如何能够通过这六个点将空间分割，就如下图一样。

当然上面这个图只是一种方案，或许还有其他的划分方式。

对此例来说，其分割步骤为

1. 计算x，y方向上数据的标准差，可得$s_x\approx 2.4,s_y\approx 2.1$，即$s_x>x_y$，所以先分割x方向的数据。
2. x轴方向的值为2,5,9,4,8,7，排序后为2,4,5,7,8,9，中值为7，所以先在$x=7$的位置画一条与y轴平行的线，这条线经过点(7,2)，将平面分成左子空间和右子空间。
3. $x⩽7$的左子空间，包含3个节点{(2,3), (5,4), (4,7)}；$x>7$的右子空间，则包含2个节点{(9,6)，(8,1)}。
4. 对左子空间和右子空间重复1过程，直到所有的点都画了线，最终就得到上图了。

而这个生成分割图的过程，也是生成kd树的过程，其树图为