source: www/study/index.html @ 1899

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