逼近散乱点云数据的三角形网格精确剖分

张 伟

（中国计量学院机电工程学院，浙江 杭州 310018）

逼近散乱点云数据的三角形网格精确剖分

张 伟

（中国计量学院机电工程学院，浙江 杭州 310018）

基于自组织特征映射神经网络构建的三角形网格模型可以实现测量点云压缩后的Delaunay三角逼近剖分，但该模型存在逼近误差和边缘误差。为减小三角形网格的逼近误差和边缘误差，构建了精确逼近的三角形网格模型。首先采用整个测量点云，对三角形网格模型中的所有神经元进行整体训练；然后对三角形网格中的网格神经元的位置权重，沿网格顶点法矢方向进行修正；最后采用测量点云中的边界点集，对三角形网格模型中的网格边界神经元进行训练。算例表明，应用该模型，可以有效减小三角形网格的边缘误差，三角形网格逼近散乱点云的逼近精度得到大幅提高并覆盖散乱点云整体分布范围。

逆向工程；三角形网格；神经网络；逼近误差；边缘误差；散乱点云

逆向工程是从一个已有的物理模型产生出相应CAD模型或实体模型的过程。在离散数据的逆向工程中，常采用小三角平面片（三角形网格）或三角域上的Bezier曲面片进行产品外形拟合。三角曲面能够适应复杂的形状及不规则的边界，因而在对复杂型面的曲面构造过程中以及在逆向工程中，具有很大的应用潜力。在面向快速原型制造的应用中，只要对给定的离散数据点进行三角剖分就能得到STL格式的零件几何表示。

近年来，以扫描测量为基础的“点云”数据采集的发展非常迅速，由此生成的三角形网格可多达几万甚至上百万个，这样不仅占用了大量的存储空间，也不利于网格的后续处理，尤其是在快速原型制造领域的应用更是存在着很多不便之处。如果依然沿用传统的三角片逼近造型方法，将遇到难以克服的困难[1]。

国内外学者对模型简化的研究已取得了一系列成果。Schroeder和Zarge[2]提出了基于顶点删除的网格删减方法；Hamann[3]通过曲率计算移去三角形，从而简化模型；Hoppe和Derose[4]提出了一种整体的网格优化过程，此后又采用渐进网格[5]的表示方法来存储和传输三角网格；Eck的 Rossignac[6]利用小波技术进行模型简化；Dehamer和Zyda[7]应用了自适应剖分方法进行网格简化；Garland和Heckbert[8]应用了边折叠操作方法进行网格简化；Hussain[9]提出了一种高效的特征保持简化算法；Chong等[10]结合遗传算法对大规模网格模型进行简化和优化。国内在这方面的研究起步较晚，但也取得了许多研究成果[11-17]。张伟等[18]进行了基于自组织特征映射(self-organizing feature map, SOFM)神经网络[19]的三维散乱测量点云的拓扑三角形网格自组织压缩重建的探索。该文所建三角形网格模型可以实现测量点云压缩后的Delaunay三角逼近剖分。Zhang等[20]在文献[18]的基础上，将单视密集散乱数据压缩、拓扑三角形网格逼近剖分和网格顶点法矢量生成统一在一个进程中。文献[18]、[20]不足之处是三角形网格模型在效率与精度层面与神经网络规模关联程度较高，提高神经网络规模，可以提高三角形网格的逼近精度，但同时也使神经网络的训练时间延长。

现有的三角形网格简化模型构建方法在效率与精度层面有待提高。本文将在文献[20]的基础上研究构建高效精确逼近散乱点云数据的简化三角形网格模型及其训练模式。

1 精确逼近的三角形网格模型

1.1 三角形网格自组织压缩重建

用于散乱点云数据压缩的 SOFM神经网络二维阵列模型，如图1所示。图中网络的输入矢量就是复杂曲面上的测点矢量Pj(x, y, z)，网络输出层具有m×n个神经元结点，即该三角形网格重建模型具有m×n个神经元。网络神经元对曲面空间测量样本点的学习和训练来模拟曲面上的点与点之间的内在关系，结点连接权重矢量集重构曲面样本点的内在拓扑关系及实现对测点集的工程近似化，实现曲面三维散乱点云的自组织压缩，构成三角剖分。

图1 数据压缩二维阵列网络模型

图2 六角形阵列邻区Nc

