Changeset 2134


Ignore:
Timestamp:
Dec 12, 2007, 12:06:32 AM (12 years ago)
Author:
Sam Hocevar
Message:
  • Knuth's dot diffusion algorithm.
Location:
www/study
Files:
8 added
2 edited

Legend:

Unmodified
Added
Removed
  • www/study/part3.html

    r2133 r2134  
    288288<h3> 3.5. Dot diffusion </h3>
    289289
    290 <p> <b>TODO</b>: understand Knuth’s implementation of Dot diffusion. </p>
     290<p> Dot diffusion is an error diffusion method by Donald E. Knuth that uses
     291tileable matrices just like ordered dithering, except that only the cell
     292order is taken into account. For instance, in the following example, cell 25’s
     293error is propagated to cells 44, 36, 30, 34 and 49. With dot diffusion, 100%
     294of the error is distributed, and diagonal cells get half as much as directly
     295adjacent cells. </p>
     296
     297<p style="text-align: center;">
     298  <img src="fig3-5-1.png" width="240" height="240"
     299       class="matrix" alt="Atkinson" />
     300</p>
     301
     302<p> The initial result is not extraordinary. But Knuth suggests applying a
     303sharpen filter to the original image before applying dot diffusion. On the
     304right is the result of applying a sharpening value of 0.9 beforehands: </p>
     305
     306<p style="text-align: center;">
     307  <img src="out3-5-1.png" width="256" height="256"
     308       class="inline" alt="Dot diffusion" />
     309  <img src="grad3-5-1.png" width="32" height="256"
     310       class="inline" alt="Dot diffusion gradient" />
     311  <img src="out3-5-2.png" width="256" height="256"
     312       class="inline" alt="Dot diffusion" />
     313  <img src="grad3-5-2.png" width="32" height="256"
     314       class="inline" alt="Dot diffusion gradient" />
     315</p>
     316
     317<p> Finally, Knuth introduces a <i>zeta</i> value to deal with the size of
     318laser printer dots. It is useless on a computer screen, but we show it here
     319for the sake of completeness. This example shows <i>zeta = 0.2</i>: </p>
     320
     321<p style="text-align: center;">
     322  <img src="out3-5-3.png" width="256" height="256"
     323       class="inline" alt="Dot diffusion" />
     324  <img src="grad3-5-3.png" width="32" height="256"
     325       class="inline" alt="Dot diffusion gradient" />
     326</p>
    291327
    292328<div style="float: left;">
  • www/study/study.py

    r2133 r2134  
    801801    test3xx(tmp, ERROR_FSTEIN, True).getZoom(2).save("out3-3-2.png")
    802802
    803 # Output 3.4.1: Ostromoukhovs variable error diffusion
     803# Output 3.4.1: Ostromoukhov's variable error diffusion
    804804def test341(src, serpentine):
    805805    m = [[13, 0, 5], [13, 0, 5], [21, 0, 10], [7, 0, 4],
     
    871871    test341(gradient256bw, True).save("grad3-4-1.png")
    872872
    873 # Output 3.5.1: Knuth's variable error diffusion
     873# Output 3.5.1: Knuth's dot diffusion
     874def sharpen(src, sharpening):
     875    (w, h) = src.size()
     876    dest = Image((w, h))
     877    for y in range(h):
     878        for x in range(w):
     879            c = src.getGray(x, y)
     880            total = 0.
     881            for j in range(-1, 2):
     882                for i in range(-1, 2):
     883                    total += src.getGray(x + i, y + j)
     884            total /= 9.
     885            d = (c - sharpening * total) / (1.0 - sharpening)
     886            if d < 0.:
     887                d = 0.
     888            elif d > 1.:
     889                d = 1.
     890            dest.setGray(x, y, d)
     891    return dest
     892
     893def test351(src, mat, zeta):
     894    (w, h) = src.size()
     895    dest = Image((w, h))
     896    dx = len(mat[0])
     897    dy = len(mat)
     898    # 1. analyse matrix to get equivalence classes
     899    classes = [(0, 0)] * dx * dy
     900    for y in range(dy):
     901        for x in range(dx):
     902            classes[mat[y][x]] = (x, y)
     903    # 2. copy image
     904    img = [[src.getGray(x, y) for x in range(w)] for y in range(h)]
     905    aa = [[1.] * w for y in range(h)]
     906    # 3. parse all classes
     907    for (x0, y0) in classes:
     908        y = y0
     909        while y < h:
     910            x = x0
     911            while x < w:
     912                c = img[y][x]
     913                if aa[y][x] == 1.:
     914                    error = c + 4. * zeta
     915                else:
     916                    error = c - zeta
     917                    if x > 0 and aa[y][x-1] == 1.: error += zeta
     918                    if y > 0 and aa[y-1][x] == 1.: error += zeta
     919                    if x < w-1 and aa[y][x+1] == 1.: error += zeta
     920                    if y < h-1 and aa[y+1][x] == 1.: error += zeta
     921                if c + error < 1.:
     922                    aa[y][x] = 0.
     923                    if x > 0 and aa[y][x-1] == 1.: aa[y][x-1] = .5
     924                    if y > 0 and aa[y-1][x] == 1.: aa[y-1][x] = .5
     925                    if x < w-1 and aa[y][x+1] == 1.: aa[y][x+1] = .5
     926                    if y < h-1 and aa[y+1][x] == 1.: aa[y+1][x] = .5
     927                else:
     928                    error = c - 1.
     929                # Propagate first line of error
     930                total = 0
     931                err = []
     932                for (i, j, e) in [(-1, -1, 1), (0, -1, 2), (1, -1, 1),
     933                                  (-1,  0, 2),             (1, 0, 2),
     934                                  (-1,  1, 1), (0,  1, 2), (1, 1, 1)]:
     935                    if x + i < 0 or x + i >= w \
     936                        or y + j < 0 or y + j >= h:
     937                        continue
     938                    n = mat[(y + j) % dy][(x + i) % dx] - mat[y % dy][x % dx]
     939                    if n <= 0:
     940                        continue
     941                    err.append((i, j, e))
     942                    total += e
     943                for (i, j, e) in err:
     944                    img[y + j][x + i] += error * e / total
     945                x += dx
     946            y += dy
     947    # 4. copy image, replacing gray with white
     948    for y in range(h):
     949        for x in range(w):
     950            dest.setGray(x, y, aa[y][x] > 0.)
     951    return dest
     952
     953if chapter(3):
     954    test351(lenna256bw, DITHER_CLUSTER88, 0.).save("out3-5-1.png")
     955    test351(gradient256bw, DITHER_CLUSTER88, 0.).save("grad3-5-1.png")
     956    tmp = sharpen(lenna256bw, 0.9)
     957    test351(tmp, DITHER_CLUSTER88, 0.).save("out3-5-2.png")
     958    test351(tmp, DITHER_CLUSTER88, 0.2).save("out3-5-3.png")
     959    tmp = sharpen(gradient256bw, 0.9)
     960    test351(tmp, DITHER_CLUSTER88, 0.).save("grad3-5-2.png")
     961    test351(tmp, DITHER_CLUSTER88, 0.2).save("grad3-5-3.png")
    874962
    875963##############################################################################
Note: See TracChangeset for help on using the changeset viewer.