cacalabs
/
web


			
				
					
						
						
							
							<?php header("Content-Type: text/html; charset=utf-8"); ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
       "http://www.w3.org/TR/xhtml1/DTD/xhtml11.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">

<head>
   <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   <meta name="GENERATOR" content="vim" />
   <meta name="Author" content="sam@zoy.org (Sam Hocevar)" />
   <meta name="Description" content="Libcaca study - 5. Greyscale dithering" />
   <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" />
   <title>Libcaca study - 5. Greyscale dithering</title>
   <link rel="icon" type="image/x-icon" href="/favicon.ico" />
   <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
   <link rel="stylesheet" type="text/css" href="/main.css" />
</head>

<body>

<?php include($_SERVER["DOCUMENT_ROOT"]."/header.inc"); ?>

<p> <span style="color: #aa0000; font-weight: bold;">Warning</span>: this
document is still work in progress. Feel free to send comments but do not
consider it final material. </p>

<div style="float: left;">
   <a href="part4.html">Model-based dithering &lt;&lt;&lt;</a>
</div>
<div style="float: right;">
   <a href="part6.html">&gt;&gt;&gt; Colour dithering</a>
</div>
<div style="text-align: center;">
   <a href="index.html">^^^ Index</a>
</div>

<h2> 5. Greyscale dithering </h2>

<p> At first sight, generalising dithering to three grey scales seems pretty
straightforward: just add grey 0.5 in the middle of the palette and dither
pixels in the [0, 0.5] range with black and grey, and pixels in the [0.5, 1]
range with grey and white. Here are two different results with 8×8 Bayer
ordered dithering and with serpentine Floyd-Steinberg error diffusion: </p>

<p style="text-align: center;">
  <img src="out/lena5-0-1.png" width="256" height="256"
       class="inline" alt="8×8 Bayer ordered dithering, 3 colours" />
  <img src="out/grad5-0-1.png" width="32" height="256"
       class="inline" alt="8×8 Bayer ordered dithering gradient, 3 colours" />
  <img src="out/lena5-0-2.png" width="256" height="256"
       class="inline" alt="serpentine FS error diffusion, 3 colours" />
  <img src="out/grad5-0-2.png" width="32" height="256"
       class="inline" alt="serpentine FS error diffusion gradient, 3 colours" />
</p>

<p> These are pretty much the images that imaging software such as The Gimp
would give (using “positioned” and “Floyd-Steinberg” dithering modes). </p>

<p> Unfortunately the result is not as good as expected: the white pattern
on Lena’s cheeks is visually disturbing, and there is a lot of 0.5 grey in
the image. Also, the whole image looks darker than with pure black-and-white
dithering, but these previous dithering results looked a lot brighter than
the original image anyway. </p>

<p> All these issues have to do with the output media’s <b>gamma</b>. </p>

<h3> 5.1. Introducing gamma </h3>

<p> If you are reading this document on a computer screen, you may have
noticed that the black and white 50% pattern was closer to a 0.73 greyscale
(left) than to the intuitively expected 0.5 value (right). If you are reading
a printed copy, it might be a different matter. </p>

<p style="text-align: center;">
  <img src="out/pat5-1-1.png" width="240" height="80"
       class="inline" alt="introducing gamma" />
</p>

<p> The mapping linking greyscale steps to intensities is called <b>gamma
correction</b>. An approximate law for gamma correction is given as
<i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour
value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
0% and 100%) and <i>γ</i> is the gamma. A pattern made of even-numbered
0%-intensity pixels and 100%-intensity pixels has an intensity of 50% by
definition. But the corresponding greyscale depends on the gamma value. </p>

<p> Most modern computer systems use the sRGB gamma model close to the law
with <i>γ = 2.2</i>. As can be seen, it is highly non-linear: </p>

<p style="text-align: center;">
  <img src="fig5-1-1.png" width="460" height="256" alt="introducing gamma" />
</p>

<p> Éric Brasseur wrote <a
href="http://www.4p8.com/eric.brasseur/gamma.html">a pretty comprehensive
essay</a> [16] about why on a computer screen a 50% black and white pattern
should be scaled down to a grey value of 0.73 instead of 0.5 and how major
computer graphics software totally misses the point. Conversely, it clearly
means that a grey value of 0.5 should not be emulated with a 50% dither
pattern. </p>

<p> The following figure shows the gamma curve for the naïve three-colour
greyscale gradient we saw above (red curve) compared to the two-colour
gradient (blue curve). Two major observations can be made: the new curve is
far closer to a perfect, linear gradient, but there is a singularity in the
middle of the curve, meaning a break in the gradient’s smoothness. </p>

