source: www/study/part3.html @ 2174

Last change on this file since 2174 was 2174, checked in by Sam Hocevar, 14 years ago
  • Omni-directional error diffusion (a dot diffusion rip-off).
File size: 20.6 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 crediting Knuth. They call their method <b>omni-directional error
373diffusion</b>. Instead of using a clustered dot matrix like dot diffusion,
374they use a dispersed dot matrix. This is a 16×12 portion of that matrix: </p>
375
376<p style="text-align: center;">
377  <img src="fig3-3-11b.png" width="320" height="240"
378       class="matrix" alt="omni-directional ED matrix sample" />
379</p>
380
381<p> The recommended implementation of omni-directional error diffusion uses
382a slightly different propagation matrix, where top and bottom neighbours get
383more error than the others: </p>
384
385<p style="text-align: center;">
386  <img src="fig3-3-11.png" width="121" height="121"
387       class="matrix" alt="omni-directional ED" />
388  <img src="out3-3-11.png" width="256" height="256"
389       class="inline" alt="omni-directional ED" />
390  <img src="grad3-3-11.png" width="32" height="256"
391       class="inline" alt="omni-directional ED gradient" />
392</p>
393
394<h3> 3.4. Variable coefficients error diffusion </h3>
395
396<p> Small error diffusion matrices usually cause artifacts to appear because
397the error is not propagated in enough directions. Ostromoukhov suggest error
398diffusion values that vary according to the input value. The list of 256
399discrete value triplets for <i>d1</i>, <i>d2</i> and <i>d3</i> he provides
400give pretty good results with serpentine parsing: </p>
401
402<p style="text-align: center;">
403  <img src="fig3-4-1.png" width="121" height="81"
404       class="matrix" alt="Ostromoukhov ED matrix" />
405  <img src="out3-4-1.png" width="256" height="256"
406       class="inline" alt="Ostromoukhov ED" />
407  <img src="grad3-4-1.png" width="32" height="256"
408       class="inline" alt="Ostromoukhov ED gradient" />
409</p>
410
411<h3> 3.5. Block error diffusion </h3>
412
413<p> Sometimes, due to physical restrictions of the target media, output
414is limited to some combinations of pixel blocks, such as the ones shown
415below: </p>
416
417<p style="text-align: center;">
418  <img src="fig3-5-1.png" width="613" height="80"
419       class="matrix" alt="list of 2×2 pixel blocks" />
420</p>
421
422<p> It is still possible to dither the image, by doing it 4 pixels at a
423time and simply choosing the block from the list that minimises the global
424error within the 2×2 block: </p>
425
426<p style="text-align: center;">
427  <img src="out3-5-1.png" width="256" height="256"
428       class="inline" alt="2×2 pixel block quantisation" />
429  <img src="grad3-5-1.png" width="32" height="256"
430       class="inline" alt="2×2 pixel block quantisation gradient" />
431</p>
432
433<p> Damera-Venkata and Evans introduce <b>block error diffusion</b> that
434reuses traditional error diffusion methods such as Floyd-Steinberg but applies
435the same error value to all pixels of a given block. Here are the results
436using the previous pixel blocks: </p>
437
438<p style="text-align: center;">
439  <img src="fig3-5-2.png" width="241" height="161"
440       class="matrix" alt="2×2-expanded Floyd-Steinberg" />
441  <img src="out3-5-2.png" width="256" height="256"
442       class="inline" alt="2×2 block Floyd-Steinberg" />
443  <img src="grad3-5-2.png" width="32" height="256"
444       class="inline" alt="2×2 block Floyd-Steinberg gradient" />
445</p>
446
447<p> Carefully chosen blocks create constraints on the final picture that may
448be of artistic interest: </p>
449
450<p style="text-align: center;">
451  <img src="fig3-5-3.png" width="354" height="207"
452       class="matrix" alt="artistic 3×3 blocks" />
453  <img src="out3-5-3.png" width="256" height="256"
454       class="inline" alt="3×3 block Floyd-Steinberg" />
455  <img src="grad3-5-3.png" width="32" height="256"
456       class="inline" alt="3×3 block Floyd-Steinberg gradient" />
457</p>
458
459<p> Using all possible pixel blocks is not equivalent to dithering the image
460pixel by pixel. This is due to both the block-choosing method, which only
461minimises the difference of mean values within blocks intead of the sum of
462local distances, and to the inefficient matrix coefficients, which propagate
463the error beyond immediate neighbours, causing the image to look sharpened.
464</p>
465
466<p> This example shows standard block Floyd-Steinberg using all possible 2×2
467blocks: </p>
468
469<p style="text-align: center;">
470  <img src="fig3-5-4.png" width="200" height="200"
471       class="matrix" alt="all possible 2×2 blocks" />
472  <img src="out3-5-4.png" width="256" height="256"
473       class="inline" alt="full 2×2 block Floyd-Steinberg" />
474  <img src="grad3-5-4.png" width="32" height="256"
475       class="inline" alt="full 2×2 block Floyd-Steinberg gradient" />
476</p>
477
478<p> And this is block Floyd-Steinberg using the same full set of blocks and
479a modified, weighed intra-block error distribution matrix. The picture still
480looks sharpened, but is significantly less noisy: </p>
481
482<p style="text-align: center;">
483  <img src="fig3-5-5.png" width="241" height="161"
484       class="matrix" alt="weighed 2×2 propagation matrix" />
485  <img src="out3-5-5.png" width="256" height="256"
486       class="inline" alt="weighed full 2×2 block Floyd-Steinberg" />
487  <img src="grad3-5-5.png" width="32" height="256"
488       class="inline" alt="weighed full 2×2 block Floyd-Steinberg gradient" />
489</p>
490
491<div style="float: left;">
492   <a href="part2.html">Halftoning patterns &lt;&lt;&lt;</a>
493</div>
494<div style="float: right;">
495   <a href="part4.html">&gt;&gt;&gt; Greyscale dithering</a>
496</div>
497<div style="text-align: center;">
498   <a href="index.html">^^^ Index</a>
499</div>
500
501<?php $rev = '$Id$';
502      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
503
504</body>
505</html>
Note: See TracBrowser for help on using the repository browser.