Bildformate / Kanal-Codierung

Ziel: Reduktion des Speicherbedarf

->Aber auch Encoding/Decoding-Zeiten beachten

Verlustfreie Kompression

• Anwendungen: Text-, Programm-, und Bildkompression

• kein Informationsverlust

• Ansatz: Effizientere Datenrepräsentation, Reduktion von Redundanzen etc.

• Bekannte Verfahren: Lauflängenkodierung, Huffman-Kodierung, Ziv-Welch-Algorithmus

• Bildformate: PNG, GIF, BMP, TIFF, RAW

Verlustbehaftete Kompression:

• Anwendungen: Bildkompression

• Informationsverlust

• Ansatz: Entfernen von unwichtigen, nicht wahrnehmbaren Informationen

• Bekannte Verfahren:

  • “Transform Coding”: Frequenzraumbasiert

  • Farbquantisierung

  • Farbunterabtastung

  • Fraktale Bildkompression

• Üblicherweise in Kombination mit verlustfreier Kompression

• Bildformate: JPEG, JPEG2000

Kompressionsrate:

• Wert durch den die unkompremierte Datenmenge zu dividieren ist, um die kompremierte Datenmenge zu erhalten

Kompressionsfaktor:

• Wert mit dem unkompremierte Datenmenge zu multiplizieren ist, um die komprimierte Datenmenge zu erhalten

Komprimierte Datenmenge:

• Gesamtheit aller notwendigen Informationen welche zur Datenkompression benötigt werden

  • z-B.: Komprimierte Information + Wörterbuch

BMP:

• primitive (verlustlose) Kompression über Lauflängenkodierung

• große Dateien

• schnelles Encoding (schnelle Verbindung, z.B. SSD, Ramdisk)

• Langsame Übertragung (z.B. Netwerk)

• einfache Implementierung

(für Hardware nahe Anwendungen)

• auch RLE (Run-Length-Encoding)

• Datenreduktion von sich (direkt) wiederholende Zeichen

• Kodierung nach (Anzahl, Wert)

• Lauflängencodierung im Spezialfall: Binär

• Bei vereinbartem Startzustand (z.B. Weiß): Kodierung der Anzahl an Bits bis Zustandswechsel

• Gute Eignung für flächige Bilder mit wenig Strukturen (z.B. SW Text: Fax-Kodierung)

Information: 558999999444

Komprimiert: 25186934

-> zuerst Wiederholungszähler, dann Pixel-Wert

• Datentransponierung beeinflusst Kompressionsrate

Portable Network Graphics

• fortschrittliche (verlustfreie) Kompression über mehrstufigen Kompressionsvorgang

  • Dekorrelation (Delta-Kodierung)

  • Substitutionskompression (ZIP)

  • Entropiekodierung (ZIP)

• kleien Dateien

• Langsames Encoding

• Schnelle Übertragung (z.B. Netwerk)

• Hohe Farbtiefe (z.b auch 16 Bit)

• Alpha-Kanal (für z.B. Transparenzen)

• Datenrepräsentation durch Differenzen zu Nachbarwerten

• Idee: Große (speicherintensive) Werte werden durch kleine (speichereffizientere) lokale Differenzwerte substituiert

• besonders effizient in Bereichen lokal geringer Unterschiede

• Häufig Vorverarbeitungsschritt für weitere Kompression

Information: 17 19 24 24 21 15

Kompremiert: 17 2 5 0 0 -3 -6

• Lempel-Ziv-Welch-Substitutionsalgorithmus

• Substitution (längerer Informationsfolgen) mit dynamischen Wörterbuch

• Vorteil: Wörterbuch wird automatisch aus der Information etnwickelt und muss nicht mit abgespeichert bzw. übergeben werden

• Decoder kann Wörterbuch aus kodiertem Datenstrom rekonstruieren

• Einsatz: PNG, TIFF, GIF

• Besonders effizient bei wiederholenden Mustern (Text)

• Kompressionsraten von Art und Struktur der zu verarbeitenden Datentypen abhängig

• Hohe Kompression für Datentypen mit vielen redundanten Informationen (Text, Programmcode, etc.)

• Wenig / keine Kompression für Floating-Arrays

1. Initialisiere das Wörterbuch so, dass es alle Zeichenketten der Länge eins enthält (Grauwertbild z.B. 0 bis 255)

2. Finde die längste Zeichenkette P im Wörterbuch, die mit der aktuellen Eingabe übereinstimmt

3. Gib den Wörtbuchindex für P an die Ausgabe aus und entferne P aus der Eingabe

4. Füge P, gefolgt vom nächsten Symbol S in der Eingabe, zum Wörterbuch hinzu

5. Gehe zu 2.

• Übergeordnete Klasse: Entropiekodierung

• Ansatz: Baumbasierte Datenrepräsentation über relative Häufigkeiten

  • Häufig verwendete Zeichen nahe der Baumkrone werden entsprechend über sehr kurzen Code repräsentiert

• Baumentwicklung: Bottum up (Blätter zur Wurzel)

• Umfang: Kodierte Daten + Codebuch

1. Bestimme für jedes Zeichen die Häufigkeit im Datensatz

2. Erstelle für jedes Zeichen einen Knoten mit Häufigkeit

3. Wiederhole bis alle Zeichen mit Baum verbunden:

   1. Fasse zu neuer Wurzel die Teilbäume mit geringster Häufigkeit zusammen

   2. Wurzelhäufigkeit des Teilbaums ist Summe der Teilwahrscheinlichkeiten

   3. Jeder Knoten wird über Binärzuordnung eindeutig beschrieben

• Verlustbehaftete Datenkompression über mehrstufigen Kompressionsvorgang

  • Downsampeling von Cb und Cr im YCbCr-Farbraum (verlustbehaftet)

  • Blockaufteilung und Tiefpass (verlustbehaftet)

  • Entropiekodierung (verlustfrei)

• Sehr kleine Dateien

• Schnelles Encoding

• Schnelle Übertragung (z.B. Netzwerk)

1. Schritt:

   • Farbraumumrechnung von (meist) RGB-Farbraum ins YCbCr-Farbmodell

   • Tiefpassfilterung und Unterabtastung der Farbigkeitssignale Cb und Cr

2. Schritt:

   • Quantisierung (Vernächlässigung der nicht signifikanten Frequenzen)

   • Aufteilung in Blöcke (8 x 8 px)

   • Für jeden Block eine DCT (Diskrete Kosinus Transformation) durchführen

   • Rundung auf quantisierbare Ganzzahl (Informationsverlust)

   • dynam. Weglassen “hoher Frequenzen” -> Reduktion der Datenmenge (Informationsverlust)

3. Schritt:

   • Huffman Datenkompression (Entropiecodierung)

• Y: Grundhelligkeit

• Cb: Blue-Yellow-Chrominance (Farbigkeit)

• Cr: Red-Green-Chrominance (Farbigkeit)

Ansatz:

• Subjektive Wahrnehmung:

  • Hoch bezüglich Helligkeitsunterschieden

  • Moderat bzg. Grün-Rot

  • Gering bzg. Gelb-Blau

• Kein Downsampeling von Y

• moderates Downsampeling von Cb

• starkers Downsampeling von Cr