communityWir suchen ständig neue Tutorials und Artikel! Habt ihr selbst schonmal einen Artikel verfasst und seid bereit dieses Wissen mit der Community zu teilen? Oder würdet ihr gerne einmal über ein Thema schreiben das euch besonders auf dem Herzen liegt? Dann habt ihr nun die Gelegenheit eure Arbeit zu veröffentlichen und den Ruhm dafür zu ernten. Schreibt uns einfach eine Nachricht mit dem Betreff „Community Articles“ und helft mit das Angebot an guten Artikeln zu vergrößern. Als Autor werdet ihr für den internen Bereich freigeschaltet und könnt dort eurer literarischen Ader freien Lauf lassen.

Datenkompression PDF Drucken E-Mail
Benutzerbewertung: / 11
SchwachPerfekt 
Geschrieben von: Stefan Behm   
Donnerstag, den 02. Januar 2014 um 17:20 Uhr
Beitragsseiten
Datenkompression
Huffman-Codierung
Alle Seiten

Einführung

Die Datenkompression oder Datenkomprimierung ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Die Vorteile der Datenkomression liegen auf der Hand. Dieselben Daten können mit erheblich weniger Speicherkapazität persistiert werden. Die Datenübertragung wird verkürzt und Ressourcen können eingespart werden. So ebnete das MP3-Format den Weg zum Austausch von Musik über das Internet. Das Verfahren zur verlustbehafteten Kompression digital gespeicherter Audiodaten wurde Anfang 1990 bekannt und ermöglichte eine Einsparung der benötigten Speichergröße um den Faktor 10, gegenüber dem bis dato verwendeten WAV-Format, bei nicht oder nur kaum verringerter wahrgenommener Audioqualität.

Bei der Datenkompression ist man primär an einem sog. Codiergewinn interessiert, der sich als Differenz aus der Darstellung der Information gegenüber einer alternativen Darstellung der gleichen Information ergibt. Man spricht von einem Codiergewinn, wenn sich die alternative Darstellung als effizienter (kürzer) erweist, als die ursprüngliche Darstellung der Information. Grundsätzlich wird bei der Datenkompression versucht, überflüssige Information zu entfernen. Dazu werden die Daten in eine Darstellung überführt, mit der sich alle – oder zumindest die meisten – Informationen in kürzerer Form darstellen lassen. Diesen Vorgang übernimmt ein Kodierer und man bezeichnet den Vorgang als Kompression oder Komprimierung. Die Umkehrung bezeichnet man als Dekompression oder Dekomprimierung.

Fundamentalprinzipien der Datenkompression

Die Datenkompression bzw. Datenreduktion ist nur aufgrund zweier fundamentaler Prinzipien möglich. Das Erste ist die Entfernung von Redundanz (Kompression) i.e.S. und das Zweite ist die Entfernung von Irrelevanz (Reduktion) aus einer beliebigen Informationsquelle. Der Unterschied zwischen Kompression und Reduktion liegt bei näherer Betrachtung auf der Hand: Bei der Kompression (i.e.S) bleiben die Originaldaten nach der Abbildung (Kompressionsvorgang) vollständig rekonstruierbar und im Sinne einer Rückabbildung erhalten. Mathematisch formuliert spricht man von einer bijektiven Abbildung. Bei der Datenreduktion hingegen sind die Originaldaten nach dem Abbildungsvorgang nicht immer fehlerfrei rekonstruierbar. Das bedeutet, es kommt zu einem Fehler zwischen den Originaldaten und den rekonstruierbaren Daten. Eine Rückabbildungsvorschrift ist zwar vorhanden, diese ist jedoch nicht in der Lage, sämtliche Originaldaten einwandfrei wieder herzustellen.

Redundanzreduktion

Als redundant bezeichnet man umgangssprachlich Informationen oder Daten, die sich aufgrund bereits überlieferter/übertragener Informationen durch Deduktion ableiten lassen. Es ist demnach nicht notwendig diese sog. redundanten Daten gesondert, zusätzlich oder überhaupt zu übertragen. Redundanz beschreibt den Grad der Vorhersagbarkeit von Teilen einer Nachricht und ist durch die Entropie festgelegt.

Die Redundanz innerhalb einer Nachricht/Information lässt sich mathematisch exakt bestimmen. Es ist trotzdem weder mit beliebigem technischem oder mathematischem Aufwand möglich eine größere Menge an Redundanz aus einer Nachricht zu entfernen, als die Nachricht enthält. Es sei denn man verfälscht die ursprüngliche Nachricht oder nimmt bewusst Fehler in der rekonstruierten Nachricht in Kauf.

Die Vermeidung von Redundanz erfolgt mit den Methoden zur verlustfreien Datenkompression. Bei der verlustfreien Datenkompression geht es darum, die zu übertragende Nachricht durch eine kürzere aber äquivalente Nachricht zu ersetzen, sie anschließend zu übertragen und auf der Seite des Empfängers fehlerfrei zu rekonstruieren. Bei der Codierung unterscheidet man statistische, Wörterbuch-basierende und kombinierte Ansätze.

Irrelevanzreduktion

Als irrelevant bezeichnet man Informationen oder Daten, die vom Beobachter bzw. Empfänger nicht wahrgenommen werden können oder deren Genauigkeit nicht hinreichend wahrnehmbar ist. Als schlechtes Beispiel könnte man einen Rot/Grün-Blinden wählen, der bekanntlich schwer zwischen Rot und Grün unterscheiden kann. Durch die fehlende Unterscheidbarkeit beim Empfänger würde es bspw. ausreichen, wahlweise den Rot oder den Grün-Anteil zu übertragen. Das heißt man benutzt physiologische Grundlagen, Gegebenheiten und Modelle um zu entscheiden, ob eine Information eine Übertragung wert ist oder nicht. Das MP3-Format nutzt die Irrelevanzreduktion, indem sie Frequenzen ausfiltert, die normalerweise vom menschlichen Gehör nicht wahrgenommen werden können.

Bei der Irrelevanz ist es mittels technischer oder mathematischer Modelle möglich, relevante Informationen von irrelevanten Informationen zu trennen. Meist müssen dazu komplexe Modelle, Messmethoden oder empirische Werte gefunden werden, anhand derer die Entscheidung vorgenommen werden kann, ob eine Information relevant oder irrelevant ist. Dabei spielen insbesondere objektive und subjektive Kriterien eine Rolle.

Darüber hinaus ist es möglich, nicht nur nicht hinreichend wahrnehmbare Informationen zu unterschlagen, sondern bewusst auch wahrnehmbare Fehler in Kauf zu nehmen, um so die zu übertragende Information an die Art der Codierung anzupassen. Der Vorteil der Anpassung an die Art der Codierung besteht darin, dass der Codierer entscheiden kann, welche Modifikation während der Codierung zu einer besseren Kompressionsleistung führen. Der Codierer erzeugt durch die Modifikation sog. Kompressionsartefakte, die es dem Codierer möglich machen eine vorgegebene Kompressionsrate zu erreichen oder zu unterschreiten. Die Verfahren mit denen diese Art der Codierung erreicht werden kann, werden im Kapitel Verlustbehaftete Kompression behandelt.

Verlustfreie oder verlustbehaftete Datenkompression

Grundsätzlich unterscheidet man zwischen verlustfreier oder verlustbehafteter Datenkompression. Man spricht von verlustfreier Kompression (oder verlustfreier Kodierung), wenn aus den komprimierten Daten wieder alle Originaldaten gewonnen werden können. Das ist beispielsweise bei der Kompression ausführbarer Programmdateien notwendig.

Bei der verlustbehafteten Kompression können die Originaldaten nicht mehr aus den komprimierten Daten zurückgewonnen werden, das heißt ein Teil der Information ging verloren. Solche Verfahren werden häufig zur Bild- oder Videokompression und Audiodatenkompression eingesetzt.

datenkompression

Datenkompression in der Informationstheorie

