Do We Really Need 24-bit Color?

When I was paining in childhood, I only have 24 colors, and somethings I only buy 4 colors to use (i.e., red, green, blue and white). However, blending of all colors could create vivid pictures.

1f140bdadb5ad6ea8342e4a5a5cb8011

(image from pininterest)

On the other side, the storage of digital colors in computer can be very expensive: for each pixel, we need 256*256*256 = 16M to store just a single pixel.

How to reduce that? Color quantification is very useful in computer graphics, image compression and the visual web. However, traditional color quantification suffers from ugly blocks.

Dithering_example_undithered Dithering_example_undithered_16color_palette

(Image from Wikipedia)

I learnt image compression from iq’s wavelet compression.

I got some great results but I am not satisfied with using the entire color space. So how shall we go further?

Initially, people do color quantization by population algorithm / method, which essentially constructs a histogram of equal-sized ranges and assigns colors to the ranges containing the most points.

A more modern popular method is clustering using octrees. The most popular algorithm by far is the median cut algorithm.  Voronoi diagram is used to decompose the color cube.

Another useful library is scolorq: A Spatial Color Quantization Utility

In this post, I would like to introduce Floyd–Steinberg dithering, which is a very inexpensive way to generate vivid pictures using only a few colors. An example can be seen from the trailer image. And here is the comparison:

1 Floyd–Steinberg-dithering

(image taken by myself)

Almost no difference, eh?

Floyd–Steinberg dithering is an image dithering algorithm first published in 1976 by Robert W. Floyd and Louis Steinberg. It is commonly used by image manipulation software, for example when an image is converted into GIF format that is restricted to a maximum of 256 colors. The algorithm achieves dithering using error diffusion, meaning it pushes (adds) the residual quantization error of a pixel onto its neighboring pixels, to be dealt with later. It spreads the debt out according to the distribution (shown as a map of the neighboring pixels):

Here is a working code in C++ for Floyd–Steinberg dithering, I modified from StackOverFlow:

 

Reference:

1. An Overview of Color Quantization Techniques