Image and Video Compression - Exam

Aufgabe 1)

Gegeben: Eine Quelle sendet die Symbole {A, B, C, D} mit den Wahrscheinlichkeiten {0.1, 0.4, 0.2, 0.3}. Nutze die Theorie der Informationsentropie, um die folgenden Aufgaben zu lösen.

b)

Interpretierte das Ergebnis der Entropie in Bezug auf die Vorhersagbarkeit der Symbole. Was bedeutet eine hohe Entropie im Kontext der Quelle?

Lösung:

Gegeben: Eine Quelle sendet die Symbole {A, B, C, D} mit den Wahrscheinlichkeiten {0.1, 0.4, 0.2, 0.3}. Nutze die Theorie der Informationsentropie, um die folgenden Aufgaben zu lösen.

Unteraufgabe: Interpretierte das Ergebnis der Entropie in Bezug auf die Vorhersagbarkeit der Symbole. Was bedeutet eine hohe Entropie im Kontext der Quelle?

Lösung:

Informationsentropie ist ein Maß für die Unvorhersagbarkeit oder Unsicherheit einer Informationsquelle. Die Entropie H, die wir zuvor berechnet haben, beträgt etwa 1.846 Bits. Nun wollen wir verstehen, was dieses Ergebnis bedeutet.

• Interpretation der Entropie:
• Eine hohe Entropie bedeutet, dass die Quelle eine hohe Unvorhersagbarkeit hat. Das bedeutet, dass es schwieriger ist, das nächste Symbol vorherzusagen. Im Extremfall, wenn alle Symbole gleiche Wahrscheinlichkeiten haben (wie bei einer fairen Münze), wäre die Entropie maximal.
• Eine niedrige Entropie bedeutet, dass die Quelle eine geringere Unvorhersagbarkeit hat. Das bedeutet, dass es einfacher ist, das nächste Symbol vorherzusagen. Im Extremfall, wenn ein Symbol immer gesendet wird, wäre die Entropie null.
• Bedeutung der Entropie von 1.846 Bits:
• Die berechnete Entropie von 1.846 Bits liegt im mittleren Bereich, was darauf hinweist, dass die Quelle eine mäßige Unvorhersagbarkeit hat. Es ist nicht vollständig zufällig, welches Symbol als nächstes kommt, aber es ist auch nicht völlig bestimmt.
• Die Wahrscheinlichkeiten der Symbole {0.1, 0.4, 0.2, 0.3} deuten darauf hin, dass einige Symbole (insbesondere das Symbol mit 0.4 Wahrscheinlichkeit) häufiger vorkommen, während andere weniger häufig sind. Daher ist die Entropie nicht maximal, aber auch nicht minimal.

Fazit: Eine Entropie von 1.846 Bits bedeutet, dass die Quelle eine gewisse Unvorhersagbarkeit in der Symbolsequenz hat. Die Quelle ist weder vollständig zufällig noch vollständig determiniert. Eine höhere Entropie würde auf größere Unvorhersagbarkeit hinweisen, während eine niedrigere Entropie auf größere Vorhersagbarkeit hinweisen würde.

c)

Wenn ein Kodierungsverfahren die Quelle komprimiert, gibt es die Möglichkeit von Informationsverlust. Diskutiere die möglichen Impplikationen, wenn die Nachrichtenquelle eine Entropie von 1.85 Bits hat und das verwendete Kodierungsverfahren eine durchschnittliche Codewortlänge von 2.1 Bits hat.

Lösung:

Gegeben: Eine Quelle sendet die Symbole {A, B, C, D} mit den Wahrscheinlichkeiten {0.1, 0.4, 0.2, 0.3}. Nutze die Theorie der Informationsentropie, um die folgenden Aufgaben zu lösen.

Unteraufgabe: Wenn ein Kodierungsverfahren die Quelle komprimiert, gibt es die Möglichkeit von Informationsverlust. Diskutiere die möglichen Implikationen, wenn die Nachrichtenquelle eine Entropie von 1.85 Bits hat und das verwendete Kodierungsverfahren eine durchschnittliche Codewortlänge von 2.1 Bits hat.

Lösung:

Um die Implikationen der angegebenen Situation zu diskutieren, betrachten wir folgende Punkte:

