source: www/study/index.html @ 1925

Last change on this file since 1925 was 1925, checked in by Sam Hocevar, 13 years ago
  • Add information about gamma.
  • Add gradients beside all dithered images.
File size: 9.9 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</p>
43
44<h3> Foreword </h3>
45
46<p> This document makes a lot of assumptions, such as the fact that input
47images are made of pixels that have either one (gray level) or three (red,
48green and blue) values uniformly spread between 0 and 1 (with regards to
49human contrast perception). Real life is more complicated than that, but
50that is beyond the scope of this document for now. </p>
51
52<p> All the algorithms explained in this document can be found in
53the <tt><a href="study.py">study.py</a></tt> Python program. Just install
54the <tt>python-gd</tt> package on your favourite operating system and
55run the script. The original Lenna images were generated with the
56<tt><a href="lenna.py">lenna.py</a></tt> program from the original colour
57512×512 image. </p>
58
59<h2> 1. Colour quantisation </h2>
60
61<p> Colour quantisation is a very old and common computer graphics problem.
62Many methods exist to do the task, and their efficiency depends on several
63parameters: </p>
64
65<ul>
66  <li> the input image: is it a photograph? a vector drawing? a composition
67       of both? </li>
68  <li> the target media: is it a computer screen? if so, what are the size
69       and the position of the pixels? is it a printed document? if so,
70       what kind of paper?  what kind of ink? or maybe the conversion should
71       be optimised for both targets? </li>
72  <li> the quality requirements: for instance, can contrast be raised for
73       a more appealing result at the expense of accuracy?
74  <li> the allowed computation time: do we need 50fps or can we afford to
75       wait 10 seconds for a better result? </li>
76</ul>
77
78<h3> 1.1. Black and white thresholding </h3>
79
80<p> Since a grayscale pixel has a value between 0 and 1, a fast method
81to convert the image to black and white is to set all pixels below 0.5
82to black and all pixels above 0.5 to white. This method is called
83<b>thresholding</b> and, in our case, results in the following image: </p>
84
85<p style="text-align: center;">
86  <img src="out001.png" width="256" height="256"
87       class="inline" alt="50% threshold" />
88  <img src="grad001.png" width="32" height="256"
89       class="inline" alt="50% threshold gradient" />
90</p>
91
92<p> Not that bad, but we were pretty lucky: the original image’s brightness
93was rather well balanced. A lot of detail is lost, though. Different results
94can be obtained by choosing “threshold values” other than 0.5, for instance
950.4 or 0.6, resulting in a much brighter or darker image: </p>
96
97<p style="text-align: center;">
98  <img src="out002.png" width="256" height="256"
99       class="inline" alt="40% threshold" />
100  <img src="grad002.png" width="32" height="256"
101       class="inline" alt="40% threshold gradient" />
102  <img src="out003.png" width="256" height="256"
103       class="inline" alt="60% threshold" />
104  <img src="grad003.png" width="32" height="256"
105       class="inline" alt="60% threshold gradient" />
106</p>
107
108<p> Still not very good. Obviously something better is needed. </p>
109
110<h3> 1.2. Grayscale thresholding </h3>
111
112<p> Better results can be achieved with a slightly bigger palette. Here is
113thresholding applied to a 3-colour and to a 5-colour palette: </p>
114
115<p style="text-align: center;">
116  <img src="out004.png" width="256" height="256"
117       class="inline" alt="3-colour threshold" />
118  <img src="grad004.png" width="32" height="256"
119       class="inline" alt="3-colour threshold gradient" />
120  <img src="out005.png" width="256" height="256"
121       class="inline" alt="4-colour threshold" />
122  <img src="grad005.png" width="32" height="256"
123       class="inline" alt="4-colour threshold gradient" />
124</p>
125
126<h2> 2. Halftoning patterns </h2>
127
128<h3> 2.1. Overview </h3>
129
130<p> Observe the following patterns. From a certain distance or assuming small
131enough pixels, they look like shades of gray despite being made of only black
132and white pixels: </p>
133
134<p style="text-align: center;">
135  <img src="pat001.png" width="320" height="80"
136       class="inline" alt="50% pattern" />
137</p>
138
139<p> We can do even better using additional patterns such as these 25% and
140the 75% halftone patterns: </p>
141
142<p style="text-align: center;">
143  <img src="pat002.png" width="320" height="80"
144       class="inline" alt="25% and 75% patterns" />
145</p>
146
147<p> This looks promising. Let’s try immediately on Lenna! We will use the
1485-colour thresholding picture and replace the 0.25, 0.5 and 0.75 gray values
149with the above patterns: </p>
150
151<p style="text-align: center;">
152  <img src="out006.png" width="256" height="256"
153       class="inline" alt="25%, 50% and 75% halftoning" />
154  <img src="grad006.png" width="32" height="256"
155       class="inline" alt="25%, 50% and 75% halftoning gradient" />
156</p>
157
158<p> Not bad for a start. But there is a lot to improve. By the way, this
159technique is covered by Apple’s
160<a href="http://www.freepatentsonline.com/5761347.html">U.S. patent
1615761347</a>. </p>
162
163<h3> 2.2. Screen artifacts </h3>
164
165<p> If your screen’s quality is not very good, you might experience slightly
166different shades of gray for the following patterns, despite being made of 50%
167black and 50% white pixels: </p>
168
169<p style="text-align: center;">
170  <img src="pat003.png" width="240" height="80"
171       class="inline" alt="screen imperfections" />
172</p>
173
174<!--<p> Even if the shades -->
175
176<h3> 2.3. Introducing gamma </h3>
177
178<p> More importantly, if you are reading this document on a computer
179screen, you may have noticed that the above 50% pattern was closer to a 0.73
180grayscale (left) than to the intuitively expected 0.5 value (right). If you
181are reading a printed copy, it might be a different matter. </p>
182
183<p style="text-align: center;">
184  <img src="pat004.png" width="240" height="80"
185       class="inline" alt="introducing gamma" />
186</p>
187
188<p> The mapping linking grayscale steps to intensities is called <b>gamma
189correction</b>. An approximate law for gamma correction is given as
190<i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour
191value (between 0 and 1), <i>I</i> is the perceived colour intensity (between
1920 and 1) and <i>γ</i> is the gamma. Most modern computer systems use the
193sRGB gamma model where <i>γ</i> equals 2.2. As can be seen, it is highly
194non-linear: </p>
195
196<p style="text-align: center;">
197  <img src="fig001.png" width="256" height="230" alt="introducing gamma" />
198</p>
199
200<p> Éric Brasseur wrote <a href="http://www.4p8.com/eric.brasseur/gamma.html">a
201pretty comprehensive essay</a> about why on a computer screen a 50% black and
202white pattern should be scaled down to a gray value of 0.73 instead of 0.5 and
203how major computer graphics software totally misses the point. </p>
204
205<p> Conversely, it clearly means that a gray value of 0.5 should not be
206emulated with a 50% dither pattern. </p>
207
208<p> So, instead of using 25%, 50% and 75% patterns (which give non-uniform
209gray values of 0.53, 0.73 and 0.88), one should rather use 6.25%, 25% and 50%
210patterns, which give the better spread gray values of 0.28, 0.53 and 0.73
211and result in far more accurate gradients. This is especially obvious when
212observing the high intensity drop between the 25% pattern and black (top row):
213</p>
214
215<p style="text-align: center;">
216  <img src="pat005.png" width="400" height="240"
217       class="inline" alt="better gradients" />
218</p>
219
220<p> Here is the result on Lenna. As you can see, the result is visually less
221appealing than with the “incorrect” colours. But when seen from a distance,
222there is no doubt this version is more accurate: </p>
223
224<p style="text-align: center;">
225  <img src="out007.png" width="256" height="256"
226       class="inline" alt="gamma-aware 3-pattern halftoning" />
227  <img src="grad007.png" width="32" height="256"
228       class="inline" alt="gamma-aware 3-pattern halftoning gradient" />
229  <img src="out008.png" width="32" height="256"
230       class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" />
231</p>
232
233<!--
234  <img src="out008.png" width="256" height="256"
235       class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" />
236
237<p> Here is the application to Lenna, using the 0-0.2, 0.2-0.4, 0.4-0.6,
2380.6-0.8 and 0.8-1 ranges for black, white and the three patterns: </p>
239
240<p style="text-align: center;">
241  <img src="out005.png" width="256" height="256"
242       class="inline" alt="20/40/60/80% threshold and 25/50/75% halftones" />
243</p>
244-->
245
246<?php $rev = '$Id$';
247      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
248
249</body>
250</html>
Note: See TracBrowser for help on using the repository browser.