机载激光LIDAR点云顶面提取直线段的光谱聚类外文翻译资料

 2022-12-22 17:48:39

Spectral Clustering of Straight-Line Segments for Roof Plane Extraction From Airborne LiDAR Point Clouds

Chunsun Zhang , Yuxiang He, and Clive S. Fraser

Abstract: This letter presents a novel approach to automated extraction of roof planes from airborne light detection and rang-ing data based on spectral clustering of straight-line segments.The straight-line segments are derived from laser scan lines, and 3-D line geometry analysis is employed to identify coplanar line segments so as to avoid skew lines in plane estimation. Spectral analysis reveals the spectrum of the adjacency matrix formed by the straight-line segments. Spectral clustering is then performed in feature space where the clusters are more prominent, resulting in a more robust extraction of roof planes. The proposed approach has been tested on ISPRS benchmark data sets, with the results showing high quality in terms of completeness, correct-ness, and geometrical accuracy, thus confirming that the proposed approach can extract roof planes both accurately and efficiently.

Keywords: Light detection and ranging (LiDAR), plane extraction, reconstruction, roof, spectral clustering, straight line.

I. INTRODUCTION

AIRBORNE light detection and ranging (LiDAR) has been routinely adopted in recent times for the acquisition of geospatial information, and especially digital surface models.LiDAR measurements are acquired via a scanning mechanism that generates elevation profile slices of the landscape. Point clouds recorded by LiDAR systems contain abundant spatial structure information, including planar structures, which are abundant in man-made environments. The extraction of such planar structures from LiDAR data supports a broad range of spatial information applications [1]–[4]. In particular, coplanar segmentation or roof plane extraction is an essential process in 3-D building extraction and modeling. A 3-D plane, e.g., a roof plane, has an explicit mathematical model in Cartesian space, to which the coordinates of a LiDAR point fit if the LIDAR point belongs to the plane. Moreover, the normal vector or slope of a 3-D plane is invariant, so extraction of planes from LiDAR point clouds can be performed via 3-D model detection. Also, attributes of the plane, such as its normal vector and slope, can be exploited to group LiDAR points to form the roof plane. Approaches based on the Hough transform have been effective in the detection of planes in 3-D Hough space [5]. Being a voting algorithm, the Hough transformation does not consider the relationships between points and it can result in spurious planes. Voting approaches can be improved by enhanced normal coherence [6], or though taking into account the spatial relationship between points [7]. The RANSAC approach, which iteratively samples data points to determine functional model parameters, is also widely used in plane detection [8], [9]. Roof planes can be detected by grouping approaches which exploit the similarity of point attributes and the proximity of point locations. From a seed point, a planar structure can be detected by region growing by extending the seed point to the adjacent points using appropri-ate criteria [3], [10]. While widely used in point-cloudsegmen-tation, region growing methods are usually sensitive to noise in the data and may result in over or under segmentation [11]. Clustering, as a data mining technology, has been explored in LiDAR data processing for planar structure extraction. Planes are detected by fuzzy K-mean clustering of point normal vectors [12]. The K-plane algorithm uses the coordinates of LiDAR points in clustering, thus avoiding error in the estimation of the normal vector to the plane as well as reducing the computation time [13]. Planes can also be detected by classification techniques [14] or segmentation of the point cloud through optimization [4]. Approaches using straight lines for roof extraction have also been reported [15], [16].These methods are usually fast due to a reduction in data volume to be handled. However, the effective use of straight lines in plane extraction has remained insufficiently explored.

This letter presents a novel approach for planar structure extraction from LiDAR point clouds through spectral clus-tering of straight-line segments. Instead of individual LiDAR points, straight-line segments derived from the laser scan lines are used as primitives. The use of straight lines significantly reduces the data volume to be handled in the planar structure extraction. The differentiation of coplanar and skew lines can be made, which allows for the exclusion of noncoplanar points from the clustering. Spectral clustering first reveals the spec-trum of the relationship between the straight-line segments.The clustering is performed with major components in feature space, resulting in a more robust roof plane extraction.

