# Changeset 2134Tweet

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

Unmodified
Removed
• ## www/study/part3.html

 r2133

3.5. Dot diffusion

TODO: understand Knuth’s implementation of Dot diffusion.

Dot diffusion is an error diffusion method by Donald E. Knuth that uses tileable matrices just like ordered dithering, except that only the cell order is taken into account. For instance, in the following example, cell 25’s error is propagated to cells 44, 36, 30, 34 and 49. With dot diffusion, 100% of the error is distributed, and diagonal cells get half as much as directly adjacent cells.

The initial result is not extraordinary. But Knuth suggests applying a sharpen filter to the original image before applying dot diffusion. On the right is the result of applying a sharpening value of 0.9 beforehands:

Finally, Knuth introduces a zeta value to deal with the size of laser printer dots. It is useless on a computer screen, but we show it here for the sake of completeness. This example shows zeta = 0.2:

• ## www/study/study.py

 r2133 test3xx(tmp, ERROR_FSTEIN, True).getZoom(2).save("out3-3-2.png") # Output 3.4.1: Ostromoukhov’s variable error diffusion # Output 3.4.1: Ostromoukhov's variable error diffusion def test341(src, serpentine): m = [[13, 0, 5], [13, 0, 5], [21, 0, 10], [7, 0, 4], test341(gradient256bw, True).save("grad3-4-1.png") # Output 3.5.1: Knuth's variable error diffusion # Output 3.5.1: Knuth's dot diffusion def sharpen(src, sharpening): (w, h) = src.size() dest = Image((w, h)) for y in range(h): for x in range(w): c = src.getGray(x, y) total = 0. for j in range(-1, 2): for i in range(-1, 2): total += src.getGray(x + i, y + j) total /= 9. d = (c - sharpening * total) / (1.0 - sharpening) if d < 0.: d = 0. elif d > 1.: d = 1. dest.setGray(x, y, d) return dest def test351(src, mat, zeta): (w, h) = src.size() dest = Image((w, h)) dx = len(mat[0]) dy = len(mat) # 1. analyse matrix to get equivalence classes classes = [(0, 0)] * dx * dy for y in range(dy): for x in range(dx): classes[mat[y][x]] = (x, y) # 2. copy image img = [[src.getGray(x, y) for x in range(w)] for y in range(h)] aa = [[1.] * w for y in range(h)] # 3. parse all classes for (x0, y0) in classes: y = y0 while y < h: x = x0 while x < w: c = img[y][x] if aa[y][x] == 1.: error = c + 4. * zeta else: error = c - zeta if x > 0 and aa[y][x-1] == 1.: error += zeta if y > 0 and aa[y-1][x] == 1.: error += zeta if x < w-1 and aa[y][x+1] == 1.: error += zeta if y < h-1 and aa[y+1][x] == 1.: error += zeta if c + error < 1.: aa[y][x] = 0. if x > 0 and aa[y][x-1] == 1.: aa[y][x-1] = .5 if y > 0 and aa[y-1][x] == 1.: aa[y-1][x] = .5 if x < w-1 and aa[y][x+1] == 1.: aa[y][x+1] = .5 if y < h-1 and aa[y+1][x] == 1.: aa[y+1][x] = .5 else: error = c - 1. # Propagate first line of error total = 0 err = [] for (i, j, e) in [(-1, -1, 1), (0, -1, 2), (1, -1, 1), (-1,  0, 2),             (1, 0, 2), (-1,  1, 1), (0,  1, 2), (1, 1, 1)]: if x + i < 0 or x + i >= w \ or y + j < 0 or y + j >= h: continue n = mat[(y + j) % dy][(x + i) % dx] - mat[y % dy][x % dx] if n <= 0: continue err.append((i, j, e)) total += e for (i, j, e) in err: img[y + j][x + i] += error * e / total x += dx y += dy # 4. copy image, replacing gray with white for y in range(h): for x in range(w): dest.setGray(x, y, aa[y][x] > 0.) return dest if chapter(3): test351(lenna256bw, DITHER_CLUSTER88, 0.).save("out3-5-1.png") test351(gradient256bw, DITHER_CLUSTER88, 0.).save("grad3-5-1.png") tmp = sharpen(lenna256bw, 0.9) test351(tmp, DITHER_CLUSTER88, 0.).save("out3-5-2.png") test351(tmp, DITHER_CLUSTER88, 0.2).save("out3-5-3.png") tmp = sharpen(gradient256bw, 0.9) test351(tmp, DITHER_CLUSTER88, 0.).save("grad3-5-2.png") test351(tmp, DITHER_CLUSTER88, 0.2).save("grad3-5-3.png") ##############################################################################
Note: See TracChangeset for help on using the changeset viewer.