algoDetectPlane - 平面探测算法 - A Robust Statistics Approach for Plane Detection in Unorganized Point Clouds

Posted on Edited on

1 主流平面检测算法：

1.1 HoughTransform算法

  • 1 对于每个点：xyz，使用点法式表示过该点的平面：np + d = 0; n为法向，n可以用极坐标写成θ φ的向量，那么平面由三个变量可以确定
  • 2 对于点xyz，我们离散遍历所有的θ φ，可以得到对应的d，那么我们以θ φ作为xy坐标，d作为z坐标，可以画出来一个曲面(曲面上一个点代表一个经过xyz的平面)，代表所有可能经过xyz的平面
  • 3 然后对于所有其他点，我们同样可以找到对应的曲面，我们求出来最多曲面参与的焦点，就视为检测出来的平面
  • 4 复杂度：o（n * num(θ) * num(φ)），后面两个分别是离散遍历θ φ的个数

1.2 RA(andom)SA(mple)C(onsensus)算法

  • 1 选取一小集合，估计出来一个平面（比如说随机的三个点）
  • 2 然后评估能被这个平面拟合的点的个数，也就是inlier的个数
  • 3 在1，2中评估出来的所有的初始集合中，选择inlier数最大的那个对应的平面，即为最终结果
  • 4 复杂度：o(I) * o(n) = o(In)， I是选出初始集合的个数，n是点的个数，因为你需要判断某个初始拟合出来的平面的inlier的个数不就是去遍历所有的点嘛

1.3 region growing 算法

A Robust Statistics Approach for Plane Detection in Unorganized Point Clouds算法详解：

2 A Robust Statistics Approach for Plane Detection in Unorganized Point Clouds算法详解

2.1 平面检测

2.1.1 划分点云（split phase）

大致分为如下几个步骤：

  • 1 递归将点云切分成8叉树
  • 2 对于足够小的节点(比如至少是第3层的8叉树)，进行planar patch(平面patch)探测
    • 2.1 如果当前节点能够形成平面，对plannarPatch滤除外点，然后加入到结果中
      具体实现如下代码：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      bool PlaneDetector::detectPlanarPatches(Octree *node, StatisticsUtils *statistics, size_t minNumPoints, std::vector<PlanarPatch*> &patches)
      {
          if (node->numPoints() < minNumPoints) return false;
          node->partition(1, minNumPoints); // 将当前节点划分为更细节点
          bool hasPlanarPatch = false;
          for (size_t i = 0; i < 8; i++)
          {
              if (node->child(i) != NULL && detectPlanarPatches(node->child(i), statistics, minNumPoints, patches)) // 对每各子节点进行patch探测
              {
                  hasPlanarPatch = true;
              }
          }
          if (!hasPlanarPatch && node->octreeLevel() > 2) // 足够小的子节点并且没有patch
          {
              PlanarPatch *patch = new PlanarPatch(pointCloud(), statistics, node->points(), mMinNormalDiff, mMaxDist, mOutlierRatio);
              if (patch->isPlanar()) // 如果patch构成平面，则滤除外点
              {
                  patches.push_back(patch); // 将当前patch加入到探测出来的所有patch
                  hasPlanarPatch = true;
              }
              else
              {
                  delete patch;
              }
          }
          return hasPlanarPatch;
      }

2.1.2 路棒的平面性测试

那么对于足够小的节点进行palnar检测是如何做的呢？(也就是robust planarity test)
pca会受到外点影响，然后robust pca则太慢了，所以：

  • 1
  • 2
  • 3