陈新河 庞俊亭 周 波

改进的分层曲率海量点云精简算法

陈新河1庞俊亭2周 波3

1(巢湖学院电子工程与电气自动化学院 安徽 巢湖 238000)

2(湖南第一师范学院商学院 湖南 长沙 410205)

3(黑龙江科技大学计算机与信息工程学院 黑龙江 哈尔滨 150022)

海量点云精简既要考虑算法的复杂度，又要考虑精简结果的效果。根据三维扫描仪形成的点云特点，提出将空间点云划分为扫描层平面点云，从而将空间问题转化为平面问题。通过平面内Angl的简单计算获得点曲率，从而简化算法复杂度；通过引进距离参数Dis防止精简“大孔洞“的出现；通过综合考虑点的曲率和点间的距离，形成一个判别点是否被删除的标准，修改该判别标准公式中的系数，可以得到不同的精简效果。试验结果证明，该算法对海量点云的精简实践可行，具有复杂度低、数据精简率高等特点。

海量点云 数据精简 曲率 分割切面

0 引 言

点云三角化在计算机视觉、逆向工程、自由曲面设计、计算机辅助制造设计(CAGD/CAD)和地球信息系统(GIS)等许多领域广泛应用。但随着生产实践的增长要求，当前处理的点云每每超过十万、百万、甚至千万点的规模。如何对这些海量点云进行三角化处理是一个问题，如果直接对海量点云数据进行三维曲面的重构，会造成数据存储结构庞大、计算机操作困难、显示和数据交换缓慢等问题。因此，在保证一定的三维重建的精度前提下对海量点云进行精简是一个值得研究的课题。

近年来，国内外许多学者就数据精简发表了一系列的研究成果：文献[1]中研究了自适应最小率的变化而影响精简精度距离精简算法，还讨论了按距离精简的算法，它们都没有充分考虑空间点曲；文献[2]中提出了一种自适应的三维点云数据精简算法，但该算法实现起来有一定的困难；文献[3]中分析CMS采集数据的特点的基础上提出了改进的角度偏差法，但这题算法的实效性不太好；文献[4]中也提出了基于三维扫描仪的点云数据特点的数据精简算法，但算法中是人为的控制分层层数，这就很难控制分层正好处于扫描位置，而且文中仅仅认为三维扫描仪中XOY平面内扫描，Z轴为扫描层增加方向；文献[5]中提出了基于点的空间主曲率的数据精简算法，虽然这种精简效果较好，但每个点都需要二次曲面的拟合获得其主曲率，这是个非常费时的操作，对于海量点云几乎是不可能；文献[6]中提出了基于法向量夹角的数据精简算法，这种算法也可以得到比较好的精简效果，但同文献[5]中一样，也要对点云中每个点进行最小二乘拟合，计算相当费时，对海量点云不切实际。

总的来说，点云的精简算法总体分为三类：网格精简、分层精简和基于最小二乘的精简。网格精简速度快但精简效果差，基于最小二乘法的精简精度好但运算耗时，不符合海量点云的要求，分层精简的速度和精度都比较适中。本文对此提出一种基于自动分层的海量点云的精简算法。

1 算 法

三维扫描仪取点时一般是将某个轴向坐标暂时固定[7]，在该轴向的垂直平面内获取物体表面的点，然后沿该轴向进行微小移动进行下次的取点，直到整个物体表面的点全部取完。因此三维扫描仪获取的点云是分层的点云数据。基于此类点云数据的特点，本文算法的基本思路是：首先找到点云的分层方向，将点云按照自然分层分成各个小的点云切面，其次中各个切片点云中对各点的相互位置关系进行确定；然后通过相邻点计算出各点的曲率等参数的大小，对这些参数的综合值小于用户指定阈值的点进行删除；最后将所有分层点云合并成一个整体点云进行显示，以确定本次精简结果是否达到要求而进行保存或者重新精简。

1.1 相关数据结构

点及点云数值

class C3DPoint

{public:

//point coordinate in 3-dimensiom

float x,y,z;

//to sign the specialcharacteristic index of the point such as angle or position in three-dimension

float mark;

//the constructors of this class

C3DPoint(){ mark=x=y=z=0;}

C3DPoint(float xx,float yy,float zz,float mm=0) {… }

……};

typedef CArray C3DPtArray; //define 3D point array

分层点云数值链表

//this struct can let you create many point-arrays dynamically and assemble them as a whole like list.

typedef struct C3DPtArrayList

{ int index;

C3DPtArray ptArr;

C3DptArrayList *nextPtArr;

}C3DPtArrayList;

1.2 算法过程

读入点云：将点云数据从文件中读入，同时统计点云的相关参数，如点云的中心，各个方向的轴长，各个方向的最小、最大值等。

寻找分层方向：将点云沿某一轴向进行快速排序，对排序好的数组预取前边的一些点，比较它们的排序方向的坐标值是否相等。如果相等，说明他们是同一分层的点，该排序方向也是正确的分层方向；否则就沿其他方向排序并寻找点云分层方向，直到分层方向找到。

层内点间关系的确定：对于已经确定好分层方向的点云(设分层方向为X方向)，按照分层方向坐标值的变化将点云中的各点存入不同的分层数组链表对象的点数组对象ptArr中，在各个分层点的加入过程中同时统计该分层点云的重心PCent和分层面内坐标的极值点(YMin/YMax/ZMin/ZMax)。然后以点PCent为坐标原点，计算各点在极坐标下的极角并保存在对应的mark参数中，同时检查同一分层中点的mark值是否在0、1.57、3.14和4.71的4个特征值附近存在。如有2个特征值附近没有对应的mark值存在，说明此层中的点云并不是一个完成封闭的点云圈，而是一个开口的点云线(如图1所示)；否则该层中的点云是封闭点云圈(如图2所示)。对点云线只要按照点云线的主要排布方向(即由4个极值点计算出的在Y、Z方向上是最长排布方向)的坐标值进行排序就可以确定他们的相互关系了。对于封闭点云圈只要按照各点的mark值的大小排序就可以确定他们之间的关系。

图1 开口点云线(单层内) 图2 封闭点云圈(单层内)

数据点删减：对于分层点云中的任意点P，其前相邻点U和后相邻点Q已经确定，通过式(1)求得参数Angl，用1/Angl来反映该点的曲率大小。如果直接将Angl参数作为数据点是删减的依据，结果会造成一些曲率变化不大的平面点云精简后出现“大孔洞”只有边界上有少数数据点,因此本文引进另外一个与点间距离有关的参数Dis与Angl共同决定数据点的删留。Dis参数由式(2)求得，考虑到当前点P与前相邻点U之间的距离以及当前分层点云的几何尺寸大小，其中K是一个删减“孔洞”的影响因子，本文选为0.1。当某个数据点的相关参数满足式(3)，该数据点就会被保留，否则就被删除。式(3)中的α和β分别是点的曲率影响因子和点的距离影响因子，它们的值越大，相关的参数在数据点删留决策上影响也就越大中。本文选取α为0.85，β为0.15，Selector是决定这个点云精简比例的参数，其值越大，删去的点越多，点云数据压缩比越大，一般推荐使用0.3～0.4范围内选取。

(1)

(2)

(3)

整合点云并显示：将完成删减过程的所有分层点云加入一个完整的点云数组中并显示出来，以供用户决策观察。如用户满意就将精简后的数据保存，本释放相关数量空间；否则，释放精简数据结果，按照用户重新输入的参数再次进行数据精简操作。整个算法的流程图如图3所示。

图3 算法流程图

1.3 算法时间复杂度

本算法包括4个主要的步骤，假设点云中点的数量为N，点云读入和点云参数统计步骤中要经过取点、比较等操作，大概要经5N次操作；点云分层方向寻找步骤要进行快速排数和坐标值比较等操作，最坏情况要进行3NlogN+3n次操作，n是每次坐标值比较的次数，一般为几十次；数据点删减大概要经分层操作和分层点云参数统计、层内点云Angl参数计算、分层内点云的快速排序、Dis参数的计算和点删留条件的判断等操作，大概要经过的操作次数为4N+N+K(N/Klog(N/K))+N+N+N，其中K为分层层数；整合点云和显示也要经过2N次操作。整体算法大概要经15N+3NlogN+Nlog(N/K)+3n次操作，所有本文算法的时间复杂度为O(NlogN)，保证了算法精简的速度。

2 实验结果

