Python: Slice a 2d array into tiles

Question

Hi

I have a raw data file which I read into a byte buffer (a python string). Each data value represents an 8bit pixel of a 2d array representing an image. I know the width and height of this image.

I would like to split the image into tiles so that each tiles area must be larger than a 'min tile area' (eg 1024 bytes) and smaller than 'max tile area(eg 2048 bytes). The height and width of these tiles is arbirary as long as the area constraints are met, and the tiles need not all be the same size. Also the size/length of the input data is not guaranteed to be a power of two.

Whats the best way of doing this in python

Regards

Answer 1

If you're working with images you should use PIL (Python Imaging Library). Then you just load the image:

import Image
i = Image.open(imagefile)

and the you can easily crop a region of arbitrary size:

box = (FirstCornerX, FirstCornerY, SecondCornerX, SecondCornerY)
region = im.crop(box)

so you can work with it. You can also convert between Image object and 2d arrays but I don't quite remember how it was done. I had a couple functions to transform both ways between images an numpy arrays, I'll see if I can find them.

Also, you may want to look at the PIL handbook to find documentation and recipes for working with images.

Answer 2

As you give no indication of the meaning of "best", I will suppose that it means "with the less cluttered code".

Let's say you have the following data:

from collections import Sequence
import operator

assert(type(MIN_AREA) is int)
assert(type(MAX_AREA) is int)
assert(type(width) is int)
assert(type(height) is int)
assert(instanceof(data, Sequence))
assert(len(data) == width * height)
assert(MAX_AREA >= 2 * MIN_AREA)

(The condition on the MIN and MAX areas is necessary for this to work)

There is some cases in which this can't be done with any algorithm, for instance splitting a 3x3 image in tiles of between 4 and 8.

Suppose the data is stored by rows (like in PNM specification for instance).

def split_(seq, size):
    return [seq[i:i+size] for i in range(0,len(seq),size)]

tiles = list()
if width >= MIN_AREA:
    # each row is subdivided into multiple tiles
    tile_width = width / (width / MIN_AREA) # integral division
    rows = split_(data, width)
    row_tiles = [split_(row, tile_width) for row in rows]
    tiles = reduce(operator.add, row_tiles)
elif width < MIN_AREA:
    # each tile is composed of rows
    min_tile_height = int(MIN_AREA / width) + 1
    tile_height = height / (height / min_tile_height)
    tile_size = tile_height * width
    tiles = split_(data, tile_size)
    if len(tiles[-1]) < MIN_AREA:
        if (tile_height > 2):
            tiles[-2] += tiles[-1]
            del tiles[-1]
        else: # tile_height == 2, the case 1 don't pass here
            # special case, we need to split vertically the last three rows
            # if the width was 3 too we have a problem but then if we are here
            # then MIN_AREA was 4, and MAX_AREA was 8, and the rows are >= 5
            if width > 3:
                last_three_rows = split_(tiles[-2] + tiles[-1], width)
                tiles[-2] = reduce(operator.add,[row[:width/2] for row in last_three_rows])
                tiles[-1] = reduce(operator.add,[row[width/2:] for row in last_three_rows])
            else: # width = 3 and MIN_AREA = 4
                last_five_rows = reduce(operator.add, tiles[-3:])
                three_columns = [last_five_rows[i::3] for i in range(3)]
                tiles[-3:] = three_columns

Just remember that in the last cases you get two or three tiles side-by-side, and all the others are stacked above them (or below, depending on where is row '0').

If you need to store more than the raw pixel data, just adjust the tile creation process.