Le codage zigzag:
Le codage de la matrice DCT quantifiée se fait en parcourant les éléments dans l’ordre imposé par une séquence particulière appelée séquence zigzag.
On lit les valeurs en zigzags inclinés à 45° en commençant par le coin supérieur gauche et en finissant en bas à droite. Cette séquence a la propriété de parcourir les éléments en commençant par les basses fréquences et de traiter les fréquences de plus en plus hautes. Puisque la matrice DCT contient beaucoup de composantes de hautes fréquences nulles, l’ordre de la séquence zigzag va engendrer de longues suites de 0 consécutifs.
Ceci facilite de nouveau les étapes de compression suivantes : les codages RLC et VLC.
Séquence
zigzag de lecture d’un bloc de 8x8 pixels
Dans le cas de notre matrice préférée, nous aurions obtenu la suite: 62 ; -4 ; 4 ; -1 ; -5 ; 2 ; -1 ; 3 ; -3 ; -1 ; 0 ; 0 ; 0 ; -1 ; 2 ; -1 ; -1 ; 0 ; 1 ; 1 ; 0 ; 1 ; 0 ; 1 ; -1 ; -1 ; 1 ; -1 ; -1 ; 1 ; 0 ; 0 ; 0 ; -1 ; 0 ; 0 ; 0 ; 0 ; 0 ; -1 ; 0 ; -1 ; 0 ; 0 ; 0 ; 1 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 1 ; 0 ; 1 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0. Admirez les suites de 0 consécutifs.
Deux mécanismes sont mis en œuvre pour comprimer la matrice
DCT quantifiée :
D’une part les suites de valeurs nulles sont simplement codées en donnant le nombre de 0 successifs. C’est le codage RLC (Run Length Coding). Si une image contient une suite assez longue de pixels identiques, il devient intéressant de ne pas les recopier individuellement. On traite l’image ligne par ligne en recherchant les séquences de pixels de même valeur. Le taux de compression obtenu est d'autant plus élevé que les zones de couleur uniforme sont grandes. Ce codage est sans perte.
D’autre part, les valeurs non nulles seront codées en utilisant une méthode de type statistique, comme le codage VLC (Variable Length Coding). Ce système est basé sur le fait que la probabilité d'apparition d'un élément codé sur N bits n'est pas la même pour tous les éléments. Par exemple, dans une image très sombre, la valeur 0 qui correspond au noir sera très fréquente. On a intérêt à coder sur un petit nombre de bits les valeurs qui sont les plus utilisées et à réserver des mots binaires de plus grande longueur aux valeurs les plus rares. Le codage VLC se combine remarquablement bien avec le codage RLC auquel il succède souvent, histoire d'augmenter encore le taux de compression.
Dans la compression JPEG, justement, on applique une compression RLC et un codage VLC pour diminuer sans pertes la masse d'informations présentes.
Ces étapes préparent l'application de l'algorithme d'Huffmann qui sera expliqué dans: