Changeset 1931 for www


Ignore:
Timestamp:
Nov 11, 2007, 1:27:43 PM (13 years ago)
Author:
Sam Hocevar
Message:
  • Started error diffusion part. Added Floyd-Steinberg.
Location:
www/study
Files:
4 added
2 edited

Legend:

Unmodified
Added
Removed
  • www/study/index.html

    r1930 r1931  
    187187</p>
    188188
    189 <h3> 2.3. Ordered dither </h3>
     189<h3> 2.3. Ordered dithering </h3>
    190190
    191191<p> A generalisation of the dithering technique we just saw that uses a
    192 certain family of patterns is called <b>ordered dither</b>. It is based on
     192certain family of patterns is called <b>ordered dithering</b>. It is based on
    193193a <b>dither matrix</b> such as the following one: </p>
    194194
     
    204204
    205205<p> Different matrices can give very different results. This is a 4×4
    206 Bayer ordered dither matrix: </p>
     206Bayer ordered dithering matrix: </p>
    207207
    208208<p style="text-align: center;">
     
    237237       class="inline" alt="4x4 cluster dot dithering gradient" />
    238238</p>
     239
     240<p> There are two major issues with ordered dithering. First, important
     241<b>visual artifacts</b> may appear. Even the Bayer ordered dithering causes
     242weird cross-hatch pattern artifacts on some images. Second, dithering
     243matrices do not depend on the original image and thus <b>do not take input
     244data into account</b>: high frequency features in the image is often missed
     245and, in some cases, cause even worse artifacts. </p>
     246
     247<h2> 3. Error diffusion </h2>
     248
     249<p> The idea behind error diffusion is to compute the error caused by
     250thresholding a given pixel and propagate it to neighbour pixels. </p>
     251
     252<h3> 3.1. Floyd-Steinberg error diffusion </h3>
     253
     254<p> The most famous error diffusion method is the Floyd-Steinberg algorithm.
     255It handles each pixel of the image one after the other and propagates the
     256error to adjacent pixels: </p>
     257
     258<p style="text-align: center;">
     259  <img src="fig005.png" width="120" height="120" alt="Floyd-Steinberg" />
     260</p>
     261
     262<p> The error is computed by simply substracting the source value and the
     263destination value. Destination value can be chosen by many means but does
     264not impact the image a lot compared to the error distribution coefficients
     265choice. Here is the result using a 0.5 threshold: </p>
     266
     267<p style="text-align: center;">
     268  <img src="out010.png" width="256" height="256"
     269       class="inline" alt="Floyd-Steinberg error diffusion" />
     270  <img src="grad010.png" width="32" height="256"
     271       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
     272</p>
     273
    239274
    240275<!--
  • www/study/study.py

    r1930 r1931  
    163163
    164164# Output 7: 4x4 Bayer dithering
     165# Output 8: 4x4 cluster dot
     166# Output 9: 5x3 line dithering
    165167def test4(src, mat, name):
    166168    (w, h) = src.size()
     
    195197test4(lenna256bw, mat, "out009.png")
    196198test4(gradient256bw, mat, "grad009.png")
     199
     200# Output 10: standard Floyd-Steinberg
     201def test5(src, name):
     202    (w, h) = src.size()
     203    dest = Image((w, h))
     204    ep = [0.] * (w + 2)
     205    for y in range(h):
     206        en = [0.] * (w + 2)
     207        #print 'ep:', ep
     208        #print 'en:', en
     209        ex = 0
     210        for x in range(w):
     211            c = src.getGray(x, y) + ex + ep[x + 1]
     212            d = c > 0.5
     213            dest.setGray(x, y, d)
     214            error = c - d
     215            ex = error * 7. / 16.
     216            en[x] += error * 3. / 16.
     217            en[x + 1] += error * 5. / 16.
     218            en[x + 2] += error * 1. / 16.
     219        ep = en
     220    dest.writePng(name)
     221
     222test5(lenna256bw, "out010.png")
     223test5(gradient256bw, "grad010.png")
    197224
    198225##############################################################################
Note: See TracChangeset for help on using the changeset viewer.