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


Ignore:
Timestamp:
08/08/2009 02:36:52 PM (15 years ago)
Author:
Sam Hocevar
Comment:

chapter 4

Legend:

Unmodified
Added
Removed
Modified

  • libcaca/study/4

    v1 v1  
     1= 4. Model-based dithering =
     2
     3So far all dithering methods have relied on the assumption that carefully positioned black and white pixels gave the illusion of greyscales, but we have not stated exactly how the human eye reacted. Also, we do not have an automated way to compare the results of two different algorithms: judging that an algorithm is “better” has mostly been a subjective process so far.
     4
     5In order to figure out what the human eye really sees, we need a '''human visual system''' (HVS) model. Countless models exist, and we are only going to focus on simple ones for now.
     6
     7== 4.1. Gaussian human visual system model ==
     8
     9One of the simplest models is the '''gaussian HVS model'''. It states that the human eye acts like a gaussian convolution filter, slightly blurring pixel neighbourhoods and therefore simulating what the eye sees as distance from the image increases. This model, a simplified '''luminance spatial frequency response formula''', can be expressed using the two-dimensional ''exp(-(x²+y²)/2σ²)'' function. The ''σ'' parameter sort of introduces the viewing distance into the model.
     10
     11Here are the results of applying a gaussian HVS to an 8×8 Bayer dithered image, simply by convoluting the image with a gaussian blur filter. This process is also known as '''inverse halftoning'''. Different values of ''σ'' simulate what the eye sees from different distances. On the left ''σ = 1'', on the right ''σ = 2'':
     12
     13[[Image(source:/web/trunk/static/study/out/lena4-1-1.png,class="inline",alt="8×8 Bayer dither, gaussian HVS, σ = 1")]]
     14[[Image(source:/web/trunk/static/study/out/grad4-1-1.png,class="inline",alt="8×8 Bayer dither, gaussian HVS, σ = 1 gradient")]]
     15[[Image(source:/web/trunk/static/study/out/lena4-1-2.png,class="inline",alt="8×8 Bayer dither, gaussian HVS, σ = 2")]]
     16[[Image(source:/web/trunk/static/study/out/grad4-1-2.png,class="inline",alt="8×8 Bayer dither, gaussian HVS, σ = 2 gradient")]]
     17
     18== 4.2. Direct binary search ==
     19
     20We have already seen that standard error diffusion methods do not go back to pixels that have been set. '''Direct binary search''' ![4] (DBS) is an iterative method that processes the image a fixed number of times, or until the error can no longer be minimised:
     21
     22 * Generate an initial dithered image
     23 * Repeat until no changes can be applied:
     24   * Compute the global error between the original and the dithered images
     25   * For each pixel in the dithered image:
     26     * Compute the effect on the error of toggling the value of the current pixel
     27     * Compute the effect on the error of swapping the current pixel with one of its immediate neighbours
     28     * If the error can be reduced, perform the corresponding action
     29
     30The efficiency and quality of DBS depend on many implementation details, starting with the HVS model it uses to compute the error. Also, the initial image used as iteration zero will give poor results if pattern artifacts are already present. The order in which pixels are processed is important, too.  Unfortunately, despite its very high-quality results, DBS is usually a very slow algorithm.
     31
     32Below is an example of the algorithm results. The HVS uses a 11×11 convolution kernel of the ''e<small><sup> -sqrt(x²+y²)</sup></small>'' function. The initial image is randomly thresholded, and pixels are processed in raster order. Iterations 1, 2 and 5 are shown:
     33
     34[[Image(source:/web/trunk/static/study/out/lena4-2-1.png,class="inline",alt="direct binary search, iteration 0")]]
     35[[Image(source:/web/trunk/static/study/out/grad4-2-1.png,class="inline",alt="direct binary search, iteration 0 gradient")]]
     36[[Image(source:/web/trunk/static/study/out/lena4-2-2.png,class="inline",alt="direct binary search, iteration 1")]]
     37[[Image(source:/web/trunk/static/study/out/grad4-2-2.png,class="inline",alt="direct binary search, iteration 1 gradient")]]
     38
     39[[Image(source:/web/trunk/static/study/out/lena4-2-3.png,class="inline",alt="direct binary search, iteration 2")]]
     40[[Image(source:/web/trunk/static/study/out/grad4-2-3.png,class="inline",alt="direct binary search, iteration 2 gradient")]]
     41[[Image(source:/web/trunk/static/study/out/lena4-2-4.png,class="inline",alt="direct binary search, iteration 5")]]
     42[[Image(source:/web/trunk/static/study/out/grad4-2-4.png,class="inline",alt="direct binary search, iteration 5 gradient")]]
     43
     44Other HVS models can be used, giving very high quality results. Below are the results of DBS with the following HVS functions:
     45
     46{{{
     47#!latex
     48$f_1(x,y) = e^{-\dfrac{x^2+y^2}{2}}$
     49
     50$f_2(x,y) = e^{-\dfrac{x^2+y^2}{4.5}}$
     51
     52$f_3(x,y) = e^{-\dfrac{x^2+y^2}{8}}$
     53
     54$f_4(x,y) = 2e^{-\dfrac{x^2+y^2}{1.5}} + e^{-\dfrac{x^2+y^2}{8}}$
     55}}}
     56
     57The iteration shown is number 5. More iterations would have improved the results even slightly more, but that would have been at the expense of performance:
     58
     59[[Image(source:/web/trunk/static/study/out/lena4-2-5.png,class="inline",alt="direct binary search, sigma = 1, iteration 5")]]
     60[[Image(source:/web/trunk/static/study/out/grad4-2-5.png,class="inline",alt="direct binary search, sigma = 1, iteration 5 gradient")]]
     61[[Image(source:/web/trunk/static/study/out/lena4-2-6.png,class="inline",alt="direct binary search, sigma = 1.5, iteration 5")]]
     62[[Image(source:/web/trunk/static/study/out/grad4-2-6.png,class="inline",alt="direct binary search, sigma = 1.5, iteration 5 gradient")]]
     63
     64[[Image(source:/web/trunk/static/study/out/lena4-2-7.png,class="inline",alt="direct binary search, sigma = 2, iteration 5")]]
     65[[Image(source:/web/trunk/static/study/out/grad4-2-7.png,class="inline",alt="direct binary search, sigma = 2, iteration 5 gradient")]]
     66[[Image(source:/web/trunk/static/study/out/lena4-2-8.png,class="inline",alt="direct binary search, best HVS, iteration 5")]]
     67[[Image(source:/web/trunk/static/study/out/grad4-2-8.png,class="inline",alt="direct binary search, best HVS, iteration 5 gradient")]]
     68
     69== 4.3 Comparing dithering algorithms ==
     70
     71Using an HVS model, it is possible to classify previously seen algorithms simply by applying the model to both the source and the destination images, and computing their per-pixel '''mean squared error'''. This gives a better estimation of the dithering algorithm’s quality than simply computing a local, pixel-bound error.
     72
     73The following table shows that different HVS models give very different error values depending on the value of ''σ''. Also, in the case of the DBS algorithm, a carefully crafted HVS function such as the last one, which combines two different HVS models, gives low error values at every ''σ'', which means the dithered image is close to the original image at all corresponding viewing distances:
     74
     75{{{
     76#!html
     77<table class="score" cellspacing="1">
     78  <tr><th>Chapter 1: Thresholding</th>
     79      <th>Error %<br />σ = 1</th><th>Error %<br />σ = 1.5</th><th>Error %<br />σ = 2</th></tr>
     80  <tr><td>0.5 thresholding</td>
     81      <td>8.60303</td><td>7.93554</td><td>7.42669</td></tr>
     82  <tr><td>0.4 thresholding</td>
     83      <td>9.78990</td><td>9.10994</td><td>8.61878</td></tr>
     84  <tr><td>0.6 thresholding</td>
     85      <td>10.77689</td><td>10.33373</td><td>10.00462</td></tr>
     86  <tr><td>dynamic thresholding</td>
     87      <td>10.31568</td><td>9.60749</td><td>9.09760</td></tr>
     88  <tr><td>uniform random dithering</td>
     89      <td class="hi">1.57895</td><td class="hi">0.69762</td><td class="hi">0.39713</td></tr>
     90  <tr><td>gaussian random dithering</td>
     91      <td>2.95590</td><td>2.34461</td><td>2.08792</td></tr>
     92
     93  <tr><th>Chapter 2: Halftoning</th>
     94      <th>Error %<br />σ = 1</th><th>Error %<br />σ = 1.5</th><th>Error %<br />σ = 2</th></tr>
     95  <tr><td>25/50/75% patterns dithering</td>
     96      <td>0.56642</td><td>0.46490</td><td>0.41816</td></tr>
     97  <tr><td>2×2 Bayer dithering</td>
     98      <td>0.56694</td><td>0.46622</td><td>0.41956</td></tr>
     99  <tr><td>4×4 Bayer dithering</td>
     100      <td class="hi">0.20538</td><td>0.08060</td><td>0.05457</td></tr>
     101  <tr><td>8×8 Bayer dithering</td>
     102      <td class="hi">0.19691</td><td class="hi">0.06352</td><td class="hi">0.03354</td></tr>
     103  <tr><td>4×4 cluster dot dithering</td>
     104      <td>1.20026</td><td>0.14863</td><td>0.07100</td></tr>
     105  <tr><td>8×8 cluster dot dithering</td>
     106      <td>3.86236</td><td>0.85236</td><td>0.14443</td></tr>
     107  <tr><td>5×3 artistic line dithering</td>
     108      <td>2.75590</td><td>0.49420</td><td>0.11578</td></tr>
     109  <tr><td>perturbated 8×8 Bayer dithering</td>
     110      <td>0.40550</td><td>0.16971</td><td>0.09804</td></tr>
     111  <tr><td>random 3×3 dithering matrix selection</td>
     112      <td>0.60329</td><td>0.25055</td><td>0.16521</td></tr>
     113  <tr><td>“plus” pattern dithering</td>
     114      <td>0.43061</td><td>0.33540</td><td>0.29851</td></tr>
     115  <tr><td>“hex” pattern dithering</td>
     116      <td>0.26747</td><td>0.16119</td><td>0.13068</td></tr>
     117  <tr><td>“doubleplus” pattern dithering</td>
     118      <td>0.42852</td><td>0.12232</td><td>0.08904</td></tr>
     119  <tr><td>“hex2” pattern dithering</td>
     120      <td>0.35057</td><td>0.13046</td><td>0.09533</td></tr>
     121  <tr><td>4-wise supercell “plus” pattern dithering</td>
     122      <td class="hi">0.21903</td><td>0.07494</td><td>0.04423</td></tr>
     123  <tr><td>3-wise supercell “hex” pattern dithering</td>
     124      <td class="hi">0.21621</td><td>0.07356</td><td>0.04193</td></tr>
     125  <tr><td>4-wise supercell “doubleplus” pattern dithering</td>
     126      <td>0.40883</td><td>0.07051</td><td class="hi">0.03609</td></tr>
     127  <tr><td>6th order dragon curve dithering</td>
     128      <td class="hi">0.20503</td><td class="hi">0.06719</td><td class="hi">0.03539</td></tr>
     129  <tr><td>3-wise supercell “hex2” pattern dithering</td>
     130      <td>0.32643</td><td>0.07861</td><td>0.04061</td></tr>
     131  <tr><td>9-wise supercell “hex2” pattern dithering</td>
     132      <td>0.32336</td><td>0.07775</td><td>0.04087</td></tr>
     133  <tr><td>14×14 void-and-cluster dithering</td>
     134      <td class="hi">0.19726</td><td class="hi">0.06748</td><td class="hi">0.03663</td></tr>
     135  <tr><td>25×25 void-and-cluster dithering</td>
     136      <td class="hi">0.19248</td><td class="hi">0.06267</td><td class="hi">0.03325</td></tr>
     137
     138  <tr><th>Chapter 3: Error diffusion</th>
     139      <th>Error %<br />σ = 1</th><th>Error %<br />σ = 1.5</th><th>Error %<br />σ = 2</th></tr>
     140  <tr><td>naïve error diffusion</td>
     141      <td>0.33352</td><td>0.06372</td><td>0.01961</td></tr>
     142  <tr><td>Floyd-Steinberg error diffusion</td>
     143      <td class="hi">0.09249</td><td class="hi">0.01847</td><td class="hi">0.00859</td></tr>
     144  <tr><td>serpentine Floyd-Steinberg error diffusion</td>
     145      <td class="hi">0.09891</td><td class="hi">0.01849</td><td class="hi">0.00749</td></tr>
     146  <tr><td>Jarvis, Judice and Ninke dithering</td>
     147      <td>0.27198</td><td>0.06257</td><td>0.03472</td></tr>
     148  <tr><td>Fan dithering</td>
     149      <td class="hi">0.10220</td><td class="hi">0.01728</td><td class="hi">0.00705</td></tr>
     150  <tr><td>4-cell Shiau-Fan dithering</td>
     151      <td class="hi">0.11618</td><td class="hi">0.01785</td><td class="hi">0.00660</td></tr>
     152  <tr><td>5-cell Shiau-Fan dithering</td>
     153      <td class="hi">0.11550</td><td class="hi">0.01950</td><td class="hi">0.00708</td></tr>
     154  <tr><td>Stucki dithering</td>
     155      <td>0.19765</td><td>0.05373</td><td>0.03012</td></tr>
     156  <tr><td>Burkes dithering</td>
     157      <td>0.15831</td><td>0.04014</td><td>0.02178</td></tr>
     158  <tr><td>Sierra dithering</td>
     159      <td>0.23498</td><td>0.05415</td><td>0.03011</td></tr>
     160  <tr><td>Sierra 2 dithering</td>
     161      <td>0.22249</td><td>0.05121</td><td>0.02812</td></tr>
     162  <tr><td>Filter Lite</td>
     163      <td class="hi">0.09740</td><td class="hi">0.01605</td><td class="hi">0.00638</td></tr>
     164  <tr><td>Atkinson dithering</td>
     165      <td>0.47209</td><td>0.31012</td><td>0.27339</td></tr>
     166  <tr><td>Riemersma dithering on a Hilbert curve</td>
     167      <td>0.28224</td><td>0.06529</td><td>0.02693</td></tr>
     168  <tr><td>Riemersma dithering on a Hilbert 2 curve</td>
     169      <td>0.26622</td><td>0.06003</td><td>0.02492</td></tr>
     170  <tr><td>spatial Hilbert dithering on a Hilbert curve</td>
     171      <td>0.27289</td><td>0.06124</td><td>0.02184</td></tr>
     172  <tr><td>spatial Hilbert dithering on a Hilbert 2 curve</td>
     173      <td>0.22821</td><td>0.05246</td><td>0.01911</td></tr>
     174  <tr><td>dot diffusion</td>
     175      <td>0.38301</td><td>0.08063</td><td>0.01918</td></tr>
     176  <tr><td>dot diffusion with sharpen = 0.9</td>
     177      <td>0.78546</td><td>0.34941</td><td>0.23479</td></tr>
     178  <tr><td>dot diffusion with sharpen = 0.9 and zeta = 0.2</td>
     179      <td>2.91287</td><td>2.19398</td><td>1.99858</td></tr>
     180  <tr><td>serpentine Floyd-Steinberg with sharpen = 0.9</td>
     181      <td>0.62615</td><td>0.30851</td><td>0.22111</td></tr>
     182  <tr><td>omni-directional error diffusion</td>
     183      <td>0.23860</td><td>0.06821</td><td>0.03498</td></tr>
     184  <tr><td>Ostromoukhov’s variable error diffusion</td>
     185      <td class="hi">0.11203</td><td class="hi">0.01772</td><td class="hi">0.00593</td></tr>
     186  <tr><td>nearest block matching with 2×2 line tiles</td>
     187      <td>1.92430</td><td>1.34822</td><td>1.13685</td></tr>
     188  <tr><td>block error diffusion with 2×2 line tiles</td>
     189      <td>0.86807</td><td>0.22411</td><td>0.08901</td></tr>
     190  <tr><td>block error diffusion with 3×3 artistic tiles</td>
     191      <td>1.78626</td><td>0.56957</td><td>0.23000</td></tr>
     192  <tr><td>block error diffusion with all 2×2 tiles</td>
     193      <td>0.56466</td><td>0.15910</td><td>0.06946</td></tr>
     194  <tr><td>block error diffusion with all 2×2 tiles and<br />weighted intra-block error distribution</td>
     195      <td>0.37738</td><td>0.10434</td><td>0.04643</td></tr>
     196  <tr><td>sub-block error diffusion with all 2×2 tiles</td>
     197      <td>0.14697</td><td>0.02605</td><td class="hi">0.00894</td></tr>
     198  <tr><td>sub-block error diffusion with 2×2 line tiles</td>
     199      <td>0.35759</td><td>0.06081</td><td>0.01855</td></tr>
     200  <tr><td>sub-block error diffusion with all 3×3 tiles</td>
     201      <td>0.32802</td><td>0.06516</td><td>0.02165</td></tr>
     202  <tr><td>sub-block error diffusion with 3×3 artistic tiles</td>
     203      <td>1.03963</td><td>0.21839</td><td>0.06678</td></tr>
     204  <tr><th>Chapter 4: Model-based dithering</th>
     205      <th>Error %<br />σ = 1</th><th>Error %<br />σ = 1.5</th><th>Error %<br />σ = 2</th></tr>
     206  <tr><td>DBS with HVS <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>, iteration 1</td>
     207      <td>0.25810</td><td>0.06780</td><td>0.03489</td></tr>
     208  <tr><td>DBS with HVS <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>, iteration 2</td>
     209      <td>0.13762</td><td>0.03234</td><td>0.01939</td></tr>
     210  <tr><td>DBS with HVS <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>, iteration 5</td>
     211      <td class="hi">0.10452</td><td>0.02745</td><td>0.01918</td></tr>
     212  <tr><td>DBS with HVS <i>e<small><sup> -(x²+y²)/2</sup></small></i>, iteration 5</td>
     213      <td class="hi">0.10344</td><td>0.03860</td><td>0.02669</td></tr>
     214  <tr><td>DBS with HVS <i>e<small><sup> -(x²+y²)/4.5</sup></small></i>, iteration 5</td>
     215      <td>0.18034</td><td class="hi">0.00984</td><td class="hi">0.00219</td></tr>
     216  <tr><td>DBS with HVS <i>e<small><sup> -(x²+y²)/8</sup></small></i>, iteration 5</td>
     217      <td>0.37804</td><td>0.02866</td><td class="hi">0.00295</td></tr>
     218  <tr><td>DBS with HVS <i>2e<small><sup> -(x²+y²)/1.5</sup></small> + e<small><sup> -(x²+y²)/8</sup></small></i>, iteration 5</td>
     219      <td class="hi">0.09838</td><td class="hi">0.00884</td><td class="hi">0.00263</td></tr>
     220</table>
     221
     222<!--
     223DBS, sqrt:
     224  1.55543 0.68523 0.39111
     225  0.25810 0.06780 0.03489
     226  0.13762 0.03234 0.01939
     227  0.10452 0.02745 0.01918
     228DBS, sigma = 1:
     229  1.55543 0.68523 0.39111
     230  0.25379 0.09531 0.05629
     231  0.13447 0.04785 0.03057
     232  0.10344 0.03860 0.02669
     233DBS, sigma = 1.5:
     234  1.55543 0.68523 0.39111
     235  0.34373 0.05932 0.02545
     236  0.22412 0.01906 0.00560
     237  0.18034 0.00984 0.00219
     238DBS, sigma = 2:
     239  1.55543 0.68523 0.39111
     240  0.54240 0.09412 0.03133
     241  0.41340 0.04324 0.00804
     242  0.37804 0.02866 0.00295
     243-->
     244}}}