source: www/study/index.html @ 1940

Last change on this file since 1940 was 1940, checked in by Sam Hocevar, 13 years ago
  • Reworked all SVG images to improve PNG export quality.
File size: 20.3 KB
Line 
1<?php header("Content-Type: text/html; charset=utf-8"); ?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
3       "http://www.w3.org/TR/xhtml1/DTD/xhtml11.dtd">
4
5<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
6
7<head>
8   <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
9   <meta name="GENERATOR" content="vim" />
10   <meta name="Author" content="sam@zoy.org (Sam Hocevar)" />
11   <meta name="Description" content="Libcaca study" />
12   <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" />
13   <title>Libcaca study</title>
14   <link rel="icon" type="image/x-icon" href="/favicon.ico" />
15   <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
16   <link rel="stylesheet" type="text/css" href="/main.css" />
17</head>
18
19<body>
20
21<?php include($_SERVER["DOCUMENT_ROOT"]."/header.inc"); ?>
22
23<h2> Libcaca study: the science behind colour ASCII art </h2>
24
25<p> This document is an attempt at extending the leverage of skilled
26resources by uncovering and addressing the challenges the industry faces
27today in the area of colour ASCII art generation. </p>
28
29<!-- not showing this line until the document is good enough
30<p> Seriously, guys. If you think that what libcaca does is easy, you either
31don’t know what you are talking about, or we want you in the team. </p> -->
32
33<p> Meet Lenna. She will guide us through this document, because the
34seriousness of a scientific document in the area of computer graphics can
35be measured by the number of times Lenna appears in it. </p>
36
37<p style="text-align: center;">
38  <img src="lenna256.png" width="256" height="256"
39       class="inline" alt="Lenna (256x256)" />
40  <img src="lenna256bw.png" width="256" height="256"
41       class="inline" alt="Lenna (256x256BW)" />
42  <img src="gradient256bw.png" width="32" height="256"
43       class="inline" alt="gradient" />
44</p>
45
46<h3> Foreword </h3>
47
48<p> This document makes a lot of assumptions, such as the fact that input
49images are made of pixels that have either one (gray level) or three (red,
50green and blue) values uniformly spread between 0 and 1 (with regards to
51human contrast perception). Real life is more complicated than that, but
52that is beyond the scope of this document for now. </p>
53
54<p> All the algorithms explained in this document can be found in
55the <tt><a href="study.py">study.py</a></tt> Python program. Just install
56the <tt>python-gd</tt> package on your favourite operating system and
57run the script. The original Lenna images were generated with the
58<tt><a href="lenna.py">lenna.py</a></tt> program from the original colour
59512×512 image. </p>
60
61<h2> 1. Colour quantisation </h2>
62
63<p> Colour quantisation is a very old and common computer graphics problem.
64Many methods exist to do the task, and their efficiency depends on several
65parameters: </p>
66
67<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>
78</ul>
79
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
83to convert the image to black and white is to set all pixels below 0.5
84to 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
95was rather well balanced. A lot of detail is lost, though. Different results
96can be obtained by choosing “threshold values” other than 0.5, for instance
970.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
112not 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
117thresholding 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
135enough pixels, they look like shades of gray despite being made of only black
136and 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
144the 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
1525-colour thresholding picture and replace the 0.25, 0.5 and 0.75 gray values
153with 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
163technique is covered by Apple’s
164<a href="http://www.freepatentsonline.com/5761347.html">U.S. patent
1655761347</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
170different shades of gray for the following patterns, despite being made of 50%
171black 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
179computer screen. Optimising patterns so that they look good to the human
180eye and don't create artifacts is a crucial element of a dithering
181algorithm. Here is another example of two patterns that approximate to
182the 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
192certain family of patterns is called <b>ordered dithering</b>. It is based on
193a <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="2x2 dither matrix" />
197</p>
198
199<p> This matrix is then repeated all over the image, and the cells are used
200as threshold values. In this case, pixels (0,0), (0,2), (0,4) etc. will be
201thresholded with a value of 0.2. Pixels (0,1), (0, 3), (0, 4) etc. will be
202thresholded with a value of 0.8, and so on, resulting in the image seen
203in 2.1. </p>
204
205<p> Different matrices can give very different results. This is a 4×4
206Bayer ordered dithering matrix: </p>
207
208<p style="text-align: center;">
209  <img src="fig2-3-2.png" width="160" height="160"
210       style="margin-right: 30px;" alt="4x4 Bayer matrix" />
211  <img src="out2-3-1.png" width="256" height="256"
212       class="inline" alt="4x4 Bayer dithering" />
213  <img src="grad2-3-1.png" width="32" height="256"
214       class="inline" alt="4x4 Bayer dithering gradient" />
215</p>
216
217<p> This 4×4 cluster dot matrix creates dot patterns that mimic the
218halftoning techniques used by newspapers: </p>
219
220<p style="text-align: center;">
221  <img src="fig2-3-3.png" width="160" height="160"
222       style="margin-right: 30px;" alt="4x4 cluster dot matrix" />
223  <img src="out2-3-2.png" width="256" height="256"
224       class="inline" alt="4x4 cluster dot dithering" />
225  <img src="grad2-3-2.png" width="32" height="256"
226       class="inline" alt="4x4 cluster dot dithering gradient" />
227</p>
228
229<p> This unusual 5×3 matrix creates artistic vertical line artifacts: </p>
230
231<p style="text-align: center;">
232  <img src="fig2-3-4.png" width="200" height="120"
233       style="margin-right: 30px;" alt="4x4 cluster dot matrix" />
234  <img src="out2-3-3.png" width="256" height="256"
235       class="inline" alt="4x4 cluster dot dithering" />
236  <img src="grad2-3-3.png" width="32" height="256"
237       class="inline" alt="4x4 cluster dot dithering gradient" />
238</p>
239
240<p> There are two major issues with ordered dithering. First, important
241<b>visual artifacts</b> may appear. Even Bayer ordered dithering causes
242weird cross-hatch pattern artifacts on some images. Second, dithering
243matrices do not depend on the original image and thus <b>do not take input
244data into account</b>: high frequency features in the image are often missed
245and, in some cases, cause even worse artifacts. </p>
246
247<h3> 2.4. Random dithering </h3>
248
249<p> Instead of using a deterministic threshold matrix, one can use a different
250random value for each pixel in the image. This technique is simply called
251<b>random dithering</b>. Here is an example with values uniformly chosen
252between 0 and 1: </p>
253
254<p style="text-align: center;">
255  <img src="out2-4-1.png" width="256" height="256"
256       class="inline" alt="random dithering" />
257  <img src="grad2-4-1.png" width="32" height="256"
258       class="inline" alt="random dithering gradient" />
259</p>
260
261<p> This is random dithering with threshold values chosen with a gaussian
262distribution (mean 0.5, standard deviation 0.15): </p>
263
264<p style="text-align: center;">
265  <img src="out2-4-2.png" width="256" height="256"
266       class="inline" alt="gaussian (0.5, 0.15) dithering" />
267  <img src="grad2-4-2.png" width="32" height="256"
268       class="inline" alt="gaussian (0.5, 0.15) dithering gradient" />
269</p>
270
271<h2> 3. Error diffusion </h2>
272
273<p> The idea behind error diffusion is to compute the error caused by
274thresholding a given pixel and propagate it to neighbour pixels to
275compensate for the average intensity loss or gain. It is based upon the
276assumption that a slightly out-of-place pixel causes little visual harm.
277</p>
278
279<h3> 3.1. Floyd-Steinberg error diffusion </h3>
280
281<p> The most famous error diffusion method is the <b>Floyd-Steinberg</b>
282algorithm.  It handles each pixel of the image one after the other and
283propagates the error to adjacent pixels: </p>
284
285<p style="text-align: center;">
286  <img src="fig3-1-1.png" width="120" height="120" alt="Floyd-Steinberg" />
287</p>
288
289<p> The error is computed by simply substracting the source value and the
290destination value. Destination value can be chosen by many means but does
291not impact the image a lot compared to the error distribution coefficients
292choice. Here is the result using a 0.5 threshold: </p>
293
294<p style="text-align: center;">
295  <img src="out3-1-1.png" width="256" height="256"
296       class="inline" alt="Floyd-Steinberg error diffusion" />
297  <img src="grad3-1-1.png" width="32" height="256"
298       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
299</p>
300
301<p> This is a variant called <b>serpentine Floyd-Steinberg</b> that parses
302every odd line in reverse order (right to left). The results are very close
303to the original Floyd-Steinberg, but the method is said to avoid artifacts in
304some corner cases: </p>
305
306<p style="text-align: center;">
307  <img src="out3-1-2.png" width="256" height="256"
308       class="inline" alt="Floyd-Steinberg error diffusion" />
309  <img src="grad3-1-2.png" width="32" height="256"
310       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
311</p>
312
313<h3> 3.2. Floyd-Steinberg derivatives </h3>
314
315<p> <b>Fan dithering</b> is a slight modification of Floyd-Steinberg with a
316very similar matrix: </p>
317
318<p style="text-align: center;">
319  <img src="fig3-2-1.png" width="160" height="120"
320       style="margin-right: 30px;" alt="Fan" />
321  <img src="out3-2-1.png" width="256" height="256"
322       class="inline" alt="Fan error diffusion" />
323  <img src="grad3-2-1.png" width="32" height="256"
324       class="inline" alt="Fan error diffusion gradient" />
325</p>
326
327<p> <b>Jarvis, Judice and Ninke dithering</b> uses a much more complex
328error diffusion matrix than Floyd-Steinberg: </p>
329
330<p style="text-align: center;">
331  <img src="fig3-2-2.png" width="200" height="160"
332       style="margin-right: 30px;" alt="Jarvis, Judice and Ninke" />
333  <img src="out3-2-2.png" width="256" height="256"
334       class="inline" alt="Jarvis, Judice and Ninke error diffusion" />
335  <img src="grad3-2-2.png" width="32" height="256"
336       class="inline" alt="Jarvis, Judice and Ninke error diffusion gradient" />
337</p>
338
339<p> <b>Stucki dithering</b> is a slight variation of Jarvis-Judice-Ninke
340dithering: </p>
341
342<p style="text-align: center;">
343  <img src="fig3-2-3.png" width="200" height="160"
344       style="margin-right: 30px;" alt="Stucki" />
345  <img src="out3-2-3.png" width="256" height="256"
346       class="inline" alt="Stucki error diffusion" />
347  <img src="grad3-2-3.png" width="32" height="256"
348       class="inline" alt="Stucki error diffusion gradient" />
349</p>
350
351<p> <b>Burkes dithering</b> is yet another variation: </p>
352
353<p style="text-align: center;">
354  <img src="fig3-2-4.png" width="200" height="120"
355       style="margin-right: 30px;" alt="Burkes" />
356  <img src="out3-2-4.png" width="256" height="256"
357       class="inline" alt="Burkes error diffusion" />
358  <img src="grad3-2-4.png" width="32" height="256"
359       class="inline" alt="Burkes error diffusion gradient" />
360</p>
361
362<p> Frankie Sierra came up with a few error diffusion matrices: <b>Sierra
363dithering</b> is a variation of Jarvis that is slightly faster because it
364propagates to fewer pixels, <b>Two-row Sierra</b> is a simplified version
365thereof, and <b>Filter Lite</b> is one of the simplest Floyd-Steinberg
366derivatives: </p>
367
368<p style="text-align: center;">
369  <img src="fig3-2-5.png" width="200" height="160"
370       style="margin-right: 30px;" alt="Sierra" />
371  <img src="out3-2-5.png" width="256" height="256"
372       class="inline" alt="Sierra error diffusion" />
373  <img src="grad3-2-5.png" width="32" height="256"
374       class="inline" alt="Sierra error diffusion gradient" />
375</p>
376
377<p style="text-align: center;">
378  <img src="fig3-2-6.png" width="200" height="120"
379       style="margin-right: 30px;" alt="Sierra" />
380  <img src="out3-2-6.png" width="256" height="256"
381       class="inline" alt="Sierra error diffusion" />
382  <img src="grad3-2-6.png" width="32" height="256"
383       class="inline" alt="Sierra error diffusion gradient" />
384</p>
385
386<p style="text-align: center;">
387  <img src="fig3-2-7.png" width="120" height="120"
388       style="margin-right: 30px;" alt="Sierra" />
389  <img src="out3-2-7.png" width="256" height="256"
390       class="inline" alt="Sierra error diffusion" />
391  <img src="grad3-2-7.png" width="32" height="256"
392       class="inline" alt="Sierra error diffusion gradient" />
393</p>
394
395<p> <b>Atkinson dithering</b> only propagates 75% of the error, leading to a
396loss of contrast around black and white areas, but better contrast in the
397midtones: </p>
398
399<p style="text-align: center;">
400  <img src="fig3-2-8.png" width="160" height="160"
401       style="margin-right: 30px;" alt="Atkinson" />
402  <img src="out3-2-8.png" width="256" height="256"
403       class="inline" alt="Atkinson error diffusion" />
404  <img src="grad3-2-8.png" width="32" height="256"
405       class="inline" alt="Atkinson error diffusion gradient" />
406</p>
407
408<!-- XXX: Stevenson-Arce is for hexagonal cells!
409<p> <b>Stevenson-Arce dithering</b>: </p>
410
411<p style="text-align: center;">
412  <img src="fig3-2-9.png" width="280" height="200"
413       style="margin-right: 30px;" alt="Stevenson-Arce" />
414  <img src="out3-2-9.png" width="256" height="256"
415       class="inline" alt="Stevenson-Arce error diffusion" />
416  <img src="grad3-2-9.png" width="32" height="256"
417       class="inline" alt="Stevenson-Arce error diffusion gradient" />
418</p>
419-->
420
421<!--
422<p> There are countless other error diffusion techniques. However it appears
423quite clearly that the overall quality of these algorithms has reached so high
424a point that
425quite obvious that quality will hardly improve
426whatever blablah
427-->
428
429<!--
430<h3> 3. Introducing gamma </h3>
431
432<p> If you are reading this document on a computer
433screen, you may have noticed that the above 50% pattern was closer to a 0.73
434grayscale (left) than to the intuitively expected 0.5 value (right). If you
435are reading a printed copy, it might be a different matter. </p>
436
437<p style="text-align: center;">
438  <img src="pat004.png" width="240" height="80"
439       class="inline" alt="introducing gamma" />
440</p>
441
442<p> The mapping linking grayscale steps to intensities is called <b>gamma
443correction</b>. An approximate law for gamma correction is given as
444<i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour
445value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
4460 and 1) and <i>γ</i> is the gamma. Most modern computer systems use the
447sRGB gamma model close to the law with <i>γ = 2.2</i>. As can be seen, it is
448highly non-linear: </p>
449
450<p style="text-align: center;">
451  <img src="fig001.png" width="300" height="240" alt="introducing gamma" />
452</p>
453
454<p> Éric Brasseur wrote <a href="http://www.4p8.com/eric.brasseur/gamma.html">a
455pretty comprehensive essay</a> about why on a computer screen a 50% black and
456white pattern should be scaled down to a gray value of 0.73 instead of 0.5 and
457how major computer graphics software totally misses the point. </p>
458
459<p> Conversely, it clearly means that a gray value of 0.5 should not be
460emulated with a 50% dither pattern. </p>
461
462<p> So, instead of using 25%, 50% and 75% patterns (which give non-uniform
463gray values of 0.53, 0.73 and 0.88), one should rather use 6.25%, 25% and 50%
464patterns, which give the better spread gray values of 0.28, 0.53 and 0.73
465and result in far more accurate gradients. This is especially obvious when
466observing the high intensity drop between the 25% pattern and black (top row):
467</p>
468
469<p style="text-align: center;">
470  <img src="pat005.png" width="400" height="240"
471       class="inline" alt="better gradients" />
472</p>
473
474<p> Here is the result on Lenna. As you can see, the result is visually less
475appealing than with the “incorrect” colours. But when seen from a distance,
476there is no doubt this version is more accurate: </p>
477
478<p style="text-align: center;">
479  <img src="out007.png" width="256" height="256"
480       class="inline" alt="gamma-aware 3-pattern halftoning" />
481  <img src="grad007.png" width="32" height="256"
482       class="inline" alt="gamma-aware 3-pattern halftoning gradient" />
483</p>
484-->
485
486<!--
487<h3> Gamma with more gray levels </h3>
488
489<p> As seen above, the smoothest dithering pattern that can be created with
490black and white is by uniformly alterning the two colours. However, the
491resulting colour (0.73) it is not evenly situated on the gray scale. </p>
492
493  <img src="out008.png" width="256" height="256"
494       class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" />
495
496<p> Here is the application to Lenna, using the 0-0.2, 0.2-0.4, 0.4-0.6,
4970.6-0.8 and 0.8-1 ranges for black, white and the three patterns: </p>
498
499<p style="text-align: center;">
500  <img src="out005.png" width="256" height="256"
501       class="inline" alt="20/40/60/80% threshold and 25/50/75% halftones" />
502</p>
503-->
504
505<?php $rev = '$Id$';
506      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
507
508</body>
509</html>
Note: See TracBrowser for help on using the repository browser.