How to determine regions of pixels with a shared v

Question

I need to divide an image to regions of pixels whose RGB value pass a certain test.
I'm OK with scanning the image and checking each pixel's value however the part of clustering them into regions and then getting those regions coordinates (x, y, width, height) leaves me in total dark :)
here's the code I have so far

from PIL import Image

def detectRedRegions(PILImage):
      image = PILImage.load()
      width, height = PILImage.size
      reds = []
      h = 0
      while h < height:
        w = 0
        while w < width:
          px = image[w, h]
          if is_red(px):
            reds.append([w, h])
            # Here's where I'm being clueless 
          w +=1
        h +=1

I read tons about clustering but just can't wrap my head around this subject any code example s that will fit my needs will be great (and hopefully enlightening

Thanks!

Answer 1

What you want is called area labeling or connected component detection in image processing. There is an implementation provided in the scipy.ndimage package. So the following should work provided you have numpy + scipy installed

import numpy as np
import scipy.ndimage as ndi
import Image

image = Image.load()
# convert to numpy array (no data copy done since both use buffer protocol)
image = np.asarray(image)
# generate a black and white image marking red pixels as 1
bw = is_red(image)
# labeling : each region is associated with an int
labels, n = ndi.label(bw)
# provide bounding box for each region in the form of tuples of slices
objects = ndi.find_objects(labels)

Answer 2

[EDIT]

While the solution below works, it can be made better. Here is a version with better names and better performance:

from itertools import product
from PIL import Image, ImageDraw


def closed_regions(image, test):
    """
    Return all closed regions in image who's pixels satisfy test.
    """
    pixel = image.load()
    xs, ys = map(xrange, image.size)
    neighbors = dict((xy, set([xy])) for xy in product(xs, ys) if test(pixel[xy]))
    for a, b in neighbors:
        for cd in (a + 1, b), (a, b + 1):
            if cd in neighbors:
                neighbors[a, b].add(cd)
                neighbors[cd].add((a, b))
    seen = set()
    def component(node, neighbors=neighbors, seen=seen, see=seen.add):
        todo = set([node])
        next_todo = todo.pop
        while todo:
            node = next_todo()
            see(node)
            todo |= neighbors[node] - seen
            yield node
    return (set(component(node)) for node in neighbors if node not in seen)


def boundingbox(coordinates):
    """
    Return the bounding box that contains all coordinates.
    """
    xs, ys = zip(*coordinates)
    return min(xs), min(ys), max(xs), max(ys)


def is_black_enough(pixel):
    r, g, b = pixel
    return r < 10 and g < 10 and b < 10


if __name__ == '__main__':

    image = Image.open('some_image.jpg')
    draw = ImageDraw.Draw(image)
    for rect in disjoint_areas(image, is_black_enough):
        draw.rectangle(boundingbox(region), outline=(255, 0, 0))
    image.show()

Unlike disjoint_areas() below, closed_regions() returns sets of pixel coordinates instead of their bounding boxes.

Also, if we use flooding instead of the connected components algorithm, we can make it even simpler and about twice as fast:

from itertools import chain, product
from PIL import Image, ImageDraw


flatten = chain.from_iterable


def closed_regions(image, test):
    """
    Return all closed regions in image who's pixel satisfy test.
    """
    pixel = image.load()
    xs, ys = map(xrange, image.size)
    todo = set(xy for xy in product(xs, ys) if test(pixel[xy]))
    while todo:
        region = set()
        edge = set([todo.pop()])
        while edge:
            region |= edge
            todo -= edge
            edge = todo.intersection(
                flatten(((x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)) for x, y in edge))
        yield region

# rest like above

It was inspired by Eric S. Raymond's version of floodfill.

[/EDIT]

One could probably use floodfill, but I like this:

from collections import defaultdict
from PIL import Image, ImageDraw


def connected_components(edges):
    """
    Given a graph represented by edges (i.e. pairs of nodes), generate its
    connected components as sets of nodes.

    Time complexity is linear with respect to the number of edges.
    """
    neighbors = defaultdict(set)
    for a, b in edges:
        neighbors[a].add(b)
        neighbors[b].add(a)
    seen = set()
    def component(node, neighbors=neighbors, seen=seen, see=seen.add):
        unseen = set([node])
        next_unseen = unseen.pop
        while unseen:
            node = next_unseen()
            see(node)
            unseen |= neighbors[node] - seen
            yield node
    return (set(component(node)) for node in neighbors if node not in seen)


def matching_pixels(image, test):
    """
    Generate all pixel coordinates where pixel satisfies test.
    """
    width, height = image.size
    pixels = image.load()
    for x in xrange(width):
        for y in xrange(height):
            if test(pixels[x, y]):
                yield x, y


def make_edges(coordinates):
    """
    Generate all pairs of neighboring pixel coordinates.
    """
    coordinates = set(coordinates)
    for x, y in coordinates:
        if (x - 1, y - 1) in coordinates:
            yield (x, y), (x - 1, y - 1)
        if (x, y - 1) in coordinates:
            yield (x, y), (x, y - 1)
        if (x + 1, y - 1) in coordinates:
            yield (x, y), (x + 1, y - 1)
        if (x - 1, y) in coordinates:
            yield (x, y), (x - 1, y)
        yield (x, y), (x, y)


def boundingbox(coordinates):
    """
    Return the bounding box of all coordinates.
    """
    xs, ys = zip(*coordinates)
    return min(xs), min(ys), max(xs), max(ys)


def disjoint_areas(image, test):
    """
    Return the bounding boxes of all non-consecutive areas
    who's pixels satisfy test.
    """
    for each in connected_components(make_edges(matching_pixels(image, test))):
        yield boundingbox(each)


def is_black_enough(pixel):
    r, g, b = pixel
    return r < 10 and g < 10 and b < 10


if __name__ == '__main__':

    image = Image.open('some_image.jpg')
    draw = ImageDraw.Draw(image)
    for rect in disjoint_areas(image, is_black_enough):
        draw.rectangle(rect, outline=(255, 0, 0))
    image.show()

Here, pairs of neighboring pixels that both satisfy is_black_enough() are interpreted as edges in a graph. Also, every pixel is viewed as its own neighbor. Due to this re-interpretation we can use the connected component algorithm for graphs which is quite easy to implement. The result is the sequence of the bounding boxes of all areas who's pixels satisfy is_black_enough().