一种改进的基于法矢方向调整的平面点云分割方法

张 强，李 朝 奎，李 俊 晓，严 雯 英

(湖南科技大学，地理空间信息技术国家地方联合工程实验室，湖南 湘潭 411201；湖南科技大学，地理空间信息湖南省工程实验室，湖南 湘潭 411201)



一种改进的基于法矢方向调整的平面点云分割方法

张 强，李 朝 奎*，李 俊 晓，严 雯 英

(湖南科技大学，地理空间信息技术国家地方联合工程实验室，湖南 湘潭 411201；湖南科技大学，地理空间信息湖南省工程实验室，湖南 湘潭 411201)

智慧城市的蓬勃发展和快速推广，使得三维建模成为当前热点研究方向。平面点云分割是三维点云建模中数据处理的关键环节。该文提出一种三角面片法向量方向调整方法，通过后续对邻近法向量进行加权平均估算实现平面点云的分割。首先采用八叉树的空间划分方法将无序的点云建立索引，利用K紧邻搜索获取参考点的K个邻近点，然后将该局部点构建不规则三角网并且得到包含参考点的所有三角面片以及三角面片的法向量，并通过将三维点投影到二维平面，利用平面三角形两边向量叉乘的方法，判断并调整各三角面片的顶点排列顺序，使三角面片的法向量一致化，最后对包含参考点的所有三角面片的法向量加权平均，估算参考点的法向量，根据点云法矢一致、共面的原则将平面点云分割出来。以徕卡Scanstation 2 型扫描仪获取点云数据，对该方法进行检验，结果显示其能较好地实现对点云法矢量方向的调整与估算，并对平面点云数据进行分割提取。

点云；三角面片；法向量；分割

0 引言

随着激光扫描技术的不断升级，三维激光扫描仪能够快速、方便地获取目标物的高精度点云数据，利用点云数据建模即可得到相应的三维模型，该技术方法已渗透到智慧城市建设、机械制造、逆向工程等多个行业[1]。鉴于点云数据格式简单，方便存储，并且能够突出复杂物体的细节部分，点云模型的应用备受关注，点云转变成模型的处理过程已成为当前研究的重点[2]。由于激光点云散乱无章、曲面性质异同[3]，对海量的点云数据统一建模处理会加大算法的难度和数学表示的复杂性，因此首先要对点云进行分割分类，区分对待处理。

当前实用的点云分割方法主要有[4]：1)基于边缘检测的分割通过检测算法查找特征产生差异的分界点，然后将其连接成为一个曲面，该方法提取边界效果较好，但点云曲率或法矢量对杂点敏感度高，提取轮廓容易断裂；2)基于区域生长的分割将点云几何特性一致的相邻空间点划定为一个集合，可以有效地克服噪声的影响，但其边界点识别差，不够准确；3)基于激光反射特性差异的分割。

本文采用八叉树的空间划分方法将无序的点云建立索引，利用K紧邻搜索获取参考点P的K个邻近点，将k+1个点构建不规则三角网并得到包含参考点P的所有三角面片及三角面片法向量，并通过调整三角面片的顶点排列顺序，使三角面片法向量一致化，通过对相邻面片的法向量加权平均的方法估算参考点法向量，最后根据点云法矢一致、共面的原则将平面点云分割出来。该方法对点的法矢量能够较为准确地进行调整和估算，有效提取平面点云。

1 改进平面点云分割方法原理

1.1 索引建立

三维激光扫描仪所获取的点云数据是一系列散乱、无序的空间点，点与点之间没有直接的拓扑关系[5]，要对大量的点对象进行处理会大大影响其效率，因此必须对点云建立一个空间索引，加强空间关联性。本文主要利用八叉树空间网格方法划分点云空间[6]，从而快速提取离散点的K邻域。

