Lectures Research Publications Vitae Contact

Color Quantization

How many colors does an image need?
 Ubiquitous Computing
 Ubiquitous Media
 Hybrid Libraries
 Museum Technology
 Pervasive Games
Color Quantization
 Image Compression
 Quality of Service
 Intelligent Internet Services
 Seamless Media Adaptation

 Supervised Theses
Modern digital image facilities, such as advanced scanners or video digitizers produce true color images, where each pixel is given by a triple of color coordinates in an appropriate chosen color space, like RGB, CIE, etc. However, in order to visualize true color images on CLUT (Color Lookup Table) – oriented graphical devices with a reduced number of simultaneously displayable colors (e.g. in mobile phones, PDAs, Laptops, etc.), a color quantization process is required. Since color quantization is an NP-hard optimization problem, only suboptimal heuristic approaches with quite different objectives and results have been proposed. In my PhD thesis, I developed a new evolutionary approach. EAQUANT is based on a hybrid combination of an explorative evolutionary algorithm and an explorative standard local search algorithm (K-MEANS). Since color quantization can be considered as a special case of cluster analysis, the EAQUANT approach was compared to other deterministic clustering algorithms (agglomerative, divisive, partitive) and found to be superior. This superiority was also shown in relation to other probabilistic optimization techniques, like random search, hill-climbing, iterated local search and neural nets. In the EALABQUANT approach, the approach was adopted to the human visual system by incorporating uniform color spaces, dithering algorithms and subjective image quality measures.

How to get some good colors as fast as possible?
The motivation behind GREEDYQUANT was to develop a very fast, but still good initialization method for the EAQUANT color quantization algorithm. Instead of searching all the image colors, a first prequantization with 6 bit accuracy is performed. Random pixels are selected until about 5000 different colors are collected into a color 3-dim. histogram. Afterwards, a kd-tree is constructed for a random color table. The color space of the histogram is fully partitioned by determining the nearest neighbor in the color table. The algorithm is now calculating for each color table entry the respective color of the histogram, causing the largest error. In case, the overall error can be reduced, the table entry is reduced by these histogram value. The exchange process is repeated, until none of the table entries can be modified anymore. The GREEDYQUANT algorithm is extremely fast and performs surprisingly well. The runtime complexity is of O(K |H| + K log(K)) with K: number of colors in table, H: histogram. GREEDYQUANT performs better than many well-known color quantization algorithms, including MEDIAN-CUT by Paul Heckbert. Although it does not give the best error values compared to more sophisticated algorithms like TRUE VARIANCE or PRINCIPAL AXIS, it can be considered as one of the fastest algorithms available. In addition it has the advantage of avoiding regular structures in regular image patterns, which often lead to reduced visual quality regardless of optimized MSE values.

Original EAQUANT
How to get very good colors using natural processes?
EAQUANT is is a color quantization algorithm based on the hybrid combination of an evolutionary algorithm (EA) and a standard local search strategy (K-means). The EA is responsible for exploring the search space and the local search algorithm is used to find a local minimum. Therefore you can consider EAQUANT to be an evolutionary algorithm with a limited search space consisting of local minima or a heuristic approach of iterated local search, where the re-initialization is optimized evolutionary. EAQUANT is a postclustering algorithm operating on a population of individuals, each representing a color lookup table (CLUT). GREEDYQUANT is used to build an initial population of 8 CLUTs, which has been identified as the optimal population size in a large number of experiments. Replacement is realized using the Deterministic Rank Based Sampling method from evolutionary strategies in combination with exclusive collection of individuals avoiding copies in the same population. Uniform Crossover is combined with a new developed Component Convex Hull Mutation of individual color components. In the beginning, crossover is used exclusively. After convergence, only mutation is used. We call this the ONESWITCH strategy. A dynamic combination of prequantization and subsampling is used to increase the efficiency without degradation of quality. In extensive tests with large image sets, EAQUANT has been proven to be the most effective color quantization algorithm available.

How to trick the eye with false colors?
The above mentioned EAQUANT algorithm operates in the RGB color space, which has some limitations for the visual quality of the quantization process, since it is not optimized for the human perception system. EAQUANT uses the uniform 1976 CIEL*a*b* color space. In general, we could transform every image color from the original RGB space into CIEL*a*b* before quantization. But an efficient alternative is given by only performing distance calculations in the uniform color space and remain all individual representations in RGB. This is useful, since RGB has to used in the final output. The EALABQUANT algorithm has been compared with other well-known color quantization algorithms (e.g. PRINCIPAL AXIS) and showed significant superiority. Drawback is a decreased performance due to the complex distance calculations in CIEL*a*b*. The subjective results of uniform quantized images is not necessarily more convincing and depends on the overall number of colors in the image and their distribution in the color space.
PhD Thesis Details about the color quantization algorithms can be found in:
Andreas Schrader
Evolutionäre Algorithmen zur Farbquantisierung und asymmetrischen Codierung digitaler Farbbilder (in German)
  Wissenschaftlicher Verlag Berlin, 1998.
ICEC_1997 Bernd Freisleben and Andreas Schrader
An Evolutionary Approach to Color Quantization
Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC'97) Indianapolis, Indiana, USA, April 14-17, 1997, pp. 459-464
IPA_1997 Bernd Freisleben and Andreas Schrader
Color Quantization with a Hybrid Genetic Algorithm
Proceedings of the Sixth IEE International Conference on Image Processing and its Applications (IPA'97) Dublin, Irland, July 14-17, 1997, pp. 89-93
© 2003 Andreas Schrader & Martin Heike