Paul Heckbert’s Median Cut Approach

Heckbert’s median cut approach is a process that selects an optimum palette for direct color images. In contrast to the two previous approaches, median-cut output is image-dependent so that different images usually have very different palettes. The primary objective is democratic in that each palette entry theoretically represents the same number of image pixels. So, for images with 512 x 512 resolution, theoretically each palette entry represents (512 x 512)/256, or 1,024, image pixels. The process repeatedly subdivides the RGB cube into smaller and smaller rectangular spaces based on the equal representation principle.

The median-cut approach generally produces good results despite a few essential oversimplifications that favor performance. It consists of four steps:

1. Determining the original image’s pixel distribution
2. Selecting an optimum color map (palette) based on the first step
3. Mapping image pixels to the “nearest” palette entry
4. Assigning image pixel ranges to individual palette entries with optional error diffusion

To understand the process, first assume that an image has no primary blue intensity contribution present in any pixel so that the image consists of fully saturated colors consisting solely of red and green intensities. This reduces the palette selection to a two-dimensional exercise.

To determine the original image’s pixel distribution, plot each point on a chart that allows red and green values to range from zero to the maximum intensity, say 255. This produces the color image’s histogram (see Figure 15-1).

To select the optimum color map, subtract the maximum red value from the minimum red value and call the difference DeltaR. Similarly, subtract the maximum green value from the minimum green value and call the difference DeltaG. Suppose now that DeltaR is bigger than DeltaG— indicating the red component range is bigger than the green component range. Now determine the median red value—the value such that half the red values are above this value and half are equal to or less than this value. Drawing a horizontal line at this point splits the square into two rectangles.

Figure 15-1  Color image histogram (assumes blue contribution value is zero for each pixel)

Now, find which of the two rectangles has the largest component range for red or green and split that rectangle at the median point for the color component with the largest range. Now there are three rectangles. Each rectangle subdivision produces two rectangles from one, so each subdivision increases the total number of rectangles by one. Repeat this maximum red-green component range analysis procedure for all existing rectangles and median subdivision process until you have created as many rectangles as you have allotted palette entries.

Now, within each rectangle, average the red value for each pixel the rectangle contains and average the green value for each pixel the rectangle contains. This produces a weighted center-of-gravity pixel value for the rectangle which is a palette entry. Finally, assign each image pixel to one of the palette entries and diffuse the red-green errors to neighboring pixels.

The only process difference for images that contain all three color components is that the subdivision process is three-dimensional, involving rectangular volumes. Selecting what volume to divide into two rectangular volumes involves analyzing the ranges of the three color components for each existing rectangular solid and dividing at the median point. Anton Krueger’s thoughtful “Median-Cut Color Quantization” article and C language implementation is in Dr. Dobb’s Journal September 1994 issue on page 46.

Xiaolin Wu’s Optimal Color Quantization

Xiaolin Wu’s optimal color quantization divides the RGB color cube into rectangular solids like Heckbert’s median-cut method. However, the division criteria significantly differs. Wu’s approach calculates the center of gravity of each volume and the statistical variance of the color components around it. The subdivision occurs so that it minimizes the sum of the statistical variances for the color component with the maximum statistical variance within an existing volume, producing two new subvolumes.

The computational resources to calculate the division point are formidable, exceeded only by the complexity of Xiaolin Wu’s mathematics presented in his article titled “Efficient Statistical Computations for Optimal Color Quantization” in Graphics Gems II, page 126. Luckily, Dr. Wu makes a public domain implementation available which first quantizes color components to 32 intensity levels for computational efficiency. His version is for a Sun Microsystems workstation and has been significantly modified to adapt it to the PC.

Dr. Wu’s implementation uses several automatic 32x32x32 four-byte word arrays. Each such array requires 128 KBytes of memory. This exceeds available PC-DOS memory and coincidentally destroys the PC’s rather anemic stack, so this book’s implementation first quantizes color components to 16 intensity levels and uses 16x16x16 four-byte word static arrays. Unfortunately, this reduces the color gamut from Dr. Wu’s 32K possible colors to 12K possible colors. To quantize at 32 levels for non-PC-DOS implementations, simply change the COMPONENT_BIT_ DEPTH preprocessor identifier value to 5.

The sample WDS_QNT.C program in Chapter 17 contains the PC-adapted version of Dr. Wu’s original program.