
 

Image Compression
How many bits 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

For storing and transmitting high resolution images, compression algorithms are mandatory.
Many different approaches have been proposed in the literature. Most of them perform a tradeoff between image quality
and computing power requirements. In a large variety of scenarios, where images are coded once and used many times afterwards,
the time for compressing the image can be significantly longer than for decompression.
Examples are writeoncereadmany storage medias, like CDROM, image databases, the World Wide Web and many more.
In my PhD thesis I presented several asymmetrical compression algorithms for color, greyscale, and black & white images,
which take use of that property.

 

FASTQUANT
How to get present JPEG images on a CLUT device?
FASTQUANT allows for compressing colorreduced images using the JPEG standard.
Main contribution is an efficient coding scheme for 3dimensional voronoi diagrams of color spaces,
which enables realtime decompression of JPEGcompressed images on graphic systems with reduced colors.
This work was performed in cooperation with the Philips Research Laboratories in Siegen, Germany.
Details about FASTQUANT can be found in:
Andreas Schrader: Image Compression with JPEG (in German), Diploma Thesis,
University of Siegen, Germany, 1991.

 

Andreas Schrader and Friedrich Wittgruber
Fast Color Quantization of JPEG Images
Proceedings of the Second International Conference on Technical Informatics (CONTI 1996),
vol. 2 (Computer Science and Engineering), pp. 109116, Timisoara, Romania, November 1416, 1996.

 

Andreas Schrader and Friedrich Wittgruber
Fast Color Quantization of Compressed True Color Images
Proceedings of the International Conference on Robotics, Vision And Parallel Processing For Industrial Automation
(ROVPIA 1996), pp. 275280, Ipoh, Malaysia, November 2830, 1996.

 

EACCC
How to use evolutionary algorithms for compression?
The Color Cell Compression (CCC) algorithm is a BlockTruncation Coder for color images.
It uses the property of the human visual system, where lightness is more important than color information,
to create an efficient representation of color values in image blocks. The most important part of CCC is the
choice of an appropriated color table as a result of a color quantization process.
In the original version of CCC, MedianCut developed by Paul Heckbert in 1982 was used. But this algorithm is far from optimal.
I developed the EACCC as an evolutionary enhanced version of the CCC algorithm, where the EAQUANT algorithm is used to
determine optimal color tables. In addition, error tolerant mapping functions have been developed.
The EACCC outperforms the CCC algorithm significantly and allows very efficient and effective image compression.

 

Details about EACCC can be found in:
Andreas Schrader
Effective Mutation Operators for Genetic Color Quantization
1st FORMAT Workshop on Formal Languages and Automata Theory,
IFIP Working Group 1.2, Descriptional Complexity,
Siegen, Germany, May 23, 1997.

 

Andreas Schrader and Bernd Freisleben
EACCC  Evolutionary Algorithm Color Cell Compression
Proceedings of the International Conference on Imaging Science, Systems, And Technology
(
CISST'98),
pp. 175182, Las Vegas, Nevada, USA, July 69, 1998.

 

DFACOMPRESS
How to use finite automata for compression?
By interpreting an image as a regular language, we can use methods and theories both from formal languages and
automaton theory to find an efficient way of coding the respective finite automaton. Instead of transmitting
image sample values, the decoder can reconstruct the original image without any loss by using the same automaton.
The resulting DFACOMPRESS approach contains several heuristic approaches to produce a compact representation
of statetransitiontables. The results depend on the image content, but the superiority of the algorithms
was demonstrated in comparison with other wellknown lossless strategies, like LempelZiv and Huffman.

 

Details about DFACOMPRESS can be found in:
Andreas Schrader
Image Compression with finite Automatons (in german)
5th Workshop on Automatons and Formal Languages, German Informatics Society (GI)
Schloss Rauischholzhausen, Gießen, Germany, September 2829, 1995.
Theorietag, 1995.
Download
Paper.
See also Master Theses of Michael Zettler and Frank Katritzke (University of Siegen, 1994).

 

GENALLOC
How to optimize bit allocation in transform codecs?
Transform coders are very common mechanisms in current image compression algorithms (e.g. JPEG).
The most important part in transform coders is the quantization table as the only lossy part of the complete process.
Usually, ratedistortion theory is used to determine the number of quantizer bits for each frequency coefficient.
Unfortunately, the ratedistortion function rd() is only known as an approximation. We therefore developed
two approaches for determining the bitallocation matrix of the quantizer without using the rd()function.
GREEDYALLOC is a very fast heuristic using local optimal decisions to distribute the bits.
GENALLOC uses a genetic algorithm to determine a global optimum solution.
The superiority of both approaches has been demonstrated for a number of test images using the DCT transform.
Details can be found in the thesis of Oliver Peter: Optimized Quantization of Transform Coefficients with Genetic Algorithms
(in German, University of Siegen, 1996).

 

Details about all image compression algorithms above can be found in:
Andreas Schrader
Evolutionäre Algorithmen zur Farbquantisierung und asymmetrischen Codierung digitaler Farbbilder (in German)
Wissenschaftlicher Verlag Berlin, 1998.



