复杂曲面点云非均匀简化技术研究

高红卫，刘庆刚

（1.宝鸡文理学院机电工程系，陕西 宝鸡721016；2.济宁职业技术学院机电工程系，山东 济宁272037）

0 引言

逆向工程是以产品实物、模型作为研究对象，根据测量三维点云数据通过几何建模方法重构实物模型的过程。在三维数据测量和曲面重建过程中借助计算机硬件设施及相关软件为研究平台，充分利用数字化优势，有利于产品设计向智能化、集成化方向发展，是一种产品设计的新手段［1］。实物模型表面信息由大量三维坐标数据来精确描述，数以百万的冗余数据，使得数据运算速度降低、曲面重构难度增大。因此，点云数据简化非常必要。近些年来，人们在点云简化方面做了大量研究［2－5］。通常，对于简单规则点云数据精简方法较多，容易实现，但对于曲率变化大的复杂曲面，点云直接进行简化时容易出现特征点丢失等问题、有时甚至难以直接简化。

针对复杂曲面点云简化问题，提出按照曲率分块，自动划分特征区域的非均匀数据精简方法。通过建立点云之间拓扑关系，按照曲率大小进行数据分块，划分特征点区域，点云曲率较大的细节特征区尽可能多保留数据，较非特征区域数据将被大量简化，从而可以解决数据精简时特征点丢失问题。

1 点云拓扑关系的建立

通常海量点云数据之间相互独立，没有任何联系；如果在同一坐标系中，把每一个点看作构成整个物体的分子，通过计算邻近关系点，来进一步表达点在整个点云模型中的几何性质，构成点云数据的模型就像分子与分子之间关系一样，使孤立点云形成一个相互联系的整体，建立点云之间的关系。

点云拓扑关系建立采用最邻近分类算法［6］。思路如下：在定义类决策上由待分样本所属的类别依据最邻近的一个或者几个样本类别来决定（假设所选择的邻近点都是已正确分类的对象），主要根据周围有限的邻近样本来确定所属类别。在类别决策时，只与少量相邻样本有关。因此，该方法适合于类域的交叉或重叠较多的待分样本集。

KNN算法数学描述：给定数据集D，可根据KNN（q）＝｛｜pi－q｜≤｜p－q｜，pi∈D｝，pi，（i＝1，2，3，…，k）计算得到q的邻近点。首先把点云数据按空间位置将每一维进行区间划分，通常划分成n个子区间，再把每一个区域进行编码，最后根据编码寻找落在邻近区域中的点，直到找出数据点q的k个最近的点，计算流程如图1所示。

图1 算法流程

2 点云曲率计算数学模型

2.1 点云曲率

曲率用来度量几何体的不平坦程度，能够表示曲线弯曲的程度。即L＝lim｜Δα／Δd｜，Δd趋向于0时，定义L为曲率；当角度和弧长同时趋近于0时，就是光滑曲线曲率的定义。对于点云模型而言，数据点之间是离散的，无法对单独一个点计算曲率；通常点云曲率定义为点与点之间形成的曲线（或者曲面）的弯曲度［7］。因此，计算离散点云的曲率时，首先计算采样点的K最邻近点，利用邻近点形成的局部曲面计算曲率信息。在连续曲线中，平面曲线曲率是指曲线上某个点的切线方向角对弧长的偏离程度；若曲率值越小，则曲线越平坦；反之，曲线弯曲度越大［7］。

2.2 曲面微分法计算点云曲率

在对离散点云建立拓扑关系后，得到样点k个邻近点，对k＋1个点进行局部曲面拟合、微分即可求得点的曲率。为了达到较好拟合效果，采用双三次B样条曲面微分法计算点云曲率［8］，其定义为：

Bi，j为曲面控制点；Ni，k与 Mj，l分别为u 和v 方向的三次B样条基函数。Ni，l（u）与 Ni，k（u）可分别用下式来表示，即

Mj，I（v）定义与 Ni，k（u）类似，为曲面的另一基函数，根据式（1）建立B样条曲面方程为：

对邻近点进行拟合得到局部曲面，并对曲面进行偏导得到点的一阶导数二阶导数和混合偏导，结果为：

根据一阶、二阶导数、混合偏导及微分几何中曲率的定义，计算采样点的平均曲率为：

（A B C ）＝［Wu×Wv］［WuuWuvWvv］，计算出的点云平均曲率和曲面面积的第一积分密切相关，点云曲率变化越大，则说明曲面越复杂。

3 特征点区域划分方法

点云特征点是描述复杂曲面几何特征信息的关键元素，在简化点云时保留特征点尤为重要。通过计算点云曲率对点云分块，进行特征区域自动划分。在非特征点区域，按照均匀取样法进行数据精简；在特征点区域随着点云曲率的减小精简率依次增大，实现根据曲率变化进行非均匀简化。为了有效提取点云模型曲率较大的特征点，可根据K邻近点坐标集构造函数［9］，即

