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

[Douglas Bagnall]

Jeffrey Wise wrote:

> I'm in my first week with PIL and doing well - it's a tremendous library!
> 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.  
> 
> The image is composed of pixels of value 0 or 255 in "L" B&W format.  I
> assume such an algorithm will need to find a pixel of value 255 and then
> 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
> array-like accessor, so I have free access to each pixel.

That's more or less floodfill, as John Cupitt said, and would look
something like this:

http://mail.python.org/pipermail/image-sig/2005-September/003559.html

There's a version of it at the bottom of ImageDraw.py in 1.1.6.

You'll presumably want to change the innermost bit from changing the
colour to shifting the shape onto another image, or something.


douglas