离散激光脚点点群分割

6.3.2　离散激光脚点点群分割

机载激光雷达测量所获得的激光脚点的分布并不规则，在三维空间的分布形态呈现随机离散的数据点“点云”(Points Cloud)。在这些点中，有些点位于真实地形表面，有些点位于人工建筑物(房屋、烟囱、塔、输电线等)或自然植被(树、灌木、草)。从激光脚点数据点云中提取数字地面高程模型(DTM/DEM)，需要将其中的地物数据点去掉，即滤波。机载激光雷达测量所获得的离散激光脚点点云经过滤波处理后分成两类，一类是地面上的激光脚点;一类是地物上的激光脚点。如果对地物脚点进一步分类，又可分成不同种类地物的激光脚点，如植被上的激光脚点、建筑物上的激光脚点等。如果要进行地物提取和建筑物重建等就需要对地物激光脚点的数据点云进行分类或分割，区分植被数据点和人工地物点，以提取城市建筑物数据点阵系列，这就是所谓的机载激光雷达测量数据分类(分割)。目前，分割激光脚点的方法主要有基于已有的平面GIS数据、基于高程纹理以及基于多光谱数据等手段。但这些方法有时并不是适用于所有场合，如没有现成的平面GIS数据或多光谱数据，那么对应的方法就不能用。而基于高程纹理的方法对于成片的房屋区域，该法不能将每个房屋的点群分割开来。在城区，用机载激光雷达测量激光脚点数据进行建筑物三维重建时，通常需要将每个建筑物上的激光脚点提取出来，即从建筑物群的点云群中分离出属于每个建筑物的点云，此时上述方法就不适用了。

将滤波分类后得到的建筑物的点云垂直投影到平面可形成如图6-9所示的二维点阵。从图6-9可以看出，每个建筑物的激光脚点分别聚集在一起，属于不同建筑物的点阵片彼此分开。通常可以采用聚类分析的方法来进行单个建筑物点群的分割。

(1)聚类分析法

聚类分析主要用于在没有先验的类别标准情况下将样品进行分类的场合，包括系统聚类法、动态聚类法、分裂法、最优分割法等。其中系统聚类法是聚类分析中最为常用的一种聚类分析方法，它的基本原理是:首先将一定量的样品各自看成一类，根据样品的亲疏程度，将亲疏程度最高的两类进行合并。然后考虑合并后的类与其他类之间的亲疏程度，再进行合并，重复上述过程，直至将样品合并为不同的类。衡量样品之间的亲疏程度的指标有距离和相似系数两种。分割建筑物群的激光脚点点云，在聚类分析时，衡量其亲疏程度的指标是距离。其基本原理是:首先将每个点看成分别属于不同的房屋，求出任意两点之间的欧氏距离，找出其中最近的两点，如果它们间的距离小于某个阈值，则将这两点合并成属于同一个房屋，然后再求这个房屋与其他房屋脚点间的距离。重复以上过程，直到最近两点的距离大于阈值为止，则建筑物群点云就被分成一个个的房屋。聚类分析算法如下。

第一步，点P₁，P₂，…，P_n各视为一类，则有n类G₁，G₂，…，G_n，计算距离矩阵为:

图6-9　建筑物群激光脚点地面投影点阵

式中，d_ij表示i、j两点之间的距离。

第二步，记，如果d(k，l)小于阈值，则将G_k与G_l类合并成新类G_n+1，否则算法结束。

第三步，重新计算距离矩阵，得新矩阵D⁽¹⁾，返回第二步。

可以看出，从理论上来讲，建筑物群点云的分割实质上就是一个聚类分析的问题，以上算法是完全适用的。但是，如果简单地使用聚类分析法来分割建筑物群，其运算效率非常低。目前，机载系统提供的激光脚点的密度越来越高，有些系统能达到每平方米几十个激光脚点，激光脚点点云数据都是几十万个点以上，采用上述方法进行分割，每次循环都要进行庞大的距离矩阵计算，普通CPU的PC机将难以胜任。下面提出一种新的方法来分割成片的房屋区域的激光脚点点群，即“扫描带法”，该方法能克服聚类分析法的缺陷。

(2)扫描带法

