NikolaStikov /Yves Goussard - Polytechnique Montréal · 2016. 3. 16. · 15 mars2016 NikolaStikov (ELE8812) CompressionetcodageI 15mars2016 1/27. Plan 1 Notionsfondamentales Introduction

Compression et codage : méthodes élémentaires

Nikola Stikov/Yves Goussard

ELE8812

15 mars 2016

Nikola Stikov (ELE8812) Compression et codage I 15 mars 2016 1 / 27

Plan

1 Notions fondamentalesIntroductionNotion de redondanceModèle de codage et normesNotion d’information

2 Codage de sourceCodage de HuffmanCodage de GolombCodage arithmétiqueCodage de Lempel-Ziv-Welch

3 Redondance spatialeCodage par longueur de plage (RLC)Codage par plans de bits (BPC)Codage par symboles


Notions fondamentales Introduction

Introduction

Nécessité de compresser les imagesPrévalence des images ou des séquences d’images (loisirs, industrie,santé, ...)Problème de taille : 1 film de 2h00, basse résolution = 224 Go

Compression nécessaire pourStocker les imagesTransmettre les images (de la télécopie à internet)

ExemplesDossier médical informatisé(PACS)Archives historiques

Blogs, Facebook, ...Photographie numérique


Notions fondamentales Notion de redondance

Notions fondamentales

DéfinitionsImage originale : b bits ; image compressée : b

′bits

Taux de compression : C = b/b′

Redondance relative : R = 1− 1/C

Codage : utilisation de la redondance

Redondance de source Redondance spatiale Information nonpertinente

c©1992-2008 R. C. Gonzalez & R. E. Woods



Redondance de source

PrincipeImage : suite de symboles indépendantsExemple de codage à longueur variable :


L̄ =∑k

l(rk)p(rk)

L̄ = 1, 81 bits



Redondance spatiale

Exemple : codage par longueur de plage (RLC)


Codage de la longueur et de la valeur de chaque segment horizontald’intensité constante512 octets : C = 128 !



Information non pertinente

Exemple : image quasi-homogène


Compression avec perte : une seule valeur. C = 2562 !Compression sans perte : redondance spatiale et redondance de source


Notions fondamentales Modèle de codage et normes

Structure d’un système de codage

Principales étapes Codage RLC


Possible ajout de redondance lors de la transmission ou du stockageQuelle transformation (mapper) ?Quel codage de source (symbol coder) ?



Normes, conteneurs et formats (1)Réponses toutes faites

Format de fichier


Conteneur




Normes, conteneurs et formats (2)Réponses toutes faites

Norme de compression


En pratiqueTransformation : doit être adaptée au type d’image (de redondancespatiale) à compresserCodeur de symboles : mesures de qualité (en fonction de la probabilitédes différents symboles...)


Notions fondamentales Notion d’information

Arrière-plan mathématique

Notion d’informationInformation contenue par un évènement E : I (E ) = − log2 p(E ) (bits)Entropie d’une source (symboles indépendants) :H = E [I (r)] = −

∑k

p(rk) log2 p(rk)

Premier théorème de Shannon : H limite inférieure de L̄

Attention aux hypothèses sur la source !

Fidélité (codage avec perte)

f̂ (x , y) : image résultant du codage de f (x , y)

Mesure la plus courante : SNR =‖f̂ (x , y)‖2

‖f̂ (x , y)− f (x , y)‖2


Codage de source Codage de Huffman

Codage de Huffman (1)

PrincipeProbabilité de chaque symbole connueCodage de longueur variable (probabilité ↘, longueur ↗)

Exemple de construction

0,15

0,20

0,35

0,1

0,08

0,05

0,04

0,03

0,35

0,2

0,15

0,1

0,08

0,07

0,05

1

0

0

1

0,08

0,2

0,35

0,12

0,1

0,15

0

1

0,12

0,15

0,2

0,35

0,18

0

1

0,18

0,2

0,35

0,27

0

1

0,27

0,35

0,38

0

1

0,38

0,620

1

r0r1r2r3r4r5r6r7


Codage de source Codage de Huffman

Codage de Huffman (2)

Résultat de la constructionr0 : 00 r4 : 111r1 : 10 r5 : 0111r2 : 010 r6 : 01100r3 : 110 r7 : 01101

PropriétésSéparabilité ⇒ pas de nécessité de coder la séparation entre symbolesQuasi-optimalité au sens de la théorie de l’information.

En pratiquep(rk) ? Indépendance entre symboles ?Quantités à transmettre :

symboles et leur probabilitésymboles codés


Codage de source Codage de Golomb

Codage de Golomb (1)

