Dither a Grayscale Image Dither a grayscale image into pure black and white with your own algorithm.

Guidelines: You must come up with your own new algorithm. You cannot use pre-existing algorithms (ex. Floyd-Steinburg) but you can use the general technique. Your program must be able to read an image and produce an image the same size. This is a popularity contest, so whoever produces the best (closest to original) and most creative (determined by votes) wins. Bonus if the code is short, though this is not necessary. 

You can use whatever grayscale image you want as input, it should be larger than 300x300. Any file format is fine. 

Example input: 



Example output:



This is a pretty good job, but there still are visible lines and patterns.
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.