在许多机器人应用的领域能够实时在三维点云中进行平面提取是非常困难的。在论文中提出了一个算法能够在类似Kinect 传感器采集到的点云进行实时可靠的多平面的检测。具体的算法一共有三个步骤第一步生成图模型每一个节点都代表的是一个点集每条边代表点集之间的关系第二步在构建好的图模型上利用层次聚类的方法进行点集的的融合直到平面拟合的均方误差超过设定的阈值第三步使用像素级别的局域增招对上一步提取到的平面进行优化。论文中演示了该算法在640x480的点云中以超过35Hz的帧率对场景中所有主要的平面进行可靠的检测。主流的几类平面提取的方法有1RANSAC-based methodslong computation time2Region-grow-based methodspixel、voxel、line3turn into normal space compute the distance between the point cloud and the original4normal estimation5Graph-based segmentationpaper中也是使用图来表达数据之间的关系但是还是与之前图模型的方法有一定的区别的1没有RGB的信息2不用对每个点进行法线估计3对节点与节点之间的边使用动态的权重paper中还提到线回归和3D点云的平面提取的区别主要有两点1节点是没有重叠性的节点与节点之间是没有共同的点的2尝试融合的次数会高于线回归因为线回归只要左右两端进行融合尝试就可以了但是在三维点云中至少有上下左右四个方向的融合尝试如果是 比较大的聚类融合尝试的此时可能会更加多一些。下面就对算法的三个步骤进行详细的描述1.图模型的初始化将图像中的点云均匀的分成H×W为一个节点例如图像为10×10HW5那么就分成10/5×10/54总共分成四块也就是有四个节点。但是根据paper中为了更好的使用AHC层次聚类需要移除下面几类节点和它们对应的边1节点对应很高的MSE2节点缺少数据信息传感器的限制3节点包含的深度不连续4节点在两个平面的边界上值得一提的是针对这种非重叠的节点默认是在一个平面上的所以也就不需要对每个节点中的点进行法线估计这会很大的提高整个算法的速度。2.层次聚类AHC1首先先建立一个最小堆的数据结构使得能够更有效的找到有最小均方误进行融合2再次计算融合后的平面拟合均方误差找到获得均方误差最小的对应两个节点3如果均方误差超过一个预先设定的阈值非固定一个平面的分割节点就算是找到了把它从图中提取出来否则就把这两个节点融合好重新加到构建的图中对建立的最小堆进行更新4重复上述2、3操作。因为最小堆建立可以被看成是一个近似的完全二叉树所以在建立最小堆的复杂度是线性时间复杂度而在排序的时候就是一个O(nlgn)O(nlgn)O(nlgn)的时间复杂度3.分割优化在步骤2层次聚类后只能算是比较粗糙的分割而且在第一个步骤中我们舍弃了很多节点所以在最后的优化时我们是基于像素点的优化主要是有下面三种类型1在边缘处会产生锯齿状的分割会使得少量异常点包含在估计中通过腐蚀边界区域优化这种现象2未使用的数据点就近分类未使用的点周围平面3过度分割在特别小的图中通常是小于30个节点再次进行AHC。参考文献[1]Feng C, Taguchi Y, Kamat V R. Fast plane extraction in organized point clouds using agglomerative hierarchical clustering[C]// IEEE International Conference on Robotics and Automation. IEEE, 2014:6218-6225.