• Die Entropie der Quelle beträgt 1.85 Bits, was ein Maß für die durchschnittliche Informationsmenge pro Symbol ist.
• Das verwendete Kodierungsverfahren hat eine durchschnittliche Codewortlänge von 2.1 Bits pro Symbol.

Implikationen und Diskussion:

• Effizienz des Kodierungsverfahrens:
• Ein idealer Code hätte eine durchschnittliche Codewortlänge, die der Entropie der Quelle sehr nahe kommt. In diesem Fall wäre das 1.85 Bits. Das bedeutet, dass das Kodierungsverfahren möglichst effizient die Informationsmenge pro Symbol repräsentieren sollte.
• Da die durchschnittliche Codewortlänge des verwendeten Kodierungsverfahrens 2.1 Bits beträgt, ist dieses Verfahren nicht ganz optimal. Es erzeugt im Durchschnitt etwas längere Codewörter als notwendig. Die Redundanz des Codes gegenüber der optimalen Kompression beträgt 2.1 - 1.85 = 0.25 Bits pro Symbol.
• Potentieller Informationsverlust:
• Da die Entropie 1.85 Bits beträgt und das verwendete Kodierungsverfahren eine längere durchschnittliche Codewortlänge von 2.1 Bits hat, bedeutet dies, dass kein Informationsverlust auftritt. Der Unterschied zwischen der Entropie und der durchschnittlichen Codewortlänge stellt lediglich die Ineffizienz des Kodierungsschemas dar, nicht den Verlust von Informationen.
• Speicherplatz und Übertragungseffizienz:
• Die längere Codewortlänge von 2.1 Bits führt zu einem höheren Speicher- und Datenübertragungsaufwand. Mehr Speicherplatz und Bandbreite werden benötigt, um die gleiche Informationsmenge zu übertragen oder zu speichern im Vergleich zu einem idealerweise komprimierten Code bei 1.85 Bits pro Symbol.
• Dadurch entstehen zusätzliche Kosten und Anforderungen an das Speichersystem und die Kommunikationskanäle, welche vermieden werden könnten durch die Implementierung eines effizienteren Kodierungsschemas.

Fazit:

Das verwendete Kodierungsverfahren ist nicht optimal und führt zu einer kleinen Menge an Redundanz (0.25 Bits pro Symbol). Dies bedeutet, dass mehr Speicherplatz und Bandbreite benötigt werden als im Idealfall. Die Entropie der Quelle selbst (1.85 Bits) gewährleistet jedoch, dass keine Informationen verloren gehen; die Ineffizienz betrifft nur die Ressourcennutzung.

d)

Berechne die Redundanz des Kodierungsverfahrens, wenn die durchschnittliche Codewortlänge 2.1 Bits beträgt. Wie abhängig ist die Redundanz von der Entropie der Quelle?

Lösung:

Gegeben: Eine Quelle sendet die Symbole {A, B, C, D} mit den Wahrscheinlichkeiten {0.1, 0.4, 0.2, 0.3}. Nutze die Theorie der Informationsentropie, um die folgenden Aufgaben zu lösen.

Unteraufgabe: Berechne die Redundanz des Kodierungsverfahrens, wenn die durchschnittliche Codewortlänge 2.1 Bits beträgt. Wie abhängig ist die Redundanz von der Entropie der Quelle?

Lösung:

Um die Redundanz eines Kodierungsverfahrens zu berechnen, verwenden wir folgende Definition:

• Definition: Die Redundanz eines Kodierungsverfahrens ist der Unterschied zwischen der durchschnittlichen Codewortlänge \(\bar{L}\) und der Entropie \(\text{H}\) der Quelle.

Formel:

Redundanz = \(\bar{L} - H\)

Hierbei ist:

• \(\bar{L}\) die durchschnittliche Codewortlänge = 2.1 Bits
• \(\text{H}\) die Entropie der Quelle = 1.846 Bits (wie zuvor berechnet)

Setzen wir die Werte in die Formel ein:

• Redundanz = 2.1 - 1.846 = 0.254 Bits pro Symbol

Das bedeutet, dass das Kodierungsverfahren 0.254 Bits mehr pro Symbol verwendet als theoretisch notwendig, um die Information ohne Informationsverlust zu kodieren.

Abhängigkeit der Redundanz von der Entropie der Quelle:

