= 4. Model-based dithering =

So 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.

In 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.

== 4.1. Gaussian human visual system model ==

One 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.

Here 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'':

[[Image(source:/web/trunk/www/study/out/lena4-1-1.png,class="inline",alt="8×8 Bayer dither, gaussian HVS, σ = 1")]]
[[Image(source:/web/trunk/www/study/out/grad4-1-1.png,class="inline",alt="8×8 Bayer dither, gaussian HVS, σ = 1 gradient")]]
[[Image(source:/web/trunk/www/study/out/lena4-1-2.png,class="inline",alt="8×8 Bayer dither, gaussian HVS, σ = 2")]]
[[Image(source:/web/trunk/www/study/out/grad4-1-2.png,class="inline",alt="8×8 Bayer dither, gaussian HVS, σ = 2 gradient")]]

== 4.2. Direct binary search ==

We 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:

 * Generate an initial dithered image
 * Repeat until no changes can be applied:
   * Compute the global error between the original and the dithered images
   * For each pixel in the dithered image:
     * Compute the effect on the error of toggling the value of the current pixel
     * Compute the effect on the error of swapping the current pixel with one of its immediate neighbours
     * If the error can be reduced, perform the corresponding action

The 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.

Below 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:

[[Image(source:/web/trunk/www/study/out/lena4-2-1.png,class="inline",alt="direct binary search, iteration 0")]]
[[Image(source:/web/trunk/www/study/out/grad4-2-1.png,class="inline",alt="direct binary search, iteration 0 gradient")]]
[[Image(source:/web/trunk/www/study/out/lena4-2-2.png,class="inline",alt="direct binary search, iteration 1")]]
[[Image(source:/web/trunk/www/study/out/grad4-2-2.png,class="inline",alt="direct binary search, iteration 1 gradient")]]

[[Image(source:/web/trunk/www/study/out/lena4-2-3.png,class="inline",alt="direct binary search, iteration 2")]]
[[Image(source:/web/trunk/www/study/out/grad4-2-3.png,class="inline",alt="direct binary search, iteration 2 gradient")]]
[[Image(source:/web/trunk/www/study/out/lena4-2-4.png,class="inline",alt="direct binary search, iteration 5")]]
[[Image(source:/web/trunk/www/study/out/grad4-2-4.png,class="inline",alt="direct binary search, iteration 5 gradient")]]

Other HVS models can be used, giving very high quality results. Below are the results of DBS with the following HVS functions:

{{{
#!latex
$f_1(x,y) = e^{-\dfrac{x^2+y^2}{2}}$

$f_2(x,y) = e^{-\dfrac{x^2+y^2}{4.5}}$

$f_3(x,y) = e^{-\dfrac{x^2+y^2}{8}}$

$f_4(x,y) = 2e^{-\dfrac{x^2+y^2}{1.5}} + e^{-\dfrac{x^2+y^2}{8}}$
}}}

The 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:

[[Image(source:/web/trunk/www/study/out/lena4-2-5.png,class="inline",alt="direct binary search, sigma = 1, iteration 5")]]
[[Image(source:/web/trunk/www/study/out/grad4-2-5.png,class="inline",alt="direct binary search, sigma = 1, iteration 5 gradient")]]
[[Image(source:/web/trunk/www/study/out/lena4-2-6.png,class="inline",alt="direct binary search, sigma = 1.5, iteration 5")]]
[[Image(source:/web/trunk/www/study/out/grad4-2-6.png,class="inline",alt="direct binary search, sigma = 1.5, iteration 5 gradient")]]

[[Image(source:/web/trunk/www/study/out/lena4-2-7.png,class="inline",alt="direct binary search, sigma = 2, iteration 5")]]
[[Image(source:/web/trunk/www/study/out/grad4-2-7.png,class="inline",alt="direct binary search, sigma = 2, iteration 5 gradient")]]
[[Image(source:/web/trunk/www/study/out/lena4-2-8.png,class="inline",alt="direct binary search, best HVS, iteration 5")]]
[[Image(source:/web/trunk/www/study/out/grad4-2-8.png,class="inline",alt="direct binary search, best HVS, iteration 5 gradient")]]

