Dither a Grayscale Image
GraphicsMagick/ImageMagick

Ordered Dither:

magick B2DBy.jpg -gamma .45455 -ordered-dither [all] 4x4 ordered4x4g45.pbm


Before complaining about my using an "established algorithm" please read the ChangeLog for GraphicsMagick and ImageMagick for April 2003 where you'll see that I implemented the algorithm in those applications.  Also, the combination of "-gamma .45455" with "-ordered-dither" is new.

The "-gamma .45455" takes care of the image being too light.  The "all" parameter is only needed with GraphicsMagick.

There's banding because there are only 17 graylevels in a 4x4 ordered-dither image.
The appearance of banding can be reduced by using an 8x8 ordered-dither which has 65 levels.

Here are the original image, the 4x4 and 8x8 ordered dithered output and the random-threshold output:


I prefer the ordered-dither version, but am including the random-threshold version for completeness. 

magick B2DBy.jpg -gamma .6 -random-threshold 10x90% random-threshold.pbm


The "10x90%" means to render below 10 percent intensity pixels as pure black and above 90 percent as pure white, to avoid having a few lonely specks in those areas.

It's probably worth noting that both are as memory-efficient as they can possibly be.  Neither does any diffusion, so they work one pixel at a time, even when writing ordered-dither blocks, and don't need to know anything about the neighboring pixels.  ImageMagick and GraphicsMagick process a row at a time, but it's not necessary for these methods.  The ordered-dither conversions take less than .04 second real time on my old x86_64 computer.