Yesterday, the Bing Maps blog announced the availability of their experimental service for road detection.
That is good news for OpenStreetMap, especially because this service is easily accessible and can already be used inside JOSM to assist the mapper.
It can also be tested at qualitystreetmap
However, I could not find any information about how it works, but I suspect they use a shortest-path algorithm such as Dijkstra, perhaps with some heuristic like A*.
It works pretty well especially when the road is not too sinuous. Unfortunately, the results are worse when the road makes important angles, encouraging the algorithm to take a faulty shortcut.
Faulty road extraction
Assuming that Dijkstra was used, the quality of the results are highly dependent on the pre-processing step. The images need to be desaturated, and some processing will increase the chances for the algorithm to follow exactly the roads.
I have been playing around today, running an old program implementing the Dijkstra algorithm in C, here is what I get:
Shortest-path computation with Dijkstra algorithm
Of course, that is far from being perfect: it looks like Dijkstra is drunk (thanks Philippe), and the selected path does not stay centered on the road. A post processing step for smoothing could be used (even decimation could do a good job), or the preprocessing may also need to be fine-tuned.
An accurate and robust road extraction is a matter of trade-offs, and this example might not be representative of the real performances of the algorithm used at Bing maps.
To obtain that, the cost function (distance) of the Dijkstra algorithm is the most straightforward one: the cost from one to the next pixel is related to the difference of their intensity. (after some smoothing.)
Dijkstra wants to minimize the cost of the path, and needs to be comfortable on the road. The preprocessing that I used for that is simply a histogram equalization after desaturating by lightness, and finally inverting colors. This way, the roads are very dark, and the travel cost is minimized when they are followed.
A good way to visualize that is to see this gray-level picture as an altitude map, where the darkest pixels represent the lowest altitude, while the brightest ones are at higher altitude.
The road forms some kind of valley. As mentioned before, sometimes a lot of the road pixels lie in the 0-altitude level, and the cost for moving around the center of the road is zero: this leads to a sinuous path. This can be fixed by applying a slight amount of Gaussian blur, which will bend the bottom of this valley and force a straighter path.
Another potentially interesting feature is the possibility to decrease the computation time when long paths are to be found. A first pass is done on a lower resolution image, and a region of interest is defined around that approximate path. Then, only the pixels of this region of interest are used to compute the path at higher resolution.
Schematics of the multi-resolution behaviour
Speaking of computation time, the screenshot shown above requires 60ms to compute the path (no multi-resolution). Most of the time is spent creating the initial graph (478ms). It can be used later for other computation in that area.
I would be interested to know more about the algorithm implemented at Bing maps, how they concretely handle the required image processing to achieve vectorization. Also, I am wondering how interesting it is when mapping a region: road extraction is already quite easy to do "by hand". May be that the real gain would be the ability to automatically extract roads for a whole residential area, and just let the user check and fix it.
The source for the Dijkstra algorithm can be found here. You may want to try the Python module, which is easier to use than the multiple tests presents in the source with hardcoded values (sorry for that.)
Go to src/python_mod3, build and install the module. Finally, look at the file module_use_example.py to find out how to run it.