The remainder of this letter is organized as follows.In Section II, the theory of spectral clustering is outlined and the motivation for its use in roof plane extraction explained.Section III describes straight-line extraction and 3-D line geometry analysis. Spectral clustering of straight-line seg-ments is then presented in Section IV. The proposed method has been tested with the ISPRS benchmark data sets. The results obtained, along with an evaluation utilizing reference data, are presented in Section V. Finally, conclusions are drawn in Section VI.

II. SPECTRAL CLUSTERING

Clustering in general is an unsupervised technique to split the observed data into disjoint clusters, with the data in a given cluster having higher similarity than that in different clusters.Spectral clustering splits data through graph partition using the weighted adjacency matrix and its spectrum [17], [18].Thus, spectral clustering investigates and exploits the major components in the data re

剩余内容已隐藏，支付完成后下载完整资料

机载激光LIDAR点云顶面提取直线段的光谱聚类

张春生，何玉祥，Clive S.Fraser

摘要：这篇文章介绍了一种基于直线段谱聚类的机载激光探测和测距数据自动提取屋顶平面的新方法。直线段来源于激光扫描线，采用三维直线几何分析确定共面线段，避免平面估计中的偏斜线。光谱分析揭示了由直线段形成的邻接矩阵的频谱。然后在特征空间中执行光谱聚类，其中聚类更加突出，导致屋顶平面的更强大的提取。所提出的方法已经在ISPRS基准数据集上进行了测试，结果在完整性，正确性和几何精度方面表现出了高质量，从而证实了所提出的方法可以准确而有效地提取屋顶平面。

关键字：光检测和测距（LiDAR），平面提取，重建，屋顶，谱聚类，直线

  1. 介绍

机载激光探测和测距（LiDAR）近来已被用于获取地理空间信息，特别是数字表面模型。 LiDAR测量是通过扫描机制获取的，该机制可生成景观的海拔剖面切片。由LiDAR系统记录的点云包含丰富的空间结构信息，包括在人造环境中丰富的平面结构。从LiDAR数据中提取这种平面结构支持广泛的空间信息应用[1]-[4]。具体而言，共面分割或屋顶平面提取是三维建筑物提取和建模中的重要过程。三维平面，例如屋顶平面，在笛卡尔空间中具有明确的数学模型，如果LiDAR点属于该平面，则LiDAR点的坐标适合该平面。此外，三维平面的法向矢量或斜率是不变的，所以提取来自LiDAR点云的飞机可以通过三维模型检测来执行。此外，可以利用平面属性（如法向矢量和坡度）将LiDAR点分组以形成屋顶平面。基于Hough变换的方法在三维Hough空间中检测平面方面已经很有效[5]。作为一种投票算法，霍夫变换不考虑点之间的关系，它可能导致伪平面。投票方法可以通过增强正常一致性[6]或者考虑点之间的空间关系来改善[7]。 RANSAC方法迭代地采样数据点以确定功能模型参数，也广泛用于平面检测[8]，[9]。可以通过利用点属性的相似性和点位置的接近度的分组方法来检测屋顶平面。从种子点看，平面结构可以通过使用适当的标准将种子点延伸到相邻点而通过区域生长来检测[3]，[10]。虽然广泛应用于点云分割，但区域增长方法通常对数据中的噪声敏感，并可能导致分割过度或不足[11]。作为数据挖掘技术的聚类已经在平面结构提取的LiDAR数据处理中进行了探索。平面通过点法向量的模糊K -mean聚类来检测[12]。K平面算法利用LiDAR点的坐标进行聚类，避免了法向量估计误差，同时减少了计算时间[13]。平面也可以通过分类技术[14]或通过优化分割点云来检测[4]。也报道了使用直线进行屋顶提取的方法[15]，[16]。由于要处理的数据量减少，这些方法通常很快。但是，平面提取中直线的有效使用仍未充分探索。这篇文章提出了一种新的方法，用于通过直线段的谱聚类从LiDAR点云中提取平面结构。代替单个LiDAR点，从激光扫描线导出的直线段被用作基元。使用直线显着减少了平面结构提取中要处理的数据量。可以进行共面和倾斜线的区分，这允许从聚类中排除非共面点。光谱聚类首先揭示了直线段之间关系的频段。聚类是在特征空间中执行的主要组件，从而提供了更加可靠的屋顶平面提取。

这篇文章的其余部分如下，在第二节中，概述了谱聚类的理论，解释了它在顶板提取中使用的动机。第三节描述了直线提取和三维线几何分析。然后在第四节中介绍直线段的谱聚类。所提出的方法已经用ISPRS基准数据集进行了测试。所获得的结果以及利用参考数据进行的评估将在第五部分中给出。最后，第六部分得出结论。

  1. 光谱聚类

一般而言，聚类是一种无监督的技术，将观察到的数据分为不相交的聚类，给定聚类中的数据与不同聚类中的数据具有较高的相似性。频谱聚类使用加权邻接矩阵及其频谱[17]，[18]通过图分区分割数据。因此，谱聚类研究并利用频谱揭示的数据中的主要组成部分，从而在特征空间中更强大地表示数据，并因此促进数据聚类。另外，谱聚类不会对数据簇的形式作出任何假设。因此，谱聚类通常优于传统的聚类算法[17]，因此它在机器学习，数据挖掘和计算机视觉中被广泛采用[18]。谱聚类的全面介绍可以在[18]中找到。

考虑一组n个数据点。对称加权邻接矩阵WR^n*n编码成对相似性，其中对于所有i和j，其中0le;wijle;1,为了获取一个对称归一化权重矩阵，归一化图拉普拉斯算法为

L=D^(-1/2)*WD^(-1/2)

使得Lij = Lji = wij /(DiiDjj)^1/2，度矩阵D是一个对角矩阵，Dii=sum;nj=1^wij,让z1 z2hellip;zn为L的标准正交特征向量,相应的特征值为lambda;1ge;lambda;2ge;···ge;lambda;n，一个新的矩阵U R n k可以通过叠加第一个最大的k特征向量z1, z2，hellip;zk (L)在列中。让L(k) = UU^T，其中U^T是U的转置，L(k)是L的最好的近似，并保留了L[18],[19]中的大部分信息。L的主要矢量可以用eigengap来确定，也就是连续特征值之间相对较大的差异[18]。主要的特征向量通常是聚类的稳定信息，而剩下的部分则归因于数据中的噪音。在[20]中详细讨论了对簇的内聚性和特征向量集的稳定性的假设，从而证明了eigengap命题的正确性。

随着U的构造，原始数据被表示在k维特征空间中，其中数据点i被视为U的第i行。因此，数据维度显着减少。同时，特征向量继承了邻接矩阵中的信息，新的表示增强了特征空间中数据点的聚类属性。已经证明，投影在特征空间中的数据点要么聚集得更近，要么进一步分开[21]，导致聚类在特征空间中更加突出。

图1.屋顶平面上的共面和倾斜线。红点代表LiDAR点。l11和l12是从激光扫描线s1得到的具有顶点a，b和c的直线段。 p11和p12是从激光扫描线s2得到的具有顶点d，e和f的直线段。

  1. 直线段提取和三维几何分析

LiDAR指向覆盖屋顶平面的激光扫描线通常构成一条直线，并且该直线上的所有点位于相同的屋顶平面内，因此使用直线作为屋顶平面提取的基元。直线段由一系列点组成的事实意味着将直线段用作基元会极大地减少要处理的数据量。另外，直线在几何上比单个点更稳定，因此对LiDAR点云中的固有噪声和随机误差更具鲁棒性。此外，由于倾斜线可以很容易地检测出来，并且使用三维几何体可以有效识别共面线段，所以可以避免非共面直线，并且只需要在数据聚类中进一步探索共面线段，如图1所示。