将建筑物激光脚点点云垂直投影到xy平面可形成如图6-9所示的片块状的点阵，且投影后的平面脚点和空间脚点一一对应。将建筑物群点云的平面点阵在y方向上由小到大排序，设定阈值trd，其值应比测区内激光脚点的平均间隔稍大一点。从y值最小的点开始，设其y值为y₀，提取出y∈［y₀，y₀+trd］的点，这些点组成一个点带，然后对这个点带中的点按x坐标进行排序，按该点带相邻点之间的间距是否大于阈值trd，可将此点带分成若干段，每段应分别属于不同的房屋。存储每个点段的x坐标区间，并与上一次得到的每个房屋点集的x坐标区间进行比较，如果两个区间相交叉，则表明这段点集属于该房屋，将这些点加入该房屋，并修改该房屋的x坐标区间;如果该区间不与任何已有房屋的x坐标区间相交叉，则新建一个房屋点集;如果一个x坐标区间与多个已有房屋点集的x坐标区间相交叉，则这多个房屋点集属于一个房屋，将这些房屋合并。如此重复，继续寻找y∈［y₀+trd，y₀+2trd］中的点，直到所有点都确定出其归属。当然，区间相交只是确定点段归属的一个条件，还必须要两区间的y坐标差小于trd，如果不满足这个条件，则可判定剩余点中已没有该房屋中的点。

将一个房屋点云用如下结构体来表示:

struct Building

{

　　　　int num;　　　　　　　　//记录房屋点云的点数

　　　　PFOOTPOINT pfntPoints;//记录房屋点云中激光脚点的三维坐标

　　　　double lowx，highx，highy;//分别表示x区间的下限、上限，y的最大值

};

“扫描带法”的具体算法如下。

第一步，将原始点集按y坐标的数值从小到大进行快速排序，存放在数组dot中，令i=0，设定阈值trd。

第二步，提取y∈［dot［i］.y，dot［i］.y+trd］中的点组成一个点带，按x坐标由小到大排序，按相邻点x坐标之差大于阈值trd，将该点带分成若干段，存贮每段的x坐标范围(x₀，x₁)。

第三步，对每个点段，同已有的房屋点集进行比较，确定各段的归属。若Building.highy+trd＜dot［i］.y，表明剩余的点集中已没有该房屋中的点;若Building.highy+trd≥dot［i］.y且(Building.lowx，Building.highx)与(x₀，x₁)相交，即含有公共区间，则表明该点段内的点属于这个房屋，同时置Building.lowx=x₀，Building.highx=x₁;Building.highy=dot［i］.y+trd;若(x₀，x₁)与多个房屋点集相交，则这多个房屋合并成一个房屋，同时置Building.lowx=x₀，Building.highx=x₁，Building.highy=dot［i］.y+trd;若没有任何一个房屋点集与(x₀，x₁)相交，则新建一个房屋点集，同时置Building.lowx=x₀，Building.highx=x₁，Building.highy=dot［i］.y+trd。

第四步，若全部点已确定归属，则算法结束;否则，令i为剩余点中y坐标最小的一个点的下标，返回第二步。

算法流程图见图6-10。

用该方法在Pentium 4 Processor 1.8GHz的PC机上对图6-9所示的建筑物群激光脚点点云数据(约几万个激光脚点)进行分割，耗时不到1s。而采用聚类分析法对相同的激光脚点点云数据进行分割，在相同的运行平台环境下，耗时数小时。当然，上述方法主要是用于对滤波以后获得的成片建筑物的激光脚点点云的分割处理，而不能直接对原始的没有经过滤波处理的激光脚点点云数据进行分割。

在城市及其郊区用机载激光雷达测量技术建立数字城市模型和建筑物三维重构时，采用上述方法比较有效。但前提是，在分割之前，需借助于已有的滤波算法，先将地面上的激光脚点滤掉，然后还要将植被上的激光脚点分离出来，而剩下的是成片的建筑物上的激光脚点。尽管投影到xy平面上的激光脚点直观上看是一块一块分隔开的(见图6-9)，但计算机并不知道哪个点属于哪个房屋，必须借助于一定的算法才能将属于不同房屋的激光脚点点群分割开来。扫描带法的核心是认为每栋房子或建筑物之间有空隙或间距(见图6-9)。当然，由于扫描带法是根据预先设定的阈值来进行分带和分段的，为了分割可靠，使用该方法需尽量满足房屋间距大于五倍以上的激光脚点平均间距的条件。

图6-10　扫描带法的算法流程图

聚类分析法分割建筑物激光脚点群，每次循环都要进行庞大的距离矩阵计算，运算的时间长。当然，聚类分析法的通用算法根据实际情况是可以优化的，辅以排序和分网格查找可以大大提高运算的速度。比较而言，扫描带法的优势非常明显，它完全不同于聚类分析的思路，避免了大量反复的点位间距离的运算，仅仅是x、y坐标的大小比较，运算速度快，算法的实现也相对容易。扫描带法可用于同类特点的成片建筑物的激光脚点点群的分割，是一种通用的算法。但是，由于扫描带法要根据预先设定的阈值来进行分带和分段，因此，使用该方法时，要保证激光脚点有足够的密度，且有足够的房屋间距。