1.1.1 八叉树网格结构 在空间数据处理中，八叉树格网结构是一种高效的存储管理方法。其基本构建思想：首先遍历三维点云数据，获得点集中空间上3个正交方向的最大值和最小值，即Xmax、Xmin、Ymax、Ymin、Zmax、Zmin，从而构建点云集的最小外包围立方体，作为该八叉树结构模型的根节点并建立编码，然后将立方体沿正交方向均匀分割，得到大小一致的8个子立方体并建立下一级编码(图1)。同理，分别对8个子立方体进行空间划分，直至子立方体对象不满足划分要求则停止分割，否则继续对子立方体进行划分，直到所有的子立方体都符合最小的空间划分阈值。基于后续处理对索引的需求，建立八叉树格网的结构体如下：

Public class Octree

{

public string RootNode;//父节点索引；

public string [] LeafNode;//子节点索引；

public string ID;//立方体所在的编码;

public mTreeNode[] Vertex;//立方体的8个顶点；

public P3D_struct Midpoint;//立方体的中心点；

public P3D_struct NearMid;//所含的点云中距离立方体距离中心点的最近点；

Public List Pointlist;//立方体包含的点云集合；

};

图1 八叉树结构图

Fig.1 The structure diagram of Octree

本文选择子立方体中包含的点数量γ阈值作为划分条件：1)对子立方体空间包含点数量γ与γ阈值进行比较；2)当子立方体空间包含点γ≤γ阈值时，则停止对该子立方体的空间划分，并对划分结果进行存储；3)当子立方体空间包含点γ>γ阈值时，则继续对该子立方体进行空间划分，成为下一级子立方体，然后重复步骤1-3，直到所有子立方体都满足要求且存储完成。

1.1.2 K邻近点的搜索 空间上点与点之间是不连续的，无法体现空间几何特性[7]，需要结合邻近点反映其特征。常用的方法就是寻找该点在空间上与其距离最近的K个点，即K邻近点搜索[8]。具体搜索步骤如下：首先利用上文所建立的八叉树网格结构，根据目标点P的三维坐标值，反求出其所在子立方体的编码M(x,y,z)，然后找到子立方体空间上与其相邻的26个子立方体编码M(x±1,y±1,z±1)，并将编码为M(x,y,z)和M(x±1,y±1,z±1)的27个子立方体作为目标点P的邻近点的搜索范围，最后根据到P点的空间距离，对搜索范围内所有邻近点进行排序，取出距P点最近的K个点，存储到K邻近数组中。如果在P点的27个立方体搜索范围中，点的数量少于K个，则需要将P点的邻近立方体扩大一层至125个子立方体，直到能够找到其邻近的K点。

1.2 法线方向调整和估算

离散点云的法矢量是点在空间分布的重要特征，因此估算点的法向量成为点云分割过程中的一个重要环节。有学者采用各种拟合算法，将P点邻域中的K个邻近点拟合成一个平面或曲面，并将曲面该点处的法向量或曲率[9]作为该点法矢量信息的估算值；也有学者利用最小二乘方法，将相邻点局部进行平面拟合，得到P点的一个微分切平面，由此切平面得到该点的法向量估算值。以上方法所得点的法线方向具有任意性[10]，有些指向曲面内测，有些指向外侧，对后续法矢量的计算应用产生影响。本文通过三角网格顶点排序方法将法线方向归一化，然后通过加权平均法估算单点的法向量，主要步骤如下：

(1)将参考点P与其K相邻点建立Delaunay三角网，筛选全部包含参考点P为顶点的三角面片，并存储三角面片顶点。

(2)计算各三角面片的法向量。由于三角形顶点排序无规则，所求出法线的指向也不一致，一些法线方向指向外侧，一些指向内侧(图2)，这样无法对相关法线进行准确估算，需调整法向量方向。

