Image and Video Compression - Cheatsheet

Theorie der Informationsentropie

Definition:

Maß für den Informationsgehalt in einer Nachricht. Häufig verwendet zur Bewertung der Effizienz von Kodierungsverfahren.

Details:

• Entropie (H) einer Zufallsvariable X: \[H(X) = - \sum_{i=1}^n P(x_i) \log_b P(x_i)\]
• \(P(x_i)\): Wahrscheinlichkeit des Auftretens des Symbols \(x_i\)
• Einheit der Entropie: Bits (\(b=2\)) oder Nat (\(b=e\))
• Je höher die Entropie, desto größer die Unvorhersehbarkeit der Nachricht
• Wichtige Konzepte: Informationsverlust, Redundanz, Effizienz

Huffman-Kodierung

Definition:

Huffman-Kodierung ist ein verlustfreies Kompressionsverfahren, das häufig in der Bild- und Videokompression verwendet wird.

Details:

• Erstellt bitoptimale Präfixcodes für ein Alphabet basierend auf Häufigkeiten.
• Algorithmus: Häufigkeiten zählen, binären Baum erstellen, Codes generieren.
• Kürzere Codes für häufigere Symbole, längere für seltenere.
• Kodiertabelle und dekodierte Nachrichten werden benötigt.
• Kodierung in $O(n \text{log} n)$ Zeit, für $n$ verschiedene Symbole.

Diskrete Kosinustransformation (DCT)

Definition:

DCT wandelt Diagramme von Zeit- oder Raumdomänen in Frequenzdomänen um, oft im Kontext der Bild- und Videokompression verwendet.

Details:

• Transformation: \ \[ X_k = \sum_{n=0}^{N-1} x_n \cos \left( \frac{\pi}{N} \left( n + \frac{1}{2} \right) k \right) \]
• Häufig in JPEG und MPEG verwendet.
• Reduziert Datenmenge durch Konzentration der meisten Signalinformationen auf wenige Frequenzkomponenten.
• DCT-Varianten: DCT-I, DCT-II (am häufigsten), DCT-III, DCT-IV.

Quantisierung und ihre Auswirkungen auf die Bildqualität

Definition:

Quantisierung ist der Prozess der Unterscheidung und Reduktion der Werte von Signal Amplituden zu einer endlichen Anzahl von Stufen. Es ist ein wesentlicher Schritt in der Bild- und Videokomprimierung.

Details:

• Führt zu Datenreduktion: Weniger Bits zur Darstellung erforderlich
• Je grober die Quantisierung, desto mehr Bildinformationen gehen verloren
• Zu starke Quantisierung kann sichtbare Artefakte erzeugen, z.B. Blockbildung
• Bitrate-Bildqualität-Tradeoff: Höhere Bitraten bedeuten tendenziell bessere Bildqualität
• Formel für Quantisierungsfehler: \[ Q_e = x - \tilde{x} \] (wobei \( x \) das Originalsignal und \( \tilde{x} \) das quantisierte Signal ist)
• Verwendung in JPEG, MPEG etc.

MPEG-4: Interaktive Multimediaanwendungen

Definition:

MPEG-4: Standard für interaktive Multimediaanwendungen mit hohem Kompressionsgrad bei gleichbleibender Qualität.

Details:

• Verwendung: Streaming, interaktive Anwendungen, Multimedia.
• Elemente: Video, Audio, 3D-Grafiken, Texte, Bilder.
• Kompressionstechniken: Wellenformcodierung, 3D-Mesh-Codierung.
• Profil- und Ebenenkonzept: Anpassung an unterschiedliche Anwendungen und Geräte.
• MPEG-4 Teile: MPEG-4 Teil 2 (Bildcodierung), MPEG-4 Teil 10 (H.264/AVC).
• Interaktivität: Benutzerinteraktionen einbindbar, z.B. in virtuellen Umgebungen.
• Codec-Bekanntheit: Xvid, DivX als bekannte Implementierungen.

H.264 und AVC (Advanced Video Coding)

Definition:

H.264/AVC ist ein weit verbreiteter Video-Codec-Standard zur Kompression von Videodaten.

Details:

• Ermöglicht hohe Kompressionsraten bei gleichzeitiger Beibehaltung hoher Videoqualität.
• Verwendet Block-orientierte Makroblockstruktur (16x16 Pixel).
• Intra- und Interframe-Kompressionstechniken.
• Unterstützt verschiedene Profile und Level für unterschiedliche Anwendungsbereiche.
• Wird in vielen Anwendungen verwendet: Streaming, Blu-ray Discs, Video-Telefonie.
• Nutzung der diskreten Kosinustransformation (DCT) in der Codierung.

Interframe- und Intraframe-Videokompression

Definition:

Interframe- und Intraframe-Videokompression sind Techniken zur Reduzierung der Datenmenge von Videodaten. Intraframe-Kompression reduziert die Datenmenge innerhalb eines einzelnen Frames (Bildes). Interframe-Kompression nutzt Redundanz zwischen aufeinanderfolgenden Frames.

Details:

• Intraframe-Kompression: Reduktion innerhalb eines Frames, z.B. DCT (Diskrete Kosinustransformation)
• Interframe-Kompression: Reduktion zwischen Frames, z.B. durch Bewegungsprädiktion und Kompensation
• Intraframe arbeitet nur mit räumlicher Redundanz, Interframe mit zeitlicher Redundanz
• Interframe-Kompression speichert Differenz zwischen Frames (Prädiktionsfehler)
• Wichtige Standards: MPEG, H.264, HEVC
• Formeln:
  • Intraframe-DCT: \[ F(u,v) = \sum_{x=0}^{N-1} \sum_{y=0}^{M-1} f(x,y) \cos \left[ \frac{(2x+1)u\pi}{2N} \right] \cos \left[ \frac{(2y+1)v\pi}{2M} \right] \]
  • Interframe-Vorhersage: \[ P_t(x,y) = f_{t-1}(x+u,y+v) \]

Algorithmische Ansätze zur Bewegungsschätzung

Definition:

Methoden zur Bestimmung der Bewegung von Objekten zwischen benachbarten Frames in einem Video - Grundlage für Kompressionstechniken wie MPEG oder H.264.

Details:

• Block-Matching-Verfahren: Teilt Bild in Blöcke und sucht nach Bereich mit minimaler Kostenfunktion.
• Kostenfunktionen: MSE (Mean Squared Error), MAD (Mean Absolute Difference), SAD (Sum of Absolute Differences).
• Hierarchische Suche: Beginnt mit grober Auflösung und verfeinert sukzessive.
• Gradientenbasierte Methoden: Nutzt Bildgradienten zur Schätzung der Bewegungsvektoren.
• Optischer Fluss: Berechnet Vektorfeld, das Bewegungspfade von Pixeln beschreibt.
• Komplexitätsbetrachtungen: Trade-off zwischen Genauigkeit und Berechnungsaufwand.