Es gibt eine Vielzahl von Beispielen, anhand derer gezeigt werden kann, dass die verlustfreie oder verlustbehaftete Datenkompression sinnvoll sind. Die Datenkompression ist eng mit der Informationstheorie, wie sie von Claude Shannon im Jahr 1948 formuliert wurde, verbunden. Die Informationstheorie und die Informationstheoretischen Ansätze haben nach über 50 Jahren der Existenz derart viele Bereiche berührt, dass die moderne Informatik und Informationstechnik nicht ohne diese theoretische Abhandlung denkbar wären. Heute geht es mehr denn je, um die Speicherung und Verarbeitung digitaler Daten und es ist völlig egal in welche Richtung man blickt. Die moderne Medizin kommt heute nicht ohne bildverarbeitende Methoden aus. Nachdem die Information digital wurden, suchte man nach Möglichkeiten sie auch digital zu übertragen, digital zu speichern und digital zu verarbeiten. Erst dadurch gelang es Informationen digital und somit verlustfrei zu verarbeiten oder zu kopieren.

Nachdem die Information digital aufgezeichnet werden konnte, wollte man erfahren, wie viel Information tatsächlich in einer Nachricht steckt. Diese Frage ist sowohl von philosophischem, als auch von ingenieurstechnischem Interesse. Die ingenieurstechnischen Fragen beantwortete Claude Elwood Shannon (Vater der Informationstheorie) mit seiner berühmt gewordenen Arbeit "A Mathematical Theory of Communication". Sie wurde 1949 unter dem Titel "The Mathematical Theory of Communication" leicht erweitert und erneut veröffentlicht.

Information: der negative Kehrwert der Wahrscheinlichkeit.

Die Informationstheorie gibt durch den Informationsgehalt eine minimale Anzahl an Bits vor, die zur Kodierung eines Symbols benötigt werden. Dabei ist die Entropie ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte einer Nachricht. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt.

Je kleiner die Auftrittswahrscheinlichkeit eines Zeichens ist, desto höher ist seine Information. Andersherum ist die Information eines Zeichens gering, wenn es oft vorkommt. Eine niedrige Entropie bedeutet, dass es mehr redundante Informationen gibt und es lassen sich somit gute Kompressionsraten erzielen. Aus einer niedrigen Entropie kann man auf regelmäßige Strukturen in der Nachricht schließen. Umgekehrt gilt: ist die Entropie hoch, so sind weniger redundante Informationen in der Nachricht enthalten und sie lässt sich nur schlecht komprimieren. Die Entropie kann somit als Maß dafür gewertet werden, wie gut sich eine Datenquelle für eine Kompression eignet. Die Entropie spielt auch bei der Generierung von Zufallszahlen und der Verschlüsselung von Daten eine zentrale Rolle. Sie ist auch der Grund, warum beispielsweise verschlüsselte Daten in der Regel nicht mehr effektiv komprimiert werden können.

Nach über 50 Jahren der Informationstheorie gibt es keinen Bereich, der nicht von der Informationstheorie berührt worden ist und es gibt keinen Bereich, der sich früher oder später nicht mit der Codierung und Kompression von Daten bzw. Informationen beschäftigen muss.

Anwendung entwickeln

In diesem Artikel wird die Entropiekodierung zur verlustfreien Datenkompression vorgestellt. Die Entwicklung der Software vollzieht sich in mehreren Schritten. Zunächst werden Klassen zur Serialisierung von Daten entworfen. Anschließend wird die Huffman-Kodierung in C++ implementiert. Am Ende werden die Teilschritte in eine fertige Anwendung integriert, die die Komprimierung von beleibigen Dateien ermöglicht.

Serialisierung von Datentypen

In der Informatik bezeichnet die Serialisierung im Kontext der Datenspeicherung und Datenübertragung den Prozess der Konvertierung von Datenstrukturen oder Objekten in ein Format, das persistent gespeichert oder über ein Netzwerk übertragen werden kann um anschließend in derselben oder einer anderen Umgebung wieder „genutzt“ zu wer-den. Die Serialisierung ist eine Abbildung von Objekten auf eine sequenzielle Darstellung. Wenn die sequenziellen Bits wieder nach dem Objektserialisierungsformat gelesen werden, ist es möglich einen semantisch identischen Klon des Originalobjekts zu erzeugen.