(3)三角面片顶点排序。首先将三维空间的点投影到X-Y平面，将二维三角面片的两个边向量叉乘，根据边向量叉乘结果调整三角面片顶点的顺序，将三角面片的顶点按照逆时针方式排列存储。如图3所示：包含顶点P的三角形ABP，其存储的顶点顺序为A、B、P(或B、P、A或P、A、B)。通过规范三角面片顶点顺序，将三角面片的法向量指向一致化：指向外侧(或内侧)，结果如图4所示。

图2 三角面片法向量 图3 三角面片顶点排序 图4 调整后的三角面片法向量

Fig.2 The normal vector of triangular patch Fig.3 The sequence of triangle vertex Fig.4 The normal vector of triangle after adjustment

(4)法矢量估算。本文利用点P与其相邻点共同构建三角面片，则点P的法向量会受到所有包含顶点P的三角面片的法向量的影响，为了综合考虑各法矢量对P点法矢量的贡献，采取加权平均各相关法向量方法对P点的法向量进行估算(图5)，点P的法向量用np表示，其表达式如式(1)、式(2)：

(1)

(2)

图5 单点法向量估算

Fig.5Theestimationofsinglepointnormalvector

1.3 平面点云分割

经过加权平均，得到了三维点的法向量，根据法向量特性，可以设置一定的限制条件对平面点云进行分割。由平面的基本特征可知，平面点云必须满足两个条件：1)散乱点的法向量指向必须一致或夹角小于一定的阈值，即同向性；2)散乱点的局部拟合平面之间距离必须小于一定的阈值，即共面性。

(3)

条件2中，两个局部拟合平面间的距离并非这两个点间的距离。此处两个拟合平面的距离d为：

(4)

图6 平面点云约束条件

Fig.6Theconstraintconditionsofplanarpointclouds

根据以上分析，本文采取的平面点云分割算法流程如下：1)建立点云索引，得出第i个点的K邻域。2)将第i个点与其K邻近点构建不规则三角网，查找并存储包含i点为顶点的N个三角面片，并得出三角面片的法向量。3)将这N个三角面片从三维空间投影到X-Y平面，然后根据三角面片其中两边的叉乘值，判断三角面片的顶点排序，如果满足逆时针排序，则不做调整，否则，将其调整为逆时针排序，重新计算该面片的法向量。经过该步骤，三角面片法向量指向一致。4)利用式(1)、式(2)，计算第i个点法向量。5)重复步骤1-4，直到所有点的法向量计算完毕。6)根据平面点云分割条件同向性、共面性，对点云进行分割，提取出平面点云得到最后结果。

2 实验与分析

利用徕卡Scanstation2型激光扫描仪获取实验点云数据，桌面水杯模型和雕塑模型都包含有平面点数据和非平面点噪声数据。通过不断调整阈值进行实验，取阈值数据γ阈值=10，向量夹角α=0.12，面片距离d=0.8时分割效果比较理想。从图7和图8可以看出：平面点云已经被分割出来，但平面上明显比原数据多出一些空斑点，这是由于局部地区点云并不平坦，而被作为噪声点排除在外。

图7 桌面水杯模型实验效果 图8 雕塑模型实验效果

Fig.7 The experimental results of cup model Fig.8 The experimental result of statue model

法矢分割方法将原始数据分割成平面点云数据集，通过与人工判断分割的结果进行对比，定量呈现其分割效果。从表1的实验数据看，两个模型中被分割出的平面点数据与人工分割的平面数据比较接近，分割合格率分别达到96.32%和96.49%。实验表明：本文方法能够很好地对点的法矢量进行调整和估算，将平面点与非平面点进行分离，从而保障了以后对平面模型的重建效率。

表1 法矢分割与人工判断结果比较

Table 1 Comparison of segmentation experimental results

数据分割方法实验数据点数(个)分割后平面点数(个)剔除的非平面点数(个)分割合格率(%)桌面水杯模型雕塑模型法矢方法13954811613423414人工判断13954812056718981法矢方法1652369889535人工判断1652372429281 96．3296．49

3 结论

