PaletteOptimiser

Changeset

113:939b08faaf93
2015-10-11 Paul Boddie raw files shortlog changelog graph Made a new module for a similar separation of concerns to the Shedskin version. simpleimage
optimiser.py (file) optimiserlib.py (file)
     1.1 --- a/optimiser.py	Sun Oct 11 18:50:55 2015 +0200
     1.2 +++ b/optimiser.py	Sun Oct 11 20:07:05 2015 +0200
     1.3 @@ -20,202 +20,12 @@
     1.4  with this program.  If not, see <http://www.gnu.org/licenses/>.
     1.5  """
     1.6  
     1.7 -from random import random, randrange
     1.8 +from optimiserlib import *
     1.9  from os.path import split, splitext
    1.10  import EXIF
    1.11  import PIL.Image
    1.12 -import itertools
    1.13  import sys
    1.14  
    1.15 -corners = [
    1.16 -    (0, 0, 0), (255, 0, 0), (0, 255, 0), (255, 255, 0),
    1.17 -    (0, 0, 255), (255, 0, 255), (0, 255, 255), (255, 255, 255)
    1.18 -    ]
    1.19 -
    1.20 -# Basic colour operations.
    1.21 -
    1.22 -def within(v, lower, upper):
    1.23 -    return min(max(v, lower), upper)
    1.24 -
    1.25 -def clip(v):
    1.26 -    return int(within(v, 0, 255))
    1.27 -
    1.28 -def restore(srgb):
    1.29 -    r, g, b = srgb
    1.30 -    return int(r * 255.0), int(g * 255.0), int(b * 255.0)
    1.31 -
    1.32 -def scale(rgb):
    1.33 -    r, g, b = rgb
    1.34 -    return r / 255.0, g / 255.0, b / 255.0
    1.35 -
    1.36 -def invert(srgb):
    1.37 -    r, g, b = srgb
    1.38 -    return 1.0 - r, 1.0 - g, 1.0 - b
    1.39 -
    1.40 -scaled_corners = map(scale, corners)
    1.41 -zipped_corners = zip(corners, scaled_corners)
    1.42 -
    1.43 -# Colour distribution functions.
    1.44 -
    1.45 -def combination(rgb):
    1.46 -
    1.47 -    "Return the colour distribution for 'rgb'."
    1.48 -
    1.49 -    # Get the colour with components scaled from 0 to 1, plus the inverted
    1.50 -    # component values.
    1.51 -
    1.52 -    srgb = scale(rgb)
    1.53 -    rgbi = invert(srgb)
    1.54 -    pairs = zip(rgbi, srgb)
    1.55 -
    1.56 -    # For each corner of the colour cube (primary and secondary colours plus
    1.57 -    # black and white), calculate the corner value's contribution to the
    1.58 -    # input colour.
    1.59 -
    1.60 -    d = []
    1.61 -    for corner, scaled in zipped_corners:
    1.62 -        rs, gs, bs = scaled
    1.63 -
    1.64 -        # Obtain inverted channel values where corner channels are low;
    1.65 -        # obtain original channel values where corner channels are high.
    1.66 -
    1.67 -        d.append((pairs[0][int(rs)] * pairs[1][int(gs)] * pairs[2][int(bs)], corner))
    1.68 -
    1.69 -    # Balance the corner contributions.
    1.70 -
    1.71 -    return balance(d)
    1.72 -
    1.73 -def complements(rgb):
    1.74 -
    1.75 -    "Return 'rgb' and its complement."
    1.76 -
    1.77 -    r, g, b = rgb
    1.78 -    return rgb, restore(invert(scale(rgb)))
    1.79 -
    1.80 -bases = [(0, 0, 0), (255, 0, 0), (0, 255, 0), (0, 0, 255)]
    1.81 -base_complements = map(complements, bases)
    1.82 -
    1.83 -def balance(d):
    1.84 -
    1.85 -    """
    1.86 -    Balance distribution 'd', cancelling opposing values and their complements
    1.87 -    and replacing their common contributions with black and white contributions.
    1.88 -    """
    1.89 -
    1.90 -    d = dict([(value, f) for f, value in d])
    1.91 -    for primary, secondary in base_complements:
    1.92 -        common = min(d[primary], d[secondary])
    1.93 -        d[primary] -= common
    1.94 -        d[secondary] -= common
    1.95 -    return [(f, value) for value, f in d.items()]
    1.96 -
    1.97 -def combine(d):
    1.98 -
    1.99 -    "Combine distribution 'd' to get a colour value."
   1.100 -
   1.101 -    out = [0, 0, 0]
   1.102 -    for v, rgb in d:
   1.103 -        out[0] += v * rgb[0]
   1.104 -        out[1] += v * rgb[1]
   1.105 -        out[2] += v * rgb[2]
   1.106 -    return tuple(map(int, out))
   1.107 -
   1.108 -def pattern(rgb, chosen=None):
   1.109 -
   1.110 -    """
   1.111 -    Obtain a sorted colour distribution for 'rgb', optionally limited to any
   1.112 -    specified 'chosen' colours.
   1.113 -    """
   1.114 -
   1.115 -    l = [(f, value) for f, value in combination(rgb) if not chosen or value in chosen]
   1.116 -    l.sort(reverse=True)
   1.117 -    return l
   1.118 -
   1.119 -def get_value(rgb, chosen=None, fail=False):
   1.120 -
   1.121 -    """
   1.122 -    Get an output colour for 'rgb', optionally limited to any specified 'chosen'
   1.123 -    colours. If 'fail' is set to a true value, return None if the colour cannot
   1.124 -    be expressed using any of the chosen colours.
   1.125 -    """
   1.126 -
   1.127 -    l = pattern(rgb, chosen)
   1.128 -    limit = sum([f for f, c in l])
   1.129 -    if not limit:
   1.130 -        if fail:
   1.131 -            return None
   1.132 -        else:
   1.133 -            return l[randrange(0, len(l))][1]
   1.134 -
   1.135 -    choose = random() * limit
   1.136 -    threshold = 0
   1.137 -    for f, c in l:
   1.138 -        threshold += f
   1.139 -        if choose < threshold:
   1.140 -            return c
   1.141 -    return c
   1.142 -
   1.143 -# Colour processing operations.
   1.144 -
   1.145 -def sign(x):
   1.146 -    return x >= 0 and 1 or -1
   1.147 -
   1.148 -def saturate_rgb(rgb, exp):
   1.149 -    r, g, b = rgb
   1.150 -    return saturate_value(r, exp), saturate_value(g, exp), saturate_value(b, exp)
   1.151 -
   1.152 -def saturate_value(x, exp):
   1.153 -    return int(127.5 + sign(x - 127.5) * 127.5 * pow(abs(x - 127.5) / 127.5, exp))
   1.154 -
   1.155 -def amplify_rgb(rgb, exp):
   1.156 -    r, g, b = rgb
   1.157 -    return amplify_value(r, exp), amplify_value(g, exp), amplify_value(b, exp)
   1.158 -
   1.159 -def amplify_value(x, exp):
   1.160 -    return int(pow(x / 255.0, exp) * 255.0)
   1.161 -
   1.162 -# Image operations.
   1.163 -
   1.164 -def get_colours(im, y):
   1.165 -
   1.166 -    "Get a colour distribution from image 'im' for the row 'y'."
   1.167 -
   1.168 -    width, height = im.size
   1.169 -    c = {}
   1.170 -    x = 0
   1.171 -    while x < width:
   1.172 -        rgb = im.getpixel((x, y))
   1.173 -
   1.174 -        # Sum the colour probabilities.
   1.175 -
   1.176 -        for f, value in combination(rgb):
   1.177 -            if not c.has_key(value):
   1.178 -                c[value] = f
   1.179 -            else:
   1.180 -                c[value] += f
   1.181 -
   1.182 -        x += 1
   1.183 -
   1.184 -    d = [(n/width, value) for value, n in c.items()]
   1.185 -    d.sort(reverse=True)
   1.186 -    return d
   1.187 -
   1.188 -def get_combinations(c, n):
   1.189 -
   1.190 -    """
   1.191 -    Get combinations of colours from 'c' of size 'n' in decreasing order of
   1.192 -    probability.
   1.193 -    """
   1.194 -
   1.195 -    all = []
   1.196 -    for l in itertools.combinations(c, n):
   1.197 -        total = 0
   1.198 -        for f, value in l:
   1.199 -            total += f
   1.200 -        all.append((total, l))
   1.201 -    all.sort(reverse=True)
   1.202 -    return [l for total, l in all]
   1.203 -
   1.204  def test():
   1.205  
   1.206      "Generate slices of the colour cube."
   1.207 @@ -264,119 +74,6 @@
   1.208  
   1.209      return im.resize((width, height))
   1.210  
   1.211 -def count_colours(im, colours):
   1.212 -
   1.213 -    """
   1.214 -    Count colours on each row of image 'im', returning a tuple indicating the
   1.215 -    first row with more than the given number of 'colours' together with the
   1.216 -    found colours; otherwise returning None.
   1.217 -    """
   1.218 -
   1.219 -    width, height = im.size
   1.220 -
   1.221 -    y = 0
   1.222 -    while y < height:
   1.223 -        l = set()
   1.224 -        x = 0
   1.225 -        while x < width:
   1.226 -            l.add(im.getpixel((x, y)))
   1.227 -            x += 1
   1.228 -        if len(l) > colours:
   1.229 -            return (y, l)
   1.230 -        y += 1
   1.231 -    return None
   1.232 -
   1.233 -def process_image(pim, saturate, desaturate, darken, brighten):
   1.234 -
   1.235 -    """
   1.236 -    Process image 'pim' using the given options: 'saturate', 'desaturate',
   1.237 -    'darken', 'brighten'.
   1.238 -    """
   1.239 -
   1.240 -    width, height = pim.size
   1.241 -    im = SimpleImage(list(pim.getdata()), pim.size)
   1.242 -
   1.243 -    if saturate or desaturate or darken or brighten:
   1.244 -        y = 0
   1.245 -        while y < height:
   1.246 -            x = 0
   1.247 -            while x < width:
   1.248 -                rgb = im.getpixel((x, y))
   1.249 -                if saturate or desaturate:
   1.250 -                    rgb = saturate_rgb(rgb, saturate and 0.5 / saturate or 2 * desaturate)
   1.251 -                if darken or brighten:
   1.252 -                    rgb = amplify_rgb(rgb, brighten and 0.5 / brighten or 2 * darken)
   1.253 -                im.putpixel((x, y), rgb)
   1.254 -                x += 1
   1.255 -            y += 1
   1.256 -
   1.257 -    pim.putdata(im.getdata())
   1.258 -
   1.259 -def convert_image(pim, colours):
   1.260 -
   1.261 -    "Convert image 'pim' to an appropriate output representation."
   1.262 -
   1.263 -    width, height = pim.size
   1.264 -    im = SimpleImage(list(pim.getdata()), pim.size)
   1.265 -
   1.266 -    y = 0
   1.267 -    while y < height:
   1.268 -        c = get_colours(im, y)
   1.269 -
   1.270 -        suggestions = []
   1.271 -
   1.272 -        for l in get_combinations(c, colours):
   1.273 -            most = [value for f, value in l]
   1.274 -            missing = 0
   1.275 -
   1.276 -            x = 0
   1.277 -            while x < width:
   1.278 -                rgb = im.getpixel((x, y))
   1.279 -                value = get_value(rgb, most, True)
   1.280 -                if value is None:
   1.281 -                    missing += 1
   1.282 -                x += 1
   1.283 -
   1.284 -            if not missing:
   1.285 -                break # use this combination
   1.286 -            suggestions.append((missing, l))
   1.287 -
   1.288 -        # Find the most accurate suggestion.
   1.289 -
   1.290 -        else:
   1.291 -            suggestions.sort()
   1.292 -            most = [value for f, value in suggestions[0][1]] # get the combination
   1.293 -
   1.294 -        x = 0
   1.295 -        while x < width:
   1.296 -            rgb = im.getpixel((x, y))
   1.297 -            value = get_value(rgb, most)
   1.298 -            im.putpixel((x, y), value)
   1.299 -
   1.300 -            if x < width - 1:
   1.301 -                rgbn = im.getpixel((x+1, y))
   1.302 -                rgbn = (
   1.303 -                    clip(rgbn[0] + (rgb[0] - value[0]) / 4.0),
   1.304 -                    clip(rgbn[1] + (rgb[1] - value[1]) / 4.0),
   1.305 -                    clip(rgbn[2] + (rgb[2] - value[2]) / 4.0)
   1.306 -                    )
   1.307 -                im.putpixel((x+1, y), rgbn)
   1.308 -
   1.309 -            if y < height - 1:
   1.310 -                rgbn = im.getpixel((x, y+1))
   1.311 -                rgbn = (
   1.312 -                    clip(rgbn[0] + (rgb[0] - value[0]) / 2.0),
   1.313 -                    clip(rgbn[1] + (rgb[1] - value[1]) / 2.0),
   1.314 -                    clip(rgbn[2] + (rgb[2] - value[2]) / 2.0)
   1.315 -                    )
   1.316 -                im.putpixel((x, y+1), rgbn)
   1.317 -
   1.318 -            x += 1
   1.319 -
   1.320 -        y += 1
   1.321 -
   1.322 -    pim.putdata(im.getdata())
   1.323 -
   1.324  def get_parameter(options, flag, conversion, default, missing):
   1.325  
   1.326      """
   1.327 @@ -395,28 +92,6 @@
   1.328      except ValueError:
   1.329          return missing
   1.330  
   1.331 -class SimpleImage:
   1.332 -
   1.333 -    "An image behaving like PIL.Image."
   1.334 -
   1.335 -    def __init__(self, data, size):
   1.336 -        self.data = data
   1.337 -        self.width, self.height = self.size = size
   1.338 -
   1.339 -    def copy(self):
   1.340 -        return SimpleImage(self.data[:], self.size)
   1.341 -
   1.342 -    def getpixel(self, xy):
   1.343 -        x, y = xy
   1.344 -        return self.data[y * self.width + x]
   1.345 -
   1.346 -    def putpixel(self, xy, value):
   1.347 -        x, y = xy
   1.348 -        self.data[y * self.width + x] = value
   1.349 -
   1.350 -    def getdata(self):
   1.351 -        return self.data
   1.352 -
   1.353  # Main program.
   1.354  
   1.355  if __name__ == "__main__":
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/optimiserlib.py	Sun Oct 11 20:07:05 2015 +0200
     2.3 @@ -0,0 +1,350 @@
     2.4 +#!/usr/bin/env python
     2.5 +
     2.6 +"""
     2.7 +Convert and optimise images for display in an Acorn Electron MODE 1 variant
     2.8 +with four colours per line but eight colours available for selection on each
     2.9 +line.
    2.10 +
    2.11 +Copyright (C) 2015 Paul Boddie <paul@boddie.org.uk>
    2.12 +
    2.13 +This program is free software; you can redistribute it and/or modify it under
    2.14 +the terms of the GNU General Public License as published by the Free Software
    2.15 +Foundation; either version 3 of the License, or (at your option) any later
    2.16 +version.
    2.17 +
    2.18 +This program is distributed in the hope that it will be useful, but WITHOUT ANY
    2.19 +WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
    2.20 +PARTICULAR PURPOSE.  See the GNU General Public License for more details.
    2.21 +
    2.22 +You should have received a copy of the GNU General Public License along
    2.23 +with this program.  If not, see <http://www.gnu.org/licenses/>.
    2.24 +"""
    2.25 +
    2.26 +from random import random, randrange
    2.27 +import itertools
    2.28 +
    2.29 +corners = [
    2.30 +    (0, 0, 0), (255, 0, 0), (0, 255, 0), (255, 255, 0),
    2.31 +    (0, 0, 255), (255, 0, 255), (0, 255, 255), (255, 255, 255)
    2.32 +    ]
    2.33 +
    2.34 +# Basic colour operations.
    2.35 +
    2.36 +def within(v, lower, upper):
    2.37 +    return min(max(v, lower), upper)
    2.38 +
    2.39 +def clip(v):
    2.40 +    return int(within(v, 0, 255))
    2.41 +
    2.42 +def restore(srgb):
    2.43 +    r, g, b = srgb
    2.44 +    return int(r * 255.0), int(g * 255.0), int(b * 255.0)
    2.45 +
    2.46 +def scale(rgb):
    2.47 +    r, g, b = rgb
    2.48 +    return r / 255.0, g / 255.0, b / 255.0
    2.49 +
    2.50 +def invert(srgb):
    2.51 +    r, g, b = srgb
    2.52 +    return 1.0 - r, 1.0 - g, 1.0 - b
    2.53 +
    2.54 +scaled_corners = map(scale, corners)
    2.55 +zipped_corners = zip(corners, scaled_corners)
    2.56 +
    2.57 +# Colour distribution functions.
    2.58 +
    2.59 +def combination(rgb):
    2.60 +
    2.61 +    "Return the colour distribution for 'rgb'."
    2.62 +
    2.63 +    # Get the colour with components scaled from 0 to 1, plus the inverted
    2.64 +    # component values.
    2.65 +
    2.66 +    srgb = scale(rgb)
    2.67 +    rgbi = invert(srgb)
    2.68 +    pairs = zip(rgbi, srgb)
    2.69 +
    2.70 +    # For each corner of the colour cube (primary and secondary colours plus
    2.71 +    # black and white), calculate the corner value's contribution to the
    2.72 +    # input colour.
    2.73 +
    2.74 +    d = []
    2.75 +    for corner, scaled in zipped_corners:
    2.76 +        rs, gs, bs = scaled
    2.77 +
    2.78 +        # Obtain inverted channel values where corner channels are low;
    2.79 +        # obtain original channel values where corner channels are high.
    2.80 +
    2.81 +        d.append((pairs[0][int(rs)] * pairs[1][int(gs)] * pairs[2][int(bs)], corner))
    2.82 +
    2.83 +    # Balance the corner contributions.
    2.84 +
    2.85 +    return balance(d)
    2.86 +
    2.87 +def complements(rgb):
    2.88 +
    2.89 +    "Return 'rgb' and its complement."
    2.90 +
    2.91 +    r, g, b = rgb
    2.92 +    return rgb, restore(invert(scale(rgb)))
    2.93 +
    2.94 +bases = [(0, 0, 0), (255, 0, 0), (0, 255, 0), (0, 0, 255)]
    2.95 +base_complements = map(complements, bases)
    2.96 +
    2.97 +def balance(d):
    2.98 +
    2.99 +    """
   2.100 +    Balance distribution 'd', cancelling opposing values and their complements
   2.101 +    and replacing their common contributions with black and white contributions.
   2.102 +    """
   2.103 +
   2.104 +    d = dict([(value, f) for f, value in d])
   2.105 +    for primary, secondary in base_complements:
   2.106 +        common = min(d[primary], d[secondary])
   2.107 +        d[primary] -= common
   2.108 +        d[secondary] -= common
   2.109 +    return [(f, value) for value, f in d.items()]
   2.110 +
   2.111 +def combine(d):
   2.112 +
   2.113 +    "Combine distribution 'd' to get a colour value."
   2.114 +
   2.115 +    out = [0, 0, 0]
   2.116 +    for v, rgb in d:
   2.117 +        out[0] += v * rgb[0]
   2.118 +        out[1] += v * rgb[1]
   2.119 +        out[2] += v * rgb[2]
   2.120 +    return tuple(map(int, out))
   2.121 +
   2.122 +def pattern(rgb, chosen=None):
   2.123 +
   2.124 +    """
   2.125 +    Obtain a sorted colour distribution for 'rgb', optionally limited to any
   2.126 +    specified 'chosen' colours.
   2.127 +    """
   2.128 +
   2.129 +    l = [(f, value) for f, value in combination(rgb) if not chosen or value in chosen]
   2.130 +    l.sort(reverse=True)
   2.131 +    return l
   2.132 +
   2.133 +def get_value(rgb, chosen=None, fail=False):
   2.134 +
   2.135 +    """
   2.136 +    Get an output colour for 'rgb', optionally limited to any specified 'chosen'
   2.137 +    colours. If 'fail' is set to a true value, return None if the colour cannot
   2.138 +    be expressed using any of the chosen colours.
   2.139 +    """
   2.140 +
   2.141 +    l = pattern(rgb, chosen)
   2.142 +    limit = sum([f for f, c in l])
   2.143 +    if not limit:
   2.144 +        if fail:
   2.145 +            return None
   2.146 +        else:
   2.147 +            return l[randrange(0, len(l))][1]
   2.148 +
   2.149 +    choose = random() * limit
   2.150 +    threshold = 0
   2.151 +    for f, c in l:
   2.152 +        threshold += f
   2.153 +        if choose < threshold:
   2.154 +            return c
   2.155 +    return c
   2.156 +
   2.157 +# Colour processing operations.
   2.158 +
   2.159 +def sign(x):
   2.160 +    return x >= 0 and 1 or -1
   2.161 +
   2.162 +def saturate_rgb(rgb, exp):
   2.163 +    r, g, b = rgb
   2.164 +    return saturate_value(r, exp), saturate_value(g, exp), saturate_value(b, exp)
   2.165 +
   2.166 +def saturate_value(x, exp):
   2.167 +    return int(127.5 + sign(x - 127.5) * 127.5 * pow(abs(x - 127.5) / 127.5, exp))
   2.168 +
   2.169 +def amplify_rgb(rgb, exp):
   2.170 +    r, g, b = rgb
   2.171 +    return amplify_value(r, exp), amplify_value(g, exp), amplify_value(b, exp)
   2.172 +
   2.173 +def amplify_value(x, exp):
   2.174 +    return int(pow(x / 255.0, exp) * 255.0)
   2.175 +
   2.176 +# Image operations.
   2.177 +
   2.178 +def get_colours(im, y):
   2.179 +
   2.180 +    "Get a colour distribution from image 'im' for the row 'y'."
   2.181 +
   2.182 +    width, height = im.size
   2.183 +    c = {}
   2.184 +    x = 0
   2.185 +    while x < width:
   2.186 +        rgb = im.getpixel((x, y))
   2.187 +
   2.188 +        # Sum the colour probabilities.
   2.189 +
   2.190 +        for f, value in combination(rgb):
   2.191 +            if not c.has_key(value):
   2.192 +                c[value] = f
   2.193 +            else:
   2.194 +                c[value] += f
   2.195 +
   2.196 +        x += 1
   2.197 +
   2.198 +    d = [(n/width, value) for value, n in c.items()]
   2.199 +    d.sort(reverse=True)
   2.200 +    return d
   2.201 +
   2.202 +def get_combinations(c, n):
   2.203 +
   2.204 +    """
   2.205 +    Get combinations of colours from 'c' of size 'n' in decreasing order of
   2.206 +    probability.
   2.207 +    """
   2.208 +
   2.209 +    all = []
   2.210 +    for l in itertools.combinations(c, n):
   2.211 +        total = 0
   2.212 +        for f, value in l:
   2.213 +            total += f
   2.214 +        all.append((total, l))
   2.215 +    all.sort(reverse=True)
   2.216 +    return [l for total, l in all]
   2.217 +
   2.218 +def count_colours(im, colours):
   2.219 +
   2.220 +    """
   2.221 +    Count colours on each row of image 'im', returning a tuple indicating the
   2.222 +    first row with more than the given number of 'colours' together with the
   2.223 +    found colours; otherwise returning None.
   2.224 +    """
   2.225 +
   2.226 +    width, height = im.size
   2.227 +
   2.228 +    y = 0
   2.229 +    while y < height:
   2.230 +        l = set()
   2.231 +        x = 0
   2.232 +        while x < width:
   2.233 +            l.add(im.getpixel((x, y)))
   2.234 +            x += 1
   2.235 +        if len(l) > colours:
   2.236 +            return (y, l)
   2.237 +        y += 1
   2.238 +    return None
   2.239 +
   2.240 +def process_image(pim, saturate, desaturate, darken, brighten):
   2.241 +
   2.242 +    """
   2.243 +    Process image 'pim' using the given options: 'saturate', 'desaturate',
   2.244 +    'darken', 'brighten'.
   2.245 +    """
   2.246 +
   2.247 +    width, height = pim.size
   2.248 +    im = SimpleImage(list(pim.getdata()), pim.size)
   2.249 +
   2.250 +    if saturate or desaturate or darken or brighten:
   2.251 +        y = 0
   2.252 +        while y < height:
   2.253 +            x = 0
   2.254 +            while x < width:
   2.255 +                rgb = im.getpixel((x, y))
   2.256 +                if saturate or desaturate:
   2.257 +                    rgb = saturate_rgb(rgb, saturate and 0.5 / saturate or 2 * desaturate)
   2.258 +                if darken or brighten:
   2.259 +                    rgb = amplify_rgb(rgb, brighten and 0.5 / brighten or 2 * darken)
   2.260 +                im.putpixel((x, y), rgb)
   2.261 +                x += 1
   2.262 +            y += 1
   2.263 +
   2.264 +    pim.putdata(im.getdata())
   2.265 +
   2.266 +def convert_image(pim, colours):
   2.267 +
   2.268 +    "Convert image 'pim' to an appropriate output representation."
   2.269 +
   2.270 +    width, height = pim.size
   2.271 +    im = SimpleImage(list(pim.getdata()), pim.size)
   2.272 +
   2.273 +    y = 0
   2.274 +    while y < height:
   2.275 +        c = get_colours(im, y)
   2.276 +
   2.277 +        suggestions = []
   2.278 +
   2.279 +        for l in get_combinations(c, colours):
   2.280 +            most = [value for f, value in l]
   2.281 +            missing = 0
   2.282 +
   2.283 +            x = 0
   2.284 +            while x < width:
   2.285 +                rgb = im.getpixel((x, y))
   2.286 +                value = get_value(rgb, most, True)
   2.287 +                if value is None:
   2.288 +                    missing += 1
   2.289 +                x += 1
   2.290 +
   2.291 +            if not missing:
   2.292 +                break # use this combination
   2.293 +            suggestions.append((missing, l))
   2.294 +
   2.295 +        # Find the most accurate suggestion.
   2.296 +
   2.297 +        else:
   2.298 +            suggestions.sort()
   2.299 +            most = [value for f, value in suggestions[0][1]] # get the combination
   2.300 +
   2.301 +        x = 0
   2.302 +        while x < width:
   2.303 +            rgb = im.getpixel((x, y))
   2.304 +            value = get_value(rgb, most)
   2.305 +            im.putpixel((x, y), value)
   2.306 +
   2.307 +            if x < width - 1:
   2.308 +                rgbn = im.getpixel((x+1, y))
   2.309 +                rgbn = (
   2.310 +                    clip(rgbn[0] + (rgb[0] - value[0]) / 4.0),
   2.311 +                    clip(rgbn[1] + (rgb[1] - value[1]) / 4.0),
   2.312 +                    clip(rgbn[2] + (rgb[2] - value[2]) / 4.0)
   2.313 +                    )
   2.314 +                im.putpixel((x+1, y), rgbn)
   2.315 +
   2.316 +            if y < height - 1:
   2.317 +                rgbn = im.getpixel((x, y+1))
   2.318 +                rgbn = (
   2.319 +                    clip(rgbn[0] + (rgb[0] - value[0]) / 2.0),
   2.320 +                    clip(rgbn[1] + (rgb[1] - value[1]) / 2.0),
   2.321 +                    clip(rgbn[2] + (rgb[2] - value[2]) / 2.0)
   2.322 +                    )
   2.323 +                im.putpixel((x, y+1), rgbn)
   2.324 +
   2.325 +            x += 1
   2.326 +
   2.327 +        y += 1
   2.328 +
   2.329 +    pim.putdata(im.getdata())
   2.330 +
   2.331 +class SimpleImage:
   2.332 +
   2.333 +    "An image behaving like PIL.Image."
   2.334 +
   2.335 +    def __init__(self, data, size):
   2.336 +        self.data = data
   2.337 +        self.width, self.height = self.size = size
   2.338 +
   2.339 +    def copy(self):
   2.340 +        return SimpleImage(self.data[:], self.size)
   2.341 +
   2.342 +    def getpixel(self, xy):
   2.343 +        x, y = xy
   2.344 +        return self.data[y * self.width + x]
   2.345 +
   2.346 +    def putpixel(self, xy, value):
   2.347 +        x, y = xy
   2.348 +        self.data[y * self.width + x] = value
   2.349 +
   2.350 +    def getdata(self):
   2.351 +        return self.data
   2.352 +
   2.353 +# vim: tabstop=4 expandtab shiftwidth=4