np为p 点的法矢；｛xj｝（1≤j≤k）为p的K 邻近点pi的坐标集；｜（x－xj）·np｜为pj到p 点处切平面的距离。在计算特征点过程中，选择不同的K值可得到不同简化效果。一般情况下，c（p）计算值越大，则点云在该处的曲率就越大；为了划分点云特征点区，可以通过改变δ值（δ＝α／N∑c（pi））的范围来确定特征点。其中，N为点云数目，α为特征点调节系数；当α改变时，δ值可随之成正比变化。点云特征区域划分原则：如果c（p）大于阀值δ，则判定p为特征点；否则，认为p为非特征点。大量实验表明，当α值取22≤α≤28时，点云具有较好的简化效果。通过改变调节系数α的大小，来设置特征点区域范围。

当α＝22时，设定为特征点上限区，如图2所示。若曲率值过大，点云光顺性不仅变差，且该处点云可能存在噪声点，应按非特征点对待。当α＝28时，设定为点云特征点下限区，如图3所示。处于点云特征点上限区①与下限区④之间的点都划分为特征点区，如图4所示。曲率值小于下限区④时划分为非特征点区域，曲率值较小，点云处于较平坦区域，该处点云应被大量简化。

图2 α较小时特征点上限区

图3 α较大时特征点下限区

图4 点云特征点区域范围

4 点云简化效果分析

通过将OpenGL图形库函数嵌入到VS2008中，完成三维空间的点云数据在二维环境中计算和转化及处理。空间散乱点云的每个点都有3个数据，即X，Y，Z坐标，每个点云对应1个ASCII值，可将每个点云数据信息存储在预先定义的一个共同体内，对共同体中定义的数据进行分析，并可以将其存入相应的数组来实现［10］。因此，以米奇面部点云模型为例，分别采用系统算法和均匀取样法进行简化，对结果对比分析。

米奇面部点云特征复杂、原始点数多达38 431个，如图5所示。在耳根处、眼部及嘴部周围点云曲率较大，特征点较多，局部细节特征明显。通过建立点云拓扑关系，分析面部点云曲率。根据曲率大小自动进行区域划分，红色区域点云曲率较大，属于特征点区域范围；在其耳部中心区、额头及嘴唇等处点云较为平坦，如图6中虚线选择区域，属于非特征点区。显然，划分结果与实际面部特征较为吻合。

图5 米奇面部特征点云

图6 面部点云非特征点区域

表1 实验参数

按照表1中实验参数，采用文中算法简化后点云数为9 213个，精简率为76%，如图7所示。采用均匀取样法，精简率为77.4%，简化效果如图8所示。通过分析发现，2种方法都能完成点云精简。在精简率相近时，均匀取样法视觉效果较好，但特征点丢失较多，影响后续曲面重构精度；显然通过比较简化效果，本文方法能实现在曲率较大处点云密度也大，特征点被更多保留，简化方法更加合理。

图7 本文算法点云简化效果

图8 均匀采样法点云简化效果

5 结束语

针对复杂曲面点云简化，均匀取样法简化时不能预测哪些点将被去除，点云密度大小仅由取样间隔决定，容易造成曲面点云简化失真等问题；通过分析曲率云图，进行特征区域划分，点云密度大小随着曲率的减小而降低，在非特征点区域精简率最大。实验结果表明，当特征点调节系数α值在22≤α≤28范围内时，点云简化效果较好，精简率达76%，该方法针对复杂曲面点云简化具有一定的研究应用价值。

［1］ 单 岩，谢斌飞.Imageware逆向造型技术基础［M］.北京：清华大学出版社，2006.

［2］ Chen Y H，Neg C T，Wang Y Z.Data reduction in jntegrated reverse engineering and rapid prototyping［J］.Intemational Journal of Computer Integrated Manufacture，1999，12（2）：97－103.

［3］ Sun W，Bradley C，Zhang Y F.Cloud data modeling em ploying a unifed non－redundant triangle mesh［J］.Computer Aided Design，200l，33（2）：183－193.

［4］ 马 磊，彭国华，耿东方.基于八叉树的海量测量数据的非均匀简化［J］.计算机应用，2007，27（8）：2027－2029.

［5］ 王宏涛，张丽艳，杜 佶，等.测量点集的简化及其隐式曲面重建误差分析［J］.中国图象图形学报，2007，12（11）：2114－2118.

［6］ Vries A D，Mamoulis N，Nes N，et al.Efficient KNN search on vertically decomposed data［C］.Proceedings of the 2002ACM SIGMOD International Conference on Management of Data，Madison，Wisconsin.Madison：ACM press，2002：322－333.

［7］ 贺美芳，周来水，神会存.散乱点云数据的曲率估算及应用［J］.南京航空航天大学学报，2005，36（4）：516－519.

［8］ 吴剑煌，刘伟军.点采样曲面的曲率估计［J］.仪器仪表学报，2006，27（12）：1557－1564.

［9］ Song H，Feng H Y.A progressive point cloud simplification algorithm with preserved sharp edge data［J］.O－riginal Article，2009，45：583－592.

［10］ 张树森，郑成志，肖胜兵，等.基于 MFC环境下利用OpenGL函数实现点云数据拼合［J］.机床与液压，2006，（2）：76－78.