Changeset 1956
- Timestamp:
- Nov 14, 2007, 1:05:53 AM (13 years ago)
- Location:
- www/study
- Files:
-
- 4 added
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
www/study/index.html
r1955 r1956 20 20 21 21 <?php include($_SERVER["DOCUMENT_ROOT"]."/header.inc"); ?> 22 23 <!--<div style="float: left;"> 24 <a href=""></a> 25 </div>--> 26 <div style="float: right;"> 27 <a href="part1.html">>>> Colour quantisation</a> 28 </div> 29 30 <br style="clear: both;" /> 22 31 23 32 <h2> Libcaca study: the science behind colour ASCII art </h2> … … 59 68 512×512 image. </p> 60 69 61 <h2> 1. Colour quantisation </h2> 62 63 <p> Colour quantisation is a very old and common computer graphics problem. 64 Many methods exist to do the task, and their efficiency depends on several 65 parameters: </p> 70 <h3> Sections </h3> 66 71 67 72 <ul> 68 <li> the input image: is it a photograph? a vector drawing? a composition 69 of both? </li> 70 <li> the target media: is it a computer screen? if so, what are the size 71 and the position of the pixels? is it a printed document? if so, 72 what kind of paper? what kind of ink? or maybe the conversion should 73 be optimised for both targets? </li> 74 <li> the quality requirements: for instance, can contrast be raised for 75 a more appealing result at the expense of accuracy? 76 <li> the allowed computation time: do we need 50fps or can we afford to 77 wait 10 seconds for a better result? </li> 73 <li> <a href="part1.html">1. Colour quantisation</a> </li> 74 <li> <a href="part2.html">2. Halftoning patterns</a> </li> 75 <li> <a href="part3.html">3. Error diffusion</a> </li> 76 <li> <a href="part4.html">4. Grayscale dithering</a> </li> 78 77 </ul> 79 78 80 <h3> 1.1. Black and white thresholding </h3> 81 82 <p> Since a grayscale pixel has a value between 0 and 1, a fast method 83 to convert the image to black and white is to set all pixels below 0.5 84 to black and all pixels above 0.5 to white. This method is called 85 <b>thresholding</b> and, in our case, results in the following image: </p> 86 87 <p style="text-align: center;"> 88 <img src="out1-1-1.png" width="256" height="256" 89 class="inline" alt="50% threshold" /> 90 <img src="grad1-1-1.png" width="32" height="256" 91 class="inline" alt="50% threshold gradient" /> 92 </p> 93 94 <p> Not that bad, but we were pretty lucky: the original image’s brightness 95 was rather well balanced. A lot of detail is lost, though. Different results 96 can be obtained by choosing “threshold values” other than 0.5, for instance 97 0.4 or 0.6, resulting in a much brighter or darker image: </p> 98 99 <p style="text-align: center;"> 100 <img src="out1-1-2.png" width="256" height="256" 101 class="inline" alt="40% threshold" /> 102 <img src="grad1-1-2.png" width="32" height="256" 103 class="inline" alt="40% threshold gradient" /> 104 <img src="out1-1-3.png" width="256" height="256" 105 class="inline" alt="60% threshold" /> 106 <img src="grad1-1-3.png" width="32" height="256" 107 class="inline" alt="60% threshold gradient" /> 108 </p> 109 110 <p> Choosing the best thresholding value for a given image is called 111 <b>average dithering</b>. But even with the best value, the results will 112 not improve tremendously. </p> 113 114 <h3> 1.2. Grayscale thresholding </h3> 115 116 <p> Better results can be achieved with a slightly bigger palette. Here is 117 thresholding applied to a 3-colour and to a 5-colour palette: </p> 118 119 <p style="text-align: center;"> 120 <img src="out1-2-1.png" width="256" height="256" 121 class="inline" alt="3-colour threshold" /> 122 <img src="grad1-2-1.png" width="32" height="256" 123 class="inline" alt="3-colour threshold gradient" /> 124 <img src="out1-2-2.png" width="256" height="256" 125 class="inline" alt="4-colour threshold" /> 126 <img src="grad1-2-2.png" width="32" height="256" 127 class="inline" alt="4-colour threshold gradient" /> 128 </p> 129 130 <h2> 2. Halftoning patterns </h2> 131 132 <h3> 2.1. Overview </h3> 133 134 <p> Observe the following patterns. From a certain distance or assuming small 135 enough pixels, they look like shades of gray despite being made of only black 136 and white pixels: </p> 137 138 <p style="text-align: center;"> 139 <img src="pat2-1-1.png" width="320" height="80" 140 class="inline" alt="50% pattern" /> 141 </p> 142 143 <p> We can do even better using additional patterns such as these 25% and 144 the 75% halftone patterns: </p> 145 146 <p style="text-align: center;"> 147 <img src="pat2-1-2.png" width="320" height="80" 148 class="inline" alt="25% and 75% patterns" /> 149 </p> 150 151 <p> This looks promising. Let’s try immediately on Lenna: we will use the 152 5-colour thresholding picture and replace the 0.25, 0.5 and 0.75 gray values 153 with the above patterns: </p> 154 155 <p style="text-align: center;"> 156 <img src="out2-1-1.png" width="256" height="256" 157 class="inline" alt="25%, 50% and 75% halftoning" /> 158 <img src="grad2-1-1.png" width="32" height="256" 159 class="inline" alt="25%, 50% and 75% halftoning gradient" /> 160 </p> 161 162 <p> Not bad for a start. But there is a lot to improve. By the way, this 163 technique is covered by Apple’s 164 <a href="http://www.freepatentsonline.com/5761347.html">U.S. patent 165 5761347</a>. </p> 166 167 <h3> 2.2. Screen artifacts </h3> 168 169 <p> If your screen’s quality is not very good, you might experience slightly 170 different shades of gray for the following patterns, despite being made of 50% 171 black and 50% white pixels: </p> 172 173 <p style="text-align: center;"> 174 <img src="pat2-2-1.png" width="240" height="80" 175 class="inline" alt="screen imperfections" /> 176 </p> 177 178 <p> Obviously the middle pattern looks far better to the human eye on a 179 computer screen. Optimising patterns so that they look good to the human 180 eye and don't create artifacts is a crucial element of a dithering 181 algorithm. Here is another example of two patterns that approximate to 182 the same shade of gray but may look slightly different from a distance: </p> 183 184 <p style="text-align: center;"> 185 <img src="pat2-2-2.png" width="320" height="80" 186 class="inline" alt="two different 25% patterns" /> 187 </p> 188 189 <h3> 2.3. Ordered dithering </h3> 190 191 <p> A generalisation of the dithering technique we just saw that uses a 192 certain family of patterns is called <b>ordered dithering</b>. It is based on 193 a <b>dither matrix</b> such as the following one: </p> 194 195 <p style="text-align: center;"> 196 <img src="fig2-3-1.png" width="80" height="80" alt="2×2 dither matrix" /> 197 </p> 198 199 <p> This matrix is then repeated all over the image, and the cells are used 200 as threshold values. In this case, pixels (0,0), (0,2), (0,4) etc. will be 201 thresholded with a value of 0.2. Pixels (0,1), (0, 3), (0, 4) etc. will be 202 thresholded with a value of 0.8, and so on, resulting in the image seen 203 in 2.1. Here is a sample of what happens to groups of 4 even-coloured pixels 204 of various gray values: </p> 205 206 <p style="text-align: center;"> 207 <img src="fig2-3-5.png" width="453" height="173" 208 alt="results of 2×2 dither matrix" /> 209 </p> 210 211 <p> Different matrices can give very different results. This is a 4×4 212 Bayer ordered dithering matrix: </p> 213 214 <p style="text-align: center;"> 215 <img src="fig2-3-2.png" width="160" height="160" 216 style="margin-right: 30px;" alt="4×4 Bayer matrix" /> 217 <img src="out2-3-1.png" width="256" height="256" 218 class="inline" alt="4×4 Bayer dithering" /> 219 <img src="grad2-3-1.png" width="32" height="256" 220 class="inline" alt="4×4 Bayer dithering gradient" /> 221 </p> 222 223 <p> This 4×4 cluster dot matrix creates dot patterns that mimic the 224 halftoning techniques used by newspapers: </p> 225 226 <p style="text-align: center;"> 227 <img src="fig2-3-3.png" width="160" height="160" 228 style="margin-right: 30px;" alt="4×4 cluster dot matrix" /> 229 <img src="out2-3-2.png" width="256" height="256" 230 class="inline" alt="4×4 cluster dot dithering" /> 231 <img src="grad2-3-2.png" width="32" height="256" 232 class="inline" alt="4×4 cluster dot dithering gradient" /> 233 </p> 234 235 <p> This unusual 5×3 matrix creates artistic vertical line artifacts: </p> 236 237 <p style="text-align: center;"> 238 <img src="fig2-3-4.png" width="200" height="120" 239 style="margin-right: 30px;" alt="4×4 cluster dot matrix" /> 240 <img src="out2-3-3.png" width="256" height="256" 241 class="inline" alt="4×4 cluster dot dithering" /> 242 <img src="grad2-3-3.png" width="32" height="256" 243 class="inline" alt="4×4 cluster dot dithering gradient" /> 244 </p> 245 246 <p> There are two major issues with ordered dithering. First, important 247 <b>visual artifacts</b> may appear. Even Bayer ordered dithering causes 248 weird cross-hatch pattern artifacts on some images. Second, dithering 249 matrices do not depend on the original image and thus <b>do not take input 250 data into account</b>: high frequency features in the image are often missed 251 and, in some cases, cause even worse artifacts. </p> 252 253 <h3> 2.4. Random dithering </h3> 254 255 <p> Instead of using a deterministic threshold matrix, one can use a different 256 random value for each pixel in the image. This technique is simply called 257 <b>random dithering</b>. Here is an example with values uniformly chosen 258 between 0 and 1: </p> 259 260 <p style="text-align: center;"> 261 <img src="out2-4-1.png" width="256" height="256" 262 class="inline" alt="random dithering" /> 263 <img src="grad2-4-1.png" width="32" height="256" 264 class="inline" alt="random dithering gradient" /> 265 </p> 266 267 <p> This is random dithering with threshold values chosen with a gaussian 268 distribution (mean 0.5, standard deviation 0.15): </p> 269 270 <p style="text-align: center;"> 271 <img src="out2-4-2.png" width="256" height="256" 272 class="inline" alt="gaussian (0.5, 0.15) dithering" /> 273 <img src="grad2-4-2.png" width="32" height="256" 274 class="inline" alt="gaussian (0.5, 0.15) dithering gradient" /> 275 </p> 276 277 <h2> 3. Error diffusion </h2> 278 279 <p> The idea behind error diffusion is to compute the error caused by 280 thresholding a given pixel and propagate it to neighbour pixels to 281 compensate for the average intensity loss or gain. It is based upon the 282 assumption that a slightly out-of-place pixel causes little visual harm. 283 </p> 284 285 <h3> 3.1. Floyd-Steinberg error diffusion </h3> 286 287 <p> The most famous error diffusion method is the <b>Floyd-Steinberg</b> 288 algorithm. It handles each pixel of the image one after the other and 289 propagates the error to adjacent pixels: </p> 290 291 <p style="text-align: center;"> 292 <img src="fig3-1-1.png" width="120" height="120" alt="Floyd-Steinberg" /> 293 </p> 294 295 <p> The error is computed by simply substracting the source value and the 296 destination value. Destination value can be chosen by many means but does 297 not impact the image a lot compared to the error distribution coefficients 298 choice. The image on the left is the result using a 0.5 threshold. The image 299 on the right is a variant called <b>serpentine Floyd-Steinberg</b> that parses 300 every odd line in reverse order (right to left). The results are very close 301 to the original Floyd-Steinberg, but the method avoids artifacts in some 302 corner cases: </p> 303 304 <p style="text-align: center;"> 305 <img src="out3-1-1.png" width="256" height="256" 306 class="inline" alt="Floyd-Steinberg error diffusion" /> 307 <img src="grad3-1-1.png" width="32" height="256" 308 class="inline" alt="Floyd-Steinberg error diffusion gradient" /> 309 <img src="out3-1-2.png" width="256" height="256" 310 class="inline" alt="Floyd-Steinberg error diffusion" /> 311 <img src="grad3-1-2.png" width="32" height="256" 312 class="inline" alt="Floyd-Steinberg error diffusion gradient" /> 313 </p> 314 315 <h3> 3.2. Floyd-Steinberg derivatives </h3> 316 317 <p> <b>Fan dithering</b> is a slight modification of Floyd-Steinberg with a 318 very similar matrix: </p> 319 320 <p style="text-align: center;"> 321 <img src="fig3-2-1.png" width="160" height="120" 322 style="margin-right: 30px;" alt="Fan" /> 323 <img src="out3-2-1.png" width="256" height="256" 324 class="inline" alt="Fan error diffusion" /> 325 <img src="grad3-2-1.png" width="32" height="256" 326 class="inline" alt="Fan error diffusion gradient" /> 327 </p> 328 329 <p> <b>Jarvis, Judice and Ninke dithering</b> uses a much more complex 330 error diffusion matrix than Floyd-Steinberg: </p> 331 332 <p style="text-align: center;"> 333 <img src="fig3-2-2.png" width="200" height="160" 334 style="margin-right: 30px;" alt="Jarvis, Judice and Ninke" /> 335 <img src="out3-2-2.png" width="256" height="256" 336 class="inline" alt="Jarvis, Judice and Ninke error diffusion" /> 337 <img src="grad3-2-2.png" width="32" height="256" 338 class="inline" alt="Jarvis, Judice and Ninke error diffusion gradient" /> 339 </p> 340 341 <p> <b>Stucki dithering</b> is a slight variation of Jarvis-Judice-Ninke 342 dithering: </p> 343 344 <p style="text-align: center;"> 345 <img src="fig3-2-3.png" width="200" height="160" 346 style="margin-right: 30px;" alt="Stucki" /> 347 <img src="out3-2-3.png" width="256" height="256" 348 class="inline" alt="Stucki error diffusion" /> 349 <img src="grad3-2-3.png" width="32" height="256" 350 class="inline" alt="Stucki error diffusion gradient" /> 351 </p> 352 353 <p> <b>Burkes dithering</b> is yet another variation: </p> 354 355 <p style="text-align: center;"> 356 <img src="fig3-2-4.png" width="200" height="120" 357 style="margin-right: 30px;" alt="Burkes" /> 358 <img src="out3-2-4.png" width="256" height="256" 359 class="inline" alt="Burkes error diffusion" /> 360 <img src="grad3-2-4.png" width="32" height="256" 361 class="inline" alt="Burkes error diffusion gradient" /> 362 </p> 363 364 <p> Frankie Sierra came up with a few error diffusion matrices: <b>Sierra 365 dithering</b> is a variation of Jarvis that is slightly faster because it 366 propagates to fewer pixels, <b>Two-row Sierra</b> is a simplified version 367 thereof, and <b>Filter Lite</b> is one of the simplest Floyd-Steinberg 368 derivatives: </p> 369 370 <p style="text-align: center;"> 371 <img src="fig3-2-5.png" width="200" height="160" 372 style="margin-right: 30px;" alt="Sierra" /> 373 <img src="out3-2-5.png" width="256" height="256" 374 class="inline" alt="Sierra error diffusion" /> 375 <img src="grad3-2-5.png" width="32" height="256" 376 class="inline" alt="Sierra error diffusion gradient" /> 377 </p> 378 379 <p style="text-align: center;"> 380 <img src="fig3-2-6.png" width="200" height="120" 381 style="margin-right: 30px;" alt="Sierra" /> 382 <img src="out3-2-6.png" width="256" height="256" 383 class="inline" alt="Sierra error diffusion" /> 384 <img src="grad3-2-6.png" width="32" height="256" 385 class="inline" alt="Sierra error diffusion gradient" /> 386 </p> 387 388 <p style="text-align: center;"> 389 <img src="fig3-2-7.png" width="120" height="120" 390 style="margin-right: 30px;" alt="Sierra" /> 391 <img src="out3-2-7.png" width="256" height="256" 392 class="inline" alt="Sierra error diffusion" /> 393 <img src="grad3-2-7.png" width="32" height="256" 394 class="inline" alt="Sierra error diffusion gradient" /> 395 </p> 396 397 <p> <b>Atkinson dithering</b> only propagates 75% of the error, leading to a 398 loss of contrast around black and white areas, but better contrast in the 399 midtones: </p> 400 401 <p style="text-align: center;"> 402 <img src="fig3-2-8.png" width="160" height="160" 403 style="margin-right: 30px;" alt="Atkinson" /> 404 <img src="out3-2-8.png" width="256" height="256" 405 class="inline" alt="Atkinson error diffusion" /> 406 <img src="grad3-2-8.png" width="32" height="256" 407 class="inline" alt="Atkinson error diffusion gradient" /> 408 </p> 409 410 <!-- XXX: Stevenson-Arce is for hexagonal cells! 411 <p> <b>Stevenson-Arce dithering</b>: </p> 412 413 <p style="text-align: center;"> 414 <img src="fig3-2-9.png" width="280" height="200" 415 style="margin-right: 30px;" alt="Stevenson-Arce" /> 416 <img src="out3-2-9.png" width="256" height="256" 417 class="inline" alt="Stevenson-Arce error diffusion" /> 418 <img src="grad3-2-9.png" width="32" height="256" 419 class="inline" alt="Stevenson-Arce error diffusion gradient" /> 420 </p> 421 --> 422 423 <!-- 424 <p> There are countless other error diffusion techniques. However it appears 425 quite clearly that the overall quality of these algorithms has reached so high 426 a point that 427 quite obvious that quality will hardly improve 428 whatever blablah 429 --> 430 431 <h2> 4. Grayscale dithering </h2> 432 433 <p> Generalising dithering to more than two colours is straightforward in the 434 grayscale palette. Here are the results with 4×4 Bayer ordered dithering and 435 with Floyd-Steinberg error diffusion: </p> 436 437 <p style="text-align: center;"> 438 <img src="out4-0-1.png" width="256" height="256" 439 class="inline" alt="4×4 Bayer ordered dithering, 3 colours" /> 440 <img src="grad4-0-1.png" width="32" height="256" 441 class="inline" alt="4×4 Bayer ordered dithering gradient, 3 colours" /> 442 <img src="out4-0-2.png" width="256" height="256" 443 class="inline" alt="Floyd-Steinberg error diffusion, 3 colours" /> 444 <img src="grad4-0-2.png" width="32" height="256" 445 class="inline" alt="Floyd-Steinberg error diffusion gradient, 3 colours" /> 446 </p> 447 448 <p> Unfortunately the result is not as good as expected. The white pattern 449 on Lenna’s cheeks is visually disturbing, and the whole image looks darker 450 than with pure black-and-white dithering. But then, the previous dithering 451 results looked a lot brighter than the original image. This is due to the 452 output media’s <b>gamma</b>. </p> 453 454 <h3> 4.1. Introducing gamma </h3> 455 456 <p> If you are reading this document on a computer screen, you may have 457 noticed that the black and white 50% pattern was closer to a 0.73 grayscale 458 (left) than to the intuitively expected 0.5 value (right). If you are reading 459 a printed copy, it might be a different matter. </p> 460 461 <p style="text-align: center;"> 462 <img src="pat4-1-1.png" width="240" height="80" 463 class="inline" alt="introducing gamma" /> 464 </p> 465 466 <p> The mapping linking grayscale steps to intensities is called <b>gamma 467 correction</b>. An approximate law for gamma correction is given as 468 <i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour 469 value (between 0 and 1), <i>I</i> is the perceived colour intensity (between 470 0 and 1) and <i>γ</i> is the gamma. Most modern computer systems use the 471 sRGB gamma model close to the law with <i>γ = 2.2</i>. As can be seen, it is 472 highly non-linear: </p> 473 474 <p style="text-align: center;"> 475 <img src="fig4-1-1.png" width="300" height="240" alt="introducing gamma" /> 476 </p> 477 478 <p> Éric Brasseur wrote <a href="http://www.4p8.com/eric.brasseur/gamma.html">a 479 pretty comprehensive essay</a> about why on a computer screen a 50% black and 480 white pattern should be scaled down to a gray value of 0.73 instead of 0.5 and 481 how major computer graphics software totally misses the point. </p> 482 483 <p> Conversely, it clearly means that a gray value of 0.5 should not be 484 emulated with a 50% dither pattern. </p> 485 486 <!-- 487 <p> So, instead of using 25%, 50% and 75% patterns (which give non-uniform 488 gray values of 0.53, 0.73 and 0.88), one should rather use 6.25%, 25% and 50% 489 patterns, which give the better spread gray values of 0.28, 0.53 and 0.73 490 and result in far more accurate gradients. This is especially obvious when 491 observing the high intensity drop between the 25% pattern and black (top row): 492 </p> 493 494 <p style="text-align: center;"> 495 <img src="pat005.png" width="400" height="240" 496 class="inline" alt="better gradients" /> 497 </p> 498 499 <p> Here is the result on Lenna. As you can see, the result is visually less 500 appealing than with the “incorrect” colours. But when seen from a distance, 501 there is no doubt this version is more accurate: </p> 502 503 <p style="text-align: center;"> 504 <img src="out007.png" width="256" height="256" 505 class="inline" alt="gamma-aware 3-pattern halftoning" /> 506 <img src="grad007.png" width="32" height="256" 507 class="inline" alt="gamma-aware 3-pattern halftoning gradient" /> 508 </p> 509 --> 510 511 <!-- 512 <h3> Gamma with more gray levels </h3> 513 514 <p> As seen above, the smoothest dithering pattern that can be created with 515 black and white is by uniformly alterning the two colours. However, the 516 resulting colour (0.73) it is not evenly situated on the gray scale. </p> 517 518 <img src="out008.png" width="256" height="256" 519 class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" /> 520 521 <p> Here is the application to Lenna, using the 0-0.2, 0.2-0.4, 0.4-0.6, 522 0.6-0.8 and 0.8-1 ranges for black, white and the three patterns: </p> 523 524 <p style="text-align: center;"> 525 <img src="out005.png" width="256" height="256" 526 class="inline" alt="20/40/60/80% threshold and 25/50/75% halftones" /> 527 </p> 528 --> 79 <!--<div style="float: left;"> 80 <a href=""></a> 81 </div>--> 82 <div style="float: right;"> 83 <a href="part1.html">>>> 1. Colour quantisation</a> 84 </div> 529 85 530 86 <?php $rev = '$Id$';
Note: See TracChangeset
for help on using the changeset viewer.