基于局部和全局采样点云数据简化算法研究

付 玮，吴禄慎，陈华伟

(1．南昌大学机电工程学院，江西 南昌330031;2．南昌航空大学航空制造工程学院，江西 南昌330069)

1 引言

目前，3D激光扫描技术［1－2］在快速、准确地获取点云数据方面有了很大的进展，但是，如何处理这些庞大的点云数据成为基于3D激光扫描技术的主要问题。直接处理大量的点云数据，数据存储和处理便成为难以突破的瓶颈。实际上，并非所有的点云数据对模型重建都有用处，因此，有必要在保证一定精度的前提下，对点云数据进行简化处理。

一般点云简化方法包括:基于曲率和基于空间分割两大类方法。基于曲率方法有角度偏差法［3］、最小距离法［4］等;基于空间分割方法有均匀网格法［5］、包围盒法［6］、基于三角网格方法［7］。两类方法各有局限，基于曲率的简化算法虽能很好地保留几何特征，但是简化效率低［8］;基于空间分割的简化算法不适用于复杂特征和多曲率的散乱点云数据简化［9］。

很多研究学者在数据简化的研究中，提出了各种不同的处理方法，Vero和Leon［10］在1997年提出一种用误差带(Error Zones)减少多面体数据点的方法。Chen Y．H．［7］1999年提出一种通过减少网格模型中的三角形，从而达到减少数据点的方法。这种方法先直接将测得的数据转换成STL文件，然后通过减少STL文件的三角形数量，以实现减少数据量。本文提出了一种有效的点云数据简化方法，将局部和全局的采样特征相融合。该方法既考虑了局部点云细节，又考虑了点云的全局形状特征，可以有效的简化点云数据。对形状比较复杂的曲面(汽车模具等)有比较好的简化效果。

2 局部点云特征采样

本文采用基于点云的网格分割的非均匀网格法来提取局部点云特征。非均匀网格法［6］是点云简化中较常用的方法之一，采用非均匀网格法可以去除大量的数据点。该方法可以采用角度偏差法从模型表面点云数据中获取数据样本。

角度可通过三个连续点的方向矢量计算得到，如图1所示，(x1，y1)，(x2，y2)，(x3，y3)三点。角度代表曲率信息，角度大，曲率就大;反之，角度小，曲率也小。根据角度大小，高曲率的点可以被提取出来。通过角偏差抽取的点代表高曲率区域。为准确地表示零件外形，进行点云数据简化时，必须保留这些点。这样，使用角度偏移法进行点云提取后，对曲率小的区域采用大网格尺寸进行点云简化，对曲率大的区域采用较小网格尺寸进行点云简化。如图2所示，分离过程中网络尺寸大于最大网络尺寸，网格被进一步分割，直到小于最大网格尺寸为止。当对网格中点应用中值滤波时，将产生一个代表样点。最后，保留点是由每个网络的中值滤波点和角度偏移提取的点组成向量L。通过非均匀网格法进行点云简化，不但有减少点云数据的功能，还能有效去除噪声点，另外，这种方法只是选用其中的某些点，并不改变点的空间位置，可以很好地保留原始数据。

图1 角度偏差法

图2 非均匀网格法简化数据点

3 基于体素的全局点云特征采样

本文提出一种基于空间体素化方法对点云进行全局采样，可以最大限度地反映点云的全局特征。

体素是体图形学中描述体模型的基本数据单元。体素化(Voxelization)是从面模型到体模型的转换过程，其任务是:将物体的几何形式表示离散成最接近该物体的体素表示形式，产生体数据集，表示模型的空间体素跟表示图像的二维像素比较相似，可以理解为从二维的点扩展到三维的立方体单元。

对于数据量比较大的点云，它的点云分布一般是杂乱无章的，计算机处理这些点云数据时，非常耗费时间，效率比较低，不能达到实时处理的目的。因此，有必要将冗余点或者无用点去除，而体素化的方法，恰好可以解决这一难题，它可以大大地减少点云的数据量。

