一种基于局部曲率特征的点云精简算法

麻卫峰，周兴华，徐文学，潘光江

（1．山东科技大学 测绘科学与工程学院，山东 青岛266510；2．国家海洋局第一海洋研究所，山东 青岛266061）

三维激光扫描技术具有非接触、速度快、效率高等优点，近年来逐步发展为实物数字化的主要方法之一。但激光扫描产生的点云数量巨大，远远超过了研究扫描物特性所需要的点云数量，同时海量的点云数据严重降低了数据处理效率。因此如何在保证精度的前提下有效精简压缩点云数据，用较少的点描述扫描物的属性特征成为点云数据处理过程中的重要环节。

曲率精简原理是利用曲率的变化，采用一定的判断原则决定点的保留与删除（曲率大的地方保留足够多的点，曲率小的地方保留较少的点）［1］。目前国内针对曲率的点云精简算法主要利用斜率、距离以及角度等进行精简。刘春，吴杭彬等利用斜率变化描述曲率变化，提出基于斜率变化的点云精简方法［2］；喜文飞，方源敏等［3］针对点云三角网模型中相邻两三角形顶点与边的关系，提出基于相邻三角形法向夹角为阈值的精简方法，认为三角形与邻接三角形的夹角决定了该区域的平滑度，夹角越大说明区域曲率变化越大，区域变化越复杂，保留点越多；张丽艳［4］等人研究了用Riemann图建立散乱测点间的邻域关系，分别提出了基于简化后的数据集中点个数、数据集中点的密度阈值及删除一点引起法向误差的阈值准则的数据精简方法，但存在对临近点个数k的选取依赖过大的缺点；王玉国，周来水等人提出基于曲线曲率和采样的自适应精简压缩方法［5］。上述算法只考虑扫描线或者点曲率变化，没有考虑某个范围内的曲率变化，不能综合某个范围内的表面特征进行精简。针对这种情况，本文利用局部曲率中误差大小来衡量局部区域内的曲率变化，并设置局部曲率中误差变化阈值，当局部曲率中误差大于阈值时，认为该区域是复杂区域，应保留较多点 否则为平缓区域 保留较少点 最后统计每个点的精简概率，根据精简概率判定点的取舍。

1 曲率计算

曲率反应曲面性质的重要特性，也是曲面特征识别的主要依据之一。目前曲率计算的常用方法有：图像梯度求解法［6］，三角格网法［7］，二次曲面拟合法［8－9］。二次曲面拟合法稳定性较强且计算步骤比较简单，本文使用该方法计算曲率，其基本思想为：取点云中任意一点Pi（1≤i≤n，n为点云个数），利用点Pi的k个临近点拟合二次抛物面Z（X，Y），通过计算Z（X，Y）的主曲率及主方向确定点Pi的曲率。

1．1 K邻域构建

由于散乱点云没有明显的几何分布特征，呈散乱无序状态，为了能最大限度地提取出原始数据中有用的信息，需要建立数据点之间的空间关系，即空间数据点之间的空间拓扑关系和邻域信息［10］。国内外已有很多点云拓扑关系的研究，常见的有3种方法：基于八叉树的空间划分、空间包围盒法和K－d tree法［11］。由于空间包围盒法具有较高的搜索效率，本文采用该方法建立点Pi的邻域集合，即与点Pi的欧式距离最近的k个点构成的集合，记为｛k－NB（Pi）｝，其中1≤i≤k。国内外学者对邻域数据量k的确定做了大量实验，证明k取24～30为最佳，太小不能满足精度要求，太大影响计算效率［12］，本文k取28，即｛28－NB（Pi）｝。

1．2 空间二次曲面拟合

建立点Pi的28邻域集合后，对其邻域集合内任一点Pj∈｛28－N（Pi）｝，根据最小二乘原理，须使式（1）取最小值，即

对式（2）中系数a，b，c分别求导，并使其为0，则有

联立式（3）可求出方程系数a，b，c的值。

1．3 空间点平均曲率计算

对于抛物面Z（X，Y），根据微分几何关系求解其微分算子，可得到曲面一阶偏导数ZX，ZY；二阶偏导数ZXX，ZYY，ZXY。

