Apr 19 2018
Map apps may have transformed man’s world, however not all of it has been mapped yet. Specifically, mapping roads can be challenging and tedious: Even after capturing aerial images, companies will still have to spend many hours tracing out the roads manually. Consequently, even companies like Google haven’t yet achieved mapping the huge majority of the over 20 million miles of roads spread across the globe.
To create complete road maps companies like Google often have to have employees take existing aerial images with incomplete information and manually fill in the gaps. (Images courtesy of the researchers)
Gaps in maps are an issue, especially for systems being designed for self-driving cars. To solve this issue, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) have developed RoadTracer, an automated technique to design road maps that are 45% more accurate than present approaches.
Utilizing data from aerial images, the team says that RoadTracer is not merely more accurate, but more cost-effective than present methods. MIT professor Mohammad Alizadeh says this research will be beneficial both for top tech players like Google as well as for smaller organizations that do not have the resources to curate and correct huge amounts of inaccuracies in maps.
RoadTracer is well-suited to map areas of the world where maps are frequently out of date, which includes both places with lower population and areas where there’s frequent construction. For example, existing maps for remote areas like rural Thailand are missing many roads. RoadTracer could help make them more accurate.
Mohammad Alizadeh
For instance, if the RoadTracer looked at aerial images of New York City, it could accurately map 44% of its road junctions, which is over twice as effective as traditional methods based on image segmentation that could map just 19%.
The paper, which is a partnership between CSAIL and the Qatar Computing Research Institute (QCRI), will be presented in June at the Conference on Computer Vision and Pattern Recognition (CVPR) in Salt Lake City, Utah.
Alizadeh’s MIT co-authors comprise graduate students Fayven Bastani and Songtao He, and Professors Hari Balakrishnan, Sam Madden, and David DeWitt. QCRI co-authors include senior software engineer Sofiane Abbar and Sanjay Chawla, who is the research director of QCRI’s Data Analytics Group.
Existing efforts to automate maps include training neural networks to study aerial images and identify separate pixels as either “road” or “not road.” Since aerial images can frequently be unclear and incomplete, such systems also necessitate a post-processing step that’s intended to fill in a few of the gaps.
Unfortunately, these so-called “segmentation” methods are mostly imprecise: If the model mislabels a pixel, that mistake will get amplified in the final road map. Mistakes are more likely if the aerial images have buildings, trees, or shadows that hide where roads begin and end. (The post-processing step also necessitates making decisions based on assumptions that may not hold up at all times, like connecting two road segments just because they are adjacent to each other.)
In the meantime, the RoadTracer designs maps step-by-step. It begins at a known location on the road network, and uses a neural network to observe the surrounding area to establish which point is most probable to be the next part of the road. It then incorporates that point and repeats the process to progressively trace out the road network a single step at a time.
Rather than making thousands of different decisions at once about whether various pixels represent parts of a road, RoadTracer focuses on the simpler problem of figuring out which direction to follow when starting from a particular spot that we know is a road. This is in many ways actually a lot closer to how we as humans construct mental models of the world around us.
Fayven Bastani
The team trained the RoadTracer on aerial images of 25 cities spread over six countries in North America and Europe, and then assessed its mapping abilities on 15 more cities.
“It’s important for a mapping system to be able to perform well on cities it hasn’t trained on, because regions where automatic mapping holds the most promise are ones where existing maps are non-existent or inaccurate,” says Balakrishnan.
Bastani says that the fact that the RoadTracer had an error rate that is 45% lesser is vital to making automatic mapping systems more useful for companies like Google.
“If the error rate is too high, then it is more efficient to map the roads manually from scratch versus removing incorrect segments from the inferred map,” says Bastani.
Nevertheless, implementing something like the RoadTracer wouldn’t completely remove the human factor: The team says that they could envision the system suggesting road maps for a large region and then with a human expert the design could be double-checked.
“That said, what’s clear is that with a system like ours you could dramatically decrease the amount of tedious work that humans would have to do,” Alizadeh says.
Indeed, one benefit to the RoadTracer’s incremental method is that it makes it a lot easier to rectify errors; human supervisors can just correct them and re-run the algorithm from where they stopped, instead of continuing to use imprecise information that filters down to other parts of the map.
Obviously, aerial images are only one piece of the puzzle. They do not give users information about roads that have underpasses and overpasses, as those are very difficult to determine from above. Consequently, the team is also separately creating algorithms that can construct maps from GPS data, and working to combine these approaches into one system for mapping.
This research project was supported, partially, by the Qatar Computing Research Institute.
RoadTracer: Better Automated Maps