[Compression d'images'] : TIPE : La compression DCT (Jpeg)
PRINCIPE
INTERETS - Comme la plupart des images sont régulières, les données de l’image transformée
sont concentrées dans le domaine des basses fréquences. (gain de place)
DECOMPOSITION L'image est avant tout décomposée en blocs de 8*8 qui
sont traités indépendament les uns des autres. La transformée cosinus discrete bidimensionelle s'écrit alors: avec et .
Une forme équivalente pour cette formule est la suivante : B = P-1AP où P est la matrice dont les coefficients sont :
Pour montrer cette formule, il suffit d'effectuer le produit matriciel et on retombe sur la première formule. De plus, P-1 = Pt, donc P est une matrice orthogonale, ce qui permet de l'inverser rapidement pour obtenir la transformée inverse (on prend juste la transposée) Cette constatation peut inspirer la remqrque suivante : Si on considère la base (Eij) de l'ensemble des matrice de taille 8*8, alors, comme P est inversible, P-1AP est également une base. C'est la base qui correspond à la décomposition de l'image par la transformée de Fourrier. En effet, l'image est alors combinaison linéaire de ces vecteurs là. Il est représenté ici les vecteurs de cette base :
QUANTIFICATION Le but est le suivant :pondérer l’importance des différents domaines de fréquences, sachant que la vision humaine est moins sensible aux hautes fréquences de détails.On va donc attribuer à chaque donnée un coefficient de poids qui correspond à son importance dans l'image. Cela revient à diviser les coefficients de Fourrier de l'image par ces coefficients de poids, et ne garder que ceux supérieurs à une certaine valeur. (on ne garde que les fréquences vraiment représentée dans l'image). La matrice de quantification est empirique. Elle n'est pas unique.Une matrice convenable est la suivante :
Elle est caractérisée par des coefficients croissent en même temps que la fréquence globale du coefficient. Comme chaque coefficient est caractérisé par deux fréquences (une verticale et une horizontale - CF image ci-dessus) on appelle fréquence globale la somme des deux fréquence. On constate que dans la matrice de quantification, à fréquence globale identique on a le même coefficient de poids. L'utilisation pratique de cette matrice est très simple. On la note Q = (qij). On note également Q' l'image transformée et quantifiée. On a alors : q'ij = qij / bij Cela correspond bien à ce que l'on veut faire : on "écrase" les hautes fréquences pour privilégier les basses fréquences auxquelles l'oeil humain est plus sensible.
CODAGE ENTROPIQUE Avant toute chose, la matrice représentant l'image [en deux dimensions] est linéarisée afin de subir un codage réversible (ou entropique). Il est effectuée en diagonale.
Enuite, un codage RLE est appliqué, puis un codage de Huffman. Le principe de ce codage est le suivant : si on cosidère un fichier, celui-ci est constitué de données qui sont toutes codées avec la même quantité d'information (sur 8 bit ou 16 bit par exemple). Or, si certaines données reviennent beaucoup plus souvent que d'autres, il est plus avantageux de les coder sur un petit nombre de bit, quitte à utiliser plus de bits après pour les données qui reviennent rarement. Huffman a trouvé un algorithme qui permet d'attribuer à chaque valeur possible un code qui répond aux exigences précédentes et qui permet une lecture du fichier codé même lorsque les codes sont mis bout-à-bout (unicité de l'interprétation du fichier codé). Pour plus de détails sur Huffman, je vous renvoie à ces sites : http://www.alphabeta-net.com/Huffman.html Il existe d'autres algorithmes de codage reversible : Shannon Fano, LZW, codage arithmétique.
EXEMPLES Voici l'image sur laquelle on travaille (le contraste a été accentué) :
Guillem PRATX - Mail : mon nom de famille @stanford.edu |