基于支持向量机的散乱点云三角化方法

摘要

本发明涉及一种基于支持向量机的散乱点云三角化方法，该方法先求出原始点云数据在平面内的最小矩形包围盒，在此包围盒内以原始数据中的最小点云密度均值进行数据点重采样，并生成平面三角网格；用原始点云边界多边形对平面四边域内的三角网格进行裁剪，得到实际边界域内的三角网格；然后应用最小二乘支持向量机对经过压缩的原始三维点云进行拟合，并通过此拟合模型将平面域内的三角网格向空间映射，得到三维空间的三角网格。通过实例验证表明，该方法在处理冗余或局部残缺数据时仍能生成较规则的三角网格，不易生成奇异网格或空洞。

说明书

技术领域：

本发明涉及一种基于支持向量机的散乱点云三角化方法。

背景技术：

目前在工业产品设计、医学检验、数字化人体模型建立、三维地图绘制等领域，都需要获取物理模型的表面形状信息。常用的表面信息获取设备为三坐标测量机、激光扫描仪和计算机断层扫描仪(Computerized Tomography,CT)。这些设备得到的数据点形式各不相同，三坐标测量机和CT得到的数据分布在相互平行的平面断层上，在局部有一定的组织规律性。但从全局看，这三种设备得到的数据点都呈现散乱分布的特点。在后续完成表面连续化重建的过程中，需要对这些散乱数据点间的拓扑关系进行描述。三角化就是将各数据点间以三角形相互连接，形成一张三角网格，建立起各数据点与其邻近点间的拓扑连接关系，以揭示散乱数据点所表示的原始表面的形状和拓扑结构。

根据所处理数据点维数的不同，散乱数据三角化可分为平面域和空间域内两类算法。平面域内散乱数据三角化大多采用Delaunay三角剖分算法及其优化准则，此类算法已比较成熟。但对于空间域内的散乱数据点，其间拓扑关系更加复杂，如果采用与二维数据同样的三角化算法，则很难取得理想的效果。因此，目前对空间散乱数据点的三角化理论和算法尚不完善，需进行进一步研究。特别是当测量点分布不均匀、含有冗余数据或局部残缺时，现有的直接三角化算法容易生成奇异三角网格或空洞。

发明内容：

鉴于上述现有技术中存在的不足，本发明针对工程实践中常见的单值点云数据研究其三角网格生成方法，对于非单值点云，可将其分割为多块单值点云分别进行三角化。本发明提出一种基于最小二乘支持向量机(简称“LS-SVM”)的空间散乱数据间接三角化方法，该方法在处理冗余或局部残缺数据时仍具有良好的适应性，且不易生成奇异三角网格或空洞。

为了实现上述发明目的，本发明所采用的技术方案为：

基于支持向量机的散乱点云三角化方法，包括对Z向单值点云数据进行边界特征提取、平面域内三角网格生成、基于LS-SVM的曲面拟合、三维映射生成空间域内三角网格；在曲面拟合前对原始数据进行数据压缩过滤原始数据中的冗余信息，所述数据压缩采用基于LS-SVM方法进行，具体如下：

(1)点云分块：将原始数据点云中的数据点分为若干数据块，每个数据块中的数据点数小于给定块内数据点数最大值，得到符合要求的D个数据块；

(2)块内剪枝：用LS-SVM对各个数据块分别进行拟合，计算出拉格朗日乘子α

(3)精度检验：将经过块内剪枝的D个数据块合并得到压缩后的数据点集S

进一步，所述点云分块具体方式如下：设原始测量点云S

进一步，所述平面域内三角网格生成包括平面矩形域内三角网格生成及平面内三角网格裁剪，裁剪过程分为边界预处理和网格裁剪，所述边界预处理步骤如下：

