Make your own free website on Tripod.com

Les Mathématiques au service de la Compression des Images

 

Pour utiliser les images numériques, il faut comprimer les fichiers dans lesquels elles sont enregistrées. Voici comment on y parvient, sans les dénaturer.

L'image, bien plus que le son, consomme une quantité impressionnante d'octets quand elle est numérisée.

Pour s'en rendre compte, deux exemples suffisent. Aujourd'hui, on parle de « qualité megapixel » pour les appareils photo numériques ; cela signifie que chaque image comporte environ un million de pixels, chaque pixel nécessitant trois octets pour les composantes RVB (rouge, vert, bleu). Sans compression, cela représenterait un peu plus de 3 Mo pour une seule photographie. L’équivalent d'une pellicule de trente-six poses occuperait ainsi 100 Mo !

Pour remédier à ces contraintes, il n'y a qu'une solution : comprimer les images. Les chercheurs ont imaginé de nombreuses méthodes de compression, que l'on classe en deux catégories : celles qui se contentent de comprimer les données sans les altérer, et celles qui les compactent en les modifiant. Les premières, dites non destructives, permettent de reconstituer, au bit près, le fichier dans l'état où il était avant la compression (ce qui est indispensable pour du texte).

Jouer davantage sur les teintes que sur la luminosité

Quant aux secondes, les méthodes destructives, elles altèrent irrémédiablement les données de départ. Et ce sont elles qui servent presque toujours à comprimer les images (fixes ou aminées) sur les CD-Rom, sur les chaines numériques et sur Internet. Si la perte d'informations due à la compression n'apparaît généralement pas, c'est grâce à certaines caractéristiques de la vision humaine. Elles altèrent davantage les teintes que la luminosité. Notre oeil perçoit en effet plus facilement les grandes masses que les détails, et notre rétine est davantage sensible aux variations de lumière que de couleur.

Remplacer les motifs qui se répètent par des codes plus courts

Il en va tout autrement avec les méthodes sans perte. Elles laissent en effet le contenu des fichiers intact et n'agissent que sur la manière dont les informations sont codées. Les ordinateurs, comme on le sait, travaillent sur des séries de bits (des suites de zéros et de uns) souvent regroupés par paquets de huit, appelés octets. Ces méthodes s'affranchissent de ce découpage. Elles examinent la chaîne de 0 et de 1 et tentent de repérer des motifs. Par exemple, quatre zéros suivis de trois uns, de cinq zéros et de deux uns : 00001110000011. Si le motif se répète souvent, elles ne l’enregistrent pas tel quel, mais elles le remplacent par une codification différente, généralement plus courte. Elles font souvent l'objet de variantes, notamment la troisième, le codage de Huffman. Ces méthodes non destructives ne produisent pas des taux de compression spectaculaires , on divise par vingt le fichier dans les meilleurs cas.

Pour aller au-delà, il faut altérer les données d'origine. Le moyen économique pour y parvenir consiste à réduire le nombre de couleurs. Pour cela, il suffit de décider qu'une image, au lieu d'être reproduite en 16,8 millions de teintes, ne comportera plus que 256 couleurs. C'est le cas du format Gif. En choisissant judicieusement les 256 teintes de la palette, le résultat est spectaculaire, mais ne suffit pas si l'image doit être agrandie.

La méthode la plus connue est le JPeg qui permet d'obtenir des ratios de compression atteignant les 100:1 ! Dans la pratique, un taux avoisinant le 20:1 produit des images parfaitement exploitables, à l'affichage comme à l'impression.