假设两个激光扫描线击中建筑物的屋顶。扫描行s1的结果是两个连续直线段l11和l12通过连接顶点a、b和c顺序。让1*3向量的3个元素是a的三个坐标值，同样的用b和c表示顶点b和c的向量，类似地，从激光扫描线s2推导出两条连续的直线段p11和p12。顶点d、e和f分别对应的坐标向量d、e和f。由于l11和l12是两个连续的直线段，它们来自同一激光扫描线s1，所以它们应该停留在不同的屋顶平面上，l11上的三个LiDAR点和l12上的四个LiDAR点属于不同的平面。在激光扫描线s2上的p11和p12也可以做出同样的决定。从3D几何图形中，可以很容易地识别出斜行对l11和p12。这是因为det[a bb f] T ne; 0。因此，l11和p12为非共面，l11上的三个LiDAR点和p12上的四个LiDAR点属于不同的平面。对于斜行对l12和p11同样适用。另一方面，共面线对l11和p11以及l12和p12也可以通过3-D线几何来确定。对于l11,3D线几何分析决定了它在邻域的共面对p11，这可能与l 11在同一屋顶平面上。与此同时，三维线几何分析也确定了斜线段l12和p12，在随后的屋顶提取中被排除在l11附近。

图2所示。直线段提取。(a)输入原激光雷达点云。(b)激光扫描线。(c)提取不同颜色的线段。(d)对原始扫描线和提取的直线段进行放大。

现代激光雷达系统标记点在每条扫描线的末端，这些端点可以作为标志来定义间隔，在这里每条扫描线可以被看作是风景的轮廓。将每条扫描线与一串激光雷达点作为折线，采用迭代-端点-拟合简化算法提取直线段[22]。这个递归检测关键顶点，根据点对线距离公差。因此，原始激光扫描线被简化为连接连续的关键顶点形成的连接的直线段。图2展示了直线段提取的过程。原始的激光雷达点以不同的颜色编码在图2(a)中。图2(b)为原始激光扫描线。在迭代结束点拟合过程后，每个激光扫描线被划分为一组直线段，其点对线距离为5厘米，如图2(c)所示。图2(d)中显示了原始激光扫描线和推导出的直线段的放大图。

注意，线段包括屋顶上的点，以及属于植被和地面的点。不相关的线段需要删除，这是通过三个简单而有效的过滤器实现的。首先，消除了一小部分最后脉冲计数的线段。从直观上看，从上一个脉冲的几个点出发的一条线表明，这条线上的大多数点都是来自植被的反应。此外，只有当线段包含至少3个最后的脉冲点以避免不可靠的直线段时，才被接受。最后，将接近地面的线段移走。利用[23]中描述的算法，从激光雷达数据中计算出地表。

  1. 屋顶平面提取

通过直线段的谱聚类进行屋顶提取需要构建邻接矩阵并聚集主要特征向量来确定屋顶平面。

  1. 本地最适合飞机检索

通过分析第三节中描述的直线段的三维几何形状，可以有效地区分共面和斜直线段。局部的，与每个线段相关联的最适合的平面现在可以使用相邻的共面线段来提取。这些平面随后被用于屋顶平面的聚类提取。通过观察相邻的共面直线段通常位于同一屋檐平面上，这些线段的最佳拟合平面应该是相同的。直线段的邻域被确定为半径为r的圆柱空间，其轴与线段重合。注意，只考虑共面线段;附近的歪斜线被忽略了。给定一条线段x及其邻域的共面线段Xc,Xc={x1,x2，hellip;hellip;,xj,hellip;hellip;,xc }。x和xi构成一个平面，因此，可以生成一组候选平面{Pi}ci=1。直线段xj,xjisin;Xc,xj ne;xi,被归入pi;平面如果它的窗口满足以下标准:

