source: www/study/part3.html @ 2585

Last change on this file since 2585 was 2585, checked in by Sam Hocevar, 14 years ago
  • minor link fix.
File size: 26.5 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 - 3. Error diffusion" />
12   <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" />
13   <title>Libcaca study - 3. Error diffusion</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 &lt;&lt;&lt;</a>
29</div>
30<div style="float: right;">
31   <a href="part4.html">&gt;&gt;&gt; Model-based 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="out/lena3-0-1.png" width="256" height="256"
57       class="inline" alt="Simple error diffusion" />
58  <img src="out/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 and JaJuNi error diffusion </h3>
63
64<p> The most famous error diffusion method is the <b>Floyd-Steinberg</b>
65algorithm [5]. 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="out/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="out/lena3-1-1.png" width="256" height="256"
77       class="inline" alt="Floyd-Steinberg error diffusion" />
78  <img src="out/grad3-1-1.png" width="32" height="256"
79       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
80</p>
81
82<p> <b>Jarvis, Judice and Ninke dithering</b> [7] (sometimes nicknamed
83<b>JaJuNi</b>) was published almost at the same time as Floyd-Steinberg. It
84uses a much more complex error diffusion matrix: </p>
85
86<p style="text-align: center;">
87  <img src="out/fig3-1-3.png" width="201" height="121"
88       class="matrix" alt="Jarvis, Judice and Ninke" />
89  <img src="out/lena3-1-3.png" width="256" height="256"
90       class="inline" alt="Jarvis, Judice and Ninke error diffusion" />
91  <img src="out/grad3-1-3.png" width="32" height="256"
92       class="inline" alt="Jarvis, Judice and Ninke error diffusion gradient" />
93</p>
94
95<h3> 3.2. Floyd-Steinberg derivatives </h3>
96
97<p> Zhigang Fan came up with several Floyd-Steinberg derivatives. <b>Fan
98dithering</b> [8] just moves one coefficient around: </p>
99
100<p style="text-align: center;">
101  <img src="out/fig3-2-1.png" width="161" height="81"
102       class="matrix" alt="Fan" />
103  <img src="out/lena3-2-1.png" width="256" height="256"
104       class="inline" alt="Fan error diffusion" />
105  <img src="out/grad3-2-1.png" width="32" height="256"
106       class="inline" alt="Fan error diffusion gradient" />
107</p>
108
109<p> <b>Shiau-Fan dithering</b> use a family of matrices supposed to reduce
110the apparition of artifacts usually seen with Floyd-Steinberg: </p>
111
112<p style="text-align: center;">
113  <img src="out/fig3-2-1b.png" width="161" height="81"
114       class="matrix" alt="Shiau-Fan" />
115  <img src="out/lena3-2-1b.png" width="256" height="256"
116       class="inline" alt="Shiau-Fan error diffusion" />
117  <img src="out/grad3-2-1b.png" width="32" height="256"
118       class="inline" alt="Shiau-Fan error diffusion gradient" />
119</p>
120
121<p style="text-align: center;">
122  <img src="out/fig3-2-1c.png" width="201" height="81"
123       class="matrix" alt="Shiau-Fan 2" />
124  <img src="out/lena3-2-1c.png" width="256" height="256"
125       class="inline" alt="Shiau-Fan 2 error diffusion" />
126  <img src="out/grad3-2-1c.png" width="32" height="256"
127       class="inline" alt="Shiau-Fan 2 error diffusion gradient" />
128</p>
129
130<p> By the way, these matrices are covered by Shiau’s and Fan’s
131<a href="http://www.freepatentsonline.com/5353127.html">U.S. patent
1325353127</a>. </p>
133
134<p> <b>Stucki dithering</b> [6] is a slight variation of Jarvis-Judice-Ninke
135dithering: </p>
136
137<p style="text-align: center;">
138  <img src="out/fig3-2-3.png" width="201" height="121"
139       class="matrix" alt="Stucki" />
140  <img src="out/lena3-2-3.png" width="256" height="256"
141       class="inline" alt="Stucki error diffusion" />
142  <img src="out/grad3-2-3.png" width="32" height="256"
143       class="inline" alt="Stucki error diffusion gradient" />
144</p>
145
146<p> <b>Burkes dithering</b> is yet another variation [10] which improves on
147Stucki dithering by removing a line and making the error coefficients fractions
148of powers of two: </p>
149
150<p style="text-align: center;">
151  <img src="out/fig3-2-4.png" width="201" height="81"
152       class="matrix" alt="Burkes" />
153  <img src="out/lena3-2-4.png" width="256" height="256"
154       class="inline" alt="Burkes error diffusion" />
155  <img src="out/grad3-2-4.png" width="32" height="256"
156       class="inline" alt="Burkes error diffusion gradient" />
157</p>
158
159<p> Frankie Sierra [11] came up with a few error diffusion matrices: <b>Sierra
160dithering</b> is a variation of Jarvis that is slightly faster because it
161propagates to fewer pixels, <b>Two-row Sierra</b> is a simplified version
162thereof, and <b>Filter Lite</b> is one of the simplest Floyd-Steinberg
163derivatives: </p>
164
165<p style="text-align: center;">
166  <img src="out/fig3-2-5.png" width="201" height="121"
167       class="matrix" alt="Sierra" />
168  <img src="out/lena3-2-5.png" width="256" height="256"
169       class="inline" alt="Sierra error diffusion" />
170  <img src="out/grad3-2-5.png" width="32" height="256"
171       class="inline" alt="Sierra error diffusion gradient" />
172</p>
173
174<p style="text-align: center;">
175  <img src="out/fig3-2-6.png" width="201" height="81"
176       class="matrix" alt="Sierra" />
177  <img src="out/lena3-2-6.png" width="256" height="256"
178       class="inline" alt="Sierra error diffusion" />
179  <img src="out/grad3-2-6.png" width="32" height="256"
180       class="inline" alt="Sierra error diffusion gradient" />
181</p>
182
183<p style="text-align: center;">
184  <img src="out/fig3-2-7.png" width="121" height="81"
185       class="matrix" alt="Sierra" />
186  <img src="out/lena3-2-7.png" width="256" height="256"
187       class="inline" alt="Sierra error diffusion" />
188  <img src="out/grad3-2-7.png" width="32" height="256"
189       class="inline" alt="Sierra error diffusion gradient" />
190</p>
191
192<p> <b>Atkinson dithering</b> [12] only propagates 75% of the error, leading
193to a loss of contrast around very dark and very light areas (also called
194<b>highlights and shadows</b>), but better contrast in the midtones. The
195original Macintosh software <i>HyperScan</i> used this dithering algorithm,
196still considered superior to other Floyd-Steinberg derivatives by many Mac
197zealots: </p>
198
199<p style="text-align: center;">
200  <img src="out/fig3-2-8.png" width="161" height="121"
201       class="matrix" alt="Atkinson" />
202  <img src="out/lena3-2-8.png" width="256" height="256"
203       class="inline" alt="Atkinson error diffusion" />
204  <img src="out/grad3-2-8.png" width="32" height="256"
205       class="inline" alt="Atkinson error diffusion gradient" />
206</p>
207
208<!-- XXX: Stevenson-Arce is for hexagonal cells!
209<p> <b>Stevenson-Arce dithering</b>: </p>
210
211<p style="text-align: center;">
212  <img src="fig3-2-9.png" width="280" height="160"
213       class="matrix" alt="Stevenson-Arce" />
214  <img src="out/lena3-2-9.png" width="256" height="256"
215       class="inline" alt="Stevenson-Arce error diffusion" />
216  <img src="out/grad3-2-9.png" width="32" height="256"
217       class="inline" alt="Stevenson-Arce error diffusion gradient" />
218</p>
219-->
220
221<h3> 3.3. Changing image parsing direction </h3>
222
223<p> While image parsing order does not matter with ordered dithering, it can
224actually be crucial with error diffusion. The reason is that once a pixel has
225been processed, standard error diffusion methods do not go back. </p>
226
227<p> The usual way to parse an image is one pixel after the other, following
228their order in memory. When reaching the end of a line, we automatically jump
229to the beginning of the next line. Error diffusion methods using this
230parsing order are called <b>raster error diffusion</b>: </p>
231
232<p style="text-align: center;">
233  <img src="fig3-3-1.png" width="260" height="110"
234       class="matrix" alt="Regular parsing" />
235</p>
236
237<p> Changing the parsing order can help prevent the apparition of artifacts in
238error diffusion algorithms. This is <b>serpentine parsing</b>, where every odd
239line is parsed in reverse order (right to left): </p>
240
241<p style="text-align: center;">
242  <img src="fig3-3-2.png" width="260" height="110"
243       class="matrix" alt="Serpentine parsing" />
244</p>
245
246<p> The major problem with Floyd-Steinberg is the <b>worm artifacts</b> it
247creates. Here is an example of an image made of grey 0.9 dithered with standard
248Floyd-Steinberg and with <b>serpentine Floyd-Steinberg</b> [13 pp.266—267].
249Most of the worm artifacts have disappeared or were highly reduced: </p>
250
251<p style="text-align: center;">
252  <img src="out/lena3-3-1.png" width="256" height="256"
253       class="inline" alt="Floyd-Steinberg on grey 90%" />
254  <img src="out/lena3-3-2.png" width="256" height="256"
255       class="inline" alt="serpentine Floyd-Steinberg on grey 90%" />
256</p>
257
258<p> And here are the results of serpentine Floyd-Steinberg on Lena. Only a
259very close look will show the differences with standard Floyd-Steinberg, but
260a few of the artifacts did disappear: </p>
261
262<p style="text-align: center;">
263  <img src="out/lena3-1-2.png" width="256" height="256"
264       class="inline" alt="serpentine Floyd-Steinberg" />
265  <img src="out/grad3-1-2.png" width="32" height="256"
266       class="inline" alt="serpentine Floyd-Steinberg gradient" />
267</p>
268
269<p> <b>Riemersma dithering</b> [26] parses the image following a plane-filling
270<b>Hilbert curve</b> and only propagates the error of the last <i>q</i> pixels,
271weighting it with an exponential rule. The method is interesting and inventive,
272unfortunately the results are disappointing: structural artifacts are worse
273than with other error diffusion methods (shown here with <i>q = 16</i> and <i>r
274= 16</i>): </p>
275
276<p style="text-align: center;">
277  <img src="fig3-3-3.png" width="250" height="250"
278       class="matrix" alt="Hilbert curve parsing" />
279  <img src="out/lena3-3-3.png" width="256" height="256"
280       class="inline" alt="Riemersma dither on Hilbert curve" />
281  <img src="out/grad3-3-3.png" width="32" height="256"
282       class="inline" alt="Riemersma dither on Hilbert curve gradient" />
283</p>
284
285<p> A variation of Riemersma dithering uses a <b>Hilbert 2 curve</b>, giving
286slightly better results but still causing random artifacts here and there:
287</p>
288
289<p style="text-align: center;">
290  <img src="fig3-3-4.png" width="233" height="233"
291       class="matrix" alt="Hilbert 2 curve parsing" />
292  <img src="out/lena3-3-4.png" width="256" height="256"
293       class="inline" alt="Riemersma dither on Hilbert 2 curve" />
294  <img src="out/grad3-3-4.png" width="32" height="256"
295       class="inline" alt="Riemersma dither on Hilbert 2 curve gradient" />
296</p>
297
298<p> An inherent problem with plane-filling curves is that distances on the
299curve do not mean anything in image space. Riemersma dithering distributes
300error to pixels according to their distance on the curve rather than their
301distance in the image. </p>
302
303<p> We introduce <b>spatial Hilbert dithering</b> that addresses this issue
304by distributing the error according to spatial coordinates. We also get rid
305of the <i>r</i> parameter, choosing to distribute 100% of the error. </p>
306
307<p> This is spatial Hilbert dithering on a Hilbert curve and on a Hilbert 2
308curve. The results show a clear improvement over the original Riemersma
309algorithm, with far less noise and smoother low-gradient areas: </p>
310
311<p style="text-align: center;">
312  <img src="out/lena3-3-5.png" width="256" height="256"
313       class="inline" alt="spatial Hilbert dither on Hilbert curve" />
314  <img src="out/grad3-3-5.png" width="32" height="256"
315       class="inline" alt="spatial Hilbert dither on Hilbert curve gradient" />
316  <img src="out/lena3-3-6.png" width="256" height="256"
317       class="inline" alt="spatial Hilbert dither on Hilbert 2 curve" />
318  <img src="out/grad3-3-6.png" width="32" height="256"
319       class="inline" alt="spatial Hilbert dither on Hilbert 2 curve gradient" />
320</p>
321
322<p> <b>Dot diffusion</b> [14] is an error diffusion method by Donald E. Knuth
323that uses tileable matrices just like ordered dithering, except that the cell
324value order is taken into account for error propagation. Diagonal cells get
325half as much error as directly adjacent cells: </p>
326
327<p style="text-align: center;">
328  <img src="out/fig3-3-7b.png" width="121" height="121"
329       class="matrix" alt="Dot diffusion" />
330</p>
331
332<p> For instance, in the following example, cell 25’s error is propagated to
333cells 44, 36, 30, 34 and 49. Given the diagonal cells rule, cells 44, 30 and
33449 each get 1/7 of the error and cells 36 and 34 each get 2/7 of the error.
335Similarly, cell 63 gets 100% of cell 61’s error. </p>
336
337<p style="text-align: center;">
338  <img src="fig3-3-7.png" width="240" height="240"
339       class="matrix" alt="Dot diffusion matrix sample" />
340  <img src="out/lena3-3-7.png" width="256" height="256"
341       class="inline" alt="Dot diffusion" />
342  <img src="out/grad3-3-7.png" width="32" height="256"
343       class="inline" alt="Dot diffusion gradient" />
344</p>
345
346<p> The initial result is not extraordinary. But Knuth suggests applying a
347sharpen filter to the original image before applying dot diffusion. He also
348introduces a <i>zeta</i> value to deal with the size of laser printer dots,
349pretty similar to what we’ll see later as <b>gamma correction</b>. The
350following two images had a sharpening value of 0.9 applied to them. The image
351on the right shows <i>zeta = 0.2</i>: </p>
352
353<p style="text-align: center;">
354  <img src="out/lena3-3-8.png" width="256" height="256"
355       class="inline" alt="Dot diffusion sharpen 0.9" />
356  <img src="out/grad3-3-8.png" width="32" height="256"
357       class="inline" alt="Dot diffusion sharpen 0.9 gradient" />
358  <img src="out/lena3-3-9.png" width="256" height="256"
359       class="inline" alt="Dot diffusion sharpen 0.9 zeta 0.2" />
360  <img src="out/grad3-3-9.png" width="32" height="256"
361       class="inline" alt="Dot diffusion sharpen 0.9 zeta 0.2 gradient" />
362</p>
363
364<p> Do not get fooled by Knuth’s apparent good results. They specifically
365target dot printers and do not give terribly good results on a computer
366screen. Actually, a sharpening filter makes just any dithering method look
367better, even basic Floyd-Steinberg dithering (shown here with a sharpening
368value of 0.9, too): </p>
369
370<p style="text-align: center;">
371  <img src="out/lena3-3-10.png" width="256" height="256"
372       class="inline" alt="FS with sharpening" />
373  <img src="out/grad3-3-10.png" width="32" height="256"
374       class="inline" alt="FS with sharpening gradient" />
375</p>
376
377<p> Dot diffusion was reinvented 14 years later by Arney, Anderson and Ganawan
378without even citing Knuth. They call their method <b>omni-directional error
379diffusion</b>. Instead of using a clustered dot matrix like Knuth recommends
380for dot diffusion, they use a dispersed dot matrix, which gives far better
381results on a computer display. This is a 16×12 portion of that matrix: </p>
382
383<p style="text-align: center;">
384  <img src="out/fig3-3-11b.png" width="320" height="240"
385       class="matrix" alt="omni-directional ED matrix sample" />
386</p>
387
388<p> The preferred implementation of omni-directional error diffusion uses
389a slightly different propagation matrix, where top and bottom neighbours get
390more error than the others: </p>
391
392<p style="text-align: center;">
393  <img src="out/fig3-3-11.png" width="121" height="121"
394       class="matrix" alt="omni-directional ED" />
395  <img src="out/lena3-3-11.png" width="256" height="256"
396       class="inline" alt="omni-directional ED" />
397  <img src="out/grad3-3-11.png" width="32" height="256"
398       class="inline" alt="omni-directional ED gradient" />
399</p>
400
401<h3> 3.4. Variable coefficients error diffusion </h3>
402
403<p> Small error diffusion matrices usually cause artifacts to appear because
404the error is not propagated in enough directions. At the same time, such
405matrices also reduce the sharpened aspect common in error diffusion
406techniques. </p>
407
408<p> Ostromoukhov suggests error diffusion values that vary according to the
409input value. The list of 256 discrete value triplets for <i>d1</i>, <i>d2</i>
410and <i>d3</i> he provides [1] give pretty good results with serpentine parsing:
411</p>
412
413<p style="text-align: center;">
414  <img src="out/fig3-4-1.png" width="121" height="81"
415       class="matrix" alt="Ostromoukhov ED matrix" />
416  <img src="out/lena3-4-1.png" width="256" height="256"
417       class="inline" alt="Ostromoukhov ED" />
418  <img src="out/grad3-4-1.png" width="32" height="256"
419       class="inline" alt="Ostromoukhov ED gradient" />
420</p>
421
422<h3> 3.5. Block error diffusion </h3>
423
424<p> Sometimes, due to physical restrictions of the target media, output
425is limited to some combinations of pixel blocks, such as the ones shown
426below: </p>
427
428<p style="text-align: center;">
429  <img src="fig3-5-1.png" width="613" height="80"
430       class="matrix" alt="list of 2×2 pixel blocks" />
431</p>
432
433<p> It is still possible to dither the image, by doing it 4 pixels at a
434time and simply choosing the block from the list that minimises the global
435error within the 2×2 block: </p>
436
437<p style="text-align: center;">
438  <img src="out/lena3-5-1.png" width="256" height="256"
439       class="inline" alt="2×2 pixel block quantisation" />
440  <img src="out/grad3-5-1.png" width="32" height="256"
441       class="inline" alt="2×2 pixel block quantisation gradient" />
442</p>
443
444<p> Damera-Venkata and Evans introduce <b>block error diffusion</b> [23], which
445reuses traditional error diffusion methods such as Floyd-Steinberg but applies
446the same error value to all pixels of a given block. Only one error value is
447propagated, <i>a+b+c+d</i>, which is the global error within the block: </p>
448
449<p style="text-align: center; font-size: 2em;">
450  <img src="out/fig3-1-1.png" width="121" height="81"
451       class="math" alt="Floyd-Steinberg" />
452  ⊗
453  <img src="out/fig3-5-2b.png" width="81" height="81"
454       class="math" alt="2×2 balanced matrix" />
455  =
456  <img src="out/fig3-5-2.png" width="241" height="161"
457       class="math" alt="2×2-expanded Floyd-Steinberg" />
458</p>
459
460<p> Here are the results using the previous pixel blocks: </p>
461
462<p style="text-align: center;">
463  <img src="out/lena3-5-2.png" width="256" height="256"
464       class="inline" alt="2×2 block Floyd-Steinberg" />
465  <img src="out/grad3-5-2.png" width="32" height="256"
466       class="inline" alt="2×2 block Floyd-Steinberg gradient" />
467</p>
468
469<p> Carefully chosen blocks create constraints on the final picture that may
470be of artistic interest: </p>
471
472<p style="text-align: center;">
473  <img src="fig3-5-3.png" width="354" height="207"
474       class="matrix" alt="artistic 3×3 blocks" />
475  <img src="out/lena3-5-3.png" width="256" height="256"
476       class="inline" alt="3×3 block Floyd-Steinberg" />
477  <img src="out/grad3-5-3.png" width="32" height="256"
478       class="inline" alt="3×3 block Floyd-Steinberg gradient" />
479</p>
480
481<p> Using all possible pixel blocks is not equivalent to dithering the image
482pixel by pixel. This is due to both the block-choosing method, which only
483minimises the difference of mean values within blocks intead of the sum of
484local distances, and to the inefficient matrix coefficients, which propagate
485the error beyond immediate neighbours, causing the image to look sharpened.
486</p>
487
488<p> This example shows standard block Floyd-Steinberg using all possible 2×2
489blocks: </p>
490
491<p style="text-align: center;">
492  <img src="fig3-5-4.png" width="200" height="200"
493       class="matrix" alt="all possible 2×2 blocks" />
494  <img src="out/lena3-5-4.png" width="256" height="256"
495       class="inline" alt="full 2×2 block Floyd-Steinberg" />
496  <img src="out/grad3-5-4.png" width="32" height="256"
497       class="inline" alt="full 2×2 block Floyd-Steinberg gradient" />
498</p>
499
500<p> The results on the vertical gradient indicate poor block-choosing. In
501order to improve it, we introduce a modified, weighted intra-block error
502distribution matrix, still based on the original Floyd-Steinberg matrix: </p>
503
504<p style="text-align: center; font-size: 2em;">
505  <img src="out/fig3-1-1.png" width="121" height="81"
506       class="math" alt="Floyd-Steinberg" />
507  ⊗
508  <img src="out/fig3-5-5b.png" width="81" height="81"
509       class="math" alt="weighted 2×2 matrix" />
510  =
511  <img src="out/fig3-5-5.png" width="241" height="161"
512       class="math" alt="weighted 2×2 propagation matrix" />
513</p>
514
515<p> The result still looks sharpened, but shows considerably less noise: </p>
516
517<p style="text-align: center;">
518  <img src="out/lena3-5-5.png" width="256" height="256"
519       class="inline" alt="weighted full 2×2 block Floyd-Steinberg" />
520  <img src="out/grad3-5-5.png" width="32" height="256"
521       class="inline" alt="weighted full 2×2 block Floyd-Steinberg gradient" />
522</p>
523
524<h3> 3.6. Sub-block error diffusion </h3>
525
526<p> We introduce <b>sub-block error diffusion</b>, a novel technique improving
527on block error diffusion. It addresses the following observations: </p>
528
529<ul>
530  <li> it is not a requirement to propagate the error beyond the immediate
531       neighbours; since it causes a sharpen effect, we decide not to do it.
532       </li>
533  <li> the individual subpixels’ error should be propagated, not the
534       global block error. </li>
535  <li> subpixel <b>a</b>’s error is harder to compensate than subpixel
536       <b>d</b>’s because its immediate neighbours are already in the block
537       being processed, so we weight the sub-block matching in order to
538       prioritise pixel <b>a</b>’s matching. </li>
539</ul>
540
541<p> We use <i>m⋅n</i> error diffusion matrices, one for each of the current
542block’s pixels. Here are four error diffusion matrices for 2×2 blocks,
543generated from the standard Floyd-Steinberg matrix: </p>
544
545<p style="text-align: center;">
546  <img src="out/fig3-6-1a.png" width="161" height="121"
547       class="math" alt="sub-block 0,0 Floyd-Steinberg" />
548  <img src="out/fig3-6-1b.png" width="161" height="121"
549       class="math" alt="sub-block 1,0 Floyd-Steinberg" />
550</p>
551
552<p style="text-align: center;">
553  <img src="out/fig3-6-1c.png" width="161" height="121"
554       class="math" alt="sub-block 0,1 Floyd-Steinberg" />
555  <img src="out/fig3-6-1d.png" width="161" height="121"
556       class="math" alt="sub-block 1,1 Floyd-Steinberg" />
557</p>
558
559<p> The results are far better than with the original block error diffusion
560method. On the left, sub-block error diffusion with all possible 2×2 blocks.
561On the right, sub-block error diffusion restricted to the tiles seen in
5623.5: </p>
563
564<p style="text-align: center;">
565  <img src="out/lena3-6-1.png" width="256" height="256"
566       class="inline" alt="full 2×2 sub-block Floyd-Steinberg" />
567  <img src="out/grad3-6-1.png" width="32" height="256"
568       class="inline" alt="full 2×2 sub-block Floyd-Steinberg gradient" />
569  <img src="out/lena3-6-2.png" width="256" height="256"
570       class="inline" alt="2×2 lines sub-block Floyd-Steinberg" />
571  <img src="out/grad3-6-2.png" width="32" height="256"
572       class="inline" alt="2×2 lines sub-block Floyd-Steinberg gradient" />
573</p>
574
575<p> Similar error diffusion matrices can be generated for 3×3 blocks: </p>
576
577<p style="text-align: center;">
578  <img src="out/fig3-6-3a.png" width="150" height="120"
579       class="math" alt="sub-block 0,0/3×3 Floyd-Steinberg" />
580  <img src="out/fig3-6-3b.png" width="150" height="120"
581       class="math" alt="sub-block 1,0/3×3 Floyd-Steinberg" />
582  <img src="out/fig3-6-3c.png" width="150" height="120"
583       class="math" alt="sub-block 2,0/3×3 Floyd-Steinberg" />
584</p>
585
586<p style="text-align: center;">
587  <img src="out/fig3-6-3d.png" width="150" height="120"
588       class="math" alt="sub-block 0,1/3×3 Floyd-Steinberg" />
589  <img src="out/fig3-6-3e.png" width="150" height="120"
590       class="math" alt="sub-block 1,1/3×3 Floyd-Steinberg" />
591  <img src="out/fig3-6-3f.png" width="150" height="120"
592       class="math" alt="sub-block 2,1/3×3 Floyd-Steinberg" />
593</p>
594
595<p style="text-align: center;">
596  <img src="out/fig3-6-3g.png" width="150" height="120"
597       class="math" alt="sub-block 0,2/3×3 Floyd-Steinberg" />
598  <img src="out/fig3-6-3h.png" width="150" height="120"
599       class="math" alt="sub-block 1,2/3×3 Floyd-Steinberg" />
600  <img src="out/fig3-6-3i.png" width="150" height="120"
601       class="math" alt="sub-block 2,2/3×3 Floyd-Steinberg" />
602</p>
603
604<p> Here are the results with all the possible 3×3 blocks, and with the
605artistic 3×3 blocks seen in 3.5: </p>
606
607<p style="text-align: center;">
608  <img src="out/lena3-6-3.png" width="256" height="256"
609       class="inline" alt="3×3 sub-block Floyd-Steinberg" />
610  <img src="out/grad3-6-3.png" width="32" height="256"
611       class="inline" alt="3×3 sub-block Floyd-Steinberg gradient" />
612  <img src="out/lena3-6-4.png" width="256" height="256"
613       class="inline" alt="3×3 artistic sub-block Floyd-Steinberg" />
614  <img src="out/grad3-6-4.png" width="32" height="256"
615       class="inline" alt="3×3 artistic sub-block Floyd-Steinberg gradient" />
616</p>
617
618<div style="float: left;">
619   <a href="part2.html">Halftoning &lt;&lt;&lt;</a>
620</div>
621<div style="float: right;">
622   <a href="part4.html">&gt;&gt;&gt; Model-based dithering</a>
623</div>
624<div style="text-align: center;">
625   <a href="index.html">^^^ Index</a>
626</div>
627
628<?php $rev = '$Id$';
629      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
630
631</body>
632</html>
Note: See TracBrowser for help on using the repository browser.