4. Compression des images et des sons :
des données fortement corrélées

Une image informatique peut être assimilée à un tableau de pixels, organisé en lignes et colonnes, dont chaque élément a une valeur. La définition de cette valeur est obtenue par une ou plusieurs données numériques (généralement une pour les images monochromes, trois pour les images couleurs en représentation RVB, YUV ou YCC), ou bien par une adresse dans une table de couleurs prédéfinies, la palette (Color Look Up Table, ou CLUT).

Cependant, on constate que la couleur d'un pixel est souvent très proche, voire identique à celle des pixels contigus. Statistiquement, il y a toujours une forte corrélation entre les valeurs des pixels d'une même zone d'image, et cette spécificité peut être mise à profit pour compacter les données. Cette caractéristique est souvent désignée par le terme de “ redondance spatiale ”.

Dans le cas de phénomènes variant en fonction du temps, comme le son ou les images animées, une autre corrélation peut être mise en évidence entre des mesures successives, et elle est d'autant plus importante que la fréquence de mesure est élevée. C'est la redondance temporelle.

La quantification de ces corrélations, tant au niveau spatial pour les images fixes que temporel pour les sons et les images animées, constitue la mesure de redondance des informations. Cette notion, directement issue des travaux de Shannon, doit être prise au sens de la théorie de l'information, et non au sens commun : chaque information élémentaire se voit attribuer une quantité d'information, d'autant plus élevée qu'elle est “ nouvelle ”, c'est-à-dire non déductible du contexte. Cette quantité, évaluée en pourcentage, permet de définir également la mesure de redondance associée, qui est le complément à 1 de la quantité d'information.

Alors que, au sens commun, la redondance est liée au caractère plus ou moins superflu des informations, elle est, pour Shannon, une simple mesure mathématique indiquant sa compressibilité théorique. Aucune donnée d'une image ou d'un son n'est totalement redondante, car cela signifierait qu'elle peut être à coup sûr déduite du contexte. La “ suppression des redondances ” comme description d'une technique de compression n'a donc aucun sens, puisque aucune des informations élémentaires ne présente de redondance totale.

En fait, l'ensemble des techniques de compression des images exploitent la corrélation entre des pixels voisins pour produire une “ valeur probable ” du prochain pixel à coder. Le produit de cette prédiction étant statistiquement proche de la valeur réelle, il est alors possible d'effectuer le codage de manière plus économique, par exemple simplement en codant uniquement la différence avec la valeur prédite. Les ordres de grandeur des valeurs à transmettre sont alors statistiquement plus faibles, ce qui permet d'utiliser un nombre plus faible de bits, soit en codage de longueur fixe, soit en longueur variable (méthode statistique).

4.1. Codage par répétition : le “ Run Length Encoding ”

Le procédé “ Run Length ” ne relève pas d'une théorie mathématique très complexe. Il s'agit simplement de remplacer des éléments signifiants successifs identiques par un seul d'entre eux, suivi du nombre de répétitions (un exemple de traitement RLE est donné en annexe). Ce procédé peut paraître simpliste et peu performant si on cherche à l'appliquer, par exemple, à un texte : même dans notre belle langue française, les répétitions nombreuses de lettres n'apporteraient qu'une compression dérisoire ! En revanche, si on l'applique à une image, en particulier d'origine infographique, il est aisé de s'apercevoir que les plages de couleur homogènes sont souvent importantes, surtout si le nombre de couleurs est faible, et l'image limitée à la colorisation de quelques centaines de pixels, sur un fond uniforme...

Particulièrement simple à mettre en œuvre, c'est un procédé qui a été largement utilisé par les logiciels de dessin dans les années passées, éventuellement associé à un autre algorithmes plus complexes. Dans certains cas, le RLE est utilisé pour les images animées, sans aucune exploitation de la redondance temporelle.

Procédé

Si n octets successifs sont dans un même état, il est aisé de transmettre l'octet répété et le nombre de répétitions. On pourra ainsi, dans la plupart des cas, coder sur 3 octets les n octets composant le signal initial. Dans le cas de textes, voire de fichiers binaires, cette analyse exclusivement réalisée au niveau des octets successifs n'apporterait qu'une faible amélioration ; en revanche, dans le cas d'images bit map (codées pixel par pixel), et particulièrement pour les dessins réalisés “ à main levée ”, les plages de répétition sont considérables (zones de couleurs homogènes), et les résultats beaucoup plus probants.

S'il est relativement simple de coder l'octet à répéter, suivi du nombre de répétitions dans l'octet suivant, cette méthode peut se révéler très pénalisante pour certains fichiers : à la limite, si deux octets consécutifs sont toujours différents, le volume du fichier “ compressé ” sera le double de celui du fichier initial ! Pour éviter cet inconvénient, les versions les plus avancées du codage Run Length utilisent un code discriminant pour indiquer le début d'une séquence “ octet à répéter + nombre de répétitions ”, les octets isolés restant codés sous leur forme initiale.

