Andreas Schrader - Research


	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 trade-off 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 write-once-read-many storage medias, like CD-ROM, 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 color-reduced images using the JPEG standard. Main contribution is an efficient coding scheme for 3-dimensional voronoi diagrams of color spaces, which enables real-time decompression of JPEG-compressed images on graphic systems with reduced colors. This work was performed in co-operation 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. 109-116, Timisoara, Romania, November 14-16, 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. 275-280, Ipoh, Malaysia, November 28-30, 1996.

	EACCC How to use evolutionary algorithms for compression? The Color Cell Compression (CCC) algorithm is a Block-Truncation 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. 175-182, Las Vegas, Nevada, USA, July 6-9, 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 state-transition-tables. The results depend on the image content, but the superiority of the algorithms was demonstrated in comparison with other well-known lossless strategies, like Lempel-Ziv 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 28-29, 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, rate-distortion theory is used to determine the number of quantizer bits for each frequency coefficient. Unfortunately, the rate-distortion function rd() is only known as an approximation. We therefore developed two approaches for determining the bit-allocation 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.

Image Compression