source: www/study/study.py @ 2127

Last change on this file since 2127 was 2127, checked in by Sam Hocevar, 13 years ago
  • Shiau-Fan patented dithering.
  • Ostromoukhov's variable coefficient error diffusion.
  • Property svn:executable set to *
File size: 43.8 KB
Line 
1#!/usr/bin/env python
2
3import math, gd, random, sys
4
5# Select which chapters to run
6def chapter(n):
7    if len(sys.argv) == 1:
8        return True
9    return str(n) in sys.argv
10
11##############################################################################
12
13# Tiny image class to make examples short and readable
14class Image(gd.image):
15    gd.gdMaxColors = 256 * 256 * 256
16    def __init__(self, *args):
17        if args[0].__class__ == str:
18            print " * loading %s" % (args[0],)
19        gd.image.__init__(self, *args)
20    def save(self, name):
21        print " * saving %s" % (name,)
22        self.writePng(name)
23    def getGray(self, x, y):
24        p = self.getPixel((x, y))
25        c = self.colorComponents(p)[0] / 255.0
26        return c
27    def getRgb(self, x, y):
28        p = self.getPixel((x, y))
29        rgb = self.colorComponents(p)
30        return [rgb[0] / 255.0, rgb[1] / 255.0, rgb[2] / 255.0]
31    def setGray(self, x, y, t):
32        p = (int)(t * 255.999)
33        c = self.colorResolve((p, p, p))
34        self.setPixel((x, y), c)
35    def setRgb(self, x, y, r, g, b):
36        r = (int)(r * 255.999)
37        g = (int)(g * 255.999)
38        b = (int)(b * 255.999)
39        c = self.colorResolve((r, g, b))
40        self.setPixel((x, y), c)
41    def getRegion(self, x, y, w, h):
42        dest = Image((w, h), True)
43        self.copyTo(dest, (-x, -y))
44        return dest
45    def getZoom(self, z):
46        (w, h) = self.size()
47        dest = Image((w * z, h * z), True)
48        for y in range(h):
49            for x in range(w):
50                rgb = self.getRgb(x, y)
51                for j in range(z):
52                    for i in range(z):
53                        dest.setRgb(x * z + i, y * z + j, *rgb)
54        return dest
55
56# Manipulate gamma values
57class Gamma:
58    def CtoI(x):
59        return math.pow(x, 2.2)
60    def ItoC(x):
61        if x < 0:
62            return -math.pow(-x, 1 / 2.2)
63        return math.pow(x, 1 / 2.2)
64    CtoI = staticmethod(CtoI)
65    ItoC = staticmethod(ItoC)
66    def Cto2(x):
67        if x < Gamma.CtoI(0.50):
68            return 0.
69        return 1.
70    def Cto3(x):
71        if x < Gamma.CtoI(0.25):
72            return 0.
73        elif x < Gamma.CtoI(0.75):
74            return Gamma.CtoI(0.5)
75        return 1.
76    def Cto4(x):
77        if x < Gamma.CtoI(0.17):
78            return 0.
79        elif x < Gamma.CtoI(0.50):
80            return Gamma.CtoI(0.3333)
81        elif x < Gamma.CtoI(0.83):
82            return Gamma.CtoI(0.6666)
83        return 1.
84    Cto2 = staticmethod(Cto2)
85    Cto3 = staticmethod(Cto3)
86    Cto4 = staticmethod(Cto4)
87
88##############################################################################
89print "Initialisation"
90
91# Load the original Lenna image
92lenna512 = Image("lenna512.png")
93(w, h) = lenna512.size()
94
95# Image 1: grayscale conversion
96# Read the compression FAQ [55] for the rationale behind using the green
97# channel (http://www.faqs.org/faqs/compression-faq/part1/section-30.html)
98if chapter(0):
99    (w, h) = lenna512.size()
100    lenna512bw = Image((w, h))
101    for y in range(h):
102        for x in range(w):
103            rgb = lenna512.getRgb(x, y)
104            c = rgb[1]
105            lenna512bw.setGray(x, y, c)
106    lenna512bw.save("lenna512bw.png")
107else:
108    lenna512bw = Image("lenna512bw.png")
109   
110# Image 2: 50% grayscale
111# Image 3: 50% scaling
112if chapter(0):
113    (w, h) = lenna512.size()
114    lenna256bw = Image((w / 2, h / 2))
115    lenna256 = Image((w / 2, h / 2), True)
116    for y in range(h / 2):
117        for x in range(w / 2):
118            r = g = b = 0.
119            for j in range(2):
120                for i in range(2):
121                    rgb = lenna512.getRgb(x * 2 + i, y * 2 + j)
122                    r += Gamma.CtoI(rgb[0])
123                    g += Gamma.CtoI(rgb[1])
124                    b += Gamma.CtoI(rgb[2])
125            r = Gamma.ItoC(r / 4)
126            g = Gamma.ItoC(g / 4)
127            b = Gamma.ItoC(b / 4)
128            lenna256bw.setGray(x, y, g)
129            lenna256.setRgb(x, y, r, g, b)
130    lenna256bw.save("lenna256bw.png")
131    lenna256.save("lenna256.png")
132else:
133    lenna256bw = Image("lenna256bw.png")
134    lenna256 = Image("lenna256.png")
135
136# Create a 32x256 grayscale gradient
137if chapter(0):
138    gradient256bw = Image((32, 256))
139    for x in range(32):
140        for y in range(256):
141            gradient256bw.setGray(x, 255 - y, y / 255.)
142    gradient256bw.save("gradient256bw.png")
143else:
144    gradient256bw = Image("gradient256bw.png")
145
146##############################################################################
147if chapter(1):
148    print "Chapter 1. Colour quantisation"
149
150# Output 1.1.1: 50% threshold
151# Output 1.1.2: 40% threshold
152# Output 1.1.3: 60% threshold
153def test11x(src, threshold):
154    (w, h) = src.size()
155    dest = Image((w, h))
156    for y in range(h):
157        for x in range(w):
158            c = src.getGray(x, y) > threshold
159            dest.setGray(x, y, c)
160    return dest
161
162if chapter(1):
163    test11x(lenna256bw, 0.5).save("out1-1-1.png")
164    test11x(lenna256bw, 0.4).save("out1-1-2.png")
165    test11x(lenna256bw, 0.6).save("out1-1-3.png")
166    test11x(gradient256bw, 0.5).save("grad1-1-1.png")
167    test11x(gradient256bw, 0.4).save("grad1-1-2.png")
168    test11x(gradient256bw, 0.6).save("grad1-1-3.png")
169
170# Output 1.2.1: 3-colour threshold
171# Output 1.2.2: 5-colour threshold
172def test12x(src, colors):
173    (w, h) = src.size()
174    dest = Image((w, h))
175    q = colors - 1
176    p = -.00001 + colors
177    for y in range(h):
178        for x in range(w):
179            c = src.getGray(x, y)
180            c = math.floor(c * p) / q
181            dest.setGray(x, y, c)
182    return dest
183
184if chapter(1):
185    test12x(lenna256bw, 3).save("out1-2-1.png")
186    test12x(lenna256bw, 5).save("out1-2-2.png")
187    test12x(gradient256bw, 3).save("grad1-2-1.png")
188    test12x(gradient256bw, 5).save("grad1-2-2.png")
189
190# Output 1.2.3: 3-colour threshold, minimal error
191# Output 1.2.4: 5-colour threshold, minimal error
192def test12y(src, colors):
193    (w, h) = src.size()
194    dest = Image((w, h))
195    q = colors - 1
196    p = -.00001 + colors - 1
197    for y in range(h):
198        for x in range(w):
199            c = src.getGray(x, y)
200            c = math.floor((c + 0.5 / p) * p) / q
201            dest.setGray(x, y, c)
202    return dest
203
204if chapter(1):
205    test12y(lenna256bw, 3).save("out1-2-3.png")
206    test12y(lenna256bw, 5).save("out1-2-4.png")
207    test12y(gradient256bw, 3).save("grad1-2-3.png")
208    test12y(gradient256bw, 5).save("grad1-2-4.png")
209
210# Output 1.3.1: 2-colour threshold, dynamic thresholding
211def test13x(src, n):
212    (w, h) = src.size()
213    dest = Image((w, h))
214    # Compute histogram
215    histo = [0] * 256
216    for y in range(h):
217        for x in range(w):
218            histo[(int)(src.getGray(x, y) * 255.9999)] += 1
219    thresholds = [1. * (1. + i) / n for i in range(n - 1)]
220    values = [i / (n - 1.) for i in range(n)]
221    # Parse histogram
222    total = 0
223    t = 0
224    for i in range(256):
225        total += histo[i]
226        if total > thresholds[t] * w * h:
227            thresholds[t] = i / 255.0
228            t += 1
229            if t + 1 > n - 1:
230                break
231    # Compute image
232    for y in range(h):
233        for x in range(w):
234            c = src.getGray(x, y)
235            for (i, t) in enumerate(thresholds):
236                if c < t:
237                    dest.setGray(x, y, values[i])
238                    break
239            else:
240                dest.setGray(x, y, values[n - 1])
241    return dest
242
243if chapter(1):
244    test13x(lenna256bw, 2).save("out1-3-1.png")
245    test13x(gradient256bw, 2).save("grad1-3-1.png")
246    test13x(lenna256bw, 5).save("out1-3-2.png")
247    test13x(gradient256bw, 5).save("grad1-3-2.png")
248
249##############################################################################
250if chapter(2):
251    print "Chapter 2. Halftoning patterns"
252
253# Pattern 2.1.1: a 50% halftone pattern with various block sizes
254# Pattern 2.1.2: 25% and 75% halftone patterns with various block sizes
255if chapter(2):
256    dest = Image((320, 80))
257    for x in range(320):
258        d = 8 >> (x / 80)
259        for y in range(80):
260            c = (x / d + y / d) & 1
261            dest.setGray(x, y, c)
262    dest.save("pat2-1-1.png")
263
264    dest = Image((320, 80))
265    for x in range(320):
266        d = 8 >> (x / 80)
267        for y in range(40):
268            c = ((x / d + y / d) & 1) or (y / d & 1)
269            dest.setGray(x, y, c)
270        for y in range(40, 80):
271            c = ((x / d + y / d) & 1) and (y / d & 1)
272            dest.setGray(x, y, c)
273    dest.save("pat2-1-2.png")
274
275# Output 2.1.1: 20/40/60/80% threshold with 25/50/75% patterns inbetween:
276def test211(src):
277    (w, h) = src.size()
278    dest = Image((w, h))
279    for y in range(h):
280        for x in range(w):
281            c = src.getGray(x, y)
282            if c < 0.2:
283                c = 0.
284            elif c < 0.4:
285                c = ((x + y) & 1) and (y & 1)
286            elif c < 0.6:
287                c = (x + y) & 1
288            elif c < 0.8:
289                c = ((x + y) & 1) or (y & 1)
290            else:
291                c = 1.
292            dest.setGray(x, y, c)
293    return dest
294
295if chapter(2):
296    test211(lenna256bw).save("out2-1-1.png")
297    test211(gradient256bw).save("grad2-1-1.png")
298
299# Pattern 2.2.1: vertical, mixed and horizontal black-white halftones
300# Pattern 2.2.2: two different 25% patterns
301if chapter(2):
302    dest = Image((240, 80))
303    for y in range(80):
304        for x in range(80):
305            c = x & 1
306            dest.setGray(x, y, c)
307        for x in range(80, 160):
308            c = (x / d + y / d) & 1
309            dest.setGray(x, y, c)
310        for x in range(160, 240):
311            c = y & 1
312            dest.setGray(x, y, c)
313    dest.save("pat2-2-1.png")
314
315    dest = Image((320, 80))
316    for y in range(80):
317        for x in range(80):
318            c = (x / 2 & 1) and (y / 2 & 1)
319            dest.setGray(x, y, c)
320        for x in range(80, 160):
321            c = (x & 1) and (y & 1)
322            dest.setGray(x, y, c)
323        for x in range(160, 240):
324            c = (x & 1) and ((y + x / 2) & 1)
325            dest.setGray(x, y, c)
326        for x in range(240, 320):
327            c = (x / 2 & 1) and ((y / 2 + x / 4) & 1)
328            dest.setGray(x, y, c)
329    dest.save("pat2-2-2.png")
330
331# Output 2.3.1: 4x4 Bayer dithering
332# Output 2.3.2: 4x4 cluster dot
333# Output 2.3.3: 5x3 line dithering
334def ordereddither(src, mat):
335    (w, h) = src.size()
336    dest = Image((w, h))
337    dx = len(mat[0])
338    dy = len(mat)
339    for y in range(h):
340        for x in range(w):
341            c = src.getGray(x, y)
342            threshold = (1. + mat[y % dy][x % dx]) / (dx * dy + 1)
343            c = c > threshold
344            dest.setGray(x, y, c)
345    return dest
346
347def makebayer(rank, mat = False):
348    if not mat:
349        mat = [[0]]
350    if not rank:
351        return mat
352    n = len(mat)
353    newmat = [[0] * n * 2 for i in range(n * 2)]
354    for j in range(n):
355        for i in range(n):
356            x = mat[j][i]
357            newmat[j * 2][i * 2] = x
358            newmat[j * 2][i * 2 + 1] = x + n * n * 3
359            newmat[j * 2 + 1][i * 2] = x + n * n * 2
360            newmat[j * 2 + 1][i * 2 + 1] = x + n * n
361    return makebayer(rank - 1, newmat)
362
363DITHER_BAYER44 = makebayer(2)
364#  [[  0, 12,  3, 15],
365#   [  8,  4, 11,  7],
366#   [  2, 14,  1, 13],
367#   [ 10,  6,  9,  5]]
368
369DITHER_BAYER88 = makebayer(3)
370#  [[  0, 48, 12, 60,  3, 51, 15, 63],
371#   [ 32, 16, 44, 28, 35, 19, 47, 31],
372#   [  8, 56,  4, 52, 11, 59,  7, 55],
373#   [ 40, 24, 36, 20, 43, 27, 39, 23],
374#   [  2, 50, 14, 62,  1, 49, 13, 61],
375#   [ 34, 18, 46, 30, 33, 17, 45, 29],
376#   [ 10, 58,  6, 54,  9, 57,  5, 53],
377#   [ 42, 26, 38, 22, 41, 25, 37, 21]]
378
379DITHER_CLUSTER44 = \
380    [[ 12,  5,  6, 13],
381     [  4,  0,  1,  7],
382     [ 11,  3,  2,  8],
383     [ 15, 10,  9, 14]]
384DITHER_CLUSTER88 = \
385    [[ 24, 10, 12, 26, 35, 47, 49, 37],
386     [  8,  0,  2, 14, 45, 59, 61, 51],
387     [ 22,  6,  4, 16, 43, 57, 63, 53],
388     [ 30, 20, 18, 28, 33, 41, 55, 39],
389     [ 34, 46, 48, 36, 25, 11, 13, 27],
390     [ 44, 58, 60, 50,  9,  1,  3, 15],
391     [ 42, 56, 62, 52, 23,  7,  5, 17],
392     [ 32, 40, 54, 38, 31, 21, 19, 29]]
393DITHER_LINE53 = \
394    [[ 13,  7,  0,  4, 10],
395     [  9,  3,  1,  8, 14],
396     [ 11,  5,  2,  6, 12],]
397
398if chapter(2):
399    ordereddither(lenna256bw, DITHER_BAYER44).save("out2-3-1.png")
400    ordereddither(gradient256bw, DITHER_BAYER44).save("grad2-3-1.png")
401
402    ordereddither(lenna256bw, DITHER_BAYER88).save("out2-3-1b.png")
403    ordereddither(gradient256bw, DITHER_BAYER88).save("grad2-3-1b.png")
404
405    ordereddither(lenna256bw, DITHER_CLUSTER44).save("out2-3-2.png")
406    ordereddither(gradient256bw, DITHER_CLUSTER44).save("grad2-3-2.png")
407
408    ordereddither(lenna256bw, DITHER_CLUSTER88).save("out2-3-2b.png")
409    ordereddither(gradient256bw, DITHER_CLUSTER88).save("grad2-3-2b.png")
410
411    ordereddither(lenna256bw, DITHER_LINE53).save("out2-3-3.png")
412    ordereddither(gradient256bw, DITHER_LINE53).save("grad2-3-3.png")
413
414# Output 2.4.1: uniform random dithering
415def test241(src):
416    random.seed(0)
417    (w, h) = src.size()
418    dest = Image((w, h))
419    for y in range(h):
420        for x in range(w):
421            c = src.getGray(x, y)
422            d = c > random.random()
423            dest.setGray(x, y, d)
424    return dest
425
426if chapter(2):
427    test241(lenna256bw).save("out2-4-1.png")
428    test241(gradient256bw).save("grad2-4-1.png")
429
430# Output 2.4.2: gaussian random dithering
431def test242(src):
432    random.seed(0)
433    (w, h) = src.size()
434    dest = Image((w, h))
435    for y in range(h):
436        for x in range(w):
437            c = src.getGray(x, y)
438            d = c > random.gauss(0.5, 0.15)
439            dest.setGray(x, y, d)
440    return dest
441
442if chapter(2):
443    test242(lenna256bw).save("out2-4-2.png")
444    test242(gradient256bw).save("grad2-4-2.png")
445
446# Output 2.4.3: 4x4 Bayer dithering with gaussian perturbation
447def test243(src, mat):
448    random.seed(0)
449    (w, h) = src.size()
450    dest = Image((w, h))
451    dx = len(mat[0])
452    dy = len(mat)
453    for y in range(h):
454        for x in range(w):
455            c = src.getGray(x, y)
456            threshold = (1. + mat[y % dy][x % dx]) / (dx * dy + 1)
457            threshold += random.gauss(0, 0.08)
458            c = c > threshold
459            dest.setGray(x, y, c)
460    return dest
461
462if chapter(2):
463    test243(lenna256bw, DITHER_BAYER88).save("out2-4-3.png")
464    test243(gradient256bw, DITHER_BAYER88).save("grad2-4-3.png")
465
466# Output 2.4.4: random dither matrice selection
467def test244(src, mlist):
468    random.seed(0)
469    (w, h) = src.size()
470    dest = Image((w, h))
471    dx = len(mlist[0][0])
472    dy = len(mlist[0])
473    for y in range(h / dy):
474        for x in range(w / dx):
475            mat = mlist[(int)(random.random() * len(mlist))]
476            for j in range(dy):
477                for i in range(dx):
478                    c = src.getGray(x * dx + i, y * dy + j)
479                    threshold = (1. + mat[j][i]) / (dx * dy + 1)
480                    d = c > threshold
481                    dest.setGray(x * dx + i, y * dy + j, d)
482    return dest
483
484if chapter(2):
485    m1 = [[1, 4, 7],
486          [6, 0, 2],
487          [3, 8, 5]]
488    m2 = [[4, 6, 3],
489          [8, 1, 5],
490          [0, 3, 7]]
491    m3 = [[5, 0, 3],
492          [2, 8, 6],
493          [7, 4, 1]]
494    m4 = [[8, 2, 5],
495          [6, 4, 0],
496          [1, 7, 3]]
497    m5 = [[2, 5, 8],
498          [0, 7, 3],
499          [4, 1, 6]]
500    m6 = [[7, 4, 1],
501          [3, 6, 8],
502          [2, 0, 5]]
503    mlist = [m1, m2, m3, m4, m5, m6]
504    test244(lenna256bw, mlist).save("out2-4-4.png")
505    test244(gradient256bw, mlist).save("grad2-4-4.png")
506
507# Output 2.5.1: cross pattern
508# Output 2.5.2: hex pattern
509# Output 2.5.3: square pattern
510def test25x(src, mat, vec):
511    # 1. count non-zero pixels
512    n = 0
513    for line in mat:
514        for x in line:
515            if x > 0:
516                n += 1
517    # 2. create list of vectors
518    l = []
519    x = y = 0
520    while (x, y) not in l:
521        l.append((x, y))
522        (x, y) = ((x + vec[0][0]) % n, (y + vec[0][1]) % n)
523        if (x, y) in l:
524            (x, y) = ((x + vec[1][0]) % n, (y + vec[1][1]) % n)
525    # 3. create big matrix
526    m = [[0] * n for i in range(n)]
527    for v in l:
528        for y in range(len(mat)):
529            for x in range(len(mat[0])):
530                if mat[y][x] == 0:
531                    continue
532                m[(v[1] + y + n) % n][(v[0] + x + n) % n] = mat[y][x]
533    # 4. dither image
534    (w, h) = src.size()
535    dest = Image((w, h))
536    for y in range(h):
537        for x in range(w):
538            c = src.getGray(x, y)
539            threshold = m[y % n][x % n] / (1. + n)
540            d = c > threshold
541            dest.setGray(x, y, d)
542    return dest
543
544if chapter(2):
545    mat = [[0, 5, 0],
546           [4, 1, 2],
547           [0, 3, 0]]
548    vec = [(2, -1), (1, 2)]
549    test25x(lenna256bw, mat, vec).save("out2-5-1.png")
550    test25x(gradient256bw, mat, vec).save("grad2-5-1.png")
551    mat = [[0, 5, 3, 0],
552           [7, 1, 6, 4],
553           [0, 8, 2, 0]]
554    vec = [(2, -2), (3, 1)]
555    test25x(lenna256bw, mat, vec).save("out2-5-2.png")
556    test25x(gradient256bw, mat, vec).save("grad2-5-2.png")
557    mat = [[ 0,  0,  0,  8,  0],
558           [ 0,  3,  7, 10,  9],
559           [ 4,  1,  2,  6,  0],
560           [ 0,  5,  0,  0,  0]]
561    vec = [(2, 4), (3, 1)]
562    test25x(lenna256bw, mat, vec).save("out2-5-3.png")
563    test25x(gradient256bw, mat, vec).save("grad2-5-3.png")
564    mat = [[ 0,  0,  3,  0],
565           [ 1,  2,  4,  9],
566           [ 6,  5,  8,  7],
567           [ 0, 10,  0,  0]]
568    vec = [(2, 2), (0, 5)]
569    test25x(lenna256bw, mat, vec).save("out2-5-4.png")
570    test25x(gradient256bw, mat, vec).save("grad2-5-4.png")
571
572# Output 2.6.1: 4-wise cross pattern
573# Output 2.6.2: 3-wise hex pattern
574# Output 2.6.3: 4-wise square pattern
575if chapter(2):
576    mat = [[ 0,  0,  0, 19,  0,  0],
577           [ 0, 17, 15,  3,  7,  0],
578           [13,  1,  5, 11, 18,  0],
579           [ 0,  9, 20, 14,  2,  6],
580           [ 0, 16,  4,  8, 10,  0],
581           [ 0,  0, 12,  0,  0,  0]]
582    vec = [(4, -2), (2, 4)]
583    test25x(lenna256bw, mat, vec).save("out2-6-1.png")
584    test25x(gradient256bw, mat, vec).save("grad2-6-1.png")
585    mat = [[ 0, 13,  7,  0,  0,  0,  0],
586           [19,  1, 16, 10, 15,  9,  0],
587           [ 0, 22,  4, 21,  3, 18, 12],
588           [ 0,  0, 14,  8, 24,  6,  0],
589           [ 0, 20,  2, 17, 11,  0,  0],
590           [ 0,  0, 23,  5,  0,  0,  0]]
591    vec = [(5, -1), (-1, 5)]
592    test25x(lenna256bw, mat, vec).save("out2-6-2.png")
593    test25x(gradient256bw, mat, vec).save("grad2-6-2.png")
594    mat = [[ 0,  0,  0,  0, 31,  0,  0,  0,  0],
595           [ 0,  0, 11, 27, 39, 35,  0, 30,  0],
596           [ 0, 15,  3,  7, 23, 10, 26, 38, 34],
597           [ 0,  0, 19, 29, 14,  2,  6, 22,  0],
598           [ 0,  9, 25, 37, 33, 18, 32,  0,  0],
599           [13,  1,  5, 21, 12, 28, 40, 36,  0],
600           [ 0, 17,  0, 16,  4,  8, 24,  0,  0],
601           [ 0,  0,  0,  0, 20,  0,  0,  0,  0]]
602    vec = [(6, 2), (-2, 6)]
603    test25x(lenna256bw, mat, vec).save("out2-6-3.png")
604    test25x(gradient256bw, mat, vec).save("grad2-6-3.png")
605    mat = [[ 0,  0,  4, 36,  0,  0,  2, 34,  0,  0,  0,  0,  0],
606           [ 0,  0,  0, 20, 52,  0,  0, 18, 50,  0,  0,  0,  0],
607           [ 8, 40, 12, 44,  6, 38, 10, 42,  0,  0,  0,  0,  0],
608           [ 0, 24, 56, 28, 60, 22, 54, 26, 58,  0,  0,  0,  0],
609           [16, 48,  0,  0, 14, 46,  3, 35,  0,  0,  1, 33,  0],
610           [ 0, 32, 64,  0,  0, 30, 62, 19, 51,  0,  0, 17, 49],
611           [ 0,  0,  0,  0,  7, 39, 11, 43,  5, 37,  9, 41,  0],
612           [ 0,  0,  0,  0,  0, 23, 55, 27, 59, 21, 53, 25, 57],
613           [ 0,  0,  0,  0, 15, 47,  0,  0, 13, 45,  0,  0,  0],
614           [ 0,  0,  0,  0,  0, 31, 63,  0,  0, 29, 61,  0,  0]]
615    vec = [(8, 0), (0, 8)]
616    test25x(lenna256bw, mat, vec).save("out2-6-4.png")
617    test25x(gradient256bw, mat, vec).save("grad2-6-4.png")
618    mat = [[  0,  0,  0,  0,  0,  0,  9,  0],
619           [  0,  0,  7,  0,  3,  6, 12, 27],
620           [  1,  4, 10, 25, 18, 15, 24, 21],
621           [ 16, 13, 22, 19,  8, 30,  0,  0],
622           [  0, 28,  2,  5, 11, 26,  0,  0],
623           [  0,  0, 17, 14, 23, 20,  0,  0],
624           [  0,  0,  0, 29,  0,  0,  0,  0]]
625    vec = [(6, 1), (0, 5)]
626    test25x(lenna256bw, mat, vec).save("out2-6-5.png")
627    test25x(gradient256bw, mat, vec).save("grad2-6-5.png")
628    mat = [[  0,  0,  0,  0,  0,  0, 25,  0,  0,  0,  0,  0,  0,  0],
629           [  0,  0, 19,  0,  7, 16, 34, 79,  0,  0,  0,  0, 27,  0],
630           [  1, 10, 28, 73, 52, 43, 70, 61, 21,  0,  9, 18, 36, 81],
631           [ 46, 37, 64, 55, 22, 88,  3, 12, 30, 75, 54, 45, 72, 63],
632           [  0, 82,  4, 13, 31, 76, 48, 39, 66, 57, 24, 90,  0,  0],
633           [  0,  0, 49, 40, 67, 58, 26, 84,  6, 15, 33, 78,  0,  0],
634           [  0,  0, 20, 85,  8, 17, 35, 80, 51, 42, 69, 60,  0,  0],
635           [  2, 11, 29, 74, 53, 44, 71, 62,  0, 87,  0,  0,  0,  0],
636           [ 47, 38, 65, 56, 23, 89,  0,  0,  0,  0,  0,  0,  0,  0],
637           [  0, 83,  5, 14, 32, 77,  0,  0,  0,  0,  0,  0,  0,  0],
638           [  0,  0, 50, 41, 68, 59,  0,  0,  0,  0,  0,  0,  0,  0],
639           [  0,  0,  0, 86,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]]
640    test25x(lenna256bw, mat, vec).save("out2-6-6.png")
641    test25x(gradient256bw, mat, vec).save("grad2-6-6.png")
642
643##############################################################################
644if chapter(3):
645    print "Chapter 3. Error diffusion"
646
647# Output 3.0.1: naive error diffusion
648# Output 3.1.1: standard Floyd-Steinberg
649# Output 3.1.2: serpentine Floyd-Steinberg
650# FIXME: serpentine only works if rows == offset * 2 + 1
651# Output 3.2.1: Fan (modified Floyd-Steinberg)
652# Output 3.2.1b: Shiau-Fan 1
653# Output 3.2.1c: Shiau-Fan 2
654# Output 3.2.2: Jarvis, Judice and Ninke
655# Output 3-2-3: Stucki
656# Output 3-2-4: Burkes
657# Output 3-2-5: Sierra
658# Output 3.2.6: Two-line Sierra
659# Output 3.2.7: Sierra's Filter Lite
660# Output 3-2-8: Atkinson
661def test3xx(src, mat, serpentine):
662    (w, h) = src.size()
663    dest = Image((w, h))
664    lines = len(mat)
665    rows = len(mat[0])
666    offset = mat[0].index(-1)
667    ey = [[0.] * (w + rows - 1) for x in range(lines)]
668    for y in range(h):
669        ex = [0.] * (rows - offset)
670        if serpentine and y & 1:
671            xrange = range(w - 1, -1, -1)
672        else:
673            xrange = range(w)
674        for x in xrange:
675            # Set pixel
676            c = src.getGray(x, y) + ex[0] + ey[0][x + offset]
677            d = c > 0.5
678            dest.setGray(x, y, d)
679            error = c - d
680            # Propagate first line of error
681            for dx in range(rows - offset - 2):
682                ex[dx] = ex[dx + 1] + error * mat[0][offset + 1 + dx]
683            ex[rows - offset - 2] = error * mat[0][rows - 1]
684            # Propagate next lines
685            if serpentine and y & 1:
686                for dy in range(1, lines):
687                    for dx in range(rows):
688                        ey[dy][x + dx] += error * mat[dy][rows - 1 - dx]
689            else:
690                for dy in range(1, lines):
691                    for dx in range(rows):
692                        ey[dy][x + dx] += error * mat[dy][dx]
693        for dy in range(lines - 1):
694            ey[dy] = ey[dy + 1]
695        ey[lines - 1] = [0.] * (w + rows - 1)
696    return dest
697
698ERROR_NAIVE = \
699    [[ -1, 1]]
700ERROR_FSTEIN = \
701    [[    0.,    -1, 7./16],
702     [ 3./16, 5./16, 1./16]]
703ERROR_FAN = \
704    [[    0.,    0.,    -1, 7./16],
705     [ 1./16, 3./16, 5./16,    0.]]
706ERROR_SHIAUFAN = \
707    [[    0.,    0.,    -1, 8./16],
708     [ 2./16, 2./16, 4./16,    0.]]
709ERROR_SHIAUFAN2 = \
710    [[    0.,    0.,    0.,    -1, 8./16],
711     [ 1./16, 1./16, 2./16, 4./16,    0.]]
712ERROR_JAJUNI = \
713    [[    0.,    0.,    -1, 7./48, 5./48],
714     [ 3./48, 5./48, 7./48, 5./48, 3./48],
715     [ 1./48, 3./48, 5./48, 3./48, 1./48]]
716ERROR_STUCKI = \
717    [[    0.,    0.,    -1, 8./42, 4./42],
718     [ 2./42, 4./42, 8./42, 4./42, 2./42],
719     [ 1./42, 2./42, 4./42, 2./42, 1./42]]
720ERROR_BURKES = \
721    [[    0.,    0.,    -1, 8./32, 4./32],
722     [ 2./32, 4./32, 8./32, 4./32, 2./32]]
723ERROR_SIERRA = \
724    [[    0.,    0.,    -1, 5./32, 3./32],
725     [ 2./32, 4./32, 5./32, 4./32, 2./32],
726     [    0., 2./32, 3./32, 2./32,    0.]]
727ERROR_SIERRA2 = \
728    [[    0.,    0.,    -1, 4./16, 3./16],
729     [ 1./16, 2./16, 3./16, 2./16, 1./16]]
730ERROR_FILTERLITE = \
731    [[   0.,   -1, 2./4],
732     [ 1./4, 1./4,   0.]]
733ERROR_ATKINSON = \
734    [[   0.,   -1, 1./8, 1./8],
735     [ 1./8, 1./8, 1./8,   0.],
736     [   0., 1./8,   0.,   0.]]
737## This is Stevenson-Arce in hex lattice
738#ERROR_STAR = \
739#    [[      0.,      0.,      0.,      -1,      0.,  32./200,      0.],
740#     [ 12./200,      0., 26./200,      0., 30./200,       0., 16./200],
741#     [      0., 12./200,      0., 26./200,      0.,  12./200,      0.],
742#     [  5./200,      0., 12./200,      0., 12./200,       0.,  5./200]]
743## This is an attempt at implementing Stevenson-Arce in square lattice
744#ERROR_STAR = \
745#    [[      0.,      0.,      -1, 32./200,      0.],
746#     [  6./200, 19./200, 28./200, 23./200,  8./200],
747#     [      0., 12./200, 26./200, 12./200,      0.],
748#     [  2./200,  9./200, 12./200,  9./200,  2./200]]
749
750if chapter(3):
751    test3xx(lenna256bw, ERROR_NAIVE, False).save("out3-0-1.png")
752    test3xx(gradient256bw, ERROR_NAIVE, False).save("grad3-0-1.png")
753
754    test3xx(lenna256bw, ERROR_FSTEIN, False).save("out3-1-1.png")
755    test3xx(gradient256bw, ERROR_FSTEIN, False).save("grad3-1-1.png")
756    test3xx(lenna256bw, ERROR_FSTEIN, True).save("out3-1-2.png")
757    test3xx(gradient256bw, ERROR_FSTEIN, True).save("grad3-1-2.png")
758
759    test3xx(lenna256bw, ERROR_FAN, False).save("out3-2-1.png")
760    test3xx(gradient256bw, ERROR_FAN, False).save("grad3-2-1.png")
761    test3xx(lenna256bw, ERROR_SHIAUFAN, False).save("out3-2-1b.png")
762    test3xx(gradient256bw, ERROR_SHIAUFAN, False).save("grad3-2-1b.png")
763    test3xx(lenna256bw, ERROR_SHIAUFAN2, False).save("out3-2-1c.png")
764    test3xx(gradient256bw, ERROR_SHIAUFAN2, False).save("grad3-2-1c.png")
765
766    test3xx(lenna256bw, ERROR_JAJUNI, False).save("out3-2-2.png")
767    test3xx(gradient256bw, ERROR_JAJUNI, False).save("grad3-2-2.png")
768
769    test3xx(lenna256bw, ERROR_STUCKI, False).save("out3-2-3.png")
770    test3xx(gradient256bw, ERROR_STUCKI, False).save("grad3-2-3.png")
771
772    test3xx(lenna256bw, ERROR_BURKES, False).save("out3-2-4.png")
773    test3xx(gradient256bw, ERROR_BURKES, False).save("grad3-2-4.png")
774
775    test3xx(lenna256bw, ERROR_SIERRA, False).save("out3-2-5.png")
776    test3xx(gradient256bw, ERROR_SIERRA, False).save("grad3-2-5.png")
777
778    test3xx(lenna256bw, ERROR_SIERRA2, False).save("out3-2-6.png")
779    test3xx(gradient256bw, ERROR_SIERRA2, False).save("grad3-2-6.png")
780
781    test3xx(lenna256bw, ERROR_FILTERLITE, False).save("out3-2-7.png")
782    test3xx(gradient256bw, ERROR_FILTERLITE, False).save("grad3-2-7.png")
783
784    test3xx(lenna256bw, ERROR_ATKINSON, False).save("out3-2-8.png")
785    test3xx(gradient256bw, ERROR_ATKINSON, False).save("grad3-2-8.png")
786
787    #test3xx(lenna256bw, ERROR_STAR, False).save("out3-2-9.png")
788    #test3xx(gradient256bw, ERROR_STAR, False).save("grad3-2-9.png")
789
790    #test3xx(lenna256bw, ERROR_STAR, False).save("out3-2-9.png")
791    #test3xx(gradient256bw, ERROR_STAR, False).save("grad3-2-9.png")
792
793# Output 3-3-1: Floyd-Steinberg on grey 90%
794# Output 3-3-2: serpentine Floyd-Steinberg on grey 90%
795if chapter(3):
796    tmp = Image((128, 128))
797    for y in range(128):
798        for x in range(128):
799            tmp.setGray(x, y, 0.90)
800    test3xx(tmp, ERROR_FSTEIN, False).getZoom(2).save("out3-3-1.png")
801    test3xx(tmp, ERROR_FSTEIN, True).getZoom(2).save("out3-3-2.png")
802
803# Output 3-4-1: Ostromoukhov’s variable error diffusion
804def test341(src, serpentine):
805    m = [[13, 0, 5], [13, 0, 5], [21, 0, 10], [7, 0, 4],
806         [8, 0, 5], [47, 3, 28], [23, 3, 13], [15, 3, 8],
807         [22, 6, 11], [43, 15, 20], [7, 3, 3], [501, 224, 211],
808         [249, 116, 103], [165, 80, 67], [123, 62, 49], [489, 256, 191],
809         [81, 44, 31], [483, 272, 181], [60, 35, 22], [53, 32, 19],
810         [237, 148, 83], [471, 304, 161], [3, 2, 1], [481, 314, 185],
811         [354, 226, 155], [1389, 866, 685], [227, 138, 125], [267, 158, 163],
812         [327, 188, 220], [61, 34, 45], [627, 338, 505], [1227, 638, 1075],
813         [20, 10, 19], [1937, 1000, 1767], [977, 520, 855], [657, 360, 551],
814         [71, 40, 57], [2005, 1160, 1539], [337, 200, 247], [2039, 1240, 1425],
815         [257, 160, 171], [691, 440, 437], [1045, 680, 627], [301, 200, 171],
816         [177, 120, 95], [2141, 1480, 1083], [1079, 760, 513], [725, 520, 323],
817         [137, 100, 57], [2209, 1640, 855], [53, 40, 19], [2243, 1720, 741],
818         [565, 440, 171], [759, 600, 209], [1147, 920, 285], [2311, 1880, 513],
819         [97, 80, 19], [335, 280, 57], [1181, 1000, 171], [793, 680, 95],
820         [599, 520, 57], [2413, 2120, 171], [405, 360, 19], [2447, 2200, 57],
821         [11, 10, 0], [158, 151, 3], [178, 179, 7], [1030, 1091, 63],
822         [248, 277, 21], [318, 375, 35], [458, 571, 63], [878, 1159, 147],
823         [5, 7, 1], [172, 181, 37], [97, 76, 22], [72, 41, 17],
824         [119, 47, 29], [4, 1, 1], [4, 1, 1], [4, 1, 1],
825         [4, 1, 1], [4, 1, 1], [4, 1, 1], [4, 1, 1],
826         [4, 1, 1], [4, 1, 1], [65, 18, 17], [95, 29, 26],
827         [185, 62, 53], [30, 11, 9], [35, 14, 11], [85, 37, 28],
828         [55, 26, 19], [80, 41, 29], [155, 86, 59], [5, 3, 2],
829         [5, 3, 2], [5, 3, 2], [5, 3, 2], [5, 3, 2],
830         [5, 3, 2], [5, 3, 2], [5, 3, 2], [5, 3, 2],
831         [5, 3, 2], [5, 3, 2], [5, 3, 2], [5, 3, 2],
832         [305, 176, 119], [155, 86, 59], [105, 56, 39], [80, 41, 29],
833         [65, 32, 23], [55, 26, 19], [335, 152, 113], [85, 37, 28],
834         [115, 48, 37], [35, 14, 11], [355, 136, 109], [30, 11, 9],
835         [365, 128, 107], [185, 62, 53], [25, 8, 7], [95, 29, 26],
836         [385, 112, 103], [65, 18, 17], [395, 104, 101], [4, 1, 1]]
837    (w, h) = src.size()
838    dest = Image((w, h))
839    ey = [0.] * (w + 2)
840    for y in range(h):
841        ex = 0
842        newey = [0.] * (w + 2)
843        if serpentine and y & 1:
844            xrange = range(w - 1, -1, -1)
845        else:
846            xrange = range(w)
847        for x in xrange:
848            # Set pixel
849            c = src.getGray(x, y) + ex + ey[x + 1]
850            d = c > 0.5
851            dest.setGray(x, y, d)
852            error = c - d
853            i = (int)(c * 255.9999)
854            if i > 127:
855                i = 255 - i
856            (d1, d2, d3) = m[i]
857            t = d1 + d2 + d3
858            # Propagate error
859            ex = error * d1 / t
860            if serpentine and y & 1:
861                newey[x + 2] += error * d3 / t
862                newey[x + 1] += error * d2 / t
863            else:
864                newey[x] += error * d2 / t
865                newey[x + 1] += error * d3 / t
866        ey = newey
867    return dest
868
869if chapter(3):
870    test341(lenna256bw, True).save("out3-4-1.png")
871    test341(gradient256bw, True).save("grad3-4-1.png")
872
873##############################################################################
874if chapter(4):
875    print "Chapter 4. Grayscale dithering"
876
877# Output 4.0.1: 4x4 Bayer dithering, 3 colours
878def test401(src, mat):
879    (w, h) = src.size()
880    dest = Image((w, h))
881    dx = len(mat[0])
882    dy = len(mat)
883    for y in range(h):
884        for x in range(w):
885            c = src.getGray(x, y)
886            threshold = (1. + mat[y % dy][x % dx]) / (dx * dy + 1)
887            if c < 0.5:
888                c = 0.5 * (c > threshold / 2)
889            else:
890                c = 0.5 + 0.5 * (c > 0.5 + threshold / 2)
891            dest.setGray(x, y, c)
892    return dest
893
894if chapter(4):
895    test401(lenna256bw, DITHER_BAYER44).save("out4-0-1.png")
896    test401(gradient256bw, DITHER_BAYER44).save("grad4-0-1.png")
897
898# Output 4.0.2: standard Floyd-Steinberg, 3 colours
899def test402(src, mat, serpentine):
900    (w, h) = src.size()
901    dest = Image((w, h))
902    lines = len(mat)
903    rows = len(mat[0])
904    offset = mat[0].index(-1)
905    ey = [[0.] * (w + rows - 1) for x in range(lines)]
906    for y in range(h):
907        ex = [0.] * (rows - offset)
908        if serpentine and y & 1:
909            xrange = range(w - 1, -1, -1)
910        else:
911            xrange = range(w)
912        for x in xrange:
913            # Set pixel
914            c = src.getGray(x, y) + ex[0] + ey[0][x + offset]
915            d = 0.5 * (c > 0.25) + 0.5 * (c > 0.75)
916            dest.setGray(x, y, d)
917            error = c - d
918            # Propagate first line of error
919            for dx in range(rows - offset - 2):
920                ex[dx] = ex[dx + 1] + error * mat[0][offset + 1 + dx]
921            ex[rows - offset - 2] = error * mat[0][rows - 1]
922            # Propagate next lines
923            if serpentine and y & 1:
924                for dy in range(1, lines):
925                    for dx in range(rows):
926                        ey[dy][x + dx] += error * mat[dy][rows - 1 - dx]
927            else:
928                for dy in range(1, lines):
929                    for dx in range(rows):
930                        ey[dy][x + dx] += error * mat[dy][dx]
931        for dy in range(lines - 1):
932            ey[dy] = ey[dy + 1]
933        ey[lines - 1] = [0.] * (w + rows - 1)
934    return dest
935
936if chapter(4):
937    test402(lenna256bw, ERROR_FSTEIN, False).save("out4-0-2.png")
938    test402(gradient256bw, ERROR_FSTEIN, False).save("grad4-0-2.png")
939
940# Pattern 4.1.1: gamma-corrected 50% gray, black-white halftone, 50% gray
941if chapter(4):
942    dest = Image((240, 80))
943    for y in range(80):
944        for x in range(80):
945            dest.setGray(x, y, Gamma.ItoC(0.5))
946        for x in range(80, 160):
947            c = (x + y) & 1
948            dest.setGray(x, y, c)
949        for x in range(160, 240):
950            dest.setGray(x, y, 0.5)
951    dest.save("pat4-1-1.png")
952
953# Output 4.2.1: gamma-corrected 2-colour Floyd-Steinberg
954# Output 4.2.2: gamma-corrected 3-colour Floyd-Steinberg
955# Output 4.2.3: gamma-corrected 4-colour Floyd-Steinberg
956def test42x(src, mat, threshold):
957    (w, h) = src.size()
958    dest = Image((w, h))
959    lines = len(mat)
960    rows = len(mat[0])
961    offset = mat[0].index(-1)
962    ey = [[0.] * (w + rows - 1) for x in range(lines)]
963    for y in range(h):
964        ex = [0.] * (rows - offset)
965        for x in range(w):
966            # Set pixel
967            c = Gamma.CtoI(src.getGray(x, y)) + ex[0] + ey[0][x + offset]
968            d = threshold(c)
969            dest.setGray(x, y, Gamma.ItoC(d))
970            error = c - d
971            # Propagate first line of error
972            for dx in range(rows - offset - 2):
973                ex[dx] = ex[dx + 1] + error * mat[0][offset + 1 + dx]
974            ex[rows - offset - 2] = error * mat[0][rows - 1]
975            # Propagate next lines
976            for dy in range(1, lines):
977                for dx in range(rows):
978                    ey[dy][x + dx] += error * mat[dy][dx]
979        for dy in range(lines - 1):
980            ey[dy] = ey[dy + 1]
981        ey[lines - 1] = [0.] * (w + rows - 1)
982    return dest
983
984if chapter(4):
985    test42x(lenna256bw, ERROR_FSTEIN, Gamma.Cto2).save("out4-2-1.png")
986    test42x(gradient256bw, ERROR_FSTEIN, Gamma.Cto2).save("grad4-2-1.png")
987    test42x(lenna256bw, ERROR_FSTEIN, Gamma.Cto3).save("out4-2-2.png")
988    test42x(gradient256bw, ERROR_FSTEIN, Gamma.Cto3).save("grad4-2-2.png")
989    test42x(lenna256bw, ERROR_FSTEIN, Gamma.Cto4).save("out4-2-3.png")
990    test42x(gradient256bw, ERROR_FSTEIN, Gamma.Cto4).save("grad4-2-3.png")
991
992##############################################################################
993if chapter(5):
994    print "Chapter 5. Colour dithering"
995
996# Pattern 5.1.1: 8-colour palette
997if chapter(5):
998    dest = Image((512, 64))
999    for x in range(512):
1000        d = x / 64
1001        r = (d & 2) >> 1
1002        g = (d & 4) >> 2
1003        b = d & 1
1004        for y in range(64):
1005            dest.setRgb(x, y, r, g, b)
1006    dest.save("pat5-1-1.png")
1007
1008# Output 5.1.1: 8-colour Floyd-Steinberg RGB dithering
1009# Output 5.1.2: 8-colour gamma-corrected Floyd-Steinberg RGB dithering
1010def test51x(src, mat, func):
1011    (w, h) = src.size()
1012    dest = Image((w, h))
1013    tmp = [Image((w, h)), Image((w, h)), Image((w, h))]
1014    for y in range(h):
1015        for x in range(w):
1016            rgb = src.getRgb(x, y)
1017            for i in range(3):
1018                tmp[i].setGray(x, y, rgb[i])
1019    for i in range(3):
1020        tmp[i] = func(tmp[i], mat, Gamma.Cto2)
1021    for y in range(h):
1022        for x in range(w):
1023            (r, g, b) = [tmp[i].getGray(x, y) for i in range(3)]
1024            dest.setRgb(x, y, r, g, b)
1025    return dest
1026
1027if chapter(5):
1028    test51x(lenna256, ERROR_FSTEIN, test3xx).save("out5-1-1.png")
1029    out512 = test51x(lenna256, ERROR_FSTEIN, test42x)
1030    out512.save("out5-1-2.png")
1031
1032# Pattern 5.2.1: different colours give the same result
1033def chapter5():
1034    dest = Image((320, 160))
1035    for x in range(80):
1036        for y in range(80):
1037            r = DITHER_BAYER44[(y / 8) % 4][(x / 8) % 4] > 7
1038            g = DITHER_BAYER44[(y / 8) % 4][(x / 8) % 4] > 13
1039            b = DITHER_BAYER44[(y / 8) % 4][(x / 8) % 4] > 13
1040            dest.setRgb(x, y, b, g, r)
1041        for y in range(80, 160):
1042            r = DITHER_BAYER44[y % 4][x % 4] > 7
1043            g = DITHER_BAYER44[y % 4][x % 4] > 13
1044            b = DITHER_BAYER44[y % 4][x % 4] > 13
1045            dest.setRgb(x, y, b, g, r)
1046    for x in range(80, 160):
1047        for y in range(80):
1048            r = DITHER_BAYER44[(y / 8) % 4][(x / 8) % 4] > 7
1049            g = DITHER_BAYER44[(y / 8) % 4][(x / 8 + 1) % 4] > 13
1050            b = DITHER_BAYER44[(y / 8) % 4][(x / 8 + 1) % 4] > 13
1051            dest.setRgb(x, y, b, g, r)
1052        for y in range(80, 160):
1053            r = DITHER_BAYER44[y % 4][x % 4] > 7
1054            g = DITHER_BAYER44[y % 4][(x + 1) % 4] > 13
1055            b = DITHER_BAYER44[y % 4][(x + 1) % 4] > 13
1056            dest.setRgb(x, y, b, g, r)
1057    for x in range(160, 240):
1058        for y in range(80):
1059            r = DITHER_BAYER44[(y / 8 + 1) % 4][(x / 8 + 1) % 4] > 7
1060            g = DITHER_BAYER44[(y / 8) % 4][(x / 8) % 4] > 13
1061            b = DITHER_BAYER44[(y / 8 + 1) % 4][(x / 8) % 4] > 13
1062            dest.setRgb(x, y, b, g, r)
1063        for y in range(80, 160):
1064            r = DITHER_BAYER44[(y + 1) % 4][(x + 1) % 4] > 7
1065            g = DITHER_BAYER44[y % 4][x % 4] > 13
1066            b = DITHER_BAYER44[(y + 1) % 4][x % 4] > 13
1067            dest.setRgb(x, y, b, g, r)
1068    for x in range(240, 320):
1069        for y in range(80):
1070            r = DITHER_BAYER44[(y / 8 + 1) % 4][(x / 8) % 4] > 7
1071            g = DITHER_BAYER44[(y / 8) % 4][(x / 8) % 4] > 13
1072            b = DITHER_BAYER44[(y / 8) % 4][(x / 8 + 2) % 4] > 13
1073            dest.setRgb(x, y, b, g, r)
1074        for y in range(80, 160):
1075            r = DITHER_BAYER44[(y + 1) % 4][x % 4] > 7
1076            g = DITHER_BAYER44[y % 4][x % 4] > 13
1077            b = DITHER_BAYER44[y % 4][(x + 2) % 4] > 13
1078            dest.setRgb(x, y, b, g, r)
1079    dest.save("pat5-2-1.png")
1080
1081# Output 5.2.1: cropped 5.1.2
1082# Output 5.2.2: close-up of cropped 5.1.2
1083if chapter(5):
1084    tmp = out512.getRegion(20, 70, 32, 32)
1085    tmp.save("out5-2-1.png")
1086    tmp.getZoom(6).save("out5-2-2.png")
1087
1088    out523 = test51x(lenna256, ERROR_STUCKI, test42x)
1089    out523.save("out5-2-3.png")
1090    tmp = out523.getRegion(20, 70, 32, 32)
1091    tmp.save("out5-2-4.png")
1092    tmp.getZoom(6).save("out5-2-5.png")
1093
1094##############################################################################
1095if chapter(6):
1096    print "Chapter 6. Photographic mosaics"
1097
1098# Output 6.0.1: create a mosaic from Lenna
1099def mosaic_split(src, tnw, tnh):
1100    random.seed(0)
1101    thumbs = []
1102    (w, h) = src.size()
1103    sw = w / tnw
1104    sh = h / tnh
1105    for y in range(sh):
1106        for x in range(sw):
1107            thumbs.append(src.getRegion(x * tnw, y * tnh, tnw, tnh))
1108    random.shuffle(thumbs)
1109    return thumbs
1110
1111def mosaic_analyse(tnlist, dx, dy):
1112    coeffs = []
1113    for (n, img) in enumerate(tnlist):
1114        tmp = [[[0] * 3 for x in range(dx)] for y in range(dy)]
1115        (w, h) = img.size()
1116        for y in range(h):
1117            my = y * dy / h
1118            for x in range(w):
1119                mx = x * dx / w
1120                (r, g, b) = img.getRgb(x, y)
1121                tmp[my][mx][0] += Gamma.CtoI(r) / (w / dx * h / dy)
1122                tmp[my][mx][1] += Gamma.CtoI(g) / (w / dx * h / dy)
1123                tmp[my][mx][2] += Gamma.CtoI(b) / (w / dx * h / dy)
1124        coeffs.append(tmp)
1125    return coeffs
1126
1127def test601(tnlist, cols):
1128    (tnw, tnh) = tnlist[0].size()
1129    dw = cols
1130    dh = (len(tnlist) + cols - 1) / cols
1131    dest = Image((dw * tnw + 8 * (dw + 1), dh * tnh + 8 * (dh + 1)), True)
1132    for (n, img) in enumerate(tnlist):
1133        di = 8 + (n % dw) * (tnw + 8)
1134        dj = 8 + (n / dw) * (tnh + 8)
1135        img.copyTo(dest, (di, dj))
1136    return dest
1137
1138if chapter(6):
1139    tnlist = mosaic_split(lenna256, 32, 32)
1140    test601(tnlist, 10).save("out6-0-1.png")
1141
1142# Output 6.1.1: extract 1 colour feature from mosaic tiles
1143# Output 6.1.2: crop Lenna
1144# Output 6.1.3: generate a mosaic from the 1-feature database
1145# Output 6.1.4: extract 4 colour features from mosaic tiles
1146# Output 6.1.5: generate a mosaic from the 4-feature database
1147def test61x(coeffs, cols, tnw, tnh):
1148    dx = len(coeffs[0][0])
1149    dy = len(coeffs[0])
1150    dw = cols
1151    dh = (len(coeffs) + cols - 1) / cols
1152    dest = Image((dw * tnw + 8 * (dw + 1), dh * tnh + 8 * (dh + 1)), True)
1153    for (n, tab) in enumerate(coeffs):
1154        di = 8 + (n % dw) * (tnw + 8)
1155        dj = 8 + (n / dw) * (tnh + 8)
1156        for y in range(tnh):
1157            for x in range(tnw):
1158                (r, g, b) = tab[y * dy / tnh][x * dx / tnw]
1159                dest.setRgb(di + x, dj + y, Gamma.ItoC(r), Gamma.ItoC(g), Gamma.ItoC(b))
1160    return dest
1161
1162def test61y(src, sqw, sqh, tnlist, coeffs):
1163    (w, h) = src.size()
1164    (tnw, tnh) = tnlist[0].size()
1165    dx = len(coeffs[0][0])
1166    dy = len(coeffs[0])
1167    nx = w / sqw
1168    ny = h / sqh
1169    dest = Image((nx * tnw, ny * tnh), True)
1170    for Y in range(ny):
1171        for X in range(nx):
1172            # 1. create statistics about the current square
1173            cur = [[[0] * 3 for x in range(dx)] for y in range(dy)]
1174            for y in range(sqh):
1175                my = y * dy / sqh
1176                for x in range(sqw):
1177                    mx = x * dx / sqw
1178                    (r, g, b) = src.getRgb(X * sqw + x, Y * sqh + y)
1179                    cur[my][mx][0] += Gamma.CtoI(r) / (sqw / dx * sqh / dy)
1180                    cur[my][mx][1] += Gamma.CtoI(g) / (sqw / dx * sqh / dy)
1181                    cur[my][mx][2] += Gamma.CtoI(b) / (sqw / dx * sqh / dy)
1182            # 2. find the best mosaic part
1183            best = -1
1184            dist = 5.
1185            for (n, tmp) in enumerate(coeffs):
1186                d = 0
1187                for j in range(dy):
1188                    for i in range(dx):
1189                        for c in range(3):
1190                            t = cur[j][i][c] - tmp[j][i][c]
1191                            d += t * t
1192                if d < dist:
1193                    dist = d
1194                    best = n
1195            # 3. blit mosaic chunk
1196            tnlist[best].copyTo(dest, (X * tnw, Y * tnh))
1197    return dest
1198
1199if chapter(6):
1200    coeffs1x1 = mosaic_analyse(tnlist, 1, 1)
1201    test61x(coeffs1x1, 10, 8, 8).save("out6-1-1.png")
1202    out612 = lenna256.getRegion(100, 90, 80, 80)
1203    out612.save("out6-1-2.png")
1204    test61y(out612, 6, 6, tnlist, coeffs1x1).save("out6-1-3.png")
1205
1206    coeffs2x2 = mosaic_analyse(tnlist, 2, 2)
1207    test61x(coeffs2x2, 10, 16, 16).save("out6-1-4.png")
1208    test61y(out612, 6, 6, tnlist, coeffs2x2).save("out6-1-5.png")
1209
1210##############################################################################
1211print "Finished"
1212
1213# Place temporary cruft below this
1214sys.exit(0)
1215
1216# XXX: test -- ranked dither -- it SUCKS
1217def test26x(src, mat):
1218    (w, h) = src.size()
1219    dest = Image((w, h))
1220    dx = len(mat[0])
1221    dy = len(mat)
1222    for y in range(h / dy):
1223        for x in range(w / dx):
1224            # Step 1: get the pixels and count groups
1225            groups = {}
1226            for j in range(dy):
1227                for i in range(dx):
1228                    p = src.getGray(x * dx + i, y * dy + j)
1229                    if groups.has_key(p):
1230                        groups[p].append((i, j))
1231                    else:
1232                        groups[p] = [(i, j)]
1233            # Step 2: create the ranked dither
1234            ranked = [[0] * dx for j in range(dy)]
1235            for p, g in groups.items():
1236                n = (int)(round(p * len(g)))
1237                if not n:
1238                    continue
1239                v = [(mat[j][i], (i, j)) for (i, j) in g]
1240                v.sort()
1241                v = v[0 : n - 1]
1242                for (k, (i, j)) in v:
1243                    ranked[j][i] = 1
1244            # Step 3: blit the ranked dither
1245            for j in range(dy):
1246                for i in range(dx):
1247                    dest.setGray(x * dx + i, y * dy + j, ranked[j][i])
1248    return dest
1249
1250if chapter(2):
1251    #test26x(lenna256bw, DITHER_BAYER88).save("out2-6-1.png")
1252    #test26x(gradient256bw, DITHER_BAYER88).save("grad2-6-1.png")
1253    test26x(lenna256bw, DITHER_CLUSTER88).save("out2-6-1.png")
1254    test26x(gradient256bw, DITHER_CLUSTER88).save("grad2-6-1.png")
1255
Note: See TracBrowser for help on using the repository browser.