• Die Redundanz ist direkt abhängig von der Entropie der Quelle und der durchschnittlichen Codewortlänge des verwendeten Kodierungsverfahrens.
• Wenn die Entropie der Quelle höher wäre, würde bei gleichem Kodierungsverfahren die Redundanz sinken, da die durchschnittliche Informationsmenge pro Symbol steigen würde.
• Umgekehrt, wenn die Entropie der Quelle niedriger wäre, würde die Redundanz steigen.

Zusammenfassend:

• Die Redundanz des Kodierungsverfahrens beträgt 0.254 Bits pro Symbol.
• Die Redundanz ist direkt abhängig von der Entropie der Quelle und der durchschnittlichen Codewortlänge des Kodierungsverfahrens. Eine höhere Entropie führt zu geringerer Redundanz und umgekehrt.

Aufgabe 2)

Huffman-Kodierung

• 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.

a)

Gegeben sei das Alphabet {A, B, C, D, E} mit den Häufigkeiten {10, 15, 30, 5, 40}. Erstelle den Huffman-Baum für dieses Alphabet und leite die Huffman-Codes für jedes Symbol ab. Welche Komplexität hat der Algorithmus für diesen Fall?

Lösung:

Huffman-Baum Erstellung und Codes AbleitungGegeben sei das Alphabet {A, B, C, D, E} mit den Häufigkeiten {10, 15, 30, 5, 40}.Der Prozess zur Erstellung des Huffman-Baums und zur Ableitung der Huffman-Codes lässt sich in mehreren Schritten erklären:

• Erstelle eine Liste der Symbole mit ihren Häufigkeiten:
• A: 10
• B: 15
• C: 30
• D: 5
• E: 40
• Konvertiere jedes Symbol in einen separaten Knoten einer Prioritätswarteschlange (Min-Heap) basierend auf den Häufigkeiten:
• Initiale Min-Heap: {D: 5, A: 10, B: 15, C: 30, E: 40}
• Zusammenführen der Knoten mit den geringsten Häufigkeiten:
• Verbinde D(5) und A(10) zu einem neuen Knoten mit der Summe der Häufigkeiten:
• Neuer Knoten: DA: 15
• Aktualisierte Min-Heap: {DA: 15, B: 15, C: 30, E: 40}
• Verbinde DA(15) und B(15) zu einem neuen Knoten:
• Neuer Knoten: DAB: 30
• Aktualisierte Min-Heap: {DAB: 30, C: 30, E: 40}
• Verbinde DAB(30) und C(30):
• Neuer Knoten: DABC: 60
• Aktualisierte Min-Heap: {DABC: 60, E: 40}
• Verbinde DABC(60) und E(40):
• Finale Wurzel: DABCE: 100
• Zeichne den resultierenden Baum und weise den Kanten Binärcodes zu (links = 0, rechts = 1):
• A = 101
• B = 100
• C = 01
• D = 111
• E = 00

• Der Huffman-Algorithmus hat eine Zeitkomplexität von O(n log n) aufgrund der Verwendung einer Prioritätswarteschlange für das Einfügen und Extrahieren der minimalen Knoten.

b)

Angenommen, Du möchtest eine Nachricht mit den Symbolen {A: 4-mal, B: 5-mal, C: 2-mal, D: 1-mal, E: 3-mal} codieren. Nutze die aus Subübung 1 abgeleiteten Huffman-Codes, um die Nachricht zu kodieren. Berechne die Gesamtlänge der kodierten Nachricht in Bits.

Lösung:

Codierung der Nachricht mit den abgeleiteten Huffman-CodesAnhand der in der vorherigen Übung abgeleiteten Huffman-Codes sollen wir nun die Nachricht mit den gegebenen Häufigkeiten der Symbole {A: 4-mal, B: 5-mal, C: 2-mal, D: 1-mal, E: 3-mal} kodieren und die Gesamtlänge der kodierten Nachricht in Bits berechnen:

• Abgeleitete Huffman-Codes:
• A = 101
• B = 100
• C = 01
• D = 111
• E = 00
• Kodieren der Nachricht basierend auf den Häufigkeiten:
• A: 4-mal → 101 101 101 101
• B: 5-mal → 100 100 100 100 100
• C: 2-mal → 01 01
• D: 1-mal → 111
• E: 3-mal → 00 00 00
Konkatenierte kodierte Nachricht:

101 101 101 101 100 100 100 100 100 01 01 111 00 00 00

