Changeset 2174


Ignore:
Timestamp:
Dec 29, 2007, 11:35:48 PM (14 years ago)
Author:
Sam Hocevar
Message:
  • Omni-directional error diffusion (a dot diffusion rip-off).
Location:
www/study
Files:
5 added
3 edited

Legend:

Unmodified
Added
Removed
  • www/study/part3.html

    r2173 r2174  
    213213-->
    214214
    215 <!--
    216 <p> There are countless other error diffusion techniques. However it appears
    217 quite clearly that the overall quality of these algorithms has reached so high
    218 a point that
    219 quite obvious that quality will hardly improve
    220 whatever blablah
    221 -->
    222 
    223215<h3> 3.3. Changing image parsing direction </h3>
    224216
     
    229221<p> The usual way to parse an image is one pixel after the other, following
    230222their order in memory. When reaching the end of a line, we automatically jump
    231 to the beginning of the next line: </p>
     223to the beginning of the next line. Error diffusion methods using this
     224parsing order are called <b>raster error diffusion</b>: </p>
    232225
    233226<p style="text-align: center;">
     
    322315
    323316<p> <b>Dot diffusion</b> is an error diffusion method by Donald E. Knuth that
    324 uses tileable matrices just like ordered dithering, except that only the cell
     317uses tileable matrices just like ordered dithering, except that the cell value
    325318order is taken into account for error propagation. Diagonal cells get half as
    326 much error as directly adjacent cells. </p>
     319much error as directly adjacent cells: </p>
     320
     321<p style="text-align: center;">
     322  <img src="fig3-3-7b.png" width="121" height="121"
     323       class="matrix" alt="Dot diffusion" />
     324</p>
    327325
    328326<p> For instance, in the following example, cell 25’s error is propagated to
     
    333331<p style="text-align: center;">
    334332  <img src="fig3-3-7.png" width="240" height="240"
    335        class="matrix" alt="Dot diffusion matrix" />
     333       class="matrix" alt="Dot diffusion matrix sample" />
    336334  <img src="out3-3-7.png" width="256" height="256"
    337335       class="inline" alt="Dot diffusion" />
     
    371369</p>
    372370
     371<p> Dot diffusion was reinvented 14 years later by Arney, Anderson and Ganawan
     372without crediting Knuth. They call their method <b>omni-directional error
     373diffusion</b>. Instead of using a clustered dot matrix like dot diffusion,
     374they use a dispersed dot matrix. This is a 16×12 portion of that matrix: </p>
     375
     376<p style="text-align: center;">
     377  <img src="fig3-3-11b.png" width="320" height="240"
     378       class="matrix" alt="omni-directional ED matrix sample" />
     379</p>
     380
     381<p> The recommended implementation of omni-directional error diffusion uses
     382a slightly different propagation matrix, where top and bottom neighbours get
     383more error than the others: </p>
     384
     385<p style="text-align: center;">
     386  <img src="fig3-3-11.png" width="121" height="121"
     387       class="matrix" alt="omni-directional ED" />
     388  <img src="out3-3-11.png" width="256" height="256"
     389       class="inline" alt="omni-directional ED" />
     390  <img src="grad3-3-11.png" width="32" height="256"
     391       class="inline" alt="omni-directional ED gradient" />
     392</p>
     393
    373394<h3> 3.4. Variable coefficients error diffusion </h3>
    374395
     
    455476</p>
    456477
    457 <p> And this is block Floyd-Steinberg using a modified, weighed intra-block
    458 error distribution matrix: </p>
     478<p> And this is block Floyd-Steinberg using the same full set of blocks and
     479a modified, weighed intra-block error distribution matrix. The picture still
     480looks sharpened, but is significantly less noisy: </p>
    459481
    460482<p style="text-align: center;">
  • www/study/part5.html

    r2152 r2174  
    9090</p>
    9191
     92<p> Shaked, Arad, Fitzhugh and Sobel introduce the <b>minimum brightness
     93variation criterion</b> (MBVC), stating that in order to reduce halftone noise,
     94the halftone set which should be used to render the desired colour should be
     95the one whose brightness variation is minimal. </p>
     96
    9297<div style="float: left;">
    9398   <a href="part4.html">Greyscale dithering &lt;&lt;&lt;</a>
  • www/study/study.py

    r2173 r2174  
    11811181    return dest
    11821182
    1183 def test337(src, mat, zeta):
     1183def test337(src, mat, propagate, zeta):
    11841184    (w, h) = src.size()
    11851185    dest = Image((w, h))
    11861186    dx = len(mat[0])
    11871187    dy = len(mat)
    1188     # 1. analyse matrix to get equivalence classes
    1189     classes = [(0, 0)] * dx * dy
    1190     for y in range(dy):
    1191         for x in range(dx):
    1192             classes[mat[y][x]] = (x, y)
     1188    # 0. analyse diffusion matrix to speed up things later
     1189    diff = []
     1190    cx, cy = -1, -1
     1191    for y in range(len(propagate)):
     1192        for x in range(len(propagate[0])):
     1193            if propagate[y][x] == -1:
     1194                cx, cy = x, y
     1195    for y in range(len(propagate)):
     1196        for x in range(len(propagate[0])):
     1197            diff.append((x - cx, y - cy, propagate[y][x]))
     1198    # 1. analyse order matrix to get equivalence classes
     1199    nclasses = 0
     1200    for l in mat:
     1201        for v in l:
     1202            if v + 1 > nclasses:
     1203                nclasses = v + 1
     1204    classes = [[] for n in range(nclasses)]
     1205    for y in range(h):
     1206        for x in range(w):
     1207            classes[mat[y % dy][x % dx]].append((x, y))
    11931208    # 2. copy image
    11941209    img = [[src.getGray(x, y) for x in range(w)] for y in range(h)]
    11951210    aa = [[1.] * w for y in range(h)]
    11961211    # 3. parse all classes
    1197     for (x0, y0) in classes:
    1198         y = y0
    1199         while y < h:
    1200             x = x0
    1201             while x < w:
    1202                 c = img[y][x]
    1203                 if aa[y][x] == 1.:
    1204                     error = c + 4. * zeta
    1205                 else:
    1206                     error = c - zeta
    1207                     if x > 0 and aa[y][x-1] == 1.: error += zeta
    1208                     if y > 0 and aa[y-1][x] == 1.: error += zeta
    1209                     if x < w-1 and aa[y][x+1] == 1.: error += zeta
    1210                     if y < h-1 and aa[y+1][x] == 1.: error += zeta
    1211                 if c + error < 1.:
    1212                     aa[y][x] = 0.
    1213                     if x > 0 and aa[y][x-1] == 1.: aa[y][x-1] = .5
    1214                     if y > 0 and aa[y-1][x] == 1.: aa[y-1][x] = .5
    1215                     if x < w-1 and aa[y][x+1] == 1.: aa[y][x+1] = .5
    1216                     if y < h-1 and aa[y+1][x] == 1.: aa[y+1][x] = .5
    1217                 else:
    1218                     error = c - 1.
    1219                 # Propagate first line of error
    1220                 total = 0
    1221                 err = []
    1222                 for (i, j, e) in [(-1, -1, 1), (0, -1, 2), (1, -1, 1),
    1223                                   (-1,  0, 2),             (1, 0, 2),
    1224                                   (-1,  1, 1), (0,  1, 2), (1, 1, 1)]:
    1225                     if x + i < 0 or x + i >= w \
    1226                         or y + j < 0 or y + j >= h:
    1227                         continue
    1228                     n = mat[(y + j) % dy][(x + i) % dx] - mat[y % dy][x % dx]
    1229                     if n <= 0:
    1230                         continue
    1231                     err.append((i, j, e))
    1232                     total += e
    1233                 for (i, j, e) in err:
    1234                     img[y + j][x + i] += error * e / total
    1235                 x += dx
    1236             y += dy
     1212    for l in classes:
     1213        for x, y in l:
     1214            c = img[y][x]
     1215            if aa[y][x] == 1.:
     1216                error = c + 4. * zeta
     1217            else:
     1218                error = c - zeta
     1219                if x > 0 and aa[y][x-1] == 1.: error += zeta
     1220                if y > 0 and aa[y-1][x] == 1.: error += zeta
     1221                if x < w-1 and aa[y][x+1] == 1.: error += zeta
     1222                if y < h-1 and aa[y+1][x] == 1.: error += zeta
     1223            if c + error < 1.:
     1224                aa[y][x] = 0.
     1225                if x > 0 and aa[y][x-1] == 1.: aa[y][x-1] = .5
     1226                if y > 0 and aa[y-1][x] == 1.: aa[y-1][x] = .5
     1227                if x < w-1 and aa[y][x+1] == 1.: aa[y][x+1] = .5
     1228                if y < h-1 and aa[y+1][x] == 1.: aa[y+1][x] = .5
     1229            else:
     1230                error = c - 1.
     1231            # Propagate first line of error
     1232            total = 0
     1233            err = []
     1234            for (i, j, e) in diff:
     1235                if x + i < 0 or x + i >= w \
     1236                    or y + j < 0 or y + j >= h:
     1237                    continue
     1238                n = mat[(y + j) % dy][(x + i) % dx] - mat[y % dy][x % dx]
     1239                if n <= 0:
     1240                    continue
     1241                err.append((i, j, e))
     1242                total += e
     1243            for (i, j, e) in err:
     1244                img[y + j][x + i] += error * e / total
    12371245    # 4. copy image, replacing gray with white
    12381246    for y in range(h):
     
    12411249    return dest
    12421250
     1251ERROR_DOT = \
     1252    [[1./12, 1./6, 1./12],
     1253     [ 1./6,   -1,  1./6],
     1254     [1./12, 1./6, 1./12]]
     1255
    12431256if chapter(3):
    1244     test337(lenna256bw, DITHER_CLUSTER88, 0.).save("out3-3-7.png")
    1245     test337(gradient256bw, DITHER_CLUSTER88, 0.).save("grad3-3-7.png")
     1257    Svg(ERROR_DOT).save("fig3-3-7b.png", 40)
     1258    test337(lenna256bw, DITHER_CLUSTER88, ERROR_DOT, 0.).save("out3-3-7.png")
     1259    test337(gradient256bw, DITHER_CLUSTER88, ERROR_DOT, 0.).save("grad3-3-7.png")
    12461260    tmp = sharpen(lenna256bw, 0.9)
    1247     test337(tmp, DITHER_CLUSTER88, 0.).save("out3-3-8.png")
    1248     test337(tmp, DITHER_CLUSTER88, 0.2).save("out3-3-9.png")
     1261    test337(tmp, DITHER_CLUSTER88, ERROR_DOT, 0.).save("out3-3-8.png")
     1262    test337(tmp, DITHER_CLUSTER88, ERROR_DOT, 0.2).save("out3-3-9.png")
    12491263    test3xx(tmp, ERROR_FSTEIN, True).save("out3-3-10.png")
    12501264    tmp = sharpen(gradient256bw, 0.9)
    1251     test337(tmp, DITHER_CLUSTER88, 0.).save("grad3-3-8.png")
    1252     test337(tmp, DITHER_CLUSTER88, 0.2).save("grad3-3-9.png")
     1265    test337(tmp, DITHER_CLUSTER88, ERROR_DOT, 0.).save("grad3-3-8.png")
     1266    test337(tmp, DITHER_CLUSTER88, ERROR_DOT, 0.2).save("grad3-3-9.png")
    12531267    test3xx(tmp, ERROR_FSTEIN, True).save("grad3-3-10.png")
     1268
     1269# Output 3.3.11: omni-directional error diffusion
     1270def test3311(src):
     1271    w, h = src.size()
     1272    g = { 0: 0, 1: 1, 2: 1 }
     1273    g[-1] = g[2] - g[1]
     1274    g[-2] = g[1] - g[0]
     1275    n = 2
     1276    while g[n] < w and g[n] < h:
     1277        n += 1
     1278        g[n] = g[n - 1] + g[n - 3]
     1279        g[-n] = g[-n + 3] - g[-n + 2]
     1280    u = g[n - 2]
     1281    v = g[n - 1]
     1282    a = [[(i * u + j * v) % g[n] for i in range(g[n])] for j in range(g[n])]
     1283    return a
     1284
     1285ERROR_OMNI = \
     1286    [[0.1, 0.2, 0.1],
     1287     [0.1,  -1, 0.1],
     1288     [0.1, 0.2, 0.1]]
     1289
     1290if chapter(3):
     1291    Svg(ERROR_OMNI).save("fig3-3-11.png", 40)
     1292
     1293    mat = test3311(lenna256bw)
     1294    tmp = [[str(mat[y][x]) for x in range(16)] for y in range(12)]
     1295    for x in range(16): tmp[11][x] = '...'
     1296    for y in range(12): tmp[y][15] = '...'
     1297    Svg(tmp).save("fig3-3-11b.png", 20)
     1298    test337(lenna256bw, mat, ERROR_OMNI, 0.).save("out3-3-11.png")
     1299
     1300    mat = test3311(gradient256bw)
     1301    test337(gradient256bw, mat, ERROR_OMNI, 0.).save("grad3-3-11.png")
    12541302
    12551303# Output 3.4.1: Ostromoukhov's variable error diffusion
Note: See TracChangeset for help on using the changeset viewer.