M3201 – TD #2

Culture scientifique et
traitement de l'information S3

Rappel du TD #1

  • Une image numérique est encodée dans un tableau de pixels.
  • Pour chaque pixel, on encode 3 (ou 4) valeurs, chacune sur un octet (8 bits).
  • Ainsi, on a 256*256*256 = 16 777 216 couleurs différentes.

Codage de symboles

  • 1 bit = 2 possibilités (0, 1). Encoder deux symboles (nombres, caractères, couleurs)
  • 2 bits = 4 possibilités (00, 01, 10, 11). Encoder quatre symboles.
  • Si on veut encoder seulement trois symboles ?

Exercice

  • Choisir un codage binaire pour 3 symboles différents
  • Coder et décoder un message
  • Différentes fréquences
  • Pareil pour 5 symboles

Deux types de codage :

  • de longueur fixe
  • de longueur variable

Un codage de longueur variable permet de compresser un message (texte, son, image). Il doit être décodable.

Codage de Huffman

Étant donné un message, quel est le meilleur codage ?

Exercice

  • Un message avec 5 symboles différents
  • Faire le code de Huffman
  • Coder le message
  • Décoder le message
  • Le codage de Huffman utilise les fréquences de chaque symbole
  • Son entropie (nombre de bits/symbole) est bornée par l'entropie du message :
    \(H = - \sum_i p_i \cdot \log_2(p_i)\)
  • Utilisé dans la compression d'images.

Autres méthodes de compression :

  • Codage arithmétique
  • Run length encoding (RLE)
  • Codage par dictionnaire : LZ77, LZ78, LZW

La compression de données n'est pas magique : elle marche quand on considère un ensemble restreint de messages.

Exercice

  • Nombre de messages de longueur 4 avec 2 symboles différents
  • Nombre de messages de longueur 4 avec 2 symboles différents et fréquences 0,5 et 0,5
  • Généralisation

Compression d'images

Trois types de redondance dans une image :

  1. Redondance de codage (nombre de couleurs)
  2. Redondance spatiale (pixels voisins)
  3. Information sans importance (couleurs imperceptibles)

Deux types de compression :

  • Sans perte : en exploitant la redondance
  • Avec perte : en simplifiant l'image pour créer de la redondance

Exemple #1

  • Une image avec peu de couleurs
  • Codage de Huffman

logo vectoriel

Compressions sans perte.

Exemple #2

  • Une image avec plus de couleurs
  • Postérisation : fusionner les couleurs similaires
  • Codage de Huffman

Compression avec perte.

Exemple #3

  • Une image avec deux couleurs
  • Codage RLE : nombre de pixels identiques consécutifs

Compression sans perte.

PNG

  1. Prédiction
  2. LZ77
  3. Huffman

Compression sans perte.

JPEG

  1. Simplification de couleurs
  2. Codage par blocs (~ Fourier)
  3. RLE
  4. Huffman

Compression avec perte.

Conclusion

  • La compression (sans perte) a ses limites.
  • La compression dépend de la redondance (entropie) d'une image.
  • La compression avec perte est plus efficace, mais modifie l'image.
  • Chaque format d'image utilise plusieurs et différentes techniques.