A robust statistics approach for plane detection in unorganized point clouds

Robust plane detection §

Split phase §

1. 使用 BVH 树拆分点云成尽量小的 patch
2. 小 patch 因为噪声的存在，可能不被判定为一个平面
3. 回溯的时候，如果小 patch 不是平面，测试父亲 patch 是不是平面，此时噪声可能占总点云数目比例变小了，容易符合平面判定

Robust planarity test 鲁棒平面测试 §

Robust Statistics

平面定义 $(C,N)$ $C$: 平面上各坐标轴中点 $N$: 方向向量中点

1. Plane-sample distance test §

2. Plane-sample normal deviation test §

3. Outlier percentage test §

Growth phase §

1. 对 point 建立连接图
2. 将检测得到的小 patch 吸收周围 point 进行生长（基于 robust statistics 的区域生长）

   Grow §

   函数入口

   1. 根据噪声度量 min_normal_diff_ 从小到大排序
   2. queue 取出噪声最小的 patch，每个 patch 和 point 只使用一次
   3. 判断内点
      1. patch 和 point 法向量点乘大于 min_normal_diff
      2. 距离小于 max_point_dist_

   Link to original

Merge phase §

patches 合并

1. 三个指标判断两两 patch 是否应该合并
2. 并查集合并 patch

   Merge §

   函数入口 对所有 patch 建图，计算它们间的相关关系

   1. 首先判断法向量点乘差异是否满足阈值
   2. 遍历所有平面 patch -> 平面包含的点的 index -> 每个点的 kdtree 的邻居
      1. plane_points 从 point 到平面 patch 的索引
      2. 找到邻居点所在平面
      3. 如果两平面 patch 边缘上的点满足 kdtree 能互相找到，对两平面进行鲁棒共面检测
   3. 并查集计算
      1. 默认顺序建立并查集树，此时根节点没有物理意义，任意 patch 都有可能是根节点
      2. 使用 largest_planes 记录成为了根节点的 patch 叶子节点里面包含 point 最多的 patch
      3. 后续合并就使用 largest_planes 指向的点最多的 patch 作为初始，合并其余的 patch
   4. 合并共面 patch 根据现有点重新计算 max_point_dist_ 和 min_normal_diff_ 的值

   Link to original

Iterative grow-merge procedure §

如果有合并更新，就重新进行 Growth phase 和 Merge phase