Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus
ou
Achetez pour : 52,00 €

Lecture en ligne + Téléchargement

Format(s) : PDF

sans DRM

Techniques de compression des images (coll. Informatique)

De
260 pages
La compression des images numériques est possible selon deux méthodes - sans distorsion et avec distorsion. Quelle que soit la méthode, il existe un grand nombre de techniques plus ou moins adaptées aux besoins des utilisateurs. Le nombre de ces techniques a fait apparaître des standards de fait ou des normes permettant la construction de systèmes compatibles : format GIF, normes JPEG et MPEG etc. Techniques de compression des images présente de façon unifiée et pédagogique quelques unes de ces techniques - les plus indiscutablement utilisées en pratique - appartenant aux deux méthodes.
1. Introduction Définitions - Les images numériques en couleurs - Quantités d'informations - Les méthodes optimales 2. Méthodes réversibles Problème - Algorithme de Shannon-Fano - Codes de Huffman - Codage par plages - Lempel-Ziv Welch ou LZW 3. Méthodes irréversibles Quantification, généralités - Quantification scalaire - Quantification vectorielle - Prédiction linéaire - Transformations linéaires 4. Compensation de mouvement Principe - Champ des vitesses ou flot optique ? - Panorama des méthodes de calcul des vecteurs mouvement - Correspondance de blocs 5. Annexes Références - Index
Voir plus Voir moins

