source: www/study/part3.html @ 1974

Revision 1974, 8.1 KB checked in by sam, 6 years ago (diff)
  • Removed the useless top line in each error diffusion matrix.
  • Replaced "0" with "x" to show where the error starts from.
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, in order 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. It is
48quite impressive given its simplicity but causes important visual artifacts:
49</p>
50
51<p style="text-align: center;">
52  <img src="out3-0-1.png" width="256" height="256"
53       class="inline" alt="Simple error diffusion" />
54  <img src="grad3-0-1.png" width="32" height="256"
55       class="inline" alt="Simple error diffusion gradient" />
56</p>
57
58<h3> 3.1. Floyd-Steinberg error diffusion </h3>
59
60<p> The most famous error diffusion method is the <b>Floyd-Steinberg</b>
61algorithm. It propagates the error to more than one adjacent pixels using
62the following coefficients: </p>
63
64<p style="text-align: center;">
65  <img src="fig3-1-1.png" width="120" height="80" alt="Floyd-Steinberg" />
66</p>
67
68On the left is the result of the simple algorithm. The image on the right is
69a variant called <b>serpentine Floyd-Steinberg</b> which parses every odd line
70in reverse order (right to left). The results are very close to the original
71Floyd-Steinberg, but the method avoids artifacts in some corner cases: </p>
72
73<p style="text-align: center;">
74  <img src="out3-1-1.png" width="256" height="256"
75       class="inline" alt="Floyd-Steinberg error diffusion" />
76  <img src="grad3-1-1.png" width="32" height="256"
77       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
78  <img src="out3-1-2.png" width="256" height="256"
79       class="inline" alt="Floyd-Steinberg error diffusion" />
80  <img src="grad3-1-2.png" width="32" height="256"
81       class="inline" alt="Floyd-Steinberg error diffusion gradient" />
82</p>
83
84<h3> 3.2. Floyd-Steinberg derivatives </h3>
85
86<p> <b>Fan dithering</b> is a slight modification of Floyd-Steinberg with a
87very similar matrix: </p>
88
89<p style="text-align: center;">
90  <img src="fig3-2-1.png" width="160" height="80"
91       style="margin-right: 30px;" alt="Fan" />
92  <img src="out3-2-1.png" width="256" height="256"
93       class="inline" alt="Fan error diffusion" />
94  <img src="grad3-2-1.png" width="32" height="256"
95       class="inline" alt="Fan error diffusion gradient" />
96</p>
97
98<p> <b>Jarvis, Judice and Ninke dithering</b> uses a much more complex
99error diffusion matrix than Floyd-Steinberg: </p>
100
101<p style="text-align: center;">
102  <img src="fig3-2-2.png" width="200" height="120"
103       style="margin-right: 30px;" alt="Jarvis, Judice and Ninke" />
104  <img src="out3-2-2.png" width="256" height="256"
105       class="inline" alt="Jarvis, Judice and Ninke error diffusion" />
106  <img src="grad3-2-2.png" width="32" height="256"
107       class="inline" alt="Jarvis, Judice and Ninke error diffusion gradient" />
108</p>
109
110<p> <b>Stucki dithering</b> is a slight variation of Jarvis-Judice-Ninke
111dithering: </p>
112
113<p style="text-align: center;">
114  <img src="fig3-2-3.png" width="200" height="120"
115       style="margin-right: 30px;" alt="Stucki" />
116  <img src="out3-2-3.png" width="256" height="256"
117       class="inline" alt="Stucki error diffusion" />
118  <img src="grad3-2-3.png" width="32" height="256"
119       class="inline" alt="Stucki error diffusion gradient" />
120</p>
121
122<p> <b>Burkes dithering</b> is yet another variation: </p>
123
124<p style="text-align: center;">
125  <img src="fig3-2-4.png" width="200" height="80"
126       style="margin-right: 30px;" alt="Burkes" />
127  <img src="out3-2-4.png" width="256" height="256"
128       class="inline" alt="Burkes error diffusion" />
129  <img src="grad3-2-4.png" width="32" height="256"
130       class="inline" alt="Burkes error diffusion gradient" />
131</p>
132
133<p> Frankie Sierra came up with a few error diffusion matrices: <b>Sierra
134dithering</b> is a variation of Jarvis that is slightly faster because it
135propagates to fewer pixels, <b>Two-row Sierra</b> is a simplified version
136thereof, and <b>Filter Lite</b> is one of the simplest Floyd-Steinberg
137derivatives: </p>
138
139<p style="text-align: center;">
140  <img src="fig3-2-5.png" width="200" height="120"
141       style="margin-right: 30px;" alt="Sierra" />
142  <img src="out3-2-5.png" width="256" height="256"
143       class="inline" alt="Sierra error diffusion" />
144  <img src="grad3-2-5.png" width="32" height="256"
145       class="inline" alt="Sierra error diffusion gradient" />
146</p>
147
148<p style="text-align: center;">
149  <img src="fig3-2-6.png" width="200" height="80"
150       style="margin-right: 30px;" alt="Sierra" />
151  <img src="out3-2-6.png" width="256" height="256"
152       class="inline" alt="Sierra error diffusion" />
153  <img src="grad3-2-6.png" width="32" height="256"
154       class="inline" alt="Sierra error diffusion gradient" />
155</p>
156
157<p style="text-align: center;">
158  <img src="fig3-2-7.png" width="120" height="80"
159       style="margin-right: 30px;" alt="Sierra" />
160  <img src="out3-2-7.png" width="256" height="256"
161       class="inline" alt="Sierra error diffusion" />
162  <img src="grad3-2-7.png" width="32" height="256"
163       class="inline" alt="Sierra error diffusion gradient" />
164</p>
165
166<p> <b>Atkinson dithering</b> only propagates 75% of the error, leading to a
167loss of contrast around black and white areas, but better contrast in the
168midtones: </p>
169
170<p style="text-align: center;">
171  <img src="fig3-2-8.png" width="160" height="120"
172       style="margin-right: 30px;" alt="Atkinson" />
173  <img src="out3-2-8.png" width="256" height="256"
174       class="inline" alt="Atkinson error diffusion" />
175  <img src="grad3-2-8.png" width="32" height="256"
176       class="inline" alt="Atkinson error diffusion gradient" />
177</p>
178
179<!-- XXX: Stevenson-Arce is for hexagonal cells!
180<p> <b>Stevenson-Arce dithering</b>: </p>
181
182<p style="text-align: center;">
183  <img src="fig3-2-9.png" width="280" height="160"
184       style="margin-right: 30px;" alt="Stevenson-Arce" />
185  <img src="out3-2-9.png" width="256" height="256"
186       class="inline" alt="Stevenson-Arce error diffusion" />
187  <img src="grad3-2-9.png" width="32" height="256"
188       class="inline" alt="Stevenson-Arce error diffusion gradient" />
189</p>
190-->
191
192<!--
193<p> There are countless other error diffusion techniques. However it appears
194quite clearly that the overall quality of these algorithms has reached so high
195a point that
196quite obvious that quality will hardly improve
197whatever blablah
198-->
199
200<div style="float: left;">
201   <a href="part2.html">Halftoning patterns &lt;&lt;&lt;</a>
202</div>
203<div style="float: right;">
204   <a href="part4.html">&gt;&gt;&gt; Grayscale dithering</a>
205</div>
206<div style="text-align: center;">
207   <a href="index.html">^^^ Index</a>
208</div>
209
210<?php $rev = '$Id$';
211      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
212
213</body>
214</html>
Note: See TracBrowser for help on using the repository browser.