PrincipeCodage de valeurs entières positivesChoix d’un diviseur mCodage d’une valeur x par son quotient q et son reste r

quotient : codage unairereste : codage de longueur variable détectable sans ambiguïté (voirmanuel)

Exemple : m = 54 < m ≤ 8 : k = 3. Reste codé sur 2 ou 3 bitsc = 2k −m = 3restes ≥ c : codés par r + c sur k bitsrestes < c : codés directement sur k − 1 bits




Codage du reste (m = 5)

Reste Valeur codée Nombre de bits Code0 0 2 001 1 2 012 2 2 103 6 3 1104 7 3 111

PropriétésSéparabilité ⇒ pas de nécessité de coder la séparation entre symbolesQuasi-optimalité pour des distributions exponentielles




ExtensionsDistributions quelconques (ordonnancement par probabilitésdécroissantes)Codage de Golomb exponentiel ; analogie : représentation en virguleflottante vs. virgule fixe

En pratiqueHypothèses sur la distribution des symboles ?Quantités à transmettre :

valeur de mau besoin, table d’ordonnancement des symbolessymboles codés


Codage de source Codage arithmétique

Codage arithmétique (1)

PrincipeProbabilité de chaque symbole connueOrdonnancement lexicographique et codage de suites de symboles(messages) par la variable aléatoire uniformément répartie sur [0, 1]équivalente

Exemple : 4 symboles





Exemple : message de 5 symboles





PropriétésQuasi-optimalNécessité de choisir une représentation arithmétique appropriée del’intervalle [0, 1]

Nécessité de transmettre des codes de fin de messages

ExtensionProbabilités dépendant du contexte (probabilités conditionnelles)

En pratiqueProbabilité des symboles et granularité de la représentation de [0, 1] ?Quantités à transmettre :

probabilité de chaque symbolecode de chaque messagecode de fin de message


Codage de source Codage de Lempel-Ziv-Welch

Codage de Lempel-Ziv-Welch (LZW) (1)

PrincipeCodes de longueur fixeConstruction récurrente d’un dictionnaire (mot : suite de symboles) aucodage et au décodage

Exemple : image (4, 4) sur 256 niveaux

39 39 126 12639 39 126 12639 39 126 12639 39 126 126

Solution : voir manuelDécodage : exercice


Codage de source Codage de Lempel-Ziv-Welch

Codage de Lempel-Ziv-Welch (LZW) (2)

En pratiqueQuantités à transmettre :

Liste des symbolesTaille du dictionnaireTechnique de gestion des débordements


Redondance spatiale Codage par longueur de plage (RLC)

Codage par longueur de plage (RLC) (1)

PrincipeUtilisation de la redondance spatialeDescription d’une image par :

la longueur d’un segment d’intensité constante dans une direction debalayage de l’imagela valeur de l’intensité

Très efficace pour les images binaires (norme en télécopie)

Exemple : format BMPMode codé : 2 octets (longueur du segment, valeur de l’intensité)Mode absolu :



Redondance spatiale Codage par longueur de plage (RLC)

Codage par longueur de plage (RLC) (2)

En pratiqueRelativement peu efficace pour les images non binairesPeut conduire à un accroissement de la taille des images !Peut être associé à un codage de source Codeur-décodeur

Utilisé dans les normes CCITT


Redondance spatiale Codage par plans de bits (BPC)

Codage par plans de bits (BPC) (1)

PrincipeDécomposition de chaque pixel de l’image en forts poids → faiblespoidsConstitution et codage des k images binaires

Difficulté : sensibilité à de petites variations d’intensité

Autre possibilité : décomposition en codes de Graybk−1, bk−2, . . . , b0 valeur des k bitsCodes de Gray :

gk−1 = bk−1

gi = bi+1 XOR bi 0 ≤ i ≤ k − 2


Redondance spatiale Codage par plans de bits (BPC)

Codage par plans de bits (BPC) (2)

Décomposition BPC et codes de Gray



Redondance spatiale Codage par symboles

Codage par symboles (1)

PrincipeReconnaissance de symboles (caractères)Création d’un dictionnaire de symbolesDescription de l’image comme un assemblage de ces symboles

Exemple elémentaire



Redondance spatiale Codage par symboles

Codage par symboles (2)

Exemple d’utilisation : codage JBIG2Segmentation de l’imageCaractères ou halftones : symbolesAutres régions (e.g., lignes) : codage de source

Exemple : distorsion induite par le codage



Documents

NikolaStikov /Yves Goussard - Polytechnique Montréal · 2016. 3. 16. · 15 mars2016 NikolaStikov (ELE8812) CompressionetcodageI 15mars2016 1/27. Plan 1 Notionsfondamentales Introduction