Schreiben wir einen Video-Codec – Teil 3: Standbilder

In den vorherigen Teilen dieser Serie haben wir etwas über die Diskrete Kosinustransformation gelernt, von ihrer mathematischen Definition bis zu ihrer Implementierung in tatsächlichen Beispielen. Darüber hinaus haben wir gesehen, wie die Fähigkeit von DCT, Daten im Frequenzbereich darzustellen, eine verlustbehaftete Datenkomprimierung ermöglichen kann.

Jetzt machen wir den nächsten Schritt. Abschließend ziehen wir die Linie zwischen diesen abstrakten Zahlenfeldern, die wir besprochen haben, und den tatsächlichen Bildern, die sie darstellen können.

Am Ende dieses Artikels werden wir etwa 80 % des eigentlichen JPEG-Bildkomprimierungsprozesses wiederentdeckt haben.

Die Matrix

Im vorherigen Artikel haben wir die 2D-DCT vorgestellt. Schauen wir uns nun eine leicht angepasste Version dieser Formel an:

Die Variablen u und v repräsentieren den horizontalen und vertikalen Versatz des Werts im DCT-codierten 2D-Array. Die Funktion α(x) ist gleich 1/sqrt(2) wenn x == 0 und andernfalls 1 . Schließlich repräsentieren x und y die Position des Pixels im Quellbild.

Dies mag nicht offensichtlich erscheinen, aber dieselbe Berechnung kann als Matrixmultiplikation in der folgenden Form dargestellt werden:

In dieser Formulierung ist DCT die DCT-Matrix, T bezeichnet die Matrixtransposition und IMG ist das Quellbild.

Bedenken Sie, dass die Komplexität dieses Vorgangs proportional zur Größe des Quellbilds ist. Um Bilder beliebiger Größe zu verwalten und den Arbeitsaufwand zu reduzieren, beschränken wir unsere Berechnungen auf Bildblöcke mit einer Größe von 8 x 8 Pixeln.

Während reale Bilder tendenziell eine höhere Auflösung haben, können wir sie uns als aus vielen unabhängigen 8x8-Blöcken zusammengesetzt vorstellen.

So berechnen wir die DCT-Matrix, die den gewünschten Effekt erzeugt:

 var dctMatrix: [Float] = Array(repeating: 0.0, count: 8 * 8) for i in 0 ..< 8 { for j in 0 ..< 8 { let a: Float if i == 0 { a = sqrt(1.0 / 8.0) } else { a = sqrt(2.0 / 8.0) } dctMatrix[j * 8 + i] = a * cos((2.0 * Float(j) + 1) * Float(i) * Float.pi / (2.0 * 8)) } }

Der Wert von dctMatrix ist:

 0.35 0.49 0.46 0.42 0.35 0.28 0.19 0.10 0.35 0.42 0.19 -0.10 -0.35 -0.49 -0.46 -0.28 0.35 0.28 -0.19 -0.49 -0.35 0.10 0.46 0.42 0.35 0.10 -0.46 -0.28 0.35 0.42 -0.19 -0.49 0.35 -0.10 -0.46 0.28 0.35 -0.42 -0.19 0.49 0.35 -0.28 -0.19 0.49 -0.35 -0.10 0.46 -0.42 0.35 -0.42 0.19 0.10 -0.35 0.49 -0.46 0.28 0.35 -0.49 0.46 -0.42 0.35 -0.28 0.19 -0.10

Wie Sie sehen, handelt es sich lediglich um eine Reihe von Zahlen. Es ist nicht erforderlich, die Matrixwerte jedes Mal neu zu berechnen, wenn wir die Transformation anwenden, sodass wir sie in einem konstanten Array in unserem Code behalten können.

Dieser Code führt eine 8x8-Matrixmultiplikation durch:

 func matrixMul8x8(m1: [Float], m2: [Float], result: inout [Float]) { for i in 0 ..< 8 { for j in 0 ..< 8 { var acc: Float = 0.0 for k in 0 ..< 8 { acc += m1[i * 8 + k] * m2[k * 8 + j] } result[i * 8 + j] = acc } } }

Wir berechnen den 8x8-DCT wie folgt:

 func dct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrixT, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrix, result: &resultBlock) return resultBlock }

Die inverse DCT kann einfach durch Austauschen der regulären und transponierten DCT-Matrizen erhalten werden:

 func idct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrix, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrixT, result: &resultBlock) return resultBlock }

