Re: help on line detection in maps
- From: "Ted Dunning" <ted.dunning@xxxxxxxxx>
- Date: Fri, 30 Sep 2005 02:10:23 GMT
No, it doesn't come with source. Running it or its cousins is
instructive, however.
If you want to detect lines in a raster image, then a good place to
start is with the Hough transform.
The way that this works is that each lit pixel can be part of any line
that goes through that point. If you express these lines as a linear
expression,
y = a + b * x
then each point can belong to a set of lines which are described by the
two parameters that are solutions of y_0 = a + b * x_0. You might
prefer to use theta = tan^-1 b, but the game is the same. Each point
contributes some mass to all of the lines that it might be part of and
those lines are represented either as lines in (a,b) or curved figures
in (a, theta) space.
If take all of the pixels in your original image and convert them to
pixels in Hough space, then the brightest points in Hough space
represent linear features in the original image. Pick one or more, use
those lines to describe the original image (or segments of those lines)
and repeat until you have a good approximation of the image.
The result is an image composed of lots of nearly parallel features
clustered around linear features of the image. These linear features
are points in Hough space that can be clustered (or you can define a
simple metric and cluster directly). Now you have a representation
with a decreased number of line segments.
The final step in a simple version of a line finder is to group
neighboring but non-parallel segments to build splined representations
of curvilinear segments.
Getting to this simplest state isn't all that hard, but it does take a
fair bit of grunt work to get it all just right.
The next level of theoretical interest is to think of the thing that
originally caused the drawing you are trying to digitize. That
original thing had a probability distribution and that distribution and
the cultural conventions used to produce drawings give very strongly
peaked distributions over the space of all possible images. For
instance, an drawing that is mostly white paper is much more likely
than one that is mostly black (I am talking line drawings here, not
general images). Likewise, it is highly probable that there is a
considerable peaking of line orientations around something that is
nearly horizontal and something that is at right angles to this.
Again, circles and ellipses are more common than other curved shapes
and lines normally have fairly constant width.
All of these probabilistic considerations allow you to work in the
space of abstract drawings and build an algorithm that finds something
like an MAP estimator of the original drawing. This sort of noisy
channel drawing extraction is /much/ harder to build, but has
potentially much higher performance.
Oh.... you should also look at spectral clustering. It can be very,
very helpful as a pre-processing step.
Good luck. Share your results.
[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@xxxxxxxxxxxxxxxxxx>, and ]
[ ask your news administrator to fix the problems with your system. ]
.
- References:
- help on line detection in maps
- From: makc . the . great
- Re: help on line detection in maps
- From: makc . the . great
- help on line detection in maps
- Prev by Date: Using CBR/KBS for Service Engineers in the field
- Next by Date: Site Review
- Previous by thread: Re: help on line detection in maps
- Next by thread: ANN: MSc Intelligent Systems Stipends available (Oct 2005)
- Index(es):
Relevant Pages
|
Loading
