Refinements of data compression using weighted finite automata

Abstract

Der effizienten Speicherung und Übertragung von Bildern kommt in den letzten Jahren verstärkte Bedeutung zu, etwa bei Multimedia- oder WWW-Anwendungen. In den letzten Jahren haben sich Anwendungen wie Internet-Browser oder Multimedia-Lexika bedeutend ausgebreitet. Die dabei übertragenen und gespeicherten Bilder nehmen selbst in komprimierter Form mit gängigen Bildkompressionsverfahren wie GIF oder JPEG einen großen Teil des benötigten Speicherplatzes ein. Aus diesem Grund beschäftigt man sich weiterhin intensiv mit der Kompression von digitalisierten Bildern. Die Entwicklung solcher Kompressionsverfahren verlief dabei sowohl über verlustlose Verfahren wie Lempel-Ziv- und Huffman-Kodierung, als auch verlustbehaftete Verfahren wie Vektorquantisierung und Transformationskodierung. Zu den verlustbehafteten Kodierungsverfahren gehören auch die sogenannten fraktalen Kodierer, bei denen sich insbesondere Kodierer für iterierte Funktionensysteme (iterated function system, IFS) als auch die gewichteten endlichen Automaten (weighted finite automaton, WFA) hervorgetan haben. Die meiste Aufmerksamkeit gilt dabei den IFS-Kodierern, soweit man das an der Anzahl der dedizierten Literatur ablesen kann. Um dieses Ungleichgewicht zumindest geringfügig zurechtzurücken, wird in dieser Arbeit das Gewicht auf die Erfoschung der Methode der WFA-Kodierung gelegt. Dazu wurde ein moderner WFA-Kodierer namens AutoPic entwickelt und implementiert, um die Frage nach der Brauchbarkeit der WFA-Kodierung in der Praxis zu beantworten.

The efficient storage and transmission of digital images is gaining increasing interest, for example in multimedia and WWW applications. Pictures require a huge amount of storage capacity even in compressed form (as GIF or JPEG). For this reason, many researchers study the area of digital image compression extensively. The development of compression algorithms evolved from lossless techniques such as Lempel-Ziv and Huffman coding to lossy techniques such as vector quantization and transform coding. One of the major techniques for state of the art image compression is the fractal-based technique. One version of these are based on iterated function systems (IFS) wich have drawn by far the most attention as far as one can tell from the amount of dedicated literature. Other fractal-based techniques are the codecs based on weighted finite automata (WFA) which have been neglected by most researchers. In order to slightly correct this bias, this thesis concentrates on the topic of image coding with WFAs. We have implemented a state of the art WFA coder called AutoPic to answer the question whether WFA coding is suitable in practice.