Compression d’image : algorithmes et standards

Couverture
Page de titre
1 Introduction et généralités
Préface
Présentation générale
Prérequis
Public visé
Limites
Structuration
Détail des chapitres
Rapport d'erreur et remerciements
1 Cadre général
1.1 Les formats de fichier image classiques
1.1.1 Structure générale d'un fichier image
1.1.2 Les formats bruts
1.1.3 Compression sans perte
1.1.4 Compression avec pertes
1.1.5 D'autes formats moins répandus
1.2 Image monochrome
1.2.1 Image binaire
1.2.2 Image en niveaux de gris
1.3 Image en couleurs
1.3.1 Espaces de couleurs primaires
Synthèse additive: le système RGB
Synthèse soustractive : les systèmes CMY et CMYK
1.3.2 Espaces lumière/couleurs
Teinte/saturation/valeur : le système HSV
Luminance/chrominance : les systèmes YUV, YIQ et YC_bC_r
1.3.3 Couleurs indexées
1.3.4 Transparence / canal alpha
1.4 Les modes de stockage et de transmission
1.4.1 Transmission séquentielle
1.4.2 Transmission progressive
Entrelacement
Transmission par plans de bits
Transmission pyramidale par blocs
II Théorie de l'information et compression généraliste
2 Éléments de théorie de l'information
2.1 Signal et information
2.1.1 Source
Source markovienne
2.1.2 Probabilité et occurrence
2.1.3 Information
2.2 Quantité d'information et entropie
2.2.1 Changement d'alphabet, recodage de source
Source discrète sans mémoire
Source markovienne
2.2.2 Entropie
Thermodynamique
Théorie de l'information
2.2.3 Information globale d'un signal
Entropie d'un événement
Extension d'une source
Entropie d'un bloc
Source markovienne - entropie d'une image
2.3 L'entropie comme seuil de codage
2.3.1 Longueur moyenne d'un code
2.3.2 Théorème du codage de source sans bruit
L'entropie comme seuil absolu
2.3.3 Interprétation en compression de signal
3 Codes à longueur variable
3.1 VLC préfixé
3.1.1 Synchronisation
3.1.2 Préfixage
3.1.3 Décodage
3.2 Codage de Shannon-Fano
3.2.1 Exemples
1er exemple
2e exemple
Algorithme pour le code optimal
3.2.2 Code compact
3.3 Codage de Huffman
3.3.1 Algorithme
Huffman en deux phases
Construction directe du code
3.3.2 Propriétés du codage de Huffman
3.3.3 Décodage
3.3.4 Code de Huffman et extension de source
Un exemple détaillé
3.4 Application aux images : le codage par plage
3.5 Le codage de Huffman dynamique
4 Codage arithmétique
4.1 Principe en arithmétique réelle
4.1.1 Algorithme de codage
4.1.2 Algorithme de décodage
4.2 Codage en arithmétique entière
4.2.1 Algorithme de codage
4.2.2 Algorithme de décodage
4.2.3 Un cas particulier: underflow
4.2.4 Codage binaire
4.2.5 Variations sur le codage arithmétique
5 Méthodes à base de dictionnaire
5.1 Introduction
5.1.1 Principe général
5.1.2 Un premier exemple : dictionnaire statique
Efficacité
5.2 LZ77 : dictionnaire à fenêtre glissante
5.2.1 Codage
Bilan du codage complet
5.2.2 Décodage
5.2.3 Variantes et applications de LZ77
LZ77 et Huffman
5.3 LZ78 : construction dynamique du dictionnaire
5.3.1 Codage
5.3.2 Décodage
5.3.3 Post-traitement et variantes
5.4 LZW : variante sur LZ78
5.4.1 Codage
5.4.2 Décodage
5.4.3 Un cas critique
5.5 Applications de la classe LZ*
5.5.1 LZ77
L'utilitaire Zip
Le format d'image PNG
5.5.2 LZW
La commande compress
Le format d'image GIF
III Techniques de décorrélation Applications à la compression d'image sans perte
6 Compression sans perte d'image binaire
6.1 Décomposition en plans de bits et RLE
6.1.1 Codes binaires
6.1.2 Codes de Gray
6.1.3 Codage RLE par plans binaires
6.2 QM-Coder et le standard JBIG
6.2.1 Principe
6.2.2 Contexte de voisinage 2D
6.2.3 Une application standard: le QM-Coder
6.2.4 Codage sans perte d'image en niveaux de gris
Contexte 3D
Buffer mémoire pour le QM-Coder
6.2.5 Transmission progressive par plans de bits
Transmission pyramidale
7 Codage prédictif sans perte
7.1 Prédiction linéaire
7.1.1 Principe
7.1.2 Cas des images
7.1.3 Effets de bord
7.2 Choix des coefficients de la combinaison linéaire
7.3 Un cas pratique classique : le standard DPCM
7.3.1 Les prédicteurs du DPCM
7.3.2 Mesures statistiques sur une image
7.3.3 Encodage de l'image différentielle
7.3.4 Intégration aux formats d'image
Le format PNG
Le standard JPEG sans perte
IV Techniques de dégradation Applications à la compression d'image avec pertes
8 Introduction à la quantification
8.1 Dégradation de l'information
8.2 Fonction débit/distorsion
8.2.1 Erreur quadratique moyenne et rapport signal/bruit
8.2.2 Fonction débit/distorsion
8.3 Quantification
8.3.1 Généralités
8.3.2 Définitions mathématiques
9 Quantification scalaire
9.1 Principe et définition
9.2 Choix d'un quantificateur
9.2.1 Le critère de variance
9.2.2 Le critère de taux de compression
9.2.3 Optimisation conjointe
9.3 Quantificateur scalaire uniforme
9.3.1 Cas général
Un cas classique: quantificateur uniforme sur source uniforme
9.3.2 Application à la compression d'image
9.4 Quantificateur scalaire non uniforme (QSNU)
9.4.1 Cas général
9.4.2 Quantificateur de Lloyd-Max
Algorithme de Max pour un QSNU symétrique
Algorithme de Lloyd pour un QSNU non symétrique
9.4.3 Applications aux images
9.5 Prédiction linéaire et quantification
9.5.1 Rappels sur les principes du DPCM
9.5.2 DPCM et QS
9.6 Quantification du signal différentiel
9.6.1 Algorithmes indépendants
9.6.2 Adaptation
10 Quantification vectorielle
10.1 Principe
10.1.1 Critère de ressemblance-distance
10.1.2 Exemple en dimension 2
10.1.3 Mise en oeuvre
10.2 Caractérisation
10.2.1 Paramètres d'un quantificateur vectoriel
10.2.2 Comparaison des quantificateurs vectoriel et scalaire
QV ou double QS
Coût de calcul
Quantificateur optimal
10.3 Algorithme de Linde-Buzo-Gray
10.3.1 LBG pour un quantificateur vectoriel
Algorithme
10.3.2 Initialisation du dictionnaire
Création sur la séquence d'apprentissage
Création par dédoublement
10.3.3 Choix de la séquence d'apprentissage
V Techniques de transformation Applications à la compression d'image avec pertes
11 Généralités
11.1 Corrélations globales
11.2 Transformation
11.2.1 Schéma général et définitions
Définitions
11.2.2 Transformations linéaires
11.2.3 Transformations 2D séparables unitaires
Caractérisation et propriétés
Mesure de l'efficacité
11.3 Transformée de Karhunen-Loève
11.3.1 Matrice d'autocovariance
Construction des variables aléatoires
Covariances
11.3.2 La transformation de Karhunen-Loève ou KLT
Transformation inverse
11.3.3 Inconvénients de la KLT
11.4 Transformée de Fourier
11.4.1 Représentation dans le domaine fréquentiel
11.4.2 La transformée de Fourier continue
11.4.3 La transformée de Fourier discrète ou DFT
11.4.4 Avantages et inconvénients de la DFT
11.4.5 La transformée de Fourier rapide
Premiers pas, N = 4
Seconds pas, N = 8
Cas général
12 La DCT et la norme JPEG
12.1 Une transformation universelle : la DCT
12.1.1 De la DFT à la DCT
12.1.2 Avantages de la DCT
12.1.3 Algorithme DCT rapide
12.1.4 Décomposition fréquentielle
12.2 DCT et quantification
12.2.1 Idée générale
12.2.2 Mise en oeuvre : quelques méthodes classiques
Sélection zonale
Sélection par seuil
Matrice de quantification
Quelques remarques
12.3 La norme JPEG
12.3.1 Traitement des blocs
12.3.2 Codage entropique
12.3.3 Les modes de transmission du standard JPEG
12.4 Conclusion
VI Annexes
A Exemples
A.1 Images de test en niveaux de gris
A.2 Images de test en couleurs
Index
Hors-texte en couleurs
Images du chapitre
Images de l'annexe A.2