OpenStreetMap
Auto roads, part 2
Posted by bdiscoe on 4 September 2013 in English. Last updated on 6 September 2013.By reducing the step size, I can actually get my naive road-follower to do a better-than-expected job of following curves:
I’m guessing that this is because roads are more self-similar than what surrounds them, so looking for linear self-similarity stays on the road.
What it does NOT do, however, is find the middle of the road. Look closely and you’ll see that the path drifts over to one edge of the road and stay there, then wanders back again.
This makes sense; road edges have the same linear self-similarity as road centers, so it’s just as happy to follow an edge. But, for OSM we don’t want edges. How to tell it to stay in the “middle”? Currently each next point compares the image from the previous point. This makes it largely immune to gradual changes (like the road becoming unpaved, or wet, or shadowed, or newer/older pavement, or even aerials taken at different times) but it allows it to drift to one edge or the other. We could compare to the initial (centered) point, which would solve the drift, but that would to fare poorly if the road’s coloration changes over its course.
It will also need some criteria for deciding the road has ended. We can’t use an absolute similarity value, since it will vary from place to place. Perhaps if we assume that the initial stretch of road is good, then that calibrates our expected similarity; anything that is e.g. 50% less similar than that can be considered “probable end of road”.
Discussion
Comment from Aury88 on 4 September 2013 at 07:31
Hi bdiscoe, Your work is very impressive! I’m curious how it will work in the case of similar roads that intersect and if this algorithm can be used to identify other elements (eg rivers or the outline of buildings …) Regards, Aury88
Comment from raykendo on 4 September 2013 at 13:53
To handle the middle of the road issue, you could evaluate the similarity over an arc or a line across the road. Instead of picking the first point that’s similar, gather a list of points along the arc that are similar, and pick the one in the middle. A little slower, but it might work.
Comment from bdiscoe on 4 September 2013 at 18:58
Aury88: Right now the code assumes the road curves no more than +/- a few degrees per step, so it won’t turn sharp corners; it should stop if it reaches a T junction. If two roads intersect at a very sharp angle (a narrow Y junction) it might find either of the roads going forward; this is unavoidable, even a human might not know which is the “correct” connecting road. As for rivers, it could easily follow very regular-looking streams which don’t turn too sharply, but most rivers are too large or messy (I find that the existing JOSM plugin “FastDraw” already works well for them.) Building outlines are almost never clearly linear, so I would use a whole different approach for those (like the iD research guys have shown).
raykendo: Yeah, I’ve been thinking of doing that as an extra step. I’m already scanning forward to find which way is the most “similar”; a second scan could look for “middle”, perhaps by looking for symmetry in color. Then we have two competing directions - “this way looks like the road continues”, “this way looks like the middle of the road”, and I could try blending the two directions, perhaps based on the confidence of each result.
Comment from booo on 4 September 2013 at 23:21
Any plans to release the source code?
Comment from Peter Dobratz on 5 September 2013 at 02:49
This is interesting work. Once you figure out the middle of the road issue, you might want to vary the spacing between points based on how straight the road is.
Comment from bdiscoe on 6 September 2013 at 05:49
booo: Better than releasing the source code, if it actually works well, I’d want to see it as a standard feature in JOSM. But, I’m not assuming success here, anything resembling computer vision/AI tends to have mediocre solutions at best :)