Le procédé est long et complexe. D'abord l'image RVB est traduite dans une norme propre à la vidéo, qui définit le signal par la luminosité de chaque pixel ainsi que deux composantes associées à la couleur. Puis, elle est sous-échantillonnée ; chaque pixel conserve son information de luminosité, mais tout groupe de quatre pixels (deux horizontaux et deux verticaux) partage les mêmes données liées à la couleur, établies sur une moyenne. L’image est ensuite découpée en bloc de 8 x 8. Pourquoi pas 7 x 7 ou 12 x 12 ? Simplement parce que les expériences menées pour définir le standard JPeg ont montré que la valeur 8 était optimale. Après, tout se complique. On utilise une fonction mathématique, appelée DCT, pour modifier ces valeurs. Pour avoir une idée du procédé, il suffit de savoir que la représentation mathématique ainsi obtenue vise à transformer les variations de luminosité en fréquences. Le résultat est donc une série de soixante-quatre valeurs que l'on va encore simplifier selon le niveau de compression requis. C'est le paramètre que vous ajustez dans les fenêtres de dialogue des logiciels. Avec un taux de compression élevé, on a de nombreuses valeurs nulles dont le codage va être réduit par un algorithme sans perte, le RLE. Enfin, l'ensemble est encore comprimé par un codage de Huffman.

Au total, quatre méthodes de compression ont été employées, ce qui explique qu'une photographie de 20 Mo puisse être réduite à 1 Mo (elle tient alors sur une disquette) tout en conservant un assez bon niveau de qualité.

La compression dite fractale

Des procédés concurrents existent, notamment la compression dite fractale développée par la société Iterated Systems. Elle repose sur la constatation que toute image, avec un degré d'approximation plus ou moins grand, peut être représentée par des portions d'elle-même que l'on modifie (déplacement, rotation, changement de taille ... ). L’algorithme consiste donc à découper une image en secteurs et à identifier ceux à partir desquels on va pouvoir produire les autres. Le fichier est alors composé par ces blocs de référence et par les fonctions mathématiques servant à recalculer le reste. La technique, très lente à la compression, est en revanche rapide à la décompression. Elle permet aussi, quand on agrandit une image, d'éviter tout effet de mosaîque (pixelisation), puisque l'agrandissement ne revient pas à afficher chaque pixel en plus grand, mais à recalculer l'image mathématiquement.

La compression par ondelettes

