Wie das JPEG-Format funktioniert

JPEG-Bilder sind überall in unserem digitalen Leben zu finden, aber hinter diesem Wissen verbergen sich Algorithmen, die Details eliminieren, die vom menschlichen Auge nicht wahrgenommen werden. Am Ende ergibt sich eine höchst visuelle Qualität bei der kleinsten Dateigröße – aber wie funktioniert das konkret? Lassen Sie uns ansehen, was unsere Augen nicht sehen!

Es ist leicht, es als selbstverständlich anzunehmen, ein Foto an einen Freund zu schicken, ohne sich Gedanken darüber zu machen, welches Gerät, welchen Browser oder welches Betriebssystem er verwendet – doch das war nicht immer so. Zu Beginn der 1980er Jahre konnten Computer digitale Bilder speichern und anzeigen, aber es gab viele konkurrierende Ideen, wie man dies am besten tun sollte. Man konnte nicht einfach ein Bild von einem Computer auf einen anderen senden und hoffen, dass alles funktioniert.

Um dieses Problem zu lösen, wurde 1986 ein Komitee von Experten aus der ganzen Welt mit dem Namen „Gemeinsame Expertenkommission für Fotografie„ (Joint Photographic Experts Group, JPEG) gegründet, im Rahmen der Zusammenarbeit der Internationalen Organisation für Normung (ISO) und der Internationalen Elektrotechnischen Kommission (IEC) – zweier internationaler Normungsorganisationen mit Sitz in Genf (Schweiz).

Die Gruppe von Menschen, die JPEG genannt wird, schuf 1992 den JPEG-Standard für die Kompression digitaler Bilder. Jeder, der das Internet genutzt hat, ist wahrscheinlich auf Bilder im JPEG-Format gestoßen. Es ist die am weitesten verbreitete Methode zur Kodierung, dem Versand und der Speicherung von Bildern. Von Webseiten bis hin zu E-Mails und sozialen Medien wird JPEG Milliarden von Malen täglich verwendet – praktisch jedes Mal, wenn wir ein Bild online ansehen oder es senden. Ohne JPEG wäre das Web weniger lebendig, langsamer und würde wahrscheinlich weniger Katzenbilder enthalten!

Dieser Artikel handelt davon, wie man ein JPEG-Bild dekodiert. Mit anderen Worten, darüber, was erforderlich ist, um komprimierte Daten, die auf einem Computer gespeichert sind, in ein Bild umzuwandeln, das auf dem Bildschirm erscheint. Das sollte man nicht nur wissen, weil es wichtig ist, die Technologie zu verstehen, die wir täglich verwenden, sondern auch, weil wir durch das Aufdecken von Komprimierungsebenen besser verstehen, wie wir wahrnehmen und sehen, sowie welche Details unsere Augen am empfindlichsten wahrnehmen.

Außerdem macht es viel Spaß, mit Bildern auf diese Weise zu experimentieren.

Einen Blick ins Innere von JPEG werfen

Auf einem Computer wird alles als Folge von Binärzahlen gespeichert. Diese Bits, Nullen und Einsen, werden normalerweise in Gruppen von acht zusammengefasst, um Bytes zu bilden. Wenn Sie ein JPEG-Bild auf Ihrem Computer öffnen, muss etwas (der Browser, das Betriebssystem oder ein anderes Programm) die Bytes dekodieren und das ursprüngliche Bild als eine Liste von Farben wiederherstellen, die angezeigt werden können.

Wenn Sie dieses niedliche Katze-Foto herunterladen und in einem Texteditor öffnen, sehen Sie eine Menge zusammenhangloser Zeichen.

Hier benutze ich Notepad++, um den Inhalt der Datei zu untersuchen, da normale Texteditoren wie Notepad in Windows die Binärdatei nach dem Speichern beschädigen und sie nicht mehr dem JPEG-Format entspricht.

Wenn Sie ein Bild in einem Texteditor öffnen, verwirren Sie den Computer genauso, wie Sie Ihr Gehirn irritieren, wenn Sie sich die Augen reiben und anfangen, farbige Flecken zu sehen!