Die Umkehrung der Serialisierung, bei der ein Datenstrom in ein Objekt konvertiert wird, heißt Deserialisierung.

Objektserialisierung

Bei der Entwicklung einer Anwendung zur Datenkomprimierung steht eine konsistente Serialisierung von Objekten im Vordergrund. So müssen nicht nur primitive Datentypen komprimiert werden, sondern auch Bilder und andere komplexe Datenquellen. Anders als beispielsweise JavaTM, unterstützt die Programmiersprache C++ direkt keine Objektserialisierung. Basierend auf dem Qt-Framework werden deshalb zunächst Streaming-Klassen entworfen. Diese Klassen ermöglichen die Serialisierung von Daten zu einem so genannten IODevice. Der binäre Datenstrom ist zu 100% unabhängig von dem laufenden Betriebssystem, sowie unabhängig von der Byte-Reihenfolge der CPU. Die Klassen stellen Methoden für die Serialisierung der grundlegenden C++-Datentypen bereit, wie char, short, int, double, etc. Die Serialisierung von komplexen Datentypen wird durch die Nutzung der primitiven Datentypen realisiert und über die friend-Funktionalität von C++ ermöglicht.

Ziel ist es ein leistungsfähiges Serialisierungmodul zu entwickeln, das zum einen mit allen wesentlichen Datentypen umgehen kann, dabei eine einfach zu bedienende API bereitstellt und bei Bedarf jederzeit erweitert werden kann. Die API, sowie der Aufbau der Datenströme orientiert sich dabei an JavaTM.

Byte-Reihenfolge

Werden Daten bitweise seriell übertragen, so ist die Bit-Reihenfolge festzulegen. Die sogenannte Byte-Reihenfolge oder auch Byte-Order bezeichnet die Speicherorganisation für einfache Zahlenwerte, in erster Linie die Ablage von ganzzahligen Werten im Arbeitsspeicher. Die Festlegung des zu verwendenden Speicherungsformats ist immer dann nötig, wenn zur Codierung der zu speichernden Zahl mehr Bits erforderlich sind, als in der kleinsten adressierbaren Einheit zur Verfügung stehen. Im Regelfall ist die kleinste adressierbare Einheit auf modernen Computerarchitekturen ein Byte bzw. acht Bit. Die Speicherung einer Zahl erfolgt nun, falls hierfür mehr als ein Byte benötigt wird, in mehreren Bytes, so dass diese in den Speicheradressen direkt aufeinander folgen.

Die heute existierenden Varianten der Byte-Reihenfolge beschränken sich fast ausschließlich auf zwei Varianten, „Big-Endian“ und „Little-Endian“, sowie eine Misch-form „Middle-Endian“ beider Varianten.

endianess

In Tabelle sind die drei wichtigen Byte-Reihenfolgen samt Adresse dargestellt. Das Format Little-Endian wurde ursprünglich bei den Intel-x86-Prozessoren verwendet. Dagegen wurde das Big-Endian-Format beispielsweise bei der Motorola beziehungs-weise Coldfire-Familie, sowie Sun-SPARC-CPUs und dem PowerPC eingesetzt. Das Betriebssystem Windows verwendet auf jeder Hardware das Format Little-Endian. Das betrifft x86, x86-64, Alpha, PowerPC, MIPS und Itanium Hardware-Architekturen. Unter Linux ergibt sich ein diversifiziertes Bild. Während Linux für die gängigen Systeme x86 und x86-64 ebenfalls Little-Endian einsetzt, wird z. B. auf einem MIPS, SPARC, PA-RISC, POWER, PowerPC, oder Xtensa auf Big-Endian zurückgegriffen. Das Betriebssystem von Apple, das Mac OS X, verwendet nur noch für den alten PowerPC das Format Big-Endian. Auch die gewöhnliche Darstellung von Dezimalzahlen ist – im Sinne der Leserichtung der meisten europäischen Sprachen von links nach rechts – Big Endian. In der Industrie, sowie auf diversen Plattformen hat sich aber zunehmend Little-Endian durchgesetzt. Sowohl Linux als auch Windows verwenden heute auf modernen x86 und x86-x64 Plattformen Little-Endian, so dass für gewöhnlich die Daten in diesem Format im Speicher abgelegt sind.

Die grundlegenden Unterschiede zwischen Little-Endian und Big-Endian sind:

  • Unter Little-Endian wird das Byte mit den niederstwertigen Bits (engl. least significant bit) an der kleinsten Speicheradresse gespeichert beziehungsweise das kleinstwertige Element zuerst genannt.
  • Unter Big-Endian wird das Byte mit den höchstwertigen Bits (engl. most signi-ficant bit) zuerst gespeichert, das heißt an der kleinsten Speicheradresse. Das bedeutet, dass Daten mit dem größtwertigen Element zuerst genannt werden.

Zahlen werden in Programmiersprachen, wie C++, in der Regel im Format Little-Endian geschrieben. Die Zahl beginnt mit den höchstwertigen Bits und endet mit den niederstwertigen Bits (Leserichtung von links nach rechts). Die interne Darstellung folgt allerdings exakt der umgekehrten Richtung. Das LSB steht am Anfang im Speicher, während das MSB den Schluss markiert.

byte-order

Vor der Übertragung von Datentypen, die mehr als ein Byte im Speicher beanspruchen, wird im Protokoll von der Klasse Endian zunächst die Byte-Reihenfolge des laufen-den Betriebssystems ermittelt. Die Klasse verfügt darüber hinaus über ein Template mit dem Namen ReverseByteOrderImpl. Mit dem Template kann die Byte-Reihenfolge von diversen Datentypen umgekehrt werden. Um die Performance zu stei-gern wurden für die ersten 8 Byte insgesamt vier Template-Spezialisierungen generiert, die über direkte Bit-Manipulationen die Byte-Reihenfolge ändern.

Die Klasse „Stream“

Grundlage für die Serialisierung aller Datentypen ist ein kontinuierlicher Datenstrom. Der Datenstrom oder auch Stream, bezeichnet kontinuierliche Abfolgen von Datensätzen, deren Ende nicht im Voraus abzusehen ist. Die einzelnen Datensätze sind dabei von beliebigem, aber festem Typ. Da fast alle Systeme heute ein Byte als minimalen Datensatz verwenden, bestehen die Abfolgen meist aus einzelnen Bytes. Datenströme werden häufig zur Interprozesskommunikation verwendet.

Der Entwurf der Stream-Klassen beginnt in der Regel bei dem Fundament. Oftmals wird auch zwischen Eingabe- und Ausgabe-Streams unterschieden. Aus diesem Grunde ist es sinnvoll eine abstrakte Basisklasse zu entwerfen, die sowohl für die Ein- als auch für die Ausgabe Methoden und Felder bereitstellt. Die Klasse Stream ist so eine Klas-se. Sie stellt insgesamt sechs virtuelle Methoden zur Verfügung. Darunter befinden sich Methoden zur Festlegung der Byte-Reihenfolge, als auch eine Methode zur Ermittlung der Größe des Datenstroms. Weiterhin werden die Enumeratoren Version und ByteOrder exponiert. Der erste Enumerator dient dazu bei Versionsübergängen Funktionalitäten unterscheiden zu können um beispielsweise eine Abwärtskompatibilität zu gewährleisten. Der zweite Enumerator legt die Byte-Reihenfolge des Datenstroms fest. Die Klasse Stream bildet die Basis für alle I/O-Unterklassen.

Der nächste Schritt besteht darin den Eingabe- und Ausgabe-Streams aufzuspalten. Dazu werden die beiden abstrakten Klassen InputStream und OutputStream entwickelt. Beide Klassen besitzen mehrfache Überladungen für unterschiedliche Datentypen und implementieren die Basisklasse Stream. Die Überladungen sind durch die Methoden read() für Eingabe-Streams und write() für Ausgabe-Streams implementiert. Weiterhin wurde für die Datentypen der operator>> bzw. operator<< überladen. Beide Klassen überladen ebenfalls die C++ String-Klassen.

/**
  * @brief Base interface class for all input streams.
  *
  * Applications that need to define a subclass of InputStream 
  * must always provide a method that returns the next byte of input.
  *
  * @author CodePlanet
  * @date 30.12.2013 
  * 
  * @version 0.1 
  * Comments added (Doxygen).
  */
class InputStream : public Stream
{
public:
    ////////////////////////////////////////////////////////////
    /// Functions to read data from the stream
    ///
    ////////////////////////////////////////////////////////////
    virtual void read(bool&               data, uint32_t bit = Bits<bool>::size       ) = 0;
    virtual void read(char&               data, uint32_t bit = Bits<char>::size       ) = 0;
    virtual void read(int8_t&             data, uint32_t bit = Bits<int8_t>::size     ) = 0;
    virtual void read(uint8_t&            data, uint32_t bit = Bits<uint8_t>::size    ) = 0;
    virtual void read(int16_t&            data, uint32_t bit = Bits<int16_t>::size    ) = 0;
    virtual void read(uint16_t&           data, uint32_t bit = Bits<uint16_t>::size   ) = 0;
    virtual void read(int32_t&            data, uint32_t bit = Bits<int32_t>::size    ) = 0;
    virtual void read(uint32_t&           data, uint32_t bit = Bits<uint32_t>::size   ) = 0;      
    virtual void read(int64_t&            data, uint32_t bit = Bits<int64_t>::size    ) = 0;
    virtual void read(uint64_t&           data, uint32_t bit = Bits<uint64_t>::size   ) = 0;       
    virtual void read(float&              data, uint32_t bit = Bits<int32_t>::size    ) = 0;
    virtual void read(double&             data, uint32_t bit = Bits<int64_t>::size    ) = 0;
    //virtual void read(const char*         data, uint32_t bit = Bits<int8_t>::size     ) = 0;
    //virtual void read(const wchar_t*      data, uint32_t bit = Bits<int16_t>::size    ) = 0;
    virtual void read(std::string&        data, uint32_t maxLength                    ) = 0;
    virtual void read(std::wstring&       data, uint32_t maxLength                    ) = 0;
    virtual void read(void*               data, uint32_t length                       ) = 0;
 
    virtual int32_t read(char* b, uint32_t off, uint32_t len) = 0;
 
    ////////////////////////////////////////////////////////////
    /// Operator >> overloads to read data from the stream
    ///
    ////////////////////////////////////////////////////////////
    virtual InputStream& operator>>(bool&               data) = 0;
    virtual InputStream& operator>>(char&               data) = 0;
    virtual InputStream& operator>>(int8_t&             data) = 0;
    virtual InputStream& operator>>(uint8_t&            data) = 0;
    virtual InputStream& operator>>(int16_t&            data) = 0;
    virtual InputStream& operator>>(uint16_t&           data) = 0;
    virtual InputStream& operator>>(int32_t&            data) = 0;
    virtual InputStream& operator>>(uint32_t&           data) = 0;
    virtual InputStream& operator>>(int64_t&            data) = 0;
    virtual InputStream& operator>>(uint64_t&           data) = 0;
    virtual InputStream& operator>>(float&              data) = 0;
    virtual InputStream& operator>>(double&             data) = 0;
    //virtual InputStream& operator>>(const char*         data) = 0;
    //virtual InputStream& operator>>(const wchar_t*      data) = 0;
    virtual InputStream& operator>>(std::string&        data) = 0;
    virtual InputStream& operator>>(std::wstring&       data) = 0;
 
    struct true_type  { enum { value = true  }; };
    struct false_type { enum { value = false }; };
 
    template <typename T>
    void do_read(T& data, uint32_t bit, const false_type&) 
    {
        read(data, bit);
    }
 
    template <typename T>
    void do_read(T& data, uint32_t bit, const true_type&) 
    {
        int32_t temp;
        read(temp, bit);
        data = static_cast<T>(temp);
    }
};

ByteArrayInputStream und ByteArrayOutputStream

Die konkreten Implementierungen werden durch die beiden Klassen ByteArrayInputStream und ByteArrayOutputStream dargestellt. Beide Klassen realisieren ihre Basisklassen und operieren auf Datenströmen der Größe ein Byte oder 8-Bit. Instanziiert werden beide Klassen mit einem Objekt vom Typ IODevice oder direkt mit einem ByteArray.

In dem nachfolgenden Listing ist ein Beispiel für die Nutzung einer der beiden Klassen zu sehen:

ByteArray arr;
ByteArrayOutputStream bos(&arr); 
bos.setByteOrder(ByteArrayOutputStream::LittleEndian); 
int a = 0x52535455; 
bos << a; 
std::string str = "hello"; 
bos << str;

Die Klasse ByteArray repräsentiert im Wesentlichen einen STL-Container mit dem Datentyp char. In der zweiten Zeile kapselt die Klasse ByteArrayOutputStream eine Instanz von ByteArray. Nachdem die Byte-Reihenfolge gesetzt wurde, können beliebige Datentypen in den Ausgabestrom serialisiert werden.

Das ByteArray ermöglicht einen wahlfreien Zugriff (engl. random access) indem die Klasse ByteArrayOutputStream das Array intern in einem so genannten Buffer schachtelt. Ein Buffer implementiert die virtuellen Methoden von einem IODevice. Prinzipiell können von der Klasse ByteArrayOutputStream alle Quellen beschrieben werden, die ein IODevice realisieren. So ist es möglich auch zu einem Socket oder einer Datei zu schreiben.

Die Serialisierung der String-Klassen aus der STL geschieht dadurch, dass in den Datenstrom zu Beginn die Anzahl der nachfolgenden Zeichen geschrieben werden. Bei der Deserialisierung kann auf diese Weise der komplette Zeichenstrom rekonstruiert werden, indem zuerst die Anzahl der Zeichen gelesen werden und anschließend die Zeichen selbst. Zu beachten ist das beide Seiten dieselbe Byte-Reihenfolge verwenden müssen, d.h. es muss im selben Format geschrieben und gelesen werden. Weiterhin muss das in exakt derselben Abfolge geschehen. Wurde zuerst ein Integer geschrieben, so muss auf der Gegenseite auch zuerst ein Integer gelesen werden. Diese logische Tatsache ergibt sich aus dem Aufbau des sequenziellen Datenstroms. Sowohl der Client, als auch der Server nutzen für die Serialisierung direkt das Protokoll, so dass keine weiteren Maßnahmen notwendig sind. Das Protokoll kapselt die Serialisierung der Datentypen in Objekten, die direkt gesendet und empfangen werden können.

Datenkompression

Nachfolgend soll die Datenkompression erläutert werden. Den Vorgang der Datenkompression übernimmt ein Kodierer oder Kompressor. Die Umkehrung bezeichnet man als Dekompression oder Dekomprimierung, welche durch den Dekodierer bzw. Dekompressor vorgenommen wird.

coder-cncoder

Zur Komprimierung von Bildern stehen unterschiedliche Techniken zur Verfügung. In der Regel nutzen Bildformate standardisierte Kompressionsalgorithmen, deren Reduktion sich an den physiologischen Wahrnehmungseigenschaften des Menschen orientieren. Neben JPEG existieren unter anderen die Formate PNG, GIF oder BMP. JPEG schlägt diverse Komprimierungs- und Kodierungsmethoden vor, darunter verlustbehaftete und verlustfreie Komprimierung. Im Gegensatz zur verlustbehafteten Kompression, geht bei der verlustfreien Kompression keine Information verloren. Die Daten werden lediglich reorganisiert, indem bestimmte Redundanzen erkannt und zusammengefasst werden. Verlustbehaftet wird die Kompression oder Kodierung genannt, wenn sich die Daten im Allgemeinen nicht fehlerfrei rekonstruieren lassen. In der Tabelle wird die gebräuchliche JPEG-Norm dargestellt.

jpeg-norm

Verlustbehaftete JPEG-Verfahren können mithilfe moderater Tiefpassfilterung zur Farbreduktion zum Beispiel durch einen Algorithmus zur DCT-Transformation das Datenvolumen um mehr als 90% reduzieren. Der Preis für die starke Datenkomprimierung ist allerdings ein realer Verlust von Daten. Zudem kommt es durch die Eigenart der auf einer Fouriertransformation basierenden Datenkompression zu einer Bildung von Arte-fakten im Bild, auch als Gibbssches Phänomen bezeichnet. Dieses Phänomen basiert darauf, dass die Funktion der Partialsumme xN (t) bei einem Rechtecksignal in der Nähe der Unstetigkeitsstelle eine Welligkeit aufweist, deren Amplitude mit größer werdenden N nicht abnimmt. Bei einer Unstetigkeit mit der Höhe Eins hat die Partialsumme einen Wert von 1.09 (d.h., ein überschwingen um 9% der Unstetigkeitsstelle) unabhängig davon, wie groß N ist.

Gibbsches Phänomen

Betrachtet man die Partialsummen der Funktionen mit Sprungstellen, zeigt sich, dass diese Summen an den Sprungstellen gegen das arithmetische Mittel der Funktionswerte rechts und links der Unstetigkeitsstellen von x0 konvergieren.

formula-1

Jede Partialsumme mit genügend großem, aber endlichen n zeigt bei Rechtecksignalen in der Umgebung ihrer Sprungstellen ein Über- und Unterschwingen um jeweils 9 % der Sprunghöhe. Die Bildung von Artefakten wird auch als „Ringing“ bezeichnet und verschwindet erst bei der unendlichen Fourierreihe. Entwickelt man eine Fourierreihe aus einer unstetigen Funktion, so ergeben sich an den Unstetigkeitsstellen typische Über- und Unterschwinger, die sich auch dann nicht verringern, wenn man versucht, die Funktion noch besser zu approximieren. Dies liegt daran, dass die Reihe an der Unstetigkeitsstelle nicht mehr gleichmäßig, sondern nur punktweise konvergiert.

Die Höhe des Überschwingers in einer Richtung lässt sich bestimmen:

formula-2

Daraus ergibt sich ein prozentueller Fehler von insgesamt 17,898 %, gerundet 18 %, der Sprunghöhe.

Für Bilder bedeutet dieser Umstand, dass es an scharfen Farbübergängen, die gleichbedeutend mit Unstetigkeitsstellen sind, zu einer sichtbaren Unschärfe bei der Datenkompression kommt. Dies wird bei entsprechender starker Kompression und Vergrößerung des Bildausschnitts besonders ersichtlich und sind als Alias-Effekte bekannt.

aliasing-artifact

Als Alias-Effekte (auch Aliasing-Effekte oder kurz Aliasing) werden im Bereich der Signalanalyse Fehler bezeichnet, die auftreten, wenn im abzutastenden Signal Frequenzanteile vorkommen, die höher als die Nyquist-Frequenz (halbe Abtastfrequenz) sind.

Um ein Bild korrekt und eindeutig wieder rekonstruieren zu können, muss deshalb eine verlustfreie Kompression verwendet werden. Die verlustfreie Kompression kann allerdings bei hohem Rauschanteil in einem Bild nur eine ungenügende Kompression erzielen. Aus diesem Grund finden verlustlose digitale Kompressionsformate wie etwa das BMP-Format fast nur in der professionellen Fotografie und Bild-Gestaltung ihre Anwendung.



Zuletzt aktualisiert am Freitag, den 03. Januar 2014 um 01:18 Uhr
 
AUSWAHLMENÜ