图1所示神经网络的权重矢量调节算法如式(1)所示。

式中，Pj为测点矢量；Wi(t)为神经元连接权重矢量； α( t)为修正率；Nc为以结点 c为中心的输出结点集合，如图2所示，图中c为与输入矢量Pj匹配最佳的输出结点； β（ di）是修正率加权函数，其中 di为邻区集合Nc中结点i到c之间的距离。

经过训练，权重矢量Wi收敛到所代表的感受野（即测量点集中与权重矢量Wi的欧氏距离最近的点集）的平均值，其反映了测量点集的统计特性。三角网格剖分可按如下步骤进行：①图2中tc时刻的六角形阵列邻区Nc集合中的结点c依次与Nc中6个相邻结点相连便形成三角网格剖分；②对输出层上的每一结点都如此处理；③神经元结点对应的权重矢量Wi在三维空间构成测量点集压缩后的Delaunay三角网格逼近剖分[18]。

1.2 三角形网格顶点法向矢量

设欲重构的曲面可以用参数方程式(2)表示。

式中，P表示曲面的笛卡儿坐标(x, y, z), Q表示曲面参数(u, v)。对于曲面采样测点矢量集，曲面参数可设为(x, y)。

曲面参数方程(2)是一复杂的非线性变换，要用一个函数拟合所测得的数字化点群数据是困难的。为此可将式(2)在Qs处泰勒展开。

式中，Ps，As和Qs可用扩展SOFM(ESOFM)[20]神经网络学习而得。此式表示所构造的神经网络权重矢量Ps处的微切平面方程。依据此式，微切平面逼近式(2)表示的曲面，在Qs局域Fs中可达到很高的精度。Fs由式(4)定义。

式中，s是激活神经元；Fs是神经元s对应的输入空间，即感受野；Ω是输入空间；Qr是神经元r的外部输入权重，即分类核心。

设s为自组织特征映射神经网络阵列中的任一神经元，SOFM自组织学习算法可使 s与 Qs形成空间有序特征映射。通过SOFM算法扩展同时使s与(Ps，As)建立映射关系。通过ESOFM神经网络训练，学习Ps、As及Qs，以满足式(3)。ESOFM神经网络的权重矢量Ps、As及Qs的训练采用文献[20]的调节算法。

按上述建立的ESOFM神经网络中，每一个神经元s有一个感受野Fs以及外部输入权重Qs，那么该神经元的输出就是Ps。当输入Q偏离Qs时，则神经元的输出由式(3)得到。这样ESOFM神经网络将整个数字化点群数据分成许多子区域，每个子区域用一个微切平面逼近，每组权重各自对相应的子区域负责。式(3)中的 As可用于计算相应子区域权重矢量 Ps（即三角形网格顶点）处的法向矢量ns，其计算公式如下。

式中，As由ESOFM神经网络训练后直接得到。

1.3 三角形网格模型的改进训练模式

文献[20]按照 1.1～1.2节所述模型及其训练算法，采用整个测量的散乱点云，对三角形网格模型中的神经元阵列进行若干循环的整体训练，实现将单视密集散乱数据压缩、拓扑三角形网格逼近剖分和网格顶点法向矢量生成统一在一个进程中。为减小三角形网格的逼近误差和边缘误差，本文拟按照以下3步训练模式，依次进行三角形网格模型的训练，3步训练的结果之间具有继承性（后继承前）。

1.3.1 网格神经元整体训练的改进

按照 1.1～1.2节所述模型及其训练算法，采用整个测量的散乱点云，对模型中的神经元阵列进行若干循环的整体训练。此步训练与文献[20]采用的训练方式不同之处在于此步的训练调高了与测量点云中的边界点集匹配的神经元的训练修正率 α( t)，以加大三角形网格边界神经元及其邻区的神经元对应的位置权重矢量向测量点云边界趋近的强度，如此生成的三角形网格Ⅰ可以减小边缘误差。

1.3.2 网格神经元位置权重矢量的修正

设三角形网格顶点神经元 s，网格顶点位置权重矢量为Ps，网格顶点法向矢量为ns，网格顶点神经元s在位置权重矢量Ps处的空间感受野为Fs。则本文提出的网格神经元s的位置权重矢量Ps修正如图3所示，修正步骤如下：