Diese Flecken, die Sie sehen, sind bekannt als Phosphen, und sie sind kein Ergebnis eines Lichtreizes oder Halluzinationen, die vom Geist erzeugt werden. Sie entstehen, weil Ihr Gehirn annimmt, dass elektrische Signale in den Sehnerven Informationen über Licht übertragen. Das Gehirn muss solche Annahmen treffen, da es unmöglich ist zu wissen, ob ein Signal ein Geräusch, eine Vision oder etwas anderes ist. Alle Nerven im Körper übertragen absolut identische elektrische Impulse. Wenn Sie auf die Augen drücken, senden Sie Signale, die keine visuellen sind, aber die Rezeptoren im Auge aktivieren, was Ihr Gehirn - in diesem Fall fälschlicherweise - als etwas Visuelles interpretiert. Sie sind buchstäblich in der Lage, Druck zu sehen!

Es ist interessant darüber nachzudenken, wie sehr Computer dem menschlichen Gehirn ähneln, aber es ist auch eine nützliche Analogie, die veranschaulicht, wie stark die Bedeutung von Daten – ob sie durch den Körper über Nerven übertragen oder auf einem Computer gespeichert werden – von ihrer Interpretation abhängt. Alle binären Daten bestehen aus Nullen und Einsen, den grundlegenden Komponenten, die Informationen jeder Art übertragen können. Ihr Computer erkennt oft, wie man sie interpretiert, anhand von Hinweisen wie z. B. Dateierweiterungen. Jetzt aber fordern wir ihn auf, sie als Text zu interpretieren, da dies vom Texteditor erwartet wird.

Um zu verstehen, wie JPEG decodiert wird, müssen wir die ursprünglichen Signale – die binären Daten – sehen. Das kann man mit einem Hex-Editor machen, oder direkt auf der Webseite des Originalarticles! Dort gibt es ein Bild, neben dem im Textfeld alle seine Bytes (außer dem Header) in dezimaler Form angezeigt werden. Sie können diese ändern, und das Skript wird sie in Echtzeit neu codieren und ein neues Bild ausgeben.

Man kann viel lernen, indem man einfach mit diesem Editor spielt. Könnten Sie zum Beispiel sagen, in welcher Reihenfolge die Pixel gespeichert sind?

Das Seltsame an diesem Beispiel ist, dass die Änderung einiger Zahlen überhaupt keinen Einfluss auf das Bild hat, aber wenn man beispielsweise die Zahl 17 in der ersten Zeile durch 0 ersetzt, wird das Bild völlig ruiniert!

Andere Änderungen, wie das Ersetzen von 7 in der Zeile 1988 durch die Zahl 254, verändern die Farbe, jedoch nur die nachfolgenden Pixel.

Es könnte am seltsamsten sein, dass einige Zahlen nicht nur die Farbe, sondern auch die Form des Bildes ändern. Ändern Sie die 70 in Zeile 12 in 2 und schauen Sie sich die obere Reihe des Bildes an, um zu sehen, was ich meine.

Und egal welches JPEG-Bild Sie verwenden, Sie werden immer diese mysteriösen schachbrettartigen Sequenzen beim Bearbeiten der Bytes finden.

Wenn man mit dem Editor spielt, ist es schwer zu verstehen, wie das Bild aus diesen Bytes rekonstruiert wird, da die JPEG-Kompression aus drei verschiedenen Technologien besteht, die nacheinander auf unterschiedlichen Ebenen angewendet werden. Wir werden jede von ihnen einzeln untersuchen, um das von uns beobachtete rätselhafte Verhalten zu entschlüsseln.

Drei Ebenen der JPEG-Kompression:

1. Farbsubsampling.
2. Diskrete Kosinustransformation und Quantisierung.
3. Lauflängenkodierung, Delta und Huffman

Um Ihnen die Dimensionen der Kompression vorzustellen, beachten Sie, dass das oben gezeigte Bild 79.819 Zahlen umfasst, also etwa 79 kB. Würden wir es unkomprimiert speichern, wären für jeden Pixel drei Zahlen erforderlich – für die rot, grün und blau Komponente. Das wären 917.700 Zahlen, also ca. 917 kB. Durch die JPEG-Kompression hat sich die endgültige Datei um mehr als das 10-fache reduziert!

In der Tat kann dieses Bild viel stärker komprimiert werden. Unten sehen Sie zwei Bilder nebeneinander – das Foto rechts wurde auf 16 kB komprimiert, also 57-mal kleiner als die unkomprimierte Version!