collection informatique
Techniques
de compression
des images
Jean-Paul Guillois
HERMES Technique s d e compression
de s images CHEZ LE MÊME ÉDITEUR (extrait du catalogue)
UNIX-Utilisation, administration systèmes et réseaux, Christian Pélissier,
e2 édition revue et augmentée, 1995.
Parallélisme et applications irrégulières, Gérard Authié et al., 1995.
Les réseaux de communication et la conception de protocoles,
Guy Juanole, Ahmed Sehrouchni et Dominique Seret, 1995.
Réseaux haut débit, Pierre Rolin, 1995.
Architecture des résaux haut débit, Kim-Loan Thai, Véronique Vèque et
Simo n Znaty, 1995.
Technologie des télécoms, Pierre Lecoy, 1995.
Réseaux ATM et P-simulation, Jean Pellaumail, Patrice Leguesdron et
Pierre Boyer, 1994.
ATM, Bernard Weiss, 1995.
Temps réel, Jean-André Biancolin, 1995.
La technologie multimédia, Patrice Boursier, Pierre-Antoine Taufour,
e2 édition revue et augmentée, 1994.
eCD-Rom et vidéo sur CD, Georges Zénatti, 2 édition revue et
augmentée, 1996.
Compression et cryptage des données multimédias, Xavier Marsault,
e2 édition revue et augmentée, 1995.
La compression des images numériques, Hervé Guitter, 1995.
HTML, le langage du Web, Pierre Attar, 1996.
eLes télécoms et le droit, Mémento-Guide Alain Bensoussan, 2 édition
revue et augmentée, 1996.
Le multimédia et le droit,e Alain, 1996.
Internet, aspects juridiques, Alain Bensoussan, 1996.
Avertissement
Cet ouvrage est avant tout un support de cours présentant un certain
nombre de techniques classiques de compression appliquées aux images.
Afin d'être accessible à des lecteurs de cultures mathématiques diverses,
les difficultés ou les détails sans importance sont rejetés en annexes. Collection informatique
Techniques
de compression
des images
Jean-Paul Guillois
HERMES A mo n père, m a mère,
Daniel et Nicole.
REMERCIEMENT S
A tous mes élèves qui, sans le savoir, ont contribué à l'élaboration de ce
cours , et à l'Ecole Nationale Supérieure des Télécommunications pour sa
patience .
© Hermès, Paris, 1996
Edition s Hermès
14, rue Lantiez
75017 Paris
ISB N 2-86601-536-3
ISS N 0993-5037
Catalogage Electre-Bibliographie
Guillois, Jean-Paul
Techniques de compression des images. - Paris : Hermès, 1996. - (Informatique)
ISBN 2-86601-536-3
RAMEAU : compression d'images
infographie
images, traitement des : techniques numériques
DEWEY : 006.3 : Méthodes informatiques spéciales.
Infographie et systèmes multimédias
Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une
part, que le s "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4).
Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc
une contrefaçon sanctionnée par les articles L. 335-2 et suivants du Code de la propriété
intellectuelle. Table des matières
Chapitre 1. Problématique 9
1.1. Définitions
1.2. Les images numériques en couleur 10
1.2.1. Bases de la colorimétrie
1.2.2. Quelques chiffres3
1.3. Quantité d'informations4
1.3.1. Information de source
1.3.2.n propre {self information)7
1.3.3. Entropie 18
1.3.4. Théorème du codage de source sans bruit (adaptation) 20
1.3.5. Fonction débit/distorsion 22
1.3.6. Distorsion5
1.4. Les méthodes optimales
1.4.1. Méthodes réversibles
1.4.2.s irréversibles7
Chapitre 2. Méthodes réversibles9
2.1. Problème 2
2.1.1. Détermination des mots binaires 2
2.1.2. Synchronisation 30
2.2. Algorithme de Shannon-Fano3
2.3. Codes de Huffman
2.3.1. Algorithme4
2.3.2. Exemple5
2.3.3. Extensions8
2.4. Codage par plages 4
2.5. Lempel-Ziv Welch ou LZW2
2.5.1. Préambule
2.5.2. Performances comparées3
2.5.3. Algorithme
2.5.4. Décodage 51
2.5.5. Organisation de la table de traduction 57 6 Techniques de compression des images
Chapitre 3. Méthodes irréversibles 61
3.1. Quantification, généralités
3.1.1. Introduction
3.1.2. Inconvénient3
3.1.3. Aspects pratiques
3.2. Quantification scalaire5
3.2.1. Importance
3.2.2. Définitions 6
3.2.3. Bruit de quantification
3.2.4. Exemple : conversion A/N du signal vidéo 68
3.2.5. Calcul d'un quantificateur scalaire optimal9
3.2.6. Application aux images 73
3.3. Quantification vectorielle4
3.3.1. Préliminaires
3.3.2. Principe
3.3.3. Caractérisation8
3.3.4. QV ou QS ? Avantages/inconvénients comparés 79
3.3.5. Le quantificateur optimal 8
3.3.6. Quantification vectorielle dans l'espace des couleurs 90
3.4. Prédiction linéaire 92
3.4.1. Principe3
3.4.2. Calcul de la prédiction4
3.4.3. Mise en œuvre5
3.4.4. Calcul des coefficients6
3.4.5. Origines et conséquences du bruit en prédiction linéaire 100
3.4.6. Boucle ouverte, boucle fermée 10
3.4.7. Performances, cas pratiques7
3.5. Transformations linéaires8
3.5.1. Préliminaires
3.5.2. Principe 10
3.5.3. Transformations linéaires particulières 11
3.5.4. Problématique 122
3.5.5. Transformation de Karhunen-Loève 129
3.5.6.n de Fourier discrète : TFD 130
3.5.7.n en cosinus : DCT4
Chapitre 4. Compensation de mouvement 161
4.1. Principe ••. 16
4.1.1. Le point de vue théorique
4.1.2. Le point de vue pratique
4.2. Champ des vitesses ou flot optique ?5
4.3. Panorama des méthodes de calcul des vecteurs mouvement 166
4.4. Correspondance de blocs 167
4.4.1. Principe
4.4.2. Adaptations à la réalité8 Table des matières 7
Annexes 177
A.l. Norme de la télévision numérigue classique, le 4.2.2 17
A.2. Longueur moyenne par point, / 179
A.3. Limite pour N—>°° de VEQM d'un quantificateur scalaire donné 182
A.4. Quantificateur uniforme et symétrique 184
A.5. Espace vectoriel des blocs d'image de taille M x N 186
A.6. Relation EQM/distance
A.7. Distances et transformations linéaires 191
A.8. Energie moyenne des blocs
A.9. Matrice de Karhunen-Loève5
A. 10.e d'autocovariance 203
A. 11. Formulations de la transformation de Fourier discrète 20
A. 12. La matrice de Fourier est unitaire8
A. 13. Exemple de symétries des coefficients transformés
par transformation de Fourier 210
A. 14. Preuves des symétries desss
parn de Fourier2
A. 15. Décomposition fréquentielle de la TFD bidimentionnelle 21
A. 16. Les fondements de la DCT 223
A. 17. La DCT pour une TFD sur 2M points 237
A. 18. Quantité de calculs en recherche exhaustive9
A. 19.é des ene limitée 24
Bibliographie 241
IndexChapitre 1
Problématique
1.1. Définitions
Selon le dictionnaire le mot codage signifie : "transformation d'un message
exprimé en langage clair, suivant des équivalences convenues dans un code."
On observe que cette définition se rapporte aux messages sans qu'en soit précisée
la nature. C'est qu'en effet, on observe qu'à quelques exceptions près les mêmes
méthodes peuvent s'appliquer à différents types de messages. Toutefois, dans la
mesure où cet ouvrage est dédié aux images, ces seuls types de messages seront
mentionnés dans la suite. Cela sera particulièrement vrai pour les exemples et les
applications.
Aussi, cette définition appliquée aux images conduit aux associations suivantes :
- le "langage clair" est l'image originale elle-même ;
- le "message" est le contenu de l'image ou encore ce qu'elle nous apprend ;
- les "équivalences" sont par exemple :
• des tensions électriques dans le cas d'un codage analogique,
• des mots binaires dans le cas d'un codage numérique ;
- le "code" est l'ensemble des règles qui permettent, en particulier, de
reconstruire le langage clair c'est-à-dire l'image, à partir des équivalences.
La question qui se pose à nous est de savoir quel intérêt nous avons à vouloir
coder les images ?
La réponse est immédiate : il s'agit de profiter des avantages qu'autorisent les
technologies modernes quand il s'agit de transmettre, stocker ou traiter les images.
Or il est clair que ces techniques sont aujourd'hui essentiellement :
- celles de l'électronique et donc utilisation de tensions électriques pour
représenter une image,
- celles du traitement numérique et donc utilisation de mots binaires. 10 Techniques de compression des images
Dans la suite de l'ouvrage il ne sera question que de l'utilisation de mots binaires
et donc du codage numérique.
Nous percevons donc notre objectif : transformer les images en une suite de mots
binaires destinés à faciliter leur transmission ou leur stockage ou leur traitement.
Evidemment, la transformation inverse sera incontournable pour restituer l'image
sous sa forme initiale : le "langage clair". Dans la réalisation de cet objectif une
première étape est nécessaire : la numérisation. Cette dernière se décompose en
deux opérations :
- l'échantillonnage qui consiste à transformer le signal continu en une suite
d'échantillons ou points élémentaires, souvent appelés pixels (picture elements) ;
- la quantification qui consiste à mesurer les échantillons selon un choix limité
de valeurs appelées niveaux de quantification ou niveaux de gris. Ces derniers sont
les symboles de la théorie générale de l'information dont la réunion est appelée
alphabet.
L'ensemble des niveaux de quantification (symboles) des échantillons d'une
image est représenté par une suite de mots binaires. La détermination efficace et
unique de cette suite de mots binaires est loin d'être triviale. Ne pas y prendre garde
1peut aboutir à une surconsommation inutile de digits binaires ou d.b. ce qui est
évidemment contraire à une transmission rapide ou à un stockage économique. La
réduction du nombre de digits binaires à ce qui est juste nécessaire est appelée
compression.
En résumé :
codage = numérisation + compression
L'essentiel de ce document traite des méthodes de compression. Certaines
techniques de quantification seront évoquées parce qu'ayant des conséquences
directes sur la compression.
1.2. Les images numériques en couleur
1.2. L Bases de la colorimétrie
On peut montrer qu'un point coloré peut être obtenu à partir de trois couleurs
particulières, appelées composantes ou primaires, mélangées en doses ou intensités
1
Bien que la confusion soit largement répandue, hélas, il existe une différence majeure entre
le digit binaire et le bit. n est vrai que cette différence est essentiellement théorique puisque
les mesures de digits binaires et de bits contenus dans un signal conduisent à des nombres
souvent très proches. Nous nous permettrons de faire cette confusion lorsque nous aurons
défini la notion de "bit". Problématique 11
adaptées. C'est l'expérience des tubes de gouache que l'on mélange pour obtenir une
couleur différente. Plutôt que de parler de mélange on préfère évoquer la notion de
combinaison linéaire (voir figure 1.1). Les primaires peuvent être presque
quelconques. Dans les terminaux de télévision (caméra et récepteur) ces primaires
sont un Rouge, un Vert et un Bleu. C'est l'exemple que nous avons pris ci-dessous.
un point coloré
projeté sur l'écran
Les hachures matérialisent les couleurs
qui n'ont pu être imprimées.
un point coloré de l'image
projetée air l'écran
projecteur
bleu
projecteur projecteur
vert rouge
: : : primaire primaire primaire
rouge de verte de bleue de
l'image colorée l'image colorée l'image colorée
Figure 1.1. Bases de la colorimétrie 12 Techniques de compression des images
Une représentation pratique d'un point coloré est celle utilisée pour la
représentation des vecteurs en algèbre linéaire, voir figure 1.2. Un point coloré est
alors un "vecteur" défini par ses composantes chromatiques (R, V et fi dans
l'exemple que nous avons pris) selon les axes chromatiques (teintes) rouge, vert et
2bleu. C est un élément d'un espace à trois dimensions . Ces dernières, aussi
P
3appelées primaires, sont matérialisées ici par les trois axes, R, V, fi.
Une image numérique en couleur est un ensemble de points colorés disposés les
uns à côté des autres. Le nombre de points par ligne et le nombre de lignes
définissent la taille ou dimension de l'image. Chacun des points est
colorimétriquement défini par ses composantes chromatiques propres : R, V et fi.
L'ensemble des valeurs R d'une image constitue la primaire rouge de cette image.
Idem pour les valeurs V et fi. On peut donc considérer qu'une image en couleur est
en fait constituée du mélange de ses trois images primaires.
Une première attitude, qu'il est possible d'adopter lorsque l'on souhaite traiter une
image en couleur, consiste à traiter pareillement les trois primaires les unes après les
autres. L'avantage est qu'au niveau du traitement, les algorithmes sont identiques à
ceux des images noires et blanches (N&B), les trois primaires étant en fait des
images monochromes. Bref, l'intérêt est qu'il suffit de répéter trois fois, ce que l'on
sait faire pour les images N&B pour une image en couleur. Sauf exception c'est la
démarche que nous adopterons par la suite. Un inconvénient peut surgir de cette
façon de faire : la non prise en compte de ce que les primaires d'une image colorée
ne sont pas trois images différentes mais au contraire trois images ressemblantes.
Cette forte corrélation entre primaires est un atout qui peut disparaître lorsque l'on
traite séparément les primaires.
R est la quantité ou dose
de la couleur R contenue
dans la couleur Cp du
point P.
Idem pour V et fi.
Figure 1.2. Représentation vectorielle de la couleur
2 L'espace des couleurs n'a pas de structure d'espace vectoriel.
3 Attention d'autres primaires peuvent être utilisées :
• le magenta, le cyan et le jaune (et le noir) pour l'imprimerie,
• Y, Cb, Cr pour la télévision (en dehors des terminaux). Problématique 13
D'où une deuxième attitude qui consiste à tenir compte de cette dépendance qui
existe entre les trois primaires. En fait, deux stratégies sont possibles.
1. Recherche de primaires indépendantes ou décorrélées. On montre qu'il est en
effet possible de déterminer de telles primaires. C'est ce que fait la télévison avec ses
4primaires Y, Cb, Cr . Ces primaires, obtenues de façon abstraite, répondent entre
autres, à cet objectif. L'avantage est qu'alors le traitement successif et indépendant
des trois primaires n'a plus l'inconvénient évoqué ci-dessus.
2. Traitement direct dans l'espace des couleurs. Cette technique est peu utilisée.
Nous l'évoquerons dans la quantification vectorielle dans la mesure où elle est
appliquée dans les équipements informatiques.
REMARQUE
Les composantes Y, Cb, Cr sont définies de façon abstraite et, sauf pour Y, elles
n'ont pas de sens pour l'œil. Elles ne peuvent donc être que provisoires dans une
chaîne vidéo complète.
1.2.2 Quelques chiffres
Parmis les paramètres qui définissent une image en couleur, il y a :
- ses dimensions. Sauf cas très particuliers les dimensions d'une image sont d'au
moins quelques centaines de points et quelques centaines de lignes. Pour une taille
physique donnée, plus une image possède de points et meilleure est sa qualité (à
condition toutefois de rester dans les limites du système visuel humain). Nous
aurons l'occasion par la suite de présenter des exemples précis ;
- sa palette de couleurs. Il s'agit du nombre de teintes possibles que peuvent
prendre chacun des points de l'image ou encore le nombre de vecteurs C différents p
qu'il est possible de définir dans l'espace colorimétrique de la figure 1.2. Dans le cas
des images numériques ce nombre est fini. Là aussi la qualité de l'image est une
fonction croissante de ce dernier. Le nombre de teintes possibles d'un point est lié au
nombre de valeurs différentes que peuvent prendre ses composantes chromatiques.
Or dans une très grande majorité d'applications ce nombre de valeurs, ou niveaux de
quantification, est de 256. En d'autres termes et dans le cas des primaires de la figure
1.1, il y a 256 doses de rouge possibles, 256 doses de vert possibles et autant pour le
3bleu. Par combinaisons linéaires on peut donc réaliser 256 couleurs différentes,
c'est-à-dire un peu plus de 16 millions. C'est ce que l'on a l'habitude d'appeler des
images en vraies couleurs et c'est généralement un maximum. Une telle finesse dans
la gamme des teintes est difficile à restituer et nécessite toujours des équipements
4 Voir la Recommandation 601 du CCIR pour la définition des primaires Y, Cb, Cr. 14 Techniques de compression des images
matériels et logiciels adaptés. Les terminaux informatiques en couleur n'en sont
encore que rarement pourvus. Cela est dû au nombre important de digits binaires
qu'il faut prévoir pour coder la couleur de chaque point. En vraies couleurs, chaque
composante est codée sur 8 digits binaires, ce qui fait un total de 24 bits par point.
5Certains parlent d'image en 24 bits . Bref, une telle longueur de mots binaires est
encore relativement coûteuse et explique qu'on se satisfasse souvent d'une palette de
256 couleurs seulement. L'avantage est que 8 bits suffisent pour coder binairement
chacune d'elles, l'inconvénient est que, le nombre de couleurs étant fortement limité,
les images sont restituées avec de grandes plages de couleur identique, ou aplats,
faisant apparaître par voie de conséquence des frontières entre couleurs différentes.
6C'est le cas d'un grand nombre d'ordinateurs personnels et même professionnels .
Nous reviendrons sur cette affaire à propos de la quantification vectorielle.
1.3. Quantité d'informations
Avant d'aborder l'étude des techniques de compression des images, il paraît
fondé de se poser la question suivante : cela vaut-il encore la peine de comprimer,
face aux progrès des technologies de stockage ou de transmission ?
La réponse, affirmative, est essentiellement justifiée par les observations
suivantes :
- ne pas coder un signal n'importe comment, c'est déjà le comprimer,
7- quelle que soit sa nature , une image numérique exige dès son analyse (image
source) une telle quantité de digits binaires, ou information de source, qu'il est
toujours appréciable de la comprimer,
- la demande en images croît beaucoup plus vite que les progrès technologiques.
1.3.L Information de source
L'information de source est délivrée par l'analyseur numérique c'est-à-dire une
caméra numérique en télévision, un appareil photo numérique, un scanner de
télécopieur, etc. Cet analyseur est un matériel conçu avec des performances fixées et
précisées dans les spécifications du constructeur. Ce matériel ne tient compte ni de
l'application particulière de l'utilisateur ni du contenu de l'image. En d'autres termes
5 "bit" pour "digit binaire". Hélas, la confusion est encore grande.
6 Afin de limiter l'effet visuel défavorable qui en résulte certains matériels ou logiciels
prévoient des artifices arbitraires tels que le tramage par exemple.
7
radiographie à rayons X, affiche publicitaire, image radar, image sonar, image infrarouge... Problématique 15
il ne lui est pas demandé de s'adapter. Au contraire, c'est une qualité d'être stable
quel que soit le signal d'entrée (pour nous l'image) et quel que soit l'environnement.
1.3.1.1. Image en couleur fixe
Nous nous proposons de calculer l'information de source, ou nombre de digits
binaires, associée à une image fixe respectant la Recommandation 601 du CCIR au
niveau 4.2.2 c'est-à-dire la norme de télévision numérique (voir A.l). En première
approximation cette dernière précise les paramètres suivants :
- primaires : Y, Cb, Cr ;
- taille de la primaire Y : 720 points x 576 lignes ;
- taille des primaires Cb et Cr différente de celle de Y, dans le sens horizontal
8uniquement . Cette taille est de 360 points x 576 lignes. La raison de cette différence
de définition avec Y est que, contrairement aux primaires R, V et B, notre acuité
visuelle spatiale n'est pas identique mais de moitié dans Cb et Cr par rapport à celle
que l'on a dans Y. Ceci permet d'abandonner un point sur deux dans Cb et dans Cr
(sous échantillonnage) ;
- le nombre de niveaux de quantification de chacune des primaires est 256.
On en déduit le nombre de digits binaires nécessaires au codage d'une image fixe
de télévision en couleur :
6 nombre de digits binaires = 720 x 576 x 8 + 2 x (360 x 576 x 8) = 6,63 • 10
La quantité de digits binaires normalisée, c'est-à-dire la quantité de digits
binaires par unité donnée de signal (nombre de digits binaires par point d'image ou
par image entière par exemples) est appelée quantité d'information de source. La
figure 1.3 en donne différents exemples.
1.3.1.2. Image en couleur animée
L'image de télévision est essentiellement animée et l'on sait que l'impression de
mouvement peut être rendue à partir d'images fixes pourvu qu'elles soient présentées
à l'observateur à une fréquence suffisamment élevée. Cette technique est mise en
œuvre par la norme 4.2.2 en fixant la fréquence image, /,, c'est-à-dire le nombre
d'images par seconde, à 25 Hz. Il est alors important de savoir combien de digits
binaires par, ou débit, doivent être adressés au décodeur afin qu'il puisse
restituer les 25 images dans ce même temps. Par exemple, ce débit dimensionne la
8 II n'est pas nécessaire, en effet, qu'une image colorée ait des primaires ayant des tailles
identiques. Puique les dimensions géométriques des primaires sont égales cela signifie que
les définitions, ou finesses, de ces primaires sont différentes. 16 Techniques de compression des images
vitesse de transmission du support, ou réseau, chargé de transférer ces digits binaires
afin qu'à l'autre bout la séquence puisse être rejouée. De même le débit permet de
connaître la quantité de mémoire (magnétique ou non) permettant de stocker une
séquence complète connaissant sa durée.
Pour une séquence de télévision le calcul du débit est simple :
Débit = Nombre de digits binaires par image x f d'où : i
6Débit = 6,63 • 10 x 25 = 166 Mbit/ s
Ce résultat ne tient compte que des informations utiles et définit ce que l'on
appelle le débit net. En réalité, pour qu'un système de télévision fonctionne il est
nécessaire de prévoir des signaux complémentaires dits de services tels que les
signaux de synchronisation. L'ensemble de tous ces signaux conduit à un débit brut
de 216 10° digits binaires/s. Voir la figure 1.3.
1.3.1.3. D'autres exemples
Nous présentons dans la figure 1.3 d'autres exemples, tous calculs faits, de quantités
d'information et de débits.
Nombre de Débit net Type d'image
6 610 d.b*./image 10 d.b\/s
Télévision haute def. (projet européen) 35,4 1800
Télévision classique 6,6 166
Visiophonie (qualité minimale) 0,304 2,3 < <9,1
Diapositive (24 x 36) = 150
fac-similé (A4, définition normale) 2
*d.b. pour Digits Binaires.
Figure 1.3. Exemples de débits
De tels résultats conduisent à de sérieuses difficultés d'ordre technologique ou
économique dans le cas de certains traitements comme le stockage ou la
transmission. Pour s'en convaincre donnons quelques exemples :
- stockage : on observe qu'une disquette de 3,5 pouces haute densité ne peut
contenir qu'une seule image de télévision classique, Problématique 17
- transmission : ni la TVHD (télévision haute définition), ni la télévision
classique ne peuvent être transmises sur un réseau numérique classique (débit
6maximum normalisé : = 140 10 digits binaires/s).
La conclusion est que la réduction du nombre de digits binaires est
incontournable dans certaines applications pour des raisons technologiques, et
nécessaire pour des raisons de coûts.
1.3.1.4. L'image de référence noire et blanche
A cause de son impact, il sera fréquent de prendre pour exemple de quantité
d'information de source celle de la télévision : 8 digits binaires par point pour une
image noire et blanche (256 niveaux de gris).
1.3.2. Information propre (self information)
Les notions d'information propre, d'entropie et la fonction débit/distorsion (voir
plus loin) sont issues de la théorie de l'information à laquelle Shannon a laissé des
travaux d'une importance essentielle. Bien que ce soit la base théorique de la
compression des signaux en général, la théorie de l'information n'est pas présentée
dans cet ouvrage. Seules quelques notions utiles seront démystifiées. L'inconvénient
majeur sera certainement un manque de rigueur. On trouvera l'essentiel dans
[GALL] et [GRAY]. Même si une première lecture de ce chapitre nous paraît
essentielle, le lecteur est vivement invité à ne pas s'y attarder mais à y revenir,
9éventuellement, après avoir vu l'exemple proposé pour l'algorithme de Huffman .
Soit un album d'images numériques de même type (mêmes dimensions, même
nature telle que noire et blanche, même nombre de niveaux de gris...). Lorsque l'on
regarde une image particulière de cet album on a conscience d'avoir reçu une
information. Comme autre exemple nous aurions pu prendre un ensemble d'articles
de journaux de même type (même nombre de lettres, écrites avec une police de
caractères identique...). On admet volontiers qu'après la lecture d'un de ces articles
nous avons acquis une plus ou moins grande quantité d'information. On admet aussi
qu'une grande image a toutes les chances d'apporter une plus grande quantité
d'information qu'une petite. L'objectif de la théorie de l'information est justement de
définir puis de quantifier, c'est-à-dire chiffrer, la quantité d'information reçue. Et ce
d'une façon très générale, lorsque l'on a connaissance de la valeur prise par une
variable aléatoire.
9 Tout devrait alors paraître simple. 18 Techniques de compression des images
D'ailleurs chaque point d'une image sera considéré comme une variable aléatoire
et une image de N points sera considérée comme une suite de N variables aléatoires.
Soit P un point particulier d'une image. Il définit une variable aléatoire :
- dont les valeurs sont les niveaux de gris possibles, n,, que peut revêtir P.
(0 < i < 255 en télévision 4.2.2),
- que l'on suppose indépendante des autres variables aléatoires c'est-à-dire des
autres points de l'image.
Une telle variable aléatoire, ou source, est appelée DMS (Discrete Memoryless
Source).
Soit p(n ) la probabilité du niveau de gris .
t
L'information propre de /«, est définie par /(rç ) telle que :
/(n,-) = log -^— fl
P(n) t
REMARQUES
/(n ) mesure la quantité d'information reçue lorsqu'on sait que P a pour niveau (
de gris .
Plus la probabilité est petite et plus la quantité d'information propre est grande.
Exemple : dans un pays où tous les trains arrivent à l'heure il n'est pas étonnant
qu'un train particulier soit ponctuel. Un train en retard est en revanche extrêmement
inattendu et mérite qu'on en parle tout simplement parce que c'est rare ! De même si
un niveau de gris est très peu probable, le fait qu'il se présente s'accompagne d'une
quantité d'information importante.
1.3.3. Entropie
1.3.3.1. Entropie d'un point
L'entropie de P est la valeur moyenne de /(rç). Elle se note H(P). De la valeur
choisie pour la base du logarithme dépend l'unité (norme) de la quantité
d'information. Presque toujours a = 2 et définit une unité appelée : bit. Finalement,
en appelant m le nombre total de niveaux de gris potentiels que peut revêtir P :
en bit (1) Problématique 19
REMARQUES
Dans le cas de la télévision 4.2.2. : m = 256.
Tous les points d'une image n'ont pas nécessairement la même entropie. Sinon
10
cela suppose des hypothèses de stationnarité et d'ergodicité . Ces hypothèses sont
souvent arbitrairement admises à des fins de simplifications.
Le calcul de H nécessite celui des probabilités des différents niveaux de gris. Si
1 1l'on admet les hypothèses de stationnarité et d'ergodicité on pourra calculer p(n ) i
en comptant, dans la même image, le nombre de points ayant le niveau de gris et
en divisant par le nombre total de points N.
Nous expliquerons plus loin la confusion qui est faite entre bit et digit binaire.
Notons pourtant une différence essentielle : un nombre de digits binaires est toujours
entier et au moins égal à 1 alors qu'une entropie (exprimée en bit) est un nombre réel
pouvant être inférieur à l'unité.
La formulation précédente suppose que P est indépendant de ses voisins (DMS).
Dans les images, comme dans bien d'autres exemples pratiques, ce n'est pas le cas.
Aussi est-il souvent nécessaire d'adopter des formulations qui s'appuient sur des
hypothèses plus réelles. Elles sont alors plus complexes. Quoi qu'il en soit on ne
peut, dans la réalité, qu'approcher la valeur de l'entropie.
L'entropie prend toute son importance dans le théorème du codage de source
sans bruit.
1.3.3.2. Entropie d'un bloc
Ce qui précède a permis de calculer la quantité d'information obtenue lorsque
l'on connaît la valeur du niveau de gris d'un point. Imaginons, maintenant, que
l'image soit recouverte par un masque dans lequel est pratiquée une ouverture
laissant apparaître L points. Quelle est la quantité d'information que l'on tire de la
connaissance des niveaux de gris de ces L points ?
L'opération qui consiste à s'intéresser à un bloc de L points s'appelle : faire une
Lextension d'ordre L. Si l'on appelle P (ceci n'est qu'une notation) la variable
10L a stationnarité et l'ergodicité sont des propriétés définies par la théorie des probabilités. La
première précise, dans notre cas et lorsqu'elle est vérifiée, que tous les points possèdent des
propriétés statistiques identiques. Ceci permet en particulier de ne pas avoir à préciser le
point dans l'image auquel nous nous intéressons.
1
^ e qui, hélas, n'est pas le cas mais qui peut permettre une approximation suffisante des
P(«,)-20 Techniques de compression des images
12aléatoire ayant pour valeurs les blocs de L points , on montre que, dans des
1 3situations ou modèles classiques :
LH(P )= LH(P)
L'interprétation est que la quantité d'information apportée par L points est L fois
la quantité d'information apportée par un seul point. On en déduirait la quantité
d'information apportée par l'image entière.
1.3.4. Théorème du codage de source sans bruit (adaptation)
L'adaptation proposée est celle de Rabbani et Jones. Le théorème du codage de
source sans bruit renseigne sur le nombre minimum de digits binaires qu'il faut
prévoir pour coder binairement un signal et donc une image. D'une manière
générale, rien n'impose de remplacer le niveau de gris de chacun des points par un
mot binaire propre. Au contraire il y a intérêt, du point de vue de la compression, à
rassembler les points en blocs, autrement dit faire une extension, et remplacer
chacun de ces blocs par un mot binaire unique. Dans la figure 1.4, l'image est
découpée en blocs de quatre points voisins (extension d'ordre L = 4). Nous
appellerons MB le mot binaire du /ème bloc Bl.
i t
4 niveaux de gri s remplacés par le mêm e mot binaire :MBl
• 4 niveaux de gri s remplacés par le mêm e mot binaire :MB2
L = A
Le s carrés représentent
le s points élémentaires d'une
imag e fortement grossie.
Le s hachures matérialisent de s
• niveau x de gri s difficiles à
Coi n supérieur
représenter .
gauch e d'une
imag e
Figure 1.4. Extension d'ordre 4
12I1 s'agit donc d'un vecteur aléatoire.
13 P appartient à une chaîne de Markov stationnaire, ergodique, d'ordre quelconque. Le cas où
la chaîne de Markov est d'ordre nul correspond à P indépendant de ses voisins. On parle de
source sans mémoire ou DMS {Discrete Memoryless Source). Problématique 21
La théorie de l'information montre que si les probabilités des MB sont {
différentes il y a intérêt à leur accorder un nombre différent de digits binaires. Ceci
est contraire à l'habitude. Prenons l'exemple de la télévision 4.2.2. Les 256 niveaux
de gris sont tous codés binairement avec des mots binaires de longueur identique à
savoir : 8 digits binaires (notons que l'extension est, ici, d'ordre 1). Or, on montre
que cela n'est pas optimal (vis-à-vis du nombre total de digits binaires utilisés par
l'image) si les niveaux de gris, ou blocs dans le cas d'une extension d'ordre supérieur
à 1, présentent des probabilités différentes. De plus il est possible, parce que
décodable, d'accorder à ces différents niveaux de gris, ou blocs, des longueurs, c'est-
à-dire des nombres de digits binaires, différentes.
Nous verrons plus loin (algorithme de Huffman) les solutions apportées aux
problèmes de la définition et de la mise en œuvre des mots binaires à longueur
variable.
Soient :
- L l'ordre d'extension (on remplace des blocs de L points par des mots binaires),
- lj la longueur, ou nombre de digits binaires, de MB,
i
- ï la longueur moyenne par point, définie par / = -j- E{/,} avec :
(voir A.2).
- H(P) l'entropie d'un point d'une image supposée stationnaire et ergodique.
Une conséquence du théorème du codage de source sans bruit est :
V<5>0 3L Vi 3MB H(P)<Î <H(P) + S t
Cette formule est plus simple à interpréter qu'elle n'y paraît. Elle exprime
que quelle que soit ô (Vô>0), il est toujours possible de trouver une taille des
blocs, (3L), telle qu'à chacun des blocs, (V/), correspondent des mots binaires
(3MB) tels que leur nombre moyen de digits binaires soit compris entre l'entropie et
t
l'entropie plus ô, (H(P)<ï < H(P) + 5).
Nous avons dans ce théorème l'intérêt majeur de l'entropie. On observe en effet
qu'il est toujours possible de trouver des mots binaires tels que leur nombre moyen
de digits soit proche de la valeur de l'entropie. On montre, en outre, que plus on
souhaite êtree de l'entropie et plus il faut augmenter L (l'ordre d'extension ou
encore la taille des blocs). On trouvera un exemple simple d'illustration de ce
phénomène dans le chapitre sur l'algorithme de Huffman.
L'entropie est donc la limite inférieure du nombre moyen de digits binaires juste
nécessaire au codage binaire d'une image (et plus généralement de tout signal). C'est
sans doute cette subtilité qui crée la confusion entre digits binaires et bit. Cette 22 Techniques de compression des images
précision étant faite il nous arrivera désormais d'utiliser indifféremment ces deux
termes, là où aucune ambiguïté ne sera à craindre.
REMARQUES
Notons que le décodage est a priori possible et permet la reconstruction parfaite
de l'image originale.
Sauf dans les cas simples, il n'existe pas de méthodes permettant de coder une
image avec un nombre moyen de digits binaires rigoureusement égal à l'entropie. En
revanche il en existe qui permettent de l'approcher avec une précision qui ne dépend
que du temps calcul dont on dispose ou de la complexité algorithmique que l'on
s'autorise. Toutes ces méthodes sont qualifiées indifféremment de méthodes sans
pertes, méthodes sans bruit, méthodes sans distorsion, méthodes réversibles ou
encore de codage entropique.
1.3.5. Fonction débit/distorsion
Il n'est pas rare qu'une transmission ou un stockage soit soumis à des erreurs
certes faibles mais réelles. De plus, dans la pratique, il n'est pas toujours nécessaire
de conserver la qualité initiale d'une image. On montre en effet que le système visuel
humain accepte volontiers qu'il y ait des différences, ou mieux distorsions, entre
l'image originale et l'image décodée. L'avantage est que, conformément à ce qui est
démontré en théorie de l'information, il est possible alors de tenir compte de ces
distorsions, ou pertes, ou bruit, pour coder une image (et plus généralement un
signal) avec un nombre de digits binaires inférieur à l'entropie.
Une autre façon de présenter la chose est la suivante. Dans le paragraphe
précédent nous avons montré qu'il est possible de coder binairement une image avec
un nombre minimum de digits binaires égal à l'entropie. Dire que cela est possible
signifie que l'on est capable de décoder l'information binaire et de retrouver l'image
originale. Cette information binaire constitue par exemple ce que l'on a l'habitude
d'appeler un fichier informatique. Même si ce dernier contient un nombre de digits
binaires juste égal à l'entropie, rien n'empêche un utilisateur de supprimer du fichier,
à coups d'instructions informatiques, des digits binaires supplémentaires et donc
comprimer davantage...! La théorie de l'information montre qu'on ne peut alors
garantir l'existence d'un décodage assurant l'intégrité de l'image originale.
Pour résumer, il est possible de coder binairement une image avec un nombre de
digits binaires inférieur à l'entropie, mais alors des distorsions (différences entre
image originale et image décodée) s'introduisent.
Si l'on veut que l'image décodée nous apparaisse acceptable il est nécessaire de
contrôler ces distorsions et donc de les mesurer. Appelons D la quantité de
distorsions, ou tout simplement la distorsion, entre deux images qui ne sont pas Problématique 23
totalement identiques. Nous verrons au chapitre suivant une méthode permettant de
mesurer D.
La théorie de l'information démontre, ce qui était évidemment prévisible, qu'en-
dessous de l'entropie, plus le nombre de digits binaires est réduit et plus D
augmente. Pour une source donnée, un ensemble d'images par exemple, une fonction
décroissante lie le nombre de digits binaires à D, c'est la fonction débit/distorsion
(rate distortion function), voir la figure 1.5.
Cette fonction, en reprenant les résultats du chapitre sur l'entropie, contient
l'essentiel de la théorie de l'information. On y trouve les éléments suivants :
- sur l'axe des abscisses, la mesure de D sur laquelle nous reviendrons au
chapitre suivant ;
- sur l'axe des ordonnées :
• soit le nombre de digits binaires utilisés pour coder binairement l'image
considérée,
• soit le nombre de digits binaires par seconde c'est-à-dire le débit ;
- I ou la quantité d'information de source. C'est la quantité de digits binaires
s
directement fournie par l'analyseur d'image numérique (caméra de télévision
numérique, fichier informatique d'une image originale,...). L'image est livrée brute
sous forme d'un codage binaire simple résultant souvent d'une conversion
analogique/numérique ou numérisation. Aucune compression n'est effectuée ;
- H ou l'entropie qui correspond à la quantité minimale de digits binaires
permettant un décodage sans distorsion.
d.b. (digits binaires) Le s a présentés sont ceux obtenus
OU A pou r des images.
d.b.Is débit)é
Is : quantit é d'information de sourc e
méthode s réversibles (o < 2.5)
H : entropie
méthode s irréversibles (a » 2.5)
Dmax D
Figure 1.5. Fonction débit/distorsion 24 Techniques de compression des images
La fonction débit/distorsion présente deux zones bien distinctes :
- la zone sans distorsion comprise entre l et H, s
- la zone avec distorsionse entre H et 0.
Avant d'interpréter ces deux zones il est nécessaire de définir a ou encore le taux
de compression. Ce dernier sert à mesurer l'efficacité d'une méthode de compression
en comparant, sous la forme d'un rapport, la quantité de digits binaires utilisée par
l'image originale et la quantité de digits binaires utilisée par l'image comprimée. En
matière d'image, l'habitude est de poser :
_ Nombre de digits binaires utilisés par l'image originale
Nombre de digits par comprimée
L'objectif de la compression des images est donc d'avoir o le plus grand possible.
Notons que a est toujours supérieur ou égal à 1.
1.3.5.1. La zone sans distorsion
La courbe est confondue avec l'axe des ordonnées puisque D= 0. Dans cette
zone le décodage de l'image originale est possible.
L'entropie est une limite inférieure que dans les cas réels on ne peut atteindre
exactement. Et encore, nous n'avons souvent qu'une valeur approchée de l'entropie.
En ce qui concerne les images de scènes naturelles ou de type photographique,
comme par exemple l'image de la télévision 4.2.2., le codage entropique ne permet
pas de dépasser des taux de compression supérieurs à 2,5.
1.3.5.2. La zone avec distorsions
Les images sont ici codées avec un nombre de digits binaires inférieur à
l'entropie. De la distorsion est alors introduite dans l'image décodée (£>* 0). Les
nombreuses méthodes qui permettent de coder une image dans cette condition, tout
en contrôlant la distorsion, sont qualifiées de méthodes avec distorsions, ou avec
bruit, ou avec pertes ou irréversibles (puisqu'on ne peut garantir un décodage
permettant de remonter à l'image originale). Là encore la courbe est une limite
inférieure que tentent d'atteindre les méthodes que nous présenterons.
Parce que :
- les images conduisent à des valeurs de l d'emblée extrêmement importantes,
s
- dans la plupart des applications, l'œil accepte que l'image décodée soit
différente (il peut même se faire qu'il ne perçoive pas les différences).

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin