翟月

(安徽电子信息职业技术学院 软件学院，安徽 蚌埠 233000)

建筑物的三维屋顶重构是三维建筑虚拟化的重要组成部分，准确地对屋顶进行重构对于诸如城市规划、应急响应和基于位置的服务尤为关键。但是，开发能够生成高精度建筑模型的计算机视觉系统是一项具有挑战性的任务。三维建筑重构中的关键步骤是从原始数据中检索到建筑对象边界的噪声，以避免噪声对建筑物的真实形状造成不良影响。大多数现有的研究采用遥感数据(如激光点云)实现建筑的自动重构。机载光探测和测距 (LiDAR) 扫描仪是主要的数据采集工具，它能够以高密度和精度快速捕获三维目标环境[1-3]。本研究设计了一个数据驱动的重构算法，使用建模线索提取和拓扑元素重构对给定对象进行调整，实现了从机载LiDAR数据重建三维屋顶模型。

1 三维建筑物屋顶重构

图1显示了从机载LiDAR点云数据生成三维屋顶模型的整体工作流程，该流程包括三个主要部分，即建模线索提取、拓扑元素重构以及正则化。建模线索提取是从一组标记为单个建筑物对象(即建筑物标记点)的激光点云中提取屋顶元素簇、线和外边界。然后，使用二元空间分割技术建立建模线索之间的拓扑关系。最后，对建筑物外部边界和屋顶多边形进行正则化。正则化过程结合了假设检验优化和最小描述长度框架。

图1 整体工作流程

1.1 同构类构建

生成三维屋顶模型的第一步是收集建筑结构的证据(即原始几何元素)。由于三维建筑屋顶模型可以由平面屋顶面和边缘表示，因此平面和线是描述建筑结构的重要证据。平面和线性建模线索具有不同的属性，可以分别从 LiDAR点云中提取。基于高度相似性和平面相似性，建筑点被依次分割成同构簇。然后，使用同构簇的边界点提取线性建模线索。

屋顶元素聚类将建筑物标记的点分割成具有层次结构的同构屋顶区域。城市地区的建筑屋顶是多层的组合，每一层都由各不同形状的平面和斜面组成。由于形状的复杂性，从整个建筑点直接提取同构区域可能会变得困难。为了降低复杂度，通过依次应用高度相似性和平面相似性，将建筑物标记的点分解为同构簇。

高度聚类过程：具有n个建筑物标记点的屋顶区域R={pi|i=1, 2,…,n}被分成m个高度簇R= {S1,S2,…,Sm}。每个点的高度相似性是在不规则三角网(TIN)中与其相邻的点测量的。首先选择高度最大的点作为种子点，然后应用常规的区域生长算法将相邻点添加到具有一定阈值(δh= 1米)的相应高度簇中。重复此过程，直到所有建筑物屋顶点都分配给高度簇。因此，高度簇满足以下属性R=S1∪…∪Si∪…∪SM，Si∩Sj= {} 。每个高度簇都包含一个或多个不同的屋顶平面。

平面聚类过程：基于平面相似性，每个高度簇被分解为k个平面簇Π= {π1,π2, . . . ,πk}。 采用主流的随机采样一致性(RANSAC)算法(如算法1所示)来获得平面簇：随机选择三个点作为种子点以生成初始平面；经过随机采样后，选择具有最大数量内点且与估计平面的用户定义公差距离小于ζ(ζ= 0.1米)的平面作为最佳平面。在前一次迭代中分配的点会在下一步中被排除。这个过程一直持续到高度簇的所有点都被分配到特定的平面簇中。

算法1平面簇聚类算法输入:S∈R,itremax,ζ输出:π1:初始化:i=0,π=ø;2:Whilei

1.2 建模线索提取

构建同构簇后，可以从其中提取线性建模线索。线性建模线索有三类：高度簇的外边界、相交线和每个高度簇内的阶梯线。

外边界提取：首先检测在TIN 结构中共享相邻高度簇的边界点，并选择其中一个作为起始边界点。随后测量与 TIN结构中前一个边界点相连的相邻边界点，通过选择逆时针方向的第一个边界点来确定下一个边界点。该过程一直持续到边界封闭。封闭的边界通过基于最小描述长度的正则化方法进行正则化。当在两个相邻的屋顶平面提取候选相交线时，如果候选线将平面的点集分开并且有足够数量的点靠近生成的线，则候选者成为有效的相交线。

