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 !

I cant understand how you had made matrices can you explain deeply..........Thanks

Not sure if this is still needed, but from what I figured so far, matrix with the shape of 2^n * 2^n will be continuously divided into quadrants until the smallest quadrant can be represented with the original 2 * 2 matrix, with each quadrant maintaining it's previous values.

For instance, if you have a matrix:
| 0...2 |
| 3...1 |

and expand it to 4*4 matrix imagine it as
| 0...2...0...2 |
| 3...1...3...1 |
| 0...2...0...2 |
| 3...1...3...1 |

, the original values replace "0" value in respective quadrant and other values will remain unknown at the moment, as such:
| 0...x...2...x |
| x...x...x...x |
| 3...x...1...x |
| x...x...x...x |

the next value to be filled in is 4 and as such is our "step" for incrementing following values. These next values will be filled in following the patter of the original 2 * 2 quadrant (0,3,2,1) with a formula x = value_caried_over_to_that_quadrant + step_value * positional_value ; where positional_value is the respective value in the 2 * 2 matrix. So, for the top left quadrant of the 4 * 4 matrix you'd have
| 0................................ x = 0 + 4 * 2 |
| x = 0 + 4 * 3..........x = 0 + 4 * 1 |

so you can see that the top left quadrant will now be:
| 0......8 |
| 12...4 |

if you continue filling in the rest of the values you'll end up with:
| ...0......8.....3...11 |
| 12......4...15.....7 |
| ...2...10.....1......9 |
| 14......6...13.....5 |

Mind you, expanding this into 8 * 8 matrix will results in each 2 * 2 portion having a value from 4 * 4 matrix in it's 0 positions, so the four
2 * 2 grids on on the top of the grid will have 0,8,3,11 in their 0 positions respectively, like such:
| 0...x.........8...x.....3...x......11...x |
| x...x.........x...x......x...x.........x...x |

Hope this helps.

about the above example
| 0................................ x = 0 + 4 * 2 |2................................ x = 2 + 4 * 2 |
| x = 0 + 4 * 3..........x = 0 + 4 * 1 |x = 2 + 4 * 3..........x = 2 + 4 * 1 |
| 3................................ x = 3 + 4 * 2 |1................................ x = 1 + 4 * 2 |
| x =3 + 4 * 3...........x = 3 + 4 * 1 |x = 1 + 4 * 3...........x = 1 + 4 * 1 |

if
| ...0......8.....3...11 |
| 12......4...15.....7 |
| ...2...10.....1......9 |
| 14......6...13.....5 |

need to fix to

| ...0......8....12...10 |
| 12......4...14.....6 |
| ...3....11....1......9 |
| 15.....7....13.....5 |

I can understand the article you share, and I know how to build the dither matrix
But, I still amazing why the quantization pixel information can realize the fake scale
Could you share the original thinking or theory
why the threshold
M(2n) =
| 4 * M(n) + 0 4 * M(n) + 2 |
| 4 * M(n) + 3 4 * M(n) + 1 |
can really success to do the image processing of the fake scale to cheat people's eyes?

and

if I don't want to only use two levels(0, 255) to quantize the color image, I hope to quantize the image maybe using six scales(ex 0, 51, 102, 153, 204, 255)
like this wikipedia
https://en.wikipedia.org/wiki/Colour_banding

how to process the specified table to the image, could you share your thinking, thanks
I hope to try to test the thinking by python

Hey there, I've been working my head around dithering for a long time as well, and have gone quite a bit into understanding it.
First of all for the dithering of more than 2 shades.(black and white) i suggest applying the threshold matrix to the colour and then setting that new colour to the closest colour in your range of colours. so if you need 6 shades you can do something like:

colour = colour + (threshold_at_xy/threshold_array_size)*(255/shades)

where shades= 6

you divide threshold_at_xy by the size of the array to have it normalize, or in other words be between 0 and 1. Then you multiply it by 255/number_of_shades to push the value closer to one or other shade
then you get the closest shade from your pallet of 6 shades by:

colour = colour-mod(colour, 255/shades)

this way colour is either 0, 51, 102, 153, 204, 255

you can do the same with not just shades but colours, just apply the same process to each r, g, b values.

Now for the reason why this is, if i understand correctly the threshold matrix is basically a gradient towards all directions, as it has all the shades in that range, spaced out equally. that way when you process one shade(which is not in the particular pallet) in that matrix, it either pushes it towards a lighter shade or a darker shade. This means, there would be more lighter pixels and less darker pixels, in a shade which is closer to a lighter shade and further from the darker shade (where the shade you want to use is in between those two shades).
In other words, if you have a 50% grey shade, then there would be equally black and white pixels arranged in a checkerboard pattern you can see in the threshold. going lighter, there would appear more white pixels and less black pixels.

I hope this helps you understand it more. Although i tend to explain this very unclearly. If you have any questions you can write to me, I'd gladly answer them.