source: www/study/index.html @ 1930

Last change on this file since 1930 was 1930, checked in by Sam Hocevar, 13 years ago
  • Introducing dither matrices.
File size: 12.8 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 dither </h3>
190
191<p> A generalisation of the dithering technique we just saw that uses a
192certain family of patterns is called <b>ordered dither</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 dither 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<!--
241<h3> 3. Introducing gamma </h3>
242
243<p> If you are reading this document on a computer
244screen, you may have noticed that the above 50% pattern was closer to a 0.73
245grayscale (left) than to the intuitively expected 0.5 value (right). If you
246are reading a printed copy, it might be a different matter. </p>
247
248<p style="text-align: center;">
249  <img src="pat004.png" width="240" height="80"
250       class="inline" alt="introducing gamma" />
251</p>
252
253<p> The mapping linking grayscale steps to intensities is called <b>gamma
254correction</b>. An approximate law for gamma correction is given as
255<i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour
256value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
2570 and 1) and <i>γ</i> is the gamma. Most modern computer systems use the
258sRGB gamma model close to the law with <i>γ = 2.2</i>. As can be seen, it is
259highly non-linear: </p>
260
261<p style="text-align: center;">
262  <img src="fig001.png" width="300" height="240" alt="introducing gamma" />
263</p>
264
265<p> Éric Brasseur wrote <a href="http://www.4p8.com/eric.brasseur/gamma.html">a
266pretty comprehensive essay</a> about why on a computer screen a 50% black and
267white pattern should be scaled down to a gray value of 0.73 instead of 0.5 and
268how major computer graphics software totally misses the point. </p>
269
270<p> Conversely, it clearly means that a gray value of 0.5 should not be
271emulated with a 50% dither pattern. </p>
272
273<p> So, instead of using 25%, 50% and 75% patterns (which give non-uniform
274gray values of 0.53, 0.73 and 0.88), one should rather use 6.25%, 25% and 50%
275patterns, which give the better spread gray values of 0.28, 0.53 and 0.73
276and result in far more accurate gradients. This is especially obvious when
277observing the high intensity drop between the 25% pattern and black (top row):
278</p>
279
280<p style="text-align: center;">
281  <img src="pat005.png" width="400" height="240"
282       class="inline" alt="better gradients" />
283</p>
284
285<p> Here is the result on Lenna. As you can see, the result is visually less
286appealing than with the “incorrect” colours. But when seen from a distance,
287there is no doubt this version is more accurate: </p>
288
289<p style="text-align: center;">
290  <img src="out007.png" width="256" height="256"
291       class="inline" alt="gamma-aware 3-pattern halftoning" />
292  <img src="grad007.png" width="32" height="256"
293       class="inline" alt="gamma-aware 3-pattern halftoning gradient" />
294</p>
295-->
296
297<!--
298<h3> Gamma with more gray levels </h3>
299
300<p> As seen above, the smoothest dithering pattern that can be created with
301black and white is by uniformly alterning the two colours. However, the
302resulting colour (0.73) it is not evenly situated on the gray scale. </p>
303
304  <img src="out008.png" width="256" height="256"
305       class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" />
306
307<p> Here is the application to Lenna, using the 0-0.2, 0.2-0.4, 0.4-0.6,
3080.6-0.8 and 0.8-1 ranges for black, white and the three patterns: </p>
309
310<p style="text-align: center;">
311  <img src="out005.png" width="256" height="256"
312       class="inline" alt="20/40/60/80% threshold and 25/50/75% halftones" />
313</p>
314-->
315
316<?php $rev = '$Id$';
317      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
318
319</body>
320</html>
Note: See TracBrowser for help on using the repository browser.