海量散乱点云out-of-core快速均匀精简算法

聂乐魁，孙殿柱，薄志成，尹逊刚

NIE Le-kui, SUN Dian-zhu, BO Zhi-cheng, YIN Xun-gang

（山东理工大学 机械工程学院，淄博 255049）

0 引言

在逆向工程中，为精确表示实物的空间信息，由光栅投影式三维测量仪等扫描设备获得点云数据规模趋于海量，甚至超出通用计算机主存储器的容量，导致点云数据无法进行可视化及交互性操作，需要对其进行精简处理[1～3]。

目前，点云数据的精简算法分为均匀精简算法与保形精简算法。Sun等[5]采用包围盒法来简化测量散乱点云数据，Martin等[6]提出均匀网格法，利用中值滤波计算包围盒的中值点来精简采样数据，能够快速均匀精简点云，但损失部分点云的几何特征。Chen等[4]对采样数据进行三角化，计算三角面片的法向量，并估计其曲率，基于曲率去除部分三角面片从而精简采样数据，能够很好地保留点云的几何特征，但精简速度过低。为能够快速显示与操作点云数据，应采用均匀精简算法对点云进行精简。但当精简海量散乱点云时，现存的均匀精简方法都将无法使用，而利用out-of-core的动态存储与加载特性可有效解决点云数据规模及计算过程中产生的数据量超出计算机主存储器容限的问题[1,2]。

为能够快速有效精简超出主存容限的海量散乱点云数据，本文算法通过改进CR树的结点分裂算法，将CR树上溢结点的子结点包围盒集转换为包围盒的中心点集，利用CR树与数据库SQLite相结合实现海量散乱点云的主存-辅存分级存储，计算CR树目标结点层中每个结点的均值点，将距离均值点最近的样点作为精简结果，根据所选结点层的不同实现海量散乱点云不同程度的精简，该算法能够快速均匀地对海量散乱点云进行精简，并且构建的动态索引可为后续工作所使用。

1 海量散乱点云的分级存储机制

CR树采用k均值聚类算法，将结点两路分裂改进为多簇分裂，结点插入代价与R树相仿，而查询性能与R*树相近，适合于数据密集型环境[7]。其结点分裂算法采用式(1)将N的子结点集{ni}转化为点集{pi}：

式中B(ni)表示N中任一子结点n的包围盒，V(x)表示包围盒x的容积，C(x)表示包围盒x的中心点。

利用上述方法所得点集往往与包围盒集的真实分布并不相符。如图1所示，对四个包围盒采用式(1)转换后的点集不能体现包围盒的位置分布，若应用k均值算法[7]将图1中的点集划为2个分类，可能会出现两个较大的包围盒被归为一类而两个较小的包围盒被归为另一类的结果，这显然并非理想的结果。

图1 上溢结点不合理的点集表示

本文算法将采用包围盒中心点集进行聚类计算，以使上溢结点的分裂问题能较大程度得以简化，即采用式(2)将上溢结点N转化为点集{pi}：

鉴于CR树良好的动态索引性能，将其与数据库SQLite相结合，分别把索引结点与点云数据存放到计算机主存储器与辅存储器中，实现点云数据的分级存储，从而能够有效的管理超出主存容限的海量点云数据，图2为分级存储机制的结构示意图。

图2 海量点云数据的分级存储机制

CR树与数据库SQLite相结合构建点云数据的分级存储机制具体步骤如下：

1）初始化：i←1，新建根结点N；

2）读取点云文件中第i行点数据1i，若1i为非空，则跳转至3），否则，分级存储机制构建完成；

3）应用CR树选择子树算法获取叶结点Nleaf，构建点链表point_l，并使Nleaf→point_l ；

4）将Nleaf对应辅存储器中的数据表data_l利用SQLite加载到主存储器中，并将data_l从辅存储器中删除，将除表头数据外的其他数据拷贝到point_l中；

5）将1i插入point_l，若point_l中元素的个数len≤M，则跳转至7），否则对Nleaf利用k-means算法进行聚类；

