PySide: Separating a spritesheet / Separating an i

I'm working on a program in which I need to separate spritesheets, or in other words, separate an image into contiguous regions of color.

I've never done any image processing before, so I'm wondering how I would go about this. What would I do after I test for pixel color? What's the best way to determine which pixel goes with each sprite?

All the input images have uniform backgrounds, and an alpha channel different from that of the background counts as color. The order of the output images needs to be left-right, up-down. My project is written in PySide, so I'm hoping to use it for this task too, but I could import more libraries if necessary.

Thanks your replies!

P.S.: I'm not sure if the PySide tag is appropriate or not, since I'm using PySide, but the question doesn't involve the GUI aspects of it. If a mod feels it doesn't belong, feel free to remove it.

For example, I have a spritesheet that looks like this:

I want to separate it into these:

That sounds like something that should be implemented in anything that deals with sprites, but here we will implement our own sprite-spliter.

The first thing we need here is to extract the individual objects. In this situation, it is only a matter of deciding whether a pixel is a background one or not. If we assume the point at origin is a background pixel, then we are done:

from PIL import Image

def sprite_mask(img, bg_point=(0, 0)):
    width, height = img.size
    im = img.load()

    bg = im[bg_point]
    mask_img = Image.new('L', img.size)
    mask = mask_img.load()
    for x in xrange(width):
        for y in xrange(height):
            if im[x, y] != bg:
                mask[x, y] = 255
    return mask_img, bg

If you save the mask image created above and open it, here is what you would see on it (I added a rectangle inside your empty window):

With the image above, the next thing we need is to fill its holes if we want to join sprites that are inside others (like the rectangle added, see figure above). This is another simple rule: if a point cannot be reached from the point at [0, 0], then it is a hole and it must be filled. All that is left is then separating each sprite in individual images. This is done by connected component labeling. For each component we get its axis-aligned bounding box in order to define the dimensions of the piece, and then we copy from the original image the points that belong to a given component. To keep it short, the following code uses scipy for these tasks:

import sys
import numpy
from scipy.ndimage import label, morphology

def split_sprite(img, mask, bg, join_interior=True, basename='sprite_%d.png'):
    im = img.load()

    m = numpy.array(mask, dtype=numpy.uint8)
    if join_interior:
        m = morphology.binary_fill_holes(m)
    lbl, ncc = label(m, numpy.ones((3, 3)))

    for i in xrange(1, ncc + 1):
        px, py = numpy.nonzero(lbl == i)
        xmin, xmax, ymin, ymax = px.min(), px.max(), py.min(), py.max()

        sprite = Image.new(img.mode, (ymax - ymin + 1, xmax - xmin + 1), bg)
        sp = sprite.load()
        for x, y in zip(px, py):
            x, y = int(x), int(y)
            sp[y - int(ymin), x - int(xmin)] = im[y, x]

        name = basename % i
        sprite.save(name)
        print "Wrote %s" % name

sprite = Image.open(sys.argv[1])
mask, bg = sprite_mask(sprite)
split_sprite(sprite, mask, bg)

Now you have all the pieces (sprite_1.png, sprite_2.png, ..., sprite_8.png) exactly as you included in the question.