🔒 Locked

Line recognition algorithms?

Started by Lutrosis Apr 9, 2003 at 11:22 AM 4 replies 500+ views

Original Post

Apr 9, 2003 at 11:22 AM

Would anyone be able to point me in some general research directions for line recognition algorithms? I did a little googling and I can''t seem to find anything. I know shape recognition is a very complicated subject, but I''m after something simpler, in that it is fairly specific - given a bitmap with a bunch of lines on it (which may intersect, or share endpoints), I would like to be able to return a list of line endpoints. All the lines are perfectly straight, with no gaps, and are only a pixel thick (though the thickness can be dropped as a requirement if there are algorithms that would perform better given a thicker line). I have some ideas I''m going to try, but I''d love to be able to check out some existing approaches. Suggestions on where to start looking? (I searched the forums naturally, couldn''t find much - mostly on OCR and much more complicated machine vision info). In case you''re interested, I''m doing a basic image recognition project for a class

We''re tasked to come up with a method of recognizing stick figures in a bitmap. The actual problem definition is pretty boring, just a pixel-for-pixel map, but I''ve been allowed to modify it a bit - stick figures will be recognized based on a particular definition - must have a verticle line segment for a body (I''m not dealing with variable orientation, we only have a week for this

), two line segments of comparable length with an endpoint on the body line above the mid-point (arms), two segments with endpoints at lower body endpoint, and of comparable length (for legs) - that sort of thing. Ideally I''ll need some way of detecting a circle as well...haven''t gotten there yet

At any rate, I figure the above should be fairly straight forward given a list of lines. Getting the list of lines from the bitmap is the tricky part. Any kind of would be great, but all I''m really looking for are some research directions =] Thanks! -Lutrosis

Eelco

237

Eelco

Apr 9, 2003 at 12:26 PM

assuming the the lines are of constant color, or have some other unique property, it is in theory not very hard to recognise lines. scan the whole image pixel by pixel. as soon as you find a color witch is not a backgroundcolor, you start a floodfill from there, filling the area of that color (or other specific property). it should be a rather unstrict floodfill, so it doesnt stop when encountering a crossing or antialiased pixels. you need another condition for the floodfill to drop out of the loop though: the angle from the start of the floodfill to the point checking with should be more or less equal to the average angle of the pixels checked before. if its too big a difference, drop out of the floodfill and end the line at the last pixel checked.

so theoreticly its not too hard, but i supose it can be a real pain in the ass to implement. i cant think of a method for circles right now, but maybe a slightly changed version of the above would do.

greenMuzz

Apr 10, 2003 at 9:22 AM

Try the Hough transform, it's a pretty simple technique and easy to implement, i've done it myself so I should know. You may need to read up on the Sobel and Canny edge detectors first though.

try here for starters
http://www.dai.ed.ac.uk/HIPR2/hough.htm

can probably send you my implementation if you'd like a look, only took me two days to write.

[edited by - greenMuzz on April 10, 2003 10:24:41 AM]

minorlogic

Apr 10, 2003 at 9:42 AM

http://citeseer.nj.nec.com/68959.html - best resource

Try Intel Image Processing Librari, for a basics. There is implemented all that you talking about.

Lutrosis

Author

Lutrosis

Apr 10, 2003 at 1:30 PM

Thanks, you guys are awesome! Exactly what I was looking for =] If the end result turns out to be interesting, perhaps I''ll post it for kicks

Thanks again!

-Lutrosis

Lutrosis

Author

Lutrosis

Apr 26, 2003 at 12:03 PM

Just wanted to say thanks once again, project was a success =)

The end result was a program that could take a 24bit .bmp file as input, and reasonably accurately detect the presence or absence of a stick figure based on a fairly loose definition of a stick figure. I was pleased with the results, as this was my first attempt at anything even remotely related to image processing - I learned quite a bit.

As a side note, it seems to me that the success of the hough line transform with regard to detecting lines in images made up of actual lines (as opposed to edge detector output) is more or less dependent on a good thinning/pruning pass applied to the thresholded accumulator array. I was able to borrow a fantastic book on image processing algorithms from a professor and hammer out a decent thinning algorithm, but it could use improvement.

I''m babbling to myself...but thanks for the guidance!

-Lutrosis

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.