抛物面Z（X，Y）第一基本量

抛物面Z（X，Y）第二基本量

式中n是点Pi的单位法向量

点Pi的平均曲率为

2 点云精简算法

每个点处于不同的邻域范围内（设邻域个数为Su m），由于不同邻域范围的复杂程度不一样，同一点不同邻域的精简结果不同（设点保留次数为Flag），精简概率即是同一点不同邻域的保留次数占总邻域个数的百分比，即：q＝Flag／Su m。本算法的基本思想如下：通过计算邻域范围内的局部平均曲率中误差σi并与设置的阈值比较。当平均曲率中误差大于阈值时，保留平均曲率大于曲率平均值λ倍的点（λ为比例系数）；当平均曲率中误差小于阈值时，保留平均曲率最接近曲率平均值的点。同时将点标记累加1（即保留次数增加1次），最后计算每个点的精简概率，判定点的取舍。具体步骤如下：

Step1：定义点Pi（1≤i≤n，n为点云数）的结构体变量：

Str uct｛

Hi＝0 %定义每个点的平均曲率初值 Pi＝［x，y，z］； %点坐标存储；

Flagi＝0； %点标记初值

Su mi＝0； %点计算次数初值

Delect＝｛1，0｝；%计算结果，1则表示删除该点；0表示保留该点

｝。

Step2：计算所有点的平均曲率H。

Step3：对点云中点Pi及其邻域集合内任一点Pu∈｛28－N（Pu）｝，求平均曲率的平均值＝Hu，其中1≤u≤k，Hu是点Pu的平均曲率值。

Step5：当σi≥σ时，保留平均曲率Hu≥λ的点，删除平均曲率Hu≤λ的点；当σi＜σ时，保留点平均曲率Hu最接近曲率平均值的点。同时将保留点标记累加1，即Flagu＝Flagu＋1，为后续计算点精简概率，邻域范围内所有点计算次数累加1，即Su mu＝Su mu＋1；其中1≤u≤k。

Step6：遍历所有点云，统计每个点的精简概率q，q＝Flagu／Su mu。精简概率q大于等于0．5时，保留该点即delect＝0；精简概率q小于0．5时，删除该点即delect＝1。

3 实验验证

点云精简率是精简删除的点云数与原始点云数的百分比，是点云精简效果的重要指标。为了验证本文的精简算法，本文基于matlab语言进行了编程实现，采用两组数据进行实验，并将处理结果与点云处理软件Geo magic的点云精简结果进行了对比

Geomagic软件是美国Rain Drop Geo magic软件公司推出的逆向工程软件。该软件是目前市面上对点云处理及三维曲面构建功能最强大的软件，其中点云精简模块有以下4种方法：

1）曲率精简法：减少平坦区域内点数目，保留高曲率区域内的点以保留细节。

2）栅格简化法：通过设置均匀的间距，不考虑曲率和密度，减少无序点数量。

3）随机采样法：从无序的点云中随机抽取一定比例的点。

4）统一采样法：使平坦曲面上点的数目减少量一致，但以规定密度减少曲面上点的数目。

实验数据1：来源于www．Pudn．co m网站兔子点云数据，原始激光点数目为35 947，分别取λ＝0．9，σ＝20；λ＝1．2，σ＝100；λ＝1．5，σ＝120三组参数进行实验，实验结果分别如图1（b）、图1（c）、图1（d）所示；Geo magic软件曲率精简法、栅格简化法、随机采样法、统一采样法处理结果分别如图2（a）、图2（b）、图2（c）、图2（d）所示。

图1 兔子点云在不同参数下的精简效果

图2 兔子点云在Geomagic软件不同方法的精简效果

实验数据2采用瑞士Leica公司生产的HDS4500型三维激光扫描仪获取的某古建筑狮子雕像点云数据，原始激光点数目为46 500，分别取λ＝0．9σ＝0．1λ＝1．5σ＝0．8λ＝0．9σ＝0．8三组参数进行实验，实验结果分别如图3（a）、图3（b）、图3（c）、图3（d）所示。

