Ordered dithering explanation

ordered_dithering.txt

(Written as a way to stop forgetting these things. 
May be wrong sometimes, as it's just the result of my research here and there. 
If it helps you, give me a shout!)   

Ordered dithering is a technique used to reduce - deliberately! - the precision of an image.
Motivation : artistic (mainly ?), color quantization --> reduce the number of color in an image

----------------------------------------------------------------
INTRODUCTION

The idea behind it is simple : given two available values a and b, let's say black and white,
the value x between a and b - that should be grayish - is simulated by mixing pixels of colors a and b.
To apply some ordered dithering on an image, we apply the same logic but in 2D by using a bayer matrix.
By turning the pixel on in a very specified order, the matrix creates the perception of 
continuous variation of color.

Here an example of a variaton for a 2x2 matrix :

■ ■ | □ ■ | □ ■ | □ □ | □ □ 
■ ■ | ■ ■ | ■ □ | ■ □ | □ □ 

----------------------------------------------------------------
BAYER MATRIX

Dither matrix are power-of-2 matrix whose elements can be considered as threshold.
In these matrices, consecutive threshold values are located far apart spatially, 
which gives the perception of a progressive variation. 
The values inside the matrix indicate how likely a pixel will be turned on.
You can rotate, mirror, transpose these matrices and it won't bring much change to the dithered image.

----------------------------------------------------------------
HOW TO CONSTRUCT A DITHER MATRIX ?

      - By hand --> become quickly fastidious but is perfect to understand how the matrix works

The simplest - yet useless - dither matrix is the zero matrix  of dimension 1x1, 
this one doesn't apply any transformation. So yeah, useless.

On the oher hand, the 2x2 matrix is fundamental : 
| 0 2 |
| 3 1 |
Given that this matrix contains 4 differents values, we will see only 4 kinds of pattern in the dithered image. 
To reach better image quality, we need to use bigger matrices. Let's compute the 4x4 matrix recursively :

Step1 4x4:
| 0  -  2  - |
| -  -  -  - |
| 3  -  1  - |
| -  -  -  - |
 
Step2 4x4:
| 0  -  2  - |
| -  4  -  6 |
| 3  -  1  - |
| -  7  -  5 |
 
...and so on... we just follow the pattern on the 2x2 case.
The first step to obtain the 8x8 is the following : 
 
Step1 8x8:
| 0  -  8  -  2  - 10  - |
| -  -  -  -  -  -  -  - |
|12  -  4  - 14  -  6  - |
| -  -  -  -  -  -  -  - |
| 3  - 11  -  1  -  9  - |
| -  -  -  -  -  -  -  - |
|15  -  7  - 13  -  5  - |

      - Using the recursive formula :

Now that we done this little prep work, it is easy to deduce the induction relation defining these matrices

M(2n) = | 4 * M(n) + 0      4 * M(n) + 2 |
        | 4 * M(n) + 3      4 * M(n) + 1 |
for all n>=1

----------------------------------------------------------------
HOW TO APPLY ORDERED DITHERING ON AN IMAGE ?

Here we are gonna focus on black&white ordered dithering.
The dither matrix is tiled across the image. The bigger the matrix is, the better it will look.
For each pixel of the image to modify, look up the member of the matrix covering it.
Then we use the matrix as a threshold mask : 
if the value of the pixel is superior to the one given by the matrix, the pixel is lit, if not it becomes black.

----------------------------------------------------------------
Done !