Table des Matieres :

II.1 INTRODUCTION 

       A présent, l’ordinateur peut être associé à des analyseurs d’images, des caméras, des appareils photo, des scanners, des modulateurs de transmission, etc.., sans oublier les logiciels et les liaisons avec des banques de données. Ainsi secondé, il devient appareil de saisie de l’information, enregistreur, machine de traitement, machine de création ou d’aide à la création, appareil de diffusion de tous messages audiovisuels et autres, en d'autres termes : machines à communiquer.

Les supports traditionnels (papier, disque, bande) peuvent être remplacés par un support unique et universel, la mémoire de l’ordinateur ( RAM , Disque dur , ...), ce que tente d’exprimer le vocable “ multimédia ”. Le seul facteur de limitation à ces techniques réside pour le moment dans l’énorme espace mémoire exigé par les images.

Un moyen réduisant le volume global des images tout en conservant l’image originale, consiste en la compression des images avec le minimum de dégradation et le maximum d’efficacité possible.

Les méthodes de compression et de codage réduisent le nombre de bits par pixel à stocker ou à transmettre, en exploitant la redondance informationnelle dans l’image.

Les principaux critères d’évaluation de toute méthode de compression sont :

 La qualité de reconstitution de l’image;

‚ Le taux de compression;

ƒ La rapidité du codeur et décodeur (codec).

II.3 Principe general de la COMPRESSION des images

Le schéma fonctionnel de la compression est présenté dans la figure ci-dessous :

Décorrélation  [GAM 92]

La dépendance existante entre chacun des pixels et ses voisins (la luminosité varie très peu d’un pixel à un pixel voisin) traduit une corrélation très forte sur l’image. On essaie donc de tirer partie de cette corrélation, pour réduire le volume d’information en effectuant une opération de décorrélation des pixels.

La décorrélation consiste à transformer les pixels initiaux en un ensemble de coefficients moins corrélés, c’est une opération réversible.

Quantification  [BOU 92][SAD 93]

La quantification des coefficients a pour but de réduire le nombre de bits nécessaires pour leurs représentations. Elle représente une étape clé de la compression. Elle approxime chaque valeur d’un signal par un multiple entier d’une quantité q, appelée quantum élémentaire ou pas de quantification. Elle peut être scalaire ou vectorielle. Un des résultats fondamentaux des travaux de Shannon concernant la relation :

montrent que l’on obtient de meilleures performances en utilisant la quantification vectorielle.

Codage [ABD 95]

Une fois les coefficients quantifiés, ils sont codés. Un codeur doit satisfaire à priori les conditions suivantes :

• Unicité : deux messages différents ne doivent pas être codés de la même façon.
• Déchiffrabilité : deux mots de codes successifs doivent être distingués sans ambiguïté.

Plusieurs types de codage seront détaillés ci-après.

II.4 classification des methodes [dek 96]

La plupart des méthodes de compression visent à enlever la redondance présente dans l’image de manière à diminuer le nombre de bits nécessaires à sa représentation.

Plusieurs types de redondance en terme de corrélation peuvent être considérés :

 La redondance spatiale entre pixels ou blocs voisins dans l’image;

‚ La redondance temporelle entre images successives dans une séquence vidéo;

Les méthodes de compression peuvent se regrouper, en deux classes :

 Les méthodes sans perte d’information (sans distorsion ou réversible );

‚ Les méthodes avec perte d’information (avec distorsion ou irréversible).

Les expérimentations menées montrent que généralement les méthodes qui atteignent des taux de compression très élevés sont les méthodes avec distorsion. Par contre, les méthodes sans distorsion engendrent des taux de compression très faibles et ne sont utilisées que dans des applications sensibles telles que les images médicales et les images satellites.

II.5 methodes sans distorsion des donnees

Elles permettent de retrouver exactement les pixels de l’image numérique originale.