图3 狮子雕像在不同参数下的精简效果

图1和图2分别是利用本文方法和Geo magic软件处理兔子点云的结果对比，图3是狮子雕像点云在本文方法下的处理结果。由图1可知，对于曲面变化较多的兔子点云，随着λ和σ值不断增大，精简率不断增加，但点云边缘部位仍保持很好的轮廓；对比图1与图2可知，在相同的精简比例下，如图1中（b）与图2中（a），本文方法比Geo magic软件更能保持边界点，尤其是尖锐部位，比如兔子耳朵边缘部位；另外，在保持相同精简效果的情况下，本文方法具有更高的精简率。表1所示，对比以上两组不同数据的精简结果可知，对于曲率变化较小的兔子点云数据，局部区域内曲率中误差的变大是由于特征点（如尖锐点耳朵部位等）曲率偏大引起的，因此应设置较大的曲率中误差阈值σ与λ，将更多范围内的点云当做平缓区域处理，在保证效果的前提下获取更大的压缩率；对于曲率变化的较大的狮子雕像点云，局部曲率中误差偏大是因为更多的复杂点曲率变化引起的，因此应设置较小的曲率中误差阈值σ，同时增大λ，可以在保持特征点的情况下保留特征边缘，如图3（c）与图3（d），以便后续特征线识别和特征重构。由于本文方法在计算点的K邻域、空间二次曲面拟合以及点云精简等方面都具有较大的计算量，严重影响了点云简化的速度，下一步可以研究如何在保证点云精简精度的前提下提高精简效率。

表1 本文方法与Geomagic方法对兔子点云精简结果指标对比

4 结束语

本文介绍了点云曲率精简的常用方法，分析了当前曲率精简算法存在的不足，并基于现状提出采用平均曲率中误差来衡量局部区域内曲面特征变化，将曲面划分为复杂曲面和缓和曲面，最后计算每个点的精简概率，判定点的删除与保留，避免了有些重要的特征点可能被错误删除的情况，保证了精简结果的准确性与稳定性。通过实验验证以及与传统方法对比可以看出，本文算法对点云数据具有较好的精简效果。

［1］ FU Jing，JOSHI S B，SI MPSON T W．Shape differention of freefor m surfaces using a si milarity measure based on an integral of Gaussian cur vature［J］．Co mputer－Aided Design，2008（40）：311－323．

［2］ 吴杭彬，刘春．三维激光扫描点云数据的空间压缩［J］．遥感信息，2006（2）：22－24．

［3］ 喜文飞，方源敏，李帅，等．一种新的激光点云数据精简方法［J］．测绘工程，2012，21（4）：38－40．

［4］ 张丽艳，周儒荣，蔡炜斌，等．海量测量数据简化技术研究［J］．计算机辅助设计与图形学报，2001，13（11）：1019－1023．

［5］ 王玉国，周来水，安鲁陵．一种基于曲线拟合与采样的点云数据压缩方法［J］．机械科学与技术，2006，25（8）：989－992．

［6］ HU Xin，XI Juntong，JIN Ye．Geometric Feature Extraction and Model Reconstr uction Based on Scatted Data［J］．Journal of Donghua University，2004（4）：33－37．

［7］ HUANG J，MENG C H．Auto matic data seg mentation for feo maric feature extraction f or m unorganized 3－D coor dinate points［J］．IEEE Transactions on robotics and Auto mation，2001，7（3）：268－279．

［8］ MILROY M J，BRADLEY C，VICKERS G W．Segmentation of a wrap－around model using an active contour［J］．Computer Aided Design，1997，29（4）：299－320．

［9］ 周煜，张万兵，杜发荣，等．散乱点云数据的曲率精简算法［J］．2010，30（7）：785－789．

［10］高志国，海量点云数据滤波处理方法研究［J］．测绘工程，2013，22（1）：35－38．

［11］刘艳丰，王守彬，汤仲安，等．基于K－d树的机载LIDAR点云滤波处理［J］．测绘工程，2009，18（5）：59－62．

［12］柯映林，单东日．基于边特征的点云数据区域分割［J］．浙江大学学报：工学版，2005，39（3）：377－382．