摘  要： 用三维光学测量系统进行测量时，由于周围环境、人、设备等各方面的影响，测量数据中常常会掺入噪声。针对体外飞点和离群成簇噪声分别采取基于K_近邻搜索的平均距离去噪算法和改进的基于近邻点距传播的去噪算法进行处理，取得了较好的去噪效果。针对直接测量或者多次测量拼接获取的点云存在“粗糙毛刺”和点云多层重叠的状况，采用基于MLS的拟合平面投影光顺算法进行光滑处理，去除“粗糙毛刺”和打薄重叠区域。该光顺去噪预处理算法已经成功运用到三维测量系统的点云处理模块中。
关键词： 去噪；光顺；MLS；点云数据；K_近邻

    逆向工程是将现有实物产品利用数据采集设备获取物体外表面三维信息，再将数据进行处理及分析，最后实现产品的三维信息数字化，重建三维模型，对产品模型进行二次设计、修改及优化。物体三维数据采集设备从采集方式上可以分为两种类型：接触式和非接触式。其中，基于结构光的非接触式测量是当前及今后优先发展的重点，它具有快速、全面获取物体三维外形数据且对物体无损伤、对自然环境无污染的优点。但是由于测量环境、人、设备等因素的影响，采集到的点云中往往含有大量的噪声，难以被直接应用于物体三维模型的重建。为了使点云数据能够运用到后期的处理过程，满足曲面拟合及造型设计等对数据高质量的要求，必须先对原始数据进行去噪、光顺方面的预处理。逆向工程与三维测量技术的迅速发展也推动了去噪光顺研究的进展，国内外许多研究学者在这方面做了深入的研究，如基于局部曲面拟合的MLS方法[1]，基于Scale-Space理论的拉普拉斯方法[2]等。近年来，传统的网格模型去噪和光顺算法得到了长足的发展。其中很多网格模型的去噪和光顺算法可以直接扩展到点模型上，比较经典的有Fleishman的双边滤波去噪算法[3]。
    本文针对点云数据所含噪声以及点云特点进行分析，然后采用不同的算法进行去噪和光顺处理。
1 去噪光顺算法
    三维测量系统获取的点云数据中混杂的噪声大致可以分为3种：(1)体外飞点，偏离实测数据较远，悬浮在主体点云外围的孤立、稀疏点；(2)离群成簇噪声，偏离主体点云较远，小而密集的噪声簇；(3)混杂噪点，噪声点和真实点混杂在一起，该种点云的形态与实体中心点云成分层状，直观表现为点云表面很多“粗糙毛刺”。
1.1 体外飞点去除算法
    针对体外飞点无序、散乱的特性，本文采用空间单元栅格法[4]建立点云数据点之间的空间拓扑关系进而搜索每个点的K_近邻。首先读入测量数据点，将三维坐标点存入一个一维数组Array[]，同时得到其X、Y、Z坐标的最大、最小值，这样可以做一个与各个坐标轴平行的大长方体栅格，包围所有的三维点。根据数据点的密度将长方体栅格划分为多个小立方体栅格，并判断每个数据点所在的小立方体栅格，将数据点的序号追加到该立方体栅格对应的线性链表中。

    确定好当前点所在小立方体栅格的索引号后，对其所在小立方体及相邻的上、下、左、右、前、后共27个小立方体栅格中查找K个最近邻的点，求取pi的K_近邻。实验时K取20。
    建立好散乱点之间的拓扑关系，搜索到每个点的K_近邻之后，采用平均距离法进行噪声点去除。算法如下：
    (1)读入三维散乱点云数据P；
    (2)利用空间单元栅格法建立点云拓扑关系；
    (3)搜索点云中任意一点pi∈P的K_邻域NB(pi)；
    (4)计算当前pi与其K_邻域内K个点之间的距离，取其平均值M(pi)；
    (5)判断该平均距离M(pi)是否超过设定的阈值M?滓，若超过，则认为该点是离群噪声点，将其删除；
    (6)重复步骤(3)~步骤(5)，直到处理完整体点云中所有的数据点。