Das große Bild

Jetzt sind wir bereit, unser Wissen auf reale Bilder anzuwenden. Lassen Sie uns mit diesem arbeiten:

Stellen Sie sich vor, wir hätten den Code, der dieses Bild als Zahlenarray lädt, wobei jede Zahl die Helligkeit eines Pixels an der entsprechenden Stelle darstellt:

 func loadImage(width: Int, height: Int) -> [Float] { ... }

Unter der Annahme, dass das Bild 256 x 256 Pixel groß ist, würden die folgenden Werte der oberen linken Ecke entsprechen:

 -2.00 3.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -2.00 4.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -3.00 -1.00 -8.00 -7.00 -6.00 -8.00 -14.00 -12.00 -7.00 -13.00 -9.00 -15.00 -15.00 -12.00 -23.00 -22.00 -18.00 -17.00 -11.00 -15.00 -11.00 -14.00 -20.00 -20.00 -21.00 -19.00 -20.00 -20.00 -18.00 -17.00 -19.00 -19.00 -16.00 -17.00 -20.00 -19.00 -17.00 -21.00 -24.00 -21.00 -19.00 -18.00 -20.00 -22.00 -19.00 -25.00 -20.00 -22.00

Aus mathematischen Gründen subtrahieren wir 128.0 , anstatt die Pixelhelligkeit als Zahl zwischen 0.0 und 255.0 auszudrücken. Mit anderen Worten: Wir zentrieren den Wert um 0.0 statt um 128.0 .

Dann wenden wir die dct -Funktion auf jeden 8x8-Block des Bildes an:

 let values: [Float] = loadImage() // convert RGB to -128.0 ... 128.0 var destinationValues: [Float] = Array(repeating: 0.0, count: values.count) for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { let block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) let resultBlock: [Float] = dct(block) storeBlock(values: &destinationValues, width: width, block: resultBlock, x: i * 8, y: j * 8) } } storeImage(destinationValues) // convert back to RGB

Das Ergebnis ist dieses Bild:

Auch wenn es auf dem Foto kaum zu erkennen ist, sind einige Muster (wie der Hut) immer noch sichtbar. Interessanterweise gibt es viele schwarze Pixel. Tatsächlich sind die meisten Pixel schwarz. Schauen wir uns einen der 8x8-Blöcke an:

Dieser 8x8-Block veranschaulicht, worum es bei der Frequenzbereichsdarstellung geht. Werte ungleich Null neigen dazu, sich in der oberen linken Ecke des Blocks zu häufen. Die Wahrscheinlichkeit eines großen Werts nimmt deutlich ab, wenn wir uns in die rechte untere Ecke bewegen.

Dies weist darauf hin, dass die Werte oben links eine größere Bedeutung für das Bild haben.

Wir können dies demonstrieren, indem wir eine „Komprimierungs“-Funktion schreiben, die einige der Werte unten rechts eliminiert, indem sie sie auf 0.0 setzt:

 func compress(_ block: [Float], level: Int) -> [Float] { var resultBlock: [Float] = block for y in 0 ..< 8 { for x in 0 ..< 8 { if x >= 8 - level || y >= 8 - level { resultBlock[y * 8 + x] = 0.0 } } } return resultBlock }

Nachdem wir unsere Verarbeitungsschleife angepasst haben:

 for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { var block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) block = dct(block) block = compress(block, level: 3) block = idct(block) storeBlock(values: &destinationValues, width: width, block: block, x: i * 8, y: j * 8) } }

Wir erhalten dieses Bild:

Nehmen Sie sich einen Moment Zeit, um darüber nachzudenken, was passiert ist. Wir haben 39 der 64 Werte für jeden Bildblock eliminiert und dennoch ein Bild erstellt, das dem Original sehr ähnlich ist. Dies ist ein Komprimierungsverhältnis von 60 %, das allein durch die Multiplikation von Matrizen und das deterministische Verwerfen von Daten erreicht wird!

Wenn wir 86 % der DCT-Koeffizienten verwerfen, passiert Folgendes:

Quantisierung

Es wäre unglaublich verschwenderisch, die DCT-Koeffizienten als Gleitkommazahlen zu speichern, die normalerweise 4 Byte Speicherplatz erfordern. Stattdessen sollten wir sie auf die nächste ganze Zahl runden. Bei 8x8-Blöcken kann jeder Wert durch eine 2-Byte-Ganzzahl dargestellt werden.

