PCA-Based Denoising Algorithm for Outdoor Lidar Point Cloud Data
<p>The general idea of the filtering method is presented. Algorithm 1 is used to process the initial data, and the wall point cloud and noise 1 are obtained. Noise 1 is composed of the ground point cloud and noise. Then, Algorithm 2 is used to process noise 1, and the ground point cloud and noise are separated. Finally, the wall and the ground are joined together.</p> "> Figure 2
<p>The filtering method based on grid principal component analysis (GPCA) is presented. The principal component analysis (PCA) algorithm is used to reduce the dimension of the initial data. A grid is constructed for the dimensionality reduction data. The number of points in the grid is counted. The data are divided into two parts by setting the threshold <math display="inline"><semantics> <mrow> <msub> <mi>k</mi> <mi>σ</mi> </msub> </mrow> </semantics></math>.</p> "> Figure 3
<p>The classification results were corrected by K nearest neighbor (KNN). Each of these categories is represented by a different color. The radius is set as the starting point <math display="inline"><semantics> <mi>A</mi> </semantics></math>, and a circle is drawn, as shown in Process 1. The categories within the statistical circle have the most dots in red. Therefore, the category <math display="inline"><semantics> <mi>A</mi> </semantics></math> stays the same. In Process 2, it is found that the circle centered on <math display="inline"><semantics> <mi>B</mi> </semantics></math> has more red dots; therefore, <math display="inline"><semantics> <mi>B</mi> </semantics></math> is updated to red. In Process 3, <math display="inline"><semantics> <mi>C</mi> </semantics></math> is updated to redpoint in the same manner. When each point is updated, points in the same plane are updated to the same class, as shown in Process n.</p> "> Figure 4
<p>Filtering based on the normals K nearest neighbor (NKNN) is presented. The data obtained consists of ground and noise in the previous step. A KD-tree is built for the data. KD-tree is used to search for the KNN. Then, the PCA algorithm is used to quickly solve the normal vector. The data are classified by setting the threshold <math display="inline"><semantics> <mi>δ</mi> </semantics></math> of the angle between the normal vectors. Then, the KNN algorithm is used for further optimization. Of all the categories, the category with the most points is the ground point cloud, and the others are noise.</p> "> Figure 5
<p>The experimental subject was a neighborhood. The red line is the path of movement when we measured the data. The <span class="html-italic">A</span> was the starting point from which we started the measurement, and the <span class="html-italic">B</span> was the endpoint.</p> "> Figure 6
<p>Backpack system and collected point cloud data (PCD): (<b>a</b>) the equipment we used to measure the data consists of a lidar, an inertial measurement unit (IMU), a wireless module, and a host. (<b>b</b>) After collection and scan registration, we obtained the three-dimensional data.</p> "> Figure 7
<p>The process of the GPCA algorithm: (<b>a</b>) the initial 3D data are mapped to a 2D plane using the PCA algorithm and (<b>b</b>) the GPCA algorithm is used to filter the noise of the wall two-dimensional points. The features of the walls are well-preserved.</p> "> Figure 8
<p>Segmentation and splicing of ground point clouds: (<b>a</b>) the two-dimensional wall is restored to three-dimensional point cloud data. (<b>b</b>) Other point clouds beside the wall: these point clouds are made up of ground and noise. (<b>c</b>) The data in (<b>b</b>) are roughly segmented by using the included angle of the normal vector. Point clouds on the ground are mostly grouped into the same category (the same color). However, many misclassified points still exist. (<b>d</b>) The classification results of the previous step are further segmented by the KNN principle, and the complete plane point cloud is obtained. (<b>e</b>) The ground and wall point clouds are joined together.</p> "> Figure 9
<p>The results of several filtering processes, where the main noise is marked within the red shape: (<b>a</b>) the initial data collected; (<b>b</b>) the data processed by artificial filtering on the initial data; (<b>c</b>) the data processed by the statistical outlier removal (SOR) filter; (<b>d</b>) the data processed by the SOR filter on the basis of voxel grid filter processing (the voxel grid statistical outlier removal (VGSOR) filter); (<b>e</b>) the data processed by the radius outlier removal (ROR) filter; (<b>f</b>) the data processed by the Gaussian filter; (<b>g</b>) the data processed by the difference of normals (DON) method; and (<b>h</b>) the data processed by the GPCA method.</p> "> Figure 9 Cont.
<p>The results of several filtering processes, where the main noise is marked within the red shape: (<b>a</b>) the initial data collected; (<b>b</b>) the data processed by artificial filtering on the initial data; (<b>c</b>) the data processed by the statistical outlier removal (SOR) filter; (<b>d</b>) the data processed by the SOR filter on the basis of voxel grid filter processing (the voxel grid statistical outlier removal (VGSOR) filter); (<b>e</b>) the data processed by the radius outlier removal (ROR) filter; (<b>f</b>) the data processed by the Gaussian filter; (<b>g</b>) the data processed by the difference of normals (DON) method; and (<b>h</b>) the data processed by the GPCA method.</p> "> Figure 10
<p>A statistical graph of the average distance of KNN: this average distance is used to evaluate the degree of data dispersion. We calculated three evaluation parameters for the initial and several filtered data. The standard deviation is expressed as <math display="inline"><semantics> <mi>σ</mi> </semantics></math>. The mean variation is expressed as <math display="inline"><semantics> <mrow> <msub> <mi>σ</mi> <mover accent="true"> <mi>x</mi> <mo>¯</mo> </mover> </msub> </mrow> </semantics></math>. The range is expressed as <math display="inline"><semantics> <mi>R</mi> </semantics></math>. (<b>a</b>) A statistical graph of the raw data, (<b>b</b>) a statistical graph of the data filtered by the artificial filter, (<b>c</b>) a statistical graph of the data filtered by the SOR filter, (<b>d</b>) a statistical graph of the data filtered by the VGSOR filter, (<b>e</b>) a statistical graph of the data filtered by the ROR filter, (<b>f</b>) a statistical graph of the data filtered by the Gaussian filter, (<b>g</b>) a statistical graph of the data filtered by the DON filter, and (<b>h</b>) a statistical graph of the data filtered by the GPCA method are presented.</p> "> Figure 10 Cont.
<p>A statistical graph of the average distance of KNN: this average distance is used to evaluate the degree of data dispersion. We calculated three evaluation parameters for the initial and several filtered data. The standard deviation is expressed as <math display="inline"><semantics> <mi>σ</mi> </semantics></math>. The mean variation is expressed as <math display="inline"><semantics> <mrow> <msub> <mi>σ</mi> <mover accent="true"> <mi>x</mi> <mo>¯</mo> </mover> </msub> </mrow> </semantics></math>. The range is expressed as <math display="inline"><semantics> <mi>R</mi> </semantics></math>. (<b>a</b>) A statistical graph of the raw data, (<b>b</b>) a statistical graph of the data filtered by the artificial filter, (<b>c</b>) a statistical graph of the data filtered by the SOR filter, (<b>d</b>) a statistical graph of the data filtered by the VGSOR filter, (<b>e</b>) a statistical graph of the data filtered by the ROR filter, (<b>f</b>) a statistical graph of the data filtered by the Gaussian filter, (<b>g</b>) a statistical graph of the data filtered by the DON filter, and (<b>h</b>) a statistical graph of the data filtered by the GPCA method are presented.</p> "> Figure 11
<p>Cumulative distribution function (CDF) of several filters: if <math display="inline"><semantics> <mrow> <mi>F</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> is represented as a CDF, then <math display="inline"><semantics> <mrow> <mi>F</mi> <mo stretchy="false">(</mo> <mi>a</mi> <mo stretchy="false">)</mo> </mrow> </semantics></math> is the proportion of points for which the average distance is less than <math display="inline"><semantics> <mi>a</mi> </semantics></math>. The faster the value of cumulative probability increases, the higher the concentration of data. Therefore, it can be used as an indicator to judge the degree of data dispersion.</p> ">
Abstract
:1. Introduction
2. Methods
2.1. Filtering Based on GPCA
Algorithm 1. GPCA outliers removed |
Input: |
Output: |
1: |
2: |
3: for do |
4: |
5: end for |
6: |
7: |
8: |
9: |
10: |
11: |
12: |
13: |
14: for do |
15: |
16: |
17: |
18: end for |
19: for do |
20: |
21: if then |
22: |
23: else |
24: |
25: end if |
26: end for |
27: |
2.2. Filtering Based on NKNN
Algorithm 2. Filtering based on NKNN |
Input: |
Output: |
1: |
2: for do |
3: |
4: |
5: end for |
6: for do |
7: |
8: |
9: |
10: |
11: |
12: end for |
13: for do |
14: for do |
15: |
16: if then |
17: |
18: |
19: end if |
20: end for |
21: if then |
22: |
23: end if |
24: end for |
25: for do |
26: |
27: |
28: end for |
29: if then |
30: |
31: else |
32: |
33: end if |
3. Experimental Process and Results
3.1. Hardware and Operating System
3.2. Our Experiment Results in a One-by-One Step
3.3. Comparison with Other Methods
4. Discussion
5. Conclusions
Author Contributions
Funding
Institutional Review Board Statement
Informed Consent Statement
Data Availability Statement
Conflicts of Interest
References
- Lin, X.; Wang, F.; Yang, B.; Zhang, W. Autonomous Vehicle Localization with Prior Visual Point Cloud Map Constraints in GNSS-Challenged Environments. Remote Sens. 2021, 13, 506. [Google Scholar] [CrossRef]
- Wang, Z.; Yu, B.; Chen, J.; Liu, C.; Zhan, K.; Sui, X.; Xue, Y.; Li, J. Research on Lidar Point Cloud Segmentation and Collision Detection Algorithm. In Proceedings of the 2019 6th International Conference on Information Science and Control Engineering (ICISCE), Shanghai, China, 20–22 December 2019; pp. 475–479. [Google Scholar]
- Deyu, Y.; Zhang, Q.; Liu, J.; Liang, X.; Wang, Y.; Chen, S.; Maanpää, J.; Hyyppä, J.; Chen, R. Interest Point Detection from Multi-Beam Light Detection and Ranging Point Cloud Using Unsupervised Convolu-tional Neural Network. IET Image Process. 2020, 15, 369–377. [Google Scholar]
- Petr, K.; Fogl, M.; Barták, V.; Gdulová, K.; Urban, R.; Moudrý, V. Sensitivity Analysis of Parameters and Contrasting Performance of Ground Filtering Algorithms with Uav Photogrammetry-Based and Lidar Point Clouds. Int. J. Digit. Earth 2020, 13, 1672–1694. [Google Scholar]
- Sarakinou, I.; Papadimitriou, K.; Georgoula, O.; Patias, P. Underwater 3d Modeling: Image Enhancement and Point Cloud Filtering. In Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 2016, Prague, Czech Republic, 12–19 July 2016; pp. 441–447. [Google Scholar]
- Jie, C. Practice of airborne LiDAR point cloud filtering method based on triangulated irregular network. In Proceedings of the 2014 IEEE Workshop on Advanced Research and Technology in Industry Applications (WARTIA), Ottawa, ON, Canada, 29–30 September 2014; pp. 1284–1286. [Google Scholar]
- Yilmaz, C.S.; Konakoglu, B.; Serifoglu, C.; Gungor, O.; Gökalp, E. Image classification-based ground filtering of point clouds extracted from UAV-based aerial photos. Geocarto Int. 2016, 33, 310–320. [Google Scholar] [CrossRef]
- Yu, C.; Ji, F.; Xue, J. Cutting Plane Based Cylinder Fitting Method With Incomplete Point Cloud Data for Digital Fringe Projection. IEEE Access 2020, 8, 149385–149401. [Google Scholar] [CrossRef]
- Jagodnik, P.; Gazibara, S.B.; Arbanas, Ž.; Arbanas, S.M. Engineering geological mapping using airborne LiDAR datasets—An example from the Vinodol Valley, Croatia. J. Maps 2020, 16, 855–866. [Google Scholar] [CrossRef]
- Grebby, S.; Cunningham, D.; Naden, J.; Tansey, K. Lithological mapping of the Troodos ophiolite, Cyprus, using airborne LiDAR topographic data. Remote Sens. Environ. 2010, 114, 713–724. [Google Scholar] [CrossRef] [Green Version]
- Xue, F.; Lu, W.; Chen, Z.; Webster, C.J. From LiDAR point cloud towards digital twin city: Clustering city objects based on Gestalt principles. Isprs J. Photogramm. Remote Sens. 2020, 167, 418–431. [Google Scholar] [CrossRef]
- Huletski, A.; Kartashov, D.; Krinkin, K. Evaluation of the modern visual SLAM methods. In Proceedings of the 2015 Artificial Intelligence and Natural Language and Information Extraction, Social Media and Web Search FRUCT Conference (AINL-ISMW FRUCT), St. Petersburg, Russia, 9–14 November 2015; pp. 19–25. [Google Scholar]
- Savaria, D.T.; Balasubramanian, R. V-SLAM: Vision-based simultaneous localization and map building for an auton-omous mobile robot. In Proceedings of the 2010 IEEE Conference on Multisensor Fusion and Integration, Salt Lake City, UT, USA, 5–7 September 2010. [Google Scholar]
- Barneto, C.B.; Rastorgueva-Foi, E.; Keskin, M.F.; Riihonen, T.; Turunen, M.; Talvitie, J.; Wymeersch, H.; Valkama, M. Radio-based Sensing and Environment Mapping in Millimeter-Wave 5G and Beyond Networks. arXiv 2021, arXiv:2102.11593. [Google Scholar]
- Guidi, F.; Guerra, A.; Dardari, D. Personal Mobile Radars with Millimeter-Wave Massive Arrays for Indoor Mapping. IEEE Trans. Mob. Comput. 2015, 15, 1471–1484. [Google Scholar] [CrossRef]
- Cadena, C.; Carlone, L.; Carrillo, H.; Latif, Y.; Scaramuzza, D.; Neira, J.; Reid, I.D.; Leonard, J.J. Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age. IEEE Trans. Robot. 2016, 32, 1309–1332. [Google Scholar] [CrossRef] [Green Version]
- Checchin, P.; Gérossier, F.; Blanc, C.; Chapuis, R.; Trassoudaine, L. Radar Scan Matching Slam Using the Fourier-Mellin Transform. Field Serv. Robot. 2010, 62, 151–161. [Google Scholar]
- Guerra, A.; Guidi, F.; DallrAra, J.; Dardari, D. Occupancy Grid Mapping for Personal Radar Applications. In Proceedings of the 2018 IEEE Statistical Signal Processing Workshop (SSP), Freiburg im Breisgau, Germany, 10–13 June 2018; pp. 766–770. [Google Scholar]
- Geiger, B. Three-Dimensional Modeling of Human Organs and Its Application to Diagnosis and Surgical Planning. 1993. Available online: https://hal.inria.fr/inria-00074567/ (accessed on 10 March 2021).
- Hu, C.; Pan, Z.; Li, P. A 3D Point Cloud Filtering Method for Leaves Based on Manifold Distance and Normal Estimation. Remote Sens. 2019, 11, 198. [Google Scholar] [CrossRef] [Green Version]
- Han, X.-F.; Jin, J.S.; Wang, M.-J.; Jiang, W.; Gao, L.; Xiao, L. A review of algorithms for filtering the 3D point cloud. Signal Process. Image Commun. 2017, 57, 103–112. [Google Scholar] [CrossRef]
- Tian, X.G.; Xu, L.J.; Li, X.L.; Xu, T.; Yao, J.N. Filtering of Airborne Lidar Point Cloud with a Method Based on Kernel Density Estimation (Kde). Lasers Eng. 2016, 34, 221–237. [Google Scholar]
- Han, X.-F.; Jin, J.S.; Wang, M.-J.; Jiang, W. Guided 3D point cloud filtering. Multimed. Tools Appl. 2017, 77, 17397–17411. [Google Scholar] [CrossRef]
- Li, Y.; Wang, J.; Li, B.; Sun, W.; Li, Y. An adaptive filtering algorithm of multilevel resolution point cloud. Surv. Rev. 2020, 1–12. [Google Scholar] [CrossRef]
- Hosseini, S.A.; Arefi, H.; Gharib, Z. Filtering of lidar point cloud using a strip based algorithm in residential mountainous areas. In Proceedings of the The 1st ISPRS International Conference on Geospatial Information Research, Tehran, Iran, 15–17 November 2014; pp. 157–162. [Google Scholar]
- Zhu, N.; Jiaa, Y.; Luo, L. Tunnel Point Cloud Filtering Method Based on Elliptic Cylindrical Model. In Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XLI-B1, Prague, Czech Republic, 12–19 July 2016; pp. 735–740. [Google Scholar]
- He, Y.; Zhang, C.; Fraser, C.S. Progressive Filtering of Airborne LiDAR Point Clouds Using Graph Cuts. IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens. 2018, 11, 2933–2944. [Google Scholar] [CrossRef]
- Feichter, S.; Hlavacs, H. Planar Simplification of Indoor Point-Cloud Environments. In Proceedings of the 2018 IEEE International Conference on Artificial Intelligence and Virtual Reality (AIVR), Taichung, Taiwan, 10–12 December 2018; pp. 274–281. [Google Scholar]
- Liu, K.; Wang, W.; Tharmarasa, R.; Wang, J.; Zuo, Y. Ground Surface Filtering of 3D Point Clouds Based on Hybrid Regression Technique. IEEE Access 2019, 7, 23270–23284. [Google Scholar] [CrossRef]
- Quan, Y.; Song, J.; Guo, X.; Miao, Q.; Yang, Y. Filtering LiDAR data based on adjacent triangle of triangulated irregular network. Multimed. Tools Appl. 2016, 76, 11051–11063. [Google Scholar] [CrossRef]
- Leal, E.; Sanchez-Torres, G.; Branch, J.W. Sparse Regularization-Based Approach for Point Cloud Denoising and Sharp Features Enhancement. Sensors 2020, 20, 3206. [Google Scholar] [CrossRef] [PubMed]
- Jia, C.C.; Wang, C.J.; Yang, T.; Fan, B.H.; He, F.G. A 3D Point Cloud Filtering Algorithm based on Surface Variation Factor Classification. Procedia Comput. Sci. 2019, 154, 54–61. [Google Scholar] [CrossRef]
- Xu, Y.; Yue, D.J. A Spatial Clustering Filtering Method for Airborne Lidar Point Cloud Based on Dual Distance. Lasers Eng. 2016, 34, 167–181. [Google Scholar]
- Zou, B.; Qiu, H.; Lu, Y. Point Cloud Reduction and Denoising Based on Optimized Downsampling and Bilateral Filtering. IEEE Access 2020, 8, 136316–136326. [Google Scholar] [CrossRef]
- Zhang, D.; Lu, X.; Qin, H.; He, Y. Pointfilter: Point Cloud Filtering via Encoder-Decoder Modeling. IEEE Trans. Vis. Comput. Graph. 2021, 27, 2015–2027. [Google Scholar] [CrossRef]
- Wang, D.; Huang, C.; Wang, Y.; Deng, Y.; Li, H. A 3D Multiobject Tracking Algorithm of Point Cloud Based on Deep Learning. Math. Probl. Eng. 2020, 2020, 1–10. [Google Scholar] [CrossRef]
- Hui, Z.; Hu, Y.; Yevenyo, Y.Z.; Yu, X. An Improved Morphological Algorithm for Filtering Airborne LiDAR Point Cloud Based on Multi-Level Kriging Interpolation. Remote Sens. 2016, 8, 35. [Google Scholar] [CrossRef] [Green Version]
- Yerokhin, A.; Semenets, V.; Nechyporenko, A.; Turuta, O.; Babii, A. F-transform 3D Point Cloud Filtering Algorithm. In Proceedings of the 2018 IEEE Second International Conference on Data Stream Mining & Processing (DSMP), Lviv, Ukraine, 21–25 August 2018; pp. 524–527. [Google Scholar]
- Kanatani, T.; Kume, H.; Taketomi, T.; Sato, T.; Yokoya, N.; Sato, T.; Yokoya, N. Detection of 3D points on moving objects from point cloud data for 3D modeling of outdoor environments. In Proceedings of the 2013 IEEE International Conference on Image Processing, Melbourne, VIC, Australia, 15–18 September 2013; pp. 2163–2167. [Google Scholar]
- Casin, P. A generalization of principal component analysis to K sets of variables. Comput. Stat. Data Anal. 2001, 35, 417–428. [Google Scholar] [CrossRef]
- Hu, L.; Nooshabadi, S.; Ahmadi, M.; Linjia, H. Massively parallel KD-tree construction and nearest neighbor search algorithms. In Proceedings of the 2015 IEEE International Symposium on Circuits and Systems (ISCAS), Lisbon, Portugal, 24–27 May 2015; pp. 2752–2755. [Google Scholar] [CrossRef]
- Carrilho, A.C.; Galo, M.; Santos, R.C. Statistical outlier detection method for airborne LiDAR data. In Proceedings of the ISPRS—International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences; Copernicus GmbH: Göttingen, Germany, 2018; Volume XLII-1, pp. 87–92. [Google Scholar]
- Jiang, J.J.; Wang, X.Q.; Duan, F.J. An Effective Frequency-Spatial Filter Method to Restrain the Interferences for Active Sensors Gain and Phase Errors Calibration. IEEE Sens. J. 2016, 16, 7713–7719. [Google Scholar]
- Ito, K.; Xiong, K.Q. Gaussian Filters for Nonlinear Filtering Problems. IEEE Trans. Automat. Contr. 2000, 45, 910–927. [Google Scholar] [CrossRef] [Green Version]
- Ioannou, Y.; Taati, B.; Harrap, R.; Greenspan, M. Difference of Normals as a Multi-scale Operator in Unorganized Point Clouds. In Proceedings of the 2012 Second International Conference on 3D Imaging, Modeling, Processing, Visualization & Transmission, Zurich, Switzerland, 13–15 October 2012. [Google Scholar]
- Balsa-Barreiro, J. Airborne light detection and ranging (LiDAR) point density analysis. Sci. Res. Essays 2012, 7, 3010–3019. [Google Scholar] [CrossRef]
- Balsa-Barreiro, J.; José, L.L. Empirical Study of Variation in Lidar Point Density over Different Land Covers. Int. J. Remote Sens. 2014, 35, 3372–3383. [Google Scholar] [CrossRef]
Filter | Noise Elimination Rate | Time Complexity | |||
---|---|---|---|---|---|
SOR filter | 53.81% | 0.0592 | 0.0472 | 0.4868 | |
VGSOR filter | 87.33% | 0.0848 | 0.0656 | 0.8276 | |
ROR filter | 49.31% | 0.0759 | 0.0553 | 0.6862 | |
Gaussian filter | 36.25% | 0.1005 | 0.0772 | 0.7860 | |
DON filter | 80.97% | 0.1726 | 0.1192 | 1.3672 | |
GPCA method | 98.03% | 0.0674 | 0.0523 | 0.5790 |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Cheng, D.; Zhao, D.; Zhang, J.; Wei, C.; Tian, D. PCA-Based Denoising Algorithm for Outdoor Lidar Point Cloud Data. Sensors 2021, 21, 3703. https://doi.org/10.3390/s21113703
Cheng D, Zhao D, Zhang J, Wei C, Tian D. PCA-Based Denoising Algorithm for Outdoor Lidar Point Cloud Data. Sensors. 2021; 21(11):3703. https://doi.org/10.3390/s21113703
Chicago/Turabian StyleCheng, Dongyang, Dangjun Zhao, Junchao Zhang, Caisheng Wei, and Di Tian. 2021. "PCA-Based Denoising Algorithm for Outdoor Lidar Point Cloud Data" Sensors 21, no. 11: 3703. https://doi.org/10.3390/s21113703