Performances

On le comprendra aisément, un tel codage ne peut apporter des performances considérables, mais il présente l'avantage de la simplicité. Cette méthode convient mieux à des dessins bit map, mais peut apporter des résultats comparables pour des images naturelles en 256 couleurs. Au delà (codages sur 4 096 couleurs et plus), les résultats obtenus se révèlent plus décevants, les pixels identiques étant moins fréquents.

En pratique, on obtient des gains de compression de 30 à 50 % dans la plupart des cas pour les dessins, sensiblement moins pour les images naturelles.

Implémentations

Le format PCX de Z-soft, repris à son compte par Microsoft avec les différentes implémentations de Paintbrush, sans doute un des plus répandus des formats graphiques, utilise ce mode de compression. Après un en-tête de 127 octets contenant diverses informations sur le codage (taille de l'image, nombre de plans, nombre de bits par pixel, ainsi éventuellement que des informations de palette), on rencontre les données compressées selon ce principe. Dans le cas où l'image est codée selon des plans de couleur (RVB par exemple), le codage se fait ligne par ligne, successivement dans les différents plans (par exemple, en VGA 16 couleurs, ligne 1 dans les quatre plans, puis ligne 2 dans les quatre plans, etc.).

Le codage Run Length est également largement utilisé dans les différents modes de télécopie développés par le CCITT (télécopie groupes 3 et 4 en particulier), généralement associé à un codage statistique de Huffman.

Les extensions multimédias de Windows reconnaissent également les fichiers RLE, qui sont une version compressée Run Length du format BMP. Ce format n'a guère connu de succés auprès des éditeurs, qui préfèrent en utiliser d'autres plus répandus (PCX ou TIFF par exemple), ou directement le format BMP non compressé.

Le CD-I de Philips, parmi d'autres formats graphiques, utilise deux formats Run Length codés respectivement sur deux octets avec une palette sur sept bits (CLUT 7) et sur un octet avec une palette sur trois bits (CLUT 3).

La méthode Run Length se révèle inutile lorsque les systèmes d'exploitation ou des utilitaires de bas niveau (Dblspace de DOS 6.0, Stacker...) mettent eux mêmes en œuvre des dispositifs plus performants (généralement LZx). L'utilisation de ces outils, qui travaillent directement au stade des écritures sur disques rend la methode Run Length totalement inutile : on ne constate pratiquement aucune différence de taille après compactage entre les fichiers soumis non compressés et ceux qui ont été traités par Run Length au préalable.

4.2. Les compressions dégradantes

Les procédés évoqués plus haut ne produisent pas de dégradation, et relèvent à ce titre du compactage plus que de la compression. Dès que l'on accepte de perdre des informations, fussent-elles jugées superflues, on entre dans le domaine de la compression dégradante. Se pose alors la question de la limite acceptable à la perte d'informations, de la sélection des critères opportuns et des paramètres à retenir pour estimer la qualité de restitution. Le contexte sémantique n'étant pas sans importance, l'appréciation est largement subjective. Dans le cas des images, par exemple, il est difficile d'évaluer objectivement la pertinence des informations, et l'appréciation ne peut que faire intervenir des éléments subjectifs. On comprendra aisément que les impératifs de séparation des couleurs, notamment, ne sont pas les mêmes sur un tableau de Van Gogh et sur une photo architecturale, et qu'aucun algorithme ne peut faire cette différence !

Plusieurs modes d'appauvrissement sont envisageables, qu'il faudra choisir en fonction de l'image à traiter et des besoins. Le nombre de niveaux de couleurs peut être réduit, éventuellement en utilisant une table d'indexation, selon des méthodes très simples... ou très complexes. Le résultat peut se révéler très convaincant, mais au prix de temps de calcul parfois très longs. Également, le nombre de points de la définition initiale devra être adapté au mode de restitution utilisé, et aux besoins liés à l'image concernée (par exemple, remplacement de blocs de 2 x 2 pixels par leur valeur moyenne).

Rappelons que la numérisation du son est obtenue en découpant le signal en fines tranches de temps (échantillonnage, généralement à 11, 22 ou 44 kHz) puis en l'évaluant par rapport à une échelle numérique de référence (quantification) [Dos. Ing., n°13, 1993]. La numérisation d'une image fixe, quant à elle, s'effectue au travers d'un échantillonnage en zones géographiques sur la surface de l'image, suivi d'une quantification par rapport à une échelle de représentation du signal lumineux ; cette représentation peut se faire par rapport aux couleurs primaires RVB, comme c'est généralement le cas en informatique, ou en séparant les informations de luminance et de chrominance, selon des techniques couramment pratiquées en vidéo (Y/C, YUV, YCC) [Cavet, 1994].

Dans bien des cas, l'information obtenue après numérisation peut se révéler trop fine pour la chaîne de restitution envisagée. Par exemple, les dispositifs de visualisation ne disposent pas tous des 24 bits généralement utilisés pour coder les couleurs, et la qualité des haut-parleurs utilisés rend souvent tout à fait superflue une définition d'enregistrement de type CD-Audio. Une analyse soignée de la pertinence des informations conservées, tenant compte de l'ensemble de la chaîne jusqu'à la restitution finale, permet de réduire considérablement la quantité des données conservées, sans dégradation lors de la restitution. Pourtant, une telle opération consiste déjà en une altération de la source, et relève donc bien d'une compression dégradante. En outre, ce type de traitement ne peut se concevoir que dans le cas de l'élaboration d'un support de diffusion, adapté à une chaîne de restitution précise ; dans le cas d'un archivage, en revanche, il sera nécessaire de prévoir une définition sensiblement plus fine, pour prévenir des besoins futurs.

D'autre part, nombre d'informations, si elles sont technologiquement restituables, sont peu ou pas perceptibles à l'oreille ou à l'œil humains. La prise en compte de la sensibilité de nos organes perceptifs permet, là encore, de minimiser les flux d'informations. Cette méthode a été utilisée très tôt en téléphonie, mais également en vidéo : l'œil étant plus sensible à la luminance qu'à la chrominance, les codages YCC et YUV notamment codent beaucoup moins finement les couleurs que l'intensité lumineuse elle-même (sous-échantillonnage de la chrominance).

Dans le cas d'images animées, on sait, depuis les origines du cinéma, que le mouvement est rendu par une succession d'images fixes à une fréquence suffisante pour la perception de l'œil humain (généralement 25 images par seconde). Chacune de ces images doit donc être traitée de la même manière qu'une image fixe lors de la numérisation. Pourtant, là encore, la quantité de données dépendra de la technologie choisie. Les paramètres retenus pour la numérisation de chaque image devront entrer en ligne de compte, mais aussi le nombre d'images par seconde (25 avec les procédés vidéo européens, 30 en NTSC), et la technique de restitution (affichage par trames entrelacées par exemple).

Cependant, s'il est possible d'adapter les paramètres de numérisation ou de codage lorsqu'on connait les caractéristiques de l'ensemble de la chaîne de restitution, ainsi que les utilisations qui sont envisagées (démarche éditoriale), cette démarche est beaucoup risquée lorsque le but de l'opération est l'archivage. Dans ce cas, en effet, on ignore quelles seront les performances des matériels utilisés dans quelques années, et, surtout, il est probablement tout à fait déraisonnable d'abandonner des informations alors que l'on ignore le type d'exploitation qui sera fait, quelquefois des années plus tard. Ainsi, le Photo CD conserve des images numérisées dans une définition seize fois plus fine que celle qui est nécessaire pour un téléviseur, pour garantir les possibilités d'utilisations futures ; et, dans bien des cas, on considère que le meilleur moyen de conserver des films ou des séquences vidéo reste les supports traditionnels argentiques ou magnétiques, tous encore analogiques.

4.3. Les méthodes prédictives : compression différentielle et différentielle adaptative

Dans le cas de sons numérisés, on peut constater que les niveaux de deux échantillons successifs présentent statistiquement une différence faible. On dira qu'il y a une forte corrélation entre le signal obtenu sur un échantillon donné et à l'échantillon précédent, ou encore, au sens de la théorie de l'information, que ses informations présentent une forte redondance.

De même, dans le cas des images, il est aisé de constater qu'il y a une forte corrélation spatiale entre un pixel et la zone qui l'entoure : dans la très grande majorité des cas, les images, naturelles ou de synthèse, présentent de larges zones dont les couleurs sont très proches (ciel, mer, constructions, etc.).

Pour les images animées, quiconque a regardé par transparence un morceau de film a pu constater que les images successives sont très souvent quasi semblables. À la corrélation spatiale évoquée plus haut s'ajoute donc une corrélation temporelle, sans doute encore plus forte.

4.3.1. Les méthodes différentielles : procédés

Méthode différentielle simple

Une première étape pour réduire la taille des données est de transmettre non plus la valeur de l'échantillon, mais celle de la différence avec l'échantillon précédent, qui est statistiquement inférieure et peut donc être codée sur un nombre de bits plus réduit. L'utilisation de ce principe pour un codage non dégradant (entièrement reversible) suppose cependant un codage des différences entre deux échantillons avec un codage à longueur variable, à la manière de la méthode de Huffman. Or, une telle méthode, qui suppose une analyse statistique préalable de l'ensemble des données, n'est pas adaptée à ce type d'utilisation : d'une part, elle ne peut être appliquée en temps réel (analyse et compression en deux passes), et, d'autre part, elle nécessite des traitements de décodage plus complexes qui peuvent se révéler incompatibles avec les matériels de restitution grand public envisagés.

La restitution du son pouvant souvent s'accommoder de quelques pertes d'informations, la solution généralement retenue est un codage de toutes les données selon un nombre identique de bits, plus réduit que la définition originale de la quantification. Par exemple, dans le cas de sons numérisés sur 8 bits, le codage différentiel sera effectué sur seulement 4 bits, ce qui divise le flux de données par deux. En revanche, les sauts d'amplitude supérieure à 4 bits entre deux échantillons successifs ne pourront être fidèlement restitués, mais ils sont statistiquement peu fréquents.

Exemple

Dans le cas d'une numérisation du son sur 8 bits (256 niveaux), à 22 kHz, un codage différentiel sur 4 bits (16 niveaux) occasionnera au maximum un retard de 16 échantillons pour transmettre une variation d'amplitude maximale, maintenue durant une durée égale au moins à 16 échantillons. Un tel évènement est fort improbable, et le retard moyen constaté (et donc la perte de qualité) se révèle proche de zéro. Les données transmises sont équivalentes en volume à un codage à 11 kHz sur 8 bits, avec une qualité de restitution généralement bien supérieure.

Dans le cas des images fixes, on peut également utiliser une méthode différentielle, par ligne, ou par colonne. Chaque pixel sera alors codé à partir de la différence avec le pixel précédent, et on peut alors appliquer les méthodes Huffman ou LZ aux données obtenues. Ce codage, largement utilisé par le passé, suppose néanmoins des traitements assez lourds (calcul des différences et codage LZW) et se révèle de moins en moins performant lorsque le nombre de couleurs augmente. Dans ce cas, il est nécessaire de réaliser un codage en 3 plans monochromes (RVB ou YCC) pour obtenir de bons résultats.

On peut également citer le format DYUV exploité par le CD-I, qui ne code totalement que le premier pixel de chaque ligne, les autres étant codés par différence avec l'élément précédent.

Méthode différentielle adaptative

Le procédé peut être amélioré en réalisant une “ prédiction ” plus précise que la simple prise en compte de la valeur de l'échantillon précédent. Cela peut par exemple, dans le cas du son, être réalisé par extrapolation de la vitesse de variation du signal sur les échantillons précédents. La valeur délivrée par le prédicteur est alors celle de l'échantillon précédent, corrigée en tenant compte de la moyenne des variations constatées sur quelques échantillons passés. Le codage ainsi obtenu permet, avec un même nombre de bits de codage, des altérations largement plus réduites qu'avec la méthode différentielle simple.

La compression d'images peut également être réalisée en calculant une valeur théorique probable pour un pixel à partir des pixels voisins, et en codant la différence entre l'état réel du pixel et cette prédiction. Les méthodes classiques de compactage, comme celles de Huffman ou de Lempel-Ziv, permettent alors de réduire la taille des données obtenues. Dans le cas le plus simple, la prédiction est réalisée à partir de la moyenne des pixels de l'image, le coefficient de corrélation des pixels consécutifs, et l'unique valeur du pixel précédent.

L'algorithme obtenu est disymétrique : le codage, qui comprend une analyse préalable de la totalité de l'image, se révéle largement plus complexe que le décodage. Des procédés plus élaborés peuvent être utilisés en étendant l'environnement à un plus grand nombre de pixels (souvent 8), ainsi qu'en découpant l'image de base en plusieurs images plus réduites (souvent 8x8 pixels), ce qui permet de réduire l'écart type.

Pour les images animées, les procédés d'extrapolation utilisés pour le son peuvent permettre de prédire le mouvement, mais il est souvent plus efficace de le traduire sous forme d'un vecteur obtenu par interpolation entre deux images distantes. Cependant, dans ce cas, les images doivent être traitées dans un ordre différent de celui de la restitution, ce qui contribue à rendre les traitements plus complexes, notamment en ce qui concerne le codage.

Performances

Dans le cas de la compression de données sonores, les codages différentiels et différentiels adaptatifs (DPCM et ADPCM) offrent des résultats satisfaisants. La qualité de restitution est directement fonction des paramètres de numérisation, en particulier la fréquence d'échantillonnage et le nombre de valeurs disponibles sur l'échelle de quantification (8 bits : 256 valeurs ; 16 bits : 65 536 valeurs). Un codage DPCM ou ADPCM sur un nombre de bits divisé par 2 offre un encombrement équivalent à une fréquence d'échantillonnage divisée par 2, avec une qualité largement supérieure.

Dans tous les cas, le rapport de compression envisageable sans dégradation sensible ne peut dépasser 10. En effet, le signal sonore est unidimensionnel et présente une corrélation beaucoup moins forte que les images.

La compression d'images selon ces méthodes donne des gains de compression temporelle très variables, selon la nature des données (entre 20 et 80 %), mais qui se détériorent lorsque le nombre de couleurs augmente. Les algorithmes prédictifs introduisent la notion de traitement dissymétrique, le codage étant beaucoup plus complexe (et long) que le décodage.

Implémentations

Sons : les méthodes DPCM et ADPCM sont largement utilisées en téléphonie, pour laquelle elles ont été élaborées. Elles sont reprises dans le cadre des spécifications Windows Multimédia (DPCM), CD-ROM XA et CD-I (ADPCM).

En ce qui concerne les images, le format GIF, développé par Compuserve, utilise la méthode différentielle, associée aux méthodes de compactage traditionnelles LZ et Huffman.

4.4. Au secours : les maths reviennent !

L'utilisation de transformations mathématiques permet de remplacer les valeurs produites par la numérisation par des données de nature différente qui peuvent se révéler plus faciles à compresser.

Signal vocal de numérotation téléphonique (touche 4) et sa décomposition spectrale
obtenue par transformation de Fourier

Parmi les transformations mathématiques les plus connues, la transformation de Fourier permet de traduire une variation de signal par rapport au temps dans le domaine fréquentiel (décomposition spectrale). On démontre en effet que tout phénomène oscillatoire peut être décomposé en une combinaison de fonctions trigonométriques simples (décomposition en série de Fourier) ; chacune d'entre elles est alors caractérisée par des coefficents (amplitude et fréquence), qui peuvent être représentées par un diagramme en batonnets des différentes fréquences présentes.

Concernant des signaux numérisés, qui sont des représentations discrètes (le nombre de valeurs par unité de temps est fini et connu) de phénomènes oscillatoires, on peut utiliser la transformation de Fourier discrète (Fast Fourier Transform ou FFT). Elle exploite les mêmes principes que la décomposition en série de Fourier, mais, contrairement à elle, produit une décomposition en une somme finie de valeurs fréquentielles, ce qui lui donne la propriété d'être entièrement reversible. En pratique, on définit aussi la transformation inverse (IFFT ou Inverse Fast Fourier Transform) qui restitue fidèlement les données initiales. En outre, les calculs nécessaires à cette transformation sont une succession de multiplications et d'additions, très rapidement exécutables par un processeur simple.

4.4.1. La transformation cosinus discrète, ou DCT

Dans le cas d'images fixes, il s'agit d'analyser un signal ne variant plus en fonction du temps, mais bien en fonction de la position du pixel dans le pseudo-plan de l'écran ; c'est une transformation de même nature que la transformée de Fourier qui est invoquée, mais opérant en fonction des coordonnées X et Y du pixel. La Transformation Cosinus Discrète (DCT ou Discrete Cosine Transform) permet de décomposer le signal lumineux composant l'image (X et Y pour les coordonnées du pixel, Z pour sa définition lumineuse) selon une combinaison de fonctions trigonométriques, identifiables par leur fréquence et leur amplitude.

Application de la DCT à un pavé de 8 pixels de coté.

Elle traduit cette information spatiale en une information fréquentielle (spectrale), X et Y représentant alors les fréquences du signal dans ces deux dimensions (horizontale et verticale).

Comme la FFT, la DCT est une transformation entièrement reversible (IDCT, inverse de la DCT restitue fidèlement les données initiales), et son application n'est à l'origine d'aucune perte d'information.

En pratique, l'image est généralement codée en YUV, et traitée comme trois “ images ” monochromes ou plans. La DCT est alors appliquée successivement aux données du plan de luminance (Y) et des 2 plans de chrominance (U, V). Pour limiter le nombre d'opérations à effectuer, la transformation est appliquée à des zones rectangulaires de l'écran, généralement de 8 x 8 pixels.

1 : décomposition d'une image en 3 plans YUV

2 : découpage de chaque plan en pavés de 8 x 8 pixels et application de la DCT

La DCT produit elle même une matrice de 64 coefficients (8 x 8 ), rangés selon les fréquences croissantes selon les axes horzontal et vertical. Généralement, la plus grande partie de l'énergie est concentrée dans les basses fréquences du spectre qui sont exprimées par les coefficients les plus proches du coin supérieur gauche de la matrice.

Matrice des valeurs de luminance des pixels et sa transformée DCT [Terrasson, 1992]

Représentation des données issues de la DCT

Représentations d'une matrice de pixels et de sa transformée DCT.
On remarque clairement l'importance de la valeur supérieure gauche de la matrice,
qui correspond à la moyenne des pixels de la zone.

(Pixel (x,y) désigne la valeur du pixel de coordonnées (x,y) et DCT(i,j) le coefficient repéré par la ligne i et la colonne j dans la matrice DCT.

La DCT existe : je l'ai rencontrée !
Transformations DCT et IDCT appliquées à un pavé de N x N pixels

La compression sera réalisée ultérieurement sur cette matrice en remplaçant progressivement les coefficients les moins significatifs (ceux proches du coin inférieur droit de la matrice) par des approximations de plus en plus grossières, selon des échelles de quantification bien définies ; pour des gains supérieurs, on ignorera les valeurs les plus proches du coin inférieur droit de la matrice. Le décodeur utilisant alors un intervalle de valeur et non la valeur exacte, la précision des valeurs du bloc de pixel reconstruit par l'IDCT est réduite.

Le coefficient supérieur gauche de la matrice (coordonnées 0,0) représente une fréquence horizontale et verticale nulle ; il est proportionnel à la valeur moyenne des pixels du bloc traité et permet donc à lui seul une prédiction du bloc de 8 x 8, voire la reconstruction d'une image de prévisualisation par pavés de 8 x 8 (compression théorique du bloc N x N : 1/N²). Ainsi, la DCT permettra d'effectuer aisément une compression dégradante en éliminant progressivement les informations les moins pertinentes.

4.4.2. Vers d'autres transformations mathématiques

Après la FFT et DCT, les ondelettes !

Si les transformées de Fourier et autres DCT rendent de considérables services, elles sont à l'origine plus adaptées aux traitements de signaux continus stationnaires (par exemple les signaux utilisés en radio), et seules des versions dérivées appauvries sont utilisées en traitement numérique. Dans le secret des laboratoires de recherche, on travaille aujourd'hui à de nouvelles transformations qui décomposent le signal non pas en fonctions sinusoïdales simples, mais en des fonctions moins régulières, les “ fonctions en ondelettes ”. Il s'agit ici de décomposer le signal en une combinaison de morceaux d'ondes, ce qui équivaut à un filtrage en sous-bandes, utilisé dans les techniques de compression audio.

Bien plus adaptée au traitement des images numériques, les transformations en ondelettes permettront sans doute dans un avenir proche d'obtenir de bien meilleurs taux de compression, avec une moindre dégradation. Cependant, l'utilisation de telles méthodes suppose dans bien des cas la réalisation de processeurs spécialisés ; compte tenu de l'antériorité des méthodes fondées sur la DCT, et de la banalisation des processeurs correspondants, on peut se poser des questions sur l'avenir de méthodes alternatives, aussi prometteuses soient-elles.

Fractales : le retour !

La décomposition fractale des images est une autre piste souvent évoquée par les chercheurs. Il s'agit ici de déterminer point par point une ou des fonctions mathématiques particulières (les fonctions fractales) dont les valeurs approcheront au mieux l'image initiale. Si le traitement initial est important (il s'agit de trouver point par point la fonction qui approche le mieux le signal), la décompression est de nature toute différente puisqu'il s'agit alors “ seulement ” d'appliquer la fonction trouvée.

Essentiellement dissymétriques, les algorithmes fractals semblent pouvoir offrir des gains de compression considérables, sous réserve de disposer de capacités de calcul suffisantes (la compression d'une image superVGA peut prendre jusqu'à une dizaine de minutes avec un 486 DX 33).

Les premiers logiciels et matériels de compression fractale sont commercialisés aux Etats Unis, et même importés, quoiqu'un peu confidentiellement, en France. Ils sont aujourd'hui capables de traiter une image 640 X 480, 16 millions de couleurs en quelques minutes pour la compression, alors que l'affichage se fait plus rapidement que pour les images JPEG équivalentes (moins d'une seconde). Un taux de compression de 1 % (!), vérifiable par la taille du fichier (de 900 ko à 9 ko), permet d'afficher une image sans dégradation notable, alors qu'une compression JPEG dans les mêmes proportions ne permet la restitution que d'un vague damier.

Encore convient-il de préciser que ce procédé ne convient pas à tous types d'images. Une particularité de cette méthode est qu'elle produit un codage entièrement vectorisé, et ne conduit donc à aucun effet de pixélisation. Il est même possible de restituer l'image à une définition supérieure à celle de départ (généralement 2 fois plus fine) ! Bien entendu, les points intermédiaires sont produits par calcul, à partir de la fonction fractale obtenue, sans rapport direct avec l'image de départ. Si l'image traitée est suffisamment “ régulière ”, le résultat peut être étonnant, mais il peut également se révéler décevant dans le cas de contours très finement ciselés.

Le logiciel Images Incorporated, de la société Iterad System Inc, est disponible auprès de la société Image etc. (environ 3 500 F HT), qui diffuse également une boîte à outils de développement (Color Box Compression SDK). Une carte d'extension, permettant une compression plus rapide, est également proposée.

Ce procédé a été notamment utilisé par Microsoft pour l'encyclopédie Encarta. Il permet de stocker un très grand nombre d'images sur un support (par exemple, 10 images 640 X 480 en 16 millions de couleurs sur une disquette), mais requiert un logiciel spécifique pour la décompression. L'absence de normalisation de cette solution reste cependant une limite à son exploitation.

4.4.3. Les processeurs de traitement du signal

Tous les appareils numériques, même les plus simples, nécessitent un traitement de nature informatique pour soumettre un signal à un périphérique de restitution qui est le plus souvent... analogique (haut-parleur, moniteur). Ainsi, les lecteurs de disques laser et autres consoles de jeux font appel à des circuits spécialisés, les processeurs de traitement du signal ou DSP (Digital Signal Processor).

Comme son nom l'indique, le processeur de signal numérique intervient pour traiter un signal issu, pour tous les dispositifs de mesure physique, d'un capteur qui fournit une variation de tension, donc de nature analogique. Avant de l'exploiter de manière numérique, il est donc nécessaire de le coder à travers un convertisseur ADC (Analogic Digital Converter), puis de le transmettre au DSP. Tous les calculs nécessaires à un traitement de signal numérique pourraient être effectués par un processeur traditionnel, mais avec des performances catastrophiques. En effet, une simple multiplication demande près de 20 cycles d'horloge sur un processeur de type Intel i386 ou Motorola 68 030, alors qu'un multiplieur câblé n'utilisera que deux cycles. De tels dispositifs existent dans les coprocesseurs arithmétiques, intégrés ou non aux processeurs principaux (i486, Pentium), mais ils sont alors conçus pour des calculs à virgule flottante, alors que les signaux numériques n'utilisent que des entiers. Des composants spécialisés ont donc été développés et se sont rapidement répandus avec la diffusion considérable des équipements numériques (CD-Audio, consoles de jeux, etc.). Leur application la plus connue est le traitement du son dans les CD-Audio, mais ils sont souvent également utilisés en télécommunications (télécopie, transfert de données, liaison Numéris) et de plus en plus pour les applications informatiques exploitant des données numérisées.

Les diverses fonctions que peut avoir un DSP relèvent généralement de l'analyse et du filtrage du signal, et éventuellement de sa compression, lorsqu'elle n'est pas entièrement logicielle ou confiée à un autre processeur spécialisé. La plupart des calculs de filtrage ou d'analyse du signal ne sont pas effectués sur le signal lui-même, mais sur sa décomposition spectrale, obtenue par des transformations de type FFT ou DCT. Les DSP sont donc conçus pour s'adapter au mieux à ce type de transformation, et calculent aujourd'hui une FFT de 10 à 20 fois plus vite qu'un processeur traditionnel. En particulier, ces traitements faisant appel à de multiples séquences de multiplications et additions d'entiers, les DSP sont dotés d'une unité arithmétique de conception spécifique, le MAC (Multiply And Accumulate) capable d'effectuer un produit et de l'ajouter au résultat précédent en un seul cycle d'horloge.

De même, la formule de la DCT citée plus haut montre à l'évidence que son exécution (mais c'est le cas pour bien d'autres traitements confiés au DSP) doit être réalisée par de nombreuses boucles, chaque itération étant constituée d'un nombre réduit d'opérations. La gestion du compteur de boucle, qui constitue une partie non négligeable du traitement, est confiée à un module spécialisé qui permet de décharger le MAC de cette tâche.

Pour accéder à ces diverses fonctions, les DSP de dernière génération sont dotés d'un jeu d'instructions spécifique : ce sont des processeurs programmables (tout au moins à un niveau élémentaire), et il devient ainsi possible de les utiliser pour effectuer des traitements variés, de les adapter à l'exécution de multiples algorithmes. Aujourd'hui réservés à des équipements informatiques particuliers (cartes sonores, équipement de digitalisation/restitution), ils équiperont demain directement la carte mère des micro-ordinateurs, à l'image des Macintosh AV. Plus tard, progressivement, ces circuits seront directement intégrés au processeur principal.

Les processeurs spécialisés dans les traitements de l'image comme le i750 d'Intel ou le C450 de C-Cube sont en fait de supers DSP, intégrant l'équivalent de plusieurs DSP classiques, mais aussi des convertisseurs ADC/DAC, et des circuits logiques câblés pour la mise en œuvre d'algorithmes préprogrammés. Les plus récents disposent même de larges possibilités de programmation pour exploiter de nouveaux algorithmes.

4.4.4. Les méthodes modernes : les images fixes JPEG / JBIG

Le CCITT et l'ISO ont réuni dans les années quatre-vingt le groupe JPEG (Joint Photographic Experts Group) qui a permis l'adoption en 1992 de la norme ISO/CEI 10 918, plus connue sous le nom de norme JPEG. Dans le même temps, des travaux comparables conduisaient à l'adoption de la norme ISO/CEI 11 544, plus connue sous le nom de JBIG.

JPEG et JBIG sont des ensembles de spécifications et algorithmes de compression des images fixes. Leur statut de norme officielle constitue une évolution essentielle puisque cela permettra sans doute la réalisation de processeurs spécialisés à bas prix, fabriqués à grande échelle, qui pourront être intégrés dans de nombreuses machines.

Chacune de ces normes est en fait composée de plusieurs techniques de compression, incluant notamment des spécifications pour un codage conservatif (entièrement reversible) et pour un autre dégradant. Dans le second cas, il s'agit de codages adaptables, dont le comportement peut varier en fonction des images à traiter, mais aussi des contraintes liées au matériel utilisé.

Le cahier des charges défini à l'origine des travaux du comité JBIG ciblait davantage les besoins d'un puissant algorithme pour la transmission des images, notamment en télécopie. Ce procédé est donc particulièrement adapté pour les images monochromes, ainsi que pour les images codées sur un petit nombre de couleurs. En outre, ce codage prévoit d'une part une restitution séquentielle, ligne à ligne, particulièrement adaptée à la télécopie, et d'autre part une décompression progressive de qualité croissante, par pavés (imagette, définition écran, ou haute définition pour l'impression).

JPEG propose également un mode progressif et un mode séquentiel, mais il est originellement prévu pour des images en 16 millions de couleurs (24 bits par pixel). Il a été élaboré pour permettre aussi bien une exécution logicielle que la réalisation de circuits spécialisés.

Les travaux des comités ISO ont montré que les algorithmes JBIG donnent de meilleurs résultats que JPEG lorsque chaque pixel est codé sur moins de 8 bits.

Dans les deux cas, l'image est découpée en un damier, chaque zone obtenue étant ensuite traitée indépendamment. Chaque pavé ainsi obtenu (généralement 8 x 8 pixels) est considéré comme une matrice de pixels sur laquelle peut être appliquée la transformée DCT.

La technique conservative combine les techniques de codage prédictif/adaptatif avec les méthodes statistiques de Huffman, qui produit une compression conservative optimale (taux de 50 % environ). Les travaux du groupe JPEG sont pourtant essentiellement connus pour les compressions non conservatives.

Procédé

Les algorithmes JPEG et JBIG de compression non conservative sont fondés sur les propriétés de le transformation DCT.

Les images couleur sont généralement codées comme trois images monochromes. Le codage de base des données représentant chaque pixel ne fait l'objet d'aucune spécification, mais c'est le YUV qui est généralement utilisé. L'image est tout d'abord découpée en zones de dimensions réduites (8 x 8 pixels), puis chaque pavé est traité par la DCT. La compression, selon un taux laissé au choix de l'utilisateur, est effectuée par quantification des coefficients issus de cette décomposition spectrale. Cette étape est la seule à l'origine des dégradations. Enfin, les données obtenues sont codées sous une forme elle-même compressée au moyen des algorithmes conservatifs décrits plus haut (Huffman essentiellement).

Performances

Les compressions/décompressions successives sont toujours dégradantes, avec un effet cumulatif, et il convient donc de limiter ces opérations. On estime généralement qu'une image JPEG ne contenant aucune information superflue (définition en nombre de points et de couleurs conforme au dispositif de restitution) tolère sans dégradation notable un taux de compression de l'ordre de 1 pour 10 ou 13. L'affichage d'une image “ plein écran ” peut prendre environ 1 seconde sur un Macintosh 68 040 ou un PC Intel i486. En outre, il faut noter que l'extension multimédia Quicktime du système d'exploitation du Macintosh supporte le codage JPEG.

Cependant, les images couleur sont généralement codées en “ vraies couleurs ” sur 24 bits par pixel, alors que les dispositifs d'affichage ne sont pas aussi performants (mémoire vidéo insuffisante notamment) ; l'affichage en un nombre de couleurs plus réduit (4 ou 8 bits) se fait au moyen de tramages coûteux en termes de temps de traitement, qui rendent la restitution plus laborieuse.

Implémentations

Une fraction croissante des logiciels de traitement d'images exploitent actuellement le format JPEG, en importation comme en exportation. Près d'une dizaine de processeurs spécialisés sont également disponibles sur le marché. L'extension Quicktime du Système 7 d'Apple assure le traitement JPEG directement au niveau du système d'exploitation.

Il faut également signaler des versions dérivées de JPEG adaptées au codage de la vidéo animée, connue sous le nom de M-JPEG (Moving JPEG ou Motion JPEG). La méthode retenue consiste en un codage de chaque image selon le procédé JPEG, avec un taux de compression optimal, compte tenu de la bande passante disponible. Ces procédés souffrent cependant d'une absence de normalsation.

Sommaire

Suite