相交线提取：通过两个相邻的屋顶平面提取交叉线候选。如果候选者将平面的点集分开并且有足够数量的点靠近生成的线，则候选者被接受为有效的交线。

阶梯线提取：不属于外边界或相交线的平面簇的边界点被视为阶梯线的候选点。 给定一个包含l个候选点的序列D= {c1,c2, . . . ,cl}，以类似于道格拉斯-普克 (DP) 算法(如算法2所示)的方式提取阶梯线。该过程从连接序列的第一个点和最后一个点的直线(c1cl)开始，然后递归添加距离大于用户定义容差的候选点。线段的每一段被认为是阶梯线。

算法2阶梯线提取算法输入:D,epsilon输出:D’1: maxH=0,index=0;2: fori<=ldo3: h=DisPointToLine(ci,c0,cl);4: ifh>maxHdo5: maxH=h;6: index=i;7: D’=ø;8: ifmaxH>epsilondo9: TempL=ø,TempR=ø;10: fori<=ldo11: ifi

1.3 拓扑关系重构

使用二元空间分割技术构建线索之间的拓扑关系。二元空间分割技术是一种分层划分方法，能以递归的方式将空间细分为具有超线的凸集。采用该方法从不完整的建模线索重建拓扑和具有正确几何结构的3D建筑屋顶模型。拓扑恢复过程包括划分步骤和平面合并步骤。在划分步骤中，通过将父区域划分为具有超线(线性建模线索)的两个子区域来生成分层二叉树。通过最大化由平面均匀性、几何规则性和边缘对应性组成的分区分数来实现分区优化。在平面合并步骤中，通过应用用户定义的阈值合并具有相似法向量角的相邻屋顶平面。合并过程一直持续到共面相似性测试无法接受任何平面为止。一旦所有多边形合并在一起，就可以通过收集二元空间分割树中的最终叶节点来重建三维建筑屋顶模型。

2 屋顶模型正则化

如前所述，从错误的建模线索中恢复无错误的三维屋顶模型是一项具有挑战性的任务。平行性、对称性和正交性等几何约束可以用作屋顶结构的先验知识，以补偿错误建模线索的局限性。然而，显示地施加约束在描述现实中出现的复杂建筑物方面存在局限性。因此，提出了一种隐式正则化，为描述更复杂的屋顶模型提供灵活性。所提出的正则化过程是基于最小描述长度框架中的假设检验优化进行的。

最小描述长度由模型复杂度和模型紧密度组成，如下所示：

2.1 最小描述长度的屋顶模型

DL=λL(D丨H)+(1-λ)L(H)

(1)

其中L(D丨H)表示给定模型H的观测值D的拟合优度，而L(H)表示模型H的复杂程度。λ是平衡模型接近度和模型复杂度的权重参数。假设表示数据的最优模型具有最小描述长度，模型选择过程允许模型H收敛到最优模型H*。

假设由随机误差引起的n个测量值的不规则分布D= {x1, . . . ,xn}服从高斯分布x～N(μ,σ2)。模型与数据的拟合程度可以用L(D丨μ,σ2)来衡量，然后模型紧密度可以改写为对：

(2)

在式(2)中，所有假设都具有相同的σ，因此可以忽略最后两项。此时，式(2)可简化为：

(3)

本模型的复杂性受三个几何因素影响：顶点数Nv、相同线方向的数量Nd以及内角过渡Nθ。如果多边形的顶点数和相同线方向数较少，并且内角过渡更平滑或更正交，那么相应的模型就是更好的。

因此，模型复杂度 L(H) 的子项的描述长度的总和为：

(4)

2.2 假设检验

