[Image-SIG] An algorithm to find connected groups of pixels

[jcupitt at gmail.com]

Hi Jeff,

On 9/27/07, Jeffrey Wise <jefflwise at verizon.net> wrote:
> I've gotten to the point in my image analysis that I need to find all the
> groups of connected pixels in an image.  These groups form arbitrary shapes
> in the image.  I want to preserve the shape information for each group, so I
> can compare/analyze/categorize... it later.

This is usually done with chain codes. Use a filter (and morphology?)
and a threshold to turn your image into a set of edges, then search
for part of the edge and trace around it, recording up/down/left/right
movements. Once you have the boundary as a set of lines it's easy to
calculate things like area and principal axis.

> check in every direction about it for a neighbor that is 255 too.  The
> algorithm would presumably recurse to find neighbors of the neighbor, etc.
> I suspect the trick in this algorithm is the data structures needed to keep
> track of the discovered adjacencies.  I have loaded the image into the 2D

This sounds very like a flood-fill. You'll find if you recurse for
each connection you will use huge amounts of stack. It's usually
better to keep a list of candidates for later testing and iterate
rather then recurse.

You can also do it a line at a time rather than a point at a time.
Write a function to fill to the right or left until it hits an edge,
then add the point below to your undone list. You need much less
memory and it'll run a lot quicker.

But chain codes are probably a better bet.

John