Re: Fast segmentation of large images



Hi Soren,

I would suggest using a run-length encoding based connected component
analysis. As the pixels you are looking for make about 1-2% of full
image, this would work much quicker than using flood fill or its
variations. Some good links on this subject are:

http://www.cs.bilkent.edu.tr/~duygulu/Courses/CS554/Spring2006/Notes/BinaryImageAnalysis.pdf
http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tp/&toc=comp/trans/tp/1996/01/i1toc.xml&DOI=10.1109/34.476016

Essentially you walk once through your image row-by-row creating a
run-length encoded image. Then for finding connected components you
just work with the compressed representation. The bwlabel() function in
Matlab is also coded that way. It should work much faster for typical
images compared to flood fill or its variants.

Regards,

Tahir

Soren Holstebroe wrote:
You can use modified single-pass indexed floodfill. You will have to
make an indexed image, index for each pixel. Make a table for scanned
connected areas and a table for joining connected areas.

Thank you for your comment. I have considered this traditional method, but I
would prefer not allocating, say 16 or 32 bits times 80 mpixels so I was
rather fishing for a lean mean low-cost method.

I have struggled creating my own algorithm where I have an index table for
the last and current row. It actually works fast and has a tiny memory
overhead, but it fails for some patterns, like circular connected areas. I
have some ideas how to overcome these problems, but these experiments take a
lot of time, so I figured that someone might have developed an efficient
algorithm for fast large image, low object density, low memory footprint
segmentation. I have found dozens of links to segmentation algorithms, but
since this is a tight scheduled real life project, I don't have the time to
read them all.

That said, using an image size index buffer is not catastrophic. The
dangerous part is asking the system for such a big chunk of memory, but
since the images have a constant size, I could reuse the buffer for the
lifetime of the application. It's just not the optimal solution.
I think I will work a few hours more with my two-line buffer algorithm and
if it fails, use a big buffer algorithm.

Soren

.