首先，使用规则的三维网格来划分点云空间，每个点云都在三维立体单元中，其存储了每个体素的质心坐标和点云数。体素化方法主要是针对点云的XYZ坐标值的编码。编码是采用12位的整数，它由3部分四位数组成。每部分表示其中一个XYZ坐标值，将其除以体素大小，便可将坐标值转换为体素单元，并且用最小的XYZ坐标值来替代原始点云数。参见公式(1)。这样，三部分就可以组成一个简单的编码。简单的编码原理如图3所示。

编码格式:

其中，X，Y，Z分别是体素的坐标值，X0，Y0，Z0分别是体素X，Y，Z坐标值的最小值;Vs是体素大小。

12位编码值储存在一个简单向量G中。向量长度等于点云数N。考虑到属于同一体素中的点云有相同的编码，向量元素根据它们的数值大小来分类。因此，同一体素内的点被聚集在一起。如图3所示。为了获取更多的采样点，体素单元网格需要进一步细分，如果体素单元网格的标准偏差大于给定值，则单元网格被继续细分;这个过程反复进行直到网格的标准偏差小于给定值;或者网格尺寸达到用户设定的值。通常网格最小尺寸根据零件复杂程度选定。

编码算法过程:假设有一个点，其体素尺寸大小取为0．1 cm。其X坐标值为:2468．232;Y坐标值为:3578．556;Z坐标值为:98．662。其Xmin为:2000;Ymin为:3000;Zmin为:0;根据公式(1)得:X体素值为:4682;Y体素值为:5785;Z体素值为:986。最后，12位的编码为:468257850986。表1是对12个体素点的编码。

图3 体素单元

表1 点云索引及编码

由表1可以看出，点1，7在A体素中;点4，8，11在B体素中;点2，5，9在C体素中;点3，6，10，12在D体素中。可以将点1，4，2，3(分别属于体素A，B，C，D)组成一个向量G，由该矢量代表体素的特征值，其他的值可以滤去，这样原来体素中有12个点，经过此方法后简化为4个点。但是可以完全的表达点云的全局特征。

4 点云特征的融合

为了获取更好的简化结果，这里将局部和全局采样点特征融合在一起。L是局部采样特征值，G是全局采样特征值，点云简化特征S可以通过公式(2)来定义:

其中，T是控制局部采样点集和全局采样点集的权重。如果T过大，这种方法仍然可以很好地表示全局形状，但它可能会失去许多局部的形状细节。当T变小时，可以比较好地表示局部形状，但全局形状表示可能会受到影响。因此，需要通过实验找到一个合适的T值。

5 实验及误差分析

5．1 算法实验

图4是利用该算法进行点云数据简化的流程图，首先通过三维光栅扫描、解相、去包裹、除噪等过程获取物体三维点云图。

图4 点云简化算法流程

通过非均匀网格法提取点云数据曲率比较大的局部特征值;然后运用空间体素编码法提取点云数据的全局形状特征值。最后，使用公式(2)将二者特征值融合，获取点云简化最佳效果值。

为了验证算法的有效性和正确性，本文分别对Bunny模型和某型号汽车模具点云进行简化，如表2所示三种算法的点云简化数据。测试环境为:Intel core 2．0 GHz，CPU 2G内存;根据实验，权值取T=6．5。

表2 实例点云数据

图5为实验简化效果图，通过上面实验可以得出，本文算法能够有效简化物体的点云数据，又能保证物体形状特征。空间体素编码法简化效率优于非均匀网格算法。本文提出的融合算法简化效率优于非均匀网格算法和空间体素编码法。Bunny模型和汽车模具在融合算法下，基本保留了模型数据的表面特征，简化数据量最少，而非均匀网格算法，简化数据明显较多;采用体素编码算法，简化数据比非均匀网格算法少。由此可见，本文融合算法的简化效率较好。本算法中的T值根据模型的曲率和形状是可调的。

图5 简化效果图

实验还对本文所提出的算法与文献［12］算法在点云简化时间上做了比较，本文算法在对Bunny模型简化耗时0．76 s，对汽车模具简化耗时0．94 s;而文献［12］算法对Bunny模型简化耗时0．87 s，对汽车模具简化耗时1．03 s。可见，本文算法的简化运行速度优于文献［12］算法速度，具有较好的实用性。

5．2 简化误差分析

