OpenStreetMap

First attempt at automatic road following

Posted by bdiscoe on 3 September 2013 in English (English)

My naive thought was, many roads are clear and self-similar, how hard could it be to write an algorithm which simply walks along a step at a time, moving in the direction which is most similar to the previous spot in the image?

It turns out the catch is in "similar". There are apparently countless academic papers on how to evaluate when two images are "similar". I naively went ahead and tried a dumb algorithm: the summed difference of the RGB values.

Amazingly, it actually works in a lot of cases. Behold:

following

The first two points are given, the rest moving downward follow the road based on naive image similarly. Now, it's not hard to find cases where it fails and drifts off the road - in particular it struggles if the road gets a few pixels wider, as many do - but this is just a first test.

Comment from Richard on 3 September 2013 at 08:31

Looks great. LAB colours are really good for colour differences, and simple to code: see P2 code at https://github.com/systemed/potlatch2/blob/tracer/net/systemeD/potlatch2/tools/TracerPoint.as .

The Potlatch 2 branch was working really, really well (if I say so myself :) ). I actually traced large parts of SW England and NW Wales using it when the licence changeover was imminent; two major contributors in the area hadn't agreed to the new licence, and auto-tracing from OS StreetView imagery provided an easy way to save the roads.

The main reason it was never deployed is that I hadn't figured out a UI for defining the limits of the tracing operation. The current viewport was usually too small, the 'sum total of loaded imagery' too large (and too random).

I may resuscitate it one day, but until then, you can see the rest of the code at https://github.com/systemed/potlatch2/blob/tracer/net/systemeD/potlatch2/tools/Tracer.as . Effectively the workflow is:

  1. Flood-fill (startPixelIndex/runPixelIndex)
  2. Thin to a skeleton (runThin/thin)
  3. Mark junctions (makeWaysFromSkeleton)
  4. Remove unnecessary junctions (makeWaysFromSkeleton -> thinJunctions)
  5. Create pixel chains, i.e. polylines at pixel resolution (createPixelChains)
  6. Delete dupes (createPixelChains)
  7. Run Douglas-Peucker over each one to make sensible polylines (createPixelChains)
  8. Convert to OSM nodes and ways (createPixelChains)
Hide this comment

Comment from bdiscoe on 4 September 2013 at 05:34

That approach actually worked in many cases? I'm glad to hear it, and I look forward to trying it someday, but it seems like a no-go from the first step, flood-fill. Most roads vary considerably in color over the course, from one end to the other they may be wet or dry, shadowed or not, pavement or dirt conditions varying. A flood-fill would have to be loose enough to find the whole road, but not so loose that it spills far outside - and those bounds would have to be adjusted from place to place. How could that work?

Hide this comment

Leave a comment

Parsed with Markdown

  • Headings

    # Heading
    ## Subheading

  • Unordered list

    * First item
    * Second item

  • Ordered list

    1. First item
    2. Second item

  • Link

    [Text](URL)
  • Image

    ![Alt text](URL)

Login to leave a comment