一种基于最小广义方差估计的TLS点云抗差法向量求解方法
|
摘要
针对地面激光扫描点云中的粗差与不均匀采样对法向量计算的影响,基于最小广义方差估计与局部平面拟合原理提出了一种抗差法向量求解方法。首先通过快速近似最近邻居搜索算法得到最近k邻居点集,然后由确定型最小广义方差估计方法和多元马氏距离得到邻居点集协方差矩阵的抗差估计,最后根据主成分分析法(principal component analysis,PCA)计算得到抗差法向量。通过构造的模拟地面激光扫描(terrestrial laser scanning,TLS)点云数据将提出的方法分别与基于PCA、鲁棒PCA和随机抽样一致的法向量求解方法进行实验比较。结果表明,所提方法的抗差性能优异,且并行优化改进后可以满足大规模TLS点云的计算需求。将该方法应用于实际野外地形TLS点云数据,由求解的抗差法向量重建的泊松表面更符合实际地形,表明了该方法在实际应用中的有效性。
A robust normal estimation method based on local plane fitting and minimum covariance determinant(MCD)is proposed for terrestrial laser scanning(TLS)point cloud with gross errors and non-uniform sampling.Firstly,fast library for approximate nearest neighbors algorithm is performed to retrieve k nearest neighbor point set.Then,robust estimation of its covariance is calculated by DetMCD(deterministic MCD)and multivariate Mahalanobis distance.Finally,robust estimation of normal vector is calculated through principal component analysis(PCA)method.Compared with PCA,robust PCA and random sample consensus based normal estimation method,on simulated TLS point cloud,experimental results show that the proposed method can get more accurate normal estimation under the influences of gross errors.And its parallel improvement can meet the requirement of efficiency for large scale TLS point cloud processing.Further experiment on real TLS data from natural terrain shows that the proposed method helps to better Poisson surface reconstruction and prove its effectiveness in practical application.
A robust normal estimation method based on local plane fitting and minimum covariance determinant(MCD)is proposed for terrestrial laser scanning(TLS)point cloud with gross errors and non-uniform sampling.Firstly,fast library for approximate nearest neighbors algorithm is performed to retrieve k nearest neighbor point set.Then,robust estimation of its covariance is calculated by DetMCD(deterministic MCD)and multivariate Mahalanobis distance.Finally,robust estimation of normal vector is calculated through principal component analysis(PCA)method.Compared with PCA,robust PCA and random sample consensus based normal estimation method,on simulated TLS point cloud,experimental results show that the proposed method can get more accurate normal estimation under the influences of gross errors.And its parallel improvement can meet the requirement of efficiency for large scale TLS point cloud processing.Further experiment on real TLS data from natural terrain shows that the proposed method helps to better Poisson surface reconstruction and prove its effectiveness in practical application.
引文
[1] Li Guojun,Li Zongchun,Sun Yuanchao,et al.Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds[J].Geomatics and Information Science of Wuhan University,2017,42(1):123-129(李国俊,李宗春,孙元超,等.利用Delaunay细分进行噪声点云曲面重建[J].武汉大学学报獉信息科学版,2017,42(1):123-129)
[2] Tan Kai,Cheng Xiaojun,Zhang Jixing.Correction for Incidence Angle and Distance Effects on TLS Intensity Data[J].Geomatics and Information Science of Wuhan University,2017,42(2):223-228(谭凯,程效军,张吉星.TLS强度数据的入射角及距离效应改正方法[J].武汉大学学报獉信息科学版,2017,42(2):223-228)
[3] Hoppe H,DeRose T,Duchamp T,et al.Surface Reconstruction from Unorganized Points[C].The19th Annual Conference on Computer Graphics and Interactive Techniques,New York,USA,1992
[4] Li Bao,Cheng Zhiquan,Dang Gang,et al.Survey on Normal Estimation for 3D Point Clouds[J].Computer Engineering and Applications,2010,46(23):1-7(李宝,程志全,党岗,等.三维点云法向量估计综述[J].计算机工程与应用,2010,46(23):1-7)
[5] Yang M,Lee E.Segmentation of Measured Point Data Using a Parametric Quadric Surface Approximation[J].Computer-Aided Design,1999,31(7):449-457
[6] Alexa M,Behr J,Cohen-Or D,et al.Point Set Surfaces[C].The Conference on Visualization’01,San Diego,California,USA,2001
[7] Pauly M,Keiser R,Kobbelt L P,et al.Shape Modeling with Point-Sampled Geometry[J].ACM Transactions on Graphics,2003,22(3):641-650
[8] Fleishman S,Cohenor D,Silva C T.Robust Moving Least-Squares Fitting with Sharp Features[J].ACM Transactions on Graphics,2005,24(3):544-552
[9] Castillo E,Liang J,Zhao H K.Point Cloud Segmentation and Denoising via Constrained Nonlinear Least Squares Normal Estimates[M]//BreuM,Bruckstein A,Maragos P.Innovations for Shape Analysis.Berlin,Heidelberg:Springer,2013
[10]Schnabel R,Wahl R,Klein R.Efficient RANSAC for Point-Cloud Shape Detection[J].Computer Graphics Forum,2007,26(2):214-226
[11]Yoon M,Lee Y,Lee S,et al.Surface and Normal Ensembles for Surface Reconstruction[J].Computer-Aided Design,2007,39(5):408-420
[12]Li B,Schnabel R,Klein R,et al.Robust Normal Estimation for Point Clouds with Sharp Features[J].Computers&Graphics,2010,34(2):94-106
[13]Hubert M,Rousseeuw P J,Verdonck T.A Deterministic Algorithm for Robust Location and Scatter[J].Journal of Computational&Graphical Statistics,2012,21(3):618-637
[14]Muja M,Lowe D G.Scalable Nearest Neighbor Algorithms for High Dimensional Data[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2014,36(11):2 227-2 240
[15]Mitra N J,Nguyen A,Guibas L.Estimating Surface Normals in Noisy Point Cloud Data[J].International Journal of Computational Geometry&Applications,2004,14(4-5):261-276
[16]Rousseeuw P J.Multivariate Estimation with High Breakdown Point[J].Mathematical Statistics and Applications,1985,B:283-297
[17]Nurunnabi A,Belton D,West G.Diagnostic-Robust Statistical Analysis for Local Surface Fitting in3DPoint Cloud Data[C].The 22nd Congress of International Society for Photogrammetry and Remote Sensing,Melbourne,Australia,2012
[18]McLachlan J.Discriminant Analysis and Statistical Pattern Recognition[J].Technometrics,1993,88(422):695-697
[19] Wang Xingce,Cai Jianping,Wu Zhongke,et al.Normal Estimation and Normal Orientation for Point Cloud Model Based on Improved Local Surface Fitting[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(4):614-620(王醒策,蔡建平,武仲科,等.局部表面拟合的点云模型法向估计及重定向算法[J].计算机辅助设计与图形学学报,2015,27(4):614-620)
[20]Hubert M,Rousseeuw P J.ROBPCA:A New Approach to Robust Principal Component Analysis[J].Technometrics,2005,47(1):64-79
[21]Fischler M A,Bolles R C.Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J].Communications of the ACM,1981,24(6):381-395
[2] Tan Kai,Cheng Xiaojun,Zhang Jixing.Correction for Incidence Angle and Distance Effects on TLS Intensity Data[J].Geomatics and Information Science of Wuhan University,2017,42(2):223-228(谭凯,程效军,张吉星.TLS强度数据的入射角及距离效应改正方法[J].武汉大学学报獉信息科学版,2017,42(2):223-228)
[3] Hoppe H,DeRose T,Duchamp T,et al.Surface Reconstruction from Unorganized Points[C].The19th Annual Conference on Computer Graphics and Interactive Techniques,New York,USA,1992
[4] Li Bao,Cheng Zhiquan,Dang Gang,et al.Survey on Normal Estimation for 3D Point Clouds[J].Computer Engineering and Applications,2010,46(23):1-7(李宝,程志全,党岗,等.三维点云法向量估计综述[J].计算机工程与应用,2010,46(23):1-7)
[5] Yang M,Lee E.Segmentation of Measured Point Data Using a Parametric Quadric Surface Approximation[J].Computer-Aided Design,1999,31(7):449-457
[6] Alexa M,Behr J,Cohen-Or D,et al.Point Set Surfaces[C].The Conference on Visualization’01,San Diego,California,USA,2001
[7] Pauly M,Keiser R,Kobbelt L P,et al.Shape Modeling with Point-Sampled Geometry[J].ACM Transactions on Graphics,2003,22(3):641-650
[8] Fleishman S,Cohenor D,Silva C T.Robust Moving Least-Squares Fitting with Sharp Features[J].ACM Transactions on Graphics,2005,24(3):544-552
[9] Castillo E,Liang J,Zhao H K.Point Cloud Segmentation and Denoising via Constrained Nonlinear Least Squares Normal Estimates[M]//BreuM,Bruckstein A,Maragos P.Innovations for Shape Analysis.Berlin,Heidelberg:Springer,2013
[10]Schnabel R,Wahl R,Klein R.Efficient RANSAC for Point-Cloud Shape Detection[J].Computer Graphics Forum,2007,26(2):214-226
[11]Yoon M,Lee Y,Lee S,et al.Surface and Normal Ensembles for Surface Reconstruction[J].Computer-Aided Design,2007,39(5):408-420
[12]Li B,Schnabel R,Klein R,et al.Robust Normal Estimation for Point Clouds with Sharp Features[J].Computers&Graphics,2010,34(2):94-106
[13]Hubert M,Rousseeuw P J,Verdonck T.A Deterministic Algorithm for Robust Location and Scatter[J].Journal of Computational&Graphical Statistics,2012,21(3):618-637
[14]Muja M,Lowe D G.Scalable Nearest Neighbor Algorithms for High Dimensional Data[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2014,36(11):2 227-2 240
[15]Mitra N J,Nguyen A,Guibas L.Estimating Surface Normals in Noisy Point Cloud Data[J].International Journal of Computational Geometry&Applications,2004,14(4-5):261-276
[16]Rousseeuw P J.Multivariate Estimation with High Breakdown Point[J].Mathematical Statistics and Applications,1985,B:283-297
[17]Nurunnabi A,Belton D,West G.Diagnostic-Robust Statistical Analysis for Local Surface Fitting in3DPoint Cloud Data[C].The 22nd Congress of International Society for Photogrammetry and Remote Sensing,Melbourne,Australia,2012
[18]McLachlan J.Discriminant Analysis and Statistical Pattern Recognition[J].Technometrics,1993,88(422):695-697
[19] Wang Xingce,Cai Jianping,Wu Zhongke,et al.Normal Estimation and Normal Orientation for Point Cloud Model Based on Improved Local Surface Fitting[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(4):614-620(王醒策,蔡建平,武仲科,等.局部表面拟合的点云模型法向估计及重定向算法[J].计算机辅助设计与图形学学报,2015,27(4):614-620)
[20]Hubert M,Rousseeuw P J.ROBPCA:A New Approach to Robust Principal Component Analysis[J].Technometrics,2005,47(1):64-79
[21]Fischler M A,Bolles R C.Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J].Communications of the ACM,1981,24(6):381-395