• Berechnung der Gesamtlänge der kodierten Nachricht in Bits:
• A (4-mal): 4-mal 3 Bits = 4 * 3 = 12 Bits
• B (5-mal): 5-mal 3 Bits = 5 * 3 = 15 Bits
• C (2-mal): 2-mal 2 Bits = 2 * 2 = 4 Bits
• D (1-mal): 1-mal 3 Bits = 1 * 3 = 3 Bits
• E (3-mal): 3-mal 2 Bits = 3 * 2 = 6 Bits
• Gesamtlänge der kodierten Nachricht:
• 12 + 15 + 4 + 3 + 6 = 40 Bits
Die kodierte Nachricht hat eine Gesamtlänge von 40 Bits.

c)

Dekodiere die folgende Nachricht, die mit den aus Subübung 1 abgeleiteten Huffman-Codes kodiert wurde: 110011011001010100101. Gehe dabei Schritt für Schritt vor und gib die dekodierte Zeichenkette an.

Lösung:

Dekodierung der Nachricht mit den abgeleiteten Huffman-Codes

• Abgeleitete Huffman-Codes aus der vorherigen Übung:
• A: 101
• B: 100
• C: 01
• D: 111
• E: 00
• Gegebene kodierte Nachricht: 110011011001010100101
• Wir dekodieren die Nachricht Schritt für Schritt:
• Schlüssel:110 -> (nicht gefunden, also weiter)1100 -> (nicht gefunden, also weiter)11001 -> (nicht gefunden, also weiter)110010 -> (nicht gefunden, also weiter)110011 -> E
• Nachricht: 110011011001010100101 -> E
• Nachricht: 11001011001010100101 -> \tagbisjetzt
• Schlüssel:10 -> (nicht gefunden, also weiter)100 -> B
• Nachricht: 110010110010101001-> EB
• Nachricht: 1011001010100101
• Schlüssel:10 -> (nicht gefunden, also weiter)100 -> B
• Nachricht: 11001010100101-> EBB
• Nachricht: 101001010100101
• Schlüssel:10 -> (nicht gefunden, also weiter)100 -> A
• Nachricht: 101001010100101-> EBBA
• Nachricht: 001010100101
• Schlüssel:00 -> E
• Nachricht: 00101010100101-> EBBAE
• Nachricht: 0101010100101
• Schlüssel:01 -> C
• Nachricht: 00101010100101-> EBBAEC
• Nachricht: 01010100101
Schlüssel:01 -> CNachricht: 0101010100101-> EBBAECNachricht: 010C1 A0101 -> EBBAECC
• Nachricht: 001CCCC001
• Schlüssel:01 ->011 -> 0
• ==>==01 Nachricht: 01 Nachricht: 001NKOTES:
• E
• E\tSML\t---BEGIN-01001-000Z001111011\t..>-0 0 Nachricht: <----Nachricht: 101
• Schlüssel Soews-
• 101 Nachricht:N.E<49 Nar198 EBBAECCEB\t---001 ZeiB002

d)

Vergleiche die Effizienz der Huffman-Kodierung mit einer festen Länge Kodierung für das Alphabet {A, B, C, D, E}. Berechne die durchschnittliche Kodierlänge beider Verfahren und diskutiere die Ergebnisse unter Berücksichtigung der Häufigkeiten der einzelnen Symbole.

Lösung:

Vergleich der Effizienz der Huffman-Kodierung mit einer festen Länge KodierungUm die Effizienz der Huffman-Kodierung zu vergleichen, betrachten wir sowohl die Huffman-Kodierung als auch eine feste Länge Kodierung für das Alphabet {A, B, C, D, E} mit den Häufigkeiten {A: 10, B: 15, C: 30, D: 5, E: 40}.