Wenn man genau hinsieht, wird deutlich, dass diese Bilder nicht identisch sind. Beide sind JPEG-komprimierte Bilder, jedoch ist das rechte viel kleiner. Außerdem sieht es etwas schlechter aus (schauen Sie sich die farbigen Hintergrundquadrate an). Deshalb wird JPEG auch als verlustbehaftete Kompression bezeichnet; während des Kompressionsprozesses verändert sich das Bild und verliert einige Details.

1. Farbunterabtastung

Hier ist das Bild mit nur der ersten Kompressionsebene.

(Interaktive Version – im Originalartikel). Das Entfernen einer Zahl zerstört alle Farben. Wenn man jedoch genau sechs Zahlen entfernt, hat das praktisch keine Auswirkungen auf das Bild. Jetzt sind die Zahlen etwas einfacher zu entschlüsseln. Es ist fast eine einfache Farbliste, bei der jedes Byte genau einen Pixel ändert, aber es ist bereits halb so groß wie das unkomprimierte Bild (das etwa 300 kB in dieser reduzierten Größe einnehmen würde). Wissen Sie, warum?

Man sieht, dass diese Zahlen nicht die Standardwerte für rot, grün und blau repräsentieren, denn wenn man alle Zahlen durch Nullen ersetzt, erhält man ein grünes Bild (und nicht ein weißes).

Das liegt daran, dass diese Bytes Y (Helligkeit) darstellen,

Cb (relative Blauigkeit),

und Cr (relative Rötlichkeit) des Bildes.

Warum nicht RGB verwenden? So funktioniert es doch bei den meisten modernen Bildschirmen. Ihr Monitor kann jede Farbe darstellen, einschließlich rot, grün und blau in unterschiedlicher Intensität für jeden Pixel. Weiß entsteht, wenn alle drei Farben auf maximale Helligkeit eingestellt sind, während schwarz ihre Deaktivierung bedeutet.

Das ähnelt auch der Funktionsweise des menschlichen Auges. Die Farbrezeptoren unserer Augen werden "

Zapfen" genannt." genannt.«, und sie werden in drei Typen unterteilt, von denen jeder empfindlicher auf entweder Rot, Grün oder Blau reagiert [S-Typ-Stäbchen sind empfindlich im violett-blauen (S von engl. Short – kurzwelliges Spektrum), M-Typ – im grün-gelben (M von engl. Medium – mittelwellig), und L-Typ – im gelb-roten (L von engl. Long – langwellig) Spektralbereich. Das Vorhandensein dieser drei Arten von Stäbchen (und Zapfen, die empfindlich im smaragdgrünen Bereich des Spektrums sind) verleiht dem Menschen das Farbsehen. \/ Anmerkung des Übersetzers.] Zapfen, ein anderer Typ von Photorezeptoren in unseren Augen, kann Veränderungen in der Helligkeit wahrnehmen, ist jedoch viel empfindlicher gegenüber Farbe. In unseren Augen gibt es etwa 120 Millionen Stäbchen und nur 6 Millionen Zapfen.

Unsere Augen nehmen daher Veränderungen in der Helligkeit viel besser wahr als Veränderungen in der Farbe. Wenn man Farbe von Helligkeit trennt, kann man etwas Farbe entfernen, und niemand wird es bemerken. Farbsubdiskretisierung ist der Prozess, bei dem die Farbkomponenten eines Bildes mit einer geringeren Auflösung im Vergleich zu den Helligkeitskomponenten dargestellt werden. Im obigen Beispiel hat jeder Pixel genau eine Y-Komponente, und jede einzelne Gruppe von vier Pixeln hat genau eine Cb- und eine Cr-Komponente. Daher enthält das Bild viermal weniger Farbinformationen als das Original.

Der Farbraum YCbCr wird nicht nur in JPEG verwendet. Er wurde ursprünglich 1938 für Fernsehsendungen entwickelt. Nicht jeder hat einen Farbfernseher, daher ermöglichte die Trennung von Farbe und Helligkeit allen, dasselbe Signal zu empfangen, wobei Farblos-Fernseher nur die Helligkeitskomponente verwendeten.

