1

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++) ?

JarsOfJam-Scheduler
  • 2,809
  • 3
  • 31
  • 70
  • 2
    look at this http://stackoverflow.com/a/36820654/2521214 just use only palette consisting from 2 colors black and white ... – Spektre Dec 31 '16 at 10:01

1 Answers1

3

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.

Michel Rouzic
  • 1,013
  • 1
  • 9
  • 22
  • 2
    Congratulations on recognizing the importance of converting from gamma corrected levels, I was ignorant of that problem for many years. While random dithering is dirt simple, it can be slow (because random number generation is slow) and deliver ugly results. I prefer Floyd-Steinberg myself, or one of its many variants. For the difference between pure random noise and high frequency noise see http://math.stackexchange.com/questions/2136099/restore-range-and-uniform-distribution-to-modified-random-numbers – Mark Ransom Feb 10 '17 at 21:12
  • 3
    Mark don't you remember? You saw my technique for doing it fast almost 4 years ago :D http://stackoverflow.com/questions/15793747/how-to-best-display-30-bpp-graphics-on-a-24-bpp-display/15793794#15793794 – Michel Rouzic Feb 11 '17 at 00:15