基于散乱点云的疵点去除与体积积分算法研究

吕 繁，郭晓锐，李红军

（武汉纺织大学 机械工程与自动化学院，湖北 武汉 430073）

随着计算机技术的快速发展，3D模型应用在数据处理与可视化上得到了技术支撑。相较于平面，3D模型能够直观地呈现物体多角度下视图和空间结构信息，在此基础上能更快速准确的计算被测物体的体积。目前获取3D模型主要信息的方式有：对物体进行超声波扫描；摄像机多视角获得照片序列，通过图像拼接生成全景图，计算目标物体的空间坐标；激光扫描仪对被测物体进行表面扫描，获得扫描范围内的点云数据等[1]。激光扫描仪具有采集速度快、扫描精度高、抗干扰性强等优势，常用的基于散乱点云计算体积的算法有：切片法，将物体的散乱点云按特定方向顺序进行等间距切片处理，利用切片面积及相邻切片间距求解每段点云片的体积，求和即得到物体整体体积[2]；投影法，计算三角剖分后每个三角面片及其在指定投影平面上的投影所形成的凸五面体的体积和[3]。投影法的优势在于无论被测物体的形状是否规则，通过扫描仪获取其整体外形表面的点云数据，经三角剖分和体积分割处理后积分求其体积。由于激光扫描仪的扫描精度、光照的反射干涉以及扫描环境的电磁干扰等因素会导致在实际扫描获取点云数据时出现视觉盲区和数据跃迁，从而导致本应相同的断面点云数据量数据不对称和数据缺失进而寻找疵点并去除，修正法向量偏差等[4]。

根据以上提出的问题和不足，本文提出基于空间三角剖分投影改进体积积分算法。三角剖分投影法的基本原理是：将扫描仪扫描出的断面点云数据进行三角剖分，由于扫描断面具有一定的空间顺序性和规律性，通过迭代的方式将断面数据一层层根据一定的拓扑结构划分空间三角面片，通过计算所有三角形相对于地面平面的投影体积来计算待测物体体积。在大型工业现场进行的物料体积计算和不同扫描精度下的点云数据体积计算测试结果都表明此体积算法能够简化、改进从三角剖分投影入手的点云断面数据的体积计算问题。

1 点云数据疵点去除处理

1.1 基于点云数据的三角剖分

三角剖分算法首先将凸包集合点U(k)的凸包分割成(k-2)个以凸包顶点为三角形顶点的三角形[5]，之后再对凸包三角形进行逐个迭代分割。将散乱点S(n)基于Lawson算法的逐点插入方式形成新的三角形。此算法的时间复杂度为O(N2)[6]。由于本文的点云数据是有一定拓扑结构的断面数据，在传统的三角剖分系统中由于退化现象而导致鲁棒性不强，故本文使用改进的层递式三角剖分算法对断面点云数据进行三角剖分。要求每个三角形均能够满足空圆特性，即任意三角面片的外接圆内均不包含散乱点云集中其他点[7]。

1.2 法向量调整及疵点去除

1.2.1 k邻域搜索

常用的搜索k邻域方法主要有八义树、空间单元格和kd-tree法。本文首先通过kd-tree建立空间拓扑关系，从而进行各数据点的最近邻域搜索，得到临近点的位置和各数据点的结构信息，同时能够减少处理时间，提高效率。在这个基础上，从密度较大的地方开始对数据点进行K邻域搜索（本文处理的数据有一定的范围），然后进行法向量计算，随之对其进行方向调整，这样就可以获得每个点以及临近点的法向量，去除掉每个点邻域外或者平均法向量相关性小于一定范围（与扫描仪的测量精度与每个断面之间的精度相关）的点，从而较有效的去除散乱点中疵点和离群点，避免出现因为个别点导致物体拓扑信息发生畸变的情况出现。

1.2.2 法向量的计算

由于每个三角面片的法向量的方向都不一致，需为每个三角形面片确定具有相同特征的法向量。为获得每个三角面片法向量，取一定半径内的点进行曲面拟合，在拟合曲面的基础上求对应三角面片的法向量。当邻域k值较小，而点云数据量庞大时，为减少曲面拟合时间，采用点 p ( xi, yi, zi)，p∈S(n)的k邻域中各点进行平面拟合，再计算点p的法向量的大小，代表此邻域中曲面在p点的法向量。本文使用最小二乘法来计算平面参数。设拟合平面为： a x + b y+cz − d =0,需要满足k邻域中的点到平面的距离最小，即满足a2+ b2+c2=1，在此限制下点p的最佳拟合平面为

