open3d八叉树：Octree

Open3d快速上手💎点云对象详解

open3d实现

oc树是一种空间栅格化方法，其思路来自于二分法。

以一维空间举例，就是对一条线段不断地二分，得到一系列的子线段，如果子线段中包含的元素大于2，那么就继续分割，直到所有子线段中至多只有一个元素为止。

就一维而言是二分，二维空间是四分，三维空间就是八分了，故而是八叉树。考虑到本文主要介绍open3d中的八叉树，故而将更详细的解释放在后面。

在open3d中，提供了Octree类用以创建八叉树，其创建方法为先建立对象，再注入点云数据。

pcd = o3d.io.read_point_cloud("rabbit.pcd")
octree = o3d.geometry.Octree(max_depth=6)
octree.convert_from_point_cloud(pcd, size_expand=0.01)
o3d.visualization.draw_geometries([octree])

直观感受一下大致是这种

其中，参数max_depth可以理解为八分的最多次数。这个东西很微妙，如果不设置，当一个小区域内有大量点的时候，就会不断地分割下去，很浪费性能。size_expand是一个微小的膨胀系数，从而让每个方块把点包裹进去。

除了通过点云生成八叉树，也可以通过体元生成八叉树

vxs = o3d.geometry.VoxelGrid.create_from_point_cloud(pcd, voxel_size=0.01)
octree = o3d.geometry.Octree(max_depth=6)
octree.create_from_voxel_grid(vxs)
o3d.visualization.draw_geometries([octree])

其绘制结果和上面的图是一样的，故不再展示。

为了让这棵八叉树更加清晰，可以对点云上色

import numpy as np
colors = np.random.rand(len(pcd.points), 3)
pcd.colors = o3d.utility.Vector3dVector(colors)
octree = o3d.geometry.Octree(max_depth=5)
octree.convert_from_point_cloud(pcd, size_expand=0.01)
o3d.visualization.draw_geometries([octree])

效果为

原理

八叉树(octree)是一种空间中的栅格化方法，为了更直观地理解八叉树的思想，可通过其二维形式——四叉树来进行说明。仍以六个数据点作为研究对象：{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}，如果以$[0,10)$为坐标空间，那么通过对这个空间四等分，可得到下左图

	=》

令所有的分割都是左闭右开的，那么被分割后的四个区间中，除了右下角的方块包含三个点之外，剩下三个方块都只有一个点。只有一个点的方块显然就没法继续分割了，而第四个方块则可继续分割，得到右图。

这样，右下角的方块被继续分成了四个小方块，且每个小方块的元素都不超过一个，所以无法继续再分，四叉树也就完成了。

八叉树就是按照同样的逻辑，对空间进行等间隔分割，由于三维坐标系有8个卦限，故而每一次都将产生8个立方体，如图所示。