== 4.3 Comparing dithering algorithms ==

Using 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.

The 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:

{{{
#!html
<table class="score" cellspacing="1">
  <tr><th>Chapter 1: Thresholding</th>
      <th>Error %<br />σ = 1</th><th>Error %<br />σ = 1.5</th><th>Error %<br />σ = 2</th></tr>
  <tr><td>0.5 thresholding</td>
      <td>8.60303</td><td>7.93554</td><td>7.42669</td></tr>
  <tr><td>0.4 thresholding</td>
      <td>9.78990</td><td>9.10994</td><td>8.61878</td></tr>
  <tr><td>0.6 thresholding</td>
      <td>10.77689</td><td>10.33373</td><td>10.00462</td></tr>
  <tr><td>dynamic thresholding</td>
      <td>10.31568</td><td>9.60749</td><td>9.09760</td></tr>
  <tr><td>uniform random dithering</td>
      <td class="hi">1.57895</td><td class="hi">0.69762</td><td class="hi">0.39713</td></tr>
  <tr><td>gaussian random dithering</td>
      <td>2.95590</td><td>2.34461</td><td>2.08792</td></tr>

  <tr><th>Chapter 2: Halftoning</th>
      <th>Error %<br />σ = 1</th><th>Error %<br />σ = 1.5</th><th>Error %<br />σ = 2</th></tr>
  <tr><td>25/50/75% patterns dithering</td>
      <td>0.56642</td><td>0.46490</td><td>0.41816</td></tr>
  <tr><td>2×2 Bayer dithering</td>
      <td>0.56694</td><td>0.46622</td><td>0.41956</td></tr>
  <tr><td>4×4 Bayer dithering</td>
      <td class="hi">0.20538</td><td>0.08060</td><td>0.05457</td></tr>
  <tr><td>8×8 Bayer dithering</td>
      <td class="hi">0.19691</td><td class="hi">0.06352</td><td class="hi">0.03354</td></tr>
  <tr><td>4×4 cluster dot dithering</td>
      <td>1.20026</td><td>0.14863</td><td>0.07100</td></tr>
  <tr><td>8×8 cluster dot dithering</td>
      <td>3.86236</td><td>0.85236</td><td>0.14443</td></tr>
  <tr><td>5×3 artistic line dithering</td>
      <td>2.75590</td><td>0.49420</td><td>0.11578</td></tr>
  <tr><td>perturbated 8×8 Bayer dithering</td>
      <td>0.40550</td><td>0.16971</td><td>0.09804</td></tr>
  <tr><td>random 3×3 dithering matrix selection</td>
      <td>0.60329</td><td>0.25055</td><td>0.16521</td></tr>
  <tr><td>“plus” pattern dithering</td>
      <td>0.43061</td><td>0.33540</td><td>0.29851</td></tr>
  <tr><td>“hex” pattern dithering</td>
      <td>0.26747</td><td>0.16119</td><td>0.13068</td></tr>
  <tr><td>“doubleplus” pattern dithering</td>
      <td>0.42852</td><td>0.12232</td><td>0.08904</td></tr>
  <tr><td>“hex2” pattern dithering</td>
      <td>0.35057</td><td>0.13046</td><td>0.09533</td></tr>
  <tr><td>4-wise supercell “plus” pattern dithering</td>
      <td class="hi">0.21903</td><td>0.07494</td><td>0.04423</td></tr>
  <tr><td>3-wise supercell “hex” pattern dithering</td>
      <td class="hi">0.21621</td><td>0.07356</td><td>0.04193</td></tr>
  <tr><td>4-wise supercell “doubleplus” pattern dithering</td>
      <td>0.40883</td><td>0.07051</td><td class="hi">0.03609</td></tr>
  <tr><td>6th order dragon curve dithering</td>
      <td class="hi">0.20503</td><td class="hi">0.06719</td><td class="hi">0.03539</td></tr>
  <tr><td>3-wise supercell “hex2” pattern dithering</td>
      <td>0.32643</td><td>0.07861</td><td>0.04061</td></tr>
  <tr><td>9-wise supercell “hex2” pattern dithering</td>
      <td>0.32336</td><td>0.07775</td><td>0.04087</td></tr>
  <tr><td>14×14 void-and-cluster dithering</td>
      <td class="hi">0.19726</td><td class="hi">0.06748</td><td class="hi">0.03663</td></tr>
  <tr><td>25×25 void-and-cluster dithering</td>
      <td class="hi">0.19248</td><td class="hi">0.06267</td><td class="hi">0.03325</td></tr>

  <tr><th>Chapter 3: Error diffusion</th>
      <th>Error %<br />σ = 1</th><th>Error %<br />σ = 1.5</th><th>Error %<br />σ = 2</th></tr>
  <tr><td>naïve error diffusion</td>
      <td>0.33352</td><td>0.06372</td><td>0.01961</td></tr>
  <tr><td>Floyd-Steinberg error diffusion</td>
      <td class="hi">0.09249</td><td class="hi">0.01847</td><td class="hi">0.00859</td></tr>
  <tr><td>serpentine Floyd-Steinberg error diffusion</td>
      <td class="hi">0.09891</td><td class="hi">0.01849</td><td class="hi">0.00749</td></tr>
  <tr><td>Jarvis, Judice and Ninke dithering</td>
      <td>0.27198</td><td>0.06257</td><td>0.03472</td></tr>
  <tr><td>Fan dithering</td>
      <td class="hi">0.10220</td><td class="hi">0.01728</td><td class="hi">0.00705</td></tr>
  <tr><td>4-cell Shiau-Fan dithering</td>
      <td class="hi">0.11618</td><td class="hi">0.01785</td><td class="hi">0.00660</td></tr>
  <tr><td>5-cell Shiau-Fan dithering</td>
      <td class="hi">0.11550</td><td class="hi">0.01950</td><td class="hi">0.00708</td></tr>
  <tr><td>Stucki dithering</td>
      <td>0.19765</td><td>0.05373</td><td>0.03012</td></tr>
  <tr><td>Burkes dithering</td>
      <td>0.15831</td><td>0.04014</td><td>0.02178</td></tr>
  <tr><td>Sierra dithering</td>
      <td>0.23498</td><td>0.05415</td><td>0.03011</td></tr>
  <tr><td>Sierra 2 dithering</td>
      <td>0.22249</td><td>0.05121</td><td>0.02812</td></tr>
  <tr><td>Filter Lite</td>
      <td class="hi">0.09740</td><td class="hi">0.01605</td><td class="hi">0.00638</td></tr>
  <tr><td>Atkinson dithering</td>
      <td>0.47209</td><td>0.31012</td><td>0.27339</td></tr>
  <tr><td>Riemersma dithering on a Hilbert curve</td>
      <td>0.28224</td><td>0.06529</td><td>0.02693</td></tr>
  <tr><td>Riemersma dithering on a Hilbert 2 curve</td>
      <td>0.26622</td><td>0.06003</td><td>0.02492</td></tr>
  <tr><td>spatial Hilbert dithering on a Hilbert curve</td>
      <td>0.27289</td><td>0.06124</td><td>0.02184</td></tr>
  <tr><td>spatial Hilbert dithering on a Hilbert 2 curve</td>
      <td>0.22821</td><td>0.05246</td><td>0.01911</td></tr>
  <tr><td>dot diffusion</td>
      <td>0.38301</td><td>0.08063</td><td>0.01918</td></tr>
  <tr><td>dot diffusion with sharpen = 0.9</td>
      <td>0.78546</td><td>0.34941</td><td>0.23479</td></tr>
  <tr><td>dot diffusion with sharpen = 0.9 and zeta = 0.2</td>
      <td>2.91287</td><td>2.19398</td><td>1.99858</td></tr>
  <tr><td>serpentine Floyd-Steinberg with sharpen = 0.9</td>
      <td>0.62615</td><td>0.30851</td><td>0.22111</td></tr>
  <tr><td>omni-directional error diffusion</td>
      <td>0.23860</td><td>0.06821</td><td>0.03498</td></tr>
  <tr><td>Ostromoukhov’s variable error diffusion</td>
      <td class="hi">0.11203</td><td class="hi">0.01772</td><td class="hi">0.00593</td></tr>
  <tr><td>nearest block matching with 2×2 line tiles</td>
      <td>1.92430</td><td>1.34822</td><td>1.13685</td></tr>
  <tr><td>block error diffusion with 2×2 line tiles</td>
      <td>0.86807</td><td>0.22411</td><td>0.08901</td></tr>
  <tr><td>block error diffusion with 3×3 artistic tiles</td>
      <td>1.78626</td><td>0.56957</td><td>0.23000</td></tr>
  <tr><td>block error diffusion with all 2×2 tiles</td>
      <td>0.56466</td><td>0.15910</td><td>0.06946</td></tr>
  <tr><td>block error diffusion with all 2×2 tiles and<br />weighted intra-block error distribution</td>
      <td>0.37738</td><td>0.10434</td><td>0.04643</td></tr>
  <tr><td>sub-block error diffusion with all 2×2 tiles</td>
      <td>0.14697</td><td>0.02605</td><td class="hi">0.00894</td></tr>
  <tr><td>sub-block error diffusion with 2×2 line tiles</td>
      <td>0.35759</td><td>0.06081</td><td>0.01855</td></tr>
  <tr><td>sub-block error diffusion with all 3×3 tiles</td>
      <td>0.32802</td><td>0.06516</td><td>0.02165</td></tr>
  <tr><td>sub-block error diffusion with 3×3 artistic tiles</td>
      <td>1.03963</td><td>0.21839</td><td>0.06678</td></tr>
  <tr><th>Chapter 4: Model-based dithering</th>
      <th>Error %<br />σ = 1</th><th>Error %<br />σ = 1.5</th><th>Error %<br />σ = 2</th></tr>
  <tr><td>DBS with HVS <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>, iteration 1</td>
      <td>0.25810</td><td>0.06780</td><td>0.03489</td></tr>
  <tr><td>DBS with HVS <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>, iteration 2</td>
      <td>0.13762</td><td>0.03234</td><td>0.01939</td></tr>
  <tr><td>DBS with HVS <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>, iteration 5</td>
      <td class="hi">0.10452</td><td>0.02745</td><td>0.01918</td></tr>
  <tr><td>DBS with HVS <i>e<small><sup> -(x²+y²)/2</sup></small></i>, iteration 5</td>
      <td class="hi">0.10344</td><td>0.03860</td><td>0.02669</td></tr>
  <tr><td>DBS with HVS <i>e<small><sup> -(x²+y²)/4.5</sup></small></i>, iteration 5</td>
      <td>0.18034</td><td class="hi">0.00984</td><td class="hi">0.00219</td></tr>
  <tr><td>DBS with HVS <i>e<small><sup> -(x²+y²)/8</sup></small></i>, iteration 5</td>
      <td>0.37804</td><td>0.02866</td><td class="hi">0.00295</td></tr>
  <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>
      <td class="hi">0.09838</td><td class="hi">0.00884</td><td class="hi">0.00263</td></tr>
</table>

<!--
DBS, sqrt:
  1.55543 0.68523 0.39111
  0.25810 0.06780 0.03489
  0.13762 0.03234 0.01939
  0.10452 0.02745 0.01918
DBS, sigma = 1:
  1.55543 0.68523 0.39111
  0.25379 0.09531 0.05629
  0.13447 0.04785 0.03057
  0.10344 0.03860 0.02669
DBS, sigma = 1.5:
  1.55543 0.68523 0.39111
  0.34373 0.05932 0.02545
  0.22412 0.01906 0.00560
  0.18034 0.00984 0.00219
DBS, sigma = 2:
  1.55543 0.68523 0.39111
  0.54240 0.09412 0.03133
  0.41340 0.04324 0.00804
  0.37804 0.02866 0.00295
-->
}}}