gif encoder inspired by /DavidBuchanan314/gif-enc

gif.py

from struct import pack
from random import sample

dist = lambda a, b: (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 + (a[2] - b[2]) ** 2
nn = lambda rgb, centers: min((dist(rgb, c), i) for i, c in enumerate(centers))[1]

class GIF(object):
    def __init__(self, data, size):
        self.size = size
        self.data = data

    def kmeans(self, K=32):
        centers = []
        for i in xrange(3):
            centers.extend(sample(self.data, K - len(centers)))
            clusters = {}
            for rgb in self.data:
                clusters.setdefault(nn(rgb, centers), []).append(rgb)
            centers = [tuple(sum(col) / len(cluster) for col in zip(*cluster))
                for cluster in sorted(clusters.values(), key=lambda x: -len(x))]
        return centers

    def quantize(self, palette):
        data = self.data[:]
        w, h = self.size
        for y in xrange(h):
            for x in xrange(w):
                idx = nn(data[y * w + x], palette)
                err = [a - b for a, b in zip(data[y * w + x], palette[idx])]
                data[y * w + x] = idx
                for dx, dy, c in [(1, 0, 7), (-1, 1, 3), (0, 1, 5), (1, 1, 1)]:
                    xn, yn = x + dx, y + dy
                    if 0 <= xn < w and yn < h:
                        data[yn * w + xn] = [a + b * c / 16
                            for a, b in zip(data[yn * w + xn], err)]
        return data

    def save(self, fh, quantized, palette):
        w, h = self.size
        palette = sum(map(list, palette), [])
        palette.extend([0] * (384 - len(palette)))

        buf = 'GIF89a'
        buf += pack('<HHBBB', w, h, 0b11110110, 0, 0)
        buf += ''.join(map(chr, palette))
        buf += pack('<BHHHHB', 0x2C, 0, 0, w, h, 0)
        buf += '\x07'

        S = 126
        for i in xrange(len(quantized) / S + 1):
            chunk = [0x80] + quantized[i * S: i * S + S]
            buf += chr(len(chunk))
            buf += ''.join(map(chr, chunk))

        buf += '\x01\x81\x00\x3b'
        fh.write(buf)

test.py

from PIL import Image

img = Image.open('../cat.png')
data = list(img.getdata())

width, height = img.size

from gif import GIF
gif = GIF(data, (width, height))

palette = gif.kmeans()
quantized = gif.quantize(palette)
gif.save(open('/var/www/output.gif', 'w'), quantized, palette)

outp = sum(map(list, palette), [])
outp.extend([0] * (768 - len(outp)))

output = Image.new(mode='P', size=(width, height))
output.putdata(data)
output.putpalette(outp)

output.save('/var/www/output.bmp')