How to use dithering to display an gray image with only black and white pixels?

Question

I have a 256 gray levels image, which I want to draw thanks to only #000 (black) and #FFF (white) pixels (nothing else).

One way to do that is to use dithering : https://upload.wikimedia.org/wikipedia/commons/6/6d/Dithering_example_red_blue.png

In such an algorithm, a sort of blur is made by increasing the number of pixels (white and black for me) in an area.

I don't know how to implement it however : how can I determine the number of pixels to represent the required level of gray ? Could you please write such an algorithm (use pseudocode for example, or Java, Scala, C, C++) ?

Answer 1

There are many different algorithms to create dithering, my favourite being random, it's simple to implement, it has no repeating patterns, and if you re-dither your image every frame then it all kind of averages out over time.

First of all an important and often neglected part is to convert your 256 gray levels from sRGB (gamma compressed) values to linear (gamma uncompressed) values, otherwise as in the examples in Wikipedia's Dither article your dithering image will be too bright. To do the conversion use a 256 entry look up table, and make the linear values go from 0 to 4095.

Then simply set your dithering using linear_value < (rand()&4095) ? 0 : 255, this works by having a random value between 0 and 4095 being compared against your linear value, giving you either a black or white pixel. So if you linear_value is let's say 3072 (very light gray), then 3 times out of 4 you'll get a white pixel, whereas with a value of 41 (dark grey), you'll get black 99 times out of 100.