Changes between Initial Version and Version 1 of libcaca/study/6


Ignore:
Timestamp:
08/08/2009 03:09:08 PM (15 years ago)
Author:
Sam Hocevar
Comment:

chapter 6

Legend:

Unmodified
Added
Removed
Modified
  • libcaca/study/6

    v1 v1  
     1= 6. Colour dithering =
     2
     3Dithering colour images means dithering three-dimensional elements (RGB pixels) instead of one-dimensional grey values. It is very complex and depends on the output media even more than greyscale dithering.
     4
     5== 6.1. Separate-space dithering ==
     6
     7In some cases it is possible to perform three one-dimensional dithering operations instead of one three-dimensional one. Consider for instance the following palette:
     8
     9[[Image(source:/web/trunk/static/study/out/pat6-1-1.png,class="inline",alt="8-colour RGB palette")]]
     10
     11It is made of the eight possible red/green/blue combinations made of 0 and 1 values:
     12
     13|| '''Red'''   || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 ||
     14|| '''Green''' || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 ||
     15|| '''Blue'''  || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 ||
     16
     17One way of dithering an image using this palette is to convert the image into three greyscale images (separating the red, green and blue channels), dither each subimage to two colours separately and recombine the images into three channels. For instance, if at a given pixel the red channel is dithered to 1 and the green and blue channels are dithered to 0, the final pixel will be [1  0  0] which is the colour red.
     18
     19Separate-space dithering works by splitting the image into three red, green and blue channels. Each of this channel is treated as a greyscale image that is then dithered to black and white using any dithering method seen previously. The resulting images are then treated again as three red, green and blue channels and recombined into the final image:
     20
     21[[Image(source:/web/trunk/static/study/fig6-1-7.png,class="matrix",alt="separate-space dithering")]]
     22
     23Here are the results with serpentine Floyd-Steinberg dithering applied to each channel. On the left, no colour correction, as The Gimp or Photoshop would do; on the right, gamma-corrected dithering:
     24
     25[[Image(source:/web/trunk/static/study/out/lena6-1-1.png,class="inline",alt="serpentine FS, 8 colours")]]
     26[[Image(source:/web/trunk/static/study/out/grad6-1-1.png,class="inline",alt="serpentine FS, 8 colours gradient")]]
     27[[Image(source:/web/trunk/static/study/out/lena6-1-2.png,class="inline",alt="serpentine FS, 8 colours, gamma-corrected")]]
     28[[Image(source:/web/trunk/static/study/out/grad6-1-2.png,class="inline",alt="serpentine FS, 8 colours, gamma-corrected gradient")]]
     29
     30== 6.2. Accounting for other dimensions ==
     31
     32The previous palette was suitable for separate-space dithering. Such a palette is called '''separable''' or '''orthogonal'''.
     33
     34Here is a palette that cannot be used in the same way:
     35
     36[[Image(source:/web/trunk/static/study/out/pat6-2-2.png,class="inline",alt="8-colour RGB palette")]]
     37
     38As can be seen, it does not have the [0.5 0.5 0.5] grey colour, or the [1 0.5 0] orange colour, for instance, despite having other combinations of 0, 0.5 and 1 values:
     39
     40|| '''Red'''   || 0 || 0 || 0.5 || 0.5 || 0 || 0 || 0.5 || 0.7 || 0.3 || 0 || 1 || 1 || 0 || 0 || 1 || 1 ||
     41|| '''Green''' || 0 || 0 || 0 || 0 || 0.5 || 0.5 || 0.5 || 0.7 || 0.3 || 0 || 0 || 0 || 1 || 1 || 1 || 1 ||
     42|| '''Blue'''  || 0 || 0.5 || 0 || 0.5 || 0 || 0.5 || 0 || 0.7 || 0.3 || 1 || 0 || 1 || 0 || 1 || 0 || 1 ||
     43
     44It is no longer possible to compute the closest colour in each colourspace and combine them into an RGB colour, since that colour might not be available in the palette. So we need to determine what the “closest colour” means when dealing with the whole colour spectrum.
     45
     46The following examples show gamma-corrected Floyd-Steinberg using the above 16-colour palette and two different definitions of distance: the '''sum of absolute differences''' and the '''euclidian distance'''. The sum of absolute differences performs pretty poorly because it does not penalise wide disparities:
     47
     48[[Image(source:/web/trunk/static/study/out/lena6-2-1.png,class="inline",alt="Floyd-Steinberg, sum of absolute differences")]]
     49[[Image(source:/web/trunk/static/study/out/grad6-2-1.png,class="inline",alt="Floyd-Steinberg, sum of absolute differences gradient")]]
     50[[Image(source:/web/trunk/static/study/out/lena6-2-2.png,class="inline",alt="Floyd-Steinberg, euclidian distance")]]
     51[[Image(source:/web/trunk/static/study/out/grad6-2-2.png,class="inline",alt="Floyd-Steinberg, euclidian distance gradient")]]
     52
     53Distances can be computed in another space. For instance, the '''HSV space''' allows to give colour variations a smaller influence than brightness variations simply by changing the HSV cone’s height. On the left is spatial Floyd-Steinberg using the euclidian distance in an HSV cone of height 1 and base radius 1. On the right is the same distance within a cone of height 3 and base radius 1:
     54
     55[[Image(source:/web/trunk/static/study/out/lena6-2-3.png,class="inline",alt="Floyd-Steinberg, 1×1 HSV cone")]]
     56[[Image(source:/web/trunk/static/study/out/grad6-2-3.png,class="inline",alt="Floyd-Steinberg, 1×1 HSV cone gradient")]]
     57[[Image(source:/web/trunk/static/study/out/lena6-2-4.png,class="inline",alt="Floyd-Steinberg, 3×1 HSV cone")]]
     58[[Image(source:/web/trunk/static/study/out/grad6-2-4.png,class="inline",alt="Floyd-Steinberg, 3×1 HSV cone gradient")]]
     59
     60== 6.3. Reducing visual artifacts ==
     61
     62The following patterns show four ways to dither the same colour using our 8-colour palette:
     63
     64 * 1/2 black, 3/8 blue, 1/8 white
     65 * 1/2 blue, 3/8 black, 1/8 yellow
     66 * 3/8 black, 3/8 blue, 1/8 red, 1/8 cyan
     67 * 1/2 blue, 1/4 black, 1/8 red, 1/8 green
     68
     69All patterns visually blend to the same shade, but the last one is the most visually appealing:
     70
     71[[Image(source:/web/trunk/static/study/out/pat6-2-1.png,class="inline",alt="3 ways to dither the same colour")]]
     72
     73Shaked, Arad, Fitzhugh and Sobel introduce the '''minimum brightness variation criterion''' (MBVC), stating that in order to reduce halftone noise, the halftone set which should be used to render the desired colour should be the one whose brightness variation is minimal ![25]. Similarly, Klassen ''et al.'' suggest the selection of low-contrast colour combiation wherever possible ![24].
     74
     75== 6.4. Colour sub-block error diffusion ==
     76
     77Adapting sub-block error diffusion to colour images is almost straightforward. The major problem is proper weighting in the block-choosing step. It is a crucial part of the algorithm, and we have yet to find an efficient method to perform it.
     78
     79The images below shows the result using our now well-known “lines” tile list, using respectively the 8-colour palette and the 16-colour palette:
     80
     81[[Image(source:/web/trunk/static/study/out/lena6-4-1.png,class="inline",alt="8-colour sub-block error diffusion")]]
     82[[Image(source:/web/trunk/static/study/out/grad6-4-1.png,class="inline",alt="8-colour sub-block error diffusion gradient")]]
     83[[Image(source:/web/trunk/static/study/out/lena6-4-2.png,class="inline",alt="16-colour sub-block error diffusion")]]
     84[[Image(source:/web/trunk/static/study/out/grad6-4-2.png,class="inline",alt="16-colour sub-block error diffusion gradient")]]
     85
     86Speed is starting to become a problematic issue. A 16-colour palette can generate 65,536 unique 2×2 blocks. Exhaustive search to determine the best tile is no longer realistic, and we need to find better ways to find the best matching block.