# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1443806537 -7200
# Node ID 21c5d47536ea23890c1fd87bd197e47c293eec60
# Parent  736979f993792736a288b559217ebfd96474aaf8
Added experiments with PIL's dithering/quantizing, summing colour probabilities,
finding the "best" combinations where more than four colours are required.
Removed the preview image saving.

diff -r 736979f99379 -r 21c5d47536ea dither.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dither.py	Fri Oct 02 19:22:17 2015 +0200
@@ -0,0 +1,24 @@
+#!/usr/bin/env python
+
+import PIL.Image
+import sys
+
+def get_palette():
+    l = []
+    for i in range(0, 8):
+        r = ((i / 4) % 2) * 255; g = ((i / 2) % 2) * 255; b = (i % 2) * 255
+        for j in range(0, 32):
+            l.extend((r, g, b))
+
+    imp = PIL.Image.new("P", (1, 1))
+    imp.putpalette(l)
+    return imp
+
+def dither(im, imp=None):
+    return im.quantize(palette=imp or get_palette())
+
+im = PIL.Image.open(sys.argv[1])
+im2 = dither(im)
+im2.save(sys.argv[2])
+
+# vim: tabstop=4 expandtab shiftwidth=4
diff -r 736979f99379 -r 21c5d47536ea optimiser.py
--- a/optimiser.py	Fri Oct 02 13:37:29 2015 +0200
+++ b/optimiser.py	Fri Oct 02 19:22:17 2015 +0200
@@ -1,9 +1,11 @@
 #!/usr/bin/env python
 
+from dither import dither
 from random import random
-from os.path import extsep, splitext
+from os.path import splitext
 import EXIF
 import PIL.Image
+import itertools
 import math
 import sys
 
@@ -17,10 +19,10 @@
     r2, g2, b2 = rgb2
     return math.sqrt(pow(r1 - r2, 2) + pow(g1 - g2, 2) + pow(b1 - b2, 2))
 
-def distribution(rgb, points):
+def distribution(rgb, values=None):
     l = []
     total = 0
-    for c in points:
+    for c in values or corners:
         d = distance(rgb, c)
         if d == 0:
             return [(1, c)]
@@ -51,6 +53,22 @@
 def saturate_value(x, exp):
     return int(127.5 + sign(x - 127.5) * 127.5 * pow(abs(x - 127.5) / 127.5, exp))
 
+def get_best(im, width, y, colours):
+    best = 0
+    best_values = None
+
+    for values in itertools.combinations([value for n, value in colours], 4):
+        current = 0
+        for x in range(0, width):
+            rgb = im.getpixel((x, y))
+            for f, value in distribution(rgb, values):
+                current += f
+        if current >= best:
+            best_values = values
+            best = current
+
+    return best_values
+
 def test():
     size = 512
     for r in (0, 63, 127, 191, 255):
@@ -94,21 +112,23 @@
 
     input_filename, output_filename = sys.argv[1:3]
     basename, ext = splitext(output_filename)
-    preview_filename = extsep.join([basename + "_preview", ext])
 
-    preview = "-p" in sys.argv[3:]
     rotate = "-r" in sys.argv[3:]
     saturate = sys.argv[3:].count("-s")
     desaturate = sys.argv[3:].count("-d")
+    best = "-b" in sys.argv[3:]
+    dithering = "-d" in sys.argv[3:]
 
     x = EXIF.process_file(open(input_filename))
     im = PIL.Image.open(input_filename).convert("RGB")
     im = rotate_and_scale(im, width, height, rotate)
 
-    if preview:
-        im_preview = im.copy()
+    width, height = im.size
 
-    width, height = im.size
+    im_original = im
+
+    if dithering:
+        im = dither(im).convert("RGB")
 
     colours = []
 
@@ -123,28 +143,25 @@
                 rgb = saturate_rgb(rgb, saturate and math.pow(0.5, saturate) or math.pow(2, desaturate))
                 im.putpixel((x, y), rgb)
 
-            # Count the number of requested colours.
+            # Sum the colour probabilities.
 
-            value = get_value(rgb)
-            if not c.has_key(value):
-                c[value] = 1
-            else:
-                c[value] += 1
-
-            if preview:
-                im_preview.putpixel((x, y), value)
+            for f, value in distribution(rgb):
+                if not c.has_key(value):
+                    c[value] = f
+                else:
+                    c[value] += f
 
         c = [(n, value) for value, n in c.items()]
         c.sort(reverse=True)
         colours.append(c)
 
-    if preview:
-        im_preview.save(preview_filename)
-
     for y, c in enumerate(colours):
         most = [value for n, value in c[:4]]
         least = [value for n, value in c[4:]]
 
+        if least and best:
+            most = get_best(im_original, width, y, c)
+
         for x in range(0, width):
             rgb = im.getpixel((x, y))
 
@@ -153,7 +170,9 @@
 
             value = get_value(rgb)
             if value in least:
+                rgb = im_original.getpixel((x, y))
                 value = get_value(rgb, most)
+
             im.putpixel((x, y), value)
 
     im.save(output_filename)