# HG changeset patch # User Paul Boddie # Date 1443629987 -7200 # Node ID 99d5a002b1ce54b1e6ea56cc611437bce52b7bf6 # Parent 783e5bbb92a5c0a5b2467a1fc9c9b63bfb00ecbd Changed the approach, introducing dithering with the "vertex colours" and a halftoning algorithm first, then choosing the most used four colours on each row, assigning the nearest of these colours to any other colours used. diff -r 783e5bbb92a5 -r 99d5a002b1ce optimiser.py --- a/optimiser.py Fri Sep 18 13:55:41 2015 +0200 +++ b/optimiser.py Wed Sep 30 18:19:47 2015 +0200 @@ -1,71 +1,89 @@ #!/usr/bin/env python -from array import array from itertools import combinations +from random import randint import EXIF import PIL.Image +import math import sys -def scale(v): - return (v + 43) / 85 - -def point(rgb): - return tuple(map(scale, rgb)) - -def index(p): - return p[0] * 16 + p[1] * 4 + p[2] - -def colour(i): - return (255 * (i % 2), 255 * ((i / 2) % 2), 255 * ((i / 4) % 2)) - -def add(d, v): - d[v] = (d.has_key(v) and d[v] or 0) + 1 - -def by_frequency(d): - l = [(f, t) for (t, f) in d.items()] - l.sort(reverse=True) - return [i[1] for i in l] - -def match(b, bases): - return b in bases and b - -def fallback(bases): - for b in by_frequency(bases): - if b not in ["_", "W"]: - return b - return by_frequency(bases)[0] - -tones = [ - "___", "_BB", "_BB", "BBB", # 00x - "_GG", "__C", "_BC", "BCC", # 01x - "_GG", "GGC", "BCW", "CCC", # 02x - "GGG", "GGC", "GCW", "CCW", # 03x - "_RR", "_MM", "BMM", "MBB", # 10x - "_YY", "_**", "**B", "BBC", # 11x - "_GY", "GGC", "*CC", "BCW", # 12x - "BGY", "GGC", "CCW", "CCW", # 13x - "_RR", "_RM", "*MM", "RMM", # 20x - "RYY", "*RY", "RMM", "MMM", # 21x - "YYY", "YYW", "*WW", "*WW", # 22x - "YYY", "GYY", "GWW", "CWW", # 23x - "RRR", "RRM", "BMR", "BMR", # 30x - "RRY", "RRY", "RMW", "RMW", # 31x - "YYY", "YYW", "YYW", "WWW", # 32x - "YYY", "YYW", "YYW", "WWW", # 33x +corners = [ + (0, 0, 0), (255, 0, 0), (0, 255, 0), (255, 255, 0), + (0, 0, 255), (255, 0, 255), (0, 255, 255), (255, 255, 255) ] -colours = ["_", "R", "G", "Y", "B", "M", "C", "W"] +def distance(rgb1, rgb2): + r1, g1, b1 = rgb1 + r2, g2, b2 = rgb2 + return math.sqrt(pow(r1 - r2, 2) + pow(g1 - g2, 2) + pow(b1 - b2, 2)) + +def brightness(rgb): + return distance(rgb, (0, 0, 0)) -if __name__ == "__main__": - width = 320 - height = 256 +def factor(start, end, rgb): + r1, g1, b1 = start + r2, g2, b2 = end + gr, gg, gb = r2 - r1, g2 - g1, b2 - b1 + r, g, b = rgb + pr, pg, pb = r - r1, g - g1, b - b1 + dp = pr * gr + pg * gg + pb * gb + return dp / pow(distance(start, end), 2) + +def darklight(rgb1, rgb2): + if brightness(rgb1) <= brightness(rgb2): + return rgb1, rgb2 + else: + return rgb2, rgb1 + +def nearest(rgb, values=None): + l = map(lambda c: (distance(rgb, c), c), values or corners) + l.sort() + return l - input_filename, output_filename = sys.argv[1:3] - rotate = "-r" in sys.argv[3:] +def pattern(rgb): + l = nearest(rgb) + start, end = l[0][1], l[1][1] + f = factor(start, end, rgb) + #if f > 0.5: + # start, end = end, start + # f = 1 - f + return start, end, f + +def choose(seq, f): + last = int(seq * math.sqrt(f)) + current = int((seq + 1) * math.sqrt(f)) + return last != current + +def get_value(xy, rgb, width, height): + x, y = xy + rgb1, rgb2, f = pattern(rgb) + if choose(x + randint(0, width), f) and choose(y + randint(0, height), f): + return rgb2 + else: + return rgb1 - x = EXIF.process_file(open(input_filename)) - im = PIL.Image.open(input_filename) +def get_best(rgb, values): + return nearest(rgb, values)[0][1] +def test(): + size = 512 + for r in (0, 63, 127, 191, 255): + im = PIL.Image.new("RGB", (size, size)) + for g in range(0, size): + for b in range(0, size): + value = get_value((g, b), (r, (g * 256) / size, (b * 256 / size)), size, size) + im.putpixel((g, b), value) + im.save("rgb%d.png" % r) + +def test_flat(rgb): + size = 64 + im = PIL.Image.new("RGB", (size, size)) + for y in range(0, size): + for x in range(0, size): + im.putpixel((x, y), get_value((x, y), rgb, size, size)) + im.save("rgb%02d%02d%02d.png" % rgb) + +def rotate_and_scale(im, width, height, rotate): if rotate or x and x["Image Orientation"].values == [6L]: im = im.rotate(270) @@ -75,79 +93,55 @@ else: width = (height * w) / h - im = im.resize((width, height)) + return im.resize((width, height)) - usage = [] - base_usage = [] - toned = [] +if __name__ == "__main__": + if "--test" in sys.argv: + test() + sys.exit(0) + elif "--test-flat" in sys.argv: + test_flat((120, 40, 60)) + sys.exit(0) - for row in range(0, height): - u = {} - usage.append(u) - bu = {} - base_usage.append(bu) - tr = [] - toned.append(tr) - for column in range(0, width): - rgb = im.getpixel((column, row)) - p = point(rgb) - i = index(p) - t = tones[i] - add(u, t) - if t[0] != "*": - add(bu, t[0]) - if t[1] != "*": - add(bu, t[1]) - if t[2] != "*": - add(bu, t[2]) - tr.append(t) + width = 320 + height = 256 + + input_filename, output_filename = sys.argv[1:3] + rotate = "-r" in sys.argv[3:] - chosen = [] + x = EXIF.process_file(open(input_filename)) + im = PIL.Image.open(input_filename) + im = rotate_and_scale(im, width, height, rotate) - for row, (u, bu) in enumerate(zip(usage, base_usage)): - light = row % 2 - best = 0 - best_bases = None - best_missing = None - best_map = None + width, height = im.size + + colours = [] - for bases in combinations(bu, min(len(bu), 4)): - bases = dict([(base, bu[base]) for base in bases]) - count = 0 - missing = [] - tone_map = {} - for tone, freq in u.items(): - base = match(tone[1], bases) - if base: - tone_map[tone] = base - count += freq - else: - base = light and match(tone[2], bases) or match(tone[0], bases) or match(tone[2], bases) - if base: - tone_map[tone] = base - count += freq / 2 - else: - missing.append(tone) - if count > best: - best_bases = bases - best_missing = missing - best_map = tone_map - best = count + for y in range(0, height): + c = {} + for x in range(0, width): + rgb = im.getpixel((x, y)) + value = get_value((x, y), rgb, width, height) + im.putpixel((x, y), value) + if not c.has_key(value): + c[value] = 1 + else: + c[value] += 1 + c = [(n, value) for value, n in c.items()] + c.sort(reverse=True) + colours.append(c) - chosen.append((best, best_bases or bases, best_map or tone_map, best_missing or missing)) - - output = [] + for y, c in enumerate(colours): + if len(c) <= 4: + continue + most = [value for n, value in c[:4]] + least = [value for n, value in c[4:]] - for row, (tr, ch) in enumerate(zip(toned, chosen)): - o = [] - for column, t in enumerate(tr): - best, bases, tone_map, missing = ch - base = tone_map.get(t) or fallback(bases) - o.append(base) - i = colours.index(base) - im.putpixel((column, row), colour(i)) - - output.append("".join(o)) + for x in range(0, width): + rgb = im.getpixel((x, y)) + if rgb in least: + value = get_best(rgb, most) + im.putpixel((x, y), value) im.save(output_filename)