source: www/study/index.html @ 1931

Last change on this file since 1931 was 1931, checked in by Sam Hocevar, 13 years ago
  • Started error diffusion part. Added Floyd-Steinberg.
File size: 14.2 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="out001.png" width="256" height="256"
89       class="inline" alt="50% threshold" />
90  <img src="grad001.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="out002.png" width="256" height="256"
101       class="inline" alt="40% threshold" />
102  <img src="grad002.png" width="32" height="256"
103       class="inline" alt="40% threshold gradient" />
104  <img src="out003.png" width="256" height="256"
105       class="inline" alt="60% threshold" />
106  <img src="grad003.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="out004.png" width="256" height="256"
121       class="inline" alt="3-colour threshold" />
122  <img src="grad004.png" width="32" height="256"
123       class="inline" alt="3-colour threshold gradient" />
124  <img src="out005.png" width="256" height="256"
125       class="inline" alt="4-colour threshold" />
126  <img src="grad005.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="pat001.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="pat002.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="out006.png" width="256" height="256"
157       class="inline" alt="25%, 50% and 75% halftoning" />
158  <img src="grad006.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="pat003.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="pat004.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="fig001.png" width="128" height="128" 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="fig002.png" width="160" height="160"
210       style="margin-right: 30px;" alt="4x4 Bayer matrix" />
211  <img src="out007.png" width="256" height="256"
212       class="inline" alt="4x4 Bayer dithering" />
213  <img src="grad007.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="fig003.png" width="160" height="160"
222       style="margin-right: 30px;" alt="4x4 cluster dot matrix" />
223  <img src="out008.png" width="256" height="256"
224       class="inline" alt="4x4 cluster dot dithering" />
225  <img src="grad008.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="fig004.png" width="200" height="120"
233       style="margin-right: 30px;" alt="4x4 cluster dot matrix" />
234  <img src="out009.png" width="256" height="256"
235       class="inline" alt="4x4 cluster dot dithering" />
236  <img src="grad009.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 the 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 is often missed
245and, in some cases, cause even worse artifacts. </p>
246
247<h2> 3. Error diffusion </h2>
248
249<p> The idea behind error diffusion is to compute the error caused by
250thresholding a given pixel and propagate it to neighbour pixels. </p>
251
252<h3> 3.1. Floyd-Steinberg error diffusion </h3>
253
254<p> The most famous error diffusion method is the Floyd-Steinberg algorithm.
255It handles each pixel of the image one after the other and propagates the
256error to adjacent pixels: </p>
257
258<p style="text-align: center;">
259  <img src="fig005.png" width="120" height="120" alt="Floyd-Steinberg" />
260</p>
261
262<p> The error is computed by simply substracting the source value and the
263destination value. Destination value can be chosen by many means but does
264not impact the image a lot compared to the error distribution coefficients
265choice. Here is the result using a 0.5 threshold: </p>
266
267<p style="text-align: center;">
268  <img src="out010.png" width="256" height="256"
269       class="inline" alt="Floyd-Steinberg error diffusion" />
270  <img src="grad010.png" width="32" height="256"
271       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
272</p>
273
274
275<!--
276<h3> 3. Introducing gamma </h3>
277
278<p> If you are reading this document on a computer
279screen, you may have noticed that the above 50% pattern was closer to a 0.73
280grayscale (left) than to the intuitively expected 0.5 value (right). If you
281are reading a printed copy, it might be a different matter. </p>
282
283<p style="text-align: center;">
284  <img src="pat004.png" width="240" height="80"
285       class="inline" alt="introducing gamma" />
286</p>
287
288<p> The mapping linking grayscale steps to intensities is called <b>gamma
289correction</b>. An approximate law for gamma correction is given as
290<i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour
291value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
2920 and 1) and <i>γ</i> is the gamma. Most modern computer systems use the
293sRGB gamma model close to the law with <i>γ = 2.2</i>. As can be seen, it is
294highly non-linear: </p>
295
296<p style="text-align: center;">
297  <img src="fig001.png" width="300" height="240" alt="introducing gamma" />
298</p>
299
300<p> Éric Brasseur wrote <a href="http://www.4p8.com/eric.brasseur/gamma.html">a
301pretty comprehensive essay</a> about why on a computer screen a 50% black and
302white pattern should be scaled down to a gray value of 0.73 instead of 0.5 and
303how major computer graphics software totally misses the point. </p>
304
305<p> Conversely, it clearly means that a gray value of 0.5 should not be
306emulated with a 50% dither pattern. </p>
307
308<p> So, instead of using 25%, 50% and 75% patterns (which give non-uniform
309gray values of 0.53, 0.73 and 0.88), one should rather use 6.25%, 25% and 50%
310patterns, which give the better spread gray values of 0.28, 0.53 and 0.73
311and result in far more accurate gradients. This is especially obvious when
312observing the high intensity drop between the 25% pattern and black (top row):
313</p>
314
315<p style="text-align: center;">
316  <img src="pat005.png" width="400" height="240"
317       class="inline" alt="better gradients" />
318</p>
319
320<p> Here is the result on Lenna. As you can see, the result is visually less
321appealing than with the “incorrect” colours. But when seen from a distance,
322there is no doubt this version is more accurate: </p>
323
324<p style="text-align: center;">
325  <img src="out007.png" width="256" height="256"
326       class="inline" alt="gamma-aware 3-pattern halftoning" />
327  <img src="grad007.png" width="32" height="256"
328       class="inline" alt="gamma-aware 3-pattern halftoning gradient" />
329</p>
330-->
331
332<!--
333<h3> Gamma with more gray levels </h3>
334
335<p> As seen above, the smoothest dithering pattern that can be created with
336black and white is by uniformly alterning the two colours. However, the
337resulting colour (0.73) it is not evenly situated on the gray scale. </p>
338
339  <img src="out008.png" width="256" height="256"
340       class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" />
341
342<p> Here is the application to Lenna, using the 0-0.2, 0.2-0.4, 0.4-0.6,
3430.6-0.8 and 0.8-1 ranges for black, white and the three patterns: </p>
344
345<p style="text-align: center;">
346  <img src="out005.png" width="256" height="256"
347       class="inline" alt="20/40/60/80% threshold and 25/50/75% halftones" />
348</p>
349-->
350
351<?php $rev = '$Id$';
352      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
353
354</body>
355</html>
Note: See TracBrowser for help on using the repository browser.