（1）在位置权重矢量Ps处的空间感受野Fs中，求出与Ps最近的点q；

（2）然后过点q作法向矢量ns（其经过Ps点）的垂直交线，垂足为′相对于Ps更加逼近被测曲面；

（3）按式(7)修正位置权重矢量Ps。

图3 网格神经元位置权重矢量的修正

按照上述位置权重矢量修正而产生的三角形网格Ⅱ较三角形网格Ⅰ更加逼近采样曲面。

1.3.3 网格边界神经元的微调训练

为进一步减小三角形网格边缘误差，按以下训练方式训练网格边界神经元。

（1）采用点云数据中的边界点集，只对三角形网格模型中的网格边界神经元进行训练，微调三角形网格边界神经元对应的位置权重矢量向测量点云边界趋近。网格内部神经元不参与训练。三角形网格边界神经元采用“0”六角形邻区 Nc进行训练，其等价为一维训练方式，可有效使三角形网格边界神经元对应的位置权重矢量趋近边界点集。

（2）采用边界点集中的角点点集，只对与边界角点匹配最佳的网格边界神经元进行训练，微调与边界角点匹配最佳的三角形网格边界神经元对应的位置权重矢量向测量点云边界角点趋近。网格其他神经元不参与训练。与边界角点匹配最佳的三角形网格边界神经元采用“0”六角形邻区Nc进行训练，其等价为一维训练方式，可有效使与边界角点匹配最佳的三角形网格边界神经元对应的位置权重矢量趋近边界角点点集。

如此生成的三角形网格Ⅲ可以进一步减小边缘误差。

2 三角形网格逼近精度的仿真实验

分别以球面点集和复杂曲面点集为对象，对所构建的三角形网格模型在个人计算机上进行仿真实验。

2.1 采用球面点集的仿真实验

仿真实验中，三角形网格模型中的神经元阵列包含10×12个神经元，采用式(8)表示的球面的随机采样点集进行训练，仿真实验结果如图4所示。

图4(a)表示采样点集，球面采样的参数范围为：u=0～π/4，v=0～π/3，R=10。采样点集包含3524个点，其中边界点集包含324个点，角点点集包含4个点；图4(b)表示应用文献[20]训练模式的仿真实验结果，图中绘出了所构建的三角形网格的顶点位置、顶点处的法向矢量以及采样边界点集，从图中可以看到存在较为明显的三角形网格边缘误差；图4(c)表示将图4(b)所示的三角形网格神经元位置权重矢量沿法向矢量方向修正的结果；图4(d)表示应用本文改进的整体训练模式的仿真实验结果，图中绘出了所构建的三角形网格的顶点位置及顶点处的法向矢量，从图中可以看到三角形网格边缘误差大幅减小；图4(e)表示将图4(d)所示的三角形网格神经元位置权重矢量沿法向矢量方向修正的结果；图4(f)表示应用本文提出的网格边界神经元的微调训练模式对图4(e)所示的三角形网格Ⅱ的网格边界神经元进行训练，所生成的三角形网格Ⅲ。

图4 仿真实例1

仿真实验中生成的三角形网格逼近散乱数据的逼近误差与边缘误差如表1所示。表1中2～6列分别表示图4(b)～(f)所对应的仿真实验精度。

表1 仿真实例1的实验精度(mm)

表1中三角形网格的边缘误差表示三角形网格边界顶点与曲面边界相离的程度。本文按以下步骤计算度量：①搜寻与网格边界顶点距离最近的边界点集中的点；②计算两者的欧氏距离；③求取所有网格边界顶点与边界点集相应的欧氏距离的平均值。这是一种相对评估边缘误差的方式，边界点集的采样密度对按此方式计算的边缘误差量值有较大影响。

表1中三角形网格的逼近误差表示三角形网格顶点集偏离曲面的程度，具体可采用逼近误差Ⅰ和逼近误差Ⅱ进行度量。

逼近误差Ⅰ按式(9)进行计算度量。

式中，m×n表示神经元阵列中分布的神经元数目；R表示球面半径；Ps表示三角形网格顶点的位置权重矢量，即三角形网格顶点的空间位置。

逼近误差Ⅱ表示沿网格顶点法矢方向度量网格顶点偏离曲面的程度，其按以下步骤计算度量：①过网格顶点并沿网格顶点法向矢量 ns方向，相交于曲面得交点p；②计算网格顶点与相应交点p之间的欧氏距离；③求取所有网格顶点与相应交点之间的欧氏距离的平均值。

