Kompression & Resampling Flashcards
Führen Sie über Motivation und Anwendungsgebiete von Kompression aus. Welche Strategien zur Kompression kennen Sie?
Die Kompression von Daten wird verwendet, um Daten schneller transferieren zu können. Komprimierte Daten benötigen weniger Platz und Ressourcen auf Geräten oder Speichermedien. Auch der Speicherbedarf in einem Archiv kann mittels Kompression minimiert werden.
Motivation / Anwendung
* Speicherreduktion
* Schnellere Bearbeitung
* Resampling zur Normalisierung der Abmessungen
Strategien
Abmessung: Größenänderung/Resampling
skalare Werte: Einschränkung Wertebereich / Quantisierung, Code-Transformation (Ausnützung Entropie)
Informationsgehalt: Entfernung von irrelevanten Frequenzen des Spektrums; Datenreduktion
Welche Techniken der Kompression sind verlustfrei / verlustbehaftet?
Verlustfrei
Huffman-Codierung:
Eine effiziente Komprimierungsmethode, bei der häufig vorkommende Symbole mit kürzeren Codes und seltenere Symbole mit längeren Codes versehen werden.
LZW (Lempel-Ziv-Welch):
Ein verlustfreies Verfahren, das auf dem Ersetzen von wiederholten Zeichenketten durch kürzere Codes basiert. LZW wird in Formaten wie GIF und TIFF verwendet.
Run-Length Encoding (RLE):
Diese Methode ersetzt wiederholte Zeichen oder Pixel durch ein Symbol und eine Anzahl. Besonders effektiv bei Daten mit vielen wiederholten Werten, wie z. B. in schwarz-weiß Bildern oder einfachen Texten.
Verlustbehaftet
JPEG
Sie nutzt eine Kombination aus diskreter Kosinustransformation (DCT), Quantisierung und Huffman-Codierung
MP3 (MPEG Audio Layer 3):
Ein beliebtes Format zur Audio-Kompression. MP3 verwendet eine psychoakustische Analyse, um die Daten zu reduzieren, indem es Töne entfernt, die für das menschliche Ohr nicht hörbar sind, und dabei gleichzeitig die Dateigröße drastisch verringert.
Wie kann speziell bei Bilddaten Redundanz zu Zwecken der Kompression ausgenützt werden?
1.1 Räumliche Redundanz (Spatial Redundancy):
Bilddaten weisen häufig ähnliche oder identische Pixelwerte in benachbarten Regionen auf, insbesondere bei homogenen oder gleichmäßigen Flächen (z. B. blauer Himmel oder große einfarbige Flächen).
1.2 Spektrale Redundanz (Spectral Redundancy):
In Farbbildern gibt es oft Abhängigkeiten zwischen den verschiedenen Farbkanälen (z. B. Rot, Grün, Blau). Ein stark korrelierter Zusammenhang zwischen den Farbkanälen führt zu spektraler Redundanz.
1.3 Zeitliche Redundanz (Temporal Redundancy):
In Bildsequenzen (z. B. Videos) bleiben benachbarte Frames oft ähnlich, da sich zwischen zwei Frames oft nur ein kleiner Teil des Bildes ändert.
1.4 Psychovisuelle Redundanz:
Das menschliche Auge nimmt nicht alle Bilddetails gleich gut wahr. Es ist empfindlicher gegenüber Helligkeitsunterschieden als gegenüber Farbdetails oder feinen, hochfrequenten Details.
Führen Sie über Resampling aus. Welche Interpolationsverfahren kennen Sie in diesem Kontext? Beschreiben Sie kurz und vergleichen Sie in Bezug auf Performanz und erzielbare Qualität.
Beim Resampling kommt es zu einer vergrößernden oder verkleinernden Transformation des Bildes, und dabei müssen die Grauwerte für das neue Bild aus jenen des alten berechnet werden.
Also eine geometrische Transformation von Bildern aus einer vorliegenden Grauwertmatrix, aus der eine neue berechnet wird.
Nearest Neighbour Interpolation
(nächstgelegenen skalaren Pixelwerte aus A werden in den Zielwert nach B transferiert und ich bekomme ein stufiges, kantiges Bild und die Koordinaten werden dann ganzzahlig gerundet)
Bilineare Interpolation (ich mache eine lineare Interpolation aus den Nachbarwerten, und Gewichte den Einfluss der Nachbarwerte anhand des Abstandes von der Zielkoordinate)
Bikubische Interpolation
(wenn zwischen den viermal vier umliegenden Grauwerten im Eingabebild mit Gleichungen dritten Grades interpoliert wird)
Dabei sind diese drei Verfahren nach ihrer aufsteigenden Anordnung von 1-3 komplexer in der Implementierung und auch laufzeitintensiver, aber liefern eben auch höhere Qualität.
Erläutern Sie die Begriffe Entropie und Homogenität.
Die Entropie beschreibt das Maß der Unordnung im Bild, und quasi damit auch den Informationsgehalt. Je höher die Entropie, desto mehr Informationsgehalt ist im Bild, und desto weniger kann es komprimiert werden.
Homogenität: Homogen wenn man auf das vorhergehend Zeichen/Symbol schließen kann, bzw. wie oft die Zeichensequenz alterniert.
Nennen Sie Kompressionsverfahren und erläutern Sie, ob die erzielbare Kompressionsrate von der Entropie und/oder Homogenität abhängt. Bei welchen Anwendungsgebieten macht man sich die Entropie als Kennziffer zunutze?
Einteilung in:
● Verlustfreie Verfahren d.h. das originale Signal kann wiederhergestellt werden (z.B. ZIP, runlength coding)
● Verlustbehaftet, d.h. die Kompression ist irreversibel (z.B. JPEG, Quantisierung)
Beispiele für Kompressionsmethoden:
● Lempel Ziv Kompression (LZW)
● Runlength Coding
● Huffmann Coding
Kompressionsrate in Abhängigkeit von Homogenität und Entropie:
LZW:
Entropie: LZW funktioniert gut, wenn die Entropie niedrig ist, also wenn sich Muster häufig wiederholen.
Homogenität: Homogene Daten mit sich wiederholenden Mustern oder langen, gleichartigen Sequenzen (z. B. Text oder einfache Bilder) ergeben hohe Kompressionsraten.
Huffmann:
Entropie: Huffman-Kodierung funktioniert besser bei Daten mit geringer Entropie, wo einige Symbole häufiger vorkommen als andere. Bei gleichverteilten Symbolen (hohe Entropie) wird die Kompressionsrate reduziert.
Homogenität: Homogenität kann indirekt helfen, wenn sich dadurch die Häufigkeit bestimmter Symbole erhöht.
Runlenght:
Homogenität: Funktioniert optimal bei hoher Homogenität, d. h., wenn viele lange Wiederholungssequenzen vorkommen (z. B. große Flächen gleicher Farbe in Bildern).
Entropie: Wenn die Entropie hoch ist (viele unterschiedliche Werte ohne Wiederholungen), ist RLE ineffizient oder kann sogar zu einer negativen Kompression führen.
JPG:
Entropie: Bei Bildern mit hoher Entropie (hoher Detailgrad und viele unterschiedliche Farben) ist die erzielbare Kompressionsrate geringer.
Homogenität: Bilder mit homogener Struktur (z. B. einfache Flächen oder Farbverläufe) können stark komprimiert werden, da sie vor allem aus niedrigen Frequenzen bestehen.
Erläutern Sie Runlength Coding (+BSP)
Runlength Coding (RLE) ist ein einfaches Verfahren zur Datenkompression. Es basiert auf der Idee, aufeinanderfolgende gleiche Zeichen oder Werte (sogenannte Läufe) durch ein Paar aus dem Zeichen und der Anzahl der Wiederholungen darzustellen. Dies reduziert die Datenmenge bei vielen aufeinanderfolgenden Wiederholungen.
Einfach zu implementieren.
Effizient bei Daten mit vielen Wiederholungen (z. B. Schwarz-Weiß-Bilder oder einfache Texte).
-> Hohes Maß an Homogenität
Erläutern Sie Huffmann Coding (+BSP)
Huffman Coding ist ein verlustfreies Verfahren zur Datenkompression, das auf der Idee beruht, Zeichen mit unterschiedlicher Häufigkeit unterschiedlich lange Codes zuzuweisen. Häufige Zeichen erhalten kürzere Codes, seltene Zeichen längere, um die Gesamtlänge der codierten Nachricht zu minimieren. Es basiert auf einem binären Baum, dem sogenannten Huffman-Baum.
-> geringe Entropie
Huffman Baum erstellen! ABRACADABRA
Erläutern Sie Lempel-Ziv- Kompression (+BSP)
Die Lempel-Ziv-Kompression (LZ) ist eine verlustfreie Kompressionsmethode, die Daten auf der Basis von Wiederholungen in einer Zeichenfolge effizient komprimiert. Sie speichert keine Wiederholungen direkt, sondern ersetzt sie durch Verweise auf frühere Daten in der Sequenz. Lempel-Ziv ist die Grundlage vieler moderner Kompressionsalgorithmen, wie z. B. ZIP oder PNG.
-> hohe Homogenität
Wie wird bei JPEG Bildern verlustbehaftete Kompression erwirkt. Was sind in diesem Kontext „Quantisierungs-Tabellen“ und „Zigg-Zagg-Coding“?
- Ortsmatrix in 8x8 Segmente teilen
- Jeder 8×8-Block wird mittels DCT in Frequenzkomponenten umgewandelt:
Niedrige Frequenzen (oben links): Beschreiben grobe Strukturen und sind für das Bild am wichtigsten.
Hohe Frequenzen (unten rechts): Beschreiben feine Details, die das menschliche Auge oft kaum wahrnimmt. - die entstandenen Koeffizienten mit den Werten aus einer
Quantisierungstabelle dividieren - Quantisierte Koeffizienten erhalten (= komprimiertes Bild)
Die Frequenzkoeffizienten im 8×8-Block werden in einer Zickzack-Reihenfolge abgelegt, um Nullen (stark reduzierte oder weggerundete hohe Frequenzen) zu gruppieren. Dies erleichtert die spätere Kompression durch Laufzeitkodierung (Runlength-Encoding).
Was ist DCT?
Diskrete Kosinus-Transformation
Führen Sie über die Charakteristika des Holt-Winter Exponential Smoothings zur Vorhersage aus.
Für die Vorhersage werden 3 Aspekte berücksichtigt:
· Aktuelles Level, die unmittelbar letzten Werte
· Trend, d.h. ob die Messwerte gleich bleiben oder einem Anstieg, Abfall unterschiedlicher Stärke unterworfen sind
· Saisonale Aspekte, d.h. periodisch wiederkehrende Abweichungen vom Verlauf
Gut für die Prognosen von Verkaufszahlen, Lagerstand, etc. Ferner regeln Glättungskoeffizienten wie robust das Modell auf Ausreißer bzw. schnelle Trendumkehr reagieren soll.
——
Das aktuelle Niveau (Level): Wie viele Waffeln verkaufst du gerade im Durchschnitt?
Den Trend: Verkaufen sich Waffeln über die Zeit eher mehr oder weniger?
Die Saisonalität: Gibt es Muster, die sich regelmäßig wiederholen? Zum Beispiel, dass im Sommer mehr Eis verkauft wird als im Winter.
Angenommen, du weißt:
Aktuell verkaufst du 150 Waffeln pro Monat (Level). Deine Verkäufe steigen jedes Jahr um 10 Waffeln (Trend). Im Sommer verkaufst du immer 50 Waffeln mehr (Saisonalität).
Dann könnte die Vorhersage für nächsten Sommer sein:
150 Waffeln + 10 Waffeln (weil ein Jahr vergangen ist) + 50 Waffeln (Saison) = 210 Waffeln.
Additiv (gleichmäßige Schwankungen):
Wenn im Sommer immer 50 Waffeln mehr verkauft werden als im Winter, unabhängig davon, ob der Trend steigt oder fällt. Beispiel: Verkaufe ich 100 Waffeln im Winter, dann 150 im Sommer. Steigt der Trend, sind es z. B. 200 im Winter und 250 im Sommer.
Multiplikativ (Schwankungen wachsen mit):
Wenn im Sommer die Verkäufe immer doppelt so hoch sind wie im Winter. Beispiel: 100 Waffeln im Winter → 200 im Sommer. Steigt der Trend, könnten es 200 im Winter und 400 im Sommer sein.
Welche weiteren Konzepte und Strategien zur Extrapolation kennen Sie?
· Lineare Extrapolation nach Filterung z. B. 5 oder 30 Tagesdurchnitt bei Aktienwerte
· Splines, Polynome n-ten Grades
· Maschinelles Lernen : Neuronale Netze, Support Vectors, Genetic Programming
Lineare Extrapolation: Einfache Linie basierend auf Durchschnitt, gut für schnelle Trends.
Splines und Polynome: Kurven, die den Verlauf sanfter oder genauer beschreiben können.
Maschinelles Lernen:
Neuronale Netze: Lernen komplexe Muster, wie ein Gehirn. SVMs: Ziehen clevere Trennlinien zwischen Gruppen (z. B. Steigen/Fallen). Genetic Programming: Probiert viele Lösungen aus und verbessert sie durch "Evolution".
Wie kann man mittels Kompression Signale (Bilder) klassifizieren. Erläutern Sie dieses Vorgehen und nennen Sie etwaige Anwendungsgebiete.
Wörterbuch-basierte Kompressionsverfahren, wie gzip, können auch zur Klassifizierung verwendet werden. Klassifizierung von Text (Spracherkennung), Bildern (Kategorisierung), Sprachsignalen (Spracherkennung). Idee: Referenzsignale für die unterschiedlichen Klassen anlegen.
Verwendung von Lempel-Ziv-Welch zur Kompression. Evaluierung des Kompressionsdeltas → Datensatz wird der Referenzklasse mit dem kleinsten Kompressionsdeltas zugeordnet
Anwendungsgebiete: Spracherkennung bei Text, Kategorisierung von Bildern, Spracherkennung bei Sprachsignalen
Kompressionsalgorithmen (wie z. B. ZIP, JPEG oder andere) nutzen die statistische Redundanz in Daten, um deren Größe zu reduzieren.
Wenn zwei Signale oder Bilder ähnlich sind, haben sie ähnliche Redundanzmuster und lassen sich mit demselben Algorithmus auf ähnliche Weise komprimieren.
Der Grad der Kompression (d. h. wie stark die Datei verkleinert wird) oder der Aufwand für die Kompression (z. B. Rechenzeit) kann als Merkmal genutzt werden, um Signale oder Bilder zu vergleichen und zu klassifizieren.
