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


Ignore:
Timestamp:
12/22/2009 09:17:49 PM (14 years ago)
Author:
Sam Hocevar
Comment:

fix image links

Legend:

Unmodified
Added
Removed
Modified

  • libcaca/study/3

    v2 v3  
    77This is the simplest error diffusion method. It thresholds the image to 0.5 and propagates 100% of the error to the next (right) pixel. It is quite impressive given its simplicity but causes important visual artifacts:
    88
    9 [[Image(source:/web/trunk/static/study/out/lena3-0-1.png,class="inline",alt="Simple error diffusion")]]
    10 [[Image(source:/web/trunk/static/study/out/grad3-0-1.png,class="inline",alt="Simple error diffusion gradient")]]
     9[[Image(source:/web/trunk/www/study/out/lena3-0-1.png,class="inline",alt="Simple error diffusion")]]
     10[[Image(source:/web/trunk/www/study/out/grad3-0-1.png,class="inline",alt="Simple error diffusion gradient")]]
    1111
    1212== 3.1. Floyd-Steinberg and !JaJuNi error diffusion ==
    … …  
    1414The most famous error diffusion method is the '''Floyd-Steinberg''' algorithm ![5]. It propagates the error to more than one adjacent pixels using the following coefficients:
    1515
    16 [[Image(source:/web/trunk/static/study/out/fig3-1-1.png,alt="Floyd-Steinberg")]]
     16[[Image(source:/web/trunk/www/study/out/fig3-1-1.png,alt="Floyd-Steinberg")]]
    1717
    1818The result of this algorithm is rather impressive even compared to the best ordered dither results we could achieve:
    1919
    20 [[Image(source:/web/trunk/static/study/out/lena3-1-1.png,class="inline",alt="Floyd-Steinberg error diffusion")]]
    21 [[Image(source:/web/trunk/static/study/out/grad3-1-1.png,class="inline",alt="Floyd-Steinberg error diffusion gradient")]]
     20[[Image(source:/web/trunk/www/study/out/lena3-1-1.png,class="inline",alt="Floyd-Steinberg error diffusion")]]
     21[[Image(source:/web/trunk/www/study/out/grad3-1-1.png,class="inline",alt="Floyd-Steinberg error diffusion gradient")]]
    2222
    2323'''Jarvis, Judice and Ninke dithering''' ![7] (sometimes nicknamed '''!JaJuNi''') was published almost at the same time as Floyd-Steinberg. It uses a much more complex error diffusion matrix:
    2424
    25 [[Image(source:/web/trunk/static/study/out/fig3-1-3.png,class="matrix",alt="Jarvis, Judice and Ninke")]]
    26 [[Image(source:/web/trunk/static/study/out/lena3-1-3.png,class="inline",alt="Jarvis, Judice and Ninke error diffusion")]]
    27 [[Image(source:/web/trunk/static/study/out/grad3-1-3.png,class="inline",alt="Jarvis, Judice and Ninke error diffusion gradient")]]
     25[[Image(source:/web/trunk/www/study/out/fig3-1-3.png,class="matrix",alt="Jarvis, Judice and Ninke")]]
     26[[Image(source:/web/trunk/www/study/out/lena3-1-3.png,class="inline",alt="Jarvis, Judice and Ninke error diffusion")]]
     27[[Image(source:/web/trunk/www/study/out/grad3-1-3.png,class="inline",alt="Jarvis, Judice and Ninke error diffusion gradient")]]
    2828
    2929== 3.2. Floyd-Steinberg derivatives ==
    … …  
    3131Zhigang Fan came up with several Floyd-Steinberg derivatives. '''Fan dithering''' ![8] just moves one coefficient around:
    3232
    33 [[Image(source:/web/trunk/static/study/out/fig3-2-1.png,class="matrix",alt="Fan")]]
    34 [[Image(source:/web/trunk/static/study/out/lena3-2-1.png,class="inline",alt="Fan error diffusion")]]
    35 [[Image(source:/web/trunk/static/study/out/grad3-2-1.png,class="inline",alt="Fan error diffusion gradient")]]
     33[[Image(source:/web/trunk/www/study/out/fig3-2-1.png,class="matrix",alt="Fan")]]
     34[[Image(source:/web/trunk/www/study/out/lena3-2-1.png,class="inline",alt="Fan error diffusion")]]
     35[[Image(source:/web/trunk/www/study/out/grad3-2-1.png,class="inline",alt="Fan error diffusion gradient")]]
    3636
    3737'''Shiau-Fan dithering''' use a family of matrices supposed to reduce the apparition of artifacts usually seen with Floyd-Steinberg:
    3838
    39 [[Image(source:/web/trunk/static/study/out/fig3-2-1b.png,class="matrix",alt="Shiau-Fan")]]
    40 [[Image(source:/web/trunk/static/study/out/lena3-2-1b.png,class="inline",alt="Shiau-Fan error diffusion")]]
    41 [[Image(source:/web/trunk/static/study/out/grad3-2-1b.png,class="inline",alt="Shiau-Fan error diffusion gradient")]]
    42 
    43 [[Image(source:/web/trunk/static/study/out/fig3-2-1c.png,class="matrix",alt="Shiau-Fan 2")]]
    44 [[Image(source:/web/trunk/static/study/out/lena3-2-1c.png,class="inline",alt="Shiau-Fan 2 error diffusion")]]
    45 [[Image(source:/web/trunk/static/study/out/grad3-2-1c.png,class="inline",alt="Shiau-Fan 2 error diffusion gradient")]]
     39[[Image(source:/web/trunk/www/study/out/fig3-2-1b.png,class="matrix",alt="Shiau-Fan")]]
     40[[Image(source:/web/trunk/www/study/out/lena3-2-1b.png,class="inline",alt="Shiau-Fan error diffusion")]]
     41[[Image(source:/web/trunk/www/study/out/grad3-2-1b.png,class="inline",alt="Shiau-Fan error diffusion gradient")]]
     42
     43[[Image(source:/web/trunk/www/study/out/fig3-2-1c.png,class="matrix",alt="Shiau-Fan 2")]]
     44[[Image(source:/web/trunk/www/study/out/lena3-2-1c.png,class="inline",alt="Shiau-Fan 2 error diffusion")]]
     45[[Image(source:/web/trunk/www/study/out/grad3-2-1c.png,class="inline",alt="Shiau-Fan 2 error diffusion gradient")]]
    4646
    4747By the way, these matrices are covered by Shiau’s and Fan’s [http://www.freepatentsonline.com/5353127.html U.S. patent 5353127].
    … …  
    4949'''Stucki dithering''' ![6] is a slight variation of Jarvis-Judice-Ninke dithering:
    5050
    51 [[Image(source:/web/trunk/static/study/out/fig3-2-3.png,class="matrix",alt="Stucki")]]
    52 [[Image(source:/web/trunk/static/study/out/lena3-2-3.png,class="inline",alt="Stucki error diffusion")]]
    53 [[Image(source:/web/trunk/static/study/out/grad3-2-3.png,class="inline",alt="Stucki error diffusion gradient")]]
     51[[Image(source:/web/trunk/www/study/out/fig3-2-3.png,class="matrix",alt="Stucki")]]
     52[[Image(source:/web/trunk/www/study/out/lena3-2-3.png,class="inline",alt="Stucki error diffusion")]]
     53[[Image(source:/web/trunk/www/study/out/grad3-2-3.png,class="inline",alt="Stucki error diffusion gradient")]]
    5454
    5555'''Burkes dithering''' is yet another variation ![10] which improves on Stucki dithering by removing a line and making the error coefficients fractions of powers of two:
    5656
    57 [[Image(source:/web/trunk/static/study/out/fig3-2-4.png,class="matrix",alt="Burkes")]]
    58 [[Image(source:/web/trunk/static/study/out/lena3-2-4.png,class="inline",alt="Burkes error diffusion")]]
    59 [[Image(source:/web/trunk/static/study/out/grad3-2-4.png,class="inline",alt="Burkes error diffusion gradient")]]
     57[[Image(source:/web/trunk/www/study/out/fig3-2-4.png,class="matrix",alt="Burkes")]]
     58[[Image(source:/web/trunk/www/study/out/lena3-2-4.png,class="inline",alt="Burkes error diffusion")]]
     59[[Image(source:/web/trunk/www/study/out/grad3-2-4.png,class="inline",alt="Burkes error diffusion gradient")]]
    6060
    6161Frankie Sierra ![11] came up with a few error diffusion matrices: '''Sierra dithering''' is a variation of Jarvis that is slightly faster because it propagates to fewer pixels, '''Two-row Sierra''' is a simplified version thereof, and '''Filter Lite''' is one of the simplest Floyd-Steinberg derivatives:
    6262
    63 [[Image(source:/web/trunk/static/study/out/fig3-2-5.png,class="matrix",alt="Sierra")]]
    64 [[Image(source:/web/trunk/static/study/out/lena3-2-5.png,class="inline",alt="Sierra error diffusion")]]
    65 [[Image(source:/web/trunk/static/study/out/grad3-2-5.png,class="inline",alt="Sierra error diffusion gradient")]]
    66 
    67 [[Image(source:/web/trunk/static/study/out/fig3-2-6.png,class="matrix",alt="Sierra")]]
    68 [[Image(source:/web/trunk/static/study/out/lena3-2-6.png,class="inline",alt="Sierra error diffusion")]]
    69 [[Image(source:/web/trunk/static/study/out/grad3-2-6.png,class="inline",alt="Sierra error diffusion gradient")]]
    70 
    71 [[Image(source:/web/trunk/static/study/out/fig3-2-7.png,class="matrix",alt="Sierra")]]
    72 [[Image(source:/web/trunk/static/study/out/lena3-2-7.png,class="inline",alt="Sierra error diffusion")]]
    73 [[Image(source:/web/trunk/static/study/out/grad3-2-7.png,class="inline",alt="Sierra error diffusion gradient")]]
    74 
    75 '''Atkinson dithering''' ![12] only propagates 75% of the error, leading to a loss of contrast around very dark and very light areas (also called '''highlights and shadows'''), but better contrast in the midtones. The original Macintosh software ''HyperScan'' used this dithering algorithm, still considered superior to other Floyd-Steinberg derivatives by many Mac zealots:
    76 
    77 [[Image(source:/web/trunk/static/study/out/fig3-2-8.png,class="matrix",alt="Atkinson")]]
    78 [[Image(source:/web/trunk/static/study/out/lena3-2-8.png,class="inline",alt="Atkinson error diffusion")]]
    79 [[Image(source:/web/trunk/static/study/out/grad3-2-8.png,class="inline",alt="Atkinson error diffusion gradient")]]
     63[[Image(source:/web/trunk/www/study/out/fig3-2-5.png,class="matrix",alt="Sierra")]]
     64[[Image(source:/web/trunk/www/study/out/lena3-2-5.png,class="inline",alt="Sierra error diffusion")]]
     65[[Image(source:/web/trunk/www/study/out/grad3-2-5.png,class="inline",alt="Sierra error diffusion gradient")]]
     66
     67[[Image(source:/web/trunk/www/study/out/fig3-2-6.png,class="matrix",alt="Sierra")]]
     68[[Image(source:/web/trunk/www/study/out/lena3-2-6.png,class="inline",alt="Sierra error diffusion")]]
     69[[Image(source:/web/trunk/www/study/out/grad3-2-6.png,class="inline",alt="Sierra error diffusion gradient")]]
     70
     71[[Image(source:/web/trunk/www/study/out/fig3-2-7.png,class="matrix",alt="Sierra")]]
     72[[Image(source:/web/trunk/www/study/out/lena3-2-7.png,class="inline",alt="Sierra error diffusion")]]
     73[[Image(source:/web/trunk/www/study/out/grad3-2-7.png,class="inline",alt="Sierra error diffusion gradient")]]
     74
     75'''Atkinson dithering''' ![12] only propagates 75% of the error, leading to a loss of contrast around very dark and very light areas (also called '''highlights and shadows'''), but better contrast in the midtones. The original Macintosh software ''!HyperScan'' used this dithering algorithm, still considered superior to other Floyd-Steinberg derivatives by many Mac zealots:
     76
     77[[Image(source:/web/trunk/www/study/out/fig3-2-8.png,class="matrix",alt="Atkinson")]]
     78[[Image(source:/web/trunk/www/study/out/lena3-2-8.png,class="inline",alt="Atkinson error diffusion")]]
     79[[Image(source:/web/trunk/www/study/out/grad3-2-8.png,class="inline",alt="Atkinson error diffusion gradient")]]
    8080
    8181{{{
    … …  
    8585'''Stevenson-Arce dithering''':
    8686
    87 [[Image(source:/web/trunk/static/study/fig3-2-9.png,class="matrix",alt="Stevenson-Arce")]]
    88 [[Image(source:/web/trunk/static/study/out/lena3-2-9.png,class="inline",alt="Stevenson-Arce error diffusion")]]
    89 [[Image(source:/web/trunk/static/study/out/grad3-2-9.png,class="inline",alt="Stevenson-Arce error diffusion gradient")]]
     87[[Image(source:/web/trunk/www/study/fig3-2-9.png,class="matrix",alt="Stevenson-Arce")]]
     88[[Image(source:/web/trunk/www/study/out/lena3-2-9.png,class="inline",alt="Stevenson-Arce error diffusion")]]
     89[[Image(source:/web/trunk/www/study/out/grad3-2-9.png,class="inline",alt="Stevenson-Arce error diffusion gradient")]]
    9090}}}
    9191
    … …  
    9696The usual way to parse an image is one pixel after the other, following their order in memory. When reaching the end of a line, we automatically jump to the beginning of the next line. Error diffusion methods using this parsing order are called '''raster error diffusion''':
    9797
    98 [[Image(source:/web/trunk/static/study/fig3-3-1.png,class="matrix",alt="Regular parsing")]]
     98[[Image(source:/web/trunk/www/study/fig3-3-1.png,class="matrix",alt="Regular parsing")]]
    9999
    100100Changing the parsing order can help prevent the apparition of artifacts in error diffusion algorithms. This is '''serpentine parsing''', where every odd line is parsed in reverse order (right to left):
    101101
    102 [[Image(source:/web/trunk/static/study/fig3-3-2.png,class="matrix",alt="Serpentine parsing")]]
     102[[Image(source:/web/trunk/www/study/fig3-3-2.png,class="matrix",alt="Serpentine parsing")]]
    103103
    104104The major problem with Floyd-Steinberg is the '''worm artifacts''' it creates. Here is an example of an image made of grey 0.9 dithered with standard Floyd-Steinberg and with '''serpentine Floyd-Steinberg''' ![13 pp.266—267].  Most of the worm artifacts have disappeared or were highly reduced:
    105105
    106 [[Image(source:/web/trunk/static/study/out/lena3-3-1.png,class="inline",alt="Floyd-Steinberg on grey 90%")]]
    107 [[Image(source:/web/trunk/static/study/out/lena3-3-2.png,class="inline",alt="serpentine Floyd-Steinberg on grey 90%")]]
     106[[Image(source:/web/trunk/www/study/out/lena3-3-1.png,class="inline",alt="Floyd-Steinberg on grey 90%")]]
     107[[Image(source:/web/trunk/www/study/out/lena3-3-2.png,class="inline",alt="serpentine Floyd-Steinberg on grey 90%")]]
    108108
    109109And here are the results of serpentine Floyd-Steinberg on Lena. Only a very close look will show the differences with standard Floyd-Steinberg, but a few of the artifacts did disappear:
    110110
    111 [[Image(source:/web/trunk/static/study/out/lena3-1-2.png,class="inline",alt="serpentine Floyd-Steinberg")]]
    112 [[Image(source:/web/trunk/static/study/out/grad3-1-2.png,class="inline",alt="serpentine Floyd-Steinberg gradient")]]
     111[[Image(source:/web/trunk/www/study/out/lena3-1-2.png,class="inline",alt="serpentine Floyd-Steinberg")]]
     112[[Image(source:/web/trunk/www/study/out/grad3-1-2.png,class="inline",alt="serpentine Floyd-Steinberg gradient")]]
    113113
    114114'''Riemersma dithering''' ![26] parses the image following a plane-filling '''Hilbert curve''' and only propagates the error of the last ''q'' pixels, weighting it with an exponential rule. The method is interesting and inventive, unfortunately the results are disappointing: structural artifacts are worse than with other error diffusion methods (shown here with ''q = 16'' and ''r = 16''):
    115115
    116 [[Image(source:/web/trunk/static/study/fig3-3-3.png,class="matrix",alt="Hilbert curve parsing")]]
    117 [[Image(source:/web/trunk/static/study/out/lena3-3-3.png,class="inline",alt="Riemersma dither on Hilbert curve")]]
    118 [[Image(source:/web/trunk/static/study/out/grad3-3-3.png,class="inline",alt="Riemersma dither on Hilbert curve gradient")]]
     116[[Image(source:/web/trunk/www/study/fig3-3-3.png,class="matrix",alt="Hilbert curve parsing")]]
     117[[Image(source:/web/trunk/www/study/out/lena3-3-3.png,class="inline",alt="Riemersma dither on Hilbert curve")]]
     118[[Image(source:/web/trunk/www/study/out/grad3-3-3.png,class="inline",alt="Riemersma dither on Hilbert curve gradient")]]
    119119
    120120A variation of Riemersma dithering uses a '''Hilbert 2 curve''', giving slightly better results but still causing random artifacts here and there:
    121121
    122 [[Image(source:/web/trunk/static/study/fig3-3-4.png,class="matrix",alt="Hilbert 2 curve parsing")]]
    123 [[Image(source:/web/trunk/static/study/out/lena3-3-4.png,class="inline",alt="Riemersma dither on Hilbert 2 curve")]]
    124 [[Image(source:/web/trunk/static/study/out/grad3-3-4.png,class="inline",alt="Riemersma dither on Hilbert 2 curve gradient")]]
     122[[Image(source:/web/trunk/www/study/fig3-3-4.png,class="matrix",alt="Hilbert 2 curve parsing")]]
     123[[Image(source:/web/trunk/www/study/out/lena3-3-4.png,class="inline",alt="Riemersma dither on Hilbert 2 curve")]]
     124[[Image(source:/web/trunk/www/study/out/grad3-3-4.png,class="inline",alt="Riemersma dither on Hilbert 2 curve gradient")]]
    125125
    126126An inherent problem with plane-filling curves is that distances on the curve do not mean anything in image space. Riemersma dithering distributes error to pixels according to their distance on the curve rather than their distance in the image.
    … …  
    130130This is spatial Hilbert dithering on a Hilbert curve and on a Hilbert 2 curve. The results show a clear improvement over the original Riemersma algorithm, with far less noise and smoother low-gradient areas:
    131131
    132 [[Image(source:/web/trunk/static/study/out/lena3-3-5.png,class="inline",alt="spatial Hilbert dither on Hilbert curve")]]
    133 [[Image(source:/web/trunk/static/study/out/grad3-3-5.png,class="inline",alt="spatial Hilbert dither on Hilbert curve gradient")]]
    134 [[Image(source:/web/trunk/static/study/out/lena3-3-6.png,class="inline",alt="spatial Hilbert dither on Hilbert 2 curve")]]
    135 [[Image(source:/web/trunk/static/study/out/grad3-3-6.png,class="inline",alt="spatial Hilbert dither on Hilbert 2 curve gradient")]]
     132[[Image(source:/web/trunk/www/study/out/lena3-3-5.png,class="inline",alt="spatial Hilbert dither on Hilbert curve")]]
     133[[Image(source:/web/trunk/www/study/out/grad3-3-5.png,class="inline",alt="spatial Hilbert dither on Hilbert curve gradient")]]
     134[[Image(source:/web/trunk/www/study/out/lena3-3-6.png,class="inline",alt="spatial Hilbert dither on Hilbert 2 curve")]]
     135[[Image(source:/web/trunk/www/study/out/grad3-3-6.png,class="inline",alt="spatial Hilbert dither on Hilbert 2 curve gradient")]]
    136136
    137137'''Dot diffusion''' ![14] is an error diffusion method by Donald E. Knuth that uses tileable matrices just like ordered dithering, except that the cell value order is taken into account for error propagation. Diagonal cells get half as much error as directly adjacent cells:
    … …  
    141141For instance, in the following example, cell 25’s error is propagated to cells 44, 36, 30, 34 and 49. Given the diagonal cells rule, cells 44, 30 and 49 each get 1/7 of the error and cells 36 and 34 each get 2/7 of the error.  Similarly, cell 63 gets 100% of cell 61’s error.
    142142
    143 [[Image(source:/web/trunk/static/study/fig3-3-7.png,class="matrix",alt="Dot diffusion matrix sample")]]
    144 [[Image(source:/web/trunk/static/study/out/lena3-3-7.png,class="inline",alt="Dot diffusion")]]
    145 [[Image(source:/web/trunk/static/study/out/grad3-3-7.png,class="inline",alt="Dot diffusion gradient")]]
     143[[Image(source:/web/trunk/www/study/fig3-3-7.png,class="matrix",alt="Dot diffusion matrix sample")]]
     144[[Image(source:/web/trunk/www/study/out/lena3-3-7.png,class="inline",alt="Dot diffusion")]]
     145[[Image(source:/web/trunk/www/study/out/grad3-3-7.png,class="inline",alt="Dot diffusion gradient")]]
    146146
    147147The initial result is not extraordinary. But Knuth suggests applying a sharpen filter to the original image before applying dot diffusion. He also introduces a ''zeta'' value to deal with the size of laser printer dots, pretty similar to what we’ll see later as '''gamma correction'''. The following two images had a sharpening value of 0.9 applied to them. The image on the right shows ''zeta = 0.2'':
    148148
    149 [[Image(source:/web/trunk/static/study/out/lena3-3-8.png,class="inline",alt="Dot diffusion sharpen 0.9")]]
    150 [[Image(source:/web/trunk/static/study/out/grad3-3-8.png,class="inline",alt="Dot diffusion sharpen 0.9 gradient")]]
    151 [[Image(source:/web/trunk/static/study/out/lena3-3-9.png,class="inline",alt="Dot diffusion sharpen 0.9 zeta 0.2")]]
    152 [[Image(source:/web/trunk/static/study/out/grad3-3-9.png,class="inline",alt="Dot diffusion sharpen 0.9 zeta 0.2 gradient")]]
     149[[Image(source:/web/trunk/www/study/out/lena3-3-8.png,class="inline",alt="Dot diffusion sharpen 0.9")]]
     150[[Image(source:/web/trunk/www/study/out/grad3-3-8.png,class="inline",alt="Dot diffusion sharpen 0.9 gradient")]]
     151[[Image(source:/web/trunk/www/study/out/lena3-3-9.png,class="inline",alt="Dot diffusion sharpen 0.9 zeta 0.2")]]
     152[[Image(source:/web/trunk/www/study/out/grad3-3-9.png,class="inline",alt="Dot diffusion sharpen 0.9 zeta 0.2 gradient")]]
    153153
    154154Do not get fooled by Knuth’s apparent good results. They specifically target dot printers and do not give terribly good results on a computer screen. Actually, a sharpening filter makes just any dithering method look better, even basic Floyd-Steinberg dithering (shown here with a sharpening value of 0.9, too):
    155155
    156 [[Image(source:/web/trunk/static/study/out/lena3-3-10.png,class="inline",alt="FS with sharpening")]]
    157 [[Image(source:/web/trunk/static/study/out/grad3-3-10.png,class="inline",alt="FS with sharpening gradient")]]
     156[[Image(source:/web/trunk/www/study/out/lena3-3-10.png,class="inline",alt="FS with sharpening")]]
     157[[Image(source:/web/trunk/www/study/out/grad3-3-10.png,class="inline",alt="FS with sharpening gradient")]]
    158158
    159159Dot diffusion was reinvented 14 years later by Arney, Anderson and Ganawan without even citing Knuth. They call their method '''omni-directional error diffusion'''. Instead of using a clustered dot matrix like Knuth recommends for dot diffusion, they use a dispersed dot matrix, which gives far better results on a computer display. This is a 16×12 portion of that matrix:
    160160
    161 [[Image(source:/web/trunk/static/study/out/fig3-3-11b.png,class="matrix",alt="omni-directional ED matrix sample")]]
     161[[Image(source:/web/trunk/www/study/out/fig3-3-11b.png,class="matrix",alt="omni-directional ED matrix sample")]]
    162162
    163163The preferred implementation of omni-directional error diffusion uses a slightly different propagation matrix, where top and bottom neighbours get more error than the others:
    164164
    165 [[Image(source:/web/trunk/static/study/out/fig3-3-11.png,class="matrix",alt="omni-directional ED")]]
    166 [[Image(source:/web/trunk/static/study/out/lena3-3-11.png,class="inline",alt="omni-directional ED")]]
    167 [[Image(source:/web/trunk/static/study/out/grad3-3-11.png,class="inline",alt="omni-directional ED gradient")]]
     165[[Image(source:/web/trunk/www/study/out/fig3-3-11.png,class="matrix",alt="omni-directional ED")]]
     166[[Image(source:/web/trunk/www/study/out/lena3-3-11.png,class="inline",alt="omni-directional ED")]]
     167[[Image(source:/web/trunk/www/study/out/grad3-3-11.png,class="inline",alt="omni-directional ED gradient")]]
    168168
    169169== 3.4. Variable coefficients error diffusion ==
    … …  
    173173Ostromoukhov suggests error diffusion values that vary according to the input value. The list of 256 discrete value triplets for ''d1'', ''d2'' and ''d3'' he provides ![1] give pretty good results with serpentine parsing:
    174174
    175 [[Image(source:/web/trunk/static/study/out/fig3-4-1.png,class="matrix",alt="Ostromoukhov ED matrix")]]
    176 [[Image(source:/web/trunk/static/study/out/lena3-4-1.png,class="inline",alt="Ostromoukhov ED")]]
    177 [[Image(source:/web/trunk/static/study/out/grad3-4-1.png,class="inline",alt="Ostromoukhov ED gradient")]]
     175[[Image(source:/web/trunk/www/study/out/fig3-4-1.png,class="matrix",alt="Ostromoukhov ED matrix")]]
     176[[Image(source:/web/trunk/www/study/out/lena3-4-1.png,class="inline",alt="Ostromoukhov ED")]]
     177[[Image(source:/web/trunk/www/study/out/grad3-4-1.png,class="inline",alt="Ostromoukhov ED gradient")]]
    178178
    179179== 3.5. Block error diffusion ==
    … …  
    181181Sometimes, due to physical restrictions of the target media, output is limited to some combinations of pixel blocks, such as the ones shown below:
    182182
    183 [[Image(source:/web/trunk/static/study/fig3-5-1.png,class="matrix",alt="list of 2×2 pixel blocks")]]
     183[[Image(source:/web/trunk/www/study/fig3-5-1.png,class="matrix",alt="list of 2×2 pixel blocks")]]
    184184
    185185It is still possible to dither the image, by doing it 4 pixels at a time and simply choosing the block from the list that minimises the global error within the 2×2 block:
    186186
    187 [[Image(source:/web/trunk/static/study/out/lena3-5-1.png,class="inline",alt="2×2 pixel block quantisation")]]
    188 [[Image(source:/web/trunk/static/study/out/grad3-5-1.png,class="inline",alt="2×2 pixel block quantisation gradient")]]
     187[[Image(source:/web/trunk/www/study/out/lena3-5-1.png,class="inline",alt="2×2 pixel block quantisation")]]
     188[[Image(source:/web/trunk/www/study/out/grad3-5-1.png,class="inline",alt="2×2 pixel block quantisation gradient")]]
    189189
    190190Damera-Venkata and Evans introduce '''block error diffusion''' ![23], which reuses traditional error diffusion methods such as Floyd-Steinberg but applies the same error value to all pixels of a given block. Only one error value is propagated, ''a+b+c+d'', which is the global error within the block:
    191191
    192 [[Image(source:/web/trunk/static/study/out/fig3-1-1.png,class="math",alt="Floyd-Steinberg")]] ⊗ [[Image(source:/web/trunk/static/study/out/fig3-5-2b.png,class="math",alt="2×2 balanced matrix")]] = [[Image(source:/web/trunk/static/study/out/fig3-5-2.png,class="math",alt="2×2-expanded Floyd-Steinberg")]]
     192[[Image(source:/web/trunk/www/study/out/fig3-1-1.png,class="math",alt="Floyd-Steinberg")]] ⊗ [[Image(source:/web/trunk/www/study/out/fig3-5-2b.png,class="math",alt="2×2 balanced matrix")]] = [[Image(source:/web/trunk/www/study/out/fig3-5-2.png,class="math",alt="2×2-expanded Floyd-Steinberg")]]
    193193
    194194Here are the results using the previous pixel blocks:
    195195
    196 [[Image(source:/web/trunk/static/study/out/lena3-5-2.png,class="inline",alt="2×2 block Floyd-Steinberg")]]
    197 [[Image(source:/web/trunk/static/study/out/grad3-5-2.png,class="inline",alt="2×2 block Floyd-Steinberg gradient")]]
     196[[Image(source:/web/trunk/www/study/out/lena3-5-2.png,class="inline",alt="2×2 block Floyd-Steinberg")]]
     197[[Image(source:/web/trunk/www/study/out/grad3-5-2.png,class="inline",alt="2×2 block Floyd-Steinberg gradient")]]
    198198
    199199Carefully chosen blocks create constraints on the final picture that may be of artistic interest:
    200200
    201 [[Image(source:/web/trunk/static/study/fig3-5-3.png,class="matrix",alt="artistic 3×3 blocks")]]
    202 [[Image(source:/web/trunk/static/study/out/lena3-5-3.png,class="inline",alt="3×3 block Floyd-Steinberg")]]
    203 [[Image(source:/web/trunk/static/study/out/grad3-5-3.png,class="inline",alt="3×3 block Floyd-Steinberg gradient")]]
     201[[Image(source:/web/trunk/www/study/fig3-5-3.png,class="matrix",alt="artistic 3×3 blocks")]]
     202[[Image(source:/web/trunk/www/study/out/lena3-5-3.png,class="inline",alt="3×3 block Floyd-Steinberg")]]
     203[[Image(source:/web/trunk/www/study/out/grad3-5-3.png,class="inline",alt="3×3 block Floyd-Steinberg gradient")]]
    204204
    205205Using all possible pixel blocks is not equivalent to dithering the image pixel by pixel. This is due to both the block-choosing method, which only minimises the difference of mean values within blocks intead of the sum of local distances, and to the inefficient matrix coefficients, which propagate the error beyond immediate neighbours, causing the image to look sharpened.
    … …  
    207207This example shows standard block Floyd-Steinberg using all possible 2×2 blocks:
    208208
    209 [[Image(source:/web/trunk/static/study/fig3-5-4.png,class="matrix",alt="all possible 2×2 blocks")]]
    210 [[Image(source:/web/trunk/static/study/out/lena3-5-4.png,class="inline",alt="full 2×2 block Floyd-Steinberg")]]
    211 [[Image(source:/web/trunk/static/study/out/grad3-5-4.png,class="inline",alt="full 2×2 block Floyd-Steinberg gradient")]]
     209[[Image(source:/web/trunk/www/study/fig3-5-4.png,class="matrix",alt="all possible 2×2 blocks")]]
     210[[Image(source:/web/trunk/www/study/out/lena3-5-4.png,class="inline",alt="full 2×2 block Floyd-Steinberg")]]
     211[[Image(source:/web/trunk/www/study/out/grad3-5-4.png,class="inline",alt="full 2×2 block Floyd-Steinberg gradient")]]
    212212
    213213The results on the vertical gradient indicate poor block-choosing. In order to improve it, we introduce a modified, weighted intra-block error distribution matrix, still based on the original Floyd-Steinberg matrix:
    214214
    215 [[Image(source:/web/trunk/static/study/out/fig3-1-1.png,class="math",alt="Floyd-Steinberg")]] ⊗ [[Image(source:/web/trunk/static/study/out/fig3-5-5b.png,class="math",alt="weighted 2×2 matrix")]] = [[Image(source:/web/trunk/static/study/out/fig3-5-5.png,class="math",alt="weighted 2×2 propagation matrix")]]
     215[[Image(source:/web/trunk/www/study/out/fig3-1-1.png,class="math",alt="Floyd-Steinberg")]] ⊗ [[Image(source:/web/trunk/www/study/out/fig3-5-5b.png,class="math",alt="weighted 2×2 matrix")]] = [[Image(source:/web/trunk/www/study/out/fig3-5-5.png,class="math",alt="weighted 2×2 propagation matrix")]]
    216216
    217217The result still looks sharpened, but shows considerably less noise:
    218218
    219 [[Image(source:/web/trunk/static/study/out/lena3-5-5.png,class="inline",alt="weighted full 2×2 block Floyd-Steinberg")]]
    220 [[Image(source:/web/trunk/static/study/out/grad3-5-5.png,class="inline",alt="weighted full 2×2 block Floyd-Steinberg gradient")]]
     219[[Image(source:/web/trunk/www/study/out/lena3-5-5.png,class="inline",alt="weighted full 2×2 block Floyd-Steinberg")]]
     220[[Image(source:/web/trunk/www/study/out/grad3-5-5.png,class="inline",alt="weighted full 2×2 block Floyd-Steinberg gradient")]]
    221221
    222222== 3.6. Sub-block error diffusion ==
    … …  
    230230We use ''m⋅n'' error diffusion matrices, one for each of the current block’s pixels. Here are four error diffusion matrices for 2×2 blocks, generated from the standard Floyd-Steinberg matrix:
    231231
    232 [[Image(source:/web/trunk/static/study/out/fig3-6-1a.png,class="math",alt="sub-block 0,0 Floyd-Steinberg")]]
    233 [[Image(source:/web/trunk/static/study/out/fig3-6-1b.png,class="math",alt="sub-block 1,0 Floyd-Steinberg")]]
    234 
    235 [[Image(source:/web/trunk/static/study/out/fig3-6-1c.png,class="math",alt="sub-block 0,1 Floyd-Steinberg")]]
    236 [[Image(source:/web/trunk/static/study/out/fig3-6-1d.png,class="math",alt="sub-block 1,1 Floyd-Steinberg")]]
     232[[Image(source:/web/trunk/www/study/out/fig3-6-1a.png,class="math",alt="sub-block 0,0 Floyd-Steinberg")]]
     233[[Image(source:/web/trunk/www/study/out/fig3-6-1b.png,class="math",alt="sub-block 1,0 Floyd-Steinberg")]]
     234
     235[[Image(source:/web/trunk/www/study/out/fig3-6-1c.png,class="math",alt="sub-block 0,1 Floyd-Steinberg")]]
     236[[Image(source:/web/trunk/www/study/out/fig3-6-1d.png,class="math",alt="sub-block 1,1 Floyd-Steinberg")]]
    237237
    238238The results are far better than with the original block error diffusion method. On the left, sub-block error diffusion with all possible 2×2 blocks.  On the right, sub-block error diffusion restricted to the tiles seen in 3.5:
    239239
    240 [[Image(source:/web/trunk/static/study/out/lena3-6-1.png,class="inline",alt="full 2×2 sub-block Floyd-Steinberg")]]
    241 [[Image(source:/web/trunk/static/study/out/grad3-6-1.png,class="inline",alt="full 2×2 sub-block Floyd-Steinberg gradient")]]
    242 [[Image(source:/web/trunk/static/study/out/lena3-6-2.png,class="inline",alt="2×2 lines sub-block Floyd-Steinberg")]]
    243 [[Image(source:/web/trunk/static/study/out/grad3-6-2.png,class="inline",alt="2×2 lines sub-block Floyd-Steinberg gradient")]]
     240[[Image(source:/web/trunk/www/study/out/lena3-6-1.png,class="inline",alt="full 2×2 sub-block Floyd-Steinberg")]]
     241[[Image(source:/web/trunk/www/study/out/grad3-6-1.png,class="inline",alt="full 2×2 sub-block Floyd-Steinberg gradient")]]
     242[[Image(source:/web/trunk/www/study/out/lena3-6-2.png,class="inline",alt="2×2 lines sub-block Floyd-Steinberg")]]
     243[[Image(source:/web/trunk/www/study/out/grad3-6-2.png,class="inline",alt="2×2 lines sub-block Floyd-Steinberg gradient")]]
    244244
    245245Similar error diffusion matrices can be generated for 3×3 blocks:
    246246
    247 [[Image(source:/web/trunk/static/study/out/fig3-6-3a.png,class="math",alt="sub-block 0,0/3×3 Floyd-Steinberg")]]
    248 [[Image(source:/web/trunk/static/study/out/fig3-6-3b.png,class="math",alt="sub-block 1,0/3×3 Floyd-Steinberg")]]
    249 [[Image(source:/web/trunk/static/study/out/fig3-6-3c.png,class="math",alt="sub-block 2,0/3×3 Floyd-Steinberg")]]
    250 
    251 [[Image(source:/web/trunk/static/study/out/fig3-6-3d.png,class="math",alt="sub-block 0,1/3×3 Floyd-Steinberg")]]
    252 [[Image(source:/web/trunk/static/study/out/fig3-6-3e.png,class="math",alt="sub-block 1,1/3×3 Floyd-Steinberg")]]
    253 [[Image(source:/web/trunk/static/study/out/fig3-6-3f.png,class="math",alt="sub-block 2,1/3×3 Floyd-Steinberg")]]
    254 
    255 [[Image(source:/web/trunk/static/study/out/fig3-6-3g.png,class="math",alt="sub-block 0,2/3×3 Floyd-Steinberg")]]
    256 [[Image(source:/web/trunk/static/study/out/fig3-6-3h.png,class="math",alt="sub-block 1,2/3×3 Floyd-Steinberg")]]
    257 [[Image(source:/web/trunk/static/study/out/fig3-6-3i.png,class="math",alt="sub-block 2,2/3×3 Floyd-Steinberg")]]
     247[[Image(source:/web/trunk/www/study/out/fig3-6-3a.png,class="math",alt="sub-block 0,0/3×3 Floyd-Steinberg")]]
     248[[Image(source:/web/trunk/www/study/out/fig3-6-3b.png,class="math",alt="sub-block 1,0/3×3 Floyd-Steinberg")]]
     249[[Image(source:/web/trunk/www/study/out/fig3-6-3c.png,class="math",alt="sub-block 2,0/3×3 Floyd-Steinberg")]]
     250
     251[[Image(source:/web/trunk/www/study/out/fig3-6-3d.png,class="math",alt="sub-block 0,1/3×3 Floyd-Steinberg")]]
     252[[Image(source:/web/trunk/www/study/out/fig3-6-3e.png,class="math",alt="sub-block 1,1/3×3 Floyd-Steinberg")]]
     253[[Image(source:/web/trunk/www/study/out/fig3-6-3f.png,class="math",alt="sub-block 2,1/3×3 Floyd-Steinberg")]]
     254
     255[[Image(source:/web/trunk/www/study/out/fig3-6-3g.png,class="math",alt="sub-block 0,2/3×3 Floyd-Steinberg")]]
     256[[Image(source:/web/trunk/www/study/out/fig3-6-3h.png,class="math",alt="sub-block 1,2/3×3 Floyd-Steinberg")]]
     257[[Image(source:/web/trunk/www/study/out/fig3-6-3i.png,class="math",alt="sub-block 2,2/3×3 Floyd-Steinberg")]]
    258258
    259259Here are the results with all the possible 3×3 blocks, and with the artistic 3×3 blocks seen in 3.5:
    260260
    261 [[Image(source:/web/trunk/static/study/out/lena3-6-3.png,class="inline",alt="3×3 sub-block Floyd-Steinberg")]]
    262 [[Image(source:/web/trunk/static/study/out/grad3-6-3.png,class="inline",alt="3×3 sub-block Floyd-Steinberg gradient")]]
    263 [[Image(source:/web/trunk/static/study/out/lena3-6-4.png,class="inline",alt="3×3 artistic sub-block Floyd-Steinberg")]]
    264 [[Image(source:/web/trunk/static/study/out/grad3-6-4.png,class="inline",alt="3×3 artistic sub-block Floyd-Steinberg gradient")]]
     261[[Image(source:/web/trunk/www/study/out/lena3-6-3.png,class="inline",alt="3×3 sub-block Floyd-Steinberg")]]
     262[[Image(source:/web/trunk/www/study/out/grad3-6-3.png,class="inline",alt="3×3 sub-block Floyd-Steinberg gradient")]]
     263[[Image(source:/web/trunk/www/study/out/lena3-6-4.png,class="inline",alt="3×3 artistic sub-block Floyd-Steinberg")]]
     264[[Image(source:/web/trunk/www/study/out/grad3-6-4.png,class="inline",alt="3×3 artistic sub-block Floyd-Steinberg gradient")]]