结合超体素与区域增长的LiDAR点云屋顶面分割

李明星，任高升，吉文来

(1.江苏省盐城技师学院，江苏 盐城 224000；2.南京工业大学，江苏 南京 211816 )

0 引 言

机载激光雷达(airborne light detection and ranging，LiDAR)是一种对地探测新技术，能够快速、精确地获取地物位置信息和高度信息，为构建三维数字城市特别是建筑物重建提供了新的手段[1-2]。屋顶面作为建筑物屋顶结构的基本组成元素，对其快速准确提取是基于机载LiDAR点云建筑物三维模型重建的关键步骤[3]。

由于机载LiDAR点云分布不规则且建筑物空间结构复杂，从建筑物LiDAR点云中高精度分割屋顶面仍面临较大挑战。相关学者对此进行了研究，主要分为聚类法、3D-Hough变换、随机抽样一致性(random sampling consensus，RANSAC)法和区域增长法等。聚类法[4]根据点云间距和点云密度等相似性测度进行聚类，提取结果较为稳定，但易受聚类参数和聚类策略的影响，导致过提取或漏提取；3D-Hough[5]通过在参数空间内进行简单累加统计得到参数聚类中心，但采样大小会影响特征提取精度，且离散化会增加计算量；RANSAC算法[6]通过迭代方式从一组数据样本中估算数学模型参数，具有较好的稳健性，但提取结果易出现伪平面，当数据复杂时，算法效率较低。区域增长法[7-8]简单易行，但参数难以设置且过度依赖局部特征的计算精度，增长过程易受噪声影响。

基于上述研究，提出一种结合超体素和区域增长的建筑物屋顶面点云分割方法。利用超体聚类算法将点云过分割为超体素，基于超体素的光滑性和表面几何特征进行区域增长，实现屋顶面点云提取。结合某地区建筑物LiDAR点云数据进行实验，验证了该方法的有效性。

1 超体素生成

超体素是由若干体素构成的集合，超体聚类算法将点云过分割为若干超体素并研究超体素之间的关系[9]。利用八叉树组织初始点云，结合相邻体素间欧氏距离和法向量信息得到特征距离并构建体素邻接图，基于流约束的聚类算法将体素划分至距离最近的种子体素构成超体素。

1.1 距离度量

Cpi·γi=λi·γi(i=0,1,2)

(1)

(2)

式中，λi为Cpi的特征值。设λ0<λ1<λ2，则邻域点集最小特征值λ0对应的特征向量γ0即为体素vi的法向量ni，Kpi为点pi的曲率。设点云的视点为vp，体素vi的中心点为Si，则对各点的法向量方向进行一致性定向[11]：

ni·(vp-Si)>0

(3)

结合点云数据的法向量信息和空间距离度量体素间的相似性，依据法向量角度差异、曲率特征和欧式距离计算种子体素及其邻接体素间的特征距离：

(4)

式中，DC为体素间的曲率变化值，Cmax为体素邻域范围内的最大曲率值，DS为体素间欧氏距离，Dθ为互为邻接关系的体素间法向量的点积，λC、λS、λθ分别为DC、DS、Dθ的权重。由于两种不同空间的距离尺度不一，对DC、DS和Dθ进行归一化处理得到邻接体素间的特征距离，以其作为体素邻接图中边的权重构建三维点云26邻接图[12]。

1.2 超体素聚类

利用流约束的聚类算法分割体素数据，算法具体过程为：

(1)初始化k个种子体素集合SSi={SS1,SS2…SSk}。

(2)搜索种子体素邻域内的体素vi与种子体素SSi之间的特征距离，若在阈值范围内，则将vi划分至Ci中。

(3)更新聚类集合Ci的中心体素：

(5)

(4)重复上述步骤，直至聚类集合的中心体素SS不再变化，聚类集合Ci即为超体素。

算法流程如图1所示。

图1 超体素生成算法流程图

2 结合超体素的区域增长算法

通过分析超体素结构特征和区域增长算法[12]的特性，提出一种基于超体素和区域增长的屋顶面点云分割方法。通过拟合平面残差值选择种子超体素，归一化法线和点特征直方图(Point Feature Histogram，PFH)度量邻接超体素间的相似性，基于区域增长算法聚类超体素提取屋顶面片点云。

2.1 相似性特征度量

超体素内包含大量的体素，对一个或几个体素计算得到的属性特征无法代表整个超体素，因此，引入PFH估计超体素的表面几何特征并利用法线方向变化确保分割结果的光滑性。在128维空间下，利用法线方向和PFH建立超体素的特征向量：

F=[x,y,z,PFH1…125]

