Changeset 2215


Ignore:
Timestamp:
Jan 25, 2008, 1:18:37 AM (14 years ago)
Author:
Sam Hocevar
Message:
  • Inserted a chapter 4, "Model-based dithering", between error diffusion and greyscale dithering.
Location:
www/study
Files:
21 added
9 deleted
21 edited
10 copied
29 moved

Legend:

Unmodified
Added
Removed

  • www/study/fig5-1-1.svg

    r2214 r2215  
    1717   version="1.0"
    1818   sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study"
    19    sodipodi:docname="fig4-1-1.svg"
     19   sodipodi:docname="fig5-1-1.svg"
    2020   inkscape:output_extension="org.inkscape.output.svg.inkscape"
    21    inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig4-1-1.png"
     21   inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig5-1-1.png"
    2222   inkscape:export-xdpi="90"
    2323   inkscape:export-ydpi="90">

  • www/study/fig5-1-2.svg

    r2214 r2215  
    1717   version="1.0"
    1818   sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study"
    19    sodipodi:docname="fig4-1-2.svg"
     19   sodipodi:docname="fig5-1-2.svg"
    2020   inkscape:output_extension="org.inkscape.output.svg.inkscape"
    21    inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig4-1-2.png"
     21   inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig5-1-2.png"
    2222   inkscape:export-xdpi="90"
    2323   inkscape:export-ydpi="90">

  • www/study/fig5-1-3.svg

    r2214 r2215  
    1717   version="1.0"
    1818   sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study"
    19    sodipodi:docname="fig4-1-3.svg"
     19   sodipodi:docname="fig5-1-3.svg"
    2020   inkscape:output_extension="org.inkscape.output.svg.inkscape"
    21    inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig4-1-3.png"
     21   inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig5-1-3.png"
    2222   inkscape:export-xdpi="90"
    2323   inkscape:export-ydpi="90">

  • www/study/fig5-3-1.svg

    r2214 r2215  
    1515   inkscape:version="0.45.1"
    1616   sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study"
    17    sodipodi:docname="fig4-3-1.svg"
     17   sodipodi:docname="fig5-3-1.svg"
    1818   inkscape:output_extension="org.inkscape.output.svg.inkscape"
    19    inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig4-3-1.png"
     19   inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig5-3-1.png"
    2020   inkscape:export-xdpi="30"
    2121   inkscape:export-ydpi="30">

  • www/study/fig6-1-7.svg

    r2214 r2215  
    1717   version="1.0"
    1818   sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study"
    19    sodipodi:docname="fig5-1-7.svg"
     19   sodipodi:docname="fig6-1-7.svg"
    2020   inkscape:output_extension="org.inkscape.output.svg.inkscape"
    21    inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig5-1-7.png"
     21   inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig6-1-7.png"
    2222   inkscape:export-xdpi="90"
    2323   inkscape:export-ydpi="90">
    … …  
    5656     inkscape:current-layer="svg83" />
    5757  <image
    58      xlink:href="out/fig5-1-1.png"
    59      sodipodi:absref="out/fig5-1-1.png"
     58     xlink:href="out/fig6-1-1.png"
     59     sodipodi:absref="out/fig6-1-1.png"
    6060     width="128"
    6161     height="128"
    … …  
    6464     y="-432" />
    6565  <image
    66      xlink:href="out/fig5-1-2c.png"
    67      sodipodi:absref="out/fig5-1-2c.png"
     66     xlink:href="out/fig6-1-2c.png"
     67     sodipodi:absref="out/fig6-1-2c.png"
    6868     width="128"
    6969     height="128"
    … …  
    7272     y="-432" />
    7373  <image
    74      xlink:href="out/fig5-1-3a.png"
    75      sodipodi:absref="out/fig5-1-3a.png"
     74     xlink:href="out/fig6-1-3a.png"
     75     sodipodi:absref="out/fig6-1-3a.png"
    7676     width="128"
    7777     height="128"
    … …  
    8080     y="-288" />
    8181  <image
    82      xlink:href="out/fig5-1-3b.png"
    83      sodipodi:absref="out/fig5-1-3b.png"
     82     xlink:href="out/fig6-1-3b.png"
     83     sodipodi:absref="out/fig6-1-3b.png"
    8484     width="128"
    8585     height="128"
    … …  
    8888     y="-288" />
    8989  <image
    90      xlink:href="out/fig5-1-3c.png"
    91      sodipodi:absref="out/fig5-1-3c.png"
     90     xlink:href="out/fig6-1-3c.png"
     91     sodipodi:absref="out/fig6-1-3c.png"
    9292     width="128"
    9393     height="128"
    … …  
    9696     y="-288" />
    9797  <image
    98      xlink:href="out/fig5-1-4a.png"
    99      sodipodi:absref="out/fig5-1-4a.png"
     98     xlink:href="out/fig6-1-4a.png"
     99     sodipodi:absref="out/fig6-1-4a.png"
    100100     width="128"
    101101     height="128"
    … …  
    104104     y="-144" />
    105105  <image
    106      xlink:href="out/fig5-1-4b.png"
    107      sodipodi:absref="out/fig5-1-4b.png"
     106     xlink:href="out/fig6-1-4b.png"
     107     sodipodi:absref="out/fig6-1-4b.png"
    108108     width="128"
    109109     height="128"
    … …  
    112112     y="-144" />
    113113  <image
    114      xlink:href="out/fig5-1-4c.png"
    115      sodipodi:absref="out/fig5-1-4c.png"
     114     xlink:href="out/fig6-1-4c.png"
     115     sodipodi:absref="out/fig6-1-4c.png"
    116116     width="128"
    117117     height="128"
    … …  
    120120     y="-144" />
    121121  <image
    122      xlink:href="out/fig5-1-5a.png"
    123      sodipodi:absref="out/fig5-1-5a.png"
     122     xlink:href="out/fig6-1-5a.png"
     123     sodipodi:absref="out/fig6-1-5a.png"
    124124     width="128"
    125125     height="128"
    … …  
    135135     inkscape:export-ydpi="90" />
    136136  <image
    137      xlink:href="out/fig5-1-2b.png"
    138      sodipodi:absref="out/fig5-1-2b.png"
     137     xlink:href="out/fig6-1-2b.png"
     138     sodipodi:absref="out/fig6-1-2b.png"
    139139     width="128"
    140140     height="128"
    … …  
    151151     inkscape:export-ydpi="90" />
    152152  <image
    153      xlink:href="out/fig5-1-2a.png"
    154      sodipodi:absref="out/fig5-1-2a.png"
     153     xlink:href="out/fig6-1-2a.png"
     154     sodipodi:absref="out/fig6-1-2a.png"
    155155     width="128"
    156156     height="128"
    … …  
    167167     inkscape:export-ydpi="90" />
    168168  <image
    169      xlink:href="out/fig5-1-6.png"
    170      sodipodi:absref="out/fig5-1-6.png"
     169     xlink:href="out/fig6-1-6.png"
     170     sodipodi:absref="out/fig6-1-6.png"
    171171     width="128"
    172172     height="128"
    … …  
    247247     style="stroke-width:3;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none" />
    248248  <image
    249      xlink:href="out/fig5-1-5b.png"
    250      sodipodi:absref="out/fig5-1-5b.png"
     249     xlink:href="out/fig6-1-5b.png"
     250     sodipodi:absref="out/fig6-1-5b.png"
    251251     width="128"
    252252     height="128"
    … …  
    264264     style="stroke-linejoin:miter;stroke-width:3;stroke-miterlimit:4;stroke-dasharray:none" />
    265265  <image
    266      xlink:href="out/fig5-1-5c.png"
    267      sodipodi:absref="out/fig5-1-5c.png"
     266     xlink:href="out/fig6-1-5c.png"
     267     sodipodi:absref="out/fig6-1-5c.png"
    268268     width="128"
    269269     height="128"

  • www/study/fig7-3-1.svg

    r2214 r2215  
    1616   inkscape:version="0.45.1"
    1717   sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study"
    18    sodipodi:docname="fig6-3-1.svg"
     18   sodipodi:docname="fig7-3-1.svg"
    1919   inkscape:output_extension="org.inkscape.output.svg.inkscape"
    20    inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig6-3-1.png"
     20   inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig7-3-1.png"
    2121   inkscape:export-xdpi="90"
    2222   inkscape:export-ydpi="90">

  • www/study/index.html

    r2211 r2215  
    100100    </ul>
    101101  </li>
    102   <li> <a href="part4.html">4. Greyscale dithering</a>
     102  <li> <a href="part4.html">4. Model-based dithering</a>
    103103    <ul>
    104       <li> 4.1. Introducing gamma </li>
    105       <li> 4.2. Gamma correction </li>
    106       <li> 4.3. Greyscale sub-block error diffusion </li>
     104      <li> 4.1. TODO </li>
    107105    </ul>
    108106  </li>
    109   <li> <a href="part5.html">5. Colour dithering</a>
     107  <li> <a href="part5.html">5. Greyscale dithering</a>
    110108    <ul>
    111       <li> 5.1. Separate-space dithering </li>
    112       <li> 5.2. Accounting for other dimensions </li>
    113       <li> 5.3. Reducing visual artifacts </li>
    114       <li> 5.4. Colour sub-block error diffusion </li>
     109      <li> 5.1. Introducing gamma </li>
     110      <li> 5.2. Gamma correction </li>
     111      <li> 5.3. Greyscale sub-block error diffusion </li>
    115112    </ul>
    116113  </li>
    117   <li> <a href="part6.html">6. Photographic mosaics</a>
     114  <li> <a href="part6.html">6. Colour dithering</a>
    118115    <ul>
    119       <li> 6.1. Image classification </li>
    120       <li> 6.2. Error diffusion </li>
    121       <li> 6.3. Colour ASCII art </li>
     116      <li> 6.1. Separate-space dithering </li>
     117      <li> 6.2. Accounting for other dimensions </li>
     118      <li> 6.3. Reducing visual artifacts </li>
     119      <li> 6.4. Colour sub-block error diffusion </li>
     120    </ul>
     121  </li>
     122  <li> <a href="part7.html">7. Photographic mosaics</a>
     123    <ul>
     124      <li> 7.1. Image classification </li>
     125      <li> 7.2. Error diffusion </li>
     126      <li> 7.3. Colour ASCII art </li>
    122127    </ul>
    123128  </li>

  • www/study/part3.html

    r2211 r2215  
    2929</div>
    3030<div style="float: right;">
    31    <a href="part4.html">&gt;&gt;&gt; Greyscale dithering</a>
     31   <a href="part4.html">&gt;&gt;&gt; Model-based dithering</a>
    3232</div>
    3333<div style="text-align: center;">
    … …  
    616616</p>
    617617
    618 <h3> 3.7. Direct binary search </h3>
    619 
    620 <p> We have already seen that standard error diffusion methods do not go back
    621 to pixels that have been set. <b>Direct binary search</b> [4] (DBS) is an
    622 iterative method that processes the image a fixed number of times, or until the
    623 error can no longer be minimised: </p>
    624 
    625 <ul>
    626   <li> Generate an initial dithered image </li>
    627   <li> Repeat until no changes can be applied:
    628     <ul>
    629       <li> Compute the global error between the original and the dithered
    630            images </li>
    631       <li> For each pixel in the dithered image:
    632         <ul>
    633           <li> Compute the effect on the error of toggling the value of the
    634                current pixel </li>
    635           <li> Compute the effect on the error of swapping the current pixel
    636                with one of its immediate neighbours </li>
    637           <li> If the error can be reduced, perform the corresponding
    638                action </li>
    639         </ul>
    640       </li>
    641     </ul>
    642   </li>
    643 </ul>
    644 
    645 <p> DBS relies on a <b>human visual system</b> model: instead of considering a
    646 local, pixel-bound error value, it tries to figure what the human eye really
    647 sees, by applying a filter to both the source and destination images, and then
    648 computes the error between these filtered signals. </p>
    649 
    650 <p> The efficiency and quality of DBS depend on many implementation details,
    651 starting with the HVS model. Also, the initial image used as iteration zero
    652 will give poor results if pattern artifacts are already present. And the order
    653 in which pixels are processed is important, too. Unfortunately, despite its
    654 very high-quality results, DBS is usually a very slow algorithm. </p>
    655 
    656 <p> Below is an example of the algorithm results. We use a 7×7 convolution
    657 kernel to approximate the human visual system, using a simplified luminance
    658 spatial frequency response formula:
    659 <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>. The initial image is
    660 randomly thresholded, and pixels are processed in raster order. Iterations 1,
    661 2 and 5 are shown: </p>
    662 
    663 <p style="text-align: center;">
    664   <img src="out/lena3-7-1.png" width="256" height="256"
    665        class="inline" alt="direct binary search, iteration 0" />
    666   <img src="out/grad3-7-1.png" width="32" height="256"
    667        class="inline" alt="direct binary search, iteration 0 gradient" />
    668   <img src="out/lena3-7-2.png" width="256" height="256"
    669        class="inline" alt="direct binary search, iteration 1" />
    670   <img src="out/grad3-7-2.png" width="32" height="256"
    671        class="inline" alt="direct binary search, iteration 1 gradient" />
    672 </p>
    673 
    674 <p style="text-align: center;">
    675   <img src="out/lena3-7-3.png" width="256" height="256"
    676        class="inline" alt="direct binary search, iteration 2" />
    677   <img src="out/grad3-7-3.png" width="32" height="256"
    678        class="inline" alt="direct binary search, iteration 2 gradient" />
    679   <img src="out/lena3-7-4.png" width="256" height="256"
    680        class="inline" alt="direct binary search, iteration 5" />
    681   <img src="out/grad3-7-4.png" width="32" height="256"
    682        class="inline" alt="direct binary search, iteration 5 gradient" />
    683 </p>
    684 
    685618<div style="float: left;">
    686619   <a href="part2.html">Halftoning &lt;&lt;&lt;</a>
    687620</div>
    688621<div style="float: right;">
    689    <a href="part4.html">&gt;&gt;&gt; Greyscale dithering</a>
     622   <a href="part4.html">&gt;&gt;&gt; Model-based dithering</a>
    690623</div>
    691624<div style="text-align: center;">

  • www/study/part4.html

    r2204 r2215  
    99   <meta name="GENERATOR" content="vim" />
    1010   <meta name="Author" content="sam@zoy.org (Sam Hocevar)" />
    11    <meta name="Description" content="Libcaca study - 4. Greyscale dithering" />
     11   <meta name="Description" content="Libcaca study - 4. Model-based dithering" />
    1212   <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" />
    13    <title>Libcaca study - 4. Greyscale dithering</title>
     13   <title>Libcaca study - 4. Model-based dithering</title>
    1414   <link rel="icon" type="image/x-icon" href="/favicon.ico" />
    1515   <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
    … …  
    2929</div>
    3030<div style="float: right;">
    31    <a href="part5.html">&gt;&gt;&gt; Colour dithering</a>
     31   <a href="part5.html">&gt;&gt;&gt; Greyscale dithering</a>
    3232</div>
    3333<div style="text-align: center;">
    … …  
    3535</div>
    3636
    37 <h2> 4. Greyscale dithering </h2>
     37<h2> 4. Model-based dithering </h2>
    3838
    39 <p> At first sight, generalising dithering to three grey scales seems pretty
    40 straightforward: just add grey 0.5 in the middle of the palette and dither
    41 pixels in the [0, 0.5] range with black and grey, and pixels in the [0.5, 1]
    42 range with grey and white. Here are two different results with 8×8 Bayer
    43 ordered dithering and with serpentine Floyd-Steinberg error diffusion: </p>
     39<p> TODO </p>
    4440
    45 <p style="text-align: center;">
    46   <img src="out/lena4-0-1.png" width="256" height="256"
    47        class="inline" alt="8×8 Bayer ordered dithering, 3 colours" />
    48   <img src="out/grad4-0-1.png" width="32" height="256"
    49        class="inline" alt="8×8 Bayer ordered dithering gradient, 3 colours" />
    50   <img src="out/lena4-0-2.png" width="256" height="256"
    51        class="inline" alt="serpentine FS error diffusion, 3 colours" />
    52   <img src="out/grad4-0-2.png" width="32" height="256"
    53        class="inline" alt="serpentine FS error diffusion gradient, 3 colours" />
    54 </p>
     41<h3> 4.2. Direct binary search </h3>
    5542
    56 <p> These are pretty much the images that imaging software such as The Gimp
    57 would give (using “positioned” and “Floyd-Steinberg” dithering modes). </p>
    58 
    59 <p> Unfortunately the result is not as good as expected: the white pattern
    60 on Lena’s cheeks is visually disturbing, and there is a lot of 0.5 grey in
    61 the image. Also, the whole image looks darker than with pure black-and-white
    62 dithering, but these previous dithering results looked a lot brighter than
    63 the original image anyway. </p>
    64 
    65 <p> All these issues have to do with the output media’s <b>gamma</b>. </p>
    66 
    67 <h3> 4.1. Introducing gamma </h3>
    68 
    69 <p> If you are reading this document on a computer screen, you may have
    70 noticed that the black and white 50% pattern was closer to a 0.73 greyscale
    71 (left) than to the intuitively expected 0.5 value (right). If you are reading
    72 a printed copy, it might be a different matter. </p>
    73 
    74 <p style="text-align: center;">
    75   <img src="out/pat4-1-1.png" width="240" height="80"
    76        class="inline" alt="introducing gamma" />
    77 </p>
    78 
    79 <p> The mapping linking greyscale steps to intensities is called <b>gamma
    80 correction</b>. An approximate law for gamma correction is given as
    81 <i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour
    82 value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
    83 0% and 100%) and <i>γ</i> is the gamma. A pattern made of even-numbered
    84 0%-intensity pixels and 100%-intensity pixels has an intensity of 50% by
    85 definition. But the corresponding greyscale depends on the gamma value. </p>
    86 
    87 <p> Most modern computer systems use the sRGB gamma model close to the law
    88 with <i>γ = 2.2</i>. As can be seen, it is highly non-linear: </p>
    89 
    90 <p style="text-align: center;">
    91   <img src="fig4-1-1.png" width="460" height="256" alt="introducing gamma" />
    92 </p>
    93 
    94 <p> Éric Brasseur wrote <a
    95 href="http://www.4p8.com/eric.brasseur/gamma.html">a pretty comprehensive
    96 essay</a> [16] about why on a computer screen a 50% black and white pattern
    97 should be scaled down to a grey value of 0.73 instead of 0.5 and how major
    98 computer graphics software totally misses the point. Conversely, it clearly
    99 means that a grey value of 0.5 should not be emulated with a 50% dither
    100 pattern. </p>
    101 
    102 <p> The following figure shows the gamma curve for the naïve three-colour
    103 greyscale gradient we saw above (red curve) compared to the two-colour
    104 gradient (blue curve). Two major observations can be made: the new curve is
    105 far closer to a perfect, linear gradient, but there is a singularity in the
    106 middle of the curve, meaning a break in the gradient’s smoothness. </p>
    107 
    108 <p style="text-align: center;">
    109   <img src="fig4-1-2.png" width="460" height="256" alt="3-colour gamma" />
    110 </p>
    111 
    112 <p> There are three possible ways to reduce the singularity and make the
    113 gradient smoother and/or closer to the original colours: </p>
     43<p> We have already seen that standard error diffusion methods do not go back
     44to pixels that have been set. <b>Direct binary search</b> [4] (DBS) is an
     45iterative method that processes the image a fixed number of times, or until the
     46error can no longer be minimised: </p>
    11447
    11548<ul>
    116   <li> Choose a different middle grey value, for instance choosing grey 0.73
    117        will cancel the singularity and match the two-colour gradients we have
    118        been using so far. This is not always possible if the output palette
    119        is fixed. </li>
    120   <li> Don’t place the grey value at the middle of the gradient, for instance
    121        a value of around 25% intensity will again match the previous two-colour
    122        gradients. </li>
    123   <li> <b>Gamma-correct</b> input pixels before assigning them an output
    124        value. This ensures that the resulting gradient is perfectly linear
    125        and has no singularity.
    126        </li>
     49  <li> Generate an initial dithered image </li>
     50  <li> Repeat until no changes can be applied:
     51    <ul>
     52      <li> Compute the global error between the original and the dithered
     53           images </li>
     54      <li> For each pixel in the dithered image:
     55        <ul>
     56          <li> Compute the effect on the error of toggling the value of the
     57               current pixel </li>
     58          <li> Compute the effect on the error of swapping the current pixel
     59               with one of its immediate neighbours </li>
     60          <li> If the error can be reduced, perform the corresponding
     61               action </li>
     62        </ul>
     63      </li>
     64    </ul>
     65  </li>
    12766</ul>
    12867
    129 <h3> 4.2. Gamma correction </h3>
     68<p> DBS relies on a <b>human visual system</b> model: instead of considering a
     69local, pixel-bound error value, it tries to figure what the human eye really
     70sees, by applying a filter to both the source and destination images, and then
     71computes the error between these filtered signals. </p>
    13072
    131 <p> Gamma correction consists in converting pixel values into intensity values
    132 before performing operations on them, then reconverting them to pixel values
    133 before displaying them. The exact same algorithms can be used, they just
    134 operate on slightly different data. </p>
     73<p> The efficiency and quality of DBS depend on many implementation details,
     74starting with the HVS model. Also, the initial image used as iteration zero
     75will give poor results if pattern artifacts are already present. And the order
     76in which pixels are processed is important, too. Unfortunately, despite its
     77very high-quality results, DBS is usually a very slow algorithm. </p>
    13578
    136 <p style="text-align: center;">
    137   <img src="fig4-1-3.png" width="460" height="256" alt="3-colour gamma coorection" />
    138 </p>
    139 
    140 <p> Here are the results of gamma-correcting input pixels before doing
    141 any computation on them, then using serpentine Floyd-Steinberg error
    142 diffusion: </p>
     79<p> Below is an example of the algorithm results. We use a 7×7 convolution
     80kernel to approximate the human visual system, using a simplified luminance
     81spatial frequency response formula:
     82<i>e<small><sup> -sqrt(x²+y²)</sup></small></i>. The initial image is
     83randomly thresholded, and pixels are processed in raster order. Iterations 1,
     842 and 5 are shown: </p>
    14385
    14486<p style="text-align: center;">
    14587  <img src="out/lena4-2-1.png" width="256" height="256"
    146        class="inline" alt="serpentine FS, 2 colours, gamma-corrected" />
     88       class="inline" alt="direct binary search, iteration 0" />
    14789  <img src="out/grad4-2-1.png" width="32" height="256"
    148        class="inline" alt="serpentine FS, 2 colours, gamma-corrected gradient" />
     90       class="inline" alt="direct binary search, iteration 0 gradient" />
    14991  <img src="out/lena4-2-2.png" width="256" height="256"
    150        class="inline" alt="serpentine FS, 3 colours, gamma-corrected" />
     92       class="inline" alt="direct binary search, iteration 1" />
    15193  <img src="out/grad4-2-2.png" width="32" height="256"
    152        class="inline" alt="serpentine FS, 3 colours, gamma-corrected gradient" />
     94       class="inline" alt="direct binary search, iteration 1 gradient" />
    15395</p>
    154 
    155 <p> Two-colour dithering is not visually satisfying: dark areas lack much
    156 detail because the gamma curve is very flat at low intensities. However,
    157 the result itself is far more accurate that previously. The problem, while
    158 still visible, is even less important with three-colour dithering: the image
    159 on the right is superior to what The Gimp or Adobe Photoshop are able to
    160 come up with. </p>
    161 
    162 <p> Finally, this is gamma-corrected 4-colour dithering: </p>
    16396
    16497<p style="text-align: center;">
    16598  <img src="out/lena4-2-3.png" width="256" height="256"
    166        class="inline" alt="serpentine FS, 4 colours, gamma-corrected" />
     99       class="inline" alt="direct binary search, iteration 2" />
    167100  <img src="out/grad4-2-3.png" width="32" height="256"
    168        class="inline" alt="serpentine FS, 4 colours, gamma-corrected gradient" />
    169 </p>
    170 
    171 <h3> 4.3. Greyscale sub-block error diffusion </h3>
    172 
    173 <p> Support for greyscale and gamma correction is trivially added to our
    174 sub-block error diffusion method. Best-tile choosing is done in contrast
    175 space, while error diffusion is done in intensity space. </p>
    176 
    177 <p> The following picture uses all possible 4-greyscale 2×2 tiles. The
    178 output quality is very close to what standard, pixel-per-pixel error diffusion
    179 achieves: </p>
    180 
    181 <p style="text-align: center;">
    182   <img src="out/lena4-3-1.png" width="256" height="256"
    183        class="inline" alt="sub-block FS, full 4-grey tiles" />
    184   <img src="out/grad4-3-1.png" width="32" height="256"
    185        class="inline" alt="sub-block FS, full 4-grey tiles gradient" />
    186 </p>
    187 
    188 <p> And finally, this picture only uses 4-greyscale combinations of the
    189 “lines” tiles seen previously: </p>
    190 
    191 <p style="text-align: center;">
    192   <img src="fig4-3-1.png" width="307" height="253"
    193        class="matrix" alt="list of 4-grey 2×2 pixel blocks" />
    194   <img src="out/lena4-3-2.png" width="256" height="256"
    195        class="inline" alt="sub-block FS, lines 4-grey tiles" />
    196   <img src="out/grad4-3-2.png" width="32" height="256"
    197        class="inline" alt="sub-block FS, lines 4-grey tiles gradient" />
     101       class="inline" alt="direct binary search, iteration 2 gradient" />
     102  <img src="out/lena4-2-4.png" width="256" height="256"
     103       class="inline" alt="direct binary search, iteration 5" />
     104  <img src="out/grad4-2-4.png" width="32" height="256"
     105       class="inline" alt="direct binary search, iteration 5 gradient" />
    198106</p>
    199107
    … …  
    202110</div>
    203111<div style="float: right;">
    204    <a href="part5.html">&gt;&gt;&gt; Colour dithering</a>
     112   <a href="part5.html">&gt;&gt;&gt; Greyscale dithering</a>
    205113</div>
    206114<div style="text-align: center;">

  • www/study/part5.html

    r2204 r2215  
    99   <meta name="GENERATOR" content="vim" />
    1010   <meta name="Author" content="sam@zoy.org (Sam Hocevar)" />
    11    <meta name="Description" content="Libcaca study - 5. Colour dithering" />
     11   <meta name="Description" content="Libcaca study - 5. Greyscale dithering" />
    1212   <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" />
    13    <title>Libcaca study - 5. Colour dithering</title>
     13   <title>Libcaca study - 5. Greyscale dithering</title>
    1414   <link rel="icon" type="image/x-icon" href="/favicon.ico" />
    1515   <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
    … …  
    2626
    2727<div style="float: left;">
    28    <a href="part4.html">Greyscale dithering &lt;&lt;&lt;</a>
     28   <a href="part4.html">Model-based dithering &lt;&lt;&lt;</a>
    2929</div>
    3030<div style="float: right;">
    31    <a href="part6.html">&gt;&gt;&gt; Photographic mosaics</a>
     31   <a href="part6.html">&gt;&gt;&gt; Colour dithering</a>
    3232</div>
    3333<div style="text-align: center;">
    … …  
    3535</div>
    3636
    37 <h2> 5. Colour dithering </h2>
    38 
    39 <p> Dithering colour images means dithering three-dimensional elements (RGB
    40 pixels) instead of one-dimensional grey values. It is very complex and
    41 depends on the output media even more than greyscale dithering. </p>
    42 
    43 <h3> 5.1. Separate-space dithering </h3>
    44 
    45 <p> In some cases it is possible to perform three one-dimensional dithering
    46 operations instead of one three-dimensional one. Consider for instance the
    47 following palette:
    48 </p>
    49 
    50 <p style="text-align: center;">
    51   <img src="out/pat5-1-1.png" width="512" height="64"
    52        class="inline" alt="8-colour RGB palette" />
    53 </p>
    54 
    55 <p> It is made of the eight possible red/green/blue combinations made of 0
    56 and 1 values: </p>
    57 
    58 <div style="text-align: center;">
    59   <table style="margin: auto;">
    60     <tr>
    61       <td><b>Red</b></td>
    62       <td>0</td> <td>0</td> <td>1</td> <td>1</td>
    63       <td>0</td> <td>0</td> <td>1</td> <td>1</td>
    64     </tr> <tr>
    65       <td><b>Green</b></td>
    66       <td>0</td> <td>0</td> <td>0</td> <td>0</td>
    67       <td>1</td> <td>1</td> <td>1</td> <td>1</td>
    68     </tr> <tr>
    69       <td><b>Blue</b></td>
    70       <td>0</td> <td>1</td> <td>0</td> <td>1</td>
    71       <td>0</td> <td>1</td> <td>0</td> <td>1</td>
    72     </tr>
    73   </table>
    74 </div>
    75 
    76 <p> One way of dithering an image using this palette is to convert the image
    77 into three greyscale images (separating the red, green and blue channels),
    78 dither each subimage to two colours separately and recombine the images into
    79 three channels. For instance, if at a given pixel the red channel is dithered
    80 to 1 and the green and blue channels are dithered to 0, the final pixel will
    81 be [1  0  0] which is the colour red. </p>
    82 
    83 <p> Separate-space dithering works by splitting the image into three red,
    84 green and blue channels. Each of this channel is treated as a greyscale image
    85 that is then dithered to black and white using any dithering method seen
    86 previously. The resulting images are then treated again as three red, green
    87 and blue channels and recombined into the final image: </p>
    88 
    89 <p style="text-align: center;">
    90   <img src="fig5-1-7.png" width="704" height="560"
    91        class="matrix" alt="separate-space dithering" />
    92 </p>
    93 
    94 <p> Here are the results with serpentine Floyd-Steinberg dithering applied to
    95 each channel. On the left, no colour correction, as The Gimp or Photoshop would
    96 do; on the right, gamma-corrected dithering: </p>
    97 
    98 <p style="text-align: center;">
    99   <img src="out/lena5-1-1.png" width="256" height="256"
    100        class="inline" alt="serpentine FS, 8 colours" />
    101   <img src="out/grad5-1-1.png" width="64" height="256"
    102        class="inline" alt="serpentine FS, 8 colours gradient" />
    103   <img src="out/lena5-1-2.png" width="256" height="256"
    104        class="inline" alt="serpentine FS, 8 colours, gamma-corrected" />
    105   <img src="out/grad5-1-2.png" width="64" height="256"
    106        class="inline" alt="serpentine FS, 8 colours, gamma-corrected gradient" />
    107 </p>
    108 
    109 <h3> 5.2. Accounting for other dimensions </h3>
    110 
    111 <p> The previous palette was suitable for separate-space dithering. Such a
    112 palette is called <b>separable</b> or <b>orthogonal</b>. </p>
    113 
    114 <p> Here is a palette that cannot be used in the same way: </p>
    115 
    116 <p style="text-align: center;">
    117   <img src="out/pat5-2-2.png" width="512" height="128"
    118        class="inline" alt="8-colour RGB palette" />
    119 </p>
    120 
    121 <p> As can be seen, it does not have the [0.5 0.5 0.5] grey colour, or the
    122 [1 0.5 0] orange colour, for instance, despite having other combinations of
    123 0, 0.5 and 1 values: </p>
    124 
    125 <div style="text-align: center;">
    126   <table style="margin: auto; border: 1px;">
    127     <tr>
    128       <td><b>Red</b></td>
    129       <td>0</td> <td>0</td> <td>0.5</td> <td>0.5</td>
    130       <td>0</td> <td>0</td> <td>0.5</td> <td>0.7</td>
    131       <td>0.3</td> <td>0</td> <td>1</td> <td>1</td>
    132       <td>0</td> <td>0</td> <td>1</td> <td>1</td>
    133     </tr> <tr>
    134       <td><b>Green</b></td>
    135       <td>0</td> <td>0</td> <td>0</td> <td>0</td>
    136       <td>0.5</td> <td>0.5</td> <td>0.5</td> <td>0.7</td>
    137       <td>0.3</td> <td>0</td> <td>0</td> <td>0</td>
    138       <td>1</td> <td>1</td> <td>1</td> <td>1</td>
    139     </tr> <tr>
    140       <td><b>Blue</b></td>
    141       <td>0</td> <td>0.5</td> <td>0</td> <td>0.5</td>
    142       <td>0</td> <td>0.5</td> <td>0</td> <td>0.7</td>
    143       <td>0.3</td> <td>1</td> <td>0</td> <td>1</td>
    144       <td>0</td> <td>1</td> <td>0</td> <td>1</td>
    145     </tr>
    146   </table>
    147 </div>
    148 
    149 <p> It is no longer possible to compute the closest colour in each colourspace
    150 and combine them into an RGB colour, since that colour might not be available
    151 in the palette. So we need to determine what the “closest colour” means when
    152 dealing with the whole colour spectrum. </p>
    153 
    154 <p> The following examples show gamma-corrected Floyd-Steinberg using the
    155 above 16-colour palette and two different definitions of distance: the <b>sum
    156 of absolute differences</b> and the <b>euclidian distance</b>. The sum of
    157 absolute differences performs pretty poorly because it does not penalise wide
    158 disparities: </p>
     37<h2> 5. Greyscale dithering </h2>
     38
     39<p> At first sight, generalising dithering to three grey scales seems pretty
     40straightforward: just add grey 0.5 in the middle of the palette and dither
     41pixels in the [0, 0.5] range with black and grey, and pixels in the [0.5, 1]
     42range with grey and white. Here are two different results with 8×8 Bayer
     43ordered dithering and with serpentine Floyd-Steinberg error diffusion: </p>
     44
     45<p style="text-align: center;">
     46  <img src="out/lena5-0-1.png" width="256" height="256"
     47       class="inline" alt="8×8 Bayer ordered dithering, 3 colours" />
     48  <img src="out/grad5-0-1.png" width="32" height="256"
     49       class="inline" alt="8×8 Bayer ordered dithering gradient, 3 colours" />
     50  <img src="out/lena5-0-2.png" width="256" height="256"
     51       class="inline" alt="serpentine FS error diffusion, 3 colours" />
     52  <img src="out/grad5-0-2.png" width="32" height="256"
     53       class="inline" alt="serpentine FS error diffusion gradient, 3 colours" />
     54</p>
     55
     56<p> These are pretty much the images that imaging software such as The Gimp
     57would give (using “positioned” and “Floyd-Steinberg” dithering modes). </p>
     58
     59<p> Unfortunately the result is not as good as expected: the white pattern
     60on Lena’s cheeks is visually disturbing, and there is a lot of 0.5 grey in
     61the image. Also, the whole image looks darker than with pure black-and-white
     62dithering, but these previous dithering results looked a lot brighter than
     63the original image anyway. </p>
     64
     65<p> All these issues have to do with the output media’s <b>gamma</b>. </p>
     66
     67<h3> 5.1. Introducing gamma </h3>
     68
     69<p> If you are reading this document on a computer screen, you may have
     70noticed that the black and white 50% pattern was closer to a 0.73 greyscale
     71(left) than to the intuitively expected 0.5 value (right). If you are reading
     72a printed copy, it might be a different matter. </p>
     73
     74<p style="text-align: center;">
     75  <img src="out/pat5-1-1.png" width="240" height="80"
     76       class="inline" alt="introducing gamma" />
     77</p>
     78
     79<p> The mapping linking greyscale steps to intensities is called <b>gamma
     80correction</b>. An approximate law for gamma correction is given as
     81<i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour
     82value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
     830% and 100%) and <i>γ</i> is the gamma. A pattern made of even-numbered
     840%-intensity pixels and 100%-intensity pixels has an intensity of 50% by
     85definition. But the corresponding greyscale depends on the gamma value. </p>
     86
     87<p> Most modern computer systems use the sRGB gamma model close to the law
     88with <i>γ = 2.2</i>. As can be seen, it is highly non-linear: </p>
     89
     90<p style="text-align: center;">
     91  <img src="fig5-1-1.png" width="460" height="256" alt="introducing gamma" />
     92</p>
     93
     94<p> Éric Brasseur wrote <a
     95href="http://www.4p8.com/eric.brasseur/gamma.html">a pretty comprehensive
     96essay</a> [16] about why on a computer screen a 50% black and white pattern
     97should be scaled down to a grey value of 0.73 instead of 0.5 and how major
     98computer graphics software totally misses the point. Conversely, it clearly
     99means that a grey value of 0.5 should not be emulated with a 50% dither
     100pattern. </p>
     101
     102<p> The following figure shows the gamma curve for the naïve three-colour
     103greyscale gradient we saw above (red curve) compared to the two-colour
     104gradient (blue curve). Two major observations can be made: the new curve is
     105far closer to a perfect, linear gradient, but there is a singularity in the
     106middle of the curve, meaning a break in the gradient’s smoothness. </p>
     107
     108<p style="text-align: center;">
     109  <img src="fig5-1-2.png" width="460" height="256" alt="3-colour gamma" />
     110</p>
     111
     112<p> There are three possible ways to reduce the singularity and make the
     113gradient smoother and/or closer to the original colours: </p>
     114
     115<ul>
     116  <li> Choose a different middle grey value, for instance choosing grey 0.73
     117       will cancel the singularity and match the two-colour gradients we have
     118       been using so far. This is not always possible if the output palette
     119       is fixed. </li>
     120  <li> Don’t place the grey value at the middle of the gradient, for instance
     121       a value of around 25% intensity will again match the previous two-colour
     122       gradients. </li>
     123  <li> <b>Gamma-correct</b> input pixels before assigning them an output
     124       value. This ensures that the resulting gradient is perfectly linear
     125       and has no singularity.
     126       </li>
     127</ul>
     128
     129<h3> 5.2. Gamma correction </h3>
     130
     131<p> Gamma correction consists in converting pixel values into intensity values
     132before performing operations on them, then reconverting them to pixel values
     133before displaying them. The exact same algorithms can be used, they just
     134operate on slightly different data. </p>
     135
     136<p style="text-align: center;">
     137  <img src="fig5-1-3.png" width="460" height="256" alt="3-colour gamma coorection" />
     138</p>
     139
     140<p> Here are the results of gamma-correcting input pixels before doing
     141any computation on them, then using serpentine Floyd-Steinberg error
     142diffusion: </p>
    159143
    160144<p style="text-align: center;">
    161145  <img src="out/lena5-2-1.png" width="256" height="256"
    162        class="inline" alt="Floyd-Steinberg, sum of absolute differences" />
    163   <img src="out/grad5-2-1.png" width="64" height="256"
    164        class="inline" alt="Floyd-Steinberg, sum of absolute differences gradient" />
     146       class="inline" alt="serpentine FS, 2 colours, gamma-corrected" />
     147  <img src="out/grad5-2-1.png" width="32" height="256"
     148       class="inline" alt="serpentine FS, 2 colours, gamma-corrected gradient" />
    165149  <img src="out/lena5-2-2.png" width="256" height="256"
    166        class="inline" alt="Floyd-Steinberg, euclidian distance" />
    167   <img src="out/grad5-2-2.png" width="64" height="256"
    168        class="inline" alt="Floyd-Steinberg, euclidian distance gradient" />
    169 </p>
    170 
    171 <p> Distances can be computed in another space. For instance, the <b>HSV
    172 space</b> allows to give colour variations a smaller influence than brightness
    173 variations simply by changing the HSV cone’s height. On the left is spatial
    174 Floyd-Steinberg using the euclidian distance in an HSV cone of height 1 and
    175 base radius 1. On the right is the same distance within a cone of height 3 and
    176 base radius 1: </p>
     150       class="inline" alt="serpentine FS, 3 colours, gamma-corrected" />
     151  <img src="out/grad5-2-2.png" width="32" height="256"
     152       class="inline" alt="serpentine FS, 3 colours, gamma-corrected gradient" />
     153</p>
     154
     155<p> Two-colour dithering is not visually satisfying: dark areas lack much
     156detail because the gamma curve is very flat at low intensities. However,
     157the result itself is far more accurate that previously. The problem, while
     158still visible, is even less important with three-colour dithering: the image
     159on the right is superior to what The Gimp or Adobe Photoshop are able to
     160come up with. </p>
     161
     162<p> Finally, this is gamma-corrected 4-colour dithering: </p>
    177163
    178164<p style="text-align: center;">
    179165  <img src="out/lena5-2-3.png" width="256" height="256"
    180        class="inline" alt="Floyd-Steinberg, 1×1 HSV cone" />
    181   <img src="out/grad5-2-3.png" width="64" height="256"
    182        class="inline" alt="Floyd-Steinberg, 1×1 HSV cone gradient" />
    183   <img src="out/lena5-2-4.png" width="256" height="256"
    184        class="inline" alt="Floyd-Steinberg, 3×1 HSV cone" />
    185   <img src="out/grad5-2-4.png" width="64" height="256"
    186        class="inline" alt="Floyd-Steinberg, 3×1 HSV cone gradient" />
    187 </p>
    188 
    189 <h3> 5.3. Reducing visual artifacts </h3>
    190 
    191 <p> The following patterns show four ways to dither the same colour using
    192 our 8-colour palette: </p>
    193 
    194 <ul>
    195   <li> 1/2 black, 3/8 blue, 1/8 white </li>
    196   <li> 1/2 blue, 3/8 black, 1/8 yellow </li>
    197   <li> 3/8 black, 3/8 blue, 1/8 red, 1/8 cyan </li>
    198   <li> 1/2 blue, 1/4 black, 1/8 red, 1/8 green </li>
    199 </ul>
    200 
    201 <p> All patterns visually blend to the same shade, but the last one is
    202 the most visually appealing: </p>
    203 
    204 <p style="text-align: center;">
    205   <img src="out/pat5-2-1.png" width="320" height="160"
    206        class="inline" alt="3 ways to dither the same colour" />
    207 </p>
    208 
    209 <p> Shaked, Arad, Fitzhugh and Sobel introduce the <b>minimum brightness
    210 variation criterion</b> (MBVC), stating that in order to reduce halftone noise,
    211 the halftone set which should be used to render the desired colour should be
    212 the one whose brightness variation is minimal [25]. Similarly, Klassen <i>et
    213 al.</i> suggest the selection of low-contrast colour combiation wherever
    214 possible [24]. </p>
    215 
    216 <h3> 5.4. Colour sub-block error diffusion </h3>
    217 
    218 <p> Adapting sub-block error diffusion to colour images is almost
    219 straightforward. The major problem is proper weighting in the block-choosing
    220 step. It is a crucial part of the algorithm, and we have yet to find an
    221 efficient method to perform it. </p>
    222 
    223 <p> The images below shows the result using our now well-known “lines” tile
    224 list, using respectively the 8-colour palette and the 16-colour palette: </p>
    225 
    226 <p style="text-align: center;">
    227   <img src="out/lena5-4-1.png" width="256" height="256"
    228        class="inline" alt="8-colour sub-block error diffusion" />
    229   <img src="out/grad5-4-1.png" width="64" height="256"
    230        class="inline" alt="8-colour sub-block error diffusion gradient" />
    231   <img src="out/lena5-4-2.png" width="256" height="256"
    232        class="inline" alt="16-colour sub-block error diffusion" />
    233   <img src="out/grad5-4-2.png" width="64" height="256"
    234        class="inline" alt="16-colour sub-block error diffusion gradient" />
    235 </p>
    236 
    237 <p> Speed is starting to become a problematic issue. A 16-colour palette can
    238 generate 65,536 unique 2×2 blocks. Exhaustive search to determine the best
    239 tile is no longer realistic, and we need to find better ways to find the
    240 best matching block. </p>
     166       class="inline" alt="serpentine FS, 4 colours, gamma-corrected" />
     167  <img src="out/grad5-2-3.png" width="32" height="256"
     168       class="inline" alt="serpentine FS, 4 colours, gamma-corrected gradient" />
     169</p>
     170
     171<h3> 5.3. Greyscale sub-block error diffusion </h3>
     172
     173<p> Support for greyscale and gamma correction is trivially added to our
     174sub-block error diffusion method. Best-tile choosing is done in contrast
     175space, while error diffusion is done in intensity space. </p>
     176
     177<p> The following picture uses all possible 4-greyscale 2×2 tiles. The
     178output quality is very close to what standard, pixel-per-pixel error diffusion
     179achieves: </p>
     180
     181<p style="text-align: center;">
     182  <img src="out/lena5-3-1.png" width="256" height="256"
     183       class="inline" alt="sub-block FS, full 4-grey tiles" />
     184  <img src="out/grad5-3-1.png" width="32" height="256"
     185       class="inline" alt="sub-block FS, full 4-grey tiles gradient" />
     186</p>
     187
     188<p> And finally, this picture only uses 4-greyscale combinations of the
     189“lines” tiles seen previously: </p>
     190
     191<p style="text-align: center;">
     192  <img src="fig5-3-1.png" width="307" height="253"
     193       class="matrix" alt="list of 4-grey 2×2 pixel blocks" />
     194  <img src="out/lena5-3-2.png" width="256" height="256"
     195       class="inline" alt="sub-block FS, lines 4-grey tiles" />
     196  <img src="out/grad5-3-2.png" width="32" height="256"
     197       class="inline" alt="sub-block FS, lines 4-grey tiles gradient" />
     198</p>
    241199
    242200<div style="float: left;">
    243    <a href="part4.html">Greyscale dithering &lt;&lt;&lt;</a>
     201   <a href="part4.html">Model-based dithering &lt;&lt;&lt;</a>
    244202</div>
    245203<div style="float: right;">
    246    <a href="part6.html">&gt;&gt;&gt; Photographic mosaics</a>
     204   <a href="part6.html">&gt;&gt;&gt; Colour dithering</a>
    247205</div>
    248206<div style="text-align: center;">

  • www/study/part6.html

    r2206 r2215  
    99   <meta name="GENERATOR" content="vim" />
    1010   <meta name="Author" content="sam@zoy.org (Sam Hocevar)" />
    11    <meta name="Description" content="Libcaca study - 6. Photographic mosaics" />
     11   <meta name="Description" content="Libcaca study - 6. Colour dithering" />
    1212   <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" />
    13    <title>Libcaca study - 6. Photographic mosaics</title>
     13   <title>Libcaca study - 6. Colour dithering</title>
    1414   <link rel="icon" type="image/x-icon" href="/favicon.ico" />
    1515   <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
    … …  
    2626
    2727<div style="float: left;">
    28    <a href="part5.html">Colour dithering &lt;&lt;&lt;</a>
     28   <a href="part5.html">Greyscale dithering &lt;&lt;&lt;</a>
    2929</div>
    3030<div style="float: right;">
    31    <a href="biblio.html">&gt;&gt;&gt; Bibliography</a>
     31   <a href="part7.html">&gt;&gt;&gt; Photographic mosaics</a>
    3232</div>
    3333<div style="text-align: center;">
    … …  
    3535</div>
    3636
    37 <h2> 6. Photographic mosaics </h2>
    38 
    39 <p> Photographic mosaics are montages of smaller images creating the illusion
    40 of a bigger image. </p>
    41 
    42 <p> Since we don’t have many images at our disposal, we will simply cut Lena
    43 into small chunks (called <b>tiles</b>) and use these parts to create mosaics.
    44 This is our <b>tile database</b>: </p>
    45 
    46 <p style="text-align: center;">
    47   <img src="out/lena6-0-1.png" width="408" height="288"
    48        class="inline" alt="Patterns taken from Lena" />
    49 </p>
    50 
    51 <p> Generating a photomosaic consists in subdividing the original picture
    52 into <i>x</i> rectangular cells and find <i>x</i> tiles in the database
    53 (with or without duplicates, depending on the set of rules that is decided)
    54 so that when recombined the resulting image resembles the original picture.
    55 By the way, this technique is covered by Runaway Technology Inc.’s
    56 <a href="http://www.freepatentsonline.com/6137498.html">U.S. patent
    57 6137498</a> [9]. </p>
    58 
    59 <p> Picking the right tile for the right cell in the grid is a very
    60 expensive and complicated operation. One of the biggest problems is the
    61 cost of a database lookup: comparing each tile area pixel-by-pixel
    62 is an O(N) operation where N is the size of the database. We can resort
    63 to <b>image classification</b> in order to speed up database lookups. </p>
    64 
    65 <h3> 6.1. Image classification </h3>
    66 
    67 <p> One of the simplest image classification techniques is the storage of
    68 each tile’s <b>average colour</b> into a separate database that is used for
    69 best match lookups. Of course, this computation should be gamma-corrected:
    70 </p>
    71 
    72 <p style="text-align: center;">
    73   <img src="out/lena6-1-1.png" width="168" height="120"
    74        class="inline" alt="1 feature extracted from Lena patterns" />
    75 </p>
    76 
    77 <p> When creating the mosaic, we then only need to check the average colour
    78 instead of comparing each pixel one by one. Below is the result of the
    79 technique applied on a portion of the Lena picture: </p>
    80 
    81 <p style="text-align: center;">
    82   <img src="out/lena6-1-2.png" width="80" height="80"
    83        class="inlinetop" alt="Lena (detail)" />
    84   <img src="out/lena6-1-3.png" width="416" height="416"
    85        class="inline" alt="Mosaic created from Lena’s detail" />
    86 </p>
    87 
    88 <p> Better results can be achieved by storing <b>four colour values</b>, one
    89 for each corner of the tile: </p>
    90 
    91 <p style="text-align: center;">
    92   <img src="out/lena6-1-4.png" width="248" height="176"
    93        class="inline" alt="4 features extracted from Lena patterns" />
    94 </p>
    95 
    96 <p> Having 12 values per tile (4 RGB triplets) is still a lot less than the
    97 original count of 3072 (for 32×32 tiles), and the results show clear
    98 improvement. For instance the feathers-hat frontier is now a lot smoother: </p>
    99 
    100 <p style="text-align: center;">
    101   <img src="out/lena6-1-2.png" width="80" height="80"
    102        class="inlinetop" alt="Lena (detail)" />
    103   <img src="out/lena6-1-5.png" width="416" height="416"
    104        class="inline" alt="Mosaic created from Lena’s detail" />
    105 </p>
    106 
    107 <h3> 6.2. Error diffusion </h3>
    108 
    109 <p> TODO </p>
    110 
    111 <h3> 6.3. Colour ASCII art </h3>
    112 
    113 <!--
    114 <p> We
    115 
    116    There are many ways to tackle the problem of colour ASCII art
    117 
    118 , also referred to as ANSI art,
    119 -->
    120 
    121 <p style="text-align: center;">
    122   <img src="fig6-3-1.png" width="395" height="196"
    123        class="matrix" alt="ASCII art tiles" />
    124 </p>
     37<h2> 6. Colour dithering </h2>
     38
     39<p> Dithering colour images means dithering three-dimensional elements (RGB
     40pixels) instead of one-dimensional grey values. It is very complex and
     41depends on the output media even more than greyscale dithering. </p>
     42
     43<h3> 6.1. Separate-space dithering </h3>
     44
     45<p> In some cases it is possible to perform three one-dimensional dithering
     46operations instead of one three-dimensional one. Consider for instance the
     47following palette:
     48</p>
     49
     50<p style="text-align: center;">
     51  <img src="out/pat6-1-1.png" width="512" height="64"
     52       class="inline" alt="8-colour RGB palette" />
     53</p>
     54
     55<p> It is made of the eight possible red/green/blue combinations made of 0
     56and 1 values: </p>
     57
     58<div style="text-align: center;">
     59  <table style="margin: auto;">
     60    <tr>
     61      <td><b>Red</b></td>
     62      <td>0</td> <td>0</td> <td>1</td> <td>1</td>
     63      <td>0</td> <td>0</td> <td>1</td> <td>1</td>
     64    </tr> <tr>
     65      <td><b>Green</b></td>
     66      <td>0</td> <td>0</td> <td>0</td> <td>0</td>
     67      <td>1</td> <td>1</td> <td>1</td> <td>1</td>
     68    </tr> <tr>
     69      <td><b>Blue</b></td>
     70      <td>0</td> <td>1</td> <td>0</td> <td>1</td>
     71      <td>0</td> <td>1</td> <td>0</td> <td>1</td>
     72    </tr>
     73  </table>
     74</div>
     75
     76<p> One way of dithering an image using this palette is to convert the image
     77into three greyscale images (separating the red, green and blue channels),
     78dither each subimage to two colours separately and recombine the images into
     79three channels. For instance, if at a given pixel the red channel is dithered
     80to 1 and the green and blue channels are dithered to 0, the final pixel will
     81be [1  0  0] which is the colour red. </p>
     82
     83<p> Separate-space dithering works by splitting the image into three red,
     84green and blue channels. Each of this channel is treated as a greyscale image
     85that is then dithered to black and white using any dithering method seen
     86previously. The resulting images are then treated again as three red, green
     87and blue channels and recombined into the final image: </p>
     88
     89<p style="text-align: center;">
     90  <img src="fig6-1-7.png" width="704" height="560"
     91       class="matrix" alt="separate-space dithering" />
     92</p>
     93
     94<p> Here are the results with serpentine Floyd-Steinberg dithering applied to
     95each channel. On the left, no colour correction, as The Gimp or Photoshop would
     96do; on the right, gamma-corrected dithering: </p>
     97
     98<p style="text-align: center;">
     99  <img src="out/lena6-1-1.png" width="256" height="256"
     100       class="inline" alt="serpentine FS, 8 colours" />
     101  <img src="out/grad6-1-1.png" width="64" height="256"
     102       class="inline" alt="serpentine FS, 8 colours gradient" />
     103  <img src="out/lena6-1-2.png" width="256" height="256"
     104       class="inline" alt="serpentine FS, 8 colours, gamma-corrected" />
     105  <img src="out/grad6-1-2.png" width="64" height="256"
     106       class="inline" alt="serpentine FS, 8 colours, gamma-corrected gradient" />
     107</p>
     108
     109<h3> 6.2. Accounting for other dimensions </h3>
     110
     111<p> The previous palette was suitable for separate-space dithering. Such a
     112palette is called <b>separable</b> or <b>orthogonal</b>. </p>
     113
     114<p> Here is a palette that cannot be used in the same way: </p>
     115
     116<p style="text-align: center;">
     117  <img src="out/pat6-2-2.png" width="512" height="128"
     118       class="inline" alt="8-colour RGB palette" />
     119</p>
     120
     121<p> As can be seen, it does not have the [0.5 0.5 0.5] grey colour, or the
     122[1 0.5 0] orange colour, for instance, despite having other combinations of
     1230, 0.5 and 1 values: </p>
     124
     125<div style="text-align: center;">
     126  <table style="margin: auto; border: 1px;">
     127    <tr>
     128      <td><b>Red</b></td>
     129      <td>0</td> <td>0</td> <td>0.5</td> <td>0.5</td>
     130      <td>0</td> <td>0</td> <td>0.5</td> <td>0.7</td>
     131      <td>0.3</td> <td>0</td> <td>1</td> <td>1</td>
     132      <td>0</td> <td>0</td> <td>1</td> <td>1</td>
     133    </tr> <tr>
     134      <td><b>Green</b></td>
     135      <td>0</td> <td>0</td> <td>0</td> <td>0</td>
     136      <td>0.5</td> <td>0.5</td> <td>0.5</td> <td>0.7</td>
     137      <td>0.3</td> <td>0</td> <td>0</td> <td>0</td>
     138      <td>1</td> <td>1</td> <td>1</td> <td>1</td>
     139    </tr> <tr>
     140      <td><b>Blue</b></td>
     141      <td>0</td> <td>0.5</td> <td>0</td> <td>0.5</td>
     142      <td>0</td> <td>0.5</td> <td>0</td> <td>0.7</td>
     143      <td>0.3</td> <td>1</td> <td>0</td> <td>1</td>
     144      <td>0</td> <td>1</td> <td>0</td> <td>1</td>
     145    </tr>
     146  </table>
     147</div>
     148
     149<p> It is no longer possible to compute the closest colour in each colourspace
     150and combine them into an RGB colour, since that colour might not be available
     151in the palette. So we need to determine what the “closest colour” means when
     152dealing with the whole colour spectrum. </p>
     153
     154<p> The following examples show gamma-corrected Floyd-Steinberg using the
     155above 16-colour palette and two different definitions of distance: the <b>sum
     156of absolute differences</b> and the <b>euclidian distance</b>. The sum of
     157absolute differences performs pretty poorly because it does not penalise wide
     158disparities: </p>
     159
     160<p style="text-align: center;">
     161  <img src="out/lena6-2-1.png" width="256" height="256"
     162       class="inline" alt="Floyd-Steinberg, sum of absolute differences" />
     163  <img src="out/grad6-2-1.png" width="64" height="256"
     164       class="inline" alt="Floyd-Steinberg, sum of absolute differences gradient" />
     165  <img src="out/lena6-2-2.png" width="256" height="256"
     166       class="inline" alt="Floyd-Steinberg, euclidian distance" />
     167  <img src="out/grad6-2-2.png" width="64" height="256"
     168       class="inline" alt="Floyd-Steinberg, euclidian distance gradient" />
     169</p>
     170
     171<p> Distances can be computed in another space. For instance, the <b>HSV
     172space</b> allows to give colour variations a smaller influence than brightness
     173variations simply by changing the HSV cone’s height. On the left is spatial
     174Floyd-Steinberg using the euclidian distance in an HSV cone of height 1 and
     175base radius 1. On the right is the same distance within a cone of height 3 and
     176base radius 1: </p>
     177
     178<p style="text-align: center;">
     179  <img src="out/lena6-2-3.png" width="256" height="256"
     180       class="inline" alt="Floyd-Steinberg, 1×1 HSV cone" />
     181  <img src="out/grad6-2-3.png" width="64" height="256"
     182       class="inline" alt="Floyd-Steinberg, 1×1 HSV cone gradient" />
     183  <img src="out/lena6-2-4.png" width="256" height="256"
     184       class="inline" alt="Floyd-Steinberg, 3×1 HSV cone" />
     185  <img src="out/grad6-2-4.png" width="64" height="256"
     186       class="inline" alt="Floyd-Steinberg, 3×1 HSV cone gradient" />
     187</p>
     188
     189<h3> 6.3. Reducing visual artifacts </h3>
     190
     191<p> The following patterns show four ways to dither the same colour using
     192our 8-colour palette: </p>
     193
     194<ul>
     195  <li> 1/2 black, 3/8 blue, 1/8 white </li>
     196  <li> 1/2 blue, 3/8 black, 1/8 yellow </li>
     197  <li> 3/8 black, 3/8 blue, 1/8 red, 1/8 cyan </li>
     198  <li> 1/2 blue, 1/4 black, 1/8 red, 1/8 green </li>
     199</ul>
     200
     201<p> All patterns visually blend to the same shade, but the last one is
     202the most visually appealing: </p>
     203
     204<p style="text-align: center;">
     205  <img src="out/pat6-2-1.png" width="320" height="160"
     206       class="inline" alt="3 ways to dither the same colour" />
     207</p>
     208
     209<p> Shaked, Arad, Fitzhugh and Sobel introduce the <b>minimum brightness
     210variation criterion</b> (MBVC), stating that in order to reduce halftone noise,
     211the halftone set which should be used to render the desired colour should be
     212the one whose brightness variation is minimal [25]. Similarly, Klassen <i>et
     213al.</i> suggest the selection of low-contrast colour combiation wherever
     214possible [24]. </p>
     215
     216<h3> 6.4. Colour sub-block error diffusion </h3>
     217
     218<p> Adapting sub-block error diffusion to colour images is almost
     219straightforward. The major problem is proper weighting in the block-choosing
     220step. It is a crucial part of the algorithm, and we have yet to find an
     221efficient method to perform it. </p>
     222
     223<p> The images below shows the result using our now well-known “lines” tile
     224list, using respectively the 8-colour palette and the 16-colour palette: </p>
     225
     226<p style="text-align: center;">
     227  <img src="out/lena6-4-1.png" width="256" height="256"
     228       class="inline" alt="8-colour sub-block error diffusion" />
     229  <img src="out/grad6-4-1.png" width="64" height="256"
     230       class="inline" alt="8-colour sub-block error diffusion gradient" />
     231  <img src="out/lena6-4-2.png" width="256" height="256"
     232       class="inline" alt="16-colour sub-block error diffusion" />
     233  <img src="out/grad6-4-2.png" width="64" height="256"
     234       class="inline" alt="16-colour sub-block error diffusion gradient" />
     235</p>
     236
     237<p> Speed is starting to become a problematic issue. A 16-colour palette can
     238generate 65,536 unique 2×2 blocks. Exhaustive search to determine the best
     239tile is no longer realistic, and we need to find better ways to find the
     240best matching block. </p>
    125241
    126242<div style="float: left;">
    127    <a href="part5.html">Colour dithering &lt;&lt;&lt;</a>
     243   <a href="part5.html">Greyscale dithering &lt;&lt;&lt;</a>
    128244</div>
    129245<div style="float: right;">
    130    <a href="biblio.html">&gt;&gt;&gt; Bibliography</a>
     246   <a href="part7.html">&gt;&gt;&gt; Photographic mosaics</a>
    131247</div>
    132248<div style="text-align: center;">

  • www/study/part7.html

    r2214 r2215  
    99   <meta name="GENERATOR" content="vim" />
    1010   <meta name="Author" content="sam@zoy.org (Sam Hocevar)" />
    11    <meta name="Description" content="Libcaca study - 6. Photographic mosaics" />
     11   <meta name="Description" content="Libcaca study - 7. Photographic mosaics" />
    1212   <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" />
    13    <title>Libcaca study - 6. Photographic mosaics</title>
     13   <title>Libcaca study - 7. Photographic mosaics</title>
    1414   <link rel="icon" type="image/x-icon" href="/favicon.ico" />
    1515   <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
    … …  
    2626
    2727<div style="float: left;">
    28    <a href="part5.html">Colour dithering &lt;&lt;&lt;</a>
     28   <a href="part6.html">Colour dithering &lt;&lt;&lt;</a>
    2929</div>
    3030<div style="float: right;">
    … …  
    3535</div>
    3636
    37 <h2> 6. Photographic mosaics </h2>
     37<h2> 7. Photographic mosaics </h2>
    3838
    3939<p> Photographic mosaics are montages of smaller images creating the illusion
    … …  
    4545
    4646<p style="text-align: center;">
    47   <img src="out/lena6-0-1.png" width="408" height="288"
     47  <img src="out/lena7-0-1.png" width="408" height="288"
    4848       class="inline" alt="Patterns taken from Lena" />
    4949</p>
    … …  
    6363to <b>image classification</b> in order to speed up database lookups. </p>
    6464
    65 <h3> 6.1. Image classification </h3>
     65<h3> 7.1. Image classification </h3>
    6666
    6767<p> One of the simplest image classification techniques is the storage of
    … …  
    7171
    7272<p style="text-align: center;">
    73   <img src="out/lena6-1-1.png" width="168" height="120"
     73  <img src="out/lena7-1-1.png" width="168" height="120"
    7474       class="inline" alt="1 feature extracted from Lena patterns" />
    7575</p>
    … …  
    8080
    8181<p style="text-align: center;">
    82   <img src="out/lena6-1-2.png" width="80" height="80"
     82  <img src="out/lena7-1-2.png" width="80" height="80"
    8383       class="inlinetop" alt="Lena (detail)" />
    84   <img src="out/lena6-1-3.png" width="416" height="416"
     84  <img src="out/lena7-1-3.png" width="416" height="416"
    8585       class="inline" alt="Mosaic created from Lena’s detail" />
    8686</p>
    … …  
    9090
    9191<p style="text-align: center;">
    92   <img src="out/lena6-1-4.png" width="248" height="176"
     92  <img src="out/lena7-1-4.png" width="248" height="176"
    9393       class="inline" alt="4 features extracted from Lena patterns" />
    9494</p>
    … …  
    9999
    100100<p style="text-align: center;">
    101   <img src="out/lena6-1-2.png" width="80" height="80"
     101  <img src="out/lena7-1-2.png" width="80" height="80"
    102102       class="inlinetop" alt="Lena (detail)" />
    103   <img src="out/lena6-1-5.png" width="416" height="416"
     103  <img src="out/lena7-1-5.png" width="416" height="416"
    104104       class="inline" alt="Mosaic created from Lena’s detail" />
    105105</p>
    106106
    107 <h3> 6.2. Error diffusion </h3>
     107<h3> 7.2. Error diffusion </h3>
    108108
    109109<p> TODO </p>
    110110
    111 <h3> 6.3. Colour ASCII art </h3>
     111<h3> 7.3. Colour ASCII art </h3>
    112112
    113113<!--
    … …  
    120120
    121121<p style="text-align: center;">
    122   <img src="fig6-3-1.png" width="395" height="196"
     122  <img src="fig7-3-1.png" width="395" height="196"
    123123       class="matrix" alt="ASCII art tiles" />
    124124</p>
    125125
    126126<div style="float: left;">
    127    <a href="part5.html">Colour dithering &lt;&lt;&lt;</a>
     127   <a href="part6.html">Colour dithering &lt;&lt;&lt;</a>
    128128</div>
    129129<div style="float: right;">

  • www/study/study.py

    r2211 r2215  
    17271727        ERROR_SUBFS33[y][x][y][1 + x] = -1
    17281728
    1729 # Output 3.7.1: direct binary search, iteration 0
    1730 # Output 3.7.2: direct binary search, iteration 1
    1731 # Output 3.7.3: direct binary search, iteration 2
    1732 # Output 3.7.4: direct binary search, iteration 5
    1733 def test37x(src):
     1729##############################################################################
     1730if chapter(4):
     1731    print "Chapter 4. Model-based dithering"
     1732
     1733# Output 4.2.1: direct binary search, iteration 0
     1734# Output 4.2.2: direct binary search, iteration 1
     1735# Output 4.2.3: direct binary search, iteration 2
     1736# Output 4.2.4: direct binary search, iteration 5
     1737def test42x(src):
    17341738    random.seed(0)
    17351739    (w, h) = src.size()
    … …  
    17411745    return dest
    17421746
    1743 def test37y(src, dest):
     1747def test42y(src, dest):
    17441748    threshold = 0.4
    17451749    kernel = Matrix(6, 6, 0.) # have a border of zeroes
    … …  
    18341838    return dest
    18351839
    1836 if chapter(3):
    1837     tmp = test37x(grad256bw)
    1838     tmp.save("out/grad3-7-1.png")
    1839     tmp = test37y(grad256bw, tmp)
    1840     tmp.save("out/grad3-7-2.png")
    1841     tmp = test37y(grad256bw, tmp)
    1842     tmp.save("out/grad3-7-3.png")
    1843     tmp = test37y(grad256bw, tmp)
    1844     tmp = test37y(grad256bw, tmp)
    1845     tmp = test37y(grad256bw, tmp)
    1846     tmp.save("out/grad3-7-4.png")
    1847 
    1848 if chapter(3):
    1849     tmp = test37x(lena256bw)
    1850     tmp.save("out/lena3-7-1.png")
    1851     tmp = test37y(lena256bw, tmp)
    1852     tmp.save("out/lena3-7-2.png")
    1853     tmp = test37y(lena256bw, tmp)
    1854     tmp.save("out/lena3-7-3.png")
    1855     tmp = test37y(lena256bw, tmp)
    1856     tmp = test37y(lena256bw, tmp)
    1857     tmp = test37y(lena256bw, tmp)
    1858     tmp.save("out/lena3-7-4.png")
     1840if chapter(4):
     1841    tmp = test42x(grad256bw)
     1842    tmp.save("out/grad4-2-1.png")
     1843    tmp = test42y(grad256bw, tmp)
     1844    tmp.save("out/grad4-2-2.png")
     1845    tmp = test42y(grad256bw, tmp)
     1846    tmp.save("out/grad4-2-3.png")
     1847    tmp = test42y(grad256bw, tmp)
     1848    tmp = test42y(grad256bw, tmp)
     1849    tmp = test42y(grad256bw, tmp)
     1850    tmp.save("out/grad4-2-4.png")
     1851
     1852if chapter(4):
     1853    tmp = test42x(lena256bw)
     1854    tmp.save("out/lena4-2-1.png")
     1855    tmp = test42y(lena256bw, tmp)
     1856    tmp.save("out/lena4-2-2.png")
     1857    tmp = test42y(lena256bw, tmp)
     1858    tmp.save("out/lena4-2-3.png")
     1859    tmp = test42y(lena256bw, tmp)
     1860    tmp = test42y(lena256bw, tmp)
     1861    tmp = test42y(lena256bw, tmp)
     1862    tmp.save("out/lena4-2-4.png")
    18591863
    18601864##############################################################################
    1861 if chapter(4):
    1862     print "Chapter 4. Greyscale dithering"
    1863 
    1864 # Output 4.0.1: 4x4 Bayer dithering, 3 colours
    1865 def test401(src, mat):
     1865if chapter(5):
     1866    print "Chapter 5. Greyscale dithering"
     1867
     1868# Output 5.0.1: 4x4 Bayer dithering, 3 colours
     1869def test501(src, mat):
    18661870    (w, h) = src.size()
    18671871    dest = Image((w, h))
    … …  
    18781882    return dest
    18791883
    1880 if chapter(4):
    1881     test401(grad256bw, DITHER_BAYER88).save("out/grad4-0-1.png")
    1882     test401(lena256bw, DITHER_BAYER88).save("out/lena4-0-1.png")
    1883 
    1884 # Output 4.0.2: standard Floyd-Steinberg, 3 colours
    1885 def test402(src, mat, serpentine):
     1884if chapter(5):
     1885    test501(grad256bw, DITHER_BAYER88).save("out/grad5-0-1.png")
     1886    test501(lena256bw, DITHER_BAYER88).save("out/lena5-0-1.png")
     1887
     1888# Output 5.0.2: standard Floyd-Steinberg, 3 colours
     1889def test502(src, mat, serpentine):
    18861890    (w, h) = src.size()
    18871891    dest = Image((w, h))
    … …  
    19201924    return dest
    19211925
    1922 if chapter(4):
    1923     test402(grad256bw, ERROR_FSTEIN, True).save("out/grad4-0-2.png")
    1924     test402(lena256bw, ERROR_FSTEIN, True).save("out/lena4-0-2.png")
    1925 
    1926 # Pattern 4.1.1: gamma-corrected 50% grey, black-white halftone, 50% grey
    1927 if chapter(4):
     1926if chapter(5):
     1927    test502(grad256bw, ERROR_FSTEIN, True).save("out/grad5-0-2.png")
     1928    test502(lena256bw, ERROR_FSTEIN, True).save("out/lena5-0-2.png")
     1929
     1930# Pattern 5.1.1: gamma-corrected 50% grey, black-white halftone, 50% grey
     1931if chapter(5):
    19281932    dest = Image((240, 80))
    19291933    for y in range(80):
    … …  
    19351939        for x in range(160, 240):
    19361940            dest.setGray(x, y, 0.5)
    1937     dest.save("out/pat4-1-1.png")
    1938 
    1939 # Output 4.2.1: gamma-corrected 2-colour Floyd-Steinberg
    1940 # Output 4.2.2: gamma-corrected 3-colour Floyd-Steinberg
    1941 # Output 4.2.3: gamma-corrected 4-colour Floyd-Steinberg
    1942 def test42x(src, mat, serpentine, threshold):
     1941    dest.save("out/pat5-1-1.png")
     1942
     1943# Output 5.2.1: gamma-corrected 2-colour Floyd-Steinberg
     1944# Output 5.2.2: gamma-corrected 3-colour Floyd-Steinberg
     1945# Output 5.2.3: gamma-corrected 4-colour Floyd-Steinberg
     1946def test52x(src, mat, serpentine, threshold):
    19431947    (w, h) = src.size()
    19441948    dest = Image((w, h))
    … …  
    19771981    return dest
    19781982
    1979 if chapter(4):
    1980     test42x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto2).save("out/grad4-2-1.png")
    1981     test42x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto2).save("out/lena4-2-1.png")
    1982     test42x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto3).save("out/grad4-2-2.png")
    1983     test42x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto3).save("out/lena4-2-2.png")
    1984     test42x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto4).save("out/grad4-2-3.png")
    1985     test42x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto4).save("out/lena4-2-3.png")
    1986 
    1987 # Output 4.3.1: full 4-colour block error diffusion
     1983if chapter(5):
     1984    test52x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto2).save("out/grad5-2-1.png")
     1985    test52x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto2).save("out/lena5-2-1.png")
     1986    test52x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto3).save("out/grad5-2-2.png")
     1987    test52x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto3).save("out/lena5-2-2.png")
     1988    test52x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto4).save("out/grad5-2-3.png")
     1989    test52x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto4).save("out/lena5-2-3.png")
     1990
     1991# Output 5.3.1: full 4-colour block error diffusion
    19881992GREY22 = []
    19891993for n in range(4*4*4*4):
    … …  
    19921996    GREY22.append([[vals[a], vals[b]], [vals[c], vals[d]]])
    19931997
    1994 if chapter(4):
     1998if chapter(5):
    19951999    subblock(grad256bw, GREY22,
    1996              ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/grad4-3-1.png")
     2000             ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/grad5-3-1.png")
    19972001    subblock(lena256bw, GREY22,
    1998              ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/lena4-3-1.png")
    1999 
    2000 # Output 4.3.2: 4-colour block error diffusion with only line tiles
     2002             ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/lena5-3-1.png")
     2003
     2004# Output 5.3.2: 4-colour block error diffusion with only line tiles
    20012005GREYLINES22 = []
    20022006for n in range(4*4*4*4):
    … …  
    20072011    GREYLINES22.append([[vals[a], vals[b]], [vals[c], vals[d]]])
    20082012
    2009 if chapter(4):
     2013if chapter(5):
    20102014    subblock(grad256bw, GREYLINES22,
    2011              ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/grad4-3-2.png")
     2015             ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/grad5-3-2.png")
    20122016    subblock(lena256bw, GREYLINES22,
    2013              ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/lena4-3-2.png")
     2017             ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/lena5-3-2.png")
    20142018
    20152019##############################################################################
    2016 if chapter(5):
    2017     print "Chapter 5. Colour dithering"
    2018 
    2019 # Pattern 5.1.1: 8-colour palette
    2020 if chapter(5):
     2020if chapter(6):
     2021    print "Chapter 6. Colour dithering"
     2022
     2023# Pattern 6.1.1: 8-colour palette
     2024if chapter(6):
    20212025    dest = Image((512, 64))
    20222026    for x in range(512):
    … …  
    20272031        for y in range(64):
    20282032            dest.setRgb(x, y, r, g, b)
    2029     dest.save("out/pat5-1-1.png")
    2030 
    2031 # Figure 5.1.1: 128x128 Lena
    2032 # Figure 5.1.2a: red channel
    2033 # Figure 5.1.2b: green channel
    2034 # Figure 5.1.2c: blue channel
    2035 # Figure 5.1.3a: red channel promoted to greyscale
    2036 # Figure 5.1.3b: green channel promoted to greyscale
    2037 # Figure 5.1.3c: blue channel promoted to greyscale
    2038 # Figure 5.1.4a: dithered red channel
    2039 # Figure 5.1.4b: dithered green channel
    2040 # Figure 5.1.4c: dithered blue channel
    2041 # Figure 5.1.5: combined dithered channels
    2042 if chapter(5):
     2033    dest.save("out/pat6-1-1.png")
     2034
     2035# Figure 6.1.1: 128x128 Lena
     2036# Figure 6.1.2a: red channel
     2037# Figure 6.1.2b: green channel
     2038# Figure 6.1.2c: blue channel
     2039# Figure 6.1.3a: red channel promoted to greyscale
     2040# Figure 6.1.3b: green channel promoted to greyscale
     2041# Figure 6.1.3c: blue channel promoted to greyscale
     2042# Figure 6.1.4a: dithered red channel
     2043# Figure 6.1.4b: dithered green channel
     2044# Figure 6.1.4c: dithered blue channel
     2045# Figure 6.1.5: combined dithered channels
     2046if chapter(6):
    20432047    tmp = gammascale(lena256, 2)
    2044     tmp.save("out/fig5-1-1.png")
     2048    tmp.save("out/fig6-1-1.png")
    20452049    (w, h) = tmp.size()
    20462050    dst = [Image((w, h), True) for i in range(3)]
    … …  
    20502054        dst[1].setRgb(x, y, 0, rgb[1], 0)
    20512055        dst[2].setRgb(x, y, 0, 0, rgb[2])
    2052     dst[0].save("out/fig5-1-2a.png")
    2053     dst[1].save("out/fig5-1-2b.png")
    2054     dst[2].save("out/fig5-1-2c.png")
     2056    dst[0].save("out/fig6-1-2a.png")
     2057    dst[1].save("out/fig6-1-2b.png")
     2058    dst[2].save("out/fig6-1-2c.png")
    20552059    for x, y in rangexy(w, h):
    20562060        for i in range(3):
    20572061            rgb = dst[i].getRgb(x, y)
    20582062            dst[i].setRgb(x, y, rgb[i], rgb[i], rgb[i])
    2059     dst[0].save("out/fig5-1-3a.png")
    2060     dst[1].save("out/fig5-1-3b.png")
    2061     dst[2].save("out/fig5-1-3c.png")
     2063    dst[0].save("out/fig6-1-3a.png")
     2064    dst[1].save("out/fig6-1-3b.png")
     2065    dst[2].save("out/fig6-1-3c.png")
    20622066    for i in range(3):
    2063         dst[i] = test42x(dst[i], ERROR_FSTEIN, True, Gamma.Cto2)
    2064     dst[0].save("out/fig5-1-4a.png")
    2065     dst[1].save("out/fig5-1-4b.png")
    2066     dst[2].save("out/fig5-1-4c.png")
     2067        dst[i] = test52x(dst[i], ERROR_FSTEIN, True, Gamma.Cto2)
     2068    dst[0].save("out/fig6-1-4a.png")
     2069    dst[1].save("out/fig6-1-4b.png")
     2070    dst[2].save("out/fig6-1-4c.png")
    20672071    for x, y in rangexy(w, h):
    20682072        for i in range(3):
    … …  
    20702074            rgb[i] = (dst[i].getRgb(x, y))[i]
    20712075            dst[i].setRgb(x, y, *rgb)
    2072     dst[0].save("out/fig5-1-5a.png")
    2073     dst[1].save("out/fig5-1-5b.png")
    2074     dst[2].save("out/fig5-1-5c.png")
     2076    dst[0].save("out/fig6-1-5a.png")
     2077    dst[1].save("out/fig6-1-5b.png")
     2078    dst[2].save("out/fig6-1-5c.png")
    20752079    for x, y in rangexy(w, h):
    20762080        rgb = [0., 0., 0.]
    … …  
    20782082            rgb[i] = (dst[i].getRgb(x, y))[i]
    20792083        tmp.setRgb(x, y, *rgb)
    2080     tmp.save("out/fig5-1-6.png")
    2081 
    2082 # Output 5.1.1: 8-colour Floyd-Steinberg RGB dithering
    2083 # Output 5.1.2: 8-colour gamma-corrected Floyd-Steinberg RGB dithering
    2084 def test51x(src, mat, func):
     2084    tmp.save("out/fig6-1-6.png")
     2085
     2086# Output 6.1.1: 8-colour Floyd-Steinberg RGB dithering
     2087# Output 6.1.2: 8-colour gamma-corrected Floyd-Steinberg RGB dithering
     2088def test61x(src, mat, func):
    20852089    (w, h) = src.size()
    20862090    dest = Image((w, h))
    … …  
    20972101    return dest
    20982102
    2099 def test51y(src, mat, serpentine, threshold):
     2103def test61y(src, mat, serpentine, threshold):
    21002104    return test3xx(src, mat, serpentine)
    21012105
    2102 if chapter(5):
    2103     test51x(grad256, ERROR_FSTEIN, test51y).save("out/grad5-1-1.png")
    2104     test51x(lena256, ERROR_FSTEIN, test51y).save("out/lena5-1-1.png")
    2105     test51x(grad256, ERROR_FSTEIN, test42x).save("out/grad5-1-2.png")
    2106     test51x(lena256, ERROR_FSTEIN, test42x).save("out/lena5-1-2.png")
    2107 
    2108 # Pattern 5.2.1: different colours give the same result
    2109 if chapter(5):
     2106if chapter(6):
     2107    test61x(grad256, ERROR_FSTEIN, test61y).save("out/grad6-1-1.png")
     2108    test61x(lena256, ERROR_FSTEIN, test61y).save("out/lena6-1-1.png")
     2109    test61x(grad256, ERROR_FSTEIN, test52x).save("out/grad6-1-2.png")
     2110    test61x(lena256, ERROR_FSTEIN, test52x).save("out/lena6-1-2.png")
     2111
     2112# Pattern 6.2.1: different colours give the same result
     2113if chapter(6):
    21102114    dest = Image((320, 160))
    21112115    for x in range(80):
    … …  
    21532157            b = DITHER_BAYER44[y % 4][(x + 2) % 4] > 13
    21542158            dest.setRgb(x, y, b, g, r)
    2155     dest.save("out/pat5-2-1.png")
    2156 
    2157 # Pattern 5.2.2: 16-colour palette
    2158 if chapter(5):
     2159    dest.save("out/pat6-2-1.png")
     2160
     2161# Pattern 6.2.2: 16-colour palette
     2162if chapter(6):
    21592163    dest = Image((512, 128))
    21602164    for x, y in rangexy(64, 64):
    … …  
    21752179        for y in range(64):
    21762180            dest.setRgb(x, y, r, g, b)
    2177     dest.save("out/pat5-2-2.png")
    2178 
    2179 # Output 5.2.1: gamma-corrected Floyd-Steinberg with ANSI palette (sigma-abs)
    2180 # Output 5.2.2: gamma-corrected Floyd-Steinberg with ANSI palette (euclidian)
    2181 def test52x(src, mat, cpal, distance, serpentine):
     2181    dest.save("out/pat6-2-2.png")
     2182
     2183# Output 6.2.1: gamma-corrected Floyd-Steinberg with ANSI palette (sigma-abs)
     2184# Output 6.2.2: gamma-corrected Floyd-Steinberg with ANSI palette (euclidian)
     2185def test62x(src, mat, cpal, distance, serpentine):
    21822186    (w, h) = src.size()
    21832187    ipal = [[Gamma.CtoI(c[i]) for i in range(3)] for c in cpal]
    … …  
    22642268    return r*r + g*g + b*b
    22652269
    2266 if chapter(5):
    2267     test52x(grad256, ERROR_FSTEIN,
    2268             ANSI_PALETTE, distmax, True).save("out/grad5-2-1.png")
    2269     test52x(lena256, ERROR_FSTEIN,
    2270             ANSI_PALETTE, distmax, True).save("out/lena5-2-1.png")
    2271     test52x(grad256, ERROR_FSTEIN,
    2272             ANSI_PALETTE, disteuclidian, True).save("out/grad5-2-2.png")
    2273     test52x(lena256, ERROR_FSTEIN,
    2274             ANSI_PALETTE, disteuclidian, True).save("out/lena5-2-2.png")
     2270if chapter(6):
     2271    test62x(grad256, ERROR_FSTEIN,
     2272            ANSI_PALETTE, distmax, True).save("out/grad6-2-1.png")
     2273    test62x(lena256, ERROR_FSTEIN,
     2274            ANSI_PALETTE, distmax, True).save("out/lena6-2-1.png")
     2275    test62x(grad256, ERROR_FSTEIN,
     2276            ANSI_PALETTE, disteuclidian, True).save("out/grad6-2-2.png")
     2277    test62x(lena256, ERROR_FSTEIN,
     2278            ANSI_PALETTE, disteuclidian, True).save("out/lena6-2-2.png")
    22752279
    22762280def rgb2hsv(r, g, b):
    … …  
    23062310    return 9*d1*d1 + d2*d2 + d3*d3
    23072311
    2308 if chapter(5):
    2309     test52x(grad256, ERROR_FSTEIN,
    2310             ANSI_PALETTE, disthsv, True).save("out/grad5-2-3.png")
    2311     test52x(lena256, ERROR_FSTEIN,
    2312             ANSI_PALETTE, disthsv, True).save("out/lena5-2-3.png")
    2313     test52x(grad256, ERROR_FSTEIN,
    2314             ANSI_PALETTE, disthsv3, True).save("out/grad5-2-4.png")
    2315     test52x(lena256, ERROR_FSTEIN,
    2316             ANSI_PALETTE, disthsv3, True).save("out/lena5-2-4.png")
    2317 
    2318 # Output 5.4.1: colour sub-block error diffusion
     2312if chapter(6):
     2313    test62x(grad256, ERROR_FSTEIN,
     2314            ANSI_PALETTE, disthsv, True).save("out/grad6-2-3.png")
     2315    test62x(lena256, ERROR_FSTEIN,
     2316            ANSI_PALETTE, disthsv, True).save("out/lena6-2-3.png")
     2317    test62x(grad256, ERROR_FSTEIN,
     2318            ANSI_PALETTE, disthsv3, True).save("out/grad6-2-4.png")
     2319    test62x(lena256, ERROR_FSTEIN,
     2320            ANSI_PALETTE, disthsv3, True).save("out/lena6-2-4.png")
     2321
     2322# Output 6.4.1: colour sub-block error diffusion
    23192323def colorsubblock(src, tiles, propagate, diff):
    23202324    (w, h) = src.size()
    … …  
    23842388                       [RGB_PALETTE[c], RGB_PALETTE[d]]])
    23852389
    2386 if chapter(5):
     2390if chapter(6):
    23872391    colorsubblock(grad256, RGBLINES22,
    2388                   ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/grad5-4-1.png")
     2392                  ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/grad6-4-1.png")
    23892393    colorsubblock(lena256, RGBLINES22,
    2390                   ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/lena5-4-1.png")
     2394                  ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/lena6-4-1.png")
    23912395
    23922396ANSILINES22 = []
    … …  
    23982402                        [ANSI_PALETTE[c], ANSI_PALETTE[d]]])
    23992403
    2400 if chapter(5):
     2404if chapter(6):
    24012405    colorsubblock(grad256, ANSILINES22,
    2402                   ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/grad5-4-2.png")
     2406                  ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/grad6-4-2.png")
    24032407    colorsubblock(lena256, ANSILINES22,
    2404                   ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/lena5-4-2.png")
     2408                  ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/lena6-4-2.png")
    24052409
    24062410##############################################################################
    2407 if chapter(6):
    2408     print "Chapter 6. Photographic mosaics"
    2409 
    2410 # Output 6.0.1: create a mosaic from Lena
     2411if chapter(7):
     2412    print "Chapter 7. Photographic mosaics"
     2413
     2414# Output 7.0.1: create a mosaic from Lena
    24112415def mosaic_split(src, tnw, tnh):
    24122416    random.seed(0)
    … …  
    24352439    return coeffs
    24362440
    2437 def test601(tnlist, cols):
     2441def test701(tnlist, cols):
    24382442    (tnw, tnh) = tnlist[0].size()
    24392443    dw = cols
    … …  
    24462450    return dest
    24472451
    2448 if chapter(6):
     2452if chapter(7):
    24492453    tnlist = mosaic_split(lena256, 32, 32)
    2450     test601(tnlist, 10).save("out/lena6-0-1.png")
    2451 
    2452 # Output 6.1.1: extract 1 colour feature from mosaic tiles
    2453 # Output 6.1.2: crop Lena
    2454 # Output 6.1.3: generate a mosaic from the 1-feature database
    2455 # Output 6.1.4: extract 4 colour features from mosaic tiles
    2456 # Output 6.1.5: generate a mosaic from the 4-feature database
    2457 def test61x(coeffs, cols, tnw, tnh):
     2454    test701(tnlist, 10).save("out/lena7-0-1.png")
     2455
     2456# Output 7.1.1: extract 1 colour feature from mosaic tiles
     2457# Output 7.1.2: crop Lena
     2458# Output 7.1.3: generate a mosaic from the 1-feature database
     2459# Output 7.1.4: extract 4 colour features from mosaic tiles
     2460# Output 7.1.5: generate a mosaic from the 4-feature database
     2461def test71x(coeffs, cols, tnw, tnh):
    24582462    dx = len(coeffs[0][0])
    24592463    dy = len(coeffs[0])
    … …  
    24692473    return dest
    24702474
    2471 def test61y(src, sqw, sqh, tnlist, coeffs):
     2475def test71y(src, sqw, sqh, tnlist, coeffs):
    24722476    (w, h) = src.size()
    24732477    (tnw, tnh) = tnlist[0].size()
    … …  
    25032507    return dest
    25042508
    2505 if chapter(6):
     2509if chapter(7):
    25062510    coeffs1x1 = mosaic_analyse(tnlist, 1, 1)
    2507     test61x(coeffs1x1, 10, 8, 8).save("out/lena6-1-1.png")
    2508     out612 = lena256.getRegion(100, 90, 80, 80)
    2509     out612.save("out/lena6-1-2.png")
    2510     test61y(out612, 6, 6, tnlist, coeffs1x1).save("out/lena6-1-3.png")
     2511    test71x(coeffs1x1, 10, 8, 8).save("out/lena7-1-1.png")
     2512    out712 = lena256.getRegion(100, 90, 80, 80)
     2513    out712.save("out/lena7-1-2.png")
     2514    test71y(out712, 6, 6, tnlist, coeffs1x1).save("out/lena7-1-3.png")
    25112515
    25122516    coeffs2x2 = mosaic_analyse(tnlist, 2, 2)
    2513     test61x(coeffs2x2, 10, 16, 16).save("out/lena6-1-4.png")
    2514     test61y(out612, 6, 6, tnlist, coeffs2x2).save("out/lena6-1-5.png")
     2517    test71x(coeffs2x2, 10, 16, 16).save("out/lena7-1-4.png")
     2518    test71y(out712, 6, 6, tnlist, coeffs2x2).save("out/lena7-1-5.png")
    25152519
    25162520##############################################################################
Note: See TracChangeset for help on using the changeset viewer.