乔周民 侯岳 蒋达

摘 要：本文对建筑物点云分割与提取的方法和流程进行研究。在研究过程中，通过对建筑物顶面进行分割，提取出建筑物各顶面的点云，精确构建建筑物房顶面片，进而实现建筑物的三维重建。

关键词：点云数据；法线；曲率；邻域点集

中图分类号：TP311.52 文献标识码：A 文章编号：1003-5168（2018）17-0013-02

Research on Point Cloud Segmentation and Extraction

Technology Based on Buildings

QIAO Zhoumin1 HOU Yue2 JIANG Da2

Abstract： In this paper， the method and process of segmentation and extraction of building point cloud were studied. In the study， the top surface of the building was extracted by dividing the top surface of the building， and the top surface of the building was accurately constructed， and then the three-dimensional reconstruction of the building was realized.

Keywords： point cloud data；normals；curvature；neighborhood point set

虽然建筑物的顶部造型各异，但一般都由一个或者多个平滑表面组成。目前，处理建筑物的点云分割算法主要有随机抽样一致性算法[1]、聚类算法、区域增长算法和3D霍夫变换等。当提取大面积的建筑物顶部形状时，由于建筑物顶部造型不一样，组成顶部的面片大小不同，难以采用统一的参数对范围内所有的建筑物顶部面片进行分割处理。本文通过点云数据法向量的分析建立了一种建筑物顶面区域增长分割种子点选取和特征参数的设置方法。

1 法线的计算与曲率的估计

法线[2]是描述曲面特征的一项重要指標，法线的估计对曲面特征的描述有着不可估量的意义。在三维空间中，法向量通常被表示为具有3个变量的矢量，一般用[n=x，y，z]表示。一般情况下，对于一个孤立的点，认为其是没有法向量的，但如果用一系列孤立的点表示一个物体时，可以利用孤立点[Pi]及其临近点拟合出一个曲面，用曲面的法向量近似代表该点的法向量，这样，就定义了孤立点的法向量。法向量的计算方法[3]有很多种，根据算法思想可以归为2类：一类是拟合出[Pi]及其附近点的曲面，利用曲面的法线向量近似代替[Pi]的法向量；另一类是直接利用[Pi]及其附近点推算[Pi]的法向量。本论文用第二类方法计算[Pi]的法向量。该方法应首先确定[Pi]的邻域点集，然后计算该点的法线和曲率。

2 邻域点集的确定

对于给定点[Pq]，其临近点集[Pk=P1kp，Pk2…Pkk]，定义邻域的概念为：

[pik-pq≤dm] （1）

式（1）中，[dm]是临近点到定点的最大允许距离，[·x]是闵可夫斯基距离范式的一个实例。邻域点集[Pk]的数量k可以预先设定。

如果采用公式（1）对所有点云进行最邻近点的搜索，工作量巨大且搜索过于频繁，导致搜索过程没有太大的意义，因此本文利用近似最近邻搜索算法[4]。

该方法可描述为：在可接受的误差范围内，设定一参数[ε≥0]，获取的邻域点集[Pki]到给定点的距离与最邻近点[qk]到给定点的距离之比不超过[1+ε]，即

[pki-pqx≤1+εqk-pqx] （2）

为了加快计算速度，本文采用了一种基于K-D tree[5]的最邻近搜索算法在多维空间中实现点的最邻近搜索。若按使用的角度，该算法实现查询点[Pq]的邻域点集[Pk]可通过2条途径：①确定与查询点[Pq]的最邻近的k个点（k-search）；②确定与查询点k的距离在半径r内的所有k个点（r-search）。

基于K-D tree最邻近搜索算法实现的关键是设置合理的参数，即如何设定k值和r值才能最优地实现邻域点集的搜索。k值和r值作为阈值，其设定的尺度大小是影响估算搜索点法线方向的重要因素，如果设定的尺度较为合理，估算的法线方向会趋于真实方向，如果设定的尺度过大，估算的法线方向和真实方向会有所偏差。

3 法线的计算

求表面某点[Pi]的法向量问题近似于求一相切面的法线问题，即求在邻域点集[Pk]中最小二乘平面拟合问题，若平面用一个点x和一个法向量[n]表示，那么[Pi]到平面的距离定义为：

[di=pi-x·n] （3）

其中，x和向量[n]使用最小二乘法计算，即

[di=0] （4）

定义x为点集[Pk]拟合平面的中心，即

[x=P=1k·i=1kPi] （5）

计算法向量[n]可采用主成分分析法，那么计算表面法线的问题就变成分析一个协方差矩阵的特征矢量和特征值，这个协方差矩阵从查询点的临近元素中创建，假如协方差矩阵用C表示，那么：

[C=1ki=1kξi·pi-p·pi-pT] （6）

[C·vj=λ·vj，j∈0，1，2] （7）

4 曲率的估计

曲率是衡量几何体不平坦程度的指标，把曲率的概念引入点云中，是为了描述点[Pi]和其临近点之间的缓急关系。对于曲率的估算方法，国内外学者已做了大量的研究，有很多种方法定义一点所在曲面的曲率，但这些方式一般要求表面已被表示为三角网格，而不仅仅是用一个孤立点来计算。例如下面两种曲率定义方式：

①定义[K，H]来表示某点在曲面的曲率。

[K=k1·k2，H=k1+k22，H2≥K] （8）

其中，[k1]和[k2]是曲面的主曲率。但是，[K，H]代表性较差，主要是由于估计值的相互作用。

②若用形状指数[SI∈0，1]定义曲率，则有：

[SI=12-1πarctan，k1≥k2] （9）

但是，利用该方法定义曲率时，噪声点对结果的影响较大，且不能从一组采样点直接进行估算。

本文定义了一种新的曲率表达，利用主成分特征分析推算点P的曲率，采用协方差C的特征值[λj]近似作為P点的曲面变化度。如果[λ0=minλj]，那么P点沿曲面法线[n]的变化度可表示为：

[σp=λ0λ0+λ1+λ2] （10）

即最小特征值和所有特征值的比值近似表示以P为中心的k-邻域曲率值，且用这种表示方式的曲率具有尺度不变性。较小的[σp]，则说明P点的k-邻域内所有的点位于表面的切平面上，因此建筑物顶面分割区域增长算法中选取最小曲率的点作为种子点。

式中，[σp]的计算依赖于k值的选取和协方差C的计算，且受噪声的影响较大。本文采用基于最优拟合面的协方差阵C来消除噪声的影响，即不再采用最小二乘拟合切平面，而是寻找最优平面模型。依据点到最优平面的距离[di]的大小，将邻域[pk]中的点分为内部点[di≤dmax]和外部点[di>dmax]，计算协方差矩阵时，内部点和外部点采用不同的权重[ξi]：

[ξi=exp-d2iμ2，pki∈外部点1，pki∈内部点] （11）

式中，[μ]表示点[pq]到邻域点[pki∈pk]的平均距离。

该方法的优点在于考虑了外部点的影响，有助于减少噪声的影响。同时，在不同的平面接边处也能得到很好的计算结果。平面估计采用了RMSAC（Randomized M-Estimator Sample Consensus）算法。

参考文献：

[1]李孟迪，蒋胜平，王红平.基于随机抽样一致性算法的稳健点云平面拟合方法[J].测绘科学，2015（1）：102-106.

[2]赵春海.三维点云数据邻域搜索与特征描述子提取算法研究[D].秦皇岛：燕山大学，2015.

[3]何望君，刘纪平，张福浩.一种基于GPU的地形顶点法向量并行计算方法[J].辽宁工程技术大学学报（自然科学版），2017（7）：734-738.

[4]张婷.基于量化的近似最近邻搜索技术研究[D].合肥：中国科学技术大学，2017.

[5]刘宇，熊有伦.基于有界kd树的最近点搜索算法[J].华中科技大学学报（自然科学版），2008（7）：73-76.