(1)在Y方向边界[y

(2)计算各条直线与初始边界多边形之间的交点：当原始边界上相邻两点间线段与L

(3)剔除冗余点，并按距离最近原则，建立新的边界点列之间的邻接关系：剔除冗余点是指在新的边界点列中，当相邻间距离小于点云密度时，则剔除后一个点；

所述网格裁剪根据三角形顶点与边界多边形的相对位置关系，对每个三角形进行处理。

进一步，所述网格裁剪具体方法如下：设三角形的三个顶点为V

设B

采用上述给出的两个位置关系函数分以下情况对三角网格进行处理：

当InorOut(V

当InorOut(V

当InorOut(V

当InorOut(V

进一步，所述平面矩形域内三角网格生成具体方法如下：

设原始点集为S

(1)将其沿Z向投影，得到XY平面内的点集S

(2)估算点云密度ρ：从S

(3)数据重采样：在y

Q＝int[(y

直线间的间距为d

y

对于每一条直线，以x

M＝int[(x

各点间距为d

x

(4)生成三角网格：经过重采样后的Q·M个数据点沿X、Y方向规则排列，应用Delaunay三角化方法即可生成平面域内的三角网格，记为mesh

进一步，所述基于LS-SVM的曲面拟合方法如下：

对于m个n维样本向量

其中

式中，w为权矢量，C为惩罚因子，b为偏差量，ζ

式中

求解式(3)，可得b和α，则回归函数可表示为：

当给定散乱点集S

进一步，求解式(3)时，需定义核函数，选择径向基核函数

进一步，所述三维映射生成空间域内三角网格的具体方式为：得到mesh

进一步，得到空间域内的三维网格后，为了控制三角网格对原始数据的逼近精度，需进行精度检验，方法如下：

(1)对于原始点集S

(2)计算点P

(3)通过式(4)计算出插入顶点

对于S

本发明提出一种以最小二乘支持向量机模型为映射函数的空间散乱点云三角化方法，是以空间局部残缺或冗余的信息不完备点云为输入数据，通过二维网格的三维映射技术，可自动得到规则、均匀的高精度、高质量网格，且所有网格形状均符合Delaunay原则，可广泛应用于工程数据可视化及逆向工程领域。

以下通过附图和具体实施方式对本发明做进一步阐述。

附图说明：

图1为本发明三角化方法的流程图；

图2为本发明三角化方法中数据压缩方法的流程图；

图3为网格裁剪时InorOut＝1时生成新三角形的示例图；

图4为网格裁剪时InorOut＝2时生成新三角形的示例图；

图5为采用本发明方法示例中原始测量点示意图；

图6为采用本发明方法示例中边界提取结果示意图；

图7为采用本发明方法示例中平面域内裁剪后三角网格示意图；

图8为采用本发明方法示例中压缩后数据点示意图；

图9为采用本发明方法示例中曲面拟合后示意图；

图10为采用本发明方法示例中生成空间三角网格后示意图。

具体实施方式：

本实施例公开一种基于支持向量机的散乱点云三角化方法，该方法如图1所示，主要包括对Z向单值点云数据进行边界特征提取、平面域内三角网格生成、基于LS-SVM的曲面拟合、三维映射生成空间域内三角网格。该方法先求出原始点云数据在平面内的最小矩形包围盒，在此包围盒内以原始数据中的最小点云密度均值进行数据点重采样，并生成平面三角网格；用原始点云边界多边形对平面四边域内的三角网格进行裁剪，得到实际边界域内的三角网格；然后应用最小二乘支持向量机对经过压缩的原始三维点云进行拟合，并通过此拟合模型将平面域内的三角网格向空间映射，得到三维空间的三角网格。下面将对上述每步具体内容详细说明。

在介绍本发明核心内容前，先介绍采用LS-SVM的曲面拟合方法：LS-SVM用等式约束替代传统支持向量机计算模型中的不等式约束，用误差平方和损失函数作为训练集的经验损失。通过这种变换，将传统支持向量机求解过程中的二次规划问题转化为线性方程组求解，减小了计算复杂度，提高了求解速度和收敛精度。

对于m个n维样本向量

其中

式中，w为权矢量，C为惩罚因子，b为偏差量，ζ

式中

求解式(3)，可得b和α，则回归函数可表示为：

当给定散乱点集S

在数据预处理阶段的边界特征点提取，对于Z向单值的点云数据，在提取其边界特征点时，可按如下现有步骤进行：点云向XY平面投影、单元格划分、边界单元提取、边界单元格内实际边界点提取、边界特征点拓扑排序。此部分属于现有技术，本实施例不对此展开过多介绍。

使用表面数据采集设备获得的原始数据点一般均较密，含有较多的冗余信息。如果直接使用原始数据点进行曲面拟合，则会使计算效率降低。因此有必要采用适当的数据压缩算法，在保证点云对表面形状表达精度的前提下，尽可能过滤原始数据中的冗余信息。因此，本发明提出一种基于LS-SVM剪枝的数据压缩算法，如图2所示，具体内容如下：

(1)点云分块：设原始测量点云S

(2)块内剪枝：用LS-SVM对各个数据块分别进行拟合，计算出α

(3)精度检验：将经过块内剪枝的D个数据块合并得到压缩后的数据点集S

关于平面域内三角网格的生成方式如下：

设原始点集为S

(1)将其沿Z向投影，得到XY平面内的点集S

(2)估算点云密度ρ。从S

(3)数据重采样。在y

Q＝int[(y

直线间的间距为d

y

对于每一条直线，以x

M＝int[(x

各点间距为d

x

(4)生成三角网格。经过重采样后的Q·M个数据点沿X、Y方向规则排列，应用Delaunay三角化方法即可生成平面域内的三角网格，记为mesh

对于上述平面矩形域内的三角网格，需使用边界多边形对其进行裁剪，以得到实际边界域内的三角网格。裁剪过程主要包括两个步骤：边界预处理和网格裁剪。边界多边形理论上可能为任意复杂的曲线，如果直接采用原始边界进行网格裁剪，则可能使计算过程不稳定。当点云密度较小时，可采用重采样的方法对边界多边形进行预处理，以便在保证精度的同时，确保计算稳定性。

边界预处理具体步骤如下：

(1)在Y方向边界[y

(2)计算各条直线与初始边界多边形之间的交点：当原始边界上相邻两点间线段与L

(3)剔除冗余点，并按距离最近原则，建立新的边界点列之间的邻接关系：剔除冗余点是指在新的边界点列中，当相邻间距离小于点云密度时，则剔除后一个点。

根据三角形顶点与边界多边形的相对位置关系，对每个三角形进行处理，可实现对三角网格的裁剪，网格裁剪具体方式如下：

设三角形的三个顶点为V

设B

采用上述给出的两个位置关系函数分以下情况对三角网格进行处理：

当InorOut(V

当InorOut(V

当InorOut(V

当InorOut(V

三维空间域内的三角网格生成方式如下：得到mesh

(1)对于原始点集S

(2)计算点P

(3)通过式(4)计算出插入顶点P

对于S

为了验证本发明上述三角化方法的实际效果，特将本发明所公开的方法用Matlab编程语言实现，并采用操作系统为windows XP，计算机CPU为Core3.3GHz，内存2G的计算机进行模拟验证。如图5所示，通过接触式三坐标测量机对某自由曲面零件表面进行数据采集，采样点间距为1.0mm，行间距1.0mm，共采集数据点6370个，原始数据中含有噪声点和空洞区域。获得原始数据后，按照本发明所提供方法进行下列操作：

(1)边界特征提取。边界提取结果如图6所示，图中‘.’表示原始数据点、‘*’表示边界单元格内的数据点，‘o’表示边界特征点。

(2)平面域内三角网格生成。平面域内生成的经裁剪后的三角网格如图7所示。原始三角形边长为1mm，共有6671个三角形。

(3)数据压缩并拟合曲面。压缩时将数据分为两块，设定压缩率为20％，最大拟合误差小于ε＝1×10

(4)空间三角网格生成。将裁剪后的平面域内的三角网格通过以LS-SVM表达的曲面(如图9所示)进行三维映射，可得到如图10所示的空间三角网格。

通过具体示例验证结果可见，采用本发明所公开的三角化方法所获得的网格非常规则、均匀，三角网格的精度高，没有出现奇异网格或空洞。

以上实施例仅用以说明本发明的技术方案而非限制，本领域普通技术人员对本发明的技术方案所做的其他修改或者等同替换，只要不脱离本发明技术方案的精神和范围，均应涵盖在本发明的权利要求范围中。