Das Entfernen einer Zahl im Editor zerstört daher alle Farben vollständig. Die Komponenten werden als Y Y Y Y Cb Cr gespeichert (tatsächlich nicht zwingend in dieser Reihenfolge – die Speicherreihenfolge wird durch den Header der Datei festgelegt). Das Entfernen der ersten Zahl führt dazu, dass der erste Cb-Wert als Y angesehen wird, Cr als Cb, und insgesamt ergibt sich der Dominoeffekt, der alle Farben des Bildes umschaltet.

Die JPEG-Spezifikation verpflichtet Sie nicht zur Verwendung von YCbCr. In den meisten Dateien wird es jedoch verwendet, da es im Vergleich zu RGB qualitativ bessere Bilder nach der Subsampling liefert. Aber Sie müssen mir nicht einfach glauben. Schauen Sie sich in der Tabelle unten an, wie das Subsampling jeder einzelnen Komponente sowohl in RGB als auch in YCbCr aussieht.

(Interaktive Version – im Originalartikel). Das Entfernen einer Zahl zerstört alle Farben. Wenn man jedoch genau sechs Zahlen entfernt, hat das praktisch keine Auswirkungen auf das Bild. Artikel).

Die Entfernung von Blau ist nicht so auffällig wie die von Rot oder Grün. Das liegt daran, dass von den sechs Millionen Zapfen in Ihren Augen etwa 64 % empfindlich auf Rot, 32 % auf Grün und 2 % auf Blau reagieren.

Das Subsampling der Y-Komponente (links unten) ist am besten zu erkennen. Selbst eine kleine Veränderung ist bemerkbar.

Die Umwandlung von Bildern von RGB in YCbCr verringert nicht die Dateigröße, erleichtert jedoch das Auffinden weniger auffälliger Details, die entfernt werden können. Die verlustbehaftete Kompression erfolgt im zweiten Schritt. Ihre Grundlage bildet die Idee, die Daten in einer komprimierbareren Form darzustellen.

2. Diskretes Kosinus-Transformieren und Subsampling

Dieses Kompressionsniveau bestimmt weitgehend die Essenz von JPEG. Nach der Farbumwandlung in YCbCr werden die Komponenten einzeln komprimiert, sodass wir uns im Folgenden nur auf die Y-Komponente konzentrieren können. So sehen die Bytes der Y-Komponente nach der Anwendung dieses Niveaus aus.

(Interaktive Version – im Originalartikel). Das Entfernen einer Zahl zerstört alle Farben. Wenn man jedoch genau sechs Zahlen entfernt, hat das praktisch keine Auswirkungen auf das Bild. Artikel). In der interaktiven Version wird ein Klick auf ein Pixel den Editor auf die Zeile scrollen, die es bezeichnet. Versuchen Sie, Zahlen am Ende zu löschen oder einige Nullen zu einer bestimmten Zahl hinzuzufügen.

Auf den ersten Blick schaut das nach einer sehr schlechten Kompression aus. In einem Bild mit 100.000 Pixeln sind zur Angabe ihrer Helligkeit (Y-Komponente) 102.400 Zahlen erforderlich – das ist schlechter, als wenn gar nichts komprimiert wird!

Beachten Sie jedoch, dass die meisten dieser Zahlen gleich Null sind. Darüber hinaus können all diese Nullen am Zeilenende entfernt werden, ohne das Bild zu ändern. Es bleiben etwa 26.000 Zahlen, was fast viermal weniger ist!

In diesem Niveau liegt das Geheimnis der Schachmuster. Im Gegensatz zu anderen Effekten, die wir gesehen haben, ist das Auftreten dieser Muster kein Fehler. Sie sind die Bausteine des gesamten Bildes. In jeder Zeile des Editors befinden sich genau 64 Zahlen, die Koeffizienten der diskreten Kosinus-Transformation (DCT), die den Intensitäten von 64 einzigartigen Mustern entsprechen.

Diese Muster werden auf der Grundlage des Cosinus-Diagramms gebildet. So sehen einige von ihnen aus:

8 von 64 Koeffizienten

Nachfolgend ist ein Bild, das alle 64 Muster zeigt.

(Interaktive Version – im Originalartikel). Das Entfernen einer Zahl zerstört alle Farben. Wenn man jedoch genau sechs Zahlen entfernt, hat das praktisch keine Auswirkungen auf das Bild. Artikel).