3. Shannon du laboratoire Bells et R. M. Fano du MIT ont développé à peu près en même temps une méthode de codage basée sur de simples connaissances de la probabilité d’occurrence de chaque symbole dans le message.

Le procédé de Shannon-Fano construit un arbre descendant à partir de la racine, par divisions successives. Le classement des fréquences se fait par ordre décroissant, ce qui suppose une première lecture du fichier et la sauvegarde de l'en-tête .

1. Classer les n fréquences non nulles {f_i} par ordre décroissant.
2. Répartir la table des fréquences en deux sous tables de fréquences proches. Poursuivre l’arborescence jusqu'à ce que toutes les fréquences soient isolées.
3. Attribuer dans l’arborescence le bit 0 à chaque première sous table.
4. Attribuer aux symboles les codes binaires correspondant aux bits de description 1 de l’arborescence.

II.5.2 codage de huffman [had 97]

Le codage de Huffman crée des codes à longueurs variables sur un nombre entier de bits. L’algorithme considère chaque message à coder comme étant une feuille d’un arbre qui reste à construire. L’idée est d’attribuer aux deux messages de plus faibles probabilités, les mots codés les plus longs. Ces deux mots codés ne se différencient que par leur dernier bit. Contrairement au codage de Shannon-Fano qui part de la racine des feuilles de l’arbre et, par fusions successives, remonte vers la racine.

1. Répartir les fréquences f(i) des lettres .
2. Classer les symboles dans l’ordre décroissant des fréquences d’occurrence. Le résultat de l’algorithme ne change donc pas si l’on remplace les fréquences f_i par les probabilités .
3. Regrouper par séquences les paires de symboles de plus faible probabilité, en les reclassant si nécessaire. Plus précisément : calculer s = f(i_n) + f(i_n-1), la somme des deux plus faibles fréquences.
4. Choisir le plus petit indice k tel que s soit supérieur ou égal à f(i_k), remplacer k par k+1.
5. Recomposer la table des fréquences en plaçant à la k ^ème position la valeur s et en décalant les autres d’une position vers le bas. Puis décrémenter n d’une unité, poursuivre jusqu'à ce que la table des fréquences ne comporte plus que deux éléments.

6.Coder avec retour arrière depuis le dernier groupe, en ajoutant un 0 ou un 1 pour différencier les symboles préalablement regroupés.

Exemple de code de Huffman :

Soit la source ayant un alphabet de 8 symboles avec les probabilités ci-dessous :

II.5.3 codage arithmetique [had 97]

Contrairement aux algorithmes de Huffman et de Shannon-Fano qui associent à des symboles des motifs binaires dont la taille dépend de leur distribution. Le codeur arithmétique traite le fichier dans son ensemble, en lui associant un unique nombre décimal rationnel.

Ce nombre compris entre 0 et 1, possède d’autant moins de chiffres après la virgule que le fichier dont il est redondant. Ces chiffres décimaux dépendent non seulement des symboles du fichier dans l’ordre où ils apparaissent, mais aussi de leur distribution statistique.

Algorithme du codage arithmétique :

 Calculer la probabilité associée à chaque symbole dans la chaîne à coder.

‚ Associer à chaque symbole un sous intervalle proportionnel à sa probabilité, dans l’intervalle [0,1] (l’ordre de rangement des intervalles sera mémorisé car il est nécessaire au décodeur).

ƒ Initialiser la limite inférieure de l’intervalle de travail à la valeur 0 et la limite supérieure à la valeur 1.

„ Tant qu’il reste un symbole dans la chaîne à coder :

- largeur = limite supérieure - limite inférieure

- limite inférieure = limite inférieure + largeur x (limite basse du sous intervalle du symbole)

- limite supérieure = limite inférieure + largeur x (limite haute du sous intervalle du symbole)

… La limite inférieure code la chaîne de manière unique.

II.5.4 methode statistique (entropique ) [nel 93]

Le principe est d’associer à chaque pixel de l’image un mot de code dont la longueur dépend de la probabilité d’apparition du niveau de gris correspondant.