为了评价简化点云集的准确性，在原始点云集和简化点云集之间的几何误差，Cignoni等［11］开发了Metro工具来比较曲面直径的误差。Pauly等［12］和Miao等［13］采用了相似的方法来评估简化误差。本文采用了原始点云集S和简化后的点云集S'的最大误差和平均误差［14］。

其中，每个点q∈S，几何误差d(q，S')是采样点q和它在简化点云曲面S'上的投影点q－之间的欧几里德距离。点云简化误差如表3所示。

表3 点云简化误差

使用本文提出的融合算法的最大误差和平均误差比非均匀网格算法和体素化编码法要小。可见其有效性较好。

6 结论

点云简化可删除大量冗余点云，而常用的非均匀网格法简化点云存在简化效率不高，容易丢失细节信息和关键特征的缺点。本文提出局部和全局特征法简化无序点云，根据调整T值灵活控制局部特征和全局特征所占权重，达到删减冗余点云数据的最好效果。实验例证本文算法简化点云数据既能保留突变区细节特征，又能大量删除平坦区冗余点云数据，相比非均匀网格法和空间体素法，具有更高的点云简化效率，而且简化误差也比较小。

［1］ LIU Weijun，SUN Yuwen．Principal，method and application of reverse Engineering［M］．Beijing:Mechanical industry press，2008．(in Chinese)刘伟军，孙玉文．逆向工程原理方法及应用［M］．北京:机械工业出版社，2008．

［2］ ZHANG Guoxiong．Three coordinate measuring machine［M］．Tianjin:tianjin university press，1999．(in Chinese)张国雄．三坐标测量机［M］．天津:天津大学出版社，1999．

［3］ Lee K H，Woo H，Suk T．Point data reduction using 3D grids［J］．The International Journal of Advanced Manufacturing Technology，2001，17(3):735－743．

［4］ LIU Deping，CHEN Jianjun．Point data reduction technique in reverse engineering［J］．Journal of xidiann university，2008，35(2):334－339．(in Chinese)刘德平，陈建军．逆向工程中数据精简技术的研究［J］．西安电子科技大学学报，2008，35(2):334－339．

［5］ Martin R R，Stroud I A，Marshal A D．Data reduction for reverse engineering Reccad deliverable document Icoperunicus project［J］．Computer and Automation Institute of Hungarian Academy of Science，1996，1068:63－6．

［6］ SUN W，Bradley C，ZHANGY F，et al，Cloud data modeling employing a unified non－redundant triangular mesh［J］．Computer Aided Design，2001，33(2):183－193．

［7］ Chen Y H，Neg C T，Wang Y Z．Data reduction integrated reverse engineering and rapid prototyping［J］．International Journal of Computer Integrated Manufacturing，1999，12(2):97－103．

［8］ SUN Dianzhu，ZHU Changzhi，FAN Zhixian．Reduction algorithm for scattered points based on model surface analysis［J］．China mechanical engineering，2009，20(23):2840－2843．(in Chinese)孙殿柱，朱昌志，范志先，等．基于型面特征的三维散乱点云精简算法［J］．中国机械工程，2009，20(23):2840－2843．

［9］ ZHOU Yu，ZHANG Wanbing，DU Farong．Algorithm for reduction of scattered point cloud data based on curvature［J］．Journal of Beijing Institute of Technology，2010，30(7):785－789．(in Chinese)周煜，张万兵，杜发荣，等．散乱点云数据的曲率精简算法［J］．北京理工大学学报，2010，30(7):785－789．

［10］Veron P，Leon J C．Static polyhedron simplification using error measurement［J］．Computer Aided Design，1997，29:287－298．

［11］Cinnoni P，Rocchini C，Scipigno R．Metro:measuring error on simplified surfaces［J］．Computer Graphics Forum 1998，17(2):167－174．

［12］Pauly M，Gross M，Kobbelt L P．Efficient simplification of point－sampled surfaces［C］．Proceeding of the 13thIEEE visualization conference，2012:163－170．

［13］Miao Y，Pajarola R，Feng J．Curvature－aware adaptive re－sampling for point－sampled geometry［J］．Computer－Aided Design，2009，41(6):395－403．

［14］Baoquan Shi，Jin Liang，Qing Liu．Adaptive simplification of point cloud using K－means clustering［J］．Computer－Aided Design，2011，43(1):910－922．