(6)

式中，x,y,z为超体素法向量的坐标，PFH1…125为125维空间的PFH向量。结合超体素光滑性和几何特征约束，归一化法线和PFH向量得到归一化距离S，将其作为种子超体素与邻接超体素之间的相似性度量。

(7)

式中，σN为法向量的权重，σPFH为超体素PFH的权重，σN+σPFH=1，SN和SPFH分别对应超体素法向量和PFH特征向量夹角的余弦值。

2.2 基于超体素的区域增长

基于超体素的区域增长算法需要选取种子超体素进行初始化。仅利用超体素质心点曲率信息无法准确度量整个超体素的结构特征，因此，结合超体素结构特征，改进区域增长算法的种子选取策略。

基于最小二乘法对每个超体素进行平面拟合，计算对应的残差值并利用残差值判断超体素表面的近似曲率，确定初始种子超体素。选择残差值最小的超体素作为当前区域初始种子，以初始种子超体素为中心进行区域增长。设定固定阈值rth筛选邻域内的候选种子超体素继续增长，保证了分割算法可以较好地处理边界区域。

综上所述，结合超体素的区域增长算法具体流程如图2所示：

图2 基于超体素的区域增长算法流程图

(1)构建KD-Tree空间索引，利用最小二乘法对每个超体素进行平面拟合并计算相应的残差值，根据残差值对所有超体素进行排序，选择残差值最小的超体素作为初始种子超体素。

(2)若当前种子超体素集合U非空，选择初始种子超体素对当前区域开始增长，设定固定的残差阈值rth筛选当前种子邻域内的候选种子集合。

(3)搜索初始种子超体素的r半径邻域，根据归一化距离S度量邻接超体素之间的相似性，将阈值Sth范围内的邻接超体素添加到当前分割区域。

(4)对初始种子邻域超体素判断结束后，从U中移除该种子超体素，选择邻域内的候选种子超体素继续对当前区域进行增长，若U为空，则停止当前区域的增长。

(5)选取新的初始种子超体素，重复上述步骤直至遍历所有的超体素数据。

3 实验分析

为了验证算法对屋顶面的提取效果及适应性，从ISPRS提供的City Site机载LiDAR数据集中(图3)选取一块包含11栋建筑物的LiDAR 点云进行测试。实验点云单个建筑物面积相对较大且包含的屋顶面个数较多，建筑物屋顶面的大小、形状差异较大。

图3 实验区点云数据

采用相关文献[13]定义的建筑物屋顶面提取质量评价体系，其中屋顶面的提取率为：

(8)

式中，S为实验选取的建筑物屋顶面，S*为算法分割获得的建筑物屋顶面。计算算法提取率时,将面积大于5 m2的屋顶面为主屋顶面，其余为次屋顶面[13]。算法需要设置4个参数，分别为体素半径Rv，相邻超体素间距离Rs，区域增长邻域搜索半径r和法向量差异阈值，Rv、Rs和r的设置均与点云密度ρ有关：

(9)

式中，n为点云中离散点的数量。屋顶面点云分割实验结果如表1所示。

表1 屋顶面分割统计结果

由表1可知，利用传统区域增长算法得到的主屋顶面、次屋顶面和所有屋顶面的提取率仅为80%、41.2%和76.2%。采用区域增长法进行屋顶面分割，较大面积的屋顶面分割效果较好，但在边缘处及屋顶面相交处，由于局部特征计算的不稳定性且难以找到合适的增长阈值，出现了邻近屋顶面被合并或者同一屋顶面被分割的现象；基于超体素的区域增长算法，得到的屋顶面提取率较高，主屋顶面、次屋顶面和所有屋顶面的提取率分别为93.3%、52.9%和87.7%。次屋顶面仍存在漏检的情况，主要原因是，次屋顶面与相邻面积较大的屋面近似平行且高差较小，算法易将屋顶面边缘点优先分配给相邻面积更大的屋顶面。与传统区域增长算法相比，本文方法屋顶面提取率较高，分割的屋顶面更加完整，在屋顶面拓扑关系复杂的情况下仍能取得较好的分割效果。

4 结 语

针对传统区域增长算法的不足，提出一种基于超体素的区域增长屋顶面点云分割方法。将点云分割为超体素，结合超体素的光滑性和几何特征约束进行区域增长，提取屋顶面片点云。实验结果表明，该方法的屋顶面提取率高且适应性好，对复杂建筑物屋顶面仍有较好的分割效果，为建筑物精细建模提供了基础。但本文算法参数较多且需要根据点云密度进行设置，如何对不同类型点云数据自适应设置参数将是下一步的研究内容。