[OSM-talk] (magical?) road detector

[Thibault North]

Hi Ido,

Thanks for your answer.
Concerning multi-resolution, as you pointed it out, it may fail is the road
is too narrow. But to be used with OSM, I don't think it will be a major
issue. Even at low zoom level, a user will need to actually see the road
network and hence there is some hope for the shortest-path algorithm to find
its way. For example, the use case demonstrated on the blog post will work
ok with a multi-resolution approach (I tried it by dividing each image
dimension by two, which is four times less pixels). This may not be
considered a huge gain, but still if the path length is important, the
high-resolution graph reduces significantly in size and leads to much
shorter computation times.

A better approach would certainly be a complete road extraction by image
processing means (a lot of papers were published on that topic), but it will
quite heavy, and can often not be achieved completely automatically
(requires user input at some point to identify the road, this is something
we have... but that we may want to know before to prepare the area with some
processing!)
Plus, we can not be sure that the road network will always be connected.

Regards,
Thibault

On Sat, Feb 5, 2011 at 5:04 PM, Ido Omer <Ido.Omer at microsoft.com> wrote:

> Hi Thibault,
>
> Thanks for the feedback and the blog post.
>
> The algorithm is indeed a shortest path algorithm. As you mentioned the
> preprocessing is probably the most important stage (but post processing is
> probably close second).
> Although our current solution is far from perfect (as you demonstrated), we
> found it generally works well, especially when you don't try to be too
> challenging...
>
> We played around with multi-resolution ideas, and we have some ideas for
> the future, but a simple multi-resolution solution will probably fail; the
> road will very quickly become too narrow to trace, and a large error at low
> resolution will not enable recovery at higher resolution.
>
> We are also thinking of other solutions that will be a bit less sensitive
> than pixel based Dijkstra, but these ideas will probably only be implemented
> in the next version.
>
> Regards,
> Ido
>
> -----Original Message-----
> From: Thibault North [mailto:thibault.north at gmail.com] On Behalf Of
> Thibault North
> Sent: Saturday, February 05, 2011 8:22 AM
> To: talk at openstreetmap.org
> Cc: Ido Omer
> Subject: Re: [OSM-talk] (magical?) road detector
>
> Hi Ido,
>
> Could we have more information about how the road detector works?
> I gave it a quick try, and wrote a few thoughts about it after making a
> short comparison with the use of Dijkstra's algorithm.
> See
> http://tnorth.ch/blog/index.php?post/2011/02/04/Bing-road-detect-API-and-
> vectorization
>
> Thanks,
> Thibault
>
> > On Fri, 2/4/11, Ido Omer <Ido.Omer at microsoft.com> wrote:
> >
> > From: Ido Omer <Ido.Omer at microsoft.com>
> > Subject: [OSM-talk] (magical?) road detector
> > To: "talk at openstreetmap.org" <talk at openstreetmap.org>
> > Date: Friday, February 4, 2011, 7:59 PM
> >
> > Hi Guys,
> >
> > I am a researcher at Microsoft and I am currently working on the road
> > detector. I joined a bit late and can’t post answers in the existing
> > road detector thread, but I might be able to provide some additional
> > info regarding the road detector. It is *FAR* from being perfect, but
> > in our experiments it may produce a lot of value (== save time) if you
> > use it correctly. When use it correctly means don’t expect too much,
> > so here are some practical tips: 1.
> > It is currently uses the two end points as example and tries to find a
> > path that is similar to those examples, so it is recommended to use
> > the tool at a zoom level that will let you make sure you click on a
> > road and not near a road (we will probably loosen that restriction in the
> future). 2.
> > Don’t try to challenge the detector too much, it will probably fail,
> > instead if you have a very complicated winding road break it into a
> > few sections and let it detect shorter legs (it will still save you
> > most of the clicks…)
> > 3.
> > One of the main features used is color, so if the road changes its
> > color a lot, break it again into shorter legs. 4.
> > We currently only compute one path (road) between the points and
> > cannot provide a meaningful score for that path. Defining a score is a
> > difficult problem (but we are open to ideas…). 5.
> > To speed things up, we are using a bounding box that is in many cases
> > smaller than the bounding box provided by the client (we take constant
> > margins around the bounding box defined by the two end points). This
> > means that if you click on the two end points of a U shaped road we
> > might truncate the lower part of the U and find a “shortcut “ through
> > buildings, fields, etc. And again you’ll need to break the query into
> > shorter legs… (I am currently working on speeding things up and I hope
> > to get rid of this limitation in a week)
> > 6.
> > The algorithm is currently ignoring junctions, but I should be able to
> > add them very soon (early next week) That is for road detection. The
> > other mode we will provide is road exploration which will enable
> > finding all the roads in a certain bounding box (well, you’ll probably
> > need to click once or twice…) I am not sure if there is an exposed
> > version of this service (I hope not, since so far it is really a bunch
> > of experiments…) but we should have it really soon (a week or two).
> > For the road exploration we will probably have some kind of certainty
> level for each road segment.
> > I will be very happy to hear of any complaints/requests/places where
> > you think the detector should work but it fails/any other feedback.
> > Thanks,
> > Ido
> >
> >
> >
> >
> >
> > -----Inline Attachment Follows-----
> >
> > _______________________________________________
> > talk mailing list
> > talk at openstreetmap.org
> > http://lists.openstreetmap.org/listinfo/talk
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/talk/attachments/20110205/f7d8dca0/attachment-0001.html>