Changes between Version 2 and Version 3 of libcaca/study/2


Ignore:
Timestamp:
12/22/2009 09:12:33 PM (15 years ago)
Author:
Sam Hocevar
Comment:

fix image links

Legend:

Unmodified
Added
Removed
Modified

  • libcaca/study/2

    v2 v3  
    55Observe 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:
    66
    7 [[Image(source:/web/trunk/static/study/out/pat2-1-1.png,class="inline",alt="50% pattern")]]
     7[[Image(source:/web/trunk/www/study/out/pat2-1-1.png,class="inline",alt="50% pattern")]]
    88
    99We can do even better using additional patterns such as these 25% and 75% halftone patterns:
    1010
    11 [[Image(source:/web/trunk/static/study/out/pat2-1-2.png,class="inline",alt="25% and 75% patterns")]]
     11[[Image(source:/web/trunk/www/study/out/pat2-1-2.png,class="inline",alt="25% and 75% patterns")]]
    1212
    1313This 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:
    1414
    15 [[Image(source:/web/trunk/static/study/out/lena2-1-1.png,class="inline",alt="25%, 50% and 75% halftoning")]]
    16 [[Image(source:/web/trunk/static/study/out/grad2-1-1.png,class="inline",alt="25%, 50% and 75% halftoning gradient")]]
     15[[Image(source:/web/trunk/www/study/out/lena2-1-1.png,class="inline",alt="25%, 50% and 75% halftoning")]]
     16[[Image(source:/web/trunk/www/study/out/grad2-1-1.png,class="inline",alt="25%, 50% and 75% halftoning gradient")]]
    1717
    1818Not 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].
    … …  
    2222If 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:
    2323
    24 [[Image(source:/web/trunk/static/study/out/pat2-2-1.png,class="inline",alt="screen imperfections")]]
     24[[Image(source:/web/trunk/www/study/out/pat2-2-1.png,class="inline",alt="screen imperfections")]]
    2525
    2626Obviously 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:
    2727
    28 [[Image(source:/web/trunk/static/study/out/pat2-2-2.png,class="inline",alt="two different 25% patterns")]]
     28[[Image(source:/web/trunk/www/study/out/pat2-2-2.png,class="inline",alt="two different 25% patterns")]]
    2929
    3030== 2.3. Ordered dithering ==
    … …  
    3232A 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:
    3333
    34 [[Image(source:/web/trunk/static/study/fig2-3-1.png,class="matrix",alt="2×2 dither matrix")]]
     34[[Image(source:/web/trunk/www/study/fig2-3-1.png,class="matrix",alt="2×2 dither matrix")]]
    3535
    3636Using 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):
    3737
    38 [[Image(source:/web/trunk/static/study/fig2-3-5.png,class="matrix",alt="results of 2×2 dither matrix")]]
     38[[Image(source:/web/trunk/www/study/fig2-3-5.png,class="matrix",alt="results of 2×2 dither matrix")]]
    3939
    4040The dither matrix is therefore repeated all over the image. The first pixel
    … …  
    4343very similar to the one previously seen in 2.1:
    4444
    45 [[Image(source:/web/trunk/static/study/fig2-3-1b.png,class="matrix",alt="tiled dither matrix")]]
    46 [[Image(source:/web/trunk/static/study/out/lena2-3-0.png,class="inline",alt="2×2 Bayer dithering")]]
    47 [[Image(source:/web/trunk/static/study/out/grad2-3-0.png,class="inline",alt="2×2 Bayer dithering gradient")]]
     45[[Image(source:/web/trunk/www/study/fig2-3-1b.png,class="matrix",alt="tiled dither matrix")]]
     46[[Image(source:/web/trunk/www/study/out/lena2-3-0.png,class="inline",alt="2×2 Bayer dithering")]]
     47[[Image(source:/web/trunk/www/study/out/grad2-3-0.png,class="inline",alt="2×2 Bayer dithering gradient")]]
    4848
    4949For better readability, the matrix is rewritten as following. The dither coefficients are trivially computed from the matrix cells and the matrix size:
    5050
    51 [[Image(source:/web/trunk/static/study/fig2-3-1c.png,class="matrix",alt="normalised 2×2 dither matrix")]]
     51[[Image(source:/web/trunk/www/study/fig2-3-1c.png,class="matrix",alt="normalised 2×2 dither matrix")]]
    5252
    5353Different 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:
    5454
    55 [[Image(source:/web/trunk/static/study/out/fig2-3-2.png,class="matrix",alt="4×4 Bayer matrix")]]
    56 [[Image(source:/web/trunk/static/study/out/lena2-3-1.png,class="inline",alt="4×4 Bayer dithering")]]
    57 [[Image(source:/web/trunk/static/study/out/grad2-3-1.png,class="inline",alt="4×4 Bayer dithering gradient")]]
     55[[Image(source:/web/trunk/www/study/out/fig2-3-2.png,class="matrix",alt="4×4 Bayer matrix")]]
     56[[Image(source:/web/trunk/www/study/out/lena2-3-1.png,class="inline",alt="4×4 Bayer dithering")]]
     57[[Image(source:/web/trunk/www/study/out/grad2-3-1.png,class="inline",alt="4×4 Bayer dithering gradient")]]
    5858
    5959This is an 8×8 Bayer matrix, recursively created from the 4×4 version:
    6060
    61 [[Image(source:/web/trunk/static/study/out/fig2-3-2b.png,class="matrix",alt="4×4 Bayer matrix")]]
    62 [[Image(source:/web/trunk/static/study/out/lena2-3-1b.png,class="inline",alt="4×4 Bayer dithering")]]
    63 [[Image(source:/web/trunk/static/study/out/grad2-3-1b.png,class="inline",alt="4×4 Bayer dithering gradient")]]
     61[[Image(source:/web/trunk/www/study/out/fig2-3-2b.png,class="matrix",alt="4×4 Bayer matrix")]]
     62[[Image(source:/web/trunk/www/study/out/lena2-3-1b.png,class="inline",alt="4×4 Bayer dithering")]]
     63[[Image(source:/web/trunk/www/study/out/grad2-3-1b.png,class="inline",alt="4×4 Bayer dithering gradient")]]
    6464
    6565This 4×4 '''cluster dot matrix''' creates dot patterns:
    6666
    67 [[Image(source:/web/trunk/static/study/out/fig2-3-3.png,class="matrix",alt="4×4 cluster dot matrix")]]
    68 [[Image(source:/web/trunk/static/study/out/lena2-3-2.png,class="inline",alt="4×4 cluster dot dithering")]]
    69 [[Image(source:/web/trunk/static/study/out/grad2-3-2.png,class="inline",alt="4×4 cluster dot dithering gradient")]]
     67[[Image(source:/web/trunk/www/study/out/fig2-3-3.png,class="matrix",alt="4×4 cluster dot matrix")]]
     68[[Image(source:/web/trunk/www/study/out/lena2-3-2.png,class="inline",alt="4×4 cluster dot dithering")]]
     69[[Image(source:/web/trunk/www/study/out/grad2-3-2.png,class="inline",alt="4×4 cluster dot dithering gradient")]]
    7070
    7171This 8×8 cluster dot matrix mimics the halftoning techniques used by newspapers:
    7272
    73 [[Image(source:/web/trunk/static/study/out/fig2-3-3b.png,class="matrix",alt="4×4 cluster dot matrix")]]
    74 [[Image(source:/web/trunk/static/study/out/lena2-3-2b.png,class="inline",alt="4×4 cluster dot dithering")]]
    75 [[Image(source:/web/trunk/static/study/out/grad2-3-2b.png,class="inline",alt="4×4 cluster dot dithering gradient")]]
     73[[Image(source:/web/trunk/www/study/out/fig2-3-3b.png,class="matrix",alt="4×4 cluster dot matrix")]]
     74[[Image(source:/web/trunk/www/study/out/lena2-3-2b.png,class="inline",alt="4×4 cluster dot dithering")]]
     75[[Image(source:/web/trunk/www/study/out/grad2-3-2b.png,class="inline",alt="4×4 cluster dot dithering gradient")]]
    7676
    7777This unusual 5×3 matrix creates artistic vertical line artifacts:
    7878
    79 [[Image(source:/web/trunk/static/study/out/fig2-3-4.png,class="matrix",alt="4×4 cluster dot matrix")]]
    80 [[Image(source:/web/trunk/static/study/out/lena2-3-3.png,class="inline",alt="4×4 cluster dot dithering")]]
    81 [[Image(source:/web/trunk/static/study/out/grad2-3-3.png,class="inline",alt="4×4 cluster dot dithering gradient")]]
     79[[Image(source:/web/trunk/www/study/out/fig2-3-4.png,class="matrix",alt="4×4 cluster dot matrix")]]
     80[[Image(source:/web/trunk/www/study/out/lena2-3-3.png,class="inline",alt="4×4 cluster dot dithering")]]
     81[[Image(source:/web/trunk/www/study/out/grad2-3-3.png,class="inline",alt="4×4 cluster dot dithering gradient")]]
    8282
    8383There 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.
    … …  
    8989For instance, this is the result of 8×8 Bayer dithering perturbated by a gaussian distribution (mean 0.0, standard deviation 0.08):
    9090
    91 [[Image(source:/web/trunk/static/study/out/lena2-4-1.png,class="inline",alt="4×4 Bayer dithering, gaussian perturbation")]]
    92 [[Image(source:/web/trunk/static/study/out/grad2-4-1.png,class="inline",alt="4×4 Bayer dithering, gaussian perturbation gradient")]]
     91[[Image(source:/web/trunk/www/study/out/lena2-4-1.png,class="inline",alt="4×4 Bayer dithering, gaussian perturbation")]]
     92[[Image(source:/web/trunk/www/study/out/grad2-4-1.png,class="inline",alt="4×4 Bayer dithering, gaussian perturbation gradient")]]
    9393
    9494Another 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.
    … …  
    9696This example shows random matrix selection from a list of six 3×3 dither matrices:
    9797
    98 [[Image(source:/web/trunk/static/study/fig2-4-1.png,class="matrix",alt="four 3×3 dispersed dot matrices")]]
    99 [[Image(source:/web/trunk/static/study/out/lena2-4-2.png,class="inline",alt="random Bayer matrix dithering")]]
    100 [[Image(source:/web/trunk/static/study/out/grad2-4-2.png,class="inline",alt="random Bayer matrix dithering gradient")]]
     98[[Image(source:/web/trunk/www/study/fig2-4-1.png,class="matrix",alt="four 3×3 dispersed dot matrices")]]
     99[[Image(source:/web/trunk/www/study/out/lena2-4-2.png,class="inline",alt="random Bayer matrix dithering")]]
     100[[Image(source:/web/trunk/www/study/out/grad2-4-2.png,class="inline",alt="random Bayer matrix dithering gradient")]]
    101101
    102102== 2.5. Non-rectangular dither tiles ==
    … …  
    104104Another 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:
    105105
    106 [[Image(source:/web/trunk/static/study/fig2-5-1.png,class="matrix",alt="cross dither tile")]]
    107 [[Image(source:/web/trunk/static/study/out/lena2-5-1.png,class="inline",alt="cross dithering")]]
    108 [[Image(source:/web/trunk/static/study/out/grad2-5-1.png,class="inline",alt="cross dithering gradient")]]
    109 
    110 [[Image(source:/web/trunk/static/study/fig2-5-2.png,class="matrix",alt="hex dither tile")]]
    111 [[Image(source:/web/trunk/static/study/out/lena2-5-2.png,class="inline",alt="hex dithering")]]
    112 [[Image(source:/web/trunk/static/study/out/grad2-5-2.png,class="inline",alt="hex dithering gradient")]]
    113 
    114 [[Image(source:/web/trunk/static/study/fig2-5-3.png,class="matrix",alt="square dither tile")]]
    115 [[Image(source:/web/trunk/static/study/out/lena2-5-3.png,class="inline",alt="square dithering")]]
    116 [[Image(source:/web/trunk/static/study/out/grad2-5-3.png,class="inline",alt="square dithering gradient")]]
    117 
    118 [[Image(source:/web/trunk/static/study/fig2-5-4.png,class="matrix",alt="hex2 dither tile")]]
    119 [[Image(source:/web/trunk/static/study/out/lena2-5-4.png,class="inline",alt="hex2 dithering")]]
    120 [[Image(source:/web/trunk/static/study/out/grad2-5-4.png,class="inline",alt="hex2 dithering gradient")]]
     106[[Image(source:/web/trunk/www/study/fig2-5-1.png,class="matrix",alt="cross dither tile")]]
     107[[Image(source:/web/trunk/www/study/out/lena2-5-1.png,class="inline",alt="cross dithering")]]
     108[[Image(source:/web/trunk/www/study/out/grad2-5-1.png,class="inline",alt="cross dithering gradient")]]
     109
     110[[Image(source:/web/trunk/www/study/fig2-5-2.png,class="matrix",alt="hex dither tile")]]
     111[[Image(source:/web/trunk/www/study/out/lena2-5-2.png,class="inline",alt="hex dithering")]]
     112[[Image(source:/web/trunk/www/study/out/grad2-5-2.png,class="inline",alt="hex dithering gradient")]]
     113
     114[[Image(source:/web/trunk/www/study/fig2-5-3.png,class="matrix",alt="square dither tile")]]
     115[[Image(source:/web/trunk/www/study/out/lena2-5-3.png,class="inline",alt="square dithering")]]
     116[[Image(source:/web/trunk/www/study/out/grad2-5-3.png,class="inline",alt="square dithering gradient")]]
     117
     118[[Image(source:/web/trunk/www/study/fig2-5-4.png,class="matrix",alt="hex2 dither tile")]]
     119[[Image(source:/web/trunk/www/study/out/lena2-5-4.png,class="inline",alt="hex2 dithering")]]
     120[[Image(source:/web/trunk/www/study/out/grad2-5-4.png,class="inline",alt="hex2 dithering gradient")]]
    121121
    122122== 2.6. Supercell dithering ==
    … …  
    126126Just 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:
    127127
    128 [[Image(source:/web/trunk/static/study/fig2-6-1.png,class="matrix",alt="4-wise cross dither tile")]]
    129 [[Image(source:/web/trunk/static/study/out/lena2-6-1.png,class="inline",alt="4-wise cross dithering")]]
    130 [[Image(source:/web/trunk/static/study/out/grad2-6-1.png,class="inline",alt="4-wise cross dithering gradient")]]
    131 
    132 [[Image(source:/web/trunk/static/study/fig2-6-2.png,class="matrix",alt="3-wise hex dither tile")]]
    133 [[Image(source:/web/trunk/static/study/out/lena2-6-2.png,class="inline",alt="3-wise hex dithering")]]
    134 [[Image(source:/web/trunk/static/study/out/grad2-6-2.png,class="inline",alt="3-wise hex dithering gradient")]]
    135 
    136 [[Image(source:/web/trunk/static/study/fig2-6-3.png,class="matrix",alt="4-wise square dither tile")]]
    137 [[Image(source:/web/trunk/static/study/out/lena2-6-3.png,class="inline",alt="4-wise square dithering")]]
    138 [[Image(source:/web/trunk/static/study/out/grad2-6-3.png,class="inline",alt="4-wise square dithering gradient")]]
     128[[Image(source:/web/trunk/www/study/fig2-6-1.png,class="matrix",alt="4-wise cross dither tile")]]
     129[[Image(source:/web/trunk/www/study/out/lena2-6-1.png,class="inline",alt="4-wise cross dithering")]]
     130[[Image(source:/web/trunk/www/study/out/grad2-6-1.png,class="inline",alt="4-wise cross dithering gradient")]]
     131
     132[[Image(source:/web/trunk/www/study/fig2-6-2.png,class="matrix",alt="3-wise hex dither tile")]]
     133[[Image(source:/web/trunk/www/study/out/lena2-6-2.png,class="inline",alt="3-wise hex dithering")]]
     134[[Image(source:/web/trunk/www/study/out/grad2-6-2.png,class="inline",alt="3-wise hex dithering gradient")]]
     135
     136[[Image(source:/web/trunk/www/study/fig2-6-3.png,class="matrix",alt="4-wise square dither tile")]]
     137[[Image(source:/web/trunk/www/study/out/lena2-6-3.png,class="inline",alt="4-wise square dithering")]]
     138[[Image(source:/web/trunk/www/study/out/grad2-6-3.png,class="inline",alt="4-wise square dithering gradient")]]
    139139
    140140This 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:
    141141
    142 [[Image(source:/web/trunk/static/study/out/fig2-6-4.png,class="matrix",alt="twin dragon dither tile")]]
    143 [[Image(source:/web/trunk/static/study/out/lena2-6-4.png,class="inline",alt="twin dragon dithering")]]
    144 [[Image(source:/web/trunk/static/study/out/grad2-6-4.png,class="inline",alt="twin dragon dithering gradient")]]
     142[[Image(source:/web/trunk/www/study/out/fig2-6-4.png,class="matrix",alt="twin dragon dither tile")]]
     143[[Image(source:/web/trunk/www/study/out/lena2-6-4.png,class="inline",alt="twin dragon dithering")]]
     144[[Image(source:/web/trunk/www/study/out/grad2-6-4.png,class="inline",alt="twin dragon dithering gradient")]]
    145145
    146146Here 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:
    147147
    148 [[Image(source:/web/trunk/static/study/fig2-6-5.png,class="matrix",alt="3-way hex2 dither tile")]]
    149 [[Image(source:/web/trunk/static/study/out/lena2-6-5.png,class="inline",alt="3-way hex2 dithering")]]
    150 [[Image(source:/web/trunk/static/study/out/grad2-6-5.png,class="inline",alt="3-way hex2 dithering gradient")]]
    151 
    152 [[Image(source:/web/trunk/static/study/fig2-6-6.png,class="matrix",alt="9-way hex2 dither tile")]]
    153 [[Image(source:/web/trunk/static/study/out/lena2-6-6.png,class="inline",alt="9-way hex2 dithering")]]
    154 [[Image(source:/web/trunk/static/study/out/grad2-6-6.png,class="inline",alt="9-way hex2 dithering gradient")]]
     148[[Image(source:/web/trunk/www/study/fig2-6-5.png,class="matrix",alt="3-way hex2 dither tile")]]
     149[[Image(source:/web/trunk/www/study/out/lena2-6-5.png,class="inline",alt="3-way hex2 dithering")]]
     150[[Image(source:/web/trunk/www/study/out/grad2-6-5.png,class="inline",alt="3-way hex2 dithering gradient")]]
     151
     152[[Image(source:/web/trunk/www/study/fig2-6-6.png,class="matrix",alt="9-way hex2 dither tile")]]
     153[[Image(source:/web/trunk/www/study/out/lena2-6-6.png,class="inline",alt="9-way hex2 dithering")]]
     154[[Image(source:/web/trunk/www/study/out/grad2-6-6.png,class="inline",alt="9-way hex2 dithering gradient")]]
    155155
    156156== 2.7. Void and cluster method ==
    … …  
    191191The 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:
    192192
    193 [[Image(source:/web/trunk/static/study/out/fig2-7-1.png,class="matrix",alt="14×14 void-and-cluster matrix")]] [[Image(source:/web/trunk/static/study/out/fig2-7-2.png,class="matrix",alt="25×25 void-and-cluster matrix")]]
     193[[Image(source:/web/trunk/www/study/out/fig2-7-1.png,class="matrix",alt="14×14 void-and-cluster matrix")]] [[Image(source:/web/trunk/www/study/out/fig2-7-2.png,class="matrix",alt="25×25 void-and-cluster matrix")]]
    194194
    195195Dither 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:
    196196
    197 [[Image(source:/web/trunk/static/study/out/lena2-7-1.png,class="inline",alt="14×14 void and cluster dithering")]]
    198 [[Image(source:/web/trunk/static/study/out/grad2-7-1.png,class="inline",alt="14×14 void and cluster dithering gradient")]]
    199 [[Image(source:/web/trunk/static/study/out/lena2-7-2.png,class="inline",alt="25×25 void and cluster dithering")]]
    200 [[Image(source:/web/trunk/static/study/out/grad2-7-2.png,class="inline",alt="25×25 void and cluster dithering gradient")]]
     197[[Image(source:/web/trunk/www/study/out/lena2-7-1.png,class="inline",alt="14×14 void and cluster dithering")]]
     198[[Image(source:/web/trunk/www/study/out/grad2-7-1.png,class="inline",alt="14×14 void and cluster dithering gradient")]]
     199[[Image(source:/web/trunk/www/study/out/lena2-7-2.png,class="inline",alt="25×25 void and cluster dithering")]]
     200[[Image(source:/web/trunk/www/study/out/grad2-7-2.png,class="inline",alt="25×25 void and cluster dithering gradient")]]
    201201
    202202This 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].