Schauen wir uns noch einmal den Block an, den wir zuvor untersucht haben. Seine (gerundete) numerische Darstellung ist:

 209 -296 -49 43 -38 22 -6 1 39 24 -37 11 -4 -3 2 6 -15 16 -17 0 13 -4 0 5 16 4 2 4 -6 4 -3 -5 -11 4 -1 3 1 -3 6 3 6 -2 2 4 -2 -2 -4 -1 -6 1 0 1 -1 0 3 -1 0 0 0 0 -1 -1 -2 1

Wie wir bereits visuell bestätigt haben, treten größere Werte eher näher an der oberen linken Ecke auf. Allerdings folgt nicht jeder Block diesem Muster. Hier ist ein weiterer Block aus unserem Bild:

Dieser Block entspricht nicht der allgemeinen Verteilung von DCT-Werten. Wenn wir die Werte unten rechts weiterhin blind verwerfen, können einige Teile des Bildes mehr Komprimierungsartefakte aufweisen. Um dies zu vermeiden, müssen wir entscheiden, welche Blöcke mehr Daten benötigen als andere.

Eine einfache, aber elegante Lösung nutzt die Clustering-Eigenschaft, die wir zuvor entdeckt haben. Man nennt es „Quantisierung“. Wir dividieren unsere DCT-Werte durch verschiedene Koeffizienten. Der Einfachheit halber verwenden wir eine Tabelle, die einen Wert für jeden DCT-Koeffizienten enthält:

 16.50 11.50 10.50 16.50 24.50 40.50 51.50 61.50 12.50 12.50 14.50 19.50 26.50 58.50 60.50 55.50 14.50 13.50 16.50 24.50 40.50 57.50 69.50 56.50 14.50 17.50 22.50 29.50 51.50 87.50 80.50 62.50 18.50 22.50 37.50 56.50 68.50 109.50 103.50 77.50 24.50 35.50 55.50 64.50 81.50 104.50 113.50 92.50 49.50 64.50 78.50 87.50 103.50 121.50 120.50 101.50 72.50 92.50 95.50 98.50 112.50 100.50 103.50 99.50

Den wichtigeren Positionen entsprechen niedrigere Teiler und umgekehrt. Wir führen den Dequantisierungsschritt durch, indem wir die quantisierten Daten mit den Koeffizienten aus der Tabelle multiplizieren.

Diese Funktionen führen Quantisierungs- bzw. Dequantisierungsschritte durch:

 func quantize(_ block: [Int], table: [Float]) -> [Int] { var result: [Int] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Int(round(Float(block[i]) / table[i])) } return result } func dequantize(_ block: [Int], table: [Float]) -> [Float] { var result: [Float] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Float(block[i]) * table[i] } return result }

Lassen Sie uns Quantisierung und Dequantisierung in unseren Code integrieren:

 block = dct(block) var iblock = rounded(block) iblock = quantize(iblock, table: testTable) block = dequantize(iblock, table: testTable) block = idct(block)

So sieht der erste Block quantisiert aus:

 13 -26 -5 3 -2 1 0 0 3 2 -3 1 0 0 0 0 -1 1 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 -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

Und das ist der zweite Block:

 -5 18 -10 0 1 1 1 0 0 3 1 -2 0 1 0 0 -4 0 1 0 1 1 0 0 -1 0 0 -2 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sie werden feststellen, dass es im zweiten Block weitere Werte ungleich Null gibt. Somit ermöglicht uns der Quantisierungsschritt, mehr nützliche Daten zu speichern und den Rest zu verwerfen.

Fazit und wie geht es weiter?

Von der grundlegenden Mathematik haben wir uns zum Kodieren und Dekodieren realer Bilder begeben. Wir haben visuell gesehen, wie das DCT beliebige Daten in eine Reihe von Frequenzen umwandelt und wie einige Frequenzen wichtiger sind als andere.

Nachdem wir uns mit der grundlegenden Komprimierung vertraut gemacht hatten, führten wir das Konzept der Quantisierung ein, das den Speicherbedarf weiter reduziert.

Im nächsten Teil gehen wir zu RGB-Bildern über und erkunden Möglichkeiten, die resultierenden Daten noch weiter zu komprimieren.

Den Code für diesen Artikel finden Sie unter https://github.com/petertechstories/image-dct