假设的生成过程是指在屋顶模型(或建筑物边界)的某些配置下提出一组可能的假设。屋顶模型由多边形ΠA= {v1,v2,v3,v4,v5,v6,v7}和多边形ΠB= {v3,v4,v5,v8,v9,v10}组成，其中v3,v4,v5是两个多边形的公共顶点。在假设的生成过程中，首先定义锚点 (AP)、浮点 (FP) 和引导点 (GP)，然后定义浮线 (FL= [AP,FP]) 和引导线 (GL=[GP) ,FP])。AP的作用是定义要改变的线(FL)的原点。FP是要移动的点，而GP用于生成指导FP移动的GL。假设是通过以AP作为FL的原点沿GL移动FP来生成的。FL的方向由CLF的代表角度决定，CLF由八个方向组成。假设生成有以下5种不同的情况。

(1)v1和v2分别指定为 AP和 FP。通过将FP移动到GL来生成假设。

(2)类似情况(1)，v3和v2分别指定为 AP 和 FP。不同的是，FP位于AP的后方。

(3)移除v2后，v3和v1分别被分配为AP和FP。通过移动v1产生新的假设。

(4)v2和v3分别分配为 AP 和 FP。v3是ΠA和ΠB中的公共顶点。 因为v3的位置发生了变化，所以两个多边形的形状都发生了变化。

(5)v2和v4分别被分配为AP和FP。去掉v3后，v4被赋值为FP，从而改变了v4的位置。

3 权重参数优化

式(1)中，λ是影响模型结果的权重参数：λ的值越小，最优模型具有越低的复杂度；较大的λ值强调对数据的拟合优度，很可能造成模型过拟合。为了自动估计合适的权重值，采用最小—最大(Min—Max)准则，即在最大化增益的同时最小化可能的损失。为了实现这一目标，首先为每个λ找到能实现式(1)最小化的最佳模型H*。考虑到边界条件，λ= 0 处的L(H)和λ=1处的L(D丨H)均为零。然后，分别使用归一化方法对L(D丨H)和L(H)进行归一化。在对每个λ计算总的DL值后，通过选择最大的DL值来推导出最佳权重值λ*。

如式(4)所示，L(H)由三个几何项组成，包括顶点数、相同线方向数和内角过渡。

在多属性决策中，熵权法常用于确定合适的属性权重：特定属性对应的熵值越大，属性的权重越小。采用熵权法来确定式(4)中三个几何项的相对重要性。在信息论中，熵被理解为对从数据中提取的属性的不确定性的度量，通常可以表征如下：

(5)

(6)

4 实验评估

使用了由ISPRS提供的通用数据集——Vaihingen数据集来进行实验评估。将本算法与GraphEdit[4]、FIE[5]和IRRRM[6]算法进行比较，结果如表1所示。实验结果表明，本算法在完整性、正确性和质量方面均优于现有重构算法。当屋顶面积大于10 m2时，本算法具有明显的优势。本算法的均方根误差较小，表明提出的算法具有较好的稳健性。

表1 实验结果对比

接下来，使用角度差、豪斯多夫距离和旋转函数距离三个指标来评估本算法的性能，结果如表2所示。二维外边界和三维屋顶平面的豪斯多夫距离平均值分别为 1.81 和 1.17 m。结果表明，通过提出的方法，参考屋顶模型和提取的屋顶模型的顶点之间的最大距离预计小于均方根误差的大约两倍。此外，二维外边界的平均豪斯多夫距离大于三维屋顶平面的值。这主要是由屋顶平面之间的拓扑关系引起的。在参考模型(或提取模型)中共享公共边的两个屋顶平面在提取模型(或参考模型)中由分离的屋顶平面表示。不同的拓扑关系导致了外边界表示的大量形状差异。

表2 角度与形状评估

5 结论

本研究提出了一种三维建筑屋顶的重建算法。该算法首先将建筑物标记点分割成具有层次结构的同质集群。为了有效地收集屋顶结构的证据，该算法分别提取了相交线、阶梯线和边界三个线性建模线索。该算法提出了正则化过程，以根据最小描述长度原理隐式地对重建的屋顶模型施加几何规律。本研究使用了通用Vaihingen数据集对算法进行性能评估，将本文算法与现有算法进行对比。实验结果表明，所提出的算法具有较好的准确性，其均方根误差较低，说明了算法具有较好的稳定性，而重构的屋顶模型则具有较高的质量和完整性。由此可知，所提出的算法能根据机载激光雷达的点云数据来准确重构三维建筑屋顶模型。