source: www/study/index.html @ 1942

Last change on this file since 1942 was 1942, checked in by Sam Hocevar, 13 years ago
  • Added a figure to explain the 2×2 Bayer matrix results.
  • Started grayscale dithering.
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 (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. 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 2x2 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="4x4 Bayer matrix" />
217  <img src="out2-3-1.png" width="256" height="256"
218       class="inline" alt="4x4 Bayer dithering" />
219  <img src="grad2-3-1.png" width="32" height="256"
220       class="inline" alt="4x4 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="4x4 cluster dot matrix" />
229  <img src="out2-3-2.png" width="256" height="256"
230       class="inline" alt="4x4 cluster dot dithering" />
231  <img src="grad2-3-2.png" width="32" height="256"
232       class="inline" alt="4x4 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="4x4 cluster dot matrix" />
240  <img src="out2-3-3.png" width="256" height="256"
241       class="inline" alt="4x4 cluster dot dithering" />
242  <img src="grad2-3-3.png" width="32" height="256"
243       class="inline" alt="4x4 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. Here is the result using a 0.5 threshold: </p>
299
300<p style="text-align: center;">
301  <img src="out3-1-1.png" width="256" height="256"
302       class="inline" alt="Floyd-Steinberg error diffusion" />
303  <img src="grad3-1-1.png" width="32" height="256"
304       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
305</p>
306
307<p> This is a variant called <b>serpentine Floyd-Steinberg</b> that parses
308every odd line in reverse order (right to left). The results are very close
309to the original Floyd-Steinberg, but the method is said to avoid artifacts in
310some corner cases: </p>
311
312<p style="text-align: center;">
313  <img src="out3-1-2.png" width="256" height="256"
314       class="inline" alt="Floyd-Steinberg error diffusion" />
315  <img src="grad3-1-2.png" width="32" height="256"
316       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
317</p>
318
319<h3> 3.2. Floyd-Steinberg derivatives </h3>
320
321<p> <b>Fan dithering</b> is a slight modification of Floyd-Steinberg with a
322very similar matrix: </p>
323
324<p style="text-align: center;">
325  <img src="fig3-2-1.png" width="160" height="120"
326       style="margin-right: 30px;" alt="Fan" />
327  <img src="out3-2-1.png" width="256" height="256"
328       class="inline" alt="Fan error diffusion" />
329  <img src="grad3-2-1.png" width="32" height="256"
330       class="inline" alt="Fan error diffusion gradient" />
331</p>
332
333<p> <b>Jarvis, Judice and Ninke dithering</b> uses a much more complex
334error diffusion matrix than Floyd-Steinberg: </p>
335
336<p style="text-align: center;">
337  <img src="fig3-2-2.png" width="200" height="160"
338       style="margin-right: 30px;" alt="Jarvis, Judice and Ninke" />
339  <img src="out3-2-2.png" width="256" height="256"
340       class="inline" alt="Jarvis, Judice and Ninke error diffusion" />
341  <img src="grad3-2-2.png" width="32" height="256"
342       class="inline" alt="Jarvis, Judice and Ninke error diffusion gradient" />
343</p>
344
345<p> <b>Stucki dithering</b> is a slight variation of Jarvis-Judice-Ninke
346dithering: </p>
347
348<p style="text-align: center;">
349  <img src="fig3-2-3.png" width="200" height="160"
350       style="margin-right: 30px;" alt="Stucki" />
351  <img src="out3-2-3.png" width="256" height="256"
352       class="inline" alt="Stucki error diffusion" />
353  <img src="grad3-2-3.png" width="32" height="256"
354       class="inline" alt="Stucki error diffusion gradient" />
355</p>
356
357<p> <b>Burkes dithering</b> is yet another variation: </p>
358
359<p style="text-align: center;">
360  <img src="fig3-2-4.png" width="200" height="120"
361       style="margin-right: 30px;" alt="Burkes" />
362  <img src="out3-2-4.png" width="256" height="256"
363       class="inline" alt="Burkes error diffusion" />
364  <img src="grad3-2-4.png" width="32" height="256"
365       class="inline" alt="Burkes error diffusion gradient" />
366</p>
367
368<p> Frankie Sierra came up with a few error diffusion matrices: <b>Sierra
369dithering</b> is a variation of Jarvis that is slightly faster because it
370propagates to fewer pixels, <b>Two-row Sierra</b> is a simplified version
371thereof, and <b>Filter Lite</b> is one of the simplest Floyd-Steinberg
372derivatives: </p>
373
374<p style="text-align: center;">
375  <img src="fig3-2-5.png" width="200" height="160"
376       style="margin-right: 30px;" alt="Sierra" />
377  <img src="out3-2-5.png" width="256" height="256"
378       class="inline" alt="Sierra error diffusion" />
379  <img src="grad3-2-5.png" width="32" height="256"
380       class="inline" alt="Sierra error diffusion gradient" />
381</p>
382
383<p style="text-align: center;">
384  <img src="fig3-2-6.png" width="200" height="120"
385       style="margin-right: 30px;" alt="Sierra" />
386  <img src="out3-2-6.png" width="256" height="256"
387       class="inline" alt="Sierra error diffusion" />
388  <img src="grad3-2-6.png" width="32" height="256"
389       class="inline" alt="Sierra error diffusion gradient" />
390</p>
391
392<p style="text-align: center;">
393  <img src="fig3-2-7.png" width="120" height="120"
394       style="margin-right: 30px;" alt="Sierra" />
395  <img src="out3-2-7.png" width="256" height="256"
396       class="inline" alt="Sierra error diffusion" />
397  <img src="grad3-2-7.png" width="32" height="256"
398       class="inline" alt="Sierra error diffusion gradient" />
399</p>
400
401<p> <b>Atkinson dithering</b> only propagates 75% of the error, leading to a
402loss of contrast around black and white areas, but better contrast in the
403midtones: </p>
404
405<p style="text-align: center;">
406  <img src="fig3-2-8.png" width="160" height="160"
407       style="margin-right: 30px;" alt="Atkinson" />
408  <img src="out3-2-8.png" width="256" height="256"
409       class="inline" alt="Atkinson error diffusion" />
410  <img src="grad3-2-8.png" width="32" height="256"
411       class="inline" alt="Atkinson error diffusion gradient" />
412</p>
413
414<!-- XXX: Stevenson-Arce is for hexagonal cells!
415<p> <b>Stevenson-Arce dithering</b>: </p>
416
417<p style="text-align: center;">
418  <img src="fig3-2-9.png" width="280" height="200"
419       style="margin-right: 30px;" alt="Stevenson-Arce" />
420  <img src="out3-2-9.png" width="256" height="256"
421       class="inline" alt="Stevenson-Arce error diffusion" />
422  <img src="grad3-2-9.png" width="32" height="256"
423       class="inline" alt="Stevenson-Arce error diffusion gradient" />
424</p>
425-->
426
427<!--
428<p> There are countless other error diffusion techniques. However it appears
429quite clearly that the overall quality of these algorithms has reached so high
430a point that
431quite obvious that quality will hardly improve
432whatever blablah
433-->
434
435<h2> 4. Grayscale dithering </h2>
436
437<p> Generalising dithering to more than two colours is straightforward in the
438grayscale palette. Here are the results with 4×4 Bayer ordered dithering and
439with Floyd-Steinberg error diffusion: </p>
440
441<p style="text-align: center;">
442  <img src="out4-0-1.png" width="256" height="256"
443       class="inline" alt="4×4 Bayer ordered dithering, 3 colours" />
444  <img src="grad4-0-1.png" width="32" height="256"
445       class="inline" alt="4×4 Bayer ordered dithering gradient, 3 colours" />
446  <img src="out4-0-2.png" width="256" height="256"
447       class="inline" alt="Floyd-Steinberg error diffusion, 3 colours" />
448  <img src="grad4-0-2.png" width="32" height="256"
449       class="inline" alt="Floyd-Steinberg error diffusion gradient, 3 colours" />
450</p>
451
452<p> Unfortunately the result is not as good as expected. The white pattern
453on Lenna’s cheeks is visually disturbing, and the whole image looks darker
454than with pure black-and-white dithering. But then, the previous dithering
455results looked a lot brighter than the original image. This is due to the
456output media’s <b>gamma</b>. </p>
457
458<h3> 4.1. Introducing gamma </h3>
459
460<p> If you are reading this document on a computer screen, you may have
461noticed that the black and white 50% pattern was closer to a 0.73 grayscale
462(left) than to the intuitively expected 0.5 value (right). If you are reading
463a printed copy, it might be a different matter. </p>
464
465<p style="text-align: center;">
466  <img src="pat4-1-1.png" width="240" height="80"
467       class="inline" alt="introducing gamma" />
468</p>
469
470<p> The mapping linking grayscale steps to intensities is called <b>gamma
471correction</b>. An approximate law for gamma correction is given as
472<i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour
473value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
4740 and 1) and <i>γ</i> is the gamma. Most modern computer systems use the
475sRGB gamma model close to the law with <i>γ = 2.2</i>. As can be seen, it is
476highly non-linear: </p>
477
478<p style="text-align: center;">
479  <img src="fig4-1-1.png" width="300" height="240" alt="introducing gamma" />
480</p>
481
482<p> Éric Brasseur wrote <a href="http://www.4p8.com/eric.brasseur/gamma.html">a
483pretty comprehensive essay</a> about why on a computer screen a 50% black and
484white pattern should be scaled down to a gray value of 0.73 instead of 0.5 and
485how major computer graphics software totally misses the point. </p>
486
487<p> Conversely, it clearly means that a gray value of 0.5 should not be
488emulated with a 50% dither pattern. </p>
489
490<!--
491<p> So, instead of using 25%, 50% and 75% patterns (which give non-uniform
492gray values of 0.53, 0.73 and 0.88), one should rather use 6.25%, 25% and 50%
493patterns, which give the better spread gray values of 0.28, 0.53 and 0.73
494and result in far more accurate gradients. This is especially obvious when
495observing the high intensity drop between the 25% pattern and black (top row):
496</p>
497
498<p style="text-align: center;">
499  <img src="pat005.png" width="400" height="240"
500       class="inline" alt="better gradients" />
501</p>
502
503<p> Here is the result on Lenna. As you can see, the result is visually less
504appealing than with the “incorrect” colours. But when seen from a distance,
505there is no doubt this version is more accurate: </p>
506
507<p style="text-align: center;">
508  <img src="out007.png" width="256" height="256"
509       class="inline" alt="gamma-aware 3-pattern halftoning" />
510  <img src="grad007.png" width="32" height="256"
511       class="inline" alt="gamma-aware 3-pattern halftoning gradient" />
512</p>
513-->
514
515<!--
516<h3> Gamma with more gray levels </h3>
517
518<p> As seen above, the smoothest dithering pattern that can be created with
519black and white is by uniformly alterning the two colours. However, the
520resulting colour (0.73) it is not evenly situated on the gray scale. </p>
521
522  <img src="out008.png" width="256" height="256"
523       class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" />
524
525<p> Here is the application to Lenna, using the 0-0.2, 0.2-0.4, 0.4-0.6,
5260.6-0.8 and 0.8-1 ranges for black, white and the three patterns: </p>
527
528<p style="text-align: center;">
529  <img src="out005.png" width="256" height="256"
530       class="inline" alt="20/40/60/80% threshold and 25/50/75% halftones" />
531</p>
532-->
533
534<?php $rev = '$Id$';
535      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
536
537</body>
538</html>
Note: See TracBrowser for help on using the repository browser.