由拉格朗日原理可知，F取极小值时有：d =ax + b y +cz ，(x,y,z)是k邻域点的重心坐标，，将d带入F中消去d，并对a、b、c求偏导数作协方差分析，得

可以得出：

将e→带入式（3）消去后得出

1.2.3 法向量调整

由上述方式获得点云数据的法向量集合后，将邻域内部选择该点的法向量进行判断，邻域内的其他点若与此点的法向量方向不同，则进行疵点调整，将反向的法向量进行反向调整，使其与此点的法向量方向一致。根据前面获得的各点的邻域及法向量，用此方式将每个点的k邻域内的点进行计算并调整和k邻域外疵点去除。

2 三角剖分投影体积积分算法

一般将目标所在的地面设置为投影面，那么在测量之前就需要获得扫描中心到地面的距离H，扫描左右两边是Y轴，前后是X轴，上下是Z轴。由此，每个扫描断面都是基于YOZ平面。由于三角面片是连续无间隔的，故每个三角面片在投影面上形成的凸五面体之间是紧凑的，单个的凸五面体体积之和就是所有三角面片在投影面上进行投影形成的多面体体积，即物体的三角网格模型体积可以由每个三角面片投影形成的凸五面体的体积之和表示。设每个三角面片的三个顶点为分别为设三个顶点按照Z的大小排序为： z3＞ z2＞ z1。为简化计算，将每个五面体分割为上半部分的小凸五面体和下半部分的三棱柱，由于小凸五面体三个侧面与投影平面是空间平面垂直，故部分无投影体积，因此上半部分凸五面体体积可由上下底面的三角面片△ABC和△AB'C'决定，且两个三角面片共用z值最小的点，即z1。

由图1可知，△A"B"C"是三角面片△ABC在地面的投影三角形，△AB'C'是以z1为高度的切割三角形，△AB'C'与△A"B"C"全等且在Z轴上平行。三棱柱体积是由三角面片的投影到XOY平面的△A"B"C"为底和高z1共同决定。故三棱柱的体积为

图1 三角面片投影体

点A到四边形BB'C'C的高度为OA，由单个投影三角形△A"B"C"的面积可以得到OA的长度为

由于侧面都是投影面，有BB'∥CC'，BB'⊥B'C'，得出四边形BB'C'C是梯形。小凸五面体又可以分割为两个四面体vABCC'和vABB'C'。由四面体体积计算公式v=1 3·Sh可得到其体积：

由于SBCC'和SBB'C'在同一平面上，由式（7）、（8）可以得到小凸五面体的体积为：

将式（6）带入消去B'C'和OA，则凸五面体的体积是

故每个三角面片投影形成的凸五面体的体积为

将式（5）和式（9）带入式（10）中可得到单个三角形投影体的体积

三角面片的集合和在投影平面上的投影三角形围成的凸多面体就是物体的体积。每个三角面片投影形成的凸五面体（形如图1所示）的体积为v。故被测物体的体积和为

3 实验与结果分析

基于上述算法，利用扫描仪SICK LMS511获取得到点云数据，扫描仪扫描仪精度为0.5°, 断面扫描精度为200mm，对大型沙堆进行点云数据获取，点云数据疵点去除和法向量调整后，采用此体积算法进行模型体积计算并三维可视化显示。

图2左是点云相对空间位置图，可以看出每个断面数据间隔相同，每个断面数据量也基本相同，此沙堆共含有14 581个点，经三角剖分处理后生成图2右所示模型图。

图2 沙堆点云及三维重建生成图

表1 体积算法验证

由图2和表1可知，采用本文算法计算体积偏差率小于1%，可符合工业要求。

4 结束语

本算法针对传统体积算法曲面拟合效率低下的问题，设计了一种基于扫描仪点云数据三角剖分快速计算体积的方法，将点云数据进行疵点去除和法向量矢量调整后，直接对三角面片投影进行了体积计算，物体表面是一个个小三角面拼接构成。算法体积计算的准确性，体积偏差率经计算小于1%。但未考虑到物体的曲面体积部分，需要进一步的提高算法的适用性和自修正性。