Pour obtenir un codage efficace, il suffit d’associer les mots de code les plus courts aux niveaux de gris ayant les plus fortes probabilités d’apparition et inversement pour les niveaux présentant une faible probabilité.

Les méthodes statistiques sont aussi connues sous le nom de méthodes VLC (Variable Lengt Code). Elles peuvent être combinées avec d’autres schémas de codage telles que les méthodes par transformée ou prédictives.

II.5.5 methode des plages [abd 95]

Lorsqu’on considère une ligne de la matrice représentant une image numérique, plusieurs échantillons successifs sur cette ligne peuvent posséder la même valeur. L’ensemble de ces échantillons est appelé “ plages ”. Cette méthode consiste donc à décrire les suites des pixels identiques par leur longueurs et leur valeurs. Par exemple, une plage de vingt pixels noirs équivaut à la donnée de 2 nombres :20 et 0.

II.6 methodes avec distorsion des donnees

Ces méthodes permettent de retrouver une approximation de l’image numérique. Les pertes sont généralement indécelables à l’œil nu.

ii.6.1 quantification vectorielle [had 97]

Les techniques de compression d’images exploitent généralement la redondance statistique présente dans l’image. La quantification scalaire qui associe à une variable

continue une variable discrète pouvant prendre un nombre plus faible, et fini de valeurs. Ces valeurs ne sont jamais totalement décorrélées, ou indépendantes. Shannon a montré qu’il était toujours possible d’améliorer la compression de données en codant des vecteurs plutôt que des scalaires.

Dans la suite de cette thèse, l’abréviation (QV) sera utilisée pour désigner la quantification vectorielle.

La QV, développée par Gersho et Gray [GRA 84] a pris une place très importante dans le domaine de la compression d’image que ce soit dans le but de transmission ou d’archivage.

Principe de la quantification vectorielle

La quantification vectorielle dans son sens le plus général est l’approximation d’un signal d’amplitude continue par un signal d’amplitude discrète. Elle peut être vue comme une application Q associant à chaque vecteur d’entrée x de dimension K un vecteur y = Q(x) de même dimension appartenant à un ensemble fini Y appelé DICTIONNAIRE de taille finie N,

Y = (y_j , j = 1...N).

Elle se décompose en deux applications : codeur, décodeur :

Codeur :

Le rôle du codeur consiste, pour tout vecteur x_i du signal en entrée à rechercher dans le dictionnaire Y le code vecteur y_j le plus proche du vecteur source x. C’est uniquement l’adresse du code vecteur y_j ainsi sélectionnée qui sera transmise ou stockée. C’est à ce niveau donc que s’effectue la compression.

Decodeur :

Il dispose d’une réplique du dictionnaire et consulte celui-ci pour fournir le code vecteur d’indice correspondant à l’adresse reçue. Le décodeur réalise l’opération de décompression.

Figure II. 3: Principe du quantificateur vectoriel

Où Min_j(x,y_j) = distorsion minimale entre les vecteurs x et y_j.

II.6.2 Méthodes par transformee [ahm 75][and 69]

Dans ces méthodes, l’image de dimension NxN est subdivisée en sous images ou blocs de taille réduite (la quantité de calcul demandée pour effectuer la transformation sur l’image entière est très élevée). Chaque bloc subit une transformation mathématique orthogonale inversible linéaire du domaine spatial vers le domaine fréquentiel, indépendamment des autres blocs (transformée en un ensemble de coefficients plus ou moins indépendants). Les coefficients obtenus sont alors quantifiés et codés en vue de leur transmission ou de leur stockage. Pour retrouver l’intensité des pixels initiaux, on applique sur ces coefficients la transformation inverse. Parmi les transformations linéaires existantes :

 Transformation de Karhunen-Loeve ( TKL ).

‚ Transformation de Fourrier discrète ( TFD ).

