source: www/study/part2.html @ 1956

Last change on this file since 1956 was 1956, checked in by Sam Hocevar, 14 years ago
  • Split document into an index page and four sections.
File size: 7.2 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="part1.html">Colour quantisation &lt;&lt;&lt;</a>
25</div>
26<div style="float: right;">
27   <a href="part3.html">&gt;&gt;&gt; Error diffusion</a>
28</div>
29<div style="text-align: center;">
30   <a href="index.html">^^^ Index</a>
31</div>
32
33<h2> 2. Halftoning patterns </h2>
34
35<h3> 2.1. Overview </h3>
36
37<p> Observe the following patterns. From a certain distance or assuming small
38enough pixels, they look like shades of gray despite being made of only black
39and white pixels: </p>
40
41<p style="text-align: center;">
42  <img src="pat2-1-1.png" width="320" height="80"
43       class="inline" alt="50% pattern" />
44</p>
45
46<p> We can do even better using additional patterns such as these 25% and
47the 75% halftone patterns: </p>
48
49<p style="text-align: center;">
50  <img src="pat2-1-2.png" width="320" height="80"
51       class="inline" alt="25% and 75% patterns" />
52</p>
53
54<p> This looks promising. Let’s try immediately on Lenna: we will use the
555-colour thresholding picture and replace the 0.25, 0.5 and 0.75 gray values
56with the above patterns: </p>
57
58<p style="text-align: center;">
59  <img src="out2-1-1.png" width="256" height="256"
60       class="inline" alt="25%, 50% and 75% halftoning" />
61  <img src="grad2-1-1.png" width="32" height="256"
62       class="inline" alt="25%, 50% and 75% halftoning gradient" />
63</p>
64
65<p> Not bad for a start. But there is a lot to improve. By the way, this
66technique is covered by Apple’s
67<a href="http://www.freepatentsonline.com/5761347.html">U.S. patent
685761347</a>. </p>
69
70<h3> 2.2. Screen artifacts </h3>
71
72<p> If your screen’s quality is not very good, you might experience slightly
73different shades of gray for the following patterns, despite being made of 50%
74black and 50% white pixels: </p>
75
76<p style="text-align: center;">
77  <img src="pat2-2-1.png" width="240" height="80"
78       class="inline" alt="screen imperfections" />
79</p>
80
81<p> Obviously the middle pattern looks far better to the human eye on a
82computer screen. Optimising patterns so that they look good to the human
83eye and don't create artifacts is a crucial element of a dithering
84algorithm. Here is another example of two patterns that approximate to
85the same shade of gray but may look slightly different from a distance: </p>
86
87<p style="text-align: center;">
88  <img src="pat2-2-2.png" width="320" height="80"
89       class="inline" alt="two different 25% patterns" />
90</p>
91
92<h3> 2.3. Ordered dithering </h3>
93
94<p> A generalisation of the dithering technique we just saw that uses a
95certain family of patterns is called <b>ordered dithering</b>. It is based on
96a <b>dither matrix</b> such as the following one: </p>
97
98<p style="text-align: center;">
99  <img src="fig2-3-1.png" width="80" height="80" alt="2×2 dither matrix" />
100</p>
101
102<p> This matrix is then repeated all over the image, and the cells are used
103as threshold values. In this case, pixels (0,0), (0,2), (0,4) etc. will be
104thresholded with a value of 0.2. Pixels (0,1), (0, 3), (0, 4) etc. will be
105thresholded with a value of 0.8, and so on, resulting in the image seen
106in 2.1. Here is a sample of what happens to groups of 4 even-coloured pixels
107of various gray values: </p>
108
109<p style="text-align: center;">
110  <img src="fig2-3-5.png" width="453" height="173"
111       alt="results of 2×2 dither matrix" />
112</p>
113
114<p> Different matrices can give very different results. This is a 4×4
115Bayer ordered dithering matrix: </p>
116
117<p style="text-align: center;">
118  <img src="fig2-3-2.png" width="160" height="160"
119       style="margin-right: 30px;" alt="4×4 Bayer matrix" />
120  <img src="out2-3-1.png" width="256" height="256"
121       class="inline" alt="4×4 Bayer dithering" />
122  <img src="grad2-3-1.png" width="32" height="256"
123       class="inline" alt="4×4 Bayer dithering gradient" />
124</p>
125
126<p> This 4×4 cluster dot matrix creates dot patterns that mimic the
127halftoning techniques used by newspapers: </p>
128
129<p style="text-align: center;">
130  <img src="fig2-3-3.png" width="160" height="160"
131       style="margin-right: 30px;" alt="4×4 cluster dot matrix" />
132  <img src="out2-3-2.png" width="256" height="256"
133       class="inline" alt="4×4 cluster dot dithering" />
134  <img src="grad2-3-2.png" width="32" height="256"
135       class="inline" alt="4×4 cluster dot dithering gradient" />
136</p>
137
138<p> This unusual 5×3 matrix creates artistic vertical line artifacts: </p>
139
140<p style="text-align: center;">
141  <img src="fig2-3-4.png" width="200" height="120"
142       style="margin-right: 30px;" alt="4×4 cluster dot matrix" />
143  <img src="out2-3-3.png" width="256" height="256"
144       class="inline" alt="4×4 cluster dot dithering" />
145  <img src="grad2-3-3.png" width="32" height="256"
146       class="inline" alt="4×4 cluster dot dithering gradient" />
147</p>
148
149<p> There are two major issues with ordered dithering. First, important
150<b>visual artifacts</b> may appear. Even Bayer ordered dithering causes
151weird cross-hatch pattern artifacts on some images. Second, dithering
152matrices do not depend on the original image and thus <b>do not take input
153data into account</b>: high frequency features in the image are often missed
154and, in some cases, cause even worse artifacts. </p>
155
156<h3> 2.4. Random dithering </h3>
157
158<p> Instead of using a deterministic threshold matrix, one can use a different
159random value for each pixel in the image. This technique is simply called
160<b>random dithering</b>. Here is an example with values uniformly chosen
161between 0 and 1: </p>
162
163<p style="text-align: center;">
164  <img src="out2-4-1.png" width="256" height="256"
165       class="inline" alt="random dithering" />
166  <img src="grad2-4-1.png" width="32" height="256"
167       class="inline" alt="random dithering gradient" />
168</p>
169
170<p> This is random dithering with threshold values chosen with a gaussian
171distribution (mean 0.5, standard deviation 0.15): </p>
172
173<p style="text-align: center;">
174  <img src="out2-4-2.png" width="256" height="256"
175       class="inline" alt="gaussian (0.5, 0.15) dithering" />
176  <img src="grad2-4-2.png" width="32" height="256"
177       class="inline" alt="gaussian (0.5, 0.15) dithering gradient" />
178</p>
179
180<div style="float: left;">
181   <a href="part1.html">Colour quantisation &lt;&lt;&lt;</a>
182</div>
183<div style="float: right;">
184   <a href="part3.html">&gt;&gt;&gt; Error diffusion</a>
185</div>
186<div style="text-align: center;">
187   <a href="index.html">^^^ Index</a>
188</div>
189
190<?php $rev = '$Id$';
191      include($_SERVER['DOCUMENT_ROOT'].'/footer.inc'); ?>
192
193</body>
194</html>
Note: See TracBrowser for help on using the repository browser.