High-definition 3D map for autonomous vehicles in Vietnam: A comparison between graph simultaneous localization and mapping and the normal distributions transform algorithm

Abstract

Autonomous vehicles have a fundamental part to play in future transportation. In order to work, such vehicles need a way of determining their exact location. To date, two techniques have proved applicable: geolocation using GPS and 3D mapping. In the latter case, the creation of the 3D map is an essential step in preparing the software. This manuscript presents a novel method for creating a high-definition 3D map using a Velodyne sensor. The primary objective is to achieve deeper understanding of the map creation algorithm and to lay the groundwork for future autonomous vehicle architecture. In this manuscript, two high-definition mapping algorithms are applied: the graph simultaneous localization and mapping algorithm and the normal distributions transform algorithm. The results of both displayed different strengths and weaknesses upon creating a high-definition 3D map, which may help other researchers to select the best algorithm in future.

Keywords

HD map autonomous vehicle Velodyne sensor

Introduction

In recent years, the autonomous vehicle (AV) industry has advanced by leaps and bounds. The Society of Automotive Engineers¹ classifies AVs into six levels: from 0 (which means no automation) up to 5 (which means full automation and driverless operation). Most AVs on the global market today are level 2 or level 3, or semi-autonomous. Some could be as high as level 4, but these are only for R&D purposes,^2

–6 rather than for commercial or consumer use. Increasingly, the AV is becoming a focus for leading companies and researchers, and a comprehensive and interdisciplinary research effort.^6,7 According to Peng et al.,⁸ commercial automated cars should be available on the market within the next few years, as AV technology matures – for example, technology designed for perception, localization and mapping, trajectory planning, decision-making, and drive-by-wire. Therefore, a data map for navigation purposes needs to be ready for the market soon.⁹

There are two main techniques for AV navigation: simultaneous localization and mapping (SLAM) and high-definition (HD) mapping.¹⁰ With SLAM, perception and localization are conducted in real time, requiring powerful algorithms for a reliable result. Moreover, its performance depends heavily on sensor performance, which could impact the AV’s object detection. Therefore, SLAM-based techniques are more suitable for AV applications that involve navigating in an unknown environment.¹¹ By contrast, HD mapping methods provide a detailed map of the surrounding environment to assist the AV in its perception. With this approach, it is much simpler to identify objects, since their information is already available in the database. Therefore, less high-end sensors could be used for navigation purposes.¹² This method is suitable for applications in which the working environment of the AV does not frequently change (e.g. in inner-city areas or expressways). However, if there is any significant change in the surrounding environments, some unexpected issues could arise in the navigation performance. Currently, the main drawbacks of the approach are the availability of a map database, the large amount of memory required to store the map, the system’s computational load requirement, and latency in transmitting data for processing.¹³

In the existing body of literature, there are two main methods for point-cloud matching during scanning to create 3D maps. The first is the iterative closest point (ICP) method.¹⁴ This is an algorithm employed to reconstruct 3D surfaces from multiple scans, to localize the AV and achieve optimal trajectory planning by minimizing the difference between two point clouds and matching them as closely as possible. This is a well-known, robust, reliable, and simple method but requires a great deal of computational power and a significant run time in real-time applications. It is also rather sensitive to rotational movement during the data collection process.^7,15

The second approach, normal distributions transform (NDT),¹⁶ transforms a reference point cloud into fixed 2D cells and converts them to a set of Gaussian probability distributions, before matching the scan data to the set of normal distributions. NDT makes matches faster than does ICP, since it does not require point-to-point registration. This algorithm is particularly suitable for trajectory planning or change and loop detection. However, it is sensitive to the accuracy of the initial estimate and uncertainty caused by moving objects.^9,17

HD mapping for AVs is not a new technology in the world, but in Vietnam, no HD map database or HD mapping companies yet exist. The application of 3D light detection and ranging (LIDAR) to construct point clouds is limited. There are only a handful of companies and groups that use photogrammetry to capture 3D point clouds, mainly for the purposes of geology and architecture conservation. In order to make AVs a reality in Vietnam in the near future, it is necessary to develop both an HD map database and tools to create HD maps. Therefore, in this manuscript, we apply two algorithms using scan matching to create HD 3D maps to see how they perform in Vietnam. This may offer other researchers a deeper understanding of the robustness of each algorithm and simplify the choice of algorithm for creating HD 3D maps in future.