Diese Muster haben eine besondere Bedeutung, da sie die Basis für Bilder der Größe 8x8 bilden. Wenn Sie mit linearer Algebra nicht vertraut sind, bedeutet dies, dass jedes Bild der Größe 8x8 aus diesen 64 Mustern erzeugt werden kann. DCT ist der Prozess, bei dem Bilder in 8x8-Blöcke zerlegt werden und jeder Block in eine Kombination aus diesen 64 Koeffizienten umgewandelt wird.

Die Tatsache, dass jedes Bild aus 64 bestimmten Mustern zusammengesetzt werden kann, wirkt wie Magie. Aber es ist dasselbe, wie zu sagen, dass jeder Ort auf der Erde mit zwei Zahlen beschrieben werden kann – Breite und Länge [unter Angabe der Hemisphären / Anm. d. Übers.]. Wir betrachten oft die Erdoberfläche als zweidimensional, weshalb wir nur zwei Zahlen benötigen. Ein 8x8-Bild hat 64 Dimensionen, deshalb benötigen wir 64 Zahlen.

Es ist noch unklar, wie uns das im Hinblick auf die Kompression hilft. Wenn wir 64 Zahlen benötigen, um ein 8x8-Bild darzustellen, warum sollte diese Methode besser sein, als einfach 64 Helligkeitskomponenten zu speichern? Wir tun dies aus demselben Grund, aus dem wir drei RGB-Zahlen in drei YCbCr-Zahlen umgewandelt haben: Es ermöglicht uns, unauffällige Details zu entfernen.

Es ist schwer zu erkennen, welche Details in diesem Stadium entfernt werden, da JPEG DCT auf 8x8-Blöcke anwendet. Niemand hindert uns jedoch daran, es auf ein ganzes Bild anzuwenden. So sieht DCT auf der Y-Komponente aus, wenn es auf ein ganzes Bild angewendet wird:

Von den letzten kann man über 60.000 Zahlen praktisch ohne merkliche Änderungen am Foto entfernen.

Beachten Sie jedoch, dass, wenn wir die ersten fünf Zahlen auf Null setzen, der Unterschied offensichtlich sein wird.

Die Zahlen am Anfang repräsentieren Änderungen niedriger Frequenz im Bild, und unsere Augen nehmen sie am besten wahr. Die Zahlen näher am Ende repräsentieren Änderungen hoher Frequenz, die schwerer zu bemerken sind. Um "das Unsichtbare zu sehen", können wir diese Hochfrequenzdetails isolieren, indem wir die ersten 5000 Zahlen auf Null setzen.

Wir sehen alle Bereiche des Bildes, in denen die größte Veränderung von Pixel zu Pixel stattfindet. Die Augen der Katze, ihre Schnurrhaare, die flauschige Decke und die Schatten in der unteren linken Ecke heben sich hervor. Man könnte sogar noch weitergehen und die ersten 10.000 Zahlen auf Null setzen:

20 000:

40 000:

60 000:

Diese hochfrequenten JPEG-Daten werden beim Komprimierungsprozess entfernt. Die Umwandlung der Farben in DCT-Koeffizienten ist verlustfrei. Verluste entstehen bei der Diskretisierung, wo hochfrequente oder nahezu null Werte entfernt werden. Wenn Sie die Qualität der JPEG-Speicherung verringern, erhöht das Programm die Schwelle der zu entfernenden Werte, was zu einer Verkleinerung der Dateigröße führt, aber das Bild pixeliger macht. Deshalb sah das Bild im ersten Abschnitt, das 57 Mal kleiner war, so aus. Jeder Block von 8x8 wurde durch eine viel geringere Anzahl von DCT-Koeffizienten im Vergleich zur qualitativ hochwertigen Version repräsentiert.

Man kann einen coolen Effekt erzielen, wie das schrittweise Streaming von Bildern. Man kann ein verschwommenes Bild anzeigen, das mit zunehmendem Herunterladen immer detaillierter wird.

Hier, nur aus Interesse, was passiert, wenn man nur 24.000 Zahlen verwendet:

Oder nur 5000:

Sehr verschwommen, aber irgendwie erkennbar!

3. Codierung von Laufzeitfolgen, Delta und Huffman

Bisher wurden alle Komprimierungsstufen verlustbehaftet durchgeführt. Der letzte Schritt hingegen erfolgt verlustfrei. Er entfernt keine Informationen, reduziert jedoch die Dateigröße erheblich.

