1 #!/usr/bin/env python 2 3 """ 4 Convert and optimise images for display in an Acorn Electron MODE 1 variant 5 with four colours per line but eight colours available for selection on each 6 line. 7 8 Copyright (C) 2015 Paul Boddie <paul@boddie.org.uk> 9 10 This program is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free Software 12 Foundation; either version 3 of the License, or (at your option) any later 13 version. 14 15 This program is distributed in the hope that it will be useful, but WITHOUT ANY 16 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 17 PARTICULAR PURPOSE. See the GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License along 20 with this program. If not, see <http://www.gnu.org/licenses/>. 21 """ 22 23 from random import random, randrange 24 import itertools 25 import math 26 27 corners = [ 28 (0, 0, 0), (255, 0, 0), (0, 255, 0), (255, 255, 0), 29 (0, 0, 255), (255, 0, 255), (0, 255, 255), (255, 255, 255) 30 ] 31 32 # Basic colour operations. 33 34 def within(v, lower, upper): 35 return min(max(v, lower), upper) 36 37 def clip(v): 38 return int(within(v, 0, 255)) 39 40 def distance(rgb1, rgb2): 41 return math.sqrt(pow(abs(rgb1[0] - rgb2[0]), 2) + pow(abs(rgb1[1] - rgb2[1]), 2) + pow(abs(rgb1[2] - rgb2[2]), 2)) 42 43 def restore(srgb): 44 r, g, b = srgb 45 return int(r * 255.0), int(g * 255.0), int(b * 255.0) 46 47 def scale(rgb): 48 r, g, b = rgb 49 return r / 255.0, g / 255.0, b / 255.0 50 51 def invert(srgb): 52 r, g, b = srgb 53 return 1.0 - r, 1.0 - g, 1.0 - b 54 55 scaled_corners = map(scale, corners) 56 zipped_corners = zip(corners, scaled_corners) 57 58 # Colour distribution functions. 59 60 def combination(rgb): 61 62 "Return the colour distribution for 'rgb'." 63 64 # Get the colour with components scaled from 0 to 1, plus the inverted 65 # component values. 66 67 srgb = scale(rgb) 68 rgbi = invert(srgb) 69 pairs = zip(rgbi, srgb) 70 71 # For each corner of the colour cube (primary and secondary colours plus 72 # black and white), calculate the corner value's contribution to the 73 # input colour. 74 75 d = [] 76 for corner, scaled in zipped_corners: 77 rs, gs, bs = scaled 78 79 # Obtain inverted channel values where corner channels are low; 80 # obtain original channel values where corner channels are high. 81 82 d.append((pairs[0][int(rs)] * pairs[1][int(gs)] * pairs[2][int(bs)], corner)) 83 84 # Balance the corner contributions. 85 86 return balance(d) 87 88 def complements(rgb): 89 90 "Return 'rgb' and its complement." 91 92 r, g, b = rgb 93 return rgb, restore(invert(scale(rgb))) 94 95 bases = [(0, 0, 0), (255, 0, 0), (0, 255, 0), (0, 0, 255)] 96 base_complements = map(complements, bases) 97 98 def balance(d): 99 100 """ 101 Balance distribution 'd', cancelling opposing values and their complements 102 and replacing their common contributions with black and white contributions. 103 """ 104 105 dd = dict([(value, f) for f, value in d]) 106 for primary, secondary in base_complements: 107 common = min(dd[primary], dd[secondary]) 108 dd[primary] -= common 109 dd[secondary] -= common 110 return [(f, value) for value, f in dd.items()] 111 112 def combine(d): 113 114 "Combine distribution 'd' to get a colour value." 115 116 out = [0, 0, 0] 117 for v, rgb in d: 118 out[0] += v * rgb[0] 119 out[1] += v * rgb[1] 120 out[2] += v * rgb[2] 121 return tuple(map(int, out)) 122 123 def pattern(rgb, chosen=None): 124 125 """ 126 Obtain a sorted colour distribution for 'rgb', optionally limited to any 127 specified 'chosen' colours. 128 """ 129 130 l = [(f, value) for f, value in combination(rgb) if not chosen or value in chosen] 131 l.sort(reverse=True) 132 return l 133 134 def get_value(rgb, chosen=None, fail=False): 135 136 """ 137 Get an output colour for 'rgb', optionally limited to any specified 'chosen' 138 colours. If 'fail' is set to a true value, return None if the colour cannot 139 be expressed using any of the chosen colours. 140 """ 141 142 l = pattern(rgb, chosen) 143 limit = sum([f for f, c in l]) 144 if not limit: 145 if fail: 146 return None 147 else: 148 return l[randrange(0, len(l))][1] 149 150 choose = random() * limit 151 threshold = 0 152 for f, c in l: 153 threshold += f 154 if choose < threshold: 155 return c 156 return c 157 158 # Colour processing operations. 159 160 def sign(x): 161 if x >= 0: 162 return 1 163 else: 164 return -1 165 166 def saturate_rgb(rgb, exp): 167 r, g, b = rgb 168 return saturate_value(r, exp), saturate_value(g, exp), saturate_value(b, exp) 169 170 def saturate_value(x, exp): 171 return int(127.5 + sign(x - 127.5) * 127.5 * pow(abs(x - 127.5) / 127.5, exp)) 172 173 def amplify_rgb(rgb, exp): 174 r, g, b = rgb 175 return amplify_value(r, exp), amplify_value(g, exp), amplify_value(b, exp) 176 177 def amplify_value(x, exp): 178 return int(pow(x / 255.0, exp) * 255.0) 179 180 # Image operations. 181 182 def get_colours(im, y): 183 184 "Get a colour distribution from image 'im' for the row 'y'." 185 186 width, height = im.size 187 c = {} 188 x = 0 189 while x < width: 190 rgb = im.getpixel((x, y)) 191 192 # Sum the colour probabilities. 193 194 for f, value in combination(rgb): 195 if not c.has_key(value): 196 c[value] = f 197 else: 198 c[value] += f 199 200 x += 1 201 202 d = [(n/width, value) for value, n in c.items()] 203 d.sort(reverse=True) 204 return d 205 206 def get_combinations(c, n): 207 208 """ 209 Get combinations of colours from 'c' of size 'n' in decreasing order of 210 probability. 211 """ 212 213 all = [] 214 for l in itertools.combinations(c, n): 215 total = 0 216 for f, value in l: 217 total += f 218 all.append((total, l)) 219 all.sort(reverse=True) 220 return [l for total, l in all] 221 222 def count_colours(im, colours): 223 224 """ 225 Count colours on each row of image 'im', returning a tuple indicating the 226 first row with more than the given number of 'colours' together with the 227 found colours; otherwise returning None. 228 """ 229 230 width, height = im.size 231 232 y = 0 233 while y < height: 234 l = set() 235 x = 0 236 while x < width: 237 l.add(im.getpixel((x, y))) 238 x += 1 239 if len(l) > colours: 240 return (y, l) 241 y += 1 242 return None 243 244 def process_image(im, saturate, desaturate, darken, brighten): 245 246 """ 247 Process image 'im' using the given options: 'saturate', 'desaturate', 248 'darken', 'brighten'. 249 """ 250 251 width, height = im.size 252 253 if saturate or desaturate or darken or brighten: 254 y = 0 255 while y < height: 256 x = 0 257 while x < width: 258 rgb = im.getpixel((x, y)) 259 if saturate or desaturate: 260 rgb = saturate_rgb(rgb, saturate and 0.5 / saturate or 2.0 * desaturate) 261 if darken or brighten: 262 rgb = amplify_rgb(rgb, brighten and 0.5 / brighten or 2.0 * darken) 263 im.putpixel((x, y), rgb) 264 x += 1 265 y += 1 266 267 def convert_image(im, colours, least_error=False): 268 269 "Convert image 'im' to an appropriate output representation." 270 271 width, height = im.size 272 273 y = 0 274 while y < height: 275 c = get_colours(im, y) 276 277 suggestions = [] 278 279 for l in get_combinations(c, colours): 280 most = [value for f, value in l] 281 error = 0 282 283 x = 0 284 while x < width: 285 rgb = im.getpixel((x, y)) 286 value = get_value(rgb, most) 287 if least_error: 288 error += distance(value, rgb) 289 elif value is None: 290 error += 1 291 x += 1 292 293 if not least_error and not error: 294 break # use this combination 295 296 suggestions.append((error, l)) 297 298 # Find the most accurate suggestion. 299 300 else: 301 suggestions.sort() 302 most = [value for f, value in suggestions[0][1]] # get the combination 303 304 x = 0 305 while x < width: 306 rgb = im.getpixel((x, y)) 307 value = get_value(rgb, most) 308 im.putpixel((x, y), value) 309 310 if x < width - 1: 311 rgbn = im.getpixel((x+1, y)) 312 rgbn = ( 313 clip(rgbn[0] + (rgb[0] - value[0]) / 4.0), 314 clip(rgbn[1] + (rgb[1] - value[1]) / 4.0), 315 clip(rgbn[2] + (rgb[2] - value[2]) / 4.0) 316 ) 317 im.putpixel((x+1, y), rgbn) 318 319 if y < height - 1: 320 rgbn = im.getpixel((x, y+1)) 321 rgbn = ( 322 clip(rgbn[0] + (rgb[0] - value[0]) / 2.0), 323 clip(rgbn[1] + (rgb[1] - value[1]) / 2.0), 324 clip(rgbn[2] + (rgb[2] - value[2]) / 2.0) 325 ) 326 im.putpixel((x, y+1), rgbn) 327 328 x += 1 329 330 y += 1 331 332 class SimpleImage: 333 334 "An image behaving like PIL.Image." 335 336 def __init__(self, data, size): 337 self.data = data 338 self.width, self.height = self.size = size 339 340 def copy(self): 341 return SimpleImage(self.data[:], self.size) 342 343 def getpixel(self, xy): 344 x, y = xy 345 return self.data[y * self.width + x] 346 347 def putpixel(self, xy, value): 348 x, y = xy 349 self.data[y * self.width + x] = value 350 351 def getdata(self): 352 return self.data 353 354 # Exercise functions for Shedskin. 355 356 if __name__ == "__main__": 357 rgb = (200, 100, 50) 358 saturate_rgb(rgb, 1.0) 359 amplify_rgb(rgb, 1.0) 360 get_value(rgb) 361 get_value(rgb, [(255, 255, 255), (255, 0, 0), (255, 255, 0), (0, 0, 0)]) 362 combine([(1.0, (255, 0, 0)), (0.0, (0, 0, 0))]) 363 clip(200.0) 364 get_combinations([(0.5, (255, 0, 0)), (0.25, (255, 255, 0)), (0.25, (0, 0, 0))], 2) 365 366 data = [(0, 0, 0), (0, 0, 0)] 367 im = SimpleImage(data, (2, 1)) 368 im2 = im.copy() 369 im2.getpixel((0, 0)) == (0, 0, 0) 370 im2.putpixel((0, 0), (255, 255, 255)) 371 im2.getdata() == [(255, 255, 255), (0, 0, 0)] 372 373 get_colours(im, 0) == [(1.0, (0, 0, 0))] 374 count_colours(im, 4) 375 376 process_image(im, 1.0, 0.0, 1.0, 0.0) 377 convert_image(im, 4, True) 378 379 # vim: tabstop=4 expandtab shiftwidth=4