Compression

TODO: Introduction, On va faire de la compression d’image. Expliquer ce qu’est l’entropie…

Les outils et formats de compression sont disponible ici, et le code utilisé pour générer les images et animation de cet article sont disponible ici.

Table des matières
Espace couleurs
Quantification
Courbe de remplissage
Codage différentiel
Compression sans perte

Espace couleurs

Table des matières
RGB
CMY
YCoCg
xRGxB

RGB

TODO: Explication de pourquoi c’est RGB le standard, donc la synthèse additive

CMY

TODO: Synthèse soustractive

R = 255 - C
G = 255 - M
B = 255 - Y

YCoCg

TODO: Formules de conversion depuis et vers RGB

TODO: GIF pour visualiser l’espace de couleur

xRGxB

Le xRGxB est l’espace de couleur utilisé dans dbimg. Il a été conçu pour avoir une traduction très rapide depuis et vers RGB, utilisant simplement deux ou exclusifs:

R  = xR ^ G
G  = G
B  = xB ^ B

Quantification

TODO: Distance dans l’espace de couleur, dithering…

Courbe de remplissage

TODO: Explication de comment on utilise les courbes de remplissage dans la compression image, qu’est ce qu’on recherche comme propriété de courbe et comment c’est utile pour la compression d’image

Dans une image, les couleurs sont rarement réparties aléatoirement. Généralement, des points proche dans l’image vont tendance a avoir une couleur similaire. Pour exploiter cette redondance, on va chercher a utiliser des courbes de remplissage. Ici, on appelle courbe de remplissage une fonction bijective entre un espace a deux dimensions et un espace a une seule dimension.

Table des matières
Trame
Serpent
Courbe de Peano
Courbe de Hilbert
Courbe de Lebesgue

Trame

La trame est la courbe de remplissage la plus simple a implémenter. L’espace est parcouru de haut en bas, de gauche a droite.

L’indice dans la courbe peut être obtenu pour un point (x, y) et une largeur d’image LARGEUR fixée avec la formule suivante:

E(x, y) = y * LARGEUR + x

D(i) = (i / LARGEUR, i % LARGEUR)

Un des avantage principale de cette méthode est sa simplicité. Un des inconvénient principal est qu’elle n’est pas continue, et que deux points (x₁, y₁) et (x₂, y₂) qui sont proche dans l’espace a deux dimensions peuvent se retrouver loin dans la courbe finale.

TODO: Calculer distance moyenne / maximum dans la courbe?

TODO: Preuve de bijectivité?

Serpent

La courbe en serpent est une amélioration simple de la courbe en trame, qui vise simplement a réparer le soucis de continuité de cette dernière. Comme son nom l’indique, elle va serpenter l’espace: en allant de haut en bas mais en alternant de gauche a droite et de droite a gauche. Son implémentation est la suivante:

E(x, y) =
  si y est paire:
    y * LARGEUR + x
  si y est impaire:
    y * LARGEUR + (LARGEUR - 1 - x)

TODO: Fonction de décodage

TODO: Avantage de cette méthode (La courbe est continue)

TODO: Inconvéniants de cette méthode (On inverse la logique pour les répétitions)

TODO: Calculer distance moyenne / maximum dans la courbe?

TODO: Preuve de bijectivité?

Courbe de Peano

TODO: Comment ça marche?

TODO: Avantage de cette méthode (La courbe est continue)

TODO: Gif pour visualiser

TODO: Avantage de cette méthode

TODO: Inconvéniants de cette méthode

TODO: Calculer distance moyenne / maximum dans la courbe?

TODO: Preuve de bijectivité?

Courbe de Hilbert

TODO: Comment ça marche?

TODO: Avantage de cette méthode

TODO: Inconvéniants de cette méthode

TODO: Calculer distance moyenne / maximum dans la courbe?

TODO: Preuve de bijectivité?

Courbe de Lebesgue

TODO: Comment ça marche?

TODO: Avantage de cette méthode

TODO: Gif pour visualiser

TODO: Avantage de cette méthode

TODO: Inconvéniants de cette méthode

TODO: Calculer distance moyenne / maximum dans la courbe?

TODO: Preuve de bijectivité?

Codage différentiel

TODO: Différents encodages différentiels, on utilise un opérateur avec certaines propriété et hop

E(0) = D(0)
E(n + 1) = D(n + 1) ⨂ D(n)

TODO: Visualisation des différents encodages différentiels d’une image source avant et après pour chaque channel? Découpé par channel et combiné? Mais quelle courbe de remplissage utiliser?

TODO: Comment introduire de la perte dans le codage différentiel (Masque, …)

Compression sans perte

Table des matières
Codage par plages
Lempel-Ziv

Codage par Plages

Le codage par plages, (en anglais Run-Length Encoding ou RLE), est un des algorithme de compression sans perte les plus simple. Il consiste a remplacer des répétitions de valeurs identique par une paire indiquant la valeur et le nombre de fois ou cette valeur doit être copiée.

TODO: GIF pour visualiser

TODO: Implémentation concrètes possibles de RLE

Lempel-Ziv

Lempel-Ziv est une généralisation du codage par plage.

TODO: Explication de Lempel-Ziv

TODO: GIF pour visualiser

TODO: Implémentation concrète possible de Lempel-Ziv