Changeset 1956


Ignore:
Timestamp:
Nov 14, 2007, 1:05:53 AM (13 years ago)
Author:
Sam Hocevar
Message:
  • Split document into an index page and four sections.
Location:
www/study
Files:
4 added
1 edited

Legend:

Unmodified
Added
Removed

  • www/study/index.html

    r1955 r1956  
    2020
    2121<?php include($_SERVER["DOCUMENT_ROOT"]."/header.inc"); ?>
     22
     23<!--<div style="float: left;">
     24   <a href=""></a>
     25</div>-->
     26<div style="float: right;">
     27   <a href="part1.html">&gt;&gt;&gt; Colour quantisation</a>
     28</div>
     29
     30<br style="clear: both;" />
    2231
    2332<h2> Libcaca study: the science behind colour ASCII art </h2>
    … …  
    5968512×512 image. </p>
    6069
    61 <h2> 1. Colour quantisation </h2>
    62 
    63 <p> Colour quantisation is a very old and common computer graphics problem.
    64 Many methods exist to do the task, and their efficiency depends on several
    65 parameters: </p>
     70<h3> Sections </h3>
    6671
    6772<ul>
    68   <li> the input image: is it a photograph? a vector drawing? a composition
    69        of both? </li>
    70   <li> the target media: is it a computer screen? if so, what are the size
    71        and the position of the pixels? is it a printed document? if so,
    72        what kind of paper?  what kind of ink? or maybe the conversion should
    73        be optimised for both targets? </li>
    74   <li> the quality requirements: for instance, can contrast be raised for
    75        a more appealing result at the expense of accuracy?
    76   <li> the allowed computation time: do we need 50fps or can we afford to
    77        wait 10 seconds for a better result? </li>
     73  <li> <a href="part1.html">1. Colour quantisation</a> </li>
     74  <li> <a href="part2.html">2. Halftoning patterns</a> </li>
     75  <li> <a href="part3.html">3. Error diffusion</a> </li>
     76  <li> <a href="part4.html">4. Grayscale dithering</a> </li>
    7877</ul>
    7978
    80 <h3> 1.1. Black and white thresholding </h3>
    81 
    82 <p> Since a grayscale pixel has a value between 0 and 1, a fast method
    83 to convert the image to black and white is to set all pixels below 0.5
    84 to black and all pixels above 0.5 to white. This method is called
    85 <b>thresholding</b> and, in our case, results in the following image: </p>
    86 
    87 <p style="text-align: center;">
    88   <img src="out1-1-1.png" width="256" height="256"
    89        class="inline" alt="50% threshold" />
    90   <img src="grad1-1-1.png" width="32" height="256"
    91        class="inline" alt="50% threshold gradient" />
    92 </p>
    93 
    94 <p> Not that bad, but we were pretty lucky: the original image’s brightness
    95 was rather well balanced. A lot of detail is lost, though. Different results
    96 can be obtained by choosing “threshold values” other than 0.5, for instance
    97 0.4 or 0.6, resulting in a much brighter or darker image: </p>
    98 
    99 <p style="text-align: center;">
    100   <img src="out1-1-2.png" width="256" height="256"
    101        class="inline" alt="40% threshold" />
    102   <img src="grad1-1-2.png" width="32" height="256"
    103        class="inline" alt="40% threshold gradient" />
    104   <img src="out1-1-3.png" width="256" height="256"
    105        class="inline" alt="60% threshold" />
    106   <img src="grad1-1-3.png" width="32" height="256"
    107        class="inline" alt="60% threshold gradient" />
    108 </p>
    109 
    110 <p> Choosing the best thresholding value for a given image is called
    111 <b>average dithering</b>. But even with the best value, the results will
    112 not improve tremendously. </p>
    113 
    114 <h3> 1.2. Grayscale thresholding </h3>
    115 
    116 <p> Better results can be achieved with a slightly bigger palette. Here is
    117 thresholding applied to a 3-colour and to a 5-colour palette: </p>
    118 
    119 <p style="text-align: center;">
    120   <img src="out1-2-1.png" width="256" height="256"
    121        class="inline" alt="3-colour threshold" />
    122   <img src="grad1-2-1.png" width="32" height="256"
    123        class="inline" alt="3-colour threshold gradient" />
    124   <img src="out1-2-2.png" width="256" height="256"
    125        class="inline" alt="4-colour threshold" />
    126   <img src="grad1-2-2.png" width="32" height="256"
    127        class="inline" alt="4-colour threshold gradient" />
    128 </p>
    129 
    130 <h2> 2. Halftoning patterns </h2>
    131 
    132 <h3> 2.1. Overview </h3>
    133 
    134 <p> Observe the following patterns. From a certain distance or assuming small
    135 enough pixels, they look like shades of gray despite being made of only black
    136 and white pixels: </p>
    137 
    138 <p style="text-align: center;">
    139   <img src="pat2-1-1.png" width="320" height="80"
    140        class="inline" alt="50% pattern" />
    141 </p>
    142 
    143 <p> We can do even better using additional patterns such as these 25% and
    144 the 75% halftone patterns: </p>
    145 
    146 <p style="text-align: center;">
    147   <img src="pat2-1-2.png" width="320" height="80"
    148        class="inline" alt="25% and 75% patterns" />
    149 </p>
    150 
    151 <p> This looks promising. Let’s try immediately on Lenna: we will use the
    152 5-colour thresholding picture and replace the 0.25, 0.5 and 0.75 gray values
    153 with the above patterns: </p>
    154 
    155 <p style="text-align: center;">
    156   <img src="out2-1-1.png" width="256" height="256"
    157        class="inline" alt="25%, 50% and 75% halftoning" />
    158   <img src="grad2-1-1.png" width="32" height="256"
    159        class="inline" alt="25%, 50% and 75% halftoning gradient" />
    160 </p>
    161 
    162 <p> Not bad for a start. But there is a lot to improve. By the way, this
    163 technique is covered by Apple’s
    164 <a href="http://www.freepatentsonline.com/5761347.html">U.S. patent
    165 5761347</a>. </p>
    166 
    167 <h3> 2.2. Screen artifacts </h3>
    168 
    169 <p> If your screen’s quality is not very good, you might experience slightly
    170 different shades of gray for the following patterns, despite being made of 50%
    171 black and 50% white pixels: </p>
    172 
    173 <p style="text-align: center;">
    174   <img src="pat2-2-1.png" width="240" height="80"
    175        class="inline" alt="screen imperfections" />
    176 </p>
    177 
    178 <p> Obviously the middle pattern looks far better to the human eye on a
    179 computer screen. Optimising patterns so that they look good to the human
    180 eye and don't create artifacts is a crucial element of a dithering
    181 algorithm. Here is another example of two patterns that approximate to
    182 the same shade of gray but may look slightly different from a distance: </p>
    183 
    184 <p style="text-align: center;">
    185   <img src="pat2-2-2.png" width="320" height="80"
    186        class="inline" alt="two different 25% patterns" />
    187 </p>
    188 
    189 <h3> 2.3. Ordered dithering </h3>
    190 
    191 <p> A generalisation of the dithering technique we just saw that uses a
    192 certain family of patterns is called <b>ordered dithering</b>. It is based on
    193 a <b>dither matrix</b> such as the following one: </p>
    194 
    195 <p style="text-align: center;">
    196   <img src="fig2-3-1.png" width="80" height="80" alt="2×2 dither matrix" />
    197 </p>
    198 
    199 <p> This matrix is then repeated all over the image, and the cells are used
    200 as threshold values. In this case, pixels (0,0), (0,2), (0,4) etc. will be
    201 thresholded with a value of 0.2. Pixels (0,1), (0, 3), (0, 4) etc. will be
    202 thresholded with a value of 0.8, and so on, resulting in the image seen
    203 in 2.1. Here is a sample of what happens to groups of 4 even-coloured pixels
    204 of various gray values: </p>
    205 
    206 <p style="text-align: center;">
    207   <img src="fig2-3-5.png" width="453" height="173"
    208        alt="results of 2×2 dither matrix" />
    209 </p>
    210 
    211 <p> Different matrices can give very different results. This is a 4×4
    212 Bayer ordered dithering matrix: </p>
    213 
    214 <p style="text-align: center;">
    215   <img src="fig2-3-2.png" width="160" height="160"
    216        style="margin-right: 30px;" alt="4×4 Bayer matrix" />
    217   <img src="out2-3-1.png" width="256" height="256"
    218        class="inline" alt="4×4 Bayer dithering" />
    219   <img src="grad2-3-1.png" width="32" height="256"
    220        class="inline" alt="4×4 Bayer dithering gradient" />
    221 </p>
    222 
    223 <p> This 4×4 cluster dot matrix creates dot patterns that mimic the
    224 halftoning techniques used by newspapers: </p>
    225 
    226 <p style="text-align: center;">
    227   <img src="fig2-3-3.png" width="160" height="160"
    228        style="margin-right: 30px;" alt="4×4 cluster dot matrix" />
    229   <img src="out2-3-2.png" width="256" height="256"
    230        class="inline" alt="4×4 cluster dot dithering" />
    231   <img src="grad2-3-2.png" width="32" height="256"
    232        class="inline" alt="4×4 cluster dot dithering gradient" />
    233 </p>
    234 
    235 <p> This unusual 5×3 matrix creates artistic vertical line artifacts: </p>
    236 
    237 <p style="text-align: center;">
    238   <img src="fig2-3-4.png" width="200" height="120"
    239        style="margin-right: 30px;" alt="4×4 cluster dot matrix" />
    240   <img src="out2-3-3.png" width="256" height="256"
    241        class="inline" alt="4×4 cluster dot dithering" />
    242   <img src="grad2-3-3.png" width="32" height="256"
    243        class="inline" alt="4×4 cluster dot dithering gradient" />
    244 </p>
    245 
    246 <p> There are two major issues with ordered dithering. First, important
    247 <b>visual artifacts</b> may appear. Even Bayer ordered dithering causes
    248 weird cross-hatch pattern artifacts on some images. Second, dithering
    249 matrices do not depend on the original image and thus <b>do not take input
    250 data into account</b>: high frequency features in the image are often missed
    251 and, in some cases, cause even worse artifacts. </p>
    252 
    253 <h3> 2.4. Random dithering </h3>
    254 
    255 <p> Instead of using a deterministic threshold matrix, one can use a different
    256 random value for each pixel in the image. This technique is simply called
    257 <b>random dithering</b>. Here is an example with values uniformly chosen
    258 between 0 and 1: </p>
    259 
    260 <p style="text-align: center;">
    261   <img src="out2-4-1.png" width="256" height="256"
    262        class="inline" alt="random dithering" />
    263   <img src="grad2-4-1.png" width="32" height="256"
    264        class="inline" alt="random dithering gradient" />
    265 </p>
    266 
    267 <p> This is random dithering with threshold values chosen with a gaussian
    268 distribution (mean 0.5, standard deviation 0.15): </p>
    269 
    270 <p style="text-align: center;">
    271   <img src="out2-4-2.png" width="256" height="256"
    272        class="inline" alt="gaussian (0.5, 0.15) dithering" />
    273   <img src="grad2-4-2.png" width="32" height="256"
    274        class="inline" alt="gaussian (0.5, 0.15) dithering gradient" />
    275 </p>
    276 
    277 <h2> 3. Error diffusion </h2>
    278 
    279 <p> The idea behind error diffusion is to compute the error caused by
    280 thresholding a given pixel and propagate it to neighbour pixels to
    281 compensate for the average intensity loss or gain. It is based upon the
    282 assumption that a slightly out-of-place pixel causes little visual harm.
    283 </p>
    284 
    285 <h3> 3.1. Floyd-Steinberg error diffusion </h3>
    286 
    287 <p> The most famous error diffusion method is the <b>Floyd-Steinberg</b>
    288 algorithm.  It handles each pixel of the image one after the other and
    289 propagates the error to adjacent pixels: </p>
    290 
    291 <p style="text-align: center;">
    292   <img src="fig3-1-1.png" width="120" height="120" alt="Floyd-Steinberg" />
    293 </p>
    294 
    295 <p> The error is computed by simply substracting the source value and the
    296 destination value. Destination value can be chosen by many means but does
    297 not impact the image a lot compared to the error distribution coefficients
    298 choice. The image on the left is the result using a 0.5 threshold. The image
    299 on the right is a variant called <b>serpentine Floyd-Steinberg</b> that parses
    300 every odd line in reverse order (right to left). The results are very close
    301 to the original Floyd-Steinberg, but the method avoids artifacts in some
    302 corner cases: </p>
    303 
    304 <p style="text-align: center;">
    305   <img src="out3-1-1.png" width="256" height="256"
    306        class="inline" alt="Floyd-Steinberg error diffusion" />
    307   <img src="grad3-1-1.png" width="32" height="256"
    308        class="inline" alt="Floyd-Steinberg error diffusion gradient" />
    309   <img src="out3-1-2.png" width="256" height="256"
    310        class="inline" alt="Floyd-Steinberg error diffusion" />
    311   <img src="grad3-1-2.png" width="32" height="256"
    312        class="inline" alt="Floyd-Steinberg error diffusion gradient" />
    313 </p>
    314 
    315 <h3> 3.2. Floyd-Steinberg derivatives </h3>
    316 
    317 <p> <b>Fan dithering</b> is a slight modification of Floyd-Steinberg with a
    318 very similar matrix: </p>
    319 
    320 <p style="text-align: center;">
    321   <img src="fig3-2-1.png" width="160" height="120"
    322        style="margin-right: 30px;" alt="Fan" />
    323   <img src="out3-2-1.png" width="256" height="256"
    324        class="inline" alt="Fan error diffusion" />
    325   <img src="grad3-2-1.png" width="32" height="256"
    326        class="inline" alt="Fan error diffusion gradient" />
    327 </p>
    328 
    329 <p> <b>Jarvis, Judice and Ninke dithering</b> uses a much more complex
    330 error diffusion matrix than Floyd-Steinberg: </p>
    331 
    332 <p style="text-align: center;">
    333   <img src="fig3-2-2.png" width="200" height="160"
    334        style="margin-right: 30px;" alt="Jarvis, Judice and Ninke" />
    335   <img src="out3-2-2.png" width="256" height="256"
    336        class="inline" alt="Jarvis, Judice and Ninke error diffusion" />
    337   <img src="grad3-2-2.png" width="32" height="256"
    338        class="inline" alt="Jarvis, Judice and Ninke error diffusion gradient" />
    339 </p>
    340 
    341 <p> <b>Stucki dithering</b> is a slight variation of Jarvis-Judice-Ninke
    342 dithering: </p>
    343 
    344 <p style="text-align: center;">
    345   <img src="fig3-2-3.png" width="200" height="160"
    346        style="margin-right: 30px;" alt="Stucki" />
    347   <img src="out3-2-3.png" width="256" height="256"
    348        class="inline" alt="Stucki error diffusion" />
    349   <img src="grad3-2-3.png" width="32" height="256"
    350        class="inline" alt="Stucki error diffusion gradient" />
    351 </p>
    352 
    353 <p> <b>Burkes dithering</b> is yet another variation: </p>
    354 
    355 <p style="text-align: center;">
    356   <img src="fig3-2-4.png" width="200" height="120"
    357        style="margin-right: 30px;" alt="Burkes" />
    358   <img src="out3-2-4.png" width="256" height="256"
    359        class="inline" alt="Burkes error diffusion" />
    360   <img src="grad3-2-4.png" width="32" height="256"
    361        class="inline" alt="Burkes error diffusion gradient" />
    362 </p>
    363 
    364 <p> Frankie Sierra came up with a few error diffusion matrices: <b>Sierra
    365 dithering</b> is a variation of Jarvis that is slightly faster because it
    366 propagates to fewer pixels, <b>Two-row Sierra</b> is a simplified version
    367 thereof, and <b>Filter Lite</b> is one of the simplest Floyd-Steinberg
    368 derivatives: </p>
    369 
    370 <p style="text-align: center;">
    371   <img src="fig3-2-5.png" width="200" height="160"
    372        style="margin-right: 30px;" alt="Sierra" />
    373   <img src="out3-2-5.png" width="256" height="256"
    374        class="inline" alt="Sierra error diffusion" />
    375   <img src="grad3-2-5.png" width="32" height="256"
    376        class="inline" alt="Sierra error diffusion gradient" />
    377 </p>
    378 
    379 <p style="text-align: center;">
    380   <img src="fig3-2-6.png" width="200" height="120"
    381        style="margin-right: 30px;" alt="Sierra" />
    382   <img src="out3-2-6.png" width="256" height="256"
    383        class="inline" alt="Sierra error diffusion" />
    384   <img src="grad3-2-6.png" width="32" height="256"
    385        class="inline" alt="Sierra error diffusion gradient" />
    386 </p>
    387 
    388 <p style="text-align: center;">
    389   <img src="fig3-2-7.png" width="120" height="120"
    390        style="margin-right: 30px;" alt="Sierra" />
    391   <img src="out3-2-7.png" width="256" height="256"
    392        class="inline" alt="Sierra error diffusion" />
    393   <img src="grad3-2-7.png" width="32" height="256"
    394        class="inline" alt="Sierra error diffusion gradient" />
    395 </p>
    396 
    397 <p> <b>Atkinson dithering</b> only propagates 75% of the error, leading to a
    398 loss of contrast around black and white areas, but better contrast in the
    399 midtones: </p>
    400 
    401 <p style="text-align: center;">
    402   <img src="fig3-2-8.png" width="160" height="160"
    403        style="margin-right: 30px;" alt="Atkinson" />
    404   <img src="out3-2-8.png" width="256" height="256"
    405        class="inline" alt="Atkinson error diffusion" />
    406   <img src="grad3-2-8.png" width="32" height="256"
    407        class="inline" alt="Atkinson error diffusion gradient" />
    408 </p>
    409 
    410 <!-- XXX: Stevenson-Arce is for hexagonal cells!
    411 <p> <b>Stevenson-Arce dithering</b>: </p>
    412 
    413 <p style="text-align: center;">
    414   <img src="fig3-2-9.png" width="280" height="200"
    415        style="margin-right: 30px;" alt="Stevenson-Arce" />
    416   <img src="out3-2-9.png" width="256" height="256"
    417        class="inline" alt="Stevenson-Arce error diffusion" />
    418   <img src="grad3-2-9.png" width="32" height="256"
    419        class="inline" alt="Stevenson-Arce error diffusion gradient" />
    420 </p>
    421 -->
    422 
    423 <!--
    424 <p> There are countless other error diffusion techniques. However it appears
    425 quite clearly that the overall quality of these algorithms has reached so high
    426 a point that
    427 quite obvious that quality will hardly improve
    428 whatever blablah
    429 -->
    430 
    431 <h2> 4. Grayscale dithering </h2>
    432 
    433 <p> Generalising dithering to more than two colours is straightforward in the
    434 grayscale palette. Here are the results with 4×4 Bayer ordered dithering and
    435 with Floyd-Steinberg error diffusion: </p>
    436 
    437 <p style="text-align: center;">
    438   <img src="out4-0-1.png" width="256" height="256"
    439        class="inline" alt="4×4 Bayer ordered dithering, 3 colours" />
    440   <img src="grad4-0-1.png" width="32" height="256"
    441        class="inline" alt="4×4 Bayer ordered dithering gradient, 3 colours" />
    442   <img src="out4-0-2.png" width="256" height="256"
    443        class="inline" alt="Floyd-Steinberg error diffusion, 3 colours" />
    444   <img src="grad4-0-2.png" width="32" height="256"
    445        class="inline" alt="Floyd-Steinberg error diffusion gradient, 3 colours" />
    446 </p>
    447 
    448 <p> Unfortunately the result is not as good as expected. The white pattern
    449 on Lenna’s cheeks is visually disturbing, and the whole image looks darker
    450 than with pure black-and-white dithering. But then, the previous dithering
    451 results looked a lot brighter than the original image. This is due to the
    452 output media’s <b>gamma</b>. </p>
    453 
    454 <h3> 4.1. Introducing gamma </h3>
    455 
    456 <p> If you are reading this document on a computer screen, you may have
    457 noticed that the black and white 50% pattern was closer to a 0.73 grayscale
    458 (left) than to the intuitively expected 0.5 value (right). If you are reading
    459 a printed copy, it might be a different matter. </p>
    460 
    461 <p style="text-align: center;">
    462   <img src="pat4-1-1.png" width="240" height="80"
    463        class="inline" alt="introducing gamma" />
    464 </p>
    465 
    466 <p> The mapping linking grayscale steps to intensities is called <b>gamma
    467 correction</b>. An approximate law for gamma correction is given as
    468 <i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour
    469 value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
    470 0 and 1) and <i>γ</i> is the gamma. Most modern computer systems use the
    471 sRGB gamma model close to the law with <i>γ = 2.2</i>. As can be seen, it is
    472 highly non-linear: </p>
    473 
    474 <p style="text-align: center;">
    475   <img src="fig4-1-1.png" width="300" height="240" alt="introducing gamma" />
    476 </p>
    477 
    478 <p> Éric Brasseur wrote <a href="http://www.4p8.com/eric.brasseur/gamma.html">a
    479 pretty comprehensive essay</a> about why on a computer screen a 50% black and
    480 white pattern should be scaled down to a gray value of 0.73 instead of 0.5 and
    481 how major computer graphics software totally misses the point. </p>
    482 
    483 <p> Conversely, it clearly means that a gray value of 0.5 should not be
    484 emulated with a 50% dither pattern. </p>
    485 
    486 <!--
    487 <p> So, instead of using 25%, 50% and 75% patterns (which give non-uniform
    488 gray values of 0.53, 0.73 and 0.88), one should rather use 6.25%, 25% and 50%
    489 patterns, which give the better spread gray values of 0.28, 0.53 and 0.73
    490 and result in far more accurate gradients. This is especially obvious when
    491 observing the high intensity drop between the 25% pattern and black (top row):
    492 </p>
    493 
    494 <p style="text-align: center;">
    495   <img src="pat005.png" width="400" height="240"
    496        class="inline" alt="better gradients" />
    497 </p>
    498 
    499 <p> Here is the result on Lenna. As you can see, the result is visually less
    500 appealing than with the “incorrect” colours. But when seen from a distance,
    501 there is no doubt this version is more accurate: </p>
    502 
    503 <p style="text-align: center;">
    504   <img src="out007.png" width="256" height="256"
    505        class="inline" alt="gamma-aware 3-pattern halftoning" />
    506   <img src="grad007.png" width="32" height="256"
    507        class="inline" alt="gamma-aware 3-pattern halftoning gradient" />
    508 </p>
    509 -->
    510 
    511 <!--
    512 <h3> Gamma with more gray levels </h3>
    513 
    514 <p> As seen above, the smoothest dithering pattern that can be created with
    515 black and white is by uniformly alterning the two colours. However, the
    516 resulting colour (0.73) it is not evenly situated on the gray scale. </p>
    517 
    518   <img src="out008.png" width="256" height="256"
    519        class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" />
    520 
    521 <p> Here is the application to Lenna, using the 0-0.2, 0.2-0.4, 0.4-0.6,
    522 0.6-0.8 and 0.8-1 ranges for black, white and the three patterns: </p>
    523 
    524 <p style="text-align: center;">
    525   <img src="out005.png" width="256" height="256"
    526        class="inline" alt="20/40/60/80% threshold and 25/50/75% halftones" />
    527 </p>
    528 -->
     79<!--<div style="float: left;">
     80   <a href=""></a>
     81</div>-->
     82<div style="float: right;">
     83   <a href="part1.html">&gt;&gt;&gt; 1. Colour quantisation</a>
     84</div>
    52985
    53086<?php $rev = '$Id$';
Note: See TracChangeset for help on using the changeset viewer.