Wie kann man etwas komprimieren, ohne Informationen abzulehnen? Stellen Sie sich vor, wie wir ein einfaches schwarzes Rechteck von 700 x 437 beschreiben würden.

JPEG verwendet dafür 5000 Zahlen, aber man kann ein viel besseres Ergebnis erzielen. Können Sie sich ein Codierungsschema vorstellen, das ein solches Bild mit möglichst wenigen Bytes beschreibt?

Das minimale Schema, das ich mir ausgedacht habe, verwendet vier: drei zur Angabe der Farbe und die vierte, wie viele Pixel diese Farbe hat. Die Idee, sich wiederholende Werte auf diese komprimierte Weise darzustellen, wird als Laufzeitcodierung bezeichnet. Sie ist verlustfrei, da wir die kodierten Daten in ihrer ursprünglichen Form wiederherstellen können.

Die Größe der JPEG-Datei mit dem schwarzen Rechteck beträgt viel mehr als 4 Byte – denken Sie daran, dass auf DCT-Ebene die Komprimierung auf 8x8 Pixel-Bock angewendet wird. Daher benötigen wir mindestens einen DCT-Koeffizienten für jede 64 Pixel. Einen brauchen wir, weil anstelle der Speicherung eines DCT-Koeffizienten, dem 63 Nullen folgen, die Laufzeitkodierung es uns ermöglicht, eine Zahl zu speichern und zu kennzeichnen, dass "alle anderen Nullen sind".

Delta-Kodierung ist eine Technik, bei der jedes Byte die Abweichung von einem bestimmten Wert und nicht den absoluten Wert enthält. Daher ändert die Bearbeitung bestimmter Bytes die Farbe aller anderen Pixel. Zum Beispiel, anstatt zu speichern

12 13 14 14 14 13 13 14

Wir könnten mit 12 beginnen und dann einfach angeben, wie viel dazu addiert oder abgezogen werden muss, um die nächste Zahl zu erhalten. Und diese Sequenz der Delta-Kodierung sieht folgendermaßen aus:

12 1 1 0 0 -1 0 1

Die transformierten Daten werden nicht kleiner als die ursprünglichen, aber sie sind leichter zu komprimieren. Die Anwendung der Delta-Kodierung vor der Laufzeitkodierung kann erheblich helfen, während sie verlustfreie Kompression bleibt.

Delta-Kodierung ist eine der wenigen Techniken, die außerhalb von 8x8 Blöcken angewendet werden. Von 64 DCT-Koeffizienten ist einer einfach eine konstante Wellenfunktion (einfarbige Farbe). Er repräsentiert die durchschnittliche Helligkeit jedes Blocks für Helligkeitskomponenten oder die durchschnittliche Bläue für Cb-Komponenten und so weiter. Der erste Wert jedes DCT-Blocks wird als DC-Wert bezeichnet, und jeder DC-Wert wird in Bezug auf die vorherigen delta-kodiert. Daher beeinflusst eine Helligkeitsänderung des ersten Blocks alle Blöcke.

Es bleibt das letzte Rätsel: Wie kann die Änderung einer einzelnen Zahl das gesamte Bild ruinieren? Bisher gab es solche Eigenschaften der Kompressionsstufen nicht. Die Antwort liegt im JPEG-Header. Die ersten 500 Bytes enthalten Metadaten zum Bild – Breite, Höhe usw., und solange wir nicht mit ihnen gearbeitet haben,

Ohne Header ist es nahezu unmöglich (oder sehr schwierig), JPEG zu dekodieren. Es würde so aussehen, als würde ich versuchen, Ihnen ein Bild zu beschreiben, und beginne, Worte zu erfinden, um meinen Eindruck zu vermitteln. Die Beschreibung wird wahrscheinlich sehr komprimiert sein, da ich Worte genau mit der Bedeutung erfinden kann, die ich vermitteln möchte, aber für alle anderen werden sie keinen Sinn ergeben.

Es klingt dumm, aber genau so läuft es. Jedes JPEG-Bild wird mit spezifischen Codes komprimiert, die nur für dieses Bild gelten. Das Code-Wörterbuch wird im Header gespeichert. Diese Technik wird als „Huffman-Code“ bezeichnet, und das Wörterbuch ist die Huffman-Tabelle. Im Header ist die Tabelle mit zwei Bytes markiert – 255 und dann 196. Jeder Farbkomponente kann ihre eigene Tabelle zugeordnet werden.