<p style="text-align: center;">
  <img src="fig5-1-2.png" width="460" height="256" alt="3-colour gamma" />
</p>

<p> There are three possible ways to reduce the singularity and make the
gradient smoother and/or closer to the original colours: </p>

<ul>
  <li> Choose a different middle grey value, for instance choosing grey 0.73
       will cancel the singularity and match the two-colour gradients we have
       been using so far. This is not always possible if the output palette
       is fixed. </li>
  <li> Don’t place the grey value at the middle of the gradient, for instance
       a value of around 25% intensity will again match the previous two-colour
       gradients. </li>
  <li> <b>Gamma-correct</b> input pixels before assigning them an output
       value. This ensures that the resulting gradient is perfectly linear
       and has no singularity.
       </li>
</ul>

<h3> 5.2. Gamma correction </h3>

<p> Gamma correction consists in converting pixel values into intensity values
before performing operations on them, then reconverting them to pixel values
before displaying them. The exact same algorithms can be used, they just
operate on slightly different data. </p>

<p style="text-align: center;">
  <img src="fig5-1-3.png" width="460" height="256" alt="3-colour gamma coorection" />
</p>

<p> Here are the results of gamma-correcting input pixels before doing
any computation on them, then using serpentine Floyd-Steinberg error
diffusion: </p>

<p style="text-align: center;">
  <img src="out/lena5-2-1.png" width="256" height="256"
       class="inline" alt="serpentine FS, 2 colours, gamma-corrected" />
  <img src="out/grad5-2-1.png" width="32" height="256"
       class="inline" alt="serpentine FS, 2 colours, gamma-corrected gradient" />
  <img src="out/lena5-2-2.png" width="256" height="256"
       class="inline" alt="serpentine FS, 3 colours, gamma-corrected" />
  <img src="out/grad5-2-2.png" width="32" height="256"
       class="inline" alt="serpentine FS, 3 colours, gamma-corrected gradient" />
</p>

<p> Two-colour dithering is not visually satisfying: dark areas lack much
detail because the gamma curve is very flat at low intensities. However,
the result itself is far more accurate that previously. The problem, while
still visible, is even less important with three-colour dithering: the image
on the right is superior to what The Gimp or Adobe Photoshop are able to
come up with. </p>

<p> Finally, this is gamma-corrected 4-colour dithering: </p>

<p style="text-align: center;">
  <img src="out/lena5-2-3.png" width="256" height="256"
       class="inline" alt="serpentine FS, 4 colours, gamma-corrected" />
  <img src="out/grad5-2-3.png" width="32" height="256"
       class="inline" alt="serpentine FS, 4 colours, gamma-corrected gradient" />
</p>

<h3> 5.3. Greyscale sub-block error diffusion </h3>

<p> Support for greyscale and gamma correction is trivially added to our
sub-block error diffusion method. Best-tile choosing is done in contrast
space, while error diffusion is done in intensity space. </p>

<p> The following picture uses all possible 4-greyscale 2×2 tiles. The
output quality is very close to what standard, pixel-per-pixel error diffusion
achieves: </p>

<p style="text-align: center;">
  <img src="out/lena5-3-1.png" width="256" height="256"
       class="inline" alt="sub-block FS, full 4-grey tiles" />
  <img src="out/grad5-3-1.png" width="32" height="256"
       class="inline" alt="sub-block FS, full 4-grey tiles gradient" />
</p>

<p> And finally, this picture only uses 4-greyscale combinations of the
“lines” tiles seen previously: </p>

<p style="text-align: center;">
  <img src="fig5-3-1.png" width="307" height="253"
       class="matrix" alt="list of 4-grey 2×2 pixel blocks" />
  <img src="out/lena5-3-2.png" width="256" height="256"
       class="inline" alt="sub-block FS, lines 4-grey tiles" />
  <img src="out/grad5-3-2.png" width="32" height="256"
       class="inline" alt="sub-block FS, lines 4-grey tiles gradient" />
</p>

<div style="float: left;">
   <a href="part4.html">Model-based dithering &lt;&lt;&lt;</a>
</div>
<div style="float: right;">
   <a href="part6.html">&gt;&gt;&gt; Colour dithering</a>
</div>
<div style="text-align: center;">
   <a href="index.html">^^^ Index</a>
</div>

<?php $rev = '$Id$';
      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>

</body>
</html>