I am working on a program that detects lines in an image. The idea was to make a program that would allow people to fill in a hand drawn image with color. The only method I can think of for detecting lines is to find the rate of change of color at each pixel, but this doesn't work well with pencil shading as there is a lot of noise in the image. I tried applying some smoothing before I check for lines but that causes less noisy areas of the image to lose detail. Any ideas would be appreciated... I'd like to here opinions of my work thus far. Some images my program created can be found on my homepage. I wasn't sure whether to put this under graphics or AI, but in the end I decided to go with AI becuase it is more related to optics than drawing.

Wavelet analysis is a very good technique for detecting abrupt changes in signal frequency... and works well on multi-dimensional data. Edge detection is a common application of this analysis technique. Start with [Google]... you'll find a wealth of information online.

Cheers,

Timkin

Run a noise reduction filter over the image.
Create a binary image from that image.
Run other filters as necessary.
You might look into an edge detection algorythm too.

There is a really good book called "Machine Vision" that is an excellent resource for this topic.

Yep, check "edge detection", but beware: most edge detection techniques are optimised for "step edges", while what you want to detect seems to be "lines edges".

The classical method to detect edges is effectively to find the "rate of change of colors", which will be called the "Image gradient" in the litterature. That works well for step edges. You compute the derivatives of the images in x an y, compute the gradient (remember your high school maths, or check the literature), and edges will be at the local maxima of the gradient.

For line edges, I recommand using the "laplacian", which means you use the second derivatives, and your edges will be located at zero-crossings. Works like a charms.

If you have noisy data, the best way is to smooth while you compute the derivative of the images. I.e instead of using finite differentes to derivate, use the derivatives of a smoothing kernel. Everyone (almost) use the derivative of the gaussian.

I strongly recommand the book "Digital Image Processing" by Gonzalez and Woods. Good beginner book, everything you will likely need for this project is inside.

I know of some articles that are akin to your project, I will check and post some reference if I find them. Welcome to the wonderful world of Image Processing :)

Here's an idea. You start small. After turning the image into binary(only black and white), you consider any two black pixels touching to be a line unit. Now you look for line units next to each other until there are none left. Those with the slope almost the same can be joined together. I am still thinking about this idea, but if it helps...

'Hough Transform'

Detects lines. Works well. Google it. :)

Will

he said "lines", but he didnt mean "straight lines", he really meant "edges".

edit: I am almost positive of that.

Ohh, yeah. I should have read more carefully.

I think you're on the right-track by applying filters to your pencil drawing before filling them.

Instead of 'smoothing' though, try recursive runs of a median filter. This should give you areas of uniform colour.

You could also try segmenting the image based on texture, instead of just colour. This may or may not help. :)

Will

Rofl... everything described here (transforms, filtering, gradient based analysis) is all covered by doing a wavelet analysis of the image. If you're going to do something, don't 'hack it', do it properly. Yes, there are other methods out there that are useful... but they're generally not as robust as this single method.

Timkin, I think a wavelet analysis is overkill for a simple edge detection. Canny have been *proven*, and I mean proven as in mathematically proven, to be more robust and accurate as anything else for step edges detection. Canny for step edges, and zero-crossing of laplacian for line edges is not "hacking it", it IS the proper way of doing it.