source: www/study/part3.html @ 1968

Last change on this file since 1968 was 1968, checked in by Sam Hocevar, 13 years ago
  • Simple error diffusion.
File size: 8.1 KB
Line 
1<?php header("Content-Type: text/html; charset=utf-8"); ?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
3       "http://www.w3.org/TR/xhtml1/DTD/xhtml11.dtd">
4
5<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
6
7<head>
8   <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
9   <meta name="GENERATOR" content="vim" />
10   <meta name="Author" content="sam@zoy.org (Sam Hocevar)" />
11   <meta name="Description" content="Libcaca study" />
12   <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" />
13   <title>Libcaca study</title>
14   <link rel="icon" type="image/x-icon" href="/favicon.ico" />
15   <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
16   <link rel="stylesheet" type="text/css" href="/main.css" />
17</head>
18
19<body>
20
21<?php include($_SERVER["DOCUMENT_ROOT"]."/header.inc"); ?>
22
23<div style="float: left;">
24   <a href="part2.html">Halftoning patterns &lt;&lt;&lt;</a>
25</div>
26<div style="float: right;">
27   <a href="part4.html">&gt;&gt;&gt; Grayscale dithering</a>
28</div>
29<div style="text-align: center;">
30   <a href="index.html">^^^ Index</a>
31</div>
32
33<h2> 3. Error diffusion </h2>
34
35<p> The idea behind error diffusion is to compute the error caused by
36thresholding a given pixel and propagate it to neighbour pixels to
37compensate for the average intensity loss or gain. It is based upon the
38assumption that a slightly out-of-place pixel causes little visual harm.
39</p>
40
41<p> The error is computed by simply substracting the source value and the
42destination value. Destination value can be chosen by many means but does
43not impact the image a lot with most methods in comparison to the crucial
44choice of error distribution coefficients. </p>
45
46<p> This is the simplest error diffusion method. It thresholds the image
47to 0.5 and propagates 100% of the error the the next (right) pixel: </p>
48
49<p style="text-align: center;">
50  <img src="out3-0-1.png" width="256" height="256"
51       class="inline" alt="Simple error diffusion" />
52  <img src="grad3-0-1.png" width="32" height="256"
53       class="inline" alt="Simple error diffusion gradient" />
54</p>
55
56<h3> 3.1. Floyd-Steinberg error diffusion </h3>
57
58<p> The most famous error diffusion method is the <b>Floyd-Steinberg</b>
59algorithm. It propagates the error to more than one adjacent pixels using
60the following coefficients: </p>
61
62<p style="text-align: center;">
63  <img src="fig3-1-1.png" width="120" height="120" alt="Floyd-Steinberg" />
64</p>
65
66On the left is the result of the simple algorithm. The image on the right is
67a variant called <b>serpentine Floyd-Steinberg</b> which parses every odd line
68in reverse order (right to left). The results are very close to the original
69Floyd-Steinberg, but the method avoids artifacts in some corner cases: </p>
70
71<p style="text-align: center;">
72  <img src="out3-1-1.png" width="256" height="256"
73       class="inline" alt="Floyd-Steinberg error diffusion" />
74  <img src="grad3-1-1.png" width="32" height="256"
75       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
76  <img src="out3-1-2.png" width="256" height="256"
77       class="inline" alt="Floyd-Steinberg error diffusion" />
78  <img src="grad3-1-2.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> <b>Fan dithering</b> is a slight modification of Floyd-Steinberg with a
85very similar matrix: </p>
86
87<p style="text-align: center;">
88  <img src="fig3-2-1.png" width="160" height="120"
89       style="margin-right: 30px;" 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>Jarvis, Judice and Ninke dithering</b> uses a much more complex
97error diffusion matrix than Floyd-Steinberg: </p>
98
99<p style="text-align: center;">
100  <img src="fig3-2-2.png" width="200" height="160"
101       style="margin-right: 30px;" alt="Jarvis, Judice and Ninke" />
102  <img src="out3-2-2.png" width="256" height="256"
103       class="inline" alt="Jarvis, Judice and Ninke error diffusion" />
104  <img src="grad3-2-2.png" width="32" height="256"
105       class="inline" alt="Jarvis, Judice and Ninke error diffusion gradient" />
106</p>
107
108<p> <b>Stucki dithering</b> is a slight variation of Jarvis-Judice-Ninke
109dithering: </p>
110
111<p style="text-align: center;">
112  <img src="fig3-2-3.png" width="200" height="160"
113       style="margin-right: 30px;" alt="Stucki" />
114  <img src="out3-2-3.png" width="256" height="256"
115       class="inline" alt="Stucki error diffusion" />
116  <img src="grad3-2-3.png" width="32" height="256"
117       class="inline" alt="Stucki error diffusion gradient" />
118</p>
119
120<p> <b>Burkes dithering</b> is yet another variation: </p>
121
122<p style="text-align: center;">
123  <img src="fig3-2-4.png" width="200" height="120"
124       style="margin-right: 30px;" alt="Burkes" />
125  <img src="out3-2-4.png" width="256" height="256"
126       class="inline" alt="Burkes error diffusion" />
127  <img src="grad3-2-4.png" width="32" height="256"
128       class="inline" alt="Burkes error diffusion gradient" />
129</p>
130
131<p> Frankie Sierra came up with a few error diffusion matrices: <b>Sierra
132dithering</b> is a variation of Jarvis that is slightly faster because it
133propagates to fewer pixels, <b>Two-row Sierra</b> is a simplified version
134thereof, and <b>Filter Lite</b> is one of the simplest Floyd-Steinberg
135derivatives: </p>
136
137<p style="text-align: center;">
138  <img src="fig3-2-5.png" width="200" height="160"
139       style="margin-right: 30px;" alt="Sierra" />
140  <img src="out3-2-5.png" width="256" height="256"
141       class="inline" alt="Sierra error diffusion" />
142  <img src="grad3-2-5.png" width="32" height="256"
143       class="inline" alt="Sierra error diffusion gradient" />
144</p>
145
146<p style="text-align: center;">
147  <img src="fig3-2-6.png" width="200" height="120"
148       style="margin-right: 30px;" alt="Sierra" />
149  <img src="out3-2-6.png" width="256" height="256"
150       class="inline" alt="Sierra error diffusion" />
151  <img src="grad3-2-6.png" width="32" height="256"
152       class="inline" alt="Sierra error diffusion gradient" />
153</p>
154
155<p style="text-align: center;">
156  <img src="fig3-2-7.png" width="120" height="120"
157       style="margin-right: 30px;" alt="Sierra" />
158  <img src="out3-2-7.png" width="256" height="256"
159       class="inline" alt="Sierra error diffusion" />
160  <img src="grad3-2-7.png" width="32" height="256"
161       class="inline" alt="Sierra error diffusion gradient" />
162</p>
163
164<p> <b>Atkinson dithering</b> only propagates 75% of the error, leading to a
165loss of contrast around black and white areas, but better contrast in the
166midtones: </p>
167
168<p style="text-align: center;">
169  <img src="fig3-2-8.png" width="160" height="160"
170       style="margin-right: 30px;" alt="Atkinson" />
171  <img src="out3-2-8.png" width="256" height="256"
172       class="inline" alt="Atkinson error diffusion" />
173  <img src="grad3-2-8.png" width="32" height="256"
174       class="inline" alt="Atkinson error diffusion gradient" />
175</p>
176
177<!-- XXX: Stevenson-Arce is for hexagonal cells!
178<p> <b>Stevenson-Arce dithering</b>: </p>
179
180<p style="text-align: center;">
181  <img src="fig3-2-9.png" width="280" height="200"
182       style="margin-right: 30px;" alt="Stevenson-Arce" />
183  <img src="out3-2-9.png" width="256" height="256"
184       class="inline" alt="Stevenson-Arce error diffusion" />
185  <img src="grad3-2-9.png" width="32" height="256"
186       class="inline" alt="Stevenson-Arce error diffusion gradient" />
187</p>
188-->
189
190<!--
191<p> There are countless other error diffusion techniques. However it appears
192quite clearly that the overall quality of these algorithms has reached so high
193a point that
194quite obvious that quality will hardly improve
195whatever blablah
196-->
197
198<div style="float: left;">
199   <a href="part2.html">Halftoning patterns &lt;&lt;&lt;</a>
200</div>
201<div style="float: right;">
202   <a href="part4.html">&gt;&gt;&gt; Grayscale dithering</a>
203</div>
204<div style="text-align: center;">
205   <a href="index.html">^^^ Index</a>
206</div>
207
208<?php $rev = '$Id$';
209      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
210
211</body>
212</html>
Note: See TracBrowser for help on using the repository browser.