Ein Standbild komprimieren
Ein unkomprimiertes Farbbild ist ein Gitter aus Abtastwerten, und das Gitter ist groß. Gregory K. Wallace setzte beim JPEG-Vorschlag einen digitalisierten Farbrahmen in Fernsehauflösung auf die Größenordnung von einer Million Byte, einen Rahmen in 35-mm-Auflösung auf etwa das Zehnfache. Die Aufnahme kann billig sein. Die Datei bleibt zu schwer zum Lagern und zum Schicken. Diese Bytes sind Pixel. Vom Modell zum Pixel folgt einem davon vom Modell bis zum Schirm. Kompression ist der spätere Schnitt: dieselben Abtastwerte sollen weniger Platz auf der Platte und auf der Leitung brauchen.
Zwei Familien machen diesen Schnitt. Ein verlustfreies Verfahren legt jeden Abtastwert zurück. Ein verlustbehaftetes tut das nicht. Archive, medizinische Bilder, technische Zeichnungen, Clipart und Comics bleiben meist verlustfrei, denn ein veränderter Abtastwert ist eine andere Tatsache. Eine Fotografie kann etwas Treue ausgeben und stark schrumpfen. Ist der Unterschied zu klein, um ihn zu sehen, heißt das Ergebnis visuell verlustfrei. Drückt man die Rate weiter, wird der Schaden zeigbar: Blöcke, Höfe an Kanten, Farbe, die flach geworden ist.
Wallace setzte 1991 den damaligen Stand für ein typisches Bild auf grob ein Zehntel bis ein Fünfzigstel der Rohgröße, ohne eine Änderung, die ein Betrachter bemerken würde. Der Bruch ist eine Einstellung, kein Gesetz. Der Codierer muss dem Benutzer den Tausch überlassen.
Was das Auge hergibt
Eine Änderung der Helligkeit sieht man schärfer als eine Änderung der Farbe. Chroma-Unterabtastung behält das Helligkeitsgitter und mittelt Farbabtastwerte oder lässt sie weg. Eine zweite Sparform wirft die meisten Farben fort und behält eine kurze Liste. GIF und PNG können eine Palette im Kopf tragen, oft 256 Einträge. Ein Pixel speichert dann einen Index in diese Liste, nicht ein eigenes Rot, Grün und Blau. Dithering streut den Rundungsfehler als Sprenkel, damit eine glatte Rampe nicht in flache Bänder fällt. Blockpaletten gehen weiter: ein Feld von 4 mal 4 bekommt nur zwei oder vier Farben. BTC, S3TC und ihre Verwandten arbeiten so. Eine komprimierte Spieltextur wirkt deshalb aus der Nähe wie ein Plakat und aus der Ferne in Ordnung.
Acht mal acht
Gregory K. Wallace legte das siegreiche Verfahren dar in The JPEG Still Picture Compression Standard, Communications of the ACM, April 1991. Er leitete die Joint Photographic Experts Group bei der Digital Equipment Corporation. JPEG war gemeinsame Arbeit von ISO und CCITT, für Halbton-Standbilder, grau und farbig. Im Juni 1987 sah sich die Gruppe Bilder aus zwölf Vorschlägen an und behielt drei. Im Januar 1988 wählte eine zweite, strengere Sichtung die adaptive diskrete Kosinustransformation auf Blöcken von 8 mal 8. Die Jahre 1988 bis 1990 gingen in die Einzelheiten, damit die Datei des einen Herstellers auf der Maschine des anderen aufgeht. Als Wallace veröffentlichte, lag Teil 1 in der Abstimmung als Komitee-Entwurf: ISO/IEC CD 10918-1, begonnen im Februar 1991. Empfehlung T.81, der ITU-T-Text derselben Arbeit, trägt das Datum September 1992.
Die Kosinustransformation ist älter als das Komitee. Nasir Ahmed, T. Natarajan und K. R. Rao veröffentlichten sie 1974. Auf einem Block von 8 mal 8 ersetzt sie 64 Abtastwerte durch 64 Koeffizienten. Eine glatte Stelle legt fast ihre ganze Energie in die ersten, die niedrigen Frequenzen. Quantisierung teilt jeden Koeffizienten durch eine Stufe aus einer Tabelle und rundet. Dort liegt der Verlust. Hochfrequente Koeffizienten, die ein Betrachter am ehesten vermisst, runden oft auf null. Die Übriggebliebenen liest man im Zickzack, die Nullen sammeln sich zu einem langen Schwanz, und ein Huffman-Code schreibt die Läufe. David A. Huffman veröffentlichte diesen Code 1952 in den Proceedings of the IRE. Arithmetische Codierung ist der andere Entropiecodierer, den der JPEG-Entwurf zuließ. Der sequentielle Basis-Codec benutzt Huffman.
| Schritt | Was geschieht |
|---|---|
| Verschieben | Vorzeichenlose Abtastwerte werden vorzeichenbehaftet, die Null liegt in der Mitte |
| Vorwärts-DCT | 64 Abtastwerte werden 64 Kosinuskoeffizienten |
| Quantisieren | Jeder Koeffizient wird durch eine Tabellenstufe geteilt und gerundet |
| Zickzack | Die Koeffizienten werden so umsortiert, dass die Nullen zusammenrücken |
| Huffman | Null-Läufe und die verbleibenden Werte werden codiert |
Die Basisreihenfolge ist ein einziger Durchlauf, von links nach rechts, von oben nach unten. Farbe ist kein zweiter Algorithmus. Jede Komponente wird als eigenes Graubild komprimiert. Der Codierer kann eine Komponente zu Ende bringen und dann die nächste, oder er verschachtelt Blöcke von 8 mal 8 aus jeder Komponente der Reihe nach. Vor der Transformation werden Abtastwerte im Bereich 0 bis 2P−1 in vorzeichenbehaftete Werte verschoben. P ist die Bitzahl je Abtastwert.
Der Entwurf nannte drei weitere Betriebsarten. Progressive Codierung hält die Koeffizienten in einem Puffer und schickt mehrere Durchläufe, erst grob, dann klarer. Das will eine langsame Leitung: zuerst ein erkennbares Bild, den Rest, während man wartet. Verlustfreie Codierung gibt jeden Abtastwert zurück und komprimiert weniger. Hierarchische Codierung speichert mehr als eine Auflösung, sodass ein kleines Bild geholt werden kann, ohne das große zu entpacken.
Verfahren, die die Abtastwerte zurücklegen
Lauflängencodierung zählt einen Wert, der sich wiederholt, und schreibt die Zahl daneben. PCX benutzt das als gewöhnliches Verfahren. BMP, TGA und TIFF können es ebenfalls. LZW, von Abraham Lempel, Jacob Ziv und Terry Welch 1984, baut ein Wörterbuch aus Zeichenfolgen, die es schon gesehen hat. GIF, 1987 eingeführt, komprimiert mit diesem Wörterbuch, und TIFF kann das auch. DEFLATE, das Verfahren von Phil Katz, festgelegt in RFC 1951 im Mai 1996, ist der Kompressor in PNG, dazu in MNG und TIFF. PNG sagt einen Abtastwert zuerst aus seinen Nachbarn voraus und speichert den Fehler. DEFLATE komprimiert dann die Fehler. Die sind kleiner und gleichförmiger als die Abtastwerte selbst.
Eine Faxseite war der ältere Beweis, dass ein gemeinsamer Kompressor ein Gerät gewöhnlich machen kann. CCITT-Empfehlung T.4 von 1980 ist das Gruppe-3-Fax. Sie komprimiert zweistufige Marken, Farbe oder keine Farbe. Eine Fotografie komprimiert sie nicht. Wallace stellte JPEG gegen diese Grenze. Dieselbe Hoffnung auf ein Verfahren für viele Hersteller, diesmal für ein Bild, das Grau enthält.
Nach den Blöcken
JPEG 2000 wurde von 1997 bis 2000 ausgearbeitet. Die Kosinusblöcke von 8 mal 8 fallen weg. Der verlustbehaftete Weg benutzt das Wavelet CDF 9/7 von Albert Cohen, Ingrid Daubechies und Jean-Christophe Feauveau, von 1992. Der verlustfreie Weg benutzt das Wavelet 5/3 von Didier Le Gall und Ali J. Tabatabai, von 1988. 2004 wurde diese Familie, Motion JPEG 2000 eingeschlossen, als Bildcodierung für das digitale Kino gewählt. Eine harte JPEG-Quetschung zeigt ein Gitter, weil die Transformation nie über den Rand ihres Blocks hinaus sah. Ein Wavelet verteilt den Fehler anders. Bei kleinem Bitbudget wirft es Information trotzdem fort.
Das Spitzen-Signal-Rausch-Verhältnis bewertet den Abtastfehler mit einer Zahl. Die JPEG-Wahl von 1987 und 1988 fiel durch Hinsehen, das Verfahren blieb den Betrachtern verborgen. Eine Datei kann das Verhältnis gewinnen und trotzdem falsch aussehen. Ein Pfad in Skalierbare Vektorgrafiken ist nie in eine Transformation von 8 mal 8 gegangen. Flache Bilder: Pixel, Sprites und Vektoren ist die Trennung zwischen dieser Formenliste und dem Gitter, das diese Algorithmen verkleinern.