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.