The tokumaru reduction

reduce.py

import sys
from PIL import Image

# attempts to convert an image into a format that makes the most of the Sega Genesis graphics hardware
# i.e. 64 colours organized into 4 16-colour palettes, with each 8x8 tile using one palette
# based on an algorithm described by tokumaru on the NESdev forums
# see here: http://forums.nesdev.com/viewtopic.php?f=23&t=14073

BLOCK_SIZE = 8
PALETTE_COUNT = 4
COLOURS_PER_PALETTE = 16

f = Image.open(sys.argv[1])
w, h = f.size

# shrink the image down to one pixel per tile; each pixel is the average colour of the tile
w_r, h_r = w/BLOCK_SIZE,h/BLOCK_SIZE
resized = f.resize((w_r,h_r), Image.BILINEAR)

# reduce the number of colours to the number of palettes;
# pixels that now match colour should correspond to tiles that match palettes
blocks = resized.convert("P", palette = Image.ADAPTIVE, colors = PALETTE_COUNT)

# organize the tiles by palette into separate buckets
buckets = [[] for i in range(PALETTE_COUNT)]
for i, bucket in enumerate(blocks.getdata()):
	row = i/w_r
	col = i%w_r
	tile = f.crop((col * BLOCK_SIZE, row * BLOCK_SIZE,
                 col * BLOCK_SIZE + BLOCK_SIZE, row * BLOCK_SIZE + BLOCK_SIZE))
	buckets[bucket].append(tile)

# construct an image for each bucket containing all of its tiles
tilestrips = [Image.new("RGB", (len(bucket) * BLOCK_SIZE, BLOCK_SIZE)) for bucket in buckets]
for i, bucket in enumerate(buckets):
	for j, image in enumerate(bucket):
		tilestrips[i].paste(image, (j * BLOCK_SIZE, 0))

# find the palette for each bucket
reduced_tilestrips = [tilestrip.convert("P", palette = Image.ADAPTIVE, colors = COLOURS_PER_PALETTE)
                      for tilestrip in tilestrips]

# reconstruct the image by copying the tiles back
reconstructed = Image.new("RGB", (w, h))
current_tile = [0,0,0,0]
for i, block in enumerate(blocks.getdata()):
	row = i/w_r
	col = i%w_r
  offset = current_tile[block] * 8
	tile = reduced_tilestrips[block].crop((offset, 0, offset + 8, 8))
	reconstructed.paste(tile, (col * 8, row * 8))
	current_tile[block] += 1
reconstructed.save(sys.argv[2])

pedants will note that this doesn't quite get you down to the Sega Genesis level, where palette entry 0 is shared and palette entries are 9-bit, not 24-bit.