Wie JPG funktioniert

Wie JPG funktioniert

Das JPG-Dateiformat war einer der technologisch beeindruckendsten Fortschritte bei der Bildkomprimierung, die 1992 auf den Markt kamen. Seitdem ist es eine dominierende Kraft bei der Darstellung von Bildern in Fotoqualität im Internet. Und das aus gutem Grund. Ein Großteil der Technologie, die hinter der Funktionsweise von JPG steht, ist außerordentlich komplex und erfordert ein genaues Verständnis dafür, wie sich das menschliche Auge an die Wahrnehmung von Farben und Kanten anpasst.

Und da ich mich für solche Dinge interessiere (und Sie auch, wenn Sie dies lesen), wollte ich die Funktionsweise der JPG-Codierung aufschlüsseln, damit wir besser verstehen, wie kleinere JPG-Dateien erstellt werden.

DER GIST

Das JPG-Komprimierungsschema ist in mehrere Phasen unterteilt. Das Bild unten beschreibt sie auf hohem Niveau, und wir werden jede Phase unten durchgehen.

Farbraumkonvertierung

Eines der Hauptprinzipien der verlustbehafteten Datenkomprimierung ist, dass menschliche Sensoren nicht so genau sind wie Computersysteme. Wissenschaftlich gesehen hat das menschliche Auge nur die physische Fähigkeit, etwa 10 Millionen verschiedene Farben zu unterscheiden. Es gibt jedoch viele Dinge, die beeinflussen können, wie das menschliche Auge eine Farbe wahrnimmt. perfekt hervorgehoben mit Farbillusionen oder der Tatsache, dass dieses Kleid das Internet brach. Das Wesentliche ist, dass das menschliche Auge in Bezug auf die Farben, die es wahrnimmt, gut manipuliert werden kann.

Die Quantisierung ist eine Form dieses Effekts bei der verlustbehafteten Bildkomprimierung. JPG verfolgt hier jedoch einen anderen Ansatz: Farbmodelle . Ein Farbraum ist eine bestimmte Organisation von Farben, und sein Farbmodell stellt die mathematische Formel für die Darstellung dieser Farben dar (z. B. Dreifach in RGB oder Vierfach in CMYK).

Das Besondere an diesem Prozess ist, dass Sie von einem Farbmodell in ein anderes konvertieren können. Dies bedeutet, dass Sie die mathematische Darstellung einer bestimmten Farbe mit einem völlig anderen Satz numerischer Werte ändern können.

Im Folgenden finden Sie beispielsweise eine bestimmte Farbe, die in RGB- und CMYK-Farbmodellen dargestellt wird. Sie haben für das menschliche Auge dieselbe Farbe, können jedoch mit einem anderen Satz numerischer Werte dargestellt werden.

JPG konvertiert von RGB zu Y-, Cb- und Cr-Farbmodellen. Welches umfasst Luminanz (Y), Chroma Blue (Cb) und Chroma Red (Cr). Der Grund dafür ist, dass psycho-visuelle Experimente (auch bekannt als die Funktionsweise des Gehirns mit Informationen, die das Auge sieht) zeigen, dass das menschliche Auge empfindlicher auf Luminanz als auf Chrominanz reagiert, was bedeutet, dass wir größere Änderungen in der Chrominanz vernachlässigen können, ohne unsere zu beeinflussen Wahrnehmung des Bildes. Daher können wir aggressive Änderungen an den CbCr-Kanälen vornehmen, bevor das menschliche Auge dies bemerkt.

Downsampling

Eines der interessanten Ergebnisse des YCbCr-Farbraums ist, dass die resultierenden Cb / Cr-Kanäle weniger feinkörnige Details aufweisen. Sie enthalten weniger Informationen als der Y-Kanal.

Infolgedessen ändert der JPG-Algorithmus die Größe der Cb- und Cr-Kanäle auf ungefähr ¼ ihrer ursprünglichen Größe (beachten Sie, dass dies eine Nuance ist, die ich hier nicht behandele…), was als Downsampling bezeichnet wird .