6）为聚类产生的每个叶结点Nleaf及其所指向的point_l在辅存储器中利用SQLite构建一个新的数据表data_l，并将它们存储到每个data_l中，其中表头为Nleaf，其他为point_l，删除主存储器中每个Nleaf所指向的point_l；

7）i←i+1，返回2）。

2 海量散乱点云的快速精简

CR树中的k均值聚类算法是一种基于样点数据之间的相似性划分数据对象的算法[7]，建树过程中该算法已对点云数据进行了空间相似性划分，因此距离结点所包含点集的均值点最近的点能够较好的反映该结点的点集分布趋势。基于所构建的主存-辅存分级存储机制，计算第h结点层每个结点所包含点集的均值点，将距离均值点最近的点代替该点集。可根据结点利用率[7]选取h值。以第h结点层为目标层，精简具体过程如下：

1）构建采样数据的分级存储机制；

2）获取第h层索引层的结点集N{ni}；

3）设i ←1，获取结点集N{ni}中结点个数num，初始化集合P{pi}；

4）计算结点ni中点集的均值点pm，并获得距离pm最近的点pmin，将pmin添加到集合P{pi}中，当i=num时，跳转至5），否则，i ←i+1，重复执行4）；

5）P{pi}为按照第h层结点的聚类结果对采样数据的精简结果。

在构建动态空间索引时，将点集表示进行改进，可以有效提高构建效率，其中通过调节结点层h的数值，可灵活调整采样数据的精简程度。

3 实验分析

采用光栅投影式三维测量仪获得手臂、半车身模型的点云数据，其原始点云如图3所示，运用本文算法对模型进行精简，根据文献[7]建议将上溢参数设为M=30。测试环境为：CPU 2.50GHz，主存4GB；操作系统为Gentoo Linux，测试程序为C语言。

图3 半车身模型的原始点云(点数180,524,735)

构建半车身模型的CR树动态空间索引结构，树的高度为8，取h值分别为5、6、7，建树时间为1328.25s，精简时间分别为34.82、37.26、40.05，精简效果分别为图4(a)、图4(b)、图4(c)所示。

图4 车身模型的精简结果

4 结论

1）CR树与SQLite相结合构建的主存-辅存分级存储机制能有效存储与管理海量点云数据。

2）利用距离均值点最近的点代替每簇点集有效提高了精简效率。

3）海量数据的out-of-core精简算法不仅可用于交互性显示与观察海量点云的几何特征，而且可作为海量数据进一步进行保形精简的预处理工作，同时其构建的动态空间索引结构也可为后续工作所使用，如三角剖分、拓扑邻域查询等。

[1]Wenzel K,Haala N,Fritsch D.Stereo model selection and point cloud filtering using an out-of-core octree[A].ISPRS-International Archives of the Photogrammetr:Remote Sensing and Spatial Information Sciences[C].2014:373-380.

[2]T.Whelan,L.Ma,E.Bondarev,et al.Incremental and batch planar simplification of dense point cloud maps[C].Conference on Mobile Robotics(ECMR)[C].2013,1:1-13.

[3]熊辉.大型复杂模具的点云预处理技术研究[D].南昌大学,2013.

[4]Chen Y H,Ng C T,Wang Y Z.Data reduction in integrated reverse engineering and rapid prototyping[J].International Journal of Computer Integrated Manufacturing,1999,12(2):97-103.

[5]Sun W,Bradley C,Zhang Y F,et al.Cloud data modeling employing a unified non-redundant triangular mesh[J].Computer-Aided Design,2001,33(2):183-193.

[6]Martin R.R.,Stroud I.A.,A.D.Marshall.Data reduction for reverse engineering[R].[S.1.]:Hungarian Academy of Science,Computer and Automation Research Institute,1996:63-69.

[7]Theodoridis Y,Brakatsoulas S,Pfoser D.Revisiting r-tree construction principles[A].Advances in Databases and Information Systems[C].2002.