Changeset 2127


Ignore:
Timestamp:
Dec 6, 2007, 11:47:14 PM (12 years ago)
Author:
Sam Hocevar
Message:
  • Shiau-Fan patented dithering.
  • Ostromoukhov's variable coefficient error diffusion.
Location:
www/study
Files:
12 added
2 edited

Legend:

Unmodified
Added
Removed
  • www/study/part3.html

    r2125 r2127  
    8282<h3> 3.2. Floyd-Steinberg derivatives </h3>
    8383
    84 <p> <b>Fan dithering</b> is a slight modification of Floyd-Steinberg with a
    85 very similar matrix: </p>
     84<p> Zhigang Fan came up with several Floyd-Steinberg derivatives. <b>Fan
     85dithering</b> just moves one coefficient around: </p>
    8686
    8787<p style="text-align: center;">
     
    9393       class="inline" alt="Fan error diffusion gradient" />
    9494</p>
     95
     96<p> <b>Shiau-Fan dithering</b> use a family of matrices supposed to reduce
     97the apparition of artifacts usually seen with Floyd-Steinberg: </p>
     98
     99<p style="text-align: center;">
     100  <img src="fig3-2-1b.png" width="160" height="80"
     101       class="matrix" alt="Shiau-Fan" />
     102  <img src="out3-2-1b.png" width="256" height="256"
     103       class="inline" alt="Shiau-Fan error diffusion" />
     104  <img src="grad3-2-1b.png" width="32" height="256"
     105       class="inline" alt="Shiau-Fan error diffusion gradient" />
     106</p>
     107
     108<p style="text-align: center;">
     109  <img src="fig3-2-1c.png" width="200" height="80"
     110       class="matrix" alt="Shiau-Fan 2" />
     111  <img src="out3-2-1c.png" width="256" height="256"
     112       class="inline" alt="Shiau-Fan 2 error diffusion" />
     113  <img src="grad3-2-1c.png" width="32" height="256"
     114       class="inline" alt="Shiau-Fan 2 error diffusion gradient" />
     115</p>
     116
     117<p> By the way, these matrices are covered by Shiau’s and Fan’s
     118<a href="http://www.freepatentsonline.com/5353127.html">U.S. patent
     1195353127</a>. </p>
    95120
    96121<p> <b>Jarvis, Judice and Ninke dithering</b> uses a much more complex
     
    196221-->
    197222
    198 <h3> 3.3. Image parsing </h3>
     223<h3> 3.3. Image parsing direction </h3>
    199224
    200225<p> While image parsing order does not matter with ordered dithering, it can
     
    240265       class="inline" alt="serpentine Floyd-Steinberg" />
    241266  <img src="grad3-1-2.png" width="32" height="256"
    242        class="inline" alt="serpentine Floyd-Steinberggradient" />
     267       class="inline" alt="serpentine Floyd-Steinberg gradient" />
     268</p>
     269
     270<h3> 3.4. Variable coefficients error diffusion </h3>
     271
     272<p> Ostromoukhov’s variable coefficients error diffusion uses a small
     273matrix, which usually causes a lot of artifacts to appear. However, the
     274coefficients here vary according to the input value, and the list of 256
     275discrete value triplets for <i>d1</i>, <i>d2</i> and <i>d3</i> provided by
     276Ostromoukhov give pretty good results: </p>
     277
     278<p style="text-align: center;">
     279  <img src="fig3-4-1.png" width="120" height="80"
     280       class="matrix" alt="Atkinson" />
     281  <img src="out3-4-1.png" width="256" height="256"
     282       class="inline" alt="Ostromoukhov ED" />
     283  <img src="grad3-4-1.png" width="32" height="256"
     284       class="inline" alt="Ostromoukhov ED gradient" />
    243285</p>
    244286
  • www/study/study.py

    r2126 r2127  
    650650# FIXME: serpentine only works if rows == offset * 2 + 1
    651651# Output 3.2.1: Fan (modified Floyd-Steinberg)
     652# Output 3.2.1b: Shiau-Fan 1
     653# Output 3.2.1c: Shiau-Fan 2
    652654# Output 3.2.2: Jarvis, Judice and Ninke
    653655# Output 3-2-3: Stucki
     
    702704    [[    0.,    0.,    -1, 7./16],
    703705     [ 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.]]
    704712ERROR_JAJUNI = \
    705713    [[    0.,    0.,    -1, 7./48, 5./48],
     
    751759    test3xx(lenna256bw, ERROR_FAN, False).save("out3-2-1.png")
    752760    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")
    753765
    754766    test3xx(lenna256bw, ERROR_JAJUNI, False).save("out3-2-2.png")
     
    788800    test3xx(tmp, ERROR_FSTEIN, False).getZoom(2).save("out3-3-1.png")
    789801    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")
    790872
    791873##############################################################################
Note: See TracChangeset for help on using the changeset viewer.