Comprimer une image fixe
Une image couleur non compressée est une grille d'échantillons, et la grille est grande. Gregory K. Wallace, en décrivant la proposition JPEG, situait une trame couleur numérisée à la résolution de la télévision dans l'ordre du million d'octets, et une trame à la résolution du 35 mm à environ dix fois cela. La prise de vue peut coûter peu. Le fichier reste trop lourd à garder ou à envoyer. Ces octets sont des pixels. Du modèle au pixel en suit un, du modèle jusqu'à l'écran. La compression est la coupe d'après : les mêmes échantillons doivent occuper moins de disque et moins de fil.
Deux familles font cette coupe. Une méthode sans perte remet chaque échantillon en place. Une méthode avec perte ne le fait pas. Archives, images médicales, dessins techniques, cliparts et bandes dessinées restent en général sans perte, parce qu'un échantillon modifié est un fait modifié. Une photographie peut dépenser un peu de fidélité et rétrécir fort. Si la différence est trop petite pour qu'on la voie, on parle de résultat visuellement sans perte. On baisse encore le débit, et le dégât se montre du doigt : des blocs, des halos le long des bords, une couleur devenue plate.
Wallace plaçait, en 1991, l'état de la technique autour d'un dixième à un cinquantième de la taille brute pour une image typique, sans changement qu'un spectateur remarquerait. La fraction est un réglage, pas une loi. Le codeur doit laisser l'utilisateur choisir l'échange.
Ce que l'œil peut céder
Un changement de luminosité se voit plus nettement qu'un changement de couleur. Le sous-échantillonnage de la chroma garde la grille de luminosité et moyenne, ou simplement abandonne, une partie des échantillons de couleur. Un second gain jette la plupart des couleurs et garde une liste courte. GIF et PNG peuvent porter une palette dans l'en-tête, souvent 256 entrées. Un pixel stocke alors un indice dans cette liste, pas un rouge, un vert et un bleu à lui. Le tramage disperse l'erreur d'arrondi en moucheture, pour qu'un dégradé lisse ne tombe pas en bandes plates. Les palettes par bloc vont plus loin : un carré de 4 par 4 ne reçoit que deux ou quatre couleurs. BTC, S3TC et leurs cousins travaillent ainsi. Une texture de jeu compressée a l'air d'une affiche de près, et tient de loin.
Huit par huit
Gregory K. Wallace a exposé la méthode retenue dans The JPEG Still Picture Compression Standard, Communications of the ACM, avril 1991. Il animait le Joint Photographic Experts Group, chez Digital Equipment Corporation. JPEG était un travail commun de l'ISO et du CCITT, pour les images fixes à tons continus, grises et en couleur. En juin 1987, le groupe a regardé les images de douze propositions et en a gardé trois. En janvier 1988, un second examen, plus strict, a choisi la transformée en cosinus discrète adaptative, sur des blocs de 8 par 8. Les années 1988 à 1990 ont servi à écrire le détail, pour qu'un fichier d'un fabricant s'ouvre sur la machine d'un autre. Quand Wallace a publié, la partie 1 était au vote comme projet de comité : ISO/IEC CD 10918-1, ouvert en février 1991. La recommandation T.81, texte UIT-T du même travail, est datée de septembre 1992.
La transformée en cosinus est plus vieille que le comité. Nasir Ahmed, T. Natarajan et K. R. Rao l'ont publiée en 1974. Sur un bloc de 8 par 8, elle remplace 64 échantillons par 64 coefficients. Une zone lisse met presque toute son énergie dans les premiers, les basses fréquences. La quantification divise chaque coefficient par un pas tiré d'une table, puis arrondit. La perte est là. Les coefficients de haute fréquence, ceux qu'un spectateur risque le moins de regretter, tombent souvent à zéro. On lit les survivants en zigzag, ce qui rassemble les zéros en une longue queue, et un code de Huffman écrit les suites. David A. Huffman a publié ce code en 1952, dans les Proceedings of the IRE. Le codage arithmétique est l'autre codeur d'entropie que le projet JPEG autorisait. Le codec séquentiel de base utilise Huffman.
| Étape | Ce qui se passe |
|---|---|
| Décalage | Les échantillons non signés deviennent signés, zéro au milieu |
| DCT directe | 64 échantillons deviennent 64 coefficients en cosinus |
| Quantification | Chaque coefficient est divisé par un pas de table et arrondi |
| Zigzag | Les coefficients sont réordonnés pour que les zéros se groupent |
| Huffman | Les suites de zéros, et les valeurs qui restent, sont codées |
L'ordre de base est un seul balayage, de gauche à droite, de haut en bas. La couleur n'est pas un second algorithme. Chaque composante est compressée comme sa propre image grise. Le codeur peut finir une composante puis passer à la suivante, ou entrelacer des blocs de 8 par 8 pris à chaque composante tour à tour. Avant la transformée, les échantillons de l'intervalle 0 à 2P−1 sont décalés vers des valeurs signées. P est le nombre de bits par échantillon.
Le projet prévoyait trois autres façons de tourner. Le codage progressif garde les coefficients dans un tampon et envoie plusieurs balayages, grossier puis plus net. C'est ce que veut une ligne lente : une image reconnaissable d'abord, le reste pendant l'attente. Le codage sans perte rend chaque échantillon et compresse moins. Le codage hiérarchique stocke plus d'une résolution, et une petite image peut être lue sans décompresser la grande.
Méthodes qui remettent les échantillons
Le codage par plages compte une valeur qui se répète et écrit le compte à côté. PCX s'en sert comme méthode ordinaire. BMP, TGA et TIFF peuvent en faire autant. LZW, d'Abraham Lempel, Jacob Ziv et Terry Welch en 1984, fait grossir un dictionnaire des chaînes déjà vues. GIF, introduit en 1987, compresse avec ce dictionnaire, et TIFF le peut aussi. DEFLATE, la méthode de Phil Katz, spécifiée dans le RFC 1951 en mai 1996, est le compresseur de PNG, et aussi de MNG et de TIFF. PNG prédit d'abord un échantillon d'après ses voisins et stocke l'erreur. DEFLATE compresse ensuite les erreurs, plus petites et plus répétitives que les échantillons.
Une page de télécopie a été la preuve plus ancienne qu'un compresseur partagé peut rendre une machine ordinaire. La recommandation T.4 du CCITT, de 1980, est la méthode de télécopie du groupe 3. Elle compresse des marques à deux niveaux, encre ou pas d'encre. Elle ne compresse pas une photographie. Wallace a placé JPEG contre cette limite. Le même espoir d'une méthode pour beaucoup de fabricants, cette fois pour une image qui contient du gris.
Après les blocs
JPEG 2000 a été préparé de 1997 à 2000. Il abandonne les blocs en cosinus de 8 par 8. La voie avec perte utilise l'ondelette CDF 9/7 d'Albert Cohen, Ingrid Daubechies et Jean-Christophe Feauveau, de 1992. La voie sans perte utilise l'ondelette 5/3 de Didier Le Gall et Ali J. Tabatabai, de 1988. En 2004, cette famille, Motion JPEG 2000 compris, a été retenue comme codage d'image pour le cinéma numérique. Une compression JPEG très forte montre une grille, parce que la transformée ne regardait pas au-delà du bord de son bloc. Une ondelette étale l'erreur autrement. Elle jette quand même de l'information quand le budget de bits est petit.
Le rapport signal sur bruit de crête note l'erreur d'échantillon par un seul nombre. Les choix JPEG de 1987 et de 1988 se sont faits en regardant, la méthode cachée aux spectateurs. Un fichier peut gagner le rapport et avoir l'air faux. Un tracé dans Le graphique vectoriel adaptable n'est jamais entré dans une transformée de 8 par 8. Images plates : pixels, sprites et vecteurs est la séparation entre cette liste de formes et la grille que ces algorithmes réduisent.