Chapter 15
Color Image Quantization

What This Chapter is About

Color image quantization is the process that selects a set of primary color mixtures to represent an image’s color gamut. In this book, it is the process that reduces 15-, 16-, and 24-bit direct color images to similar appearing images that usually contain 256 or fewer carefully selected RGB combinations. This chapter discusses two popular statistical pixel distribution analysis techniques that determine the best 256 RGB combinations for individual image palettes.

The first, known as Paul Heckbert’s median cut method, is a simplistic approach that depends on an image’s pixel statistical distribution and often yields acceptable results. The second approach, developed by Xiaolin Wu of the University of Western Ontario in London, Ontario, Canada, trades computational speed for greater image fidelity using more rigorous mathematical methods. Until Xiaolin Wu developed and published his ingenious computational shortcuts, the general approach was generally considered too computationally intensive for personal computers.

Uniform Quantization Introduction

Direct color images with 15, 16, and 24 bits describing each pixel are increasingly common. However, older, legacy display controllers typically only display 256 RGB combinations at a time. So, it is advantageous to develop strategies and approaches that transform direct color images into palettized images containing 256 RGB combinations or fewer. The process of distilling direct color image pixel information into members of a much smaller, fixed-size palette is referred to as color quantization.

Color quantization usually generates images with 256 (or fewer) colors. This allows 8 (or fewer) bits to identify the RGB combination for every pixel. This pixel information reduction provides natural compression that conserves image storage capacity and transmission bandwidth. It also allows image hue, saturation, and intensity manipulations that involve the few palette RGB combinations rather than each individual pixel within an image, allowing the manipulations to appear virtually instantaneous.

Finally, transmission bandwidth conservation is also important in multimedia video applications which often quantize individual video frame pixel information into 128 RGB combinations. This allows successive frames to alternate between palette entries zero to 127 on one frame and 128 through 255 on the next, and so on. Careful palette manipulation between successive frame display eliminates undesirable color flashing that might occur when pixel palette entries are incorrect for the current or previous frame.

The RGB24TO8.C Program

The RGB24TO8.C program illustrates two naive, straightforward, image-independent, uniform color quantization approaches and their unsatisfactory results. For each palette entry, the first approach assigns palette entry bit positions. For each of the 256 palette entries, the three high-order bits specify the red intensity, the middle three bits specify green intensities, and the two low-order bits specify blue intensities. This allows red and green intensities independently to assume eight different intensities each while blue intensities only assume four intensities which can introduce contouring in blue gradient areas.

The SetR3G3B2Palette() function initializes the palette by distributing the individual primary RGB components’ intensities uniformly (red and green use intensity values 0, 32, 64, 96, 128, 160, 192, and 224 while blue uses intensity values 0, 64, 128, and 192) and gamma correcting the resulting palette.

The program could use other schemes rather than uniform distribution, but the selected strategy is expedient. While fast, the arbitrary primary color intensity assignment leaves the palette unable to display white since the RGB (255, 255, 255) triad is absent. To display direct color image pixels, the R3G3B2() function captures the appropriate number of high-order bits for each primary color component and shifts them into a byte in the proper pixel byte position as follows:

This produces recognizable palette-adapted images that exhibit noticeable contouring or posterization.

The second approach RGB24TO8.C uses assigns numbers of uniformly distributed primary color intensities rather than palette entry bit positions. The selected approach in function SetMorphsPalette() uses seven uniformly distributed intensities for red, nine for green, and four for blue. This assigns 252 color combinations (7 x 9 x 4), using palette entries zero through 251.

However, the assignment again omits white as well as any gray values since the uniform distributions are all different, only sharing the value zero in common. Because the eye is so sensitive to achromatic deviation errors, the remaining four intensity assignments for palette entries 252 through 255 are (60, 60, 60), (120, 120, 120), (180, 180, 180), and (240, 240, 240), respectively, which provide some achromatic gray values.

From the color space discussion, the RGB cube is a three-dimensional space. To select the appropriate palette representation for each image pixel, the program computes the straight-line three-dimensional distance from each image pixel to each palette entry using the Pythagorean theorem and determines which palette entry is geometrically closest. The program assigns the first pixel it finds with the shortest distance as the representative palette entry.

Despite the improved number of green intensities, displayed images still exhibit detectable contours and the geometric distance calculation dramatically slows image rendering despite heavy look-up table use to avoid repetitive square calculations. An excellent reader exercise would involve calculating the error caused by inexact pixel assignments and distributing the error to neighboring pixels using an error diffusion algorithm. This dramatically improves many image renderings.