The Palette-Optimization Algorithm

The program that Cognitive Applications wrote to extract optimum 8-bit color mappings from 24-bit scans of paintings employed a published algorithm by Hekbert, while commercial products like Adobe Photoshop use closely related algorithms. The algorithm is topological in nature, working on the proximity of colors in a 3-D color space.

First, you must resolve all the 24-bit pixels that make up a single scan (around 300,000 of them in the case of a 640- by 480-pixel image) into their 8-bit RGB components. You can then plot each pixel to a color point in the 3-D 24-bit RGB color cube, as shown in the figure "Plotting Pixels in the RGBColor Cube."

Now sort the R, G, and B components to determine their maximum and minimum values and use these limits to "shrink" the color cube down to the smallest rectangular box in RGB space that will contain all the pixels.

You split this box into two smaller boxes along its longest axis and repeat the shrinking process on these smaller boxes. The main loop of the algorithm repeats this process of choosing a box to split, splitting it, and then shrinking the fragments, adding one new box at each iteration. Variations on the algorithm can use different criteria to select which box to split and how to split it. In general, you choose the biggest box to split, and split it to yield two equal parts. Size might be measured by the number of color points the box contains, or by the total number of pixels, since many pixels may have mapped to the same color point. Similarly, equality might refer to equal numbers of color points, pixels, or even simply equal volumes of the color space.

After 256 iterations of this process, you'll have 256 bins into which the color content of the original scanned picture has been distributed as evenly as possible by whichever criterion you used. T he optimal palette now consists of the color held in each of these final boxes. In general, each box will contain more than one color point, so you need a third selection function to pick just one; it might be the point closest to the center of the box, or an average weighted for the number of actual mapped pixels.

This algorithm gives a "fair" representation of the color distribution in a given picture, but in practice, absolute fairness may not be desirable. A human expert might prefer to sacrifice some colors and emphasize others to better suit the content and meaning of the painting, matters of which the algorithm can know nothing.

---

Figure: Plotting Pixels in the RGB Color Cube Cyan (0,255,255) Blue (0,0,255) Pixels plotted as points in RGB space Green (0,255,0) Algorithm finds smallest set of boxes that enclose all the color points. Magenta (255,0,255) White (255,255,255) Red (255,0,0) Yellow (255,255,0)