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, kann in den besten Fällen 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 Worddatei: Nach der Dekomprimierung dürfen keine Buchstaben fehlen und auch die Formatierung muss 1 zu 1 behalten bleiben, die Komprimierung muss also verlustfrei funktionieren.
2. Bei der verlustbehafteten Komprimierung gehen Daten dauerhaft verloren. 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, klar.

Am Beispiel von DXT1?

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

Funktionsweise

1. Das Bild wird im ersten Schritt in 4x4 Pixel große Blöcke aufgeteilt. Bilder, welche nicht genau zerteilbar sind, werden der Spezifikation nach nicht unterstützt. Es ist in diesem Fall allerdings möglich Bilder dessen Masse nicht x % 4 == 0 entsprechen, abzuschneiden oder aufzufüllen.
2. Aus jedem Block werden zwei Farben gewählt, um eine vier farbige Pallette zu interpolieren. Wenn die Farben mit dem größeren Wert als Integer vorne steht, wird nur zwischen 3 Farben interpoliert und der 4. Zustand wird für Transparenz genutzt. Pro Farbe der Palette werden allerdings nur zwei Byte, also RGB565 verwendet. Da meist Pixel in der gleichen Umgebung sehr ähnliche Farben haben, reicht die geringe Vielfalt der Palette aus.
3. Jeder Pixel in dem Block, also den 4x4 Pixeln, wird auf die nächste Farbe gesetzt. Da die Palette nur vier Farben beinhaltet, kann dann pro Pixel die Farbe mit zwei Bits ausgedrückt werden. Der Block nutzt also vorher 16 * 3 Bytes = 48 Bytes zu 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 noch die weiteren Vorteile aufgefallen: Es ist immer bereits vor der Kompression bekannt, wie groß dass Ergebnis ist, nämlich 1/6 des Originals. Da alle Blöcke nun auch hintereinander liegen, ist es also 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 4x4 Pixel Block vor und nach der Kompression. Zu erkennen ist, dass die Details leicht verloren gehen, das Bild aber noch deutlich erkennbar ist. Auch zu sehen ist, dass pro Block nur vier Farben verwendet werden.

Zierhut IT Favicon

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

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.