ƒ Transformation de Hadamard ( TH ).

„ Transformation de Haar ( THA ).

… Transformation en cosinus discrète (TCD).

Le principe d’un système de codage par transformation est le suivant :

Figure II.4 : Principe d'un système de codage par transformation

Transformation en Cosinus Discrète (TCD) [abd 95]

C’est une transformation mathématique qui transforme un ensemble de données d’un domaine spatial en un spectre de fréquence et inversement ( ITCD ). C’est la plus utilisée parmi les transformations citées.

Elle permet schématiquement de changer d’échelle de mesure, passant d’une échelle

définissant un pixel en fonction de sa position en x et en y à une échelle définissant la fréquence d’apparition de ce pixel dans un bloc de pixels, en effet, il est dés lors possible de supprimer des informations sans pour autant altérer le résultat final, contrairement à un bloc de pixels où la disparition brute de plusieurs éléments est immédiatement visible [MIC 92].

La TCD est effectuée sur une matrice carrée N*N de valeurs de pixels et donne une matrice carrée N*N de coefficients de fréquence. Le temps de calcul requis pour chaque élément dans la TCD dépend de la taille de la matrice.

Vu la difficulté d’appliquer la TCD sur la matrice entière, celle-ci est décomposée en blocs de taille 8*8 pixels.

A la sortie de la matrice de la TCD, la valeur de la position (0,0) est appelée le coefficient continu, cette valeur représente une moyenne de la grandeur d’ensemble de la matrice d’entrée, ce coefficient est plus grand d’un ordre de grandeur à toute valeur dans la matrice de la TCD, par convention, les 64 valeurs transformées (de chaque bloc) sont positionnées d’une certaine manière, ainsi la valeur moyenne de tous ces coefficients est placée en haut à gauche de ce bloc [MIC 92]. Plus on s’éloigne des coefficients continus plus leur grandeurs tendent à diminuer. Ce qui signifie que la TCD concentre la représentation de l’image en haut à gauche de la matrice de sortie, les coefficients en bas et à droite de cette matrice contient moins d’information utile.

Les équations qui suivent, donnent respectivement la transformée en cosinus discrète directe et inverse.

Pour u,v = 0,1,2…,N-1.

Transformée Inverse :

Pour x,y = 0,1,2…,N-1.

Avec :

 f(x,y) représente une valeur de l’image initiale pour x et y donnés.

F(u,v) représente les coefficients de la TCD.

N représente la taille d’un bloc.

II.6.3 methodes predictives [gam 92]

La méthode prédictive est l’une des plus anciennes, c’est une méthode décorrélative dont le principe est le suivant :

Dans le codage par prédiction la valeur de chaque pixel est prédite à partir des pixels précédemment codés. Seul l’écart entre la valeur prédite et la valeur réelle est quantifié puis codé et transmis. L’écart étant en général faible, sa représentation nécessite moins de bits que le pixel lui même.

Les méthodes prédictives permettent une mise en œuvre facile et conduisent à de bons taux de compression. Elles sont efficaces pour les images dont les évolutions temporelles ou spatiales sont petites.

II.6.4 methodes hybrides [gam 92]

Le terme hybride fait référence aux techniques qui combinent le codage prédictif et le codage par transformée.

Dans le cas des images fixes, on effectue une transformation à une dimension le long des lignes et ensuite une prédiction le long des colonnes. Pour les images animées, on effectue une combinaison entre une transformation bidimensionnelle dans le domaine spatial et une prédiction le long de la composante temporelle pour exploiter la redondance temporelle du signal d’image.

Le codeur hybride regroupe les avantages des deux techniques qui le composent.

II.7 les normes de compression des images

Jusqu'au début des années 80, les recherches ont essentiellement porté sur des algorithmes de compression et ont donné naissance à des normes qui permettaient des économies de l’ordre de 10 à 90%, mais qui ont été très vite insuffisantes devant les problèmes que posaient le stockage de milliers d’images ( banques d’images ) ou l’utilisation de séquences vidéo sur ordinateur, ce qui a rendu nécessaire la mise en place sur le plan international de groupes de coordination et d’étude, chargés de mettre au point des standards