其中△(xj, Pi)是xj到Pi的中间点，ni是Pi的法向量，dj是xj的方向。在{Pi} ci=1中，最大数量的inliers被确定为线段x最适合的平面。

B、图拉普拉斯算子的构造

给出了两条直线段xi和xj，以及它们的最优拟合平面P xi和P xj，利用两层之间的角差和测地线距离来测量最佳拟合平面的pairwise共面相似度。角差是这样形成的

theta;是两个平面的法向量之间的夹角P xi和P xj。测地线距离定义为

其中dist(mi, Pxj)是由xi到Pxj中点mi的欧几里得距离，而dist(mj, Pxi)是从xj中点mj到Pxi的欧几里得距离。

加权邻接矩阵Wisin;R ntimes;n是通过一个指数生成内核。

sigma;1和sigma;2缩放参数的高斯内核和维琪在区间[0,1]。wij接近1的值意味着，角差和测地线距离都很小，而xi和xj预计在同一平面上。

邻接矩阵ARn*n表示为Aij=(wij wji)/2Aij=(wij wji)/2,0le;Aij=Ajile;1对，对角矩阵D被定义为A的程度，而Dii*Dii是A的第i行的和。然后，用(1)来构造拉普拉斯矩阵。

当Lij=Aij/radic;Diiradic;Djj。直线段现在表示为每个行向量的R^n特征空间中的数据点。

图3所示,屋顶平面提取的光谱聚类图。(一)激光雷达点云。(b)提取直线段。(c)构造

邻接矩阵。(d)理想的邻接矩阵。(e)由直线段的光谱聚类提取的屋顶平面。

C、顶部平面提取的光谱聚类

在图拉普拉斯矩阵中，利用eigengap[18]确定了主要的K特征向量。所收集的特征向量构成了新矩阵UR^n*k，如第二节所述。因此，ui在U中的第i行表示特征空间中的第i个直线段。ui被归一化为单位向量ui, ui = ui /||ui ||。

然后通过在单位球面上的平均位移算法来检测平面结构。均值位移聚类的优点在于它是一种基于密度测量的非参数化算法，它通过对密度估计窗口的平移来迭代计算平均位移向量。

直到收敛达到[24]。均值转移聚类过程不需要先验知识的聚类数量。此外，它还可以处理任意形状的簇，使其更适合提取应用。

图3为屋顶平面提取的屋顶结构的光谱聚类过程。

图3(a)的屋顶由3589个激光雷达点组成，由激光雷达扫描线段获得的131个直线段表示，如图3(b)所示。使用该算法对线段进行进一步的处理。三维线几何分析确定了共面线，避免了每个线段附近的斜线。然后检索本地最适合的飞机。最后，邻接矩阵A由1和2组成，分别赋值分别为0.03和25。一个包含131的相似性度量。只有0.7的权重被接受，而其他的被赋值为0。在图3(c)中，所接受的权重以灰色表示。剩下的都是黑色的。得到了一个近似块对角结构。与图3(d)所示的理想形式相比，导出的邻接矩阵的精度高达81%。这在很大程度上可归因于3-D线几何的分析，在此基础上避免了斜线。对局部最适合的平面进行估计，从而导致在邻接矩阵中存在更强的测量值。这样一种接近理想的邻接矩阵便于连续特征向量计算。最后，由拉普拉斯矩阵L推导出的主要的六个特征向量，决定用均值位移算法构造U的矩阵U聚类，结果6个簇对应于图3(e)所示的6个屋顶平面。

  1. 实验结果和讨论
  2. 评价标准

所提出的屋顶提取算法的性能可以在完整性和正确性方面进行评估。 另外，还可以评估提取的飞机的几何质量。 首先，确定所提取的平面与参考平面之间的

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[24989]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章