Änderungen an den Tabellen beeinflussen jedes Bild radikal. Ein gutes Beispiel ist, die 1 in der 15. Zeile gegen 12 auszutauschen.

Das passiert, weil in den Tabellen angegeben ist, wie man einzelne Bits lesen muss. Bisher haben wir nur mit binären Zahlen in dezimaler Form gearbeitet. Aber das verdeckt uns die Tatsache, dass, wenn Sie die Zahl 1 in einem Byte speichern möchten, es so aussehen wird: 00000001, weil in jedem Byte genau acht Bits sein müssen, auch wenn nur eines von ihnen benötigt wird.

Das ist potenziell ein großer Platzbedarf, wenn Sie viele kleine Zahlen haben. Der Huffman-Code ist eine Technik, die es uns ermöglicht, diese Anforderung, dass jede Zahl acht Bits einnehmen muss, zu lockern. Das bedeutet, dass, wenn Sie zwei Bytes sehen:

234 115

In Abhängigkeit von der Huffman-Tabelle könnten dies drei Zahlen sein. Um sie zu extrahieren, müssen Sie sie zuerst in einzelne Bits aufteilen:

11101010 01110011

Dann schauen wir in die Tabelle, um zu verstehen, wie sie gruppiert werden. Zum Beispiel könnten das die ersten sechs Bits (111010) sein oder 58 im Dezimalsystem, gefolgt von fünf Bits (10011) oder 19 und schließlich die letzten vier Bits (0011) oder 3.

Deshalb ist es sehr schwierig, in dieser Phase der Kompression die Bytes zu entschlüsseln. Die Bytes repräsentieren nicht das, was sie zu sein scheinen. Ich werde hier nicht in die Details der Arbeit mit der Tabelle eintauchen, aber Materialien zu diesem Thema sind online ausreichend.

Einer der interessanten Tricks, die Sie wissen können, ist, den Header von JPEG zu trennen und ihn separat zu speichern. Im Grunde genommen können nur Sie die Datei lesen. Facebook macht das, um die Dateien noch weiter zu reduzieren.

Was Sie ebenfalls machen können, ist, die Huffman-Tabelle ein wenig zu verändern. Für andere wird es wie ein beschädigtes Bild aussehen. Nur Sie werden die magische Methode zur Behebung wissen.

Fassen wir zusammen: Was wird benötigt, um JPEG zu dekodieren? Es sind erforderlich:

1. Die Huffman-Tabelle(n) aus dem Header zu extrahieren und die Bits zu dekodieren.
2. Extrahiere die Koeffizienten der diskreten Cosinus-Transformation für jede Farb- und Helligkeitskomponente für jedes 8x8-Block, indem die inversen Transformationen der Laufzeitkodierung und der Deltas durchgeführt werden.
3. Kombiniere die Cosinuswerte basierend auf den Koeffizienten, um die Pixelwerte für jedes 8x8-Block zu erhalten.
4. Skaliere die Farbkomponenten, falls eine Subdiskretisierung durchgeführt wurde (diese Information befindet sich im Header).
5. Konvertiere die erhaltenen YCbCr-Werte für jedes Pixel in RGB.
6. Gib das Bild auf dem Bildschirm aus!

Eine ernsthafte Aufgabe für das einfache Anschauen eines Katzenfotos! Aber was mir daran gefällt – man sieht, wie nutzerzentriert die JPEG-Technologie ist. Sie basiert auf den Besonderheiten unserer Wahrnehmung, die es ermöglichen, eine viel bessere Kompression zu erreichen als mit herkömmlichen Technologien. Und jetzt, da ich verstehe, wie JPEG funktioniert, kann ich mir vorstellen, wie diese Technologien in andere Bereiche übertragen werden können. Zum Beispiel kann die Deltacodierung in Videos erheblich die Dateigröße reduzieren, da es dort oft große Bereiche gibt, die sich von Frame zu Frame nicht ändern (zum Beispiel der Hintergrund).

Der im Artikel verwendete Code, ist offen und enthält Anweisungen zum Ersetzen von Bildern durch eigene.

Quelle: habr.com