Congratulation from Internet Conference!
Hello
ADAPTIVE POINT CLOUD FILTERING METHOD FOR SELF-DRIVING VEHICLES
09.12.2022 14:55
[1. Information systems and technologies]
Author: Illia Mushta, graduate student at the Department of Electronic Computational Equipment Design, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine
Abstract
Measurements obtained from LiDAR sensor always contain noise detections. The origin of this noise is different. Most LiDAR systems suffer degradation from adverse environment conditions. The photodetector of the lidar system detects transient light from the sun and the surroundings, and this light produces noise that hinders the system's effectiveness. Also adverse weather conditions, such as snow, dust, heavy rain or fog, distort the point cloud image obtained by LiDAR sensor. So to obtain high quality LiDAR point cloud filtering methods are used. Traditional filtering algorithms are often limited to isolated outliers, cannot identify outlier groupings or, otherwise, remove a lot of useful environmental features and mostly are adopted to single type of outliers. What`s more, some of them are too complex to have ideal real-time performance. To adress these problems, this paper proposes new adaptive LiDAR point cloud filtering method that is based on segmentation, voxelization, dynamic statistical outlier removal algorithm, DBSCAN clustering and OPTICS-OF algorithm. Using voxelization time complexity of the algorithm is significantly reduced. While using DBSCAN algorithm clusters of outliers are detected. Initial segmentation of point cloud is used to consider spatial concentration of noise points. With the use of dynamic statistical outlier removal algorithm noise points that are close to the sensor and emerge because of adverse weather conditions are removed. OPTICS-OF algorithm is used for basic filtering.
Formulation of the proposed method
There is no need to find outliers in dense regions of point cloud, which correspond to objects. Removing point cloud regions with high density helps to reduce the amount of points that is used for outliers search. To find such dense regions initial point cloud is divided into voxels of defined size. If the number of points in a particular voxel is higher than the mean number of points in input point cloud, then the voxel is rejected from the further computation. This process is described in [1]. If point cloud contains noise points that emerge because of adverse weather conditions, they are gathered close to the sensor (up to 20m) and have high density. So in such case voxels that lie in this region are not removed from computation – corresponding points are processed separately using density statistical outlier removal filter [2]. Remaining points are filtered in the futher steps using other approaches. Density statistical outlier removal filter computes mean and standard deviation of the mean distances from points to their k-nearest neighbours. Based on the mean, standard deviation and distance from the point to the sensor dynamic threshold is computed. If the mean k-nearest-neighbours-distance of the point is greater than computed dynamic threshold, then the point is considered as outlier. This algorithm fits the best for removing dense noise point clusters that emerge because of adverse weather conditions. To identify if there are dense adverse weather-caused outliers in point cloud, average density of the voxels from the nearest to the sensor region (up to 20m) is compared to overall non-empty voxels density. If these densities differs much (more than 15-18 times) there are dense adverse weather-caused outliers.
After dense regions exclusion and adverse weather-caused outliers removal (if needed), remaining points are divided into cylindrical segments depending on the distance to the sensor. This segmentation is described in [3]. Each segment is then processed separately.
To filter obtained point clouds for every segment it is useful to apply some kind of clustering, which is machine learning technique. Clustering is used for detection dense groups of outliers. Let`s consider DBSCAN algorithm for this purpose. The pseudocode of this algorithm is depicted in the figure 1 [4].
Figure 1: pseudocode of DBSCAN algorithm
This algorithm find single outliers and divide point cloud into a set of clusters. If the density of a particular cluster is less than defined value – this cluster is considered as cluster of outliers [3]. RangeQuery method from the pseudocode is used to find neighbours of the point in a given radius. To find nearest neighbours of the point it is usefull to use KD-tree data structure [5]. So before clustering points of the given segment are organized into KD-tree data structure. This data structure gives the ability to find the neighbours of all points with the complexity .
Let`s consider the OPTICS-OF algorithm [6] as basic algorithm for outliers filtering , which is a modification of OPTICS. The time complexity of this method in the simpliest case is . To make it applicable to the task of point cloud filtering for self-driving vehicles let`s use outlier detection method based on k-nearest neighbors-local outlier factor, which was proposed by He Xu, Lin Zhang, Peng Li and Feng Zhu for data filtering [7].
So, builded KD-tree is also used here. OPTICS-OF algorithms firstly computes k-nearest neighbors (1) for every point along with core-distance (2).
In mathematical notation, if n is a number of points in the given segment:
For every point y from Y3xn find:
Here kdist(y) of y is the distance d(y,о) between y and an object o ϵ Y3xn such that at least for k objects o' ϵ Y3xn it holds that d(y,о') < = d(y,о), and for at most k-1 objects o' ϵ Y3xn it holds that d(y,о') < d(y,о) [7]. The set (1) is called k-nearest neighbors of y.
An object y whose e neighborhood contains at least MinPts objects is said to be a core object. The core-distance (2) of object y is the smallest distance e‘< =e such that y is a core object with respect to e‘ and MinPts if such an e‘ exists, i.e. if there are at least MinPts objects within the e neighborhood of y. Otherwise, the core-distance is UNDEFINED [6].
In the second pass along the data for every y from Y2xn we calculate reachability distance (3) reschdistµ, MinPts (y,о) with respect to its neighboring objects o ϵ NMinPts(y) and local reachability distance (4) lrdMinPts(y) of y [6].
In the last pass along the data outlier factor for every point y from Y3xn is calculated (5) [6].
To make noise filtering, a threshold OF value should be chosen. There is an illustration of dependency between the density of the neighbors for each point and its OF value in the article [6]. This is shown in figure 2. In figure 2 large OF values correspond to the points with small neighbors density and vice-versa. In the article [3] it was shown that in areas that are close to the sensor, points have high density and vice-versa. So the threshold OF value should be adjusted to the distance from the sensor to each point. This adjustment is done experimentally. Global parameters for DBSCAN algorithm for every segment are chosen experimentally.
Figure 2: depenency between the density of the neighbours for each point and it`s OF value
Evaluation and Results
The proposed algorithm was tested on the datasets [9] and [10]. The first dataset [9] was manually labeled as it doesn`t support outlier filtering task. The second dataset contains labels only for weather-caused outliers. For the first dataset F1 score for ROR filter is 55.12% (time 6s), for SOR filter is 48.84% (time 0.12s), for proposed filter is 56% (time 0.32s without kd-tree step). For the second algorithm F1 score for ROR algorithm is 2.8% (recall 1.6%), for SOR algorithm is 4.7% (recall 2.7%), for proposed algorithm is 34.46% (recall 93.7%). Here recall is more representative as it relates only to labeled data.
Figure 3: a) original labeled point cloud, b) point cloud after filtering
Figure 4: a) point cloud after ROR filter applying b) point cloud after SOR filter applying
Figure 5: point cloud after proposed method applying
Conclusions
Point cloud filtering is a key step in building Advanced Driving Systems (ADS) and Advanced Driver Assistance Systems (ADAS) using LiDAR technologies. Adaptive LiDAR Point Cloud Filtering Method for self-driving vehicles is proposed in this article. Low-complexity of this method is achieved by using voxelization and KD-tree data structure. Compared with the traditional filtering algorithms, the proposed method reduce the overall time complexity, preserve more environmental features while filtering noise points and is applicable for adverse weather-caused outliers removing.
Literature
[1] Fast Statistical Outlier Removal Based Method for Large 3D Point Clouds of Outdoor Environments Balta H., Velagic J., Bosschaerts W., De Cubber G., Siciliano B. (2018) IFAC-PapersOnLine, 51 (22) , pp. 348-353.
[2] A. Kurup and J. Bos, Dsor: A scalable statistical filter for removing falling snow from lidar point clouds in severe winter weather, 2021
[3] Y. Duan, C. Yang, H. Chen, W. Yan, H. Li Low-complexity point cloud denoising for LiDAR by PCA-based dimension reduction Opt. Cmmun., 482 (2021), Article 126567.
[4] https://en.wikipedia.org/wiki/DBSCAN
[5] https://en.wikipedia.org/wiki/K-d_tree
[6] Breunig MM, Kriegel H-P, Ng RT, Sander J (1999) Optics-of:Identifying local outliers. In: European conference on principlesof data mining and knowledge discovery, pp. 262–270. Springer,Berlin.
[7] He Xu, Lin Zhang, Peng Li, and Feng Zhu. 2022. Outlier detection algorithm based on k-nearest neighbors-local outlier factor. Journal of Algorithms & Computational Technology 16 (2022), 17483026221078111
[8] Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (May 2011). "Density-based clustering". Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 1 (3): 231–240.
[9] @ARTICLE{Geiger2013IJRR, author = {Andreas Geiger and Philip Lenz and Christoph Stiller and Raquel Urtasun}, title = {Vision meets Robotics: The KITTI Dataset}, journal = {International Journal of Robotics Research (IJRR)}, year = {2013}}
[10] Kurup, A., & Bos, J. (2021). The Winter Adverse Driving dataSet (WADS). Retrieved from: https://digitalcommons.mtu.edu/wads/
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter
Another articles in this section
-
ЗАСТОСУВАННЯ СУЧАСНИХ АЛГОРИТМІВ ДИНАМІЧНОГО ПОШУКУ В СКЛАДНИХ ІНФОРМАЦІЙНИХ СИСТЕМАХ
29.11.2022 03:05 -
СИСТЕМА ДОМАШНЬОГО АВТОМАТИЗУВАННЯ
29.11.2022 02:54 -
ТЕХНОЛОГІЇ «E-LEARNING» В СУЧАСНІЙ ОСВІТІ
29.11.2022 02:47 -
ВИМОГИ СТВОРЕННЯ SMART КУРСУ ЗМІШАНОГО НАВЧАННЯ
11.12.2022 00:24 -
МЕТОД ВИКОРИСТАННЯ ШАБЛОНУ КУРСУ ЗМІШАНОГО НАВЧАННЯ
11.12.2022 00:16
Сonferences
Conference 2024
Conference 2023
Conference 2022
Conference 2021
