source: www/study/part4.html @ 2221

Revision 2221, 10.7 KB checked in by sam, 5 years ago (diff)
  • Gaussian human visual system model.
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 - 4. Model-based dithering" />
12   <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" />
13   <title>Libcaca study - 4. Model-based dithering</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   <style type="text/css">
18     .score td, .score th { padding: 2px 8px; }
19     .score th { background-color: #ddf; }
20     .score tr { background-color: white; padding: 10px; }
21     tr.hi { background-color: #dfd; }
22     table.score { padding: 0px; border: 0px; background-color: black;
23                   margin-left: auto; margin-right: auto; }
24   </style>
25</head>
26
27<body>
28
29<?php include($_SERVER["DOCUMENT_ROOT"]."/header.inc"); ?>
30
31<p> <span style="color: #aa0000; font-weight: bold;">Warning</span>: this
32document is still work in progress. Feel free to send comments but do not
33consider it final material. </p>
34
35<div style="float: left;">
36   <a href="part3.html">Error diffusion &lt;&lt;&lt;</a>
37</div>
38<div style="float: right;">
39   <a href="part5.html">&gt;&gt;&gt; Greyscale dithering</a>
40</div>
41<div style="text-align: center;">
42   <a href="index.html">^^^ Index</a>
43</div>
44
45<h2> 4. Model-based dithering </h2>
46
47<p> So far all dithering methods have relied on the assumption that carefully
48positioned black and white pixels gave the illusion of greyscales, but we
49have not stated exactly how the human eye reacted. Also, we do not have an
50automated way to compare the results of two different algorithms: judging that
51an algorithm was “better” was mostly a subjective process. </p>
52
53<p> In order to figure out what the human eye really sees, we need a <b>human
54visual system</b> (HVS) model. Countless models exist, and we are only going to
55focus on simple ones for now. </p>
56
57<h3> 4.1. Gaussian human visual system model </h3>
58
59<p> One of the simplest models is the <b>gaussian HVS model</b>. It states
60that the human eye acts like a gaussian convolution filter, slightly blurring
61pixel neighbourhoods and therefore simulating what the eye sees as distance
62from the image increases. This model, a simplified <b>luminance spatial
63frequency response formula</b>, can be expressed using the two-dimensional
64<i>e<small><sup> -(x²+y²)/2σ²</sup></small></i> function. The <i>σ</i>
65parameter sort of introduces the viewing distance into the expression. </p>
66
67<p> Using this model, it is possible to classify previously seen algorithms
68simply by convoluting both the source and the destination images with a
69gaussian filter, and computing their per-pixel <b>mean squared error</b>. This
70gives a better estimation of the dithering algorithm’s quality than simply
71computing a local, pixel-bound error: </p>
72
73<table class="score" cellspacing="1">
74  <tr><th>Chapter 1: Thresholding</th><th>Per-pixel error</th></tr>
75  <tr><td>0.5 thresholding</td><td>7.94776</td></tr>
76  <tr><td>0.4 thresholding</td><td>9.12175</td></tr>
77  <tr><td>0.6 thresholding</td><td>10.34139</td></tr>
78  <tr><td>dynamic thresholding</td><td>9.61939</td></tr>
79  <tr class="hi"><td>uniform random dithering</td><td>0.70330</td></tr>
80  <tr><td>gaussian random dithering</td><td>2.35023</td></tr>
81
82  <tr><th>Chapter 2: Halftoning</th><th>Per-pixel error</th></tr>
83  <tr><td>25/50/75% patterns dithering</td><td>0.46696</td></tr>
84  <tr><td>2×2 Bayer dithering</td><td>0.46838</td></tr>
85  <tr><td>4×4 Bayer dithering</td><td>0.08147</td></tr>
86  <tr class="hi"><td>8×8 Bayer dithering</td><td>0.06441</td></tr>
87  <tr><td>4×4 cluster dot dithering</td><td>0.15063</td></tr>
88  <tr><td>8×8 cluster dot dithering</td><td>0.86831</td></tr>
89  <tr><td>5×3 artistic line dithering</td><td>0.48860</td></tr>
90  <tr><td>perturbated 8×8 Bayer dithering</td><td>0.17141</td></tr>
91  <tr><td>random 3×3 dithering matrix selection</td><td>0.25194</td></tr>
92  <tr><td>“plus” pattern dithering</td><td>0.33622</td></tr>
93  <tr><td>“hex” pattern dithering</td><td>0.16222</td></tr>
94  <tr><td>“doubleplus” pattern dithering</td><td>0.12344</td></tr>
95  <tr><td>“hex2” pattern dithering</td><td>0.13097</td></tr>
96  <tr><td>4-wise supercell “plus” pattern dithering</td><td>0.07543</td></tr>
97  <tr><td>3-wise supercell “hex” pattern dithering</td><td>0.07406</td></tr>
98  <tr><td>4-wise supercell “doubleplus” pattern dithering</td><td>0.07135</td></tr>
99  <tr class="hi"><td>6th order dragon curve dithering</td><td>0.06806</td></tr>
100  <tr><td>3-wise supercell “hex2” pattern dithering</td><td>0.07907</td></tr>
101  <tr><td>9-wise supercell “hex2” pattern dithering</td><td>0.07818</td></tr>
102  <tr class="hi"><td>14×14 void-and-cluster dithering</td><td>0.06805</td></tr>
103  <tr class="hi"><td>25×25 void-and-cluster dithering</td><td>0.06317</td></tr>
104
105  <tr><th>Chapter 3: Error diffusion</th><th>Per-pixel error</th></tr>
106  <tr><td>naïve error diffusion</td><td>0.06428</td></tr>
107  <tr class="hi"><td>Floyd-Steinberg error diffusion</td><td>0.01863</td></tr>
108  <tr class="hi"><td>serpentine Floyd-Steinberg error diffusion</td><td>0.01866</td></tr>
109  <tr><td>Jarvis, Judice and Ninke dithering</td><td>0.06308</td></tr>
110  <tr class="hi"><td>Fan dithering</td><td>0.01743</td></tr>
111  <tr class="hi"><td>4-cell Shiau-Fan dithering</td><td>0.01798</td></tr>
112  <tr class="hi"><td>5-cell Shiau-Fan dithering</td><td>0.01963</td></tr>
113  <tr><td>Stucki dithering</td><td>0.05412</td></tr>
114  <tr><td>Burkes dithering</td><td>0.04042</td></tr>
115  <tr><td>Sierra dithering</td><td>0.05461</td></tr>
116  <tr><td>Sierra 2 dithering</td><td>0.05159</td></tr>
117  <tr class="hi"><td>Filter Lite</td><td>0.01619</td></tr>
118  <tr><td>Atkinson dithering</td><td>0.31084</td></tr>
119  <tr><td>Riemersma dithering on a Hilbert curve</td><td>0.06584</td></tr>
120  <tr><td>Riemersma dithering on a Hilbert 2 curve</td><td>0.06049</td></tr>
121  <tr><td>spatial Hilbert dithering on a Hilbert curve</td><td>0.06183</td></tr>
122  <tr><td>spatial Hilbert dithering on a Hilbert 2 curve</td><td>0.05294</td></tr>
123  <tr><td>dot diffusion</td><td>0.08182</td></tr>
124  <tr><td>dot diffusion with sharpen = 0.9</td><td>0.35153</td></tr>
125  <tr><td>dot diffusion with sharpen = 0.9 and zeta = 0.2</td><td>2.19802</td></tr>
126  <tr><td>serpentine Floyd-Steinberg with sharpen = 0.9</td><td>0.30999</td></tr>
127  <tr><td>omni-directional error diffusion</td><td>0.06881</td></tr>
128  <tr class="hi"><td>Ostromoukhov’s variable error diffusion</td><td>0.01787</td></tr>
129  <tr><td>nearest block matching with 2×2 line tiles</td><td>1.35230</td></tr>
130  <tr><td>block error diffusion with 2×2 line tiles</td><td>0.22605</td></tr>
131  <tr><td>block error diffusion with 3×3 artistic tiles</td><td>0.57511</td></tr>
132  <tr><td>block error diffusion with all 2×2 tiles</td><td>0.16047</td></tr>
133  <tr><td>block error diffusion with all 2×2 tiles and<br />weighted intra-block error distribution</td><td>0.10524</td></tr>
134  <tr><td>sub-block error diffusion with all 2×2 tiles</td><td>0.02629</td></tr>
135  <tr><td>sub-block error diffusion with 2×2 line tiles</td><td>0.06136</td></tr>
136  <tr><td>sub-block error diffusion with all 3×3 tiles</td><td>0.06571</td></tr>
137  <tr><td>sub-block error diffusion with 3×3 artistic tiles</td><td>0.22023</td></tr>
138<!-- DBS: 0.69090 0.07356 0.03409 0.02846 -->
139</table>
140
141<h3> 4.2. Direct binary search </h3>
142
143<p> We have already seen that standard error diffusion methods do not go back
144to pixels that have been set. <b>Direct binary search</b> [4] (DBS) is an
145iterative method that processes the image a fixed number of times, or until the
146error can no longer be minimised: </p>
147
148<ul>
149  <li> Generate an initial dithered image </li>
150  <li> Repeat until no changes can be applied:
151    <ul>
152      <li> Compute the global error between the original and the dithered
153           images </li>
154      <li> For each pixel in the dithered image:
155        <ul>
156          <li> Compute the effect on the error of toggling the value of the
157               current pixel </li>
158          <li> Compute the effect on the error of swapping the current pixel
159               with one of its immediate neighbours </li>
160          <li> If the error can be reduced, perform the corresponding
161               action </li>
162        </ul>
163      </li>
164    </ul>
165  </li>
166</ul>
167
168<p> The efficiency and quality of DBS depend on many implementation details,
169starting with the HVS model it uses to compute the error. Also, the initial
170image used as iteration zero will give poor results if pattern artifacts are
171already present. The order in which pixels are processed is important, too.
172Unfortunately, despite its very high-quality results, DBS is usually a very
173slow algorithm. </p>
174
175<p> Below is an example of the algorithm results. The HVS uses a 7×7
176convolution kernel of the <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>
177function. The initial image is randomly thresholded, and pixels are processed
178in raster order. Iterations 1, 2 and 5 are shown: </p>
179
180<p style="text-align: center;">
181  <img src="out/lena4-2-1.png" width="256" height="256"
182       class="inline" alt="direct binary search, iteration 0" />
183  <img src="out/grad4-2-1.png" width="32" height="256"
184       class="inline" alt="direct binary search, iteration 0 gradient" />
185  <img src="out/lena4-2-2.png" width="256" height="256"
186       class="inline" alt="direct binary search, iteration 1" />
187  <img src="out/grad4-2-2.png" width="32" height="256"
188       class="inline" alt="direct binary search, iteration 1 gradient" />
189</p>
190
191<p style="text-align: center;">
192  <img src="out/lena4-2-3.png" width="256" height="256"
193       class="inline" alt="direct binary search, iteration 2" />
194  <img src="out/grad4-2-3.png" width="32" height="256"
195       class="inline" alt="direct binary search, iteration 2 gradient" />
196  <img src="out/lena4-2-4.png" width="256" height="256"
197       class="inline" alt="direct binary search, iteration 5" />
198  <img src="out/grad4-2-4.png" width="32" height="256"
199       class="inline" alt="direct binary search, iteration 5 gradient" />
200</p>
201
202<div style="float: left;">
203   <a href="part3.html">Error diffusion &lt;&lt;&lt;</a>
204</div>
205<div style="float: right;">
206   <a href="part5.html">&gt;&gt;&gt; Greyscale dithering</a>
207</div>
208<div style="text-align: center;">
209   <a href="index.html">^^^ Index</a>
210</div>
211
212<?php $rev = '$Id$';
213      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
214
215</body>
216</html>
Note: See TracBrowser for help on using the repository browser.