En dehors de cette dernière méthode, c’est la compression par ondelettes - qui semble avoir le vent en poupe, au point qu'il sera inclus dans la norme JPeg 2000. A qualité visuelle égale, il offre un taux de compression moyen de 40: 1, contre 20: 1 pour les deux autres méthodes. Il consiste à diminuer les dimensions de l'image par un processus en cascade (l'original produit quatre images de taille réduite, l'une étant une véritable image en réduction, les trois autres apportant des informations permettant de reconstituer l'image à pleine définition). Le processus est alors appliqué à nouveau sur l'image de taille réduite, et on le répète plusieurs fois. La compression proprement dite consiste à ignorer les informations les moins significatives. Le codage et le décodage sont très rapides et, quand les données sont transmises par Internet, le procédé permet d'afficher instantanément une image grossière dont les détails s'affinent progressivement, (comme certaines variantes du JPeg).

Les Techniques de Compression dans le domaine de la Vidéo

La compression d'une image fixe est dite spatiale, car elle ne fait pas intervenir le facteur temps.

Pour la vidéo, on utilise aussi, le plus souvent, une compression dite temporelle qui exploite les ressemblances existantes entre une image et les précédentes.

Le Standard MJPEG

La norme M-JPeg (Motion JPeg), associée aux cartes d'acquisition, comprime le signal pendant l'acquisition grâce à un codec matériel. Ce dernier est une puce ultra puissante qui convertit en JPeg chacune des vingt-cinq images du signal vidéo. Ce format nécessite une trés grande puissance de calcul et donc un équipement approprié mais est très utile en cas de montage numérique, permettant de faire de l’édition sur des images distinctes.

Mais ce standard MJPeg n'est pas utilisé par toute la communauté vidéo.

On peut en dire autant des codecs employés dans le cadre du montage vidéo sur PC ou Mac pour créer un fichier AVI ou QuickTime. Et qu'ils s'appellent Intel Indeo, Radius Cinepak ou Sorenson, ils ne sont pas utilisés pour diffuser des chaînes numériques ou produire des DVD.

Le standard MPeg : voir les différences.

En fait au fil des années, c’est le standard MPeg (Motion picture expert group) qui s'est imposé. Il définit à la fois un format de fichier et la méthode de compression.

La compression MPeg repose sur deux procédés complémentaires. Le premier consiste à considérer certaines images indépendamment des autres ; le second revient à exploiter les informations qui se retrouvent d'une image à l'autre, ce qui se produit souvent en vidéo. Périodiquement, le système enregistre des images complètes codées en jpeg . ce sont les images dites I, qui servent de référence pour analyser les autres images. Pour ces dernières, on détecte et on enregistre seulement les différences qu'elles présentent.

Le MPeg1 a été exploité, sans grand succès, par Philips pour le CD-video tandis que le MPeg2 est devenu un standard mondialement reconnu, en raison du niveau de qualité qu'il procure et de son ouverture vers la télévision haute définition. Le MPeg1 et le MPeg2 procèdent d'une manière similaire pour comprimer les images. Ce qui les distingue, c'est la définition (respectivement 352 x 288 et 720 x 576) et le débit maximal: 1, 5 kbps pour MPeg1 et 15 kbps pour MPeg2. Le standard MPeg définit la structure du fichier comprimé, mais elle n'impose aucun algorithme de compression. Mais quel que soit le procédé utilisé pour coder, le MPeg n'est pas, actuellement, en passe d'être supplanté par un autre format. Les recherches en cours s'attachent à adapter les images au multimédia et à l'interactivité. C'est l'objet des standards MPeg4 et MPeg7, le premier venant d'être finalisé et le second étant prévu pour 2001.

Quelques domaines d’application

Faute de moyens de stockage d'une capacité suffisante pour un encombrement et un prix réalistes, de nombreuses applications n'auraient pas été possibles sans la compression. Celle-ci a aussi permis d'atteindre les débits nécessaires pour transmettre les images ou la vidéo.

La télécopie

Elle repose sur un mode de compression sans perte devenu un standard nommé CCITT Groupe 3. Ce dernier est adapté aux images ne présentant que des zones blanches ou noires. Ce mode de compression n'est autre que le procédé de Huffman, utilisé après étude statistique sur le contenu des télécopies pour définir la table de codage

La diffusion d'images sur Internet

Pour réduire le plus possible la taille des pages Web, toutes les images et les photographies qu'elles contiennent sont comprimées. Les formats les plus employés sont le Gif (limité à 256 couleurs avec une compression LZW) ou le JPeg.

La photo numérique

En raison de leur capacité relativement faible (2 et 4 Mo à leur sortie, 128 Mo à 320 Mo actuellement), les cartes de mémoire flash des appareils photo numériques ne conviendraient pas au stockage d'images en haute définition, sans la compression. Le format jpeg est majoritairement employé, avec des niveaux de compression modérés (entre 4:1 et 16: 1).

La vidéo numérique

Le format DV(Digital Video)définit un mode de compression spécifique, chaque image étant traitée individuellement selon un procédé proche du JPeg. Cela permet ensuite de faire du montage à l'image près, sans difficulté.

Le DVD

Le DVD utilise le MPeg2 pour stocker plus de deux heures de vidéo sur une couche d'un disque, qui peut en comporter deux sur chaque face. Le niveau de compression est variable, les scènes très animées consommant plus de place que les vues statiques.

La télévision numérique

Transmettre la vidéo numérique par satellite coûte cher. Pour multiplier le nombre d'émissions diffusées, les opérateurs, grâce au format MPeg2, divisent par dix la quantité des informations à véhiculer. La télévision haute définition, récemment lancée aux États Unis, exploite également le MPeg2.

Ce texte est inspiré en grande partie de l’article de Laurent Katz (Ordinateur Individuel)