Changeset 1933 for www


Ignore:
Timestamp:
Nov 11, 2007, 1:27:49 PM (13 years ago)
Author:
Sam Hocevar
Message:
  • Floyd-Steinberg derivatives.
Location:
www/study
Files:
12 added
4 edited
1 copied

Legend:

Unmodified
Added
Removed
  • www/study/fig005.svg

    r1931 r1933  
    5757     inkscape:groupmode="layer"
    5858     id="layer1">
     59    <rect
     60       style="fill:#cccccc;fill-opacity:1;stroke:none;stroke-width:2;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
     61       id="rect2186"
     62       width="59.657413"
     63       height="59.8069"
     64       x="155"
     65       y="177.36218" />
    5966    <path
    6067       style="fill:none;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:round;stroke-miterlimit:4;stroke-dashoffset:0;stroke-opacity:1"
  • www/study/fig006.svg

    r1932 r1933  
    1515   inkscape:version="0.45.1"
    1616   sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study"
    17    sodipodi:docname="fig005.svg"
     17   sodipodi:docname="fig006.svg"
    1818   inkscape:output_extension="org.inkscape.output.svg.inkscape"
    19    inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig005.png"
    20    inkscape:export-xdpi="59.189999"
    21    inkscape:export-ydpi="59.189999">
     19   inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig006.png"
     20   inkscape:export-xdpi="59.19083"
     21   inkscape:export-ydpi="59.19083">
    2222  <defs
    2323     id="defs4" />
     
    3333     inkscape:pageshadow="2"
    3434     inkscape:zoom="1.979899"
    35      inkscape:cx="261.53318"
    36      inkscape:cy="854.65538"
     35     inkscape:cx="219.61185"
     36     inkscape:cy="850.61477"
    3737     inkscape:document-units="px"
    3838     inkscape:current-layer="layer1"
     
    5757     inkscape:groupmode="layer"
    5858     id="layer1">
     59    <rect
     60       style="fill:#cccccc;fill-opacity:1;stroke:none;stroke-width:2;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
     61       id="rect2186"
     62       width="59.657413"
     63       height="59.8069"
     64       x="155"
     65       y="177.36218" />
    5966    <path
    6067       style="fill:none;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:round;stroke-miterlimit:4;stroke-dashoffset:0;stroke-opacity:1"
    61        d="M 95,297.82287 L 275.20815,297.31779 L 275.46069,117.86726 L 95,117.36218 L 95,297.82287 z "
     68       d="M 35,297.82287 L 275.20815,297.31779 L 275.46069,117.86726 L 35,117.36218 L 35,297.82287 z "
    6269       id="rect2160"
    6370       sodipodi:nodetypes="ccccc" />
    6471    <path
    6572       style="fill:none;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:round;stroke-miterlimit:4;stroke-dashoffset:0;stroke-opacity:1;stroke-dasharray:none"
    66        d="M 95.407851,177.65386 L 274.52036,177.2725 M 154.92513,117.8526 L 155.42764,296.94494"
     73       d="M 35.407851,177.65386 L 274.52036,177.2725 M 94.92513,117.8526 L 95.42764,296.94494"
    6774       id="rect4103"
    6875       sodipodi:nodetypes="cccc" />
    6976    <path
    7077       style="fill:none;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:round;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
    71        d="M 274.52036,237.14368 L 95.407857,237.52504 M 215.00309,296.94494 L 214.50058,117.8526"
     78       d="M 274.52036,237.14368 L 35.407857,237.52504 M 215.00309,296.94494 L 214.50058,117.8526"
    7279       id="path3143"
    7380       sodipodi:nodetypes="cccc" />
     
    131138       xml:space="preserve"
    132139       style="font-size:21.27403641px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;writing-mode:lr-tb;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Serif"
    133        x="243.37863"
     140       x="63.378632"
    134141       y="259.62473"
    135142       id="text3201"
     
    137144         sodipodi:role="line"
    138145         id="tspan3203"
    139          x="243.37863"
     146         x="63.378632"
    140147         y="259.62473">1</tspan><tspan
    141148         sodipodi:role="line"
    142          x="243.37863"
     149         x="63.378632"
    143150         y="286.21727"
    144151         id="tspan3205">16</tspan></text>
     
    160167    <path
    161168       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
    162        d="M 227.67857,265.36218 L 262.5,265.36218"
     169       d="M 47.67857,265.36218 L 82.5,265.36218"
    163170       id="path3257"
    164171       sodipodi:nodetypes="cc" />
     
    207214         y="153.62473"
    208215         id="tspan2239">0</tspan></text>
     216    <path
     217       sodipodi:nodetypes="cc"
     218       id="path2187"
     219       d="M 154.92513,117.8526 L 155.42764,296.94494"
     220       style="fill:none;fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:round;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
     221    <text
     222       sodipodi:linespacing="125%"
     223       id="text2189"
     224       y="153.62473"
     225       x="65.378632"
     226       style="font-size:21.27403641px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;writing-mode:lr-tb;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Serif"
     227       xml:space="preserve"><tspan
     228         id="tspan2191"
     229         y="153.62473"
     230         x="65.378632"
     231         sodipodi:role="line">0</tspan></text>
     232    <text
     233       xml:space="preserve"
     234       style="font-size:21.27403641px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;writing-mode:lr-tb;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Serif"
     235       x="65.378632"
     236       y="213.62473"
     237       id="text2193"
     238       sodipodi:linespacing="125%"><tspan
     239         sodipodi:role="line"
     240         x="65.378632"
     241         y="213.62473"
     242         id="tspan2195">0</tspan></text>
     243    <text
     244       xml:space="preserve"
     245       style="font-size:21.27403641px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;writing-mode:lr-tb;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Serif"
     246       x="245.37863"
     247       y="273.62473"
     248       id="text2197"
     249       sodipodi:linespacing="125%"><tspan
     250         sodipodi:role="line"
     251         x="245.37863"
     252         y="273.62473"
     253         id="tspan2199">0</tspan></text>
    209254  </g>
    210255</svg>
  • www/study/index.html

    r1932 r1933  
    239239
    240240<p> There are two major issues with ordered dithering. First, important
    241 <b>visual artifacts</b> may appear. Even the Bayer ordered dithering causes
     241<b>visual artifacts</b> may appear. Even Bayer ordered dithering causes
    242242weird cross-hatch pattern artifacts on some images. Second, dithering
    243243matrices do not depend on the original image and thus <b>do not take input
    244 data into account</b>: high frequency features in the image is often missed
     244data into account</b>: high frequency features in the image are often missed
    245245and, in some cases, cause even worse artifacts. </p>
    246246
     
    254254<h3> 3.1. Floyd-Steinberg error diffusion </h3>
    255255
    256 <p> The most famous error diffusion method is the Floyd-Steinberg algorithm.
    257 It handles each pixel of the image one after the other and propagates the
    258 error to adjacent pixels: </p>
     256<p> The most famous error diffusion method is the <b>Floyd-Steinberg</b>
     257algorithm.  It handles each pixel of the image one after the other and
     258propagates the error to adjacent pixels: </p>
    259259
    260260<p style="text-align: center;">
     
    274274</p>
    275275
    276 <p> This is a variant called “serpentine Floyd-Steinberg” that parses every
    277 odd line right to left. The results is very close to the original
    278 Floyd-Steinberg, but avoids artifacts in some corner cases: </p>
     276<p> This is a variant called <b>serpentine Floyd-Steinberg</b> that parses
     277every odd line in reverse order (right to left). The results are very close
     278to the original Floyd-Steinberg, but avoid artifacts in some corner cases: </p>
    279279
    280280<p style="text-align: center;">
     
    285285</p>
    286286
     287<h3> 3.2. Floyd-Steinberg derivatives </h3>
     288
     289<p> <b>Fan dithering</b> is a slight modification of Floyd-Steinberg with a
     290very similar matrix: </p>
     291
     292<p style="text-align: center;">
     293  <img src="fig006.png" width="160" height="120"
     294       style="margin-right: 30px;" alt="Fan" />
     295  <img src="out012.png" width="256" height="256"
     296       class="inline" alt="Fan error diffusion" />
     297  <img src="grad012.png" width="32" height="256"
     298       class="inline" alt="Fan error diffusion gradient" />
     299</p>
     300
     301<p> <b>Jarvis, Judice and Ninke dithering</b> uses a much more complex
     302error diffusion matrix than Floyd-Steinberg: </p>
     303
     304<p style="text-align: center;">
     305  <img src="fig007.png" width="200" height="160"
     306       style="margin-right: 30px;" alt="Jarvis, Judice and Ninke" />
     307  <img src="out013.png" width="256" height="256"
     308       class="inline" alt="Jarvis, Judice and Ninke error diffusion" />
     309  <img src="grad013.png" width="32" height="256"
     310       class="inline" alt="Jarvis, Judice and Ninke error diffusion gradient" />
     311</p>
     312
     313<p> <b>Stucki dithering</b> is a slight variation of Jarvis, Judice and Ninke
     314dithering: </p>
     315
     316<p style="text-align: center;">
     317  <img src="fig008.png" width="200" height="160"
     318       style="margin-right: 30px;" alt="Stucki" />
     319  <img src="out014.png" width="256" height="256"
     320       class="inline" alt="Stucki error diffusion" />
     321  <img src="grad014.png" width="32" height="256"
     322       class="inline" alt="Stucki error diffusion gradient" />
     323</p>
    287324
    288325<!--
  • www/study/study.py

    r1932 r1933  
    204204    ep = [0.] * (w + 2)
    205205    for y in range(h):
    206         en = [0.] * (w + 2)
     206        ey = [0.] * (w + 2)
    207207        ex = 0
    208208        for x in range(w):
     
    212212            error = c - d
    213213            ex = error * 7. / 16.
    214             en[x] += error * 3. / 16.
    215             en[x + 1] += error * 5. / 16.
    216             en[x + 2] += error * 1. / 16.
    217         ep = en
     214            ey[x] += error * 3. / 16.
     215            ey[x + 1] += error * 5. / 16.
     216            ey[x + 2] += error * 1. / 16.
     217        ep = ey
    218218    dest.writePng(name)
    219219
     
    227227    ep = [0.] * (w + 2)
    228228    for z in range(h / 2):
    229         en = [0.] * (w + 2)
     229        ey = [0.] * (w + 2)
    230230        ex = 0
    231231        y = z * 2
     
    236236            error = c - d
    237237            ex = error * 7. / 16.
    238             en[x] += error * 3. / 16.
    239             en[x + 1] += error * 5. / 16.
    240             en[x + 2] += error * 1. / 16.
    241         ep = en
    242         en = [0.] * (w + 2)
     238            ey[x] += error * 3. / 16.
     239            ey[x + 1] += error * 5. / 16.
     240            ey[x + 2] += error * 1. / 16.
     241        ep = ey
     242        ey = [0.] * (w + 2)
    243243        ex = 0
    244244        y = z * 2 + 1
     
    249249            error = c - d
    250250            ex = error * 7. / 16.
    251             en[x] += error * 1. / 16.
    252             en[x + 1] += error * 5. / 16.
    253             en[x + 2] += error * 3. / 16.
    254         ep = en
     251            ey[x] += error * 1. / 16.
     252            ey[x + 1] += error * 5. / 16.
     253            ey[x + 2] += error * 3. / 16.
     254        ep = ey
    255255    dest.writePng(name)
    256256
    257257test6(lenna256bw, "out011.png")
    258258test6(gradient256bw, "grad011.png")
     259
     260# Output 12: Fan (modified Floyd-Steinberg)
     261def test7(src, name):
     262    (w, h) = src.size()
     263    dest = Image((w, h))
     264    ep = [0.] * (w + 3)
     265    for y in range(h):
     266        ey = [0.] * (w + 3)
     267        ex = 0
     268        for x in range(w):
     269            c = src.getGray(x, y) + ex + ep[x + 2]
     270            d = c > 0.5
     271            dest.setGray(x, y, d)
     272            error = c - d
     273            ex = error * 7. / 16.
     274            ey[x] += error * 1. / 16.
     275            ey[x + 1] += error * 3. / 16.
     276            ey[x + 2] += error * 5. / 16.
     277        ep = ey
     278    dest.writePng(name)
     279
     280test7(lenna256bw, "out012.png")
     281test7(gradient256bw, "grad012.png")
     282
     283# Output 13: Jarvis, Judice and Ninke
     284def test8(src, name):
     285    (w, h) = src.size()
     286    dest = Image((w, h))
     287    ep = [0.] * (w + 4)
     288    ey = [0.] * (w + 4)
     289    for y in range(h):
     290        ey2 = [0.] * (w + 4)
     291        ex = 0
     292        ex2 = 0
     293        for x in range(w):
     294            c = src.getGray(x, y) + ex + ep[x + 2]
     295            d = c > 0.5
     296            dest.setGray(x, y, d)
     297            error = c - d
     298            ex = ex2 + error * 7. / 48.
     299            ex2 = error * 5. / 48.
     300            ey[x] += error * 3. / 48.
     301            ey[x + 1] += error * 5. / 48.
     302            ey[x + 2] += error * 7. / 48.
     303            ey[x + 3] += error * 5. / 48.
     304            ey[x + 4] += error * 3. / 48.
     305            ey2[x] += error * 1. / 48.
     306            ey2[x + 1] += error * 3. / 48.
     307            ey2[x + 2] += error * 5. / 48.
     308            ey2[x + 3] += error * 3. / 48.
     309            ey2[x + 4] += error * 1. / 48.
     310        ep = ey
     311        ey = ey2
     312    dest.writePng(name)
     313
     314test8(lenna256bw, "out013.png")
     315test8(gradient256bw, "grad013.png")
     316
     317# Output 14: Stucki
     318# TODO: merge with Jarvis, Judice and Ninke
     319def test9(src, name):
     320    (w, h) = src.size()
     321    dest = Image((w, h))
     322    ep = [0.] * (w + 4)
     323    ey = [0.] * (w + 4)
     324    for y in range(h):
     325        ey2 = [0.] * (w + 4)
     326        ex = 0
     327        ex2 = 0
     328        for x in range(w):
     329            c = src.getGray(x, y) + ex + ep[x + 2]
     330            d = c > 0.5
     331            dest.setGray(x, y, d)
     332            error = c - d
     333            ex = ex2 + error * 8. / 42.
     334            ex2 = error * 4. / 42.
     335            ey[x] += error * 2. / 42.
     336            ey[x + 1] += error * 4. / 42.
     337            ey[x + 2] += error * 8. / 42.
     338            ey[x + 3] += error * 4. / 42.
     339            ey[x + 4] += error * 2. / 42.
     340            ey2[x] += error * 1. / 42.
     341            ey2[x + 1] += error * 2. / 42.
     342            ey2[x + 2] += error * 4. / 42.
     343            ey2[x + 3] += error * 2. / 42.
     344            ey2[x + 4] += error * 1. / 42.
     345        ep = ey
     346        ey = ey2
     347    dest.writePng(name)
     348
     349test9(lenna256bw, "out014.png")
     350test9(gradient256bw, "grad014.png")
    259351
    260352##############################################################################
Note: See TracChangeset for help on using the changeset viewer.