| | 1 | = 2. Halftoning = |
| | 2 | |
| | 3 | == 2.1. Halftoning patterns == |
| | 4 | |
| | 5 | Observe the following patterns. From a certain distance or assuming small enough pixels, they look like shades of grey despite being made of only black and white pixels: |
| | 6 | |
| | 7 | [[Image(source:/web/trunk/static/study/out/pat2-1-1.png,alt="50% pattern")]] |
| | 8 | |
| | 9 | We can do even better using additional patterns such as these 25% and 75% halftone patterns: |
| | 10 | |
| | 11 | [[Image(source:/web/trunk/static/study/out/pat2-1-2.png,alt="25% and 75% patterns")]] |
| | 12 | |
| | 13 | This looks promising. Let’s try immediately on Lena: we will use the 5-colour thresholding picture and replace the 0.25, 0.5 and 0.75 grey values with the above patterns: |
| | 14 | |
| | 15 | [[Image(source:/web/trunk/static/study/out/lena2-1-1.png,alt="25%, 50% and 75% halftoning")]] |
| | 16 | [[Image(source:/web/trunk/static/study/out/grad2-1-1.png,alt="25%, 50% and 75% halftoning gradient")]] |
| | 17 | |
| | 18 | Not bad for a start. But there is a lot to improve. By the way, this technique is covered by Apple’s [http://www.freepatentsonline.com/5761347.html U.S. patent 5761347] ![15]. |
| | 19 | |
| | 20 | == 2.2. Screen artifacts == |
| | 21 | |
| | 22 | If your screen’s quality is not very good, you might experience slightly different shades of grey for the following patterns, despite being made of 50% black and 50% white pixels: |
| | 23 | |
| | 24 | [[Image(source:/web/trunk/static/study/out/pat2-2-1.png,alt="screen imperfections")]] |
| | 25 | |
| | 26 | Obviously the middle pattern looks far better to the human eye on a computer screen. Optimising patterns so that they look good to the human eye and don't create artifacts is a crucial element of a dithering algorithm. Here is another example of two patterns that approximate to the same shade of grey but may look slightly different from a distance: |
| | 27 | |
| | 28 | [[Image(source:/web/trunk/static/study/out/pat2-2-2.png,alt="two different 25% patterns")]] |
| | 29 | |
| | 30 | == 2.3. Ordered dithering == |
| | 31 | |
| | 32 | A generalisation of the dithering technique we just saw that uses a certain family of patterns is called '''ordered dithering'''. It is based on a '''dither matrix''' such as the following one: |
| | 33 | |
| | 34 | [[Image(source:/web/trunk/static/study/fig2-3-1.png |
| | 35 | |
| | 36 | Using the matrix coefficients as threshold values yield the following results for black, white and three shades of grey (0.25, 0.5 and 0.75): |
| | 37 | |
| | 38 | [[Image(source:/web/trunk/static/study/fig2-3-5.png alt="results of 2×2 dither matrix")]] |
| | 39 | |
| | 40 | The dither matrix is therefore repeated all over the image. The first pixel |
| | 41 | will be thresholded with a value of 0.2, the second pixel with a value of 0.8, |
| | 42 | then the third pixel with a value of 0.2 again, and so on, resulting in an image |
| | 43 | very similar to the one previously seen in 2.1: |
| | 44 | |
| | 45 | [[Image(source:/web/trunk/static/study/fig2-3-1b.png,alt="tiled dither matrix")]] |
| | 46 | [[Image(source:/web/trunk/static/study/out/lena2-3-0.png,alt="2×2 Bayer dithering")]] |
| | 47 | [[Image(source:/web/trunk/static/study/out/grad2-3-0.png,alt="2×2 Bayer dithering gradient")]] |
| | 48 | |
| | 49 | For better readability, the matrix is rewritten as following. The dither coefficients are trivially computed from the matrix cells and the matrix size: |
| | 50 | |
| | 51 | [[Image(source:/web/trunk/static/study/fig2-3-1c.png alt="normalised 2×2 dither matrix")]] |
| | 52 | |
| | 53 | Different matrices can give very different results. This is a 4×4 '''Bayer ordered dither matrix''' ![17], recursively created from the previous 2×2 dither matrix: |
| | 54 | |
| | 55 | [[Image(source:/web/trunk/static/study/out/fig2-3-2.png,alt="4×4 Bayer matrix")]] |
| | 56 | [[Image(source:/web/trunk/static/study/out/lena2-3-1.png,alt="4×4 Bayer dithering")]] |
| | 57 | [[Image(source:/web/trunk/static/study/out/grad2-3-1.png,alt="4×4 Bayer dithering gradient")]] |
| | 58 | |
| | 59 | This is an 8×8 Bayer matrix, recursively created from the 4×4 version: |
| | 60 | |
| | 61 | [[Image(source:/web/trunk/static/study/out/fig2-3-2b.png,alt="4×4 Bayer matrix")]] |
| | 62 | [[Image(source:/web/trunk/static/study/out/lena2-3-1b.png,alt="4×4 Bayer dithering")]] |
| | 63 | [[Image(source:/web/trunk/static/study/out/grad2-3-1b.png,alt="4×4 Bayer dithering gradient")]] |
| | 64 | |
| | 65 | This 4×4 '''cluster dot matrix''' creates dot patterns: |
| | 66 | |
| | 67 | [[Image(source:/web/trunk/static/study/out/fig2-3-3.png,alt="4×4 cluster dot matrix")]] |
| | 68 | [[Image(source:/web/trunk/static/study/out/lena2-3-2.png,alt="4×4 cluster dot dithering")]] |
| | 69 | [[Image(source:/web/trunk/static/study/out/grad2-3-2.png,alt="4×4 cluster dot dithering gradient")]] |
| | 70 | |
| | 71 | This 8×8 cluster dot matrix mimics the halftoning techniques used by newspapers: |
| | 72 | |
| | 73 | [[Image(source:/web/trunk/static/study/out/fig2-3-3b.png,alt="4×4 cluster dot matrix")]] |
| | 74 | [[Image(source:/web/trunk/static/study/out/lena2-3-2b.png,alt="4×4 cluster dot dithering")]] |
| | 75 | [[Image(source:/web/trunk/static/study/out/grad2-3-2b.png,alt="4×4 cluster dot dithering gradient")]] |
| | 76 | |
| | 77 | This unusual 5×3 matrix creates artistic vertical line artifacts: |
| | 78 | |
| | 79 | [[Image(source:/web/trunk/static/study/out/fig2-3-4.png,alt="4×4 cluster dot matrix")]] |
| | 80 | [[Image(source:/web/trunk/static/study/out/lena2-3-3.png,alt="4×4 cluster dot dithering")]] |
| | 81 | [[Image(source:/web/trunk/static/study/out/grad2-3-3.png,alt="4×4 cluster dot dithering gradient")]] |
| | 82 | |
| | 83 | There are two major issues with ordered dithering. First, important '''visual artifacts''' may appear. Even Bayer ordered dithering causes weird cross-hatch pattern artifacts on some images. Second, dithering matrices do not depend on the original image and thus '''do not take input data into account''': high frequency features in the image are often missed and, in some cases, cause even worse artifacts. |
| | 84 | |
| | 85 | == 2.4. Random ordered dithering == |
| | 86 | |
| | 87 | Random dithering can help reduce the major problem caused by halftoning, which is the apparition of pattern artifacts. The method is as simple as '''slightly perturbating dither matrix coefficients''' (or pixel values) during the halftoning step. The difficult part is picking up an adequate perturbation function: too much perturbation and the result is unrecognisable, too little and the artifacts stay. |
| | 88 | |
| | 89 | For instance, this is the result of 8×8 Bayer dithering perturbated by a gaussian distribution (mean 0.0, standard deviation 0.08): |
| | 90 | |
| | 91 | [[Image(source:/web/trunk/static/study/out/lena2-4-1.png,alt="4×4 Bayer dithering, gaussian perturbation")]] |
| | 92 | [[Image(source:/web/trunk/static/study/out/grad2-4-1.png,alt="4×4 Bayer dithering, gaussian perturbation gradient")]] |
| | 93 | |
| | 94 | Another way to use random number generators to avoid pattern artifacts is '''random dither matrix selection''' ![22]. The image space is no longer tiled with the same matrix over and over again, but with a random selection from a list of similar dither matrices. |
| | 95 | |
| | 96 | This example shows random matrix selection from a list of six 3×3 dither matrices: |
| | 97 | |
| | 98 | [[Image(source:/web/trunk/static/study/fig2-4-1.png,alt="four 3×3 dispersed dot matrices")]] |
| | 99 | [[Image(source:/web/trunk/static/study/out/lena2-4-2.png,alt="random Bayer matrix dithering")]] |
| | 100 | [[Image(source:/web/trunk/static/study/out/grad2-4-2.png,alt="random Bayer matrix dithering gradient")]] |
| | 101 | |
| | 102 | == 2.5. Non-rectangular dither tiles == |
| | 103 | |
| | 104 | Another way to avoid disturbing pattern artifacts is to use non-rectangular dither tiles. Here are several examples, the first one generating slanted square patterns, the second one hexagonal patterns, then slanted square patterns again with a slightly different angle, and hexagonal patterns again. The artifacts usually seen in Bayer dithering do not appear here: |
| | 105 | |
| | 106 | [[Image(source:/web/trunk/static/study/fig2-5-1.png,alt="cross dither tile")]] |
| | 107 | [[Image(source:/web/trunk/static/study/out/lena2-5-1.png,alt="cross dithering")]] |
| | 108 | [[Image(source:/web/trunk/static/study/out/grad2-5-1.png,alt="cross dithering gradient")]] |
| | 109 | |
| | 110 | [[Image(source:/web/trunk/static/study/fig2-5-2.png,alt="hex dither tile")]] |
| | 111 | [[Image(source:/web/trunk/static/study/out/lena2-5-2.png,alt="hex dithering")]] |
| | 112 | [[Image(source:/web/trunk/static/study/out/grad2-5-2.png,alt="hex dithering gradient")]] |
| | 113 | |
| | 114 | [[Image(source:/web/trunk/static/study/fig2-5-3.png,alt="square dither tile")]] |
| | 115 | [[Image(source:/web/trunk/static/study/out/lena2-5-3.png,alt="square dithering")]] |
| | 116 | [[Image(source:/web/trunk/static/study/out/grad2-5-3.png,alt="square dithering gradient")]] |
| | 117 | |
| | 118 | [[Image(source:/web/trunk/static/study/fig2-5-4.png,alt="hex2 dither tile")]] |
| | 119 | [[Image(source:/web/trunk/static/study/out/lena2-5-4.png,alt="hex2 dithering")]] |
| | 120 | [[Image(source:/web/trunk/static/study/out/grad2-5-4.png,alt="hex2 dithering gradient")]] |
| | 121 | |
| | 122 | == 2.6. Supercell dithering == |
| | 123 | |
| | 124 | Supercell dithering consists in creating bigger dithering tiles (supercells) from base tiles. One example is Victor Ostromoukhov’s '''CombiScreen''' method ![3]. |
| | 125 | |
| | 126 | Just like Bayer matrices, non-rectangular tiles can be used to recursively create bigger patterns, giving finer results. The amount of shades of grey that can be rendered using a given tile is the number of cells in the tile plus one. Here are a few examples using tiles seen previously: |
| | 127 | |
| | 128 | [[Image(source:/web/trunk/static/study/fig2-6-1.png,alt="4-wise cross dither tile")]] |
| | 129 | [[Image(source:/web/trunk/static/study/out/lena2-6-1.png,alt="4-wise cross dithering")]] |
| | 130 | [[Image(source:/web/trunk/static/study/out/grad2-6-1.png,alt="4-wise cross dithering gradient")]] |
| | 131 | |
| | 132 | [[Image(source:/web/trunk/static/study/fig2-6-2.png,alt="3-wise hex dither tile")]] |
| | 133 | [[Image(source:/web/trunk/static/study/out/lena2-6-2.png,alt="3-wise hex dithering")]] |
| | 134 | [[Image(source:/web/trunk/static/study/out/grad2-6-2.png,alt="3-wise hex dithering gradient")]] |
| | 135 | |
| | 136 | [[Image(source:/web/trunk/static/study/fig2-6-3.png,alt="4-wise square dither tile")]] |
| | 137 | [[Image(source:/web/trunk/static/study/out/lena2-6-3.png,alt="4-wise square dithering")]] |
| | 138 | [[Image(source:/web/trunk/static/study/out/grad2-6-3.png,alt="4-wise square dithering gradient")]] |
| | 139 | |
| | 140 | This example shows a tile resembling a Davis-Knuth dragon curve. Though the tile itself is beautiful, it is in reality only a reorganisation of an 8×8 Bayer dither matrix. Therefore the resulting image is exactly the same as for classical Bayer dithering: |
| | 141 | |
| | 142 | [[Image(source:/web/trunk/static/study/out/fig2-6-4.png,alt="twin dragon dither tile")]] |
| | 143 | [[Image(source:/web/trunk/static/study/out/lena2-6-4.png,alt="twin dragon dithering")]] |
| | 144 | [[Image(source:/web/trunk/static/study/out/grad2-6-4.png,alt="twin dragon dithering gradient")]] |
| | 145 | |
| | 146 | Here are two consecutive iterations of the hexagonal tiling shown above. Since the area of the original tile is 10 cells, the first iteration could display 11 different shades of grey. These iterations can display respectively 31 and 91 shades: |
| | 147 | |
| | 148 | [[Image(source:/web/trunk/static/study/fig2-6-5.png,alt="3-way hex2 dither tile")]] |
| | 149 | [[Image(source:/web/trunk/static/study/out/lena2-6-5.png,alt="3-way hex2 dithering")]] |
| | 150 | [[Image(source:/web/trunk/static/study/out/grad2-6-5.png,alt="3-way hex2 dithering gradient")]] |
| | 151 | |
| | 152 | [[Image(source:/web/trunk/static/study/fig2-6-6.png,alt="9-way hex2 dither tile")]] |
| | 153 | [[Image(source:/web/trunk/static/study/out/lena2-6-6.png,alt="9-way hex2 dithering")]] |
| | 154 | [[Image(source:/web/trunk/static/study/out/grad2-6-6.png,alt="9-way hex2 dithering gradient")]] |
| | 155 | |
| | 156 | == 2.7. Void and cluster method == |
| | 157 | |
| | 158 | Robert A. Ulichney’s '''void and cluster method''' ![18] is a very generic method for dither array generation. It mainly targets huge matrices in order to reduce artifacts caused by tiling. |
| | 159 | |
| | 160 | The process goes through many steps. First, a working pattern matrix needs to be created: |
| | 161 | |
| | 162 | * Generate an empty ''w×h'' matrix full of 0s |
| | 163 | * Set ''n'' cells to 1 |
| | 164 | * The working matrix is uniformly distributed: |
| | 165 | * Find the 1 with the most neighbours set to 1 and set that cell to 0 |
| | 166 | * Find the 0 with the fewest neighbours set to 1 and set that cell to 1 |
| | 167 | * Repeat until the 1 was just put back where it originally was |
| | 168 | |
| | 169 | Usually ''n'' is about 10% of ''w×h''. It can be generated randomly, loaded from a known pattern, or created using a more powerful algorithm (chapter 3 will introduce error diffusion algorithms that may be used to generate the working pattern matrix). |
| | 170 | |
| | 171 | The dither matrix is then generated from the working pattern in three steps: |
| | 172 | |
| | 173 | * Dither indices 0 to ''n - 1'' are set using a first copy of the working matrix |
| | 174 | * ''n = n - 1'' |
| | 175 | * Find the 1 with the most neighbours set to 1 and set that cell to 0 |
| | 176 | * In the dither matrix, set the corresponding cell to ''n'' |
| | 177 | * Repeat until ''n = 0'' |
| | 178 | * Dither indices ''n'' to ''w×h/2'' are set using a second copy of the working matrix |
| | 179 | * Find the 0 with the fewest neighbours set to 1 and set that cell to 1 |
| | 180 | * In the dither matrix, set the corresponding cell to ''n'' |
| | 181 | * ''n = n + 1'' |
| | 182 | * Repeat until ''n ≥ w×h/2'' |
| | 183 | * Dither indices ''w×h/2'' to ''w×h'' are set using the same copy of the working matrix |
| | 184 | * Find the 0 with the fewest neighbours set to 1 and set that cell to 1 |
| | 185 | * In the dither matrix, set the corresponding cell to ''n'' |
| | 186 | * ''n = n + 1'' |
| | 187 | * Repeat until ''n = w×h'' |
| | 188 | |
| | 189 | The key part of the algorithm is the choice of the void finder and the cluster finder for each step. Best results are achieved using '''Voronoï tesselation''' ![19] ![22], but simpler methods such as '''gaussian convolution''' ![21] give decent results, too. |
| | 190 | |
| | 191 | The following two matrices show the results of the algorithm using randomly generated initial matrices of size respectively 14×14 and 25×25. The void and cluster finder uses a simple 7×7 gaussian convolution filter. Gray cells show the initial uniformly distributed matrix: |
| | 192 | |
| | 193 | [[Image(source:/web/trunk/static/study/out/fig2-7-1.png,alt="14×14 void-and-cluster matrix")]] |
| | 194 | |
| | 195 | [[Image(source:/web/trunk/static/study/out/fig2-7-2.png,alt="25×25 void-and-cluster matrix")]] |
| | 196 | |
| | 197 | Dither matrices generated with the void and cluster method give impressive results. They are pretty close to the best quality that can be achieved using standard ordered dithering: |
| | 198 | |
| | 199 | [[Image(source:/web/trunk/static/study/out/lena2-7-1.png,alt="14×14 void and cluster dithering")]] |
| | 200 | [[Image(source:/web/trunk/static/study/out/grad2-7-1.png,alt="14×14 void and cluster dithering gradient")]] |
| | 201 | [[Image(source:/web/trunk/static/study/out/lena2-7-2.png,alt="25×25 void and cluster dithering")]] |
| | 202 | [[Image(source:/web/trunk/static/study/out/grad2-7-2.png,alt="25×25 void and cluster dithering gradient")]] |
| | 203 | |
| | 204 | This technique is covered by Ulichney’s [http://www.freepatentsonline.com/5535020.html U.S. patent 5535020] and the specific implementation we showed is partly covered by Epson’s [http://www.freepatentsonline.com/6088512.html U.S. patent 6088512]. |