采用不同神经网络规模进行仿真实验，各种训练模式的仿真实验精度对比，如表2所示。

表2 仿真实验的逼近误差I(mm)

2.2 采用非规则曲面点集的仿真实验

仿真实验中，三角形网格模型中的神经元阵列包含8×8个神经元，采用式(10)表达的非规则曲面的随机采样点集进行训练，仿真实验结果，如图5所示。

图5(a)表示采样点集，非规则曲面采样的参数范围为：x=π/2～5π/4，y=π/7～5π/6。采样点集包含2524个点，其中边界点集包含324个点，角点点集包含4个点；图5(b)表示应用文献[20]训练模式的仿真实验结果，图中绘出了所构建的三角形网格的顶点位置、顶点处的法向矢量以及采样边界点集；图5(c)表示将图5(b)所示的三角形网格神经元位置权重矢量沿法向矢量方向修正的结果；图5(d)表示应用本文改进的整体训练模式的仿真实验结果，图中绘出了所构建的三角形网格的顶点位置及顶点处的法矢；图5(e)表示将图5(d)所示的三角形网格神经元位置权重矢量沿法矢方向修正的结果；图5(f)表示应用本文提出的网格边界神经元的微调训练模式对图5(e)所示的三角形网格Ⅱ的网格边界神经元进行训练，所生成的三角形网格Ⅲ。

仿真实验中生成的三角形网格逼近散乱数据的逼近误差Ⅱ、边缘误差及神经网络训练时间如表3所示。表3中2～6列分别表示图5(b)～(f)所对应的仿真实验结果。表3中的训练时间表示得到相应三角形网格所需的训练时间总和。

图5 仿真实例2

表3 仿真实例2的实验精度(mm)

2.3 仿真实验结果的分析

由表1和表3可知本文所构建的三角形网格模型及其训练模式显著减小了三角形网格的逼近误差和边缘误差。

在采用二种点集的仿真实验中，对网格顶点位置权重矢量Ps，采用沿网格顶点法向矢量方向修正的算法，可以使三角形网格更加逼近采样曲面，大幅降低了三角形网格的逼近误差。该算法对本文和文献[20]构建的三角形网格模型均适用。表1中逼近误差Ⅰ与逼近误差Ⅱ相差极其微小，这可以间接证明所求的三角形网格顶点处的法向矢量非常接近相应交点 p处的曲面法向矢量，也表明了逼近误差Ⅰ与逼近误差Ⅱ在度量三角形网格逼近散乱数据点集的偏离程度方面是等同的。经过运用本文提出的网格边界神经元的微调训练模式，三角形网格的边缘误差再次明显减小，网格边界神经元逼近球面的逼近精度略有提高，结果使三角形网格顶点集逼近球面的平均逼近误差进一步减小。表 2表明，提高神经网络规模可以减小三角形网格的逼近误差。相比较而言，在减小三角形网格的逼近误差方面，采用本文构建的三角形网格模型中的训练算法，要比采用提高神经网络规模的方法更加合理和更有成效。

3 结 束 语

仿真实验表明本文构建的三角形网格模型及其训练模式在应用中呈现以下特性：①可以实现测量点云压缩后的Delaunay三角逼近剖分；②显著减小了三角形网格的边缘误差；③三角形网格逼近散乱点云的逼近误差得到大幅降低；④三角形网格覆盖点云整体分布范围。所构建的三角形网格，既可用于构造散乱数据插值曲面的前置处理，也可用于快速原型STL格式的零件几何表示。今后此研究主题的工作重心是关于复杂拓扑模型和大规模分布范围的密集散乱数据的三角形网格高效精确重建，拟采取先分片三角形网格构建，后整体融合训练重构的思路。

[1] 王平江, 黄雪梅, 陈吉红, 周 济. 曲面激光密集测量三维数据的三角片逼近方法[J]. 工程图学学报, 1998, 19(1): 17-27.

[2] Schroeder W J, Zarge J A. Decimation of triangle meshes [J]. Computer Graphics, 1992, 26(2): 65-70.

[3] Hamann B. A data reduction scheme for triangulated surfaces [J]. Computer Aided Geometric Design, 1994, 11(2): 197-214.