1.2 离群成簇噪点的去除
    有些测量数据中会出现一部分离主体点云(即被测物体点云)较远的小片点云和离散点，它们称之为“离群点簇”。含有成簇噪声的点云数据，由于主体点云数据点的数量比离群点的数量大得多，所以计算每一片点云中数据点的数目，认定数目最多的点云为主体点云，其余均为离群点，可以进行删除处理。
    本文采用改进的近邻点距离传播算法去除离群成簇噪声。近邻点距离传播算法[5]主要用来计算每片点云的数量，其主要思想是：设定点与其近邻点的距离阈值，并假设某一点为种子点，向其K_近邻中以点与点之间距离小于阈值的约束进行传播，获取相对应的K_近邻的点；接着以传播得到的点作为新的种子点，再向各自K_近邻中距离小于设定阈值的点做传播。注意，每个点只能被传播一次，传播的同时记录点云数据中点的个数。当传播不能继续时，说明此片点云数据已经被传播完毕，且点的数目计算完毕。再次重新寻求未被传播到的点作为新的种子点，继续传播。这样一直到计算完每片点云点的数目。最后，点数多的即是主体点云，剩余的为离群点，将要被删除。具体算法流程如下：
    (1)创建一维数组mark[i]=-1，{i=1，2，3，…，N}，记录含点的栅格属于哪片点云。其中N为全部点云中点的总个数；
    创建两个动态存储容器vec_1、vec_2分别记录每个数据点对应的序号；
    创建int类型number，并赋初始值为0；
    设定点距离阈值为threshold_dist；
    设定K的取值，建立各点的K_近邻；
    完成初始化。
    (2)依次检查并记录mark[i]，如果mark[i]=-1，则number=number+1，mark[i]=number，然后把对应的i值追加到vec_1并转到步骤(3)执行；对每个i值遍历完以后，转到步骤(4)。
    (3)分别以vec_1中的每个序号对应的数据点作为种子点，顺序查看其K_近邻数据点，如果数据点与种子点的几何距离dist<threshold_dist，并且该数据点对应的mark[i]=-1，则使mark[j]=number，并把此数据点的序号j追加到vec_2，否则继续查看K_近邻的下一个数据点。当vec_1中的序号对应的数据点都做过了种子点后，删除vec_1中的所有元素。然后，如果vec_2为空，转到步骤(2)；否则，以vec_2中的每个序号对应的数据点为种子点，顺序查看其K_近邻点，如果数据点与种子点的几何距离dist<threshold_dist，并且该数据点对应的mark[i]=-1，则使mark[j]=number，并把此数据点的序号j追加到 vec_1，否则继续查看K_邻近的下一个数据点。当vec_2中的序号对应的数据点都做过了种子点后，删除vec_2中的所有元素。如果vec_1为空，转步骤(2)，否则继续步骤(4)。

1.3 光顺算法
    在三维光学测量过程中，由于人为、环境等因素干扰，会出现“粗糙”点云数据，再者多次测量结果拼接后会出现点云叠层的情况。为了减少“粗糙毛刺”和叠层对测量数据后期处理和造型造成影响，本文采用基于移动最小二乘拟合平面投影法对测量数据中的“粗糙毛刺”和重叠层进行光滑处理。

    随着逆向工程的广泛应用和三维测量技术的发展，人们对曲面造型设计的技术要求越来越高，对点云数据预处理效果的要求也越来越高。本文对三维光学测量系统获取的含噪点云进行分析，对不同的噪声类型采取不同的去噪光顺预处理方法来获取高质量的点云。实验结果表明，本文的算法去噪光顺速度高、稳健性强，具有较高的实用价值。
参考文献
[1] ALEXA M，BEHR J，FLEISHMAN S，et al.Point set surfaces[C].Processing of IEEE Visualization 2001，San Diego，California，21-26 October 2001，IEEE，Piscataway，New Jersey，2001：21-28，537.
[2] LANCASTER P，SALKAUSKAS K.Surfaces generated by  moving least squares methods[J].Mathematics of Computation，1981，37(155)：141-159.
[3] FLEISHMAN S，DRORI I，COHEN-Or D.Bilateral mesh denoising[J].ACM Transactions on Graphics(TOG)，2003，22(3)：950-953.
[4] 张毅，刘旭敏，隋颖，等.基于K-近邻点云去噪算法的研究与改进[J].计算机应用，2009，29(4)：1011-1014.
[5] 王雪英.离群点预处理及检测算法研究[D].成都：西南交通大学，2009.