为了验证算法的实际效果，在图4-图7中给出了高尔夫球头数据点云精简前后的对比视图。图4中显示的是原始的点云数据，该点云中包含了38 777个数据点，其他的相关参数在该截图上也有显示。图5中的截图是当曲率影响系数α取0.85、距离影响系数β取0.15、保留选点参数Selector取0.33的精简结果，精简后点云中删除了31 105个点，剩余7672个点，整体数据精简率为505.44%，从图中可以看到，曲率变化平坦的地方点很少，点主要集中的轮廓边缘，整体运行时间1389 ms；在图6中的截图的精简中，曲率影响系数α和距离影响系数β仍然取0.85和0.15，保留选点参数Selector变为0.31，精简后点云中删除了24 875个点，剩余13 902个点，整体数据精简率为278.93%。该图中因为保留选点阈值选小了，选择条件宽松了，留下的点多了，但仍然集中在曲率变化剧烈的边缘处，这次运行时间1061 ms。为了检测精简后的数据是否破坏了物体表面形状和表面光滑度，本文对图6中精简的点云进行了三角剖分，剖分的结果展示在图7中，该图说明精简后没有改变物体的形状，形成的表面光顺度较好。

图4 原始点云数据

图5 α=0.85 β=0.15 Selector=0.33精简结果

图6 α=0.85 β=0.15 Selector=0.31精简结果

图7 α=0.85 β=0.15 Selector=0.31精简剖分结果

3 结 语

本文通过分析三维扫描仪形成的点云数据的特点，提出了一种改进的分层曲率数据精简算法。该算法通过将空间立体点云按照点云的特点转化为平面内的点云。通过简单的平面内Angl参数的计算代替了多数文献中需要二次曲面拟合才能求得的点曲率，简化了算法过程，降低了算法的复杂度。同时为了防止点云面因过于平坦，造成精简后平面出现“大孔洞”的现象，算法中也引进了距离参数Dis。通过综合考虑点的曲率和点间的距离，形成了一个判别点是否被删除的标准。通过修改该判别标准公式中的系数，可以得到不同的精简效果。试验结果

证明，该算法不但算法复杂度低、运算速度快，而且精简效果好、数据精简率高，对物体形状和表面光顺度影响小。

[1] 刘德平,陈建军．逆向工程中数据精简技术的研究[J]．西安电子科技大学学报：自然科学版，2008,35(2):334-339．

[2] Yu Z W,Wong H S．ASM：an Adaptive Simplification Method for 3D Point-based Models[J]．Computer Aided Design,2010，42(7)：598-612．

[3] 方源敏，夏永华.基于改进的角度偏差法的采空区点云数据精简[J].地球科学与环境学报,2012,34(2):106-111.

[4] 王茹,周明全.基于聚类平面特征的三维点云数据精简算法[J].计算机工程,2011,37(10):249-254.

[5] 朱煜,康宝生.一种改进的点云数据精简方法[J]. 计算机应用，2012,32(2)：521-523.

[6] 李凤霞,饶永辉,刘陈,等.基于法向夹角的点云数据精简算法[J].计算机仿真学报,2012,24(9):1980-1984.

[7] 赵柳,马礼,杨银刚,等．逆向工程中散乱点云数据精简研究[J]．光电技术应用,2010,25(1)：60-63．

[8] Huang M C,Tai C C.The Pre-processing of Data Points for Curve Fitting in Reverse Engineering[J]．The International Journal of Advanced Manufacturing Technology,2010,16(9)：635-642．

IMPROVED MASSIVE POINT CLOUD REDUCING ALGORITHM BASED ON STRATIFIED CURVATURE

Chen Xinhe1Pang Junting2Zhou Bo3

1(SchoolofElectronicEngineeringandElectricAutomation,ChaohuUniversity,Chaohu238000,Anhui,China)2(SchoolofBusiness,HunanFirstNormalUniversity,Changsha410205,Hunan,China)3(SchoolofComputerandImformationEngineering,HeilongjiangUniversityofScienceandTechnology,Harbin150022,Heilongjiang,China)

Massive point cloud reduction shall consider both the complexity of the algorithm and the effect of reducing result. According to the characteristics of point cloud formed by 3-D scanner, we proposed to divide the spatial point cloud to the planar point cloud on scanning level, so that converted the space problem to the plane problem. Through simple calculation of Angl within the plane we got the point curvature, thus simplified the complexity of the algorithm. By introducing distance parameter Dis we avoided the emergence of “big hole” in reduction. By comprehensively considering the curvature of points and the distance between points, we formed a criterion determining whether to delete the points or not, and by modifying the coefficients in formula of determination criterion we could obtain different reduction effects. Test result proved that this algorithm was feasible in reducing practice of massive cloud point, and had the features of low complexity and high data reducing rate.

Massive point cloud Data reduction Curvature Segmented facets

2014-09-14。安徽高校省级科学研究2012年度项目(KJ2012B113)。陈新河，讲师，主研领域：三维重建。庞俊亭，副教授。周波,教授。

TP391

A

10.3969/j.issn.1000-386x.2016.04.062