Random dithering of images

I wanted to wrap a rectangular texture of, say, the earth around a sphere in Minecraft to make a 3D image (using RaspberryJamMod and Python). The problem was that my color palette would be limited to Minecraft blocks, and not all blocks would be appropriate--with my son's help, I selected a subset of 82 that would work well for general purpose image rendering. So I needed to reduce the color in the texture. One could just choose the nearest color available for each point in the image, but that would lose a lot of detail. The standard family of techniques to solve this is dithering. However, most dithering algorithms like Floyd-Steinberg or ordered dithering are designed for flat two-dimensional images.

One could come up with a 3D version of one of these algorithms, but I went for a different tack: random dithering. Random dithering isn't much used these days, because it is thought to produce really bad results. But while that would no doubt be true with a two-color palette, it doesn't seem to be true with a larger palette, like my Minecraft 82 block palette. The method I used was to add to each color channel a random perturbation, with distribution either uniform or a cut-off Gaussian, and the results were gratifying. Not quite as good as Floyd-Steinberg, but close.

The original is on the right. "Gaussian X/Y" means a perturbation with sigma X, cut off at -Y and Y. "Uniform X" means a perturbation uniform over the interval [-X,X].

And here's how it looks wrapped on an egg (uniform 20, I think):

Actually, on this cartoon stuff, the dithering is hardly needed. A photograph benefits more from the dithering. It's a dung beetle I photographed outside of our house some years ago.

Original:

Minecraft renderings:









In both cases, uniform 20 and Gaussian 20/30 seem good enough. Source code here.