【开源方案共享】无序点云快速的线段分割算法

作者：Xiaohu Lu, Yahui Liu, Kai Li

编译：particle

本文提出了一种基于大规模无序点云的三维线段检测算法。与传统的方法先提取三维边缘点后在拟合三维线段的算法相比，本文提出了一种基于点云分割和二维线段检测的基础上，能够快速的实现三维线段检测算法。在输入无序点云的情况下，对三维线段进行三步检测。首先，通过区域生长和区域合并将点云分割成三维平面。其次，对每个三维平面，将其所属的所有点投影到平面上形成二维图像，然后进行二维轮廓提取和最小二乘拟合得到二维线段。然后将这些二维线段重新投影到三维平面上，以获得相应的三维线段。最后，提出了一种剔除异常点和合并相邻三维线段的后处理方法。在多个公共数据集上的实验证明了该方法的有效性和鲁棒性。

更多的结果和C++源代码的公开在https://github.com/xiaohulugo/3DLineDetection

主要贡献

文章提出的方法仍然属于图像的范畴，但是针对基于图像方法的不足，提出了一种针对三维点云数据的更为快速的线段检测的方法，该方法主要包含了三个部分：

（1）点云分割：通过区域生成的和区域合并的方法，将输入的点云分割成三维平面。

（2）基于平面的三维直线的检测：对于每个点云平面，所有属于该平面的点云投影到平面上形成二维图像，然后基于二维图像进行轮廓提取和最小二乘拟合，得到每个平面的二维线段。最后将这些二维线段重影映射到三维平面上，就可以获得三维线段点云数据。

（3）后处理：通过场景的三维结构信息，去除三维平面和三维线段的异常点云，最后合并所有三维线段点云数据。

论文步骤图集

模块一点云分割，该模块主要有三个步骤

• 点云法向量计算
• 区域生成
• 区域合并

模块二基于分割后平面的三维线段的提取，步骤有

• 3D-2D的投影
• 2D图像的线检测（检测方法是LSD参考文献【1】）
• 2D-3D的映射

模块三后处理，噪声去除

• 去除噪声平面点云
• 去除噪声线段点云
• 所有线段点云合并

实验结果与总结

本文提出并证明了一种简单有效的大规模无组织点云三维直线检测算法。该方法以点云分割和二维直线检测为基础，采用后处理方法去除异常点。与传统的基于边缘点的方法不同，该方法实现简单，速度快（10万个点云40秒）。由于我们的方法是基于点云分割的，所以我们的方法的一个失败案例是在曲面上，在曲面点云实现平面的分割效果是不尽人意的。尽管如此，该方法对于结构场景还是非常有效的。

参考文献

【1】R. G. von Gioi, J. Jakubowicz, J.-M. Morel, and G. Randall, “LSD: A fast line segment detector with a false detection control,” IEEE Transactions on Pattern Analysis and Machine Intelligence.