[4] Hoppe H, Derose T. Mesh optimization [J]. Computer Graphics, 1993, 27(1): 19-26.

[5] Hoppe H. Progressive meshes [J]. Computer Graphics, 1996, 30(2): 119-128.

[6] Eck M, Rossignac J R. Multi-resolution analysis of arbitrary meshes [J]. Computer Graphics, 1995, 29(2): 171-182.

[7] Dehamer J M, Zyda M J. Simplification of objects rendered by polygonal approximations [J] Computer Graphics, 1991, 25(2): 175-184.

[8] Garland M, Heckbert P S. Surface simplification using quadric error metrics [J]. Computer Graphics, 1997, 31(3): 209- 216.

[9] Hussain M. Efficient and feature-preserving triangular mesh decimation [J]. Journal of WSCG, 2004, 12(1): 167-174.

[10] Chong C S, Lee H P, Kumar A S. Genetic algorithms in mesh optimization for visualization and finite element models [J]. Journal of Neural Computing & Applications, 2006, 15(3): 366-372.

[11] 孙玉文, 王晓明, 郭东明. 反求工程中复杂多面体模型的网格简化算法[J]. 中国机械工程, 2001, 12(8): 922-925.

[12] 蒋亚军, 朱 理. 一种基于视觉特性的三角网格简化算法[J]. 计算机仿真, 2006, 23(10): 178-180.

[13] 陈华鸿. 基于四边形折叠的三角网格简化算法[J].中山大学学报(自然科学版), 2008, 47(4): 19-24.

[14] 车翔玖, 刘 杨, 赵义武, 车 娜, 高占恒. 基于k-邻域密度的离散点云简化算法与实现[J]. 吉林大学学报(理学版), 2009, 47(5): 994-998.

[15] 闫 涛, 姜晓峰, 王 昱. 基于三角网格模型简化的研究[J]. 计算机工程与科学, 2010, 32(12): 69-72.

[16] 李 龙, 何明一. 基于特征保持和二次误差测度的网格简化[J]. 西北大学学报(自然科学版), 2010, 40(3): 419-422.

[17] 张 果, 刘旭敏. 一种基于八叉剖分的近似曲率的边折叠简化算法[J]. 计算机应用研究, 2010, 27(5): 1955-1958.

[18] 张 伟, 姜献峰, 陈丽能, 马亚良. 基于神经网络的三角形网格智能重建[J]. 工程图学学报, 2004, 25(1): 71-75.

[19] Kohonen T. The self-organizing map [J]. Proceeding of IEEE, 1990, 78(9): 1464-1479.

[20] Zhang Wei, Jiang Xianfeng, Chen Lineng, Ma Yaliang. Mesh generation from dense 3D scattered data using neural network [J]. CADDM, 2004, 14(1): 30-35.

Reconstruction of Triangle Mesh for Unorganized Point Cloud Data with High Approximation Precision

Zhang Wei
(College of Mechanical and Electronic Engineering, China Jiliang University, Hangzhou Zhejiang 310018, China)

An approach based on the self-organizing feature map (SOFM) neural network has been developed to reconstruct Delaunay triangle mesh for the unorganized measured point cloud. However the approach suffers from approximation and boundary problems. A triangle mesh model with high approximation precision is proposed in order to reduce the approximation error and boundary error. First all the neurons of the mesh model are trained directly over the unorganized point cloud. Next the neuron location weights of the mesh model are adjusted along the normal vectors of the mesh vertices. Last only the boundary neurons of the mesh model undergo training by the boundary points of the measured point cloud. As a result of applying the proposed mesh model, the boundary error is greatly reduced and the mesh is drawn toward the sampled object with higher precision comparing with the original SOFM training algorithm. The feasibility of the developed mesh model is demonstrated on two examples.

reverse engineering; triangle mesh; neural network; approximation error; boundary error; unorganized point cloud

TP 391

A

2095-302X (2014)02-0188-07

2013-05-13；定稿日期：2013-06-17

浙江省自然科学基金资助项目（Y1091012）；国家质检总局科技计划资助项目（2006QK65）

张 伟（1964-），男，浙江金华人，副教授，博士。主要研究方向为CAD/CAM/RE、神经网络技术与应用等。E-mail：zhangwei@cjlu.edu.cn