Imaging transform optimizes color displays

Developed in 1980 by Massachusetts Institute of Technology graduate student Paul Heckbert, the Heckbert algorithm has become the standard approach to allow large-pixel-depth images to de displayed using low-depth frame buffers (http://www.cs. cmu.edu/~ph). Under Nicholas Negroponte`s supervision, Heckbert hypothesized that certain image-quantization algorithms could map 24- to 8-bit images for display on low-cost display controllers. Heckbert demonstrated that most million-color images can be d

Apr 1st, 1997

Imaging transform optimizes color displays

Developed in 1980 by Massachusetts Institute of Technology graduate student Paul Heckbert, the Heckbert algorithm has become the standard approach to allow large-pixel-depth images to de displayed using low-depth frame buffers (http://www.cs. cmu.edu/~ph). Under Nicholas Negroponte`s supervision, Heckbert hypothesized that certain image-quantization algorithms could map 24- to 8-bit images for display on low-cost display controllers. Heckbert demonstrated that most million-color images can be displayed using only 256 or 512 colors with the now-standard Heckbert or median cut algorithm.

Heckbert`s work won critical acclaim and is used in the Macintosh operating system and Adobe Photoshop. Now, Steven Hickey of Inventions (Altrincham, Cheshire, England) has developed a faster algorithm that produces clearer images than the Heckbert transform. While developing a Heckbert-style palette for the company`s ILIB imaging software, Hickey noticed that the mechanism of the Heckbert palette algorithm was a special case of some general mathematics. As such, Hickey ended up with a faster algorithm that appears more like a 256-color image from the original 16 colors.

Hilary Roberts, director of marketing, says, "Just as a least squares straight line gives the minimum error from a set of data points, the Optimal palette gives the minimum error from a set of colors." Inventions include a special mathematical proof that shows that the Optimal palette image is better than the Heckbert-style image, that is, the difference between the colors it produces and the original is smaller than the difference between the colors the Heckbert produces and the original.

According to Hickey, "Images produced by the Optimal color palette are the best achievable because individual pixel values are the closest possible to those of the original image. Thus, the difference between the true color image and the reduced color image is minimal."

The basic uniform palette, the Heckbert palette, and the new Optimal palette are now part of the company`s ILIB image-processing software package, which has been used in a number of industrial applicatioans such as bottle inspection, print verification, and license-plate recognition. More information is available from Inventions; e-mail: ilib@inventions.u-net.com.

More in Boards & Software