source: www/study/part3.html @ 2190

Revision 2190, 28.4 KB checked in by sam, 5 years ago (diff)
  • Direct binary search.
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 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: </p>
441
442<p style="text-align: center;">
443  <img src="fig3-1-1.png" width="121" height="81"
444       class="math" alt="Floyd-Steinberg" />
445  ×
446  <img src="fig3-5-2b.png" width="81" height="81"
447       class="math" alt="2×2 balanced matrix" />
448  =
449  <img src="fig3-5-2.png" width="241" height="161"
450       class="math" alt="2×2-expanded Floyd-Steinberg" />
451</p>
452
453<p> Here are the results using the previous pixel blocks: </p>
454
455<p style="text-align: center;">
456  <img src="out3-5-2.png" width="256" height="256"
457       class="inline" alt="2×2 block Floyd-Steinberg" />
458  <img src="grad3-5-2.png" width="32" height="256"
459       class="inline" alt="2×2 block Floyd-Steinberg gradient" />
460</p>
461
462<p> Carefully chosen blocks create constraints on the final picture that may
463be of artistic interest: </p>
464
465<p style="text-align: center;">
466  <img src="fig3-5-3.png" width="354" height="207"
467       class="matrix" alt="artistic 3×3 blocks" />
468  <img src="out3-5-3.png" width="256" height="256"
469       class="inline" alt="3×3 block Floyd-Steinberg" />
470  <img src="grad3-5-3.png" width="32" height="256"
471       class="inline" alt="3×3 block Floyd-Steinberg gradient" />
472</p>
473
474<p> Using all possible pixel blocks is not equivalent to dithering the image
475pixel by pixel. This is due to both the block-choosing method, which only
476minimises the difference of mean values within blocks intead of the sum of
477local distances, and to the inefficient matrix coefficients, which propagate
478the error beyond immediate neighbours, causing the image to look sharpened.
479</p>
480
481<p> This example shows standard block Floyd-Steinberg using all possible 2×2
482blocks: </p>
483
484<p style="text-align: center;">
485  <img src="fig3-5-4.png" width="200" height="200"
486       class="matrix" alt="all possible 2×2 blocks" />
487  <img src="out3-5-4.png" width="256" height="256"
488       class="inline" alt="full 2×2 block Floyd-Steinberg" />
489  <img src="grad3-5-4.png" width="32" height="256"
490       class="inline" alt="full 2×2 block Floyd-Steinberg gradient" />
491</p>
492
493<p> The results on the vertical gradient indicate poor block-choosing. In
494order to improve it, we introduce a modified, weighed intra-block error
495distribution matrix, still based on the original Floyd-Steinberg matrix: </p>
496
497<p style="text-align: center;">
498  <img src="fig3-1-1.png" width="121" height="81"
499       class="math" alt="Floyd-Steinberg" />
500  ×
501  <img src="fig3-5-5b.png" width="81" height="81"
502       class="math" alt="weighed 2×2 matrix" />
503  =
504  <img src="fig3-5-5.png" width="241" height="161"
505       class="math" alt="weighed 2×2 propagation matrix" />
506</p>
507
508<p> The result still looks sharpened, but shows considerably less noise: </p>
509
510<p style="text-align: center;">
511  <img src="out3-5-5.png" width="256" height="256"
512       class="inline" alt="weighed full 2×2 block Floyd-Steinberg" />
513  <img src="grad3-5-5.png" width="32" height="256"
514       class="inline" alt="weighed full 2×2 block Floyd-Steinberg gradient" />
515</p>
516
517<h3> 3.6. Sub-block error diffusion </h3>
518
519<p> We introduce <b>sub-block error diffusion</b>, a novel technique improving
520on block error diffusion. It addresses the following observations: </p>
521
522<ul>
523  <li> it is not a requirement to propagate the error beyond the immediate
524       neighbours; since it causes a sharpen effect, we decide not to do it.
525       </li>
526  <li> the individual subpixels’ error should be propagated, not the
527       global block error. </li>
528  <li> subpixel <b>a</b>’s error is harder to compensate than subpixel
529       <b>d</b>’s because its immediate neighbours are already in the block
530       being processed, so we weigh the sub-block matching in order to
531       prioritise pixel <b>a</b>’s matching. </li>
532</ul>
533
534<p> We use <i>m×n</i> error diffusion matrices, one for each of the current
535block’s pixels. Here are four error diffusion matrices for 2×2 blocks,
536generated from the standard Floyd-Steinberg matrix: </p>
537
538<p style="text-align: center;">
539  <img src="fig3-6-1a.png" width="161" height="121"
540       class="math" alt="sub-block 0,0 Floyd-Steinberg" />
541  <img src="fig3-6-1b.png" width="161" height="121"
542       class="math" alt="sub-block 1,0 Floyd-Steinberg" />
543</p>
544
545<p style="text-align: center;">
546  <img src="fig3-6-1c.png" width="161" height="121"
547       class="math" alt="sub-block 0,1 Floyd-Steinberg" />
548  <img src="fig3-6-1d.png" width="161" height="121"
549       class="math" alt="sub-block 1,1 Floyd-Steinberg" />
550</p>
551
552<p> The results are far better than with the original block error diffusion
553method. On the left, sub-block error diffusion with all possible 2×2 blocks.
554On the right, sub-block error diffusion restricted to the tiles seen in
5553.5: </p>
556
557<p style="text-align: center;">
558  <img src="out3-6-1.png" width="256" height="256"
559       class="inline" alt="full 2×2 sub-block Floyd-Steinberg" />
560  <img src="grad3-6-1.png" width="32" height="256"
561       class="inline" alt="full 2×2 sub-block Floyd-Steinberg gradient" />
562  <img src="out3-6-2.png" width="256" height="256"
563       class="inline" alt="2×2 lines sub-block Floyd-Steinberg" />
564  <img src="grad3-6-2.png" width="32" height="256"
565       class="inline" alt="2×2 lines sub-block Floyd-Steinberg gradient" />
566</p>
567
568<p> Similar error diffusion matrices can be generated for 3×3 blocks: </p>
569
570<p style="text-align: center;">
571  <img src="fig3-6-3a.png" width="150" height="120"
572       class="math" alt="sub-block 0,0/3×3 Floyd-Steinberg" />
573  <img src="fig3-6-3b.png" width="150" height="120"
574       class="math" alt="sub-block 1,0/3×3 Floyd-Steinberg" />
575  <img src="fig3-6-3c.png" width="150" height="120"
576       class="math" alt="sub-block 2,0/3×3 Floyd-Steinberg" />
577</p>
578
579<p style="text-align: center;">
580  <img src="fig3-6-3d.png" width="150" height="120"
581       class="math" alt="sub-block 0,1/3×3 Floyd-Steinberg" />
582  <img src="fig3-6-3e.png" width="150" height="120"
583       class="math" alt="sub-block 1,1/3×3 Floyd-Steinberg" />
584  <img src="fig3-6-3f.png" width="150" height="120"
585       class="math" alt="sub-block 2,1/3×3 Floyd-Steinberg" />
586</p>
587
588<p style="text-align: center;">
589  <img src="fig3-6-3g.png" width="150" height="120"
590       class="math" alt="sub-block 0,2/3×3 Floyd-Steinberg" />
591  <img src="fig3-6-3h.png" width="150" height="120"
592       class="math" alt="sub-block 1,2/3×3 Floyd-Steinberg" />
593  <img src="fig3-6-3i.png" width="150" height="120"
594       class="math" alt="sub-block 2,2/3×3 Floyd-Steinberg" />
595</p>
596
597<p> Here are the results with all the possible 3×3 blocks, and with the
598artistic 3×3 blocks seen in 3.5: </p>
599
600<p style="text-align: center;">
601  <img src="out3-6-3.png" width="256" height="256"
602       class="inline" alt="3×3 sub-block Floyd-Steinberg" />
603  <img src="grad3-6-3.png" width="32" height="256"
604       class="inline" alt="3×3 sub-block Floyd-Steinberg gradient" />
605  <img src="out3-6-4.png" width="256" height="256"
606       class="inline" alt="3×3 artistic sub-block Floyd-Steinberg" />
607  <img src="grad3-6-4.png" width="32" height="256"
608       class="inline" alt="3×3 artistic sub-block Floyd-Steinberg gradient" />
609</p>
610
611<h3> 3.7. Direct binary search </h3>
612
613<p> We have already seen that standard error diffusion methods do not go back
614to pixels that have been set. <b>Direct binary search</b> (DBS) is an iterative
615method that processes the image a fixed number of times, or until the error
616can no longer be minimised: </p>
617
618<ul>
619  <li> Generate an initial dithered image </li>
620  <li> Repeat until no changes can be applied:
621    <ul>
622      <li> Compute the global error between the original and the dithered
623           images </li>
624      <li> For each pixel in the dithered image:
625        <ul>
626          <li> Compute the effect on the error of toggling the value of the
627               current pixel </li>
628          <li> Compute the effect on the error of swapping the current pixel
629               with one of its immediate neighbours </li>
630          <li> If the error can be reduced, perform the corresponding
631               action </li>
632        </ul>
633      </li>
634    </ul>
635  </li>
636</ul>
637
638<p> DBS relies on a <b>human visual system</b> model: instead of considering a
639local, pixel-bound error value, it tries to figure what the human eye really
640sees, by applying a filter to both the source and destination images, and then
641computes the error between these filtered signals. </p>
642
643<p> The efficiency and quality of DBS depend on many implementation details,
644starting with the HVS model. Also, the initial image used as iteration zero
645will give poor results if pattern artifacts are already present. And the order
646in which pixels are processed is important, too. Unfortunately, despite its
647very high-quality results, DBS is usually a very slow algorithm. </p>
648
649<p> Below are an example of the algorithm results. We use a 7×7 convolution
650kernel to approximate the human visual system, using a simplified luminance
651spatial frequency response formula:
652<i>e<small><sup> -sqrt(x²+y²)</sup></small></i>. The initial image is
653randomly thresholded, and pixels are processed in raster order. Iterations 1,
6542 and 5 are shown: </p>
655
656<p style="text-align: center;">
657  <img src="out3-7-1.png" width="256" height="256"
658       class="inline" alt="direct binary search, iteration 0" />
659  <img src="grad3-7-1.png" width="32" height="256"
660       class="inline" alt="direct binary search, iteration 0 gradient" />
661  <img src="out3-7-2.png" width="256" height="256"
662       class="inline" alt="direct binary search, iteration 1" />
663  <img src="grad3-7-2.png" width="32" height="256"
664       class="inline" alt="direct binary search, iteration 1 gradient" />
665</p>
666
667<p style="text-align: center;">
668  <img src="out3-7-3.png" width="256" height="256"
669       class="inline" alt="direct binary search, iteration 2" />
670  <img src="grad3-7-3.png" width="32" height="256"
671       class="inline" alt="direct binary search, iteration 2 gradient" />
672  <img src="out3-7-4.png" width="256" height="256"
673       class="inline" alt="direct binary search, iteration 5" />
674  <img src="grad3-7-4.png" width="32" height="256"
675       class="inline" alt="direct binary search, iteration 5 gradient" />
676</p>
677
678<div style="float: left;">
679   <a href="part2.html">Halftoning &lt;&lt;&lt;</a>
680</div>
681<div style="float: right;">
682   <a href="part4.html">&gt;&gt;&gt; Greyscale dithering</a>
683</div>
684<div style="text-align: center;">
685   <a href="index.html">^^^ Index</a>
686</div>
687
688<?php $rev = '$Id$';
689      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
690
691</body>
692</html>
Note: See TracBrowser for help on using the repository browser.