Datenkompression von Bildern, Videos und im Web am Beispiel von DXT1

Heutzutage ist Festplattenspeicher sehr bezahlbar geworden, und das Komprimieren von Daten, um Speicherplatz zu sparen, ist seltener geworden. Es gibt allerdings viele Gründe, Daten zu komprimieren, damit sie schneller über das Internet versendet werden können. Je nachdem, mit welcher Art von Daten und Komprimierung das geschieht, können im besten Fall 90 Prozent und mehr eingespart werden.

Einordnung zum Thema (Audio 🎧)

Verlustfrei vs. Verlustbehaftet

Eine Komprimierung kann verlustbehaftet oder verlustfrei sein.

1. Verlustfreie Komprimierung bedeutet, dass bei komprimierter Dateigröße die Bildqualität gleich bleibt – sie wird nicht schlechter. Außerdem kann die Datei auf ihre ursprüngliche Qualität dekomprimiert werden. Am Beispiel einer Word-Datei: Nach der Dekomprimierung dürfen keine Buchstaben fehlen, und auch die Formatierung muss 1:1 erhalten bleiben. Die Komprimierung muss also verlustfrei funktionieren.
2. Verlustbehaftete Komprimierung bedeutet, dass Daten dauerhaft verloren gehen. Auch wenn es um verlustbehaftet vs. verlustfrei geht, gibt es keine richtige oder falsche Wahl. Bei Bildern ist es selten nötig, wirklich die gesamte Qualität zu behalten; vor allem kleine Grafiken oder Dekorationen kommen häufig auch mit der halben Größe ohne visuell erkennbaren Unterschied aus.

Am Beispiel von DXT1?

DXT1 ist ein Format zur Speicherung von Texturen und Teil der S3TC-Familie (DXT1 bis DXT5). Die Daten werden verlustbehaftet komprimiert, um im Vergleich zu RGB888 83,3 % Speicherplatz im VRAM der Grafikkarte zu sparen. Erst 2018 lief das Patent des Algorithmus von S3 Graphics aus, nachdem es am 2. Oktober 2017 zuletzt für weitere 165 Tage verlängert worden war. Das originale Patent¹ wurde am 10. August 2004 zugelassen. Vor allem damals war der Grafikspeicher sehr begrenzt. Die GT 6800 von NVIDIA² kostete damals rund 400€³, also heute etwa 506,83 €, und brachte gerade einmal 256 MB GDDR3-Speicher mit.

Funktionsweise

1. Das Bild wird im ersten Schritt in 4×4 Pixel große Blöcke aufgeteilt. Bilder, die nicht genau zerteilbar sind, werden laut Spezifikation nicht unterstützt. Es ist in diesem Fall allerdings möglich, Bilder, deren Maße nicht x % 4 == 0 entsprechen, abzuschneiden oder aufzufüllen.
2. Aus jedem Block werden zwei Farben gewählt, um eine vierfarbige Palette zu interpolieren. Wenn die Farbe mit dem größeren Wert als Integer vorne steht, wird nur zwischen drei Farben interpoliert und der 4. Zustand wird für Transparenz genutzt. Pro Farbe der Palette werden allerdings nur zwei Byte (RGB565) verwendet. Da Pixel in der gleichen Umgebung meist sehr ähnliche Farben haben, reicht die geringe Vielfalt der Palette aus.
3. Jeder Pixel in dem Block (also den 4×4 Pixeln) wird auf die nächste Farbe gesetzt. Da die Palette nur vier Farben beinhaltet, kann pro Pixel die Farbe mit zwei Bits ausgedrückt werden. Der Block benötigt also vorher 16 * 3 Bytes = 48 Bytes und nun 2 * 2 Byte + 16 * 2 Bit = 8 Bytes.
4. Die Ergebnisse aller Blöcke werden im letzten Schritt hintereinander geschrieben.

Vielleicht sind Ihnen bei den Rechnungen bereits weitere Vorteile aufgefallen: Es ist bereits vor der Kompression bekannt, wie groß das Ergebnis ist, nämlich 1/6 des Originals. Da alle Blöcke hintereinander liegen, ist es einfach möglich, mit einer trivialen Verschiebungsrechnung die Adresse jedes einzelnen Pixels zu ermitteln: (⌊x / 4⌋ + ⌊y / 4⌋ * (Breite / 4)) * 8. Natürlich muss dafür außerdem die Palette berechnet werden.

Vorher / Nachher Bild

Beispiel Bild

Zu sehen ist ein 4×4-Pixel-Block vor und nach der Kompression. Zu erkennen ist, dass die Details leicht verloren gehen, das Bild aber noch deutlich erkennbar ist. Ebenfalls sichtbar ist, dass pro Block nur vier Farben verwendet werden.

Zierhut IT Favicon

Am Beispiel des Logos erkennt man, dass trotz nur zwei gespeicherten Farben pro Block das Bild optisch sehr gut aussieht, obwohl es nur noch 16,67 % der Originalgröße besitzt.

Verwendung in Spielen

In der Source Engine wird dieses Format innerhalb von VTF (Valve Texture File⁴) Dateien verwendet. Andere Spiele wie der Microsoft Flight Simulator⁵ nutzen ebenfalls diesen Algorithmus. Inzwischen ist DXT1 sehr verbreitet und Bestandteil von OpenGL⁶, WebGL⁷, Vulkan⁸ und DirectX⁹ Implementationen.