Mathematical algorithms

NDT algorithm

Biber¹⁶ introduced the NDT scan matching method, by using a point cloud and a uniform grid. In such a method, the initial large point cloud is divided into voxels (volume elements—cells). Each voxel stores points based on the mean and covariance (a Gaussian distribution type). That way, the discrete point clouds are transformed into successive continuous functions instead of analyzing large point clouds directly. The equations governing the NDT are shown below^16,18

p_{k} = \frac{1}{M_{k}} \sum_{i = 1}^{M_{k}} x_{k i}

\sum_{k} = \frac{1}{M_{k}} \sum_{i = 1}^{M_{k}} (x_{k i} - p_{k}) {(x_{k i} - p_{k})}^{T}

where $x_{i} = {(x_{i}, y_{i}, z_{i})}^{T}$ with i = 1:M. If R is the rotation matrix and t′ is the translation vector, the $x_{i}^{'}$ can be calculated by

x_{i}^{′} = R x_{i} + t^{'}

The pose translational and rotational parameters to estimate are

t = (t_{x}, t_{y}, t_{z}, t_{roll}, t_{pitch}, t_{yaw})

E (X, t) = \sum_{i}^{N} exp \frac{- {(x_{i}^{′} - p_{i})}^{T} \sum_{i}^{- 1} (x_{i}^{′} - p_{i})}{2}

where E(X, t) represents matched or well aligned voxels.

The literature offers various examples of successful applications of NDT. Stoyanov et al.¹⁹ evaluated three commonly used variations of NDT in relation to their accuracy in representing a sampled semi-structured environment. Choe et al.²⁰ classified urban structure based on NDT grids for practical robots. However, the standard NDT algorithm exhibits a number of drawbacks, including poor convergence. To improve upon it, Takeuchi et al.⁹ added dual resolutions to NDT to enhance the scan matching. Later, Das et al.²¹ enhanced the convergence of NDT by implementing a segmented greedy cluster to generate Gaussian clusters for the algorithm. Finally, Hong and Lee²² proposed a probabilistic-based NDT variation by employing the probabilities of point samples to represent the environment, where the point cloud is divided into high-resolution cells, which helps reduce pose estimation errors.

High-definition LIDAR algorithm

Koide et al.²³ developed high-definition LIDAR (HDL) graph SLAM with NDT scan matching-based odometry estimation and loop detection. It is worth noting that graph SLAM is one of the most widely implemented approaches to deal with SLAM problems. This technique constructs and optimizes a graph in which grid points exhibit landmark positions and sensor poses. Additionally, the edges of the grid represent relative poses between sensor poses and landmarks, which are commonly called constraints. By such a construction, the graph SLAM is optimized by minimizing the errors between the grid points and the constraints mentioned above. With the Velodyne point clouds, using filter and scan matching with floor detection, the HDL graph SLAM can create the map point. The main steps of the technique are described below (see also Figure 1):

– Step 1. Data scanning. The environment is scanned and Velodyne point clouds are stored.

– Step 2. Prefiltering. Because of the unsteady movement of AVs, the scan is polluted with a great deal of noise. Thus, the initial Velodyne point clouds include a significant number of irrelevant points. Consequently, prefiltering is employed to remove outliers, which improves the registration precision.

– Step 3. Odometry and floor detection. In this step, the two threads are conducted in parallel. The odometry is performed based on the calculated continuous transformation.

– Step 4. HDL graph SLAM. This step involves loop detection and optimizes a pose graph which takes various constraints into account to compensate the accumulated error of the scan matching.

– Step 5. Visualization and post-treatment. In the final step, all point clouds and other information after processing are visualized on Rviz.

Figure 1.

HDL algorithm proposed by Koide et al.²³

Data acquisition system and test area

Data acquisition system

For data logging, a low-cost system with only one 16-channel LIDAR sensor was used to collect point-cloud data. The LIDAR sensor has a measurement range up to 100 m with range accuracy of ±3 cm and a vertical field of view from +15° to −15°. The rotation rate can be adjusted from 5 to 20 Hz. ROS-based software was installed on a Nvidia TX2 embedded computer to collect the point-cloud data from the sensor to a ROSbag file. Both the sensor and computer were integrated into a portable backpack system (see Figure 2), which has its own battery and can run as a stand-alone logging system for up to 4 h. The LIDAR sensor was put on a monopod which can be held vertically by hand or mounted on the backpack top, while the embedded computer and battery were installed inside the backpack, which was referred to as the “3D scanning backpack.” The system can be remotely controlled by a tablet to start and stop the logging process. An engineer can carry out the logging by holding the sensor pod vertically and carrying the backpack while walking by himself or sitting on a running motorbike. Afterward, the data were processed by a high-performance desktop computer to recreate a 3D point-cloud map of the test area.

Figure 2.

Diagram and photo of the 3D mapping backpack.

Test area and strategy

In this study, the test area was a triangular area measuring 0.01 km², on the main campus of Phenikaa University, Vietnam. The 2D map of the campus is shown in Figure 3 including three points: A, B, and C. The test area includes a mixture of asphalt road with sidewalks, office buildings, and plants, which perfectly replicates a universal transportation infrastructure (see also Figure 4).

Figure 3.

2D map of test area.

Figure 4.

Landscape view of test area.

Three different testing strategies were planned to assess the two algorithms’ performance, as shown in Table 1. In the first strategy, a straight road from point A to B was scanned by the backpack from one side to the other, to test the generation of an open-loop 3D map by each method. In the second strategy, a closed-loop street in a counterclockwise direction of the campus from point A to B to C was completely scanned to test the ability of point-cloud loop-closing using only the LIDAR sensor data. In the third strategy, the closed loop was sampled in a clockwise direction for comparison purpose. The difference between the two closed-loop cases is how the first turn is made during the sampling period, which can be used to confirm the performance of two approaches without using inertial measurement units (IMUs). In strategy 2, a long straight road is sampled before making the first turn. However, in strategy 3, a turn is made much earlier, at the beginning of the test. In both cases, the ROSbag data of each test was processed by each method to create the 3D point cloud before comparison.

Table 1.

Testing strategies.

Strategy	Type	Direction
1	Open-loop	From point A to B
2	Closed-loop	Between points A, B, and C in a counterclockwise direction
3	Closed-loop	Between points A, B, and C in a clockwise direction

In this study, two distances on the street (d ₁ and d ₂) and one street corner (α) are considered, evaluating the performance of each 3D map generation method, as shown in Figure 3. The comparison was drawn between 2D maps generated by aerial imaging (5 cm/pixel resolution) and 3D maps made by HDL and NDT. The distance from the aerial image was measured by 2D map .tif file, while the distance in point-cloud files was determined by using Cloud Compare open-source software. α angles in both cases were measured by 2D images imported into ImageJ software.

Results

Open-loop result

The results for the first testing strategy are shown in Table 2. Using the same ROSbag, NDT was able to produce a cloud of 559,131 points, while HDL delivered a point cloud of 3,528,906 points (almost 6.3 times larger). Since there was no high-accuracy measurement of geographic coordination, there is only a comparison of relative distance between the aerial 2D photogrammetry data and the two point clouds. As shown in Table 2, the difference between a reference length measured from two point clouds and the 2D image is less than 2.14%, which equates to about 0.28 m in the case of NDT.

Table 2.

Result comparison in open loop test.

Parameter	2D aerial photogrammetry	HDL	NDT
Characteristics		Number of points: 3,528,906	Number of points: 559,131
Demonstration
Measurement	Distance: 13.08 m	Distance: 13.27 mDifference: 1.45%	Distance: 12.80 mDifference: 2.14%

HDL: high-definition LIDAR; NDT: normal distributions transform.Closed-loop result

In the test of the second strategy on the counterclockwise course, both HDL and NDT showed good performance in 3D point-cloud generation. Comparing with aerial photogrammetry image of the area as shown in Table 3, both methods exhibit good accuracy, since the differences are less than 5% in both cases. The point-cloud density in the case of HDL is also higher than that of NDT—the total number of points in the case of HDL is about 4,909,133, as compared to 1,150,355 points in NDT.

Table 3.

Accuracy of 3D maps in closed-loop 1 test.

Dimension	Aerial image	HDL	Difference (%)	NDT	Difference (%)
d ₁ (m)	101.16	101.33	0.16	102.10	0.93
d ₂ (m)	155.21	154.45	0.49	157.55	1.51
α (°)	25.01	24.16	3.43	24.12	3.57

HDL: high-definition LIDAR; NDT: normal distributions transform.

In the third strategy test, when the first turn is made early on, the NDT approach shows its superior ability in point-cloud loop-closing without using IMU assistance (see Table 4). In contrast, HDL failed to close the loop and there were error points at the loop joint, making the point cloud unusable. NDT showed the same performance as with the earlier counterclockwise route. Therefore, the total number of points in this case was 19,710,844, which is considerably higher than the 10,676,991 points captured by HDL. Since HDL could not close the loop to make a correct point cloud, only the point cloud generated by NDT was considered to check the accuracy. In fact, NDT also displayed good accuracy, as the difference with the aerial data is less than 4%.

Table 4.

3D point clouds generated by the two methods.

Test	(a( HDL	(b( NDT
Closed-loop test 1	Number of points: 4,909,133	Number of points: 1,150,355
Closed-loop test 1
Closed-loop test 2	Number of points: 10,676,991	Number of points: 19,710,844
Closed-loop test 2

HDL: high-definition LIDAR; NDT: normal distributions transform.

Table 5.

Accuracy of 3D maps in the closed-loop test.

Dimension	Aerial image	NDT	Difference (%)
d ₁ (m)	101.16	102.40	1.23
d ₂ (m)	155.21	157.21	1.29
α (°)	25.01	24.12	3.57

NDT: normal distributions transform.

Discussion

A complete HD map database is a crucial ingredient if AVs are to become a reality in Vietnam. Therefore, the first step in realizing this ambition is to develop a low-cost 3D mapping device. Firstly, the real-time decision-making capability of an AV, when driving and navigating, is increasingly dependent on the quality of the HD maps, in the nonstandard traffic infrastructure of Vietnam. For example, any driving scenarios such as stopping at the appropriate location, locating a traffic signal at the crossroads, or avoiding pedestrians who are not using a proper crosswalk, become very difficult for the AV to run without a proper HD map. Thus, as part of the decision-making process, mapping becomes a key factor in helping the AV make the correct decisions at the right time. Secondly, the portable personal mapping devices are especially suitable for Vietnamese traffic conditions, where most traffic is made up by motorbikes. An engineer wearing a mobile mapping backpack on a motorbike can reach many difficult locations in Vietnam.

The results of this study were compared to other works in the literature, as indicated in Table 6. Various test areas from different countries have been investigated, such as in Hong Kong, Taiwan, USA, and Vietnam. Wen et al.²⁴ tested sparse, suburban, and dense urban areas using an NDT-based graph SLAM technique. They found the mean lateral error to be 0.91 m, the mean longitudinal error 0.54 m, and the mean altitude error 0.15 m. However, it is worth noting that in that study, the accuracy of NDT-based graph SLAM depended heavily on the moving objects in the traffic such as double-decker buses, cars, and trucks. In a similar study in an urban environment, Chiang et al.²⁵ developed INS/GNSS/refreshed-SLAM for an urban area of Tainan city, Taiwan. The proposed method exhibited a performance including 0.137 m for the mean error in the northward direction and –0.794 m for the mean error in the eastward direction. In another work, Li et al.²⁶ combined NDT and graph SLAM to create an HD 3D map in underground coal mines. The relative errors for several measuring distances found by Li et al.²⁶ are –4.7% for 118 m, –24% for 200 m, and –29% for 70 m, respectively. In the present study, the relative errors for several measuring distances are 1.23% for 101.16 m and 1.29% for 155.21 m, respectively.

Table 6.

Comparison between different works for creating HD 3D maps.

References	Techniques used	Test areas	Performance	Location
Wen et al.²⁴	NDT-based graph SLAM	Sparse area, suburban area, and dense urban area	Performance in a suburban area in normal traffic conditions:Mean lateral error: 0.91 mMean longitudinal error: 0.54 mMean altitude error: 0.15m	Hong Kong
Ilci and Toth¹⁰	GNSS/IMU/LIDAR sensors	Mixed urban environment, including densely packed and tall buildings, and roads shared by cars, bicycles, and pedestrians	cm-level accuracy	Ohio State University’s main campus area, Columbus, USA
Li et al.²⁶	NDT-based graph SLAM	Underground coal mine	Relative errors for several measuring distances:118 m: −4.7%200 m: −24%70 m: −29%
Chiang et al.²⁵	INS/GNSS/refreshed-SLAM	Scenario 1:Hai’an underground parking lotScenario 2:Tainan urban and University campus	Scenario 1:Mean error in north direction: −5.633 mMean error in east direction: −2.695 mScenario 2:Mean error in north direction: 0.137 mMean error in east direction: −0.794m	Tainan city, Taiwan
This work	NDT-based graph SLAM	University campus	Relative errors for several measuring distances:101.16 m: 1.23% (102.40 m)155.21 m: 1.29% (157.21 m)	Phenikaa University’s main campus, Hanoi, Vietnam

SLAM: simultaneous localization and mapping; HDL: high-definition LIDAR; NDT: normal distributions transform.

The results in this study showed that by using only a low-cost personal mapping device with basic components, a functional data map could be generated with relative accuracy lower than 4% (Table 5) when compared with corresponding aerial data. The environment in the point cloud captured by the device is detailed enough to build up additional layers in the HD maps, such as a semantic map layer or geometric map layer. Based on these results, future studies will focus on an advanced portable mapping device for precise HD mapping with the support of ground control points measured by RTK GNSS and IMU sensors.

Conclusion and prospects

Two point-cloud map making approaches were tested in this study. Both methods only use LIDAR sensor data to generate the point cloud, without assistance from other sensors like IMU or GNSS. The result confirms that a small-scale HD point-cloud map can be produced by a low-cost mobile mapping system using only a LIDAR sensor. Combined with large-scale aerial point-cloud mapping data, a complete database of 3D maps can be compiled for navigation purposes for AVs. Furthermore, the results indicated that the NDT algorithm performs better than the HDL algorithm.

In further works, the uncertainty estimation of NDT-LIDAR graph SLAM should be investigated—for instance, uncertainty stemming from traffic conditions and 3D building models. Moreover, the accuracy of NDT-based graph SLAM should be evaluated as a function of traffic conditions including moving objects such as cars, pedestrians, and so on.

Footnotes

Abbreviations and notation

Abbreviation, notation	Explanation
AV	Autonomous vehicle
SLAM	Simultaneous localization and mapping
HD	High definition
NDT	Normal distributions transform
HDL	High-definition LIDAR
IMU	Inertial measurement unit
GNSS	Global navigation satellite systems
LIDAR	Light detection and ranging
RTK	Real-time kinematic positioning

Data availability statement

The raw/processed data required to reproduce these findings will be made available on request.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Declaration of conflicting interests

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iDs

Le Anh Son

Ho Xuan Nang

References

SAE Levels of Driving Automation^TM Refined for Clarity and International Audience, https://www.sae.org/blog/sae-j3016-update (2021). Accessed 30 August 2021.

Wang

. Ultra-local model predictive control: a model-free approach and its application on automated vehicle trajectory tracking. Control Eng Pract 2020; 101: 104482.

Beer

Haase

Ruskowski

, et al. Background light rejection in SPAD-based LiDAR sensors by adaptive photon coincidence detection. Sensors 2018; 18: 4338.

Javanmardi

, et al. Autonomous vehicle self-localization based on abstract map and multi-channel LiDAR in urban area. IATSS Research 2019; 43: 1–13.

Qiu

Yuan

, et al. A method to keep autonomous vehicles steadily drive based on lane detection. Int J Adv Robot Syst 2021; 18: 17298814211002974.

Erke

Bin

Yiming

, et al. An improved A-Star based path planning algorithm for autonomous land vehicles. Int J Adv Robot Syst 2020; 17: 1729881420962263.

Sobreira

Costa

Sousa

, et al. Map-matching algorithms for robot self-localization: a comparison between perfect match, iterative closest point and normal distributions transform. J Intell Robot Syst 2019; 93: 533–546.

Peng

Shen

. Spectrum management for multi-access edge computing in autonomous vehicular networks. IEEE trans Intell Transp Syst. Epub ahead of print 2020. DOI: 10.1109/TITS.2019.2922656.

Takeuchi

Tsubouchi

. 3-D scan matching using improved 3-D normal distributions transform for mobile robotic mapping. In: IEEE international conference on intelligent robots and systems. Epub ahead of print 2006. DOI: 10.1109/IROS.2006.282246.

10.

Ilci

Toth

. High definition 3D map creation using GNSS/IMU/LiDAR sensor integration to support autonomous vehicle navigation. Sensors (Switzerland); 20. Epub ahead of print 2020. DOI: 10.3390/s20030899.

11.

Wang

, et al. Deep regression for LiDAR-based localization in dense urban areas. ISPRS J Photogramm Remote Sens 2021; 172: 240–252.

12.

Aldibaja

Suganuma

Yanase

, et al. Reliable graph-SLAM framework to generate 2D LIDAR intensity maps for autonomous vehicles. In: 2020 IEEE 91st vehicular technology conference (VTC2020-Spring), Antwerp, Belgium, 25–28 May 2020, pp. 1–6. IEEE.

13.

Martínez-Díaz

Soriguera

Pérez

. Autonomous driving: a bird’s eye view. IET Intell Transp Syst 2019; 13: 563–579.

14.

Chetverikov

Svirko

Stepanov

, et al. The trimmed iterative closest point algorithm. In: Proceedings—international conference on pattern recognition. Epub ahead of print 2002. DOI: 10.1109/icpr.2002.1047997.

15.

, et al. Integrate point-cloud segmentation with 3D LiDAR scan-matching for mobile robot localization and mapping. Sensors 2020; 20: 237.

16.

Biber

. The normal distributions transform: a new approach to laser scan matching. IEEE Int Conf Robot Autom Systems 2003; 3: 2743–2748.

17.

Carballo

Monrroy

Wong

, et al. Characterization of multiple 3D LiDARs for localization and mapping using normal distributions transform. arXiv:200401374 [cs] , http://arxiv.org/abs/2004.01374 (2020, accessed 29 August 2021).

18.

Liu

Wang

Zhang

. High definition map for automated driving: overview and analysis. J Navig 2020; 73: 324–341.

19.

Stoyanov

Magnusson

Almqvist

, et al. On the accuracy of the 3D normal distributions transform as a tool for spatial representation. In: 2011 IEEE international conference on robotics and automation, Shanghai, China, 9–13 May 2011, pp. 4080–4085. IEEE.

20.

Choe

Shim

Chung

. Urban structure classification using the 3D normal distribution transform for practical robot applications. Adv Robot 2013; 27: 351–371.

21.

Das

Servos

Waslander

. 3D scan registration using the normal distributions transform with ground segmentation and point cloud clustering. In: 2013 IEEE international conference on robotics and automation, Karlsruhe, Germany, 6–10 May 2013, pp. 2207–2212. IEEE.

22.

Hong

Lee

. Probabilistic normal distributions transform representation for accurate 3D point cloud registration. In: 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), Vancouver, BC, Canada, 24–28 September 2017, pp. 3333–3338. IEEE.

23.

Koide

Miura

Menegatti

. A portable three-dimensional LIDAR-based system for long-term and wide-area people behavior measurement. Int J Adv Robot Syst. Epub ahead of print 2019. DOI: 10.1177/1729881419841532.

24.

Wen

Hsu

L-T

Zhang

. Performance analysis of NDT-based graph SLAM for autonomous vehicle in diverse typical driving scenarios of Hong Kong. Sensors 2018; 18: 3928.

25.

Chiang

K-W

Tsai

G-J

Chu

H-J

, et al. Performance enhancement of INS/GNSS/refreshed-SLAM integration for acceptable lane-level navigation accuracy. IEEE Trans Veh Technol 2020; 69: 2463–2476.

26.

Zhu

You

, et al. Efficient laser-based 3D SLAM for coal mine rescue robots. IEEE Access 2019; 7: 14124–14138.