adaptés à ces applications afin de rendre cohérents et compatibles les échanges d’informations sur les canaux de communication connus ou futurs.

II.7.1 la norme de compression JPEG [abd 95][huf 93]

La norme JPEG (Joint Photographic Experts Group) est conçue par le groupe ISO (International Standards Organisation) et le groupe CEI (Commission Electronic International). Elle est destinée à la compression des images fixes en couleurs et à niveaux de gris en vue de leurs stockage sur les supports numériques.

Elle a été réalisée dans la perspective de couvrir les applications les plus diversifiées en tenant compte des contraintes réalistes par rapport aux applications les plus visibles : publication, transmission, banques d’images.

Les techniques définies par la norme JPEG se divisent en deux classes : les méthodes de compression avec pertes qui sont basées sur la TCD suivie d’une quantification et d’un codeur entropique. La seconde classe, concerne les processus de codage sans pertes, cette classe de codeurs n’est pas basée sur la TCD mais sur le codage MICD suivi d’un codage entropique. Pour les méthodes avec pertes, quatre codeurs ont été spécifiés : un codage de base où l’image compressée puis décompressée n’est plus identique à l’image originale, ce processus utilise la TCD et un codage de Huffman.

Les trois autres types de codage sont une extension de codage de base. Ils diffèrent de codage de base principalement par le codage entropique en utilisant un codage arithmétique ou par restitution progressive de l’image.

Figure II.5 : principe de l'algorithme JPEG avec pertes.

Figure II.6 : principe de l'algorithme JPEG sans pertes.

II.7.2 La norme de compression JBIG

La norme JBIG ( Joint Bi-level Image Group ) est destinée à la compression d’images photographiques représentées en deux tons ( noir & blanc ), images textes.

Cette norme est destinée aussi, pour des débits variant de 9.6 Kbits/S à 64 Kbits/S. Elle utilise un codage sans perte avec codeur arithmétique adaptatif. Sa structure est sous forme de couches, chaque couche est un codeur indépendant.

II.7.3 La norme de compression H-261 [had 97]

C’est une norme développée par C.C.I.T.T. (Commission Consultative Internationale de la Télégraphie et de la Téléphonie ). Ce standard est destiné au codage des images animées pour la visiophonie (Téléphonie Visuelle).

Le H-261 utilise un codage hybride combinant la TCD et le codage prédictif. La TCD est utilisée pour la réduction de la redondance spatiale ( codage intra-trames ). Le codage prédictif pour la réduction de la redondance temporelle entre les images de la séquence (codage inter-trames ).

Les efforts développés par les équipes du CCITT (Comité Consultatif International de Téléphonie et Télécommunication) pour le H.261 ont été utilisés comme point de départ pour le développement d’un standard de codage d’images animées par ISO, ce standard s’intitule MPEG pour ² Moving Pictures Experts Group ² .

Contrairement au H.261 en première phase, MPEG est destinée au codage des images animées en vue de leur stockage sur les supports numériques d’où les contraintes plus souples que celles du H.261 (c’est pour cela qu’on l’appelle le standard des applications multimédia).

La première phase de MPEG intitulée MPEG-I spécifie une compression du signal vidéo à un débit de 1.5 Mbits/s. Les deux autres phases ont pour but d’améliorer la qualité du codage vidéo en sacrifiant une augmentation de débit, MPEG-II est destinée à la compression du signal vidéo à des débits d’ordre de 10 Mbits/s, MPEG-III étant destinée à la télévision haute définition à des débits de 30 à 40 Mbits/s. Une quatrième phase, MPEG-IV est destinée au codage d’images animées à très faibles débits (10 Mbits/s), elle devra être normalisée cette année.

conclusion