full-color GIF fancy

#!/usr/bin/env python2

import sys
import os.path
from PIL import Image
from random import shuffle

# Color difference metric: sum of squares of channel differences
def diff((r,g,b), (R,G,B)):
    return (r - R)**2 + (g - G)**2 + (b - B)**2

# Get the input file path:
_,path = sys.argv
root, _ = os.path.splitext(path)

# Open input image:
img = Image.open(path)
dat = img.getdata()
w,h = img.size
col = list(set(dat))
shuffle(col)
rev = dict((rgb,i) for (i, rgb) in enumerate(col))
idx = [ rev[rgb] for rgb in dat ]
apr = [ 0 ] *len(col)

# Generate a list of output images:
out = Image.new('P', img.size)
nfr = (len(col) + 253)//255
opt = {}
for frame in range(nfr):
    start = 255*frame + 1
    end   = min(start + 255, len(col))
    for i in range(start, end):
        apr[i] = i
        if frame < 1:  # number of frames to approximate all pixels
            for j in range(end, len(col)):
                if diff(col[i], col[j]) < diff(col[apr[j]], col[j]):
                    apr[j] = i
    out.putpalette(sum(col[start - 1:end], tuple()))
    out.putdata([ 0 if apr[i] < start else 1 + apr[i] - start for i in idx ])
    out.save('%s-%04d.gif' % (root, frame), **opt)
    opt['transparency'] = 0  # all frames except the first use transparency

# Since PIL doesn't support creating multi-frame GIF files, the resulting
# files must be converted with another tool.  I used gifsicle.