计算机模式识别 文献阅读报告.docx

上海大学20142015学年春季学期研究生课程考试文献阅读报告课程名称： 计算机模式识别 课程编号： 07SAY9008 题目: 基于紧密度模糊支持向量机的3D点云去噪算法 研究生姓名: 学 号: 评语:成 绩: 任课教师: 评阅日期: 基于紧密度模糊支持向量机的3D点云去噪算法2015年6月1日摘 要：本文分析激光扫描仪获取的3D点云数据存在小振幅噪声和离群点的原因，设计基于紧密度的模糊支持向量机分类方法。本文首先通过包围样本的最小球半径来度量样本之间的紧密度。然后，根据样本在球空间的位置来确定模糊成员的类别。实验将该算法应用到3D点云数据中，通过与SVM算法和KNN算法比较，得到结论：基于紧密的的FSVM算法可以实现高效快速的3D点云数据去噪的目的。实验验证了该算法的有效性与合理性，在有效去除噪声的同时，该算法还能较完整地保留3D点云特征数据信息。关键词： 3D点云；紧密度；模糊支持向量机；去噪3D Point Cloud Denoising based on Fuzzy Support Vector MachineAbstract: In this paper, the noise in 3D point cloud data obtained from the laser scanner is analyzed first, and then a novel method that applies Fuzzy support vector machine to denoising 3D point cloud is proposed. In order to improve the performance of denoising, the affinity among point cloud samples is provided using a sphere with minimum volume while containing the maximum of the 3D point cloud samples. Then, the fuzzy membership is defined according to the position of samples in sphere space. Compared with the SVM and KNN algorithm, this method distinguishes the valid samples from the outliers or noises in 3D point cloud data effectively. The experimental results demonstrate its effectiveness and efficiency, which can preserve the integrity of characteristics as much as possible while denoising effectively in the 3D point cloud data.Index Terms: 3D point cloud; affinity; fuzzy support vector machine (FSVM); denoising1. 引言三维扫描技术的不断发展，使得获取具有丰富几何细节的数字模型成为现实。相比传统的三角面片表示方法，利用点云表示具有复杂几何表面的三维物体，具有存储简单、无需维护拓扑结构以及显示高效等优点。随着三维扫描设备在测量效率、精度等方面的突破，3D点云模型1,2正逐步成为网络上的三维图形数据的主要交换形式，广泛应用在工业、医疗、艺术、娱乐和虚拟现实等领域。然而，在3D点云数据获取过程中，人们对测量环境和传感器设备的认知有限，加之一些人为干扰因素及被测物体表面材质等的影响，会造成传感器感知信息不完整，采集到的3D点云数据往往带有许多小振幅噪声和离群点3,4。这些噪声点将严重影响三维模型构建的精度和曲面拟合的质量，使得重建后的3D模型粗糙零乱。因此，在进行曲面重构之前必须对其进行去噪和预处理。目前大多数去噪算法主要集中在3D网格上5。但由于3D点云数据本身缺乏拓扑连接信息，不能简单地将其推广到点云数据上来，点云数据去噪变得比较困难。3D点云数据分为有序点云、部分有序点云以及无序无组织点云数据。对于有序或者部分有序的点云数据来说，可以采用以下滤波方法进行去噪，最小二乘滤波、卡尔曼滤波、平滑滤波和双边滤波6,7等。上述的滤波方法虽然在去除小振幅噪声方面效果良好，但对于一些离群点大多只能依靠手工才能实现, 无法解决对散乱点云数据离群点的自动识别和去除的难题。为此，针对无序无结构的散乱点云数据，人们提出了基于几何特征的去噪方法8、K近邻去噪方法9和支持向量机去噪方法10等。支持向量机，是针对小样本统计问题而建立的，在现有有限信息的条件下得到最优结果。它能较好地解决小样本、非线性、高维数和局部极小点等实际问题，特别是在高维数据空间下，具有较好的泛化能力10，已在LiDAR信号处理11中得到了应用。但是，当训练样本中含有噪声或野值样本时，这些含有“异常”信息的样本与其他样本在构造最优分类面时有同样的贡献，使得获得的分类面不是真正的最优分类面。针对这个问题，Lin等学者提出了模糊支持向量机方法(FSVM)12,13,14,15，对不同的样本采用不同的惩罚权系数,使得在构造目标函数时，不同的样本有不同的贡献，赋予含有噪声或野值的样本较小的权值，从而达到消除噪声与野值样本影响的目的。本文的主要贡献在于针对激光扫描仪的特性，考虑到所获取点云存在噪声或离群点野值等问题，设计紧密度的隶属度函数，将FSVM应用到3D点云去噪中，通过分析点云数据样本之间的紧密度来描述类中各个样本之间的关系，利用包围样本的最小球半径来度量样本之间的紧密度。2. 模糊支持向量机给定训练样本集，其包含N个点：S=x1,y1,1,x2,y2,2,(xN,yN,N) ，其中xiRn, yi1,-1，i为模糊隶属度。假设是从原始空间中映射到高纬空间的非线性映射，在特征空间中利用结构风险最小化原理和分类间隔最大化思想，求解最优分类超平面的优化问题可转化为： min12|w|2+Ci=1Nsii s.t.yiw.xi+ b+j 1i0 . i=1,l (1)其中，w，b分别是分类超平面的权值和阈值，i是非负松弛变量，C0是自定义的惩罚系数。构造拉格朗日函数并根据KKT条件，上述最优问题可以转化为其对偶问题： max-12i=1Nj=1NijyiyjKxi,xj+i=1Nis.t.i=1Nyii=00iiC, i=1,N (2)其中，Kxi，xj=为满足Mercer定理的核函数。于是可得到最优分类面的决策函数为： fx=signi=1NiyiKx,yi+b (3)3. 基于紧密度的模糊支持向量机在3D点云去噪当中的运用 3.1噪声分析本文利用FARO激光扫描仪进行3D点云的数据获取，激光扫描仪内置的激光发射器发射出3R级激光，通过中心镜面的反射，使激光投射在物体表面，再反射回扫描仪接收模块，从而获得该点处的数据信息并对该点进行定位。在量测过程中，由于人们对量测环境的认知有限，模型与其参数值的选择与实际情况存在偏差，传感器分辨率有限，传感器感知会受到天气或环境等因素的影响，以及一些人为干扰因素与被测物体表面材质等的影响，导致3D点云数据受到不同程度的受到噪声的污染，采集到的3D点云数据往往带有许多小振幅噪声和离群点。图1（a）是扫描获得的人脸点云模型，采样点50500。在扫描过程中，由于人脸的抖动以及量测环境等因素的影响，获得的3D人脸模型的边缘出现了大量的野值点即噪声点。(a) 人脸模型 (b) 上海大学图书馆模型图1 FARO激光扫描仪获得的原始3D点云模型图1（b）是扫描获得的上海大学图书馆模型，采样点64217。图书馆建筑空间较大，且扫描仪自身有效距离80米，人为设置的扫描分辨率较低，导致距离扫描仪位置较远的边缘区域所获得点云数据量不足；而由于图书馆窗户的玻璃材质，以及量测过程中空气中尘埃粒子的影响，使得其存在着许多杂乱的噪声点。而这些噪声的存在，导致原本结构特征丢失了精细复杂的门窗等结构的几何特征。3.2模糊隶属度设计本文充分考虑到3D点云数据样本到所在类中心之间的关系,以及样本与类中其他样本之间的关系，引入基于样本紧密度的隶属度函数16。类似求最优分类面的方法,通过对下面目标函数的最小化得到最小包围球. 即表示为：R,a,=R2+Ci=1Nis.t.|xi-a|R2，i0 , i=1,2,N (4)其中，R为能够包围样本集的最小球半径，a为球中心。构造拉格朗日函数并根据KKT条件，可以将上式转化为求二次规划问题：LR,a,=j=1Nixixj-i,j=1Nijxixj ai=1li=i=1lixi (5)通过求解上式二次规划问题，就可以求得样本对用的Langrange系数i，最后最小包围球的半径由0j R (7)其中，R为样本集中最小包围球半径，d(xj)为样本集中样本xj到其最小包围球中心a之间的距离。由式(8) 定义的基于紧密度的隶属度xj可以看出：样本到最小包围球中心a之间的距离越大， 则该样本属于该样本集的隶属度就越小，也就是说样本的隶属度与其到最小包围球中心之间的距离成反比。3.3去噪算法针对3D点云数据，利用FSVM的分类原理，采用ERBF核函数，即Kx1,x2=exp(-|x1-x2|/2)，对点云数据进行分类，区分噪声点与非噪声点，从而实现对3D点云数据的去噪。具体的解决方案是将三维点云模型数据和噪声数据当作两种不同种类别的数据进行FSVM分类处理，通过将原始3D点云数据分成两种不同的类别来达到去噪的目的。具体步骤如下： 提取部分确定的三维模型数据和噪声数据以构成训练数据，并将训练数据表示成：Xi，其中XiR3。 为每个训练数据给定一个标签值yi，这里给定三维模型数据的标签值为+1，噪声数据的标签值为-1。 基于紧密度的隶属度函数xi，我们给每一个样本数据计算一个模糊隶属度i，然后结合样本给定的标签值，将训练数据表示为S=x1,y1,1,x2,y2,2,(xN,yN,N)。 对训练数据进行训练，通过将样本数据映射到高维空间，寻找最优分类面，以获得决策函数fx=signi=1NiyiKx,yi+b。 根据紧密度的隶属度函数i计算待测点云数据的模糊隶属度，并将待测点云数据表示为S=x1,y1,1,x2,y2,2,(xM,yM,M)，其中yi可以任意赋值+1或-1。 利用获得的决策函数fx对待测点云数据S进行预测，根据预测的结果值重新给待测数据赋值标签值yi。 通过中获得的标签值对点云数据进行分类，标签为+1的点即为我们所需要的模型数据，标签为-1的点即为噪声点。4. 实验结果分析采用Matlab以及C+混合编程，对利用FARO激光扫描仪获取的人脸与图书馆点云数据（见图1）进行去噪分析。硬件环境为：i5处理器，实验环境硬件配置为P4 3.2GHz CPU，2GB内存，256MB NVIDIA显卡。通过与支持向量机和KNN算法的去噪结果比较，验证该算法的有效性与合理性。(实验来源于自己研究结果)实验一：对图1（a）中的人脸模型进行去噪处理表1与图2给出了三种算法的人脸点云模型去噪结果分析。通过分析，可以看出三种算法都对实际人脸模型都起到了去噪效果。通过峰值信噪比可以看出，FSVM的去噪效果要好于KNN以及SVM算法。通过去除的噪声点数目可得KNN方法去除的噪点较多，其次是FSVM方法，SVM方法去除的噪点最少。然而由图2（d/e/f）中的耳朵区域特写图可以看出， KNN算法明显将人脸中的固有属性-耳朵区域的点云数据误当作了噪声进行去除，虽然去除的噪声点比较多，但是其却丢失了模型的部分特征数据，这样就使得在很大程度上无法将点云数据还原成真实的模型。而与SVM相比，FSVM通过分析点云数据样本之间的紧密度来描述类中各个样本之间的关系，利用包围样本的最小球半径来度量样本之间的紧密度。在寻找最优分类面获得决策函数的过程中，FSVM所选取的支持向量明显多于SVM算法，这样就使得FSVM选取的最优分类面优于SVM算法，使得FSVM的去噪效果更好。在有效去除噪声的同时，该算法还能较完整地保留3D点云特征数据信息。 表1人脸模型去噪实验分析(FSVM,SVM,KNN)去噪前点集个数去噪后点集个数支持向量个数整体分类率峰值信噪比FSVM5050049662201588.5364%44.3234dbSVM5050050266187980.4533%42.3423dbKNN5050047957-83.3654%41.3473db（a）KNN （b）SVM （c）FSVM（d）KNN （e）SVM （f）FSVM图2 人脸模型去噪效果与耳朵特征信息(KNN/SVM/FSVM)实验二：对图1（b）中的上海大学图书馆模型进行去噪处理表2与图3给出了三种算法的图书馆建筑点云模型去噪结果分析。明显地，通过峰值信噪比可以看出，FSVM的去噪效果要好于KNN以及SVM算法。同样， 见图3（d/e/f），K近邻算法明显去除图书馆模型四周边缘大量的点，而这些点恰好是图书馆模型边缘几何特征的具体体现。由表2可知，K近邻算法比FSVM算法多去除了220个点集数据，可见KNN方法并没有很好地区分点云模型的噪声点与特征信息点。导致无法保留更多的点云模型的特征。而与SVM相比，见表2，FSVM算法获得支持向量个数多于SVM算法，而且峰值信噪比也比SVM算法高，这是因为传统的支持向量机根本无法将不确定因素所引起的噪声与高精度的门、窗点云数据进行区分开，而基于紧密度的FSVM，能够很好的对这些不确定噪点进行惩罚，从而消除其对样本的影响。表2上海大学图书馆模型去噪实验分析(FSVM,SVM,KNN)去噪前点集个数去噪后点集个数支持向量个数整体分类率峰值信噪比FSVM642176182753898.4241%44.0210dbSVM642176192850897.3883%42.6421dbKNN6421761607-97.9492%43.7960db（a）KNN （b）SVM （c） SVM（d）KNN （e）SVM （f）FSVM图3 上海大学图书馆去噪效果与特征信息分析（KNN/SVM/FSVM）5. 总结与展望本文通过引入基于紧密度的模糊隶属度，将模糊支持向量机应用到3D点云去噪中，以期获得较好的去噪效果。通过对FARO激光扫描仪所获取的实际点云数据进行实验分析，验证了该算法的有效性与合理性。但此方法仍然存在很多缺点：如数据量大、耗时长等。下一步的研究方向是学习压缩感知理论，在源头减少样本的数据量的同时，保存样本的信息。此外，研究字典对学习方法，来提高去噪的效率和加快去噪速度。参考文献1 Radu Bogdan Rusu, Zoltan Csaba Marton, Nico Blodow, Towards 3D Point cloud based object maps for household environmentsJ Robotics and Autonomous Systems,2008(11):927-9412 H.Woo, E.Kang, Semyung Wang, Kwan H.Lee, A new segmentation method for pointcloud dataJ International Journal of Machine Tools and Manufacture, 2002(2):167-1783 Dafeng Liu, Wenhe Miu, Ning Dai, Research and lementation for denoising noisy scattered point dataJ Journal of southeast University,2007(6):1108-11134 Jun Yang, Changlin Zhu, Study on Denoising and 3D Reconstruction for Point-Based Models D.Shanghai Institute of metallurgy academy of Sciences of china, 20005 Sanyuan Zhang, Qiang Li, Yin Zhang, Feature-preserving mesh denosingJ. Sciencepaper Online, 2010(2):0129-01336 Xiaoyan Du, XiaoFeng Jiang, Chuanggang Hao,Blateral Fltering Denoising algorithm for Point-cloud ModelJ.Computer Applications and Software,2010(7):263-2657 Bo Xu, Jie Tang, Gangshan Wu, CUDA-based Point Cloud Denoising AlgorithmJ.Computer Engineering,2011(2):0224-02278 Yu Fan, Yunan Wang, Junjie Wang, A Triangle Filter Method for Reducing Noise Error of Points Clouds Data Based on Geometric RelationsJ.Value Engineering,2011(20):0217-02199 Yi Zhang, Xumin Liu, Yi Sui, Research and improvement of denosing method based on K-neighborsJJournal of Computer Application, 2009(4):1011-101510 Qin Zhang, Yong Cai. Application of Support Vector Machine in Point Clouds DenosingJComputer technology development, 2011,6(6):0085-008911 Bingyu Sun, Deshuang Huang, Haitao Fang. Lidar Signal Denoising Using Least-Squares Support Vector MachineJ.IEEE signal processing letters, 2005(12):0101-010412 Xiang Zhang, Xiaoling Xiao, Guangyou Xu. Guangyou Xu. Fuzzy Support Vector Machine Based on Affinity Among SamplesJ. journal of software. 2006.5(5):951-95813 Chang Liu. Fuzzy Support Vector MachinesD.Liaoning Normal University,2008,614 Rui Zhang, Yichen Ma, Xianbao Duan, New Algorithm of Fuzzy Support Vector Machine for Classification with Outliers J. Journal of Xian Jiaotong University, 20