source: www/study/part3.html @ 2175

Last change on this file since 2175 was 2175, checked in by Sam Hocevar, 14 years ago
  • A few fixes here and there.
File size: 20.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<p> <span style="color: #aa0000; font-weight: bold;">Warning</span>: this
24document is still work in progress. Feel free to send comments but do not
25consider it final material. </p>
26
27<div style="float: left;">
28   <a href="part2.html">Halftoning patterns &lt;&lt;&lt;</a>
29</div>
30<div style="float: right;">
31   <a href="part4.html">&gt;&gt;&gt; Greyscale dithering</a>
32</div>
33<div style="text-align: center;">
34   <a href="index.html">^^^ Index</a>
35</div>
36
37<h2> 3. Error diffusion </h2>
38
39<p> The idea behind error diffusion is to compute the error caused by
40thresholding a given pixel and propagate it to neighbour pixels, in order to
41compensate for the average intensity loss or gain. It is based upon the
42assumption that a slightly out-of-place pixel causes little visual harm.
43</p>
44
45<p> The error is computed by simply substracting the source value and the
46destination value. Destination value can be chosen by many means but does
47not impact the image a lot with most methods in comparison to the crucial
48choice of error distribution coefficients. </p>
49
50<p> This is the simplest error diffusion method. It thresholds the image
51to 0.5 and propagates 100% of the error to the next (right) pixel. It is
52quite impressive given its simplicity but causes important visual artifacts:
53</p>
54
55<p style="text-align: center;">
56  <img src="out3-0-1.png" width="256" height="256"
57       class="inline" alt="Simple error diffusion" />
58  <img src="grad3-0-1.png" width="32" height="256"
59       class="inline" alt="Simple error diffusion gradient" />
60</p>
61
62<h3> 3.1. Floyd-Steinberg error diffusion </h3>
63
64<p> The most famous error diffusion method is the <b>Floyd-Steinberg</b>
65algorithm. It propagates the error to more than one adjacent pixels using
66the following coefficients: </p>
67
68<p style="text-align: center;">
69  <img src="fig3-1-1.png" width="121" height="81" alt="Floyd-Steinberg" />
70</p>
71
72<p> The result of this algorithm is rather impressive even compared to the
73best ordered dither results we could achieve: </p>
74
75<p style="text-align: center;">
76  <img src="out3-1-1.png" width="256" height="256"
77       class="inline" alt="Floyd-Steinberg error diffusion" />
78  <img src="grad3-1-1.png" width="32" height="256"
79       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
80</p>
81
82<h3> 3.2. Floyd-Steinberg derivatives </h3>
83
84<p> Zhigang Fan came up with several Floyd-Steinberg derivatives. <b>Fan
85dithering</b> just moves one coefficient around: </p>
86
87<p style="text-align: center;">
88  <img src="fig3-2-1.png" width="161" height="81"
89       class="matrix" alt="Fan" />
90  <img src="out3-2-1.png" width="256" height="256"
91       class="inline" alt="Fan error diffusion" />
92  <img src="grad3-2-1.png" width="32" height="256"
93       class="inline" alt="Fan error diffusion gradient" />
94</p>
95
96<p> <b>Shiau-Fan dithering</b> use a family of matrices supposed to reduce
97the apparition of artifacts usually seen with Floyd-Steinberg: </p>
98
99<p style="text-align: center;">
100  <img src="fig3-2-1b.png" width="161" height="81"
101       class="matrix" alt="Shiau-Fan" />
102  <img src="out3-2-1b.png" width="256" height="256"
103       class="inline" alt="Shiau-Fan error diffusion" />
104  <img src="grad3-2-1b.png" width="32" height="256"
105       class="inline" alt="Shiau-Fan error diffusion gradient" />
106</p>
107
108<p style="text-align: center;">
109  <img src="fig3-2-1c.png" width="201" height="81"
110       class="matrix" alt="Shiau-Fan 2" />
111  <img src="out3-2-1c.png" width="256" height="256"
112       class="inline" alt="Shiau-Fan 2 error diffusion" />
113  <img src="grad3-2-1c.png" width="32" height="256"
114       class="inline" alt="Shiau-Fan 2 error diffusion gradient" />
115</p>
116
117<p> By the way, these matrices are covered by Shiau’s and Fan’s
118<a href="http://www.freepatentsonline.com/5353127.html">U.S. patent
1195353127</a>. </p>
120
121<p> <b>Jarvis, Judice and Ninke dithering</b> uses a much more complex
122error diffusion matrix than Floyd-Steinberg: </p>
123
124<p style="text-align: center;">
125  <img src="fig3-2-2.png" width="201" height="121"
126       class="matrix" alt="Jarvis, Judice and Ninke" />
127  <img src="out3-2-2.png" width="256" height="256"
128       class="inline" alt="Jarvis, Judice and Ninke error diffusion" />
129  <img src="grad3-2-2.png" width="32" height="256"
130       class="inline" alt="Jarvis, Judice and Ninke error diffusion gradient" />
131</p>
132
133<p> <b>Stucki dithering</b> is a slight variation of Jarvis-Judice-Ninke
134dithering: </p>
135
136<p style="text-align: center;">
137  <img src="fig3-2-3.png" width="201" height="121"
138       class="matrix" alt="Stucki" />
139  <img src="out3-2-3.png" width="256" height="256"
140       class="inline" alt="Stucki error diffusion" />
141  <img src="grad3-2-3.png" width="32" height="256"
142       class="inline" alt="Stucki error diffusion gradient" />
143</p>
144
145<p> <b>Burkes dithering</b> is yet another variation: </p>
146
147<p style="text-align: center;">
148  <img src="fig3-2-4.png" width="201" height="81"
149       class="matrix" alt="Burkes" />
150  <img src="out3-2-4.png" width="256" height="256"
151       class="inline" alt="Burkes error diffusion" />
152  <img src="grad3-2-4.png" width="32" height="256"
153       class="inline" alt="Burkes error diffusion gradient" />
154</p>
155
156<p> Frankie Sierra came up with a few error diffusion matrices: <b>Sierra
157dithering</b> is a variation of Jarvis that is slightly faster because it
158propagates to fewer pixels, <b>Two-row Sierra</b> is a simplified version
159thereof, and <b>Filter Lite</b> is one of the simplest Floyd-Steinberg
160derivatives: </p>
161
162<p style="text-align: center;">
163  <img src="fig3-2-5.png" width="201" height="121"
164       class="matrix" alt="Sierra" />
165  <img src="out3-2-5.png" width="256" height="256"
166       class="inline" alt="Sierra error diffusion" />
167  <img src="grad3-2-5.png" width="32" height="256"
168       class="inline" alt="Sierra error diffusion gradient" />
169</p>
170
171<p style="text-align: center;">
172  <img src="fig3-2-6.png" width="201" height="81"
173       class="matrix" alt="Sierra" />
174  <img src="out3-2-6.png" width="256" height="256"
175       class="inline" alt="Sierra error diffusion" />
176  <img src="grad3-2-6.png" width="32" height="256"
177       class="inline" alt="Sierra error diffusion gradient" />
178</p>
179
180<p style="text-align: center;">
181  <img src="fig3-2-7.png" width="121" height="81"
182       class="matrix" alt="Sierra" />
183  <img src="out3-2-7.png" width="256" height="256"
184       class="inline" alt="Sierra error diffusion" />
185  <img src="grad3-2-7.png" width="32" height="256"
186       class="inline" alt="Sierra error diffusion gradient" />
187</p>
188
189<p> <b>Atkinson dithering</b> only propagates 75% of the error, leading to a
190loss of contrast around black and white areas, but better contrast in the
191midtones: </p>
192
193<p style="text-align: center;">
194  <img src="fig3-2-8.png" width="161" height="121"
195       class="matrix" alt="Atkinson" />
196  <img src="out3-2-8.png" width="256" height="256"
197       class="inline" alt="Atkinson error diffusion" />
198  <img src="grad3-2-8.png" width="32" height="256"
199       class="inline" alt="Atkinson error diffusion gradient" />
200</p>
201
202<!-- XXX: Stevenson-Arce is for hexagonal cells!
203<p> <b>Stevenson-Arce dithering</b>: </p>
204
205<p style="text-align: center;">
206  <img src="fig3-2-9.png" width="280" height="160"
207       class="matrix" alt="Stevenson-Arce" />
208  <img src="out3-2-9.png" width="256" height="256"
209       class="inline" alt="Stevenson-Arce error diffusion" />
210  <img src="grad3-2-9.png" width="32" height="256"
211       class="inline" alt="Stevenson-Arce error diffusion gradient" />
212</p>
213-->
214
215<h3> 3.3. Changing image parsing direction </h3>
216
217<p> While image parsing order does not matter with ordered dithering, it can
218actually be crucial with error diffusion. The reason is that once a pixel has
219been processed, standard error diffusion methods do not go back. </p>
220
221<p> The usual way to parse an image is one pixel after the other, following
222their order in memory. When reaching the end of a line, we automatically jump
223to the beginning of the next line. Error diffusion methods using this
224parsing order are called <b>raster error diffusion</b>: </p>
225
226<p style="text-align: center;">
227  <img src="fig3-3-1.png" width="260" height="110"
228       class="matrix" alt="Regular parsing" />
229</p>
230
231<p> Changing the parsing order can help prevent the apparition of artifacts in
232error diffusion algorithms. This is <b>serpentine parsing</b>, where every odd
233line is parsed in reverse order (right to left): </p>
234
235<p style="text-align: center;">
236  <img src="fig3-3-2.png" width="260" height="110"
237       class="matrix" alt="Serpentine parsing" />
238</p>
239
240<p> The major problem with Floyd-Steinberg is the <b>worm artifacts</b> it
241creates. Here is an example of an image made of grey 0.9 dithered with
242standard Floyd-Steinberg and with <b>serpentine Floyd-Steinberg</b>. Most
243of the worm artifacts have disappeared or were highly reduced: </p>
244
245<p style="text-align: center;">
246  <img src="out3-3-1.png" width="256" height="256"
247       class="inline" alt="Floyd-Steinberg on grey 90%" />
248  <img src="out3-3-2.png" width="256" height="256"
249       class="inline" alt="serpentine Floyd-Steinberg on grey 90%" />
250</p>
251
252<p> And here are the results of serpentine Floyd-Steinberg on Lenna. Only a
253very close look will show the differences with standard Floyd-Steinberg, but
254a few of the artifacts did disappear: </p>
255
256<p style="text-align: center;">
257  <img src="out3-1-2.png" width="256" height="256"
258       class="inline" alt="serpentine Floyd-Steinberg" />
259  <img src="grad3-1-2.png" width="32" height="256"
260       class="inline" alt="serpentine Floyd-Steinberg gradient" />
261</p>
262
263<p> <b>Riemersma dithering</b> parses the image following a plane-filling
264<b>Hilbert curve</b> and only propagates the error of the last <i>q</i>
265pixels, weighing it with an exponential rule. The method is interesting and
266inventive, unfortunately the results are disappointing: structural artifacts
267are worse than with other error diffusion methods (shown here with <i>q =
26816</i> and <i>r = 16</i>): </p>
269
270<p style="text-align: center;">
271  <img src="fig3-3-3.png" width="250" height="250"
272       class="matrix" alt="Hilbert curve parsing" />
273  <img src="out3-3-3.png" width="256" height="256"
274       class="inline" alt="Riemersma dither on Hilbert curve" />
275  <img src="grad3-3-3.png" width="32" height="256"
276       class="inline" alt="Riemersma dither on Hilbert curve gradient" />
277</p>
278
279<p> A variation of Riemersma dithering uses a <b>Hilbert 2 curve</b>, giving
280slightly better results but still causing random artifacts here and there:
281</p>
282
283<p style="text-align: center;">
284  <img src="fig3-3-4.png" width="233" height="233"
285       class="matrix" alt="Hilbert 2 curve parsing" />
286  <img src="out3-3-4.png" width="256" height="256"
287       class="inline" alt="Riemersma dither on Hilbert 2 curve" />
288  <img src="grad3-3-4.png" width="32" height="256"
289       class="inline" alt="Riemersma dither on Hilbert 2 curve gradient" />
290</p>
291
292<p> An inherent problem with plane-filling curves is that distances on the
293curve do not mean anything in image space. Riemersma dithering distributes
294error to pixels according to their distance on the curve rather than their
295distance in the image. </p>
296
297<p> We introduce <b>spatial Hilbert dithering</b> that addresses this issue
298by distributing the error according to spatial coordinates. We also get rid
299of the <i>r</i> parameter, choosing to distribute 100% of the error. </p>
300
301<p> This is spatial Hilbert dithering on a Hilbert curve and on a Hilbert 2
302curve. The results show a clear improvement over the original Riemersma
303algorithm, with far less noise and smoother low-gradient areas: </p>
304
305<p style="text-align: center;">
306  <img src="out3-3-5.png" width="256" height="256"
307       class="inline" alt="spatial Hilbert dither on Hilbert curve" />
308  <img src="grad3-3-5.png" width="32" height="256"
309       class="inline" alt="spatial Hilbert dither on Hilbert curve gradient" />
310  <img src="out3-3-6.png" width="256" height="256"
311       class="inline" alt="spatial Hilbert dither on Hilbert 2 curve" />
312  <img src="grad3-3-6.png" width="32" height="256"
313       class="inline" alt="spatial Hilbert dither on Hilbert 2 curve gradient" />
314</p>
315
316<p> <b>Dot diffusion</b> is an error diffusion method by Donald E. Knuth that
317uses tileable matrices just like ordered dithering, except that the cell value
318order is taken into account for error propagation. Diagonal cells get half as
319much error as directly adjacent cells: </p>
320
321<p style="text-align: center;">
322  <img src="fig3-3-7b.png" width="121" height="121"
323       class="matrix" alt="Dot diffusion" />
324</p>
325
326<p> For instance, in the following example, cell 25’s error is propagated to
327cells 44, 36, 30, 34 and 49. Given the diagonal cells rule, cells 44, 30 and
32849 each get 1/7 of the error and cells 36 and 34 each get 2/7 of the error.
329Similarly, cell 63 gets 100% of cell 61’s error. </p>
330
331<p style="text-align: center;">
332  <img src="fig3-3-7.png" width="240" height="240"
333       class="matrix" alt="Dot diffusion matrix sample" />
334  <img src="out3-3-7.png" width="256" height="256"
335       class="inline" alt="Dot diffusion" />
336  <img src="grad3-3-7.png" width="32" height="256"
337       class="inline" alt="Dot diffusion gradient" />
338</p>
339
340<p> The initial result is not extraordinary. But Knuth suggests applying a
341sharpen filter to the original image before applying dot diffusion. He also
342introduces a <i>zeta</i> value to deal with the size of laser printer dots,
343pretty similar to what we’ll see later as <b>gamma correction</b>. The
344following two images had a sharpening value of 0.9 applied to them. The image
345on the right shows <i>zeta = 0.2</i>: </p>
346
347<p style="text-align: center;">
348  <img src="out3-3-8.png" width="256" height="256"
349       class="inline" alt="Dot diffusion sharpen 0.9" />
350  <img src="grad3-3-8.png" width="32" height="256"
351       class="inline" alt="Dot diffusion sharpen 0.9 gradient" />
352  <img src="out3-3-9.png" width="256" height="256"
353       class="inline" alt="Dot diffusion sharpen 0.9 zeta 0.2" />
354  <img src="grad3-3-9.png" width="32" height="256"
355       class="inline" alt="Dot diffusion sharpen 0.9 zeta 0.2 gradient" />
356</p>
357
358<p> Do not get fooled by Knuth’s apparent good results. They specifically
359target dot printers and do not give terribly good results on a computer
360screen. Actually, a sharpening filter makes just any dithering method look
361better, even basic Floyd-Steinberg dithering (shown here with a sharpening
362value of 0.9, too): </p>
363
364<p style="text-align: center;">
365  <img src="out3-3-10.png" width="256" height="256"
366       class="inline" alt="FS with sharpening" />
367  <img src="grad3-3-10.png" width="32" height="256"
368       class="inline" alt="FS with sharpening gradient" />
369</p>
370
371<p> Dot diffusion was reinvented 14 years later by Arney, Anderson and Ganawan
372without even citing Knuth. They call their method <b>omni-directional error
373diffusion</b>. Instead of using a clustered dot matrix like Knuth recommends
374for dot diffusion, they use a dispersed dot matrix, which gives far better
375results on a computer display. This is a 16×12 portion of that matrix: </p>
376
377<p style="text-align: center;">
378  <img src="fig3-3-11b.png" width="320" height="240"
379       class="matrix" alt="omni-directional ED matrix sample" />
380</p>
381
382<p> The preferred implementation of omni-directional error diffusion uses
383a slightly different propagation matrix, where top and bottom neighbours get
384more error than the others: </p>
385
386<p style="text-align: center;">
387  <img src="fig3-3-11.png" width="121" height="121"
388       class="matrix" alt="omni-directional ED" />
389  <img src="out3-3-11.png" width="256" height="256"
390       class="inline" alt="omni-directional ED" />
391  <img src="grad3-3-11.png" width="32" height="256"
392       class="inline" alt="omni-directional ED gradient" />
393</p>
394
395<h3> 3.4. Variable coefficients error diffusion </h3>
396
397<p> Small error diffusion matrices usually cause artifacts to appear because
398the error is not propagated in enough directions. At the same time, such
399matrices also reduce the sharpened aspect common in error diffusion
400techniques. </p>
401
402<p> Ostromoukhov suggests error diffusion values that vary according to the
403input value. The list of 256 discrete value triplets for <i>d1</i>, <i>d2</i>
404and <i>d3</i> he provides give pretty good results with serpentine parsing:
405</p>
406
407<p style="text-align: center;">
408  <img src="fig3-4-1.png" width="121" height="81"
409       class="matrix" alt="Ostromoukhov ED matrix" />
410  <img src="out3-4-1.png" width="256" height="256"
411       class="inline" alt="Ostromoukhov ED" />
412  <img src="grad3-4-1.png" width="32" height="256"
413       class="inline" alt="Ostromoukhov ED gradient" />
414</p>
415
416<h3> 3.5. Block error diffusion </h3>
417
418<p> Sometimes, due to physical restrictions of the target media, output
419is limited to some combinations of pixel blocks, such as the ones shown
420below: </p>
421
422<p style="text-align: center;">
423  <img src="fig3-5-1.png" width="613" height="80"
424       class="matrix" alt="list of 2×2 pixel blocks" />
425</p>
426
427<p> It is still possible to dither the image, by doing it 4 pixels at a
428time and simply choosing the block from the list that minimises the global
429error within the 2×2 block: </p>
430
431<p style="text-align: center;">
432  <img src="out3-5-1.png" width="256" height="256"
433       class="inline" alt="2×2 pixel block quantisation" />
434  <img src="grad3-5-1.png" width="32" height="256"
435       class="inline" alt="2×2 pixel block quantisation gradient" />
436</p>
437
438<p> Damera-Venkata and Evans introduce <b>block error diffusion</b> that
439reuses traditional error diffusion methods such as Floyd-Steinberg but applies
440the same error value to all pixels of a given block. Here are the results
441using the previous pixel blocks: </p>
442
443<p style="text-align: center;">
444  <img src="fig3-5-2.png" width="241" height="161"
445       class="matrix" alt="2×2-expanded Floyd-Steinberg" />
446  <img src="out3-5-2.png" width="256" height="256"
447       class="inline" alt="2×2 block Floyd-Steinberg" />
448  <img src="grad3-5-2.png" width="32" height="256"
449       class="inline" alt="2×2 block Floyd-Steinberg gradient" />
450</p>
451
452<p> Carefully chosen blocks create constraints on the final picture that may
453be of artistic interest: </p>
454
455<p style="text-align: center;">
456  <img src="fig3-5-3.png" width="354" height="207"
457       class="matrix" alt="artistic 3×3 blocks" />
458  <img src="out3-5-3.png" width="256" height="256"
459       class="inline" alt="3×3 block Floyd-Steinberg" />
460  <img src="grad3-5-3.png" width="32" height="256"
461       class="inline" alt="3×3 block Floyd-Steinberg gradient" />
462</p>
463
464<p> Using all possible pixel blocks is not equivalent to dithering the image
465pixel by pixel. This is due to both the block-choosing method, which only
466minimises the difference of mean values within blocks intead of the sum of
467local distances, and to the inefficient matrix coefficients, which propagate
468the error beyond immediate neighbours, causing the image to look sharpened.
469</p>
470
471<p> This example shows standard block Floyd-Steinberg using all possible 2×2
472blocks: </p>
473
474<p style="text-align: center;">
475  <img src="fig3-5-4.png" width="200" height="200"
476       class="matrix" alt="all possible 2×2 blocks" />
477  <img src="out3-5-4.png" width="256" height="256"
478       class="inline" alt="full 2×2 block Floyd-Steinberg" />
479  <img src="grad3-5-4.png" width="32" height="256"
480       class="inline" alt="full 2×2 block Floyd-Steinberg gradient" />
481</p>
482
483<p> And this is block Floyd-Steinberg using the same full set of blocks and
484a modified, weighed intra-block error distribution matrix. The picture still
485looks sharpened, but is significantly less noisy: </p>
486
487<p style="text-align: center;">
488  <img src="fig3-5-5.png" width="241" height="161"
489       class="matrix" alt="weighed 2×2 propagation matrix" />
490  <img src="out3-5-5.png" width="256" height="256"
491       class="inline" alt="weighed full 2×2 block Floyd-Steinberg" />
492  <img src="grad3-5-5.png" width="32" height="256"
493       class="inline" alt="weighed full 2×2 block Floyd-Steinberg gradient" />
494</p>
495
496<div style="float: left;">
497   <a href="part2.html">Halftoning patterns &lt;&lt;&lt;</a>
498</div>
499<div style="float: right;">
500   <a href="part4.html">&gt;&gt;&gt; Greyscale dithering</a>
501</div>
502<div style="text-align: center;">
503   <a href="index.html">^^^ Index</a>
504</div>
505
506<?php $rev = '$Id$';
507      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
508
509</body>
510</html>
Note: See TracBrowser for help on using the repository browser.