应用区域生长（Seeded Region Growing）算法提取2D激光中的线段数据
0 Background
本文是针对于 **《A line segment extraction algorithm using laser data based on seeded region growing》**进行的算法理解记录，算法的思想方法主要来源于该文章。
文章中针对于流行的图像线段分割方法Split-and-Merge中存在的线段误分割问题（如上图所示），提出了基于区域生长（Seeded Region Growing, SRG）的算法来分割线段。该SRG算法流行于图像处理领域，是图像分割技术的一种。文中为了应用于2D激光数据的分割，进行了前后阶段的处理。
1 区域生长算法(Seeded Region Growing, SRG)
区域生长的基本思想是将具有相似性的像素集合起来构成区域。
首先对每个需要分割的区域找出一个种子像素作为生长的奇点，然后将种子像素周围邻域中与种子有相同或相似性质的像素合并到种子像素所在的区域中。
而新的像素继续作为种子向四周生长，直到再没有满足条件的像素可以包括进来，一个区域就生长而成了。
区域生长算法的基本步骤如下：
- 针对于点集N，获得第一个未检索的点P(x,y)
- 针对于点P检索其4邻域或8邻域点C,如果符合检索条件，则可将改点C分配进区域中，并将点C压入待检索栈St中。
- 从St中弹出点并作为P重复步骤2.
- 当St为空时返回步骤1
- 当点集N均被检索后算法完成。
2 SRG应用于2D激光数据的线段提取
2D激光数据中的线段提取不同于图像中的分割，其中有对拟合线段的参数估计、噪声或分离点的处理、重合部分的处理等。因此，文章中提出了几个方法来解决这些问题。
2.1 拟合线段的参数估计
对SRG应用于激光数据来说，首先要解决拟合线段ax+by+c=0中的参数估计问题，也就是“种子如何生成”的问题。文中提出了一种基于全局检索的方法，其中包含了两种对线段的判定辅助：点与线的距离和点间距离检查。算法描述如下：
- 对于点集N中的子点集Sub(i,j) 进行线段拟合求出（a,b,c）的参数，其中 Sub(i,j) 表示点集的范围是第i点至第j点。
- 针对于 [i,j] 中的点检测点与直线的距离，如果大于给定阈值则break
- 针对于 [i,j] 中的点检测点与点的距离，如果大于给定阈值则break
- 经过检测则返回Seed点集 Sub(i,j)。
其中，步骤3是针对于激光点的一个预测，某些点因为短距离扫描的夹角导致点间距过大，算法中采用了一个预测检验方式，如下图所示：
算法中用红线上的点作为predict 点来检测点点间距。
2.2 区域生长
算法思想相似与1中的介绍，对于不同 Sub(i,j) 进行邻域点检测，看是否可以分类入直线，也即生长过程。
2.3 连接区域处理
显而易见，2.1中的情况容易将本不应该多分开的线段分成两类，也就是参数敏感。文章中对相邻线段如果有邻接区域进行了处理和融合，整合了长线段分类性能。
2.4 终点检测
针对于划分好的直线，文章中的算法通过检测垂直于直线 ax+by+c=0 的点来确定终点。
3 实验结果
文章中提出的算法在效率和准确率上都优于流行的Split-and-Merge算法，如下图所示：
红色为Split-and-Merge算法的时间消耗，蓝色线为该算法的时间消耗。
算法的代码共享如下，需要可以取用，适用于Ros下操作。
链接：https://pan.baidu.com/s/1-P6lDIxQ1tZhvOIMSq35LA
提取码：yi4d