Hierbei ist zu beachten, dass das Downsampling ein verlustbehafteter Komprimierungsprozess ist (Sie können nicht die genauen Quellfarben wiederherstellen, sondern nur eine enge Annäherung), aber die Gesamtwirkung auf die visuellen Komponenten des menschlichen visuellen Kortex ist minimal. In Luma (Y) ist das Interessante und da wir nur die CbCr-Kanäle herunterabtasten, sind die Auswirkungen auf das visuelle System gering.

Bild in 8x8 Pixelblöcke unterteilt

Von hier an führt JPG alle Operationen an 8x8 Pixelblöcken aus. Dies geschieht, weil wir im Allgemeinen erwarten, dass es keine großen Unterschiede zwischen den 8x8-Blöcken gibt, selbst bei sehr komplexen Fotos besteht in den lokalen Bereichen eine gewisse Selbstähnlichkeit. Diese Ähnlichkeit werden wir später bei unserer Komprimierung nutzen.

Es ist erwähnenswert, dass wir an dieser Stelle eines der ersten häufigen „Artefakte“ der JPG-Codierung einführen. Unter „Farbbluten“ können Farben entlang scharfer Kanten auf die andere Seite „bluten“. Dies liegt daran, dass bei den Chrominanzkanälen, die die Farbe von Pixeln ausdrücken, jeder Block von 4 Pixeln zu einer einzigen Farbe gemittelt wurde und einige dieser Blöcke die scharfe Kante kreuzen.

Diskrete Kosinustransformation

Bis zu diesem Punkt waren die Dinge ziemlich zahm. Colorspaces, Downsampling und Blocking sind in der Welt der Bildkomprimierung einfach. Aber jetzt ... jetzt zeigt sich die wahre Mathematik.

Die Schlüsselkomponente der DCT-Transformation besteht darin, dass davon ausgegangen wird, dass jedes numerische Signal mithilfe einer Kombination von Kosinusfunktionen neu erstellt werden kann.

Zum Beispiel, wenn wir diese Grafik unten haben:

Sie können sehen, dass es sich tatsächlich um eine Summe von cos (x) + cos (2x) + cos (4x) handelt.

Vielleicht ist eine bessere Darstellung davon die tatsächliche Dekodierung eines Bildes bei einer Reihe von Kosinusfunktionen über einen 2D-Raum. Um dies zu demonstrieren, präsentiere ich eines der erstaunlichsten GIFs im Internet: Codierung eines 8x8-Pixelblocks mit Cosinus in einem 2D-Raum:

Was Sie hier sehen, ist die Rekonstruktion eines Bildes (ganz links). Für jeden Frame nehmen wir einen neuen Basiswert (rechtes Feld) und multiplizieren ihn mit einem Gewichtungswert (rechter Feldtext), um den Beitrag zum Bild (mittleres Feld) zu erzeugen.

Wie Sie sehen können, können wir durch Summieren verschiedener Kosinuswerte gegen ein Gewicht unser Originalbild rekonstruieren (ziemlich gut ...)

Dies ist der grundlegende Hintergrund für die Funktionsweise der diskreten Kosinustransformation. Die Idee ist, dass jeder 8x8-Block als Summe gewichteter Cosinustransformationen bei verschiedenen Frequenzen dargestellt werden kann. Der Trick bei dieser ganzen Sache besteht darin, herauszufinden, welche Cosinus-Eingaben verwendet werden sollen und wie sie zusammen gewichtet werden sollten.

Es stellt sich heraus, dass das Problem, welche Kosinusse verwendet werden sollen , ziemlich einfach ist. Nach vielen Tests wurde eine Reihe von Kosinuswerten ausgewählt, um die besten Ergebnisse zu erzielen. Sie sind unsere Basisfunktionen und werden im folgenden Bild dargestellt.

Was das Problem betrifft, wie sie zusammen gewichtet werden sollen, wenden Sie einfach (HA!) Diese Formel an.

Ich werde Ihnen ersparen, was all diese Werte bedeuten. Sie können sie auf der Wikipedia-Seite nachschlagen.

Das grundlegende Ergebnis ist, dass für einen 8x8-Pixelblock in jedem Farbkanal durch Anwenden der obigen Formel- und Basisfunktionen eine neue 8x8-Matrix erzeugt wird, die die während der Rekonstruktion zu verwendenden Gewichte darstellt. Hier ist eine Grafik des Prozesses:

Diese Matrix G stellt die Basisgewichte dar, die zur Rekonstruktion des Bildes verwendet werden sollen (der kleine Dezimalwert unten rechts in der Animation oben). Grundsätzlich multiplizieren wir es für jede Basis mit dem Gewicht in dieser Matrix, addieren das Ganze und erhalten unser resultierendes Bild.

Ab diesem Zeitpunkt arbeiten wir nicht mehr in Farbräumen, sondern direkt mit der G-Matrix (Basisgewichte). Alle weiteren Komprimierungen werden direkt auf dieser Matrix durchgeführt.

Das Problem hierbei ist jedoch, dass wir jetzt byte-ausgerichtete Ganzzahlwerte in reelle Zahlen konvertieren. Dadurch werden unsere Informationen effektiv aufgebläht (Übergang von 1 Byte zu 1 Float (4 Byte)). Um dies zu lösen und eine signifikantere Komprimierung zu erzeugen, gehen wir zur Quantisierungsphase über.

Quantisierung

Wir möchten die Gleitkommadaten also nicht komprimieren. Dies würde unseren Strom aufblähen und nicht effektiv sein. Zu diesem Zweck möchten wir einen Weg finden, die Gewichtsmatrix wieder in Werte im Raum von [0,255] umzuwandeln. Wir könnten dies direkt tun, indem wir den Min / Max-Wert für die Matrix (-415,38 bzw. 77,13) ermitteln und jede Zahl in diesem Bereich teilen, um einen Wert zwischen [0,1] zu erhalten, mit dem wir mit 255 multiplizieren um unseren endgültigen Wert zu erhalten.

Zum Beispiel: [34.12- -415.38] / [77.13 - -415.38] * 255 = 232

Dies funktioniert, aber der Kompromiss ist eine signifikante Reduzierung der Präzision. Diese Skalierung führt zu einer ungleichmäßigen Verteilung der Werte, was zu einem erheblichen visuellen Verlust des Bildes führt.

Stattdessen geht das JPG einen anderen Weg. Anstatt den Wertebereich in der Matrix als Skalierungswert zu verwenden, wird stattdessen eine vorberechnete Matrix von Quantisierungsfaktoren verwendet. Diese QFs müssen nicht Teil des Streams sein, sondern können Teil des Codecs selbst sein.

Dieses Beispiel zeigt eine häufig verwendete Matrix von Quantisierungsfaktoren, einen für jedes Basisbild.

Wir verwenden nun die Q- und G-Matrizen, um unsere quantisierte DCT-Koeffizientenmatrix zu berechnen:

Verwenden Sie beispielsweise die Werte G [0,0] = - 415,37 und Q [0,0] = 16:

Das Ergebnis ist eine endgültige Matrix von:

Beobachten Sie, wie viel einfacher die Matrix wird - sie enthält jetzt eine große Anzahl von Einträgen, die klein oder null sind, was das Komprimieren erheblich erleichtert.

Kurz gesagt, wir wenden diesen Prozess unabhängig auf Y- und CbCr-Kanäle an und benötigen daher zwei verschiedene Matrizen: eine für Y und eine für die C-Kanäle:

Durch die Quantisierung wird das Bild auf zwei wichtige Arten komprimiert: Zum einen wird der effektive Bereich der Gewichte begrenzt und die Anzahl der zur Darstellung erforderlichen Bits verringert. Zweitens werden viele der Gewichte identisch oder Null, was die Komprimierung im dritten Schritt, der Entropiecodierung, verbessert.

Als solche ist die Quantisierung die Hauptquelle für JPEG-Artefakte. Da die Bilder unten rechts tendenziell die größten Quantisierungsteiler aufweisen, ähneln JPEG-Artefakte in der Regel Kombinationen dieser Bilder. Die Matrix der Quantisierungsfaktoren kann direkt gesteuert werden, indem das „Qualitätsniveau“ des JPEG geändert wird, wodurch die Werte nach oben oder unten skaliert werden (wir werden dies in einer Minute behandeln).

Kompression

Inzwischen sind wir wieder in der Welt der ganzzahligen Werte und können eine verlustfreie Komprimierungsstufe auf unsere Blöcke anwenden. Wenn Sie sich jedoch unsere transformierten Daten ansehen, sollten Sie etwas Interessantes bemerken:

Wenn Sie sich von links oben nach rechts unten bewegen, erhöht sich die Häufigkeit von Nullen. Dies scheint ein Hauptverdächtiger für die Lauflängencodierung zu sein. Aber Reihen-Haupt- und Spalten-Hauptreihenfolgen sind hier nicht ideal, da dies diese Nullenläufe verschachteln würde, anstatt sie alle zusammen zu packen.

Stattdessen beginnen wir mit der oberen linken Ecke und dem Zick-Zack in einem diagonalen Muster über die Matrix und gehen hin und her, bis wir die untere rechte Ecke erreichen.

Das Ergebnis unserer Luma-Matrix in dieser Reihenfolge lautet:

–26, –3,0, –3, –2, –6,2, –4,1, –3,1,1,5,1,2, –1,1, –1,2,0,0 , 0,0,0, -1, -1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 , 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Sobald die Daten in diesem Format vorliegen, sind die nächsten Schritte unkompliziert: Führen Sie RLE für die Sequenz aus und wenden Sie dann einen statistischen Encoder (Huffman / Arithmetic / ANS) auf die Ergebnisse an.

Und Boom. Ihr Block ist jetzt JPG-codiert.

Qualitätsparameter verstehen

Nachdem Sie nun verstanden haben, wie JPG-Dateien tatsächlich erstellt werden, sollten Sie das Konzept des Qualitätsparameters überdenken, den Sie normalerweise beim Exportieren von JPG-Bildern aus Photoshop (oder so weiter) sehen.

Dieser Parameter, den wir q nennen, ist eine Ganzzahl von 1 bis 100. Sie sollten sich q als Maß für die Bildqualität vorstellen: Höhere Werte von q entsprechen Bildern höherer Qualität und größeren Dateien.

Dieser Qualitätswert wird während der Quantisierungsphase verwendet, um die Quantisierungsfaktoren entsprechend zu skalieren. Damit ähnelt der Quantisierungsschritt pro Basisgewicht nun rund (Gi, k / alpha * Qi, k)

Wo das Alphasymbol als Ergebnis des Qualitätsparameters erstellt wird.

Wenn entweder Alpha oder Q [x, y] erhöht wird (denken Sie daran, dass große Alpha-Werte kleineren Werten des Qualitätsparameters q entsprechen), gehen mehr Informationen verloren und die Dateigröße nimmt ab .

Wenn Sie eine kleinere Datei auf Kosten von mehr visuellen Artefakten wünschen, können Sie während der Exportphase einen niedrigeren Qualitätswert festlegen.

Beachten Sie oben im Bild mit der niedrigsten Qualität, wie wir deutliche Anzeichen der Blockierungsstufe sowie der Quantisierungsstufe sehen.

Am wichtigsten ist wahrscheinlich, dass der Qualitätsparameter je nach Bild variiert . Da jedes Bild ein Unikat ist und verschiedene Arten von visuellen Artefakten aufweist, ist auch der Q-Wert eindeutig.

Fazit

Sobald Sie verstehen, wie der JPG-Algorithmus funktioniert, werden einige Dinge offensichtlich:

  1. Es ist wichtig, den richtigen Qualitätswert pro Bild zu ermitteln, um den Kompromiss zwischen visueller Qualität und Dateigröße zu finden.
  2. Da dieser Prozess blockbasiert ist, treten Artefakte in der Regel in Blockheit oder „Klingeln“ auf.
  3. Da verarbeitete Blöcke sich nicht miteinander vermischen, ignoriert JPG im Allgemeinen die Möglichkeit, große Teile ähnlicher Blöcke zusammenzudrücken. Das WebP-Format kann dieses Problem gut lösen.

Und wenn Sie selbst damit herumspielen möchten, kann all dieser Wahnsinn auf eine Datei mit ~ 1000 Zeilen reduziert werden.

HALLO!

Möchten Sie wissen, wie Sie Ihre JPG-Dateien verkleinern können?

Möchten Sie wissen, wie PNG-Dateien funktionieren oder wie Sie sie verkleinern können?

Möchten Sie mehr Datenkomprimierungsgüte? Kaufe mein Buch!