| | 1 | = 6. Colour dithering = |
| | 2 | |
| | 3 | Dithering 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 | |
| | 7 | In 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 | |
| | 11 | It 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 | |
| | 17 | One 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 | |
| | 19 | Separate-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 | |
| | 23 | Here 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 | |
| | 32 | The previous palette was suitable for separate-space dithering. Such a palette is called '''separable''' or '''orthogonal'''. |
| | 33 | |
| | 34 | Here 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 | |
| | 38 | As 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 | |
| | 44 | It 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 | |
| | 46 | The 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 | |
| | 53 | Distances 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 | |
| | 62 | The 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 | |
| | 69 | All 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 | |
| | 73 | Shaked, 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 | |
| | 77 | Adapting 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 | |
| | 79 | The 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 | |
| | 86 | Speed 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. |
