Building a Global 3D Routing Map

Mapping company HERE, co-owned by German automotive companies Audi, BMW, and Daimler, uses a fleet of more than 200 cars to collect dense point cloud data about roads around the world. The data from these mobile mapping vehicles is processed to secure privacy and produce detailed routing maps. This data is the input for various applications, ranging from traditional car navigation to analysis of the steepness of ramps. The most compelling application, however, is the application of this data to enable self-driving cars.

Digital street maps are essential to car navigation and visualisation of online mapping products. Traditionally, such maps are made of annotated vectors in a spatial database that can be queried to retrieve optimal routing information. Increasingly, the maps are enriched with 3D contextual information. This 3D data is used for smart city management or as the foundation for driverless cars. At HERE, the 3D data is collected by mobile laser scanning on a large fleet of cars around the world.

Mobile Mapping

Over 200 cars, known as TRUE cars, are driving around the world to collect the data (Figure 1). Each vehicle is outfitted with a 1.5m-high rig that holds a laser scanner, cameras and a GNSS/IMU system. The scanner, a Velodyne HDL-32E, is a small rotating scanner that contains 32 independent lasers which emit pulses in a swath of 40 degrees. In total, the scanner collects up to 700,000 points per second. The ranging accuracy of the scanner is 2cm and points can be scanned at a distance of up to 100m. Thanks to the inclined position of the scanner on the roof of the car, shadow effects are mitigated as much as possible.

The rig contains a GNSS receiver and an inertial measurement unit (IMU) which collects position, heading and attitude data. For street imagery, the TRUE cars also include four wide-angle 24MP cameras. The images from these cameras can be stitched into panoramic photos. It is advantageous to use a small number of cameras for panoramic photography, as this reduces the number of seam lines in the stitched photo.

Operations

For efficient data collection, each TRUE car has a routing system installed that guides the driver to collect data from unmapped areas or zones which require refreshed data. The drivers focus primarily on major urban areas but data is collected in some less populated regions too, such as highways outside of urban centres or rural roads. The combined sensors generate approximately 140GB of data per day. Globally, the fleet of TRUE cars collects 100 terabytes of data, capture 9.5 million images and drive more than 50,000km in a single week. Between 2010 and 2015, 5 million kilometres of roads were mapped in 30 different countries. Once the encrypted hard drives are full, the drivers send the contents to one of three processing centres in Fargo (North Dakota, USA), Leon (Mexico) or Mumbai (India). These centres process the data and the hard drives are returned to the field for reuse after reformatting.

Processing

After the new data is received by one of the processing centres, it undergoes a number of processing steps. These steps are partly automated, but a human operator is needed to complete many of the checks. All images are visually checked for quality. Photos with bad weather or sun glare are deleted. To eliminate privacy concerns, blurring filters are automatically applied to people’s faces and licence plates. After the privacy check, each map is tagged with road attributes such as stop signs and speed limit signs. Those street signs are automatically detected from the images using algorithms that are capable of recognising signs in 22 countries. A team of analysts cross-checks the automated results with the images to confirm the output of the tags and eliminate ambiguities. The resulting map is also cross-referenced against other sources, such as government databases and city maps, and run through a program that uses a set of rules to detect illegal situations or database inconsistencies. Internally developed algorithms are run on these different data sources looking for discrepancies as the data is processed.

The point cloud data is then analysed to retrieve lane markings and curb edges (Figure 2). Lane markings can be recognised from the point cloud because each point contains a value for reflected intensity. As lane markings are bright in comparison to the pavement, they also stand out very clearly in the point cloud. Curb edges can be detected by searching for clear break lines at the roadside.

End results

The end result of all processing is a database containing the detailed geometry of the road and its attributes including lane boundaries, curb edges, lane restrictions, speed limits, etc. This data can form the basis for car navigation databases, for example. The point cloud data is stored as a separate product in a cloud environment. The collected point clouds have an absolute accuracy of 5m and a relative accuracy of 20cm over a distance of 100m (Figure 3).

Self-driving cars

The development of self-driving cars is giving significant impetus to the collection of point clouds around the world. Compared to 2D maps, the HD maps provide more information at a higher fidelity and accuracy, including features such as lane markings and roadside barriers. Autonomous cars are equipped with an array of sensors to recognise the roads. The HD map is able to provide additional context for the real-time sensors, thus allowing the vehicle to distinguish anomalous situations from regular driving conditions – e.g. is a lane divider knocked down? Has a tree fallen into the street?

Additionally, while sensors on autonomous cars can detect a distance of around 30 metres, a car travelling at high speed such as on a motorway has a sensing horizon of just one or two seconds. A detailed 3D map helps cars to ‘peek’ around the corner. In addition, self-driving cars will be able to improve their positioning by referencing re the information contained in the map against what they sense in real time. This is an additional level of reliability compared with regular GNSS/IMU positioning. In 2013, Mercedes used the HD map to recreate the world’s first long-distance journey driven by Bertha Benz – an equally historic 100km drive, but this time completed by an autonomous vehicle.

In other applications of the technology, inspecting the road condition can lead to safer roads while also reducing costs. The Americans with Disabilities Act (ADA) stipulates a certain size and maximum slope for ramps, and the City of Oakland in California used the 3D scan data to reduce the costly and labour-intensive field work required to identify and catalogue ADA-compliant ramps across the city. High-resolution panoramic imagery in conjunction with the overlapping 3D point cloud data allowed accurate measurements to be taken quickly and the necessary geometry to be extracted for cataloguing purposes.

Figure 1, A TRUE car maps the streets of Berlin.

Figure 2, Collected 3D point cloud with derived road centre lines.

Figure 3, Digitised lane centre lines at an intersection.

John Ristevski is vice president of reality capture and processing at HERE. John joined HERE in 2012 through the acquisition of his company, Earthmine, which developed mobile mapping systems. He was director of R&D at non-profit CyArk, and has lectured at Stanford’s Civil and Environmental Engineering Department. He has a master of science degree from the University of California at Berkeley and has degrees from the University of Melbourne in both geomatic engineering and law.