| |
| | |
|
|
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.
|
| | |
|
GREEDYQUANT
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.
|
| | |
|
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.
|
| | |
|
EALABQUANT
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.
|
| | |
|
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.
|
| | |
|
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
|
| | |
|
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
|
|
|
|
