source: www/study/index.html @ 1955

Last change on this file since 1955 was 1955, checked in by Sam Hocevar, 14 years ago
  • Put both FS examples on the same line.
File size: 21.6 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 (256×256)" />
40  <img src="lenna256bw.png" width="256" height="256"
41       class="inline" alt="Lenna (256×256BW)" />
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="2×2 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. Here is a sample of what happens to groups of 4 even-coloured pixels
204of 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
212Bayer 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
224halftoning 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
248weird cross-hatch pattern artifacts on some images. Second, dithering
249matrices do not depend on the original image and thus <b>do not take input
250data into account</b>: high frequency features in the image are often missed
251and, 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
256random 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
258between 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
268distribution (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
280thresholding a given pixel and propagate it to neighbour pixels to
281compensate for the average intensity loss or gain. It is based upon the
282assumption 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>
288algorithm.  It handles each pixel of the image one after the other and
289propagates 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
296destination value. Destination value can be chosen by many means but does
297not impact the image a lot compared to the error distribution coefficients
298choice. The image on the left is the result using a 0.5 threshold. The image
299on the right is a variant called <b>serpentine Floyd-Steinberg</b> that parses
300every odd line in reverse order (right to left). The results are very close
301to the original Floyd-Steinberg, but the method avoids artifacts in some
302corner 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
318very 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
330error 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
342dithering: </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
365dithering</b> is a variation of Jarvis that is slightly faster because it
366propagates to fewer pixels, <b>Two-row Sierra</b> is a simplified version
367thereof, and <b>Filter Lite</b> is one of the simplest Floyd-Steinberg
368derivatives: </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
398loss of contrast around black and white areas, but better contrast in the
399midtones: </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
425quite clearly that the overall quality of these algorithms has reached so high
426a point that
427quite obvious that quality will hardly improve
428whatever blablah
429-->
430
431<h2> 4. Grayscale dithering </h2>
432
433<p> Generalising dithering to more than two colours is straightforward in the
434grayscale palette. Here are the results with 4×4 Bayer ordered dithering and
435with 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
449on Lenna’s cheeks is visually disturbing, and the whole image looks darker
450than with pure black-and-white dithering. But then, the previous dithering
451results looked a lot brighter than the original image. This is due to the
452output 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
457noticed 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
459a 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
467correction</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
469value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
4700 and 1) and <i>γ</i> is the gamma. Most modern computer systems use the
471sRGB gamma model close to the law with <i>γ = 2.2</i>. As can be seen, it is
472highly 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
479pretty comprehensive essay</a> about why on a computer screen a 50% black and
480white pattern should be scaled down to a gray value of 0.73 instead of 0.5 and
481how 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
484emulated with a 50% dither pattern. </p>
485
486<!--
487<p> So, instead of using 25%, 50% and 75% patterns (which give non-uniform
488gray values of 0.53, 0.73 and 0.88), one should rather use 6.25%, 25% and 50%
489patterns, which give the better spread gray values of 0.28, 0.53 and 0.73
490and result in far more accurate gradients. This is especially obvious when
491observing 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
500appealing than with the “incorrect” colours. But when seen from a distance,
501there 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
515black and white is by uniformly alterning the two colours. However, the
516resulting 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,
5220.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-->
529
530<?php $rev = '$Id$';
531      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
532
533</body>
534</html>
Note: See TracBrowser for help on using the repository browser.