本文将局部邻近点格网化，通过调整三角面片顶点将法向量指向一致化，通过加权平均相邻三角面片的法矢量，估算出单点的法向量，最后根据平面点云的同向性和共面性分割提取平面点云数据。通过三角面片顶点排序、法向量指向的调整，估算点的法向量，取得了很好的效果；加权平均相邻三角面片的法向量，估算出单点法矢量的精度符合其几何特征的表达；改进的方法能够较好地对点法矢量进行估算，并对平面点云进行分割提取，为以后点云数据的精细化分割奠定一定的基础。

[1] 丁延辉,邱冬炜,王凤利,等.基于地面三维激光扫描数据的建筑物三维模型重建[J].测绘通报，2010(3):55-57.

[2] 张会霞,陈宜金,刘国波.基于三维激光扫描仪的校园建筑物建模研究[J].测绘工程,2010,19(1):32-34.

[3] 李必军,方志祥,任娟.从激光扫描数据中进行建筑物特征提取研究[J].武汉大学学报(信息科学版),2003(1):65-70.

[4] 吕德亮.散乱点云分割及特征面片识别研究[D].北京：北京建筑工程学院；2012.

[5] 王飞，赵季中,傅梁.采用局部凸性和八叉树的点云分割算法[J].西安交通大学学报,2012(10):60-65.

[6] 吴杭彬,李楠,刘春,等.机载激光扫描数据分割的三维数学形态学模型[J].遥感学报，2011(6):1189-1201.

[7] 周煜,张万兵,杜发荣,等.散乱点云数据的曲率精简算法[J].北京理工大学学报，2010,30(7):785-789.

[8] 张量,王敏.基于K邻域离散扩张的点云数据分割[J].软件导刊，2009(12):7-9.

[9] RABBANI T,VAN DEN HEUVEL F,VOSSELMANN G.Segmentation of point clouds using smoothness constraint[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences，2006,36(5):248-253.

[10] 尹辉增,孙轩,聂振钢.基于机载激光点云数据的电力线自动提取算法[J].地理与地理信息科学，2012,28(2):31-34.

Planar Point Cloud Segmentation Based on the Weighted Average of Adjusted Normal Vector

ZHANG Qiang， LI Chao-kui， LI Jun-xiao，YAN Wen-ying

(NationalandLocalJointEngineeringLaboratoryofGeospatialInformationTechnology,HunanUniversityofScienceandTechnology,Xiangtan411201；HunanProvinceEngineeringLaboratoryofGeospatialInformation，HunanUniversityofScienceandTechnology,Xiangtan411201,China)

With the vigorous development and rapid promotion of wisdom city,3D modeling is becoming the current hot research direction.Planar point cloud segmentation is the key part of three-dimensional point cloud modeling.In this paper,a kind of adjustment method is put forward in the normal vector direction of triangles,then weighted average of the adjacent normal vector is done to realize the plane segmentation of point cloud.Firstly,using Octree space division method to establish an index for the scattered point cloud,using K neighboring algorithm to obtainKneighboring points,then triangular irregular network is established,then to project the 3D point on a two-dimensional plane,according to the product of two edge vectors of triangles,the triangle vertex order is adjusted to make the normal vector point to the same side,and the weighted average of adjusted normal vector is used to estimate the normal vector of a point,finally the planar point is extracted based on the consistence in direction and coplanar condition.Taking the point cloud obtained by Scanstation 2 scanner as an example,the result shows that this method can realize the plane segmentation of point cloud data.

point cloud；triangular patch；normal vector；segmentation

2014-06-26；

2014-09-02

国家自然科学基金项目(41271390)；湖南省研究生科研创新项目基金(CX2013B405)；湖南科技大学研究生创新基金项目(S130034)

张强(1989-)，男，硕士研究生，研究方向为三维激光点云数据处理。*通讯作者E-mail:chkl_hn@163.com

10.3969/j.issn.1672-0504.2015.01.010

P208

A

1672-0504(2015)01-0045-04