• Huffman-Kodierung:
• Wir haben bereits die Huffman-Codes für die Symbole aus einer vorherigen Übung:
• A = 101
• B = 100
• C = 01
• D = 111
• E = 00
• Nun berechnen wir die durchschnittliche Kodierlänge:
• Die Formel für die durchschnittliche Kodierlänge ist:
• \[ \text{Durchschnittliche Kodierlänge} = \frac{\sum (\text{Häufigkeit des Symbols} * \text{Länge des Codes})}{\sum \text{Häufigkeiten}} \]
• Für unser Beispiel ergibt sich:
• \[\frac{(10 * 3) + (15 * 3) + (30 * 2) + (5 * 3) + (40 * 2)}{10 + 15 + 30 + 5 + 40} \]
• Die Berechnung ist:
• \[\frac{(30 + 45 + 60 + 15 + 80)}{100} = \frac{230}{100} = 2.3 \text{ Bits} \]
• Feste Länge Kodierung:
• Bei einer festen Länge Kodierung für 5 Symbole benötigen wir mindestens log₂(5) Bits pro Symbol:
• \[\lceil \log_{2}(5) \rceil = 3 \text{ Bits pro Symbol} \]
• Da alle Symbole gleich lang kodiert werden, ist die durchschnittliche Kodierlänge einfach die Länge des festen Codes:
• \[3 \text{ Bits pro Symbol} \]
Diskussion der Ergebnisse:
• Die durchschnittliche Kodierlänge der Huffman-Kodierung beträgt 2.3 Bits, während die feste Länge Kodierung 3 Bits pro Symbol benötigt.
• Dies zeigt, dass die Huffman-Kodierung effizienter ist als die Kodierung mit fester Länge, insbesondere bei ungleichen Häufigkeiten der Symbole.
• Huffman-Kodierung ist effizienter, weil sie kürzere Codes für häufigere Symbole und längere Codes für seltenere Symbole verwendet.
Fazit:Die Huffman-Kodierung bietet eine bitoptimale Kodierung, die die durchschnittliche Kodierlänge im Vergleich zu einem festen Länge Kodierung reduziert, insbesondere bei uneinheitlichen Symbolhäufigkeiten.

Aufgabe 3)

Diskrete Kosinustransformation (DCT)Die Diskrete Kosinustransformation (DCT) wird verwendet, um Signale aus der Zeit- oder Raumdomäne in die Frequenzdomäne umzuwandeln. Sie hat breite Anwendung in der Bild- und Videokompression, insbesondere in Standards wie JPEG und MPEG. Die Transformation führt dazu, dass die meisten Signalinformationen in wenigen Frequenzkomponenten konzentriert werden, wodurch die Datenmenge reduziert werden kann. Es gibt verschiedene Varianten der DCT, darunter DCT-I, DCT-II (am meisten verwendet), DCT-III und DCT-IV. Eine der Transformationen lautet:

• Transformation: \[ X_k = \sum_{n=0}^{N-1} x_n \cos \left( \frac{\pi}{N} \left( n + \frac{1}{2} \right) k \right) \]

a)

Teilaufgabe 1:Betrachte eine 8-Punkte-DCT-II-Transformation, in der die Eingangswerte durch die Folge \( x = [231, 32, 233, 161, 24, 71, 140, 245] \) gegeben sind.

• Berechne die DCT-II der gegebenen Folge mithilfe der vorgenannten Formel. Zeige deine detaillierten Berechnungen für alle Frequenzkomponenten \( X_0, X_1, \ldots, X_7 \).

Lösung:

Teilaufgabe 1:Berechne die DCT-II der gegebenen Folge

b)

Teilaufgabe 2:In der Praxis wird eine Quantisierung der Frequenzkomponenten nach der DCT durchgeführt, um die Kompression weiter zu verbessern. Angenommen, wir verwenden die Quantisierungsmatrix \( Q = [16, 11, 10, 16, 24, 40, 51, 61] \).

• Quantisiere die berechneten DCT-Koeffizienten aus Teilaufgabe 1 unter Verwendung der gegebenen Quantisierungsmatrix. Zeige deine detaillierten Berechnungen und Ergebnisse.

Lösung:

Diskrete Kosinustransformation (DCT)Die Diskrete Kosinustransformation (DCT) wird verwendet, um Signale aus der Zeit- oder Raumdomäne in die Frequenzdomäne umzuwandeln. Sie hat breite Anwendung in der Bild- und Videokompression, insbesondere in Standards wie JPEG und MPEG. Die Transformation führt dazu, dass die meisten Signalinformationen in wenigen Frequenzkomponenten konzentriert werden, wodurch die Datenmenge reduziert werden kann. Es gibt verschiedene Varianten der DCT, darunter DCT-I, DCT-II (am meisten verwendet), DCT-III und DCT-IV. Eine der Transformationen lautet:

• Transformation: \[ X_k = \sum_{n=0}^{N-1} x_n \cos \left( \frac{\pi}{N} \left( n + \frac{1}{2} \right) k \right) \]
Solve the following subexercise:Teilaufgabe 2:In der Praxis wird eine Quantisierung der Frequenzkomponenten nach der DCT durchgeführt, um die Kompression weiter zu verbessern. Angenommen, wir verwenden die Quantisierungsmatrix \[ Q = [16, 11, 10, 16, 24, 40, 51, 61] \].
• Quantisiere die berechneten DCT-Koeffizienten aus Teilaufgabe 1 unter Verwendung der gegebenen Quantisierungsmatrix. Zeige deine detaillierten Berechnungen und Ergebnisse.
Quantisierung der DCT-Koeffizienten
• Schritt-für-Schritt-Anleitung: Die Quantisierung erfolgt durch Division jedes DCT-Koeffizienten durch das entsprechende Element in der Quantisierungsmatrix und anschließendes Runden auf die nächste ganze Zahl. Die DCT-Koeffizienten aus Teilaufgabe 1 werden durch \[ X = [X_0, X_1, X_2, X_3, X_4, X_5, X_6, X_7] \] dargestellt. Die Quantisierungsmatrix lautet: \[ Q = [16, 11, 10, 16, 24, 40, 51, 61] \]. Die quantisierten Koeffizienten werden berechnet durch:

  X_q = [\frac{X_0}{Q_0}, \frac{X_1}{Q_1}, \frac{X_2}{Q_2}, \frac{X_3}{Q_3}, \frac{X_4}{Q_4}, \frac{X_5}{Q_5}, \frac{X_6}{Q_6}, \frac{X_7}{Q_7}]

• Schritte zur Berechnung: Angenommen, die DCT-Koeffizienten aus Teilaufgabe 1 sind:
  • \[ X = [114, -205, -1, 76, -32, 48, -5, -12] \] (gerundete Werte)
  Die Quantisierungsmatrix lautet:
  • \[ Q = [16, 11, 10, 16, 24, 40, 51, 61] \]
• Quantisierung:
  • \[ X_q = \left[ \frac{114}{16}, \frac{-205}{11}, \frac{-1}{10}, \frac{76}{16}, \frac{-32}{24}, \frac{48}{40}, \frac{-5}{51}, \frac{-12}{61} \right] \]
  • \[ X_q \approx \left[ 7.125, -18.636, -0.1, 4.75, -1.33, 1.2, -0.098, -0.197 \]
  • Wir runden auf die nächste ganze Zahl: \[ X_q \approx [7, -19, 0, 5, -1, 1, 0, 0] \]

Aufgabe 4)

Quantisierung und ihre Auswirkungen auf die BildqualitätQuantisierung 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.

• 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.

a)

Angenommen, Du hast ein Bildsignal mit 256 Graustufen. Eine einfache Quantisierung reduziert es auf 16 Graustufen. Berechne den maximalen Quantisierungsfehler \( Q_e \), wenn das Originalsignal \( x \) einen Wert von 120 hat. Erläutere auch die möglichen visuellen Auswirkungen dieser Quantisierung auf das Bild.

Lösung:

Berechnung des maximalen Quantisierungsfehlers und dessen Auswirkungen auf die Bildqualität

Gegeben:
• Originalsignal: 256 Graustufen
• Quantisiertes Signal: 16 Graustufen
• Originalsignalwert: 120

Quantisierung

Die Quantisierung reduziert die Anzahl der unterschiedlichen Werte, die das Signal annehmen kann. In diesem Fall werden die 256 Graustufen auf 16 Graustufen reduziert. Dies bedeutet, dass jeder Bereich von 16 aufeinanderfolgenden Graustufen des Originalsignals zu einer einzigen Graustufe im quantisierten Signal zusammengefasst wird.

Berechnung des maximalen Quantisierungsfehlers

Der Wertebereich der 256 Graustufen wird in 16 gleich große Intervalle aufgeteilt. Jedes Intervall hat daher eine Größe von: \[\frac{{256}}{{16}} = 16 Graustufen \] Die Quantisierung erfolgt so, dass jeder Intervallwert auf eine einzige Graustufe abgebildet wird.
• Intervallgrößen: 16 Graustufen
• Maximaler Fehler innerhalb eines Intervalls: \[\frac{{Intervallgröße}}{{2}} \]
• In diesem Fall: \[\frac{{16}}{{2}} = 8 Graustufen \]
Maximaler Quantisierungsfehler: Der Fehler, der durch die Quantisierung eingeführt wird, kann im schlimmsten Fall wie oben berechnet bis zu 8 Graustufen betragen.

Visuelle Auswirkungen der Quantisierung

• Verlust von Details: Da das Bildsignal von 256 auf nur 16 Graustufen reduziert wurde, gehen viele feine Abstufungen und Details verloren.
• Banding-Effekte: Starke Quantisierung kann zu sichtbaren Artefakten führen, die als Banding-Effekte bezeichnet werden. Dies erscheint als sichtbare, scharfe Übergänge zwischen den unterschiedlichen Graustufenbereichen.
• Reduzierte Bildqualität: Insgesamt wird die Bildqualität niedriger sein. Dies ist besonders in Bereichen des Bildes mit subtilen Gradienten und feinen Details bemerkbar.
• Blockbildung: In extremen Fällen können größere homogene Bereiche entstehen, die das menschliche Auge als 'Blöcke' interpretiert.

b)

Beschreibe den Bitrate-Bildqualität-Tradeoff in Bezug auf die Quantisierung anhand eines Beispiels. Berechne, wie sich die Bitrate ändert, wenn von einer 8-Bit auf eine 4-Bit Quantisierung umgestellt wird, und diskutiere die Auswirkungen auf die Bildqualität.

Lösung:

Bitrate-Bildqualität-Tradeoff bei der Quantisierung

Quantisierung: Quantisierung reduziert die Anzahl der möglichen Amplitudenwerte eines Signals, was zur Datenkompression führt. Bei der Bild- und Videokomprimierung spielt die Quantisierung eine wichtige Rolle, da sie die Bitrate beeinflusst.

Beispiel und Berechnung

• 8-Bit Quantisierung: Dies bedeutet, dass jeder Pixelwert im Bild durch 8 Bits dargestellt wird. Es gibt \[2^8 = 256\] verschiedene Graustufen.
• 4-Bit Quantisierung: Hier wird jeder Pixelwert durch 4 Bits dargestellt. Es gibt \[2^4 = 16\] verschiedene Graustufen.

Änderung der Bitrate

Angenommen, wir haben ein Bild mit einer Auflösung von \(1000 \times 1000\) Pixeln:
• Bei 8-Bit Quantisierung: Die Anzahl der Bits zur Darstellung des Bildes ist: \[1000 \times 1000 \times 8 \text{ Bits} = 8.000.000 \text{ Bits} \]
• Bei 4-Bit Quantisierung: Die Anzahl der Bits zur Darstellung des Bildes ist: \[1000 \times 1000 \times 4 \text{ Bits} = 4.000.000 \text{ Bits} \]
Reduzierung der Bitrate: Die Bitrate wird halbiert, wenn von 8 Bit auf 4 Bit quantisiert wird.

Auswirkungen auf die Bildqualität

• Reduzierte Detailgenauigkeit: Durch die geringere Anzahl von Graustufen (16 statt 256) können feine Abstufungen und Details im Bild verloren gehen.
• Banding-Effekte: Starke, sichtbare Übergänge zwischen den Quantisierungsstufen sind wahrscheinlicher, was zu unerwünschten Banding-Artefakten führt.
• Blockbildung: In Bereichen des Bildes mit feineren Gradienten kann es zu sichtbaren Blockmustern kommen, weil ähnliche Pixelwerte gröber zusammengefasst werden.
• Allgemeine Wahrnehmung: Das Bild wird allgemein eine geringere visuelle Qualität aufweisen, insbesondere in Bereichen mit sanften Übergängen oder feinen Details.

Schlussfolgerung

Der Wechsel von einer 8-Bit zu einer 4-Bit Quantisierung führt zu einer signifikanten Reduktion der Bitrate, was speicher- und übertragungstechnisch vorteilhaft ist. Allerdings geht dies auf Kosten der Bildqualität, da die Feinheit der Darstellung verringert wird und sichtbare Artefakte entstehen können. Der Bitrate-Bildqualität-Tradeoff erfordert daher eine sorgfältige Abwägung der gewünschten Komprimierungseffizienz und der akzeptablen Bildqualität.