Page de Titre Table détaillée |
|
I.S.I. Gramme |
|
Page de Titre Table détaillée |
|
I.S.I. Gramme |
Un des traitements les plus étudiés est la compression (et la décompression, bien sûr) d'images. Pour le stockage, et plus encore, pour la transmission radio ou téléphonique, il est vital de réduire la taille de mémoire occupée par une image, en perdant le minimum de qualité. De nombreux algorithmes existent, dont les (de plus en plus célèbres) JPEG et MPEG.
Les méthodes de compression exploitent la redondance spatiale interne à une image (plages de même couleur) ainsi que la corrélation entre points voisins. La moindre sensibilité de l'oeil aux détails fins (images fixes) et aux images en mouvement rapide (images animées) sont aussi des facteurs favorisants. Enfin, la redondance entre images successives est exploitées dans la compression MPEG. On parle alors de compression 'interframe' comparée à la compression 'intraframe' utilsée pour les images fixes.
Il existe plusieurs variantes, de complexité croissante, de la norme MPEG : MPEG-1, MPEG-2 et MPEG-4 sont les plus connues. Le MPEG-2 ajoute à la compression de base une notion de 'profils' qui vont de 'petits débits pour internet' jusqu'à 'haut débit pour codage interne dans les studios de production'. MPEG-4 est une mouture récente qui encapsule audio, vidéo et autres données pour permettre une interactivité du spectateur avec le flux. Exemples : sous-titres multilingues, zones cliquables dans les images, mots-clés pour une recherche de séquences dans un film,etc...
Si une image contient une suite assez longue de pixels identiques, il devient intéressant de ne pas les recopier individuellment, mais plutôt de répertorier le couple nombre/valeur de couleur. Le taux de compression obtenu est d'autant plus élevé que les zones de couleur uniforme sont grande. RLC = Run Length Coding. Ce codage est sans perte. Il est utilisé dans de nombreux utilitaires comme ZIP, ainsi qu'en étape intermédiaire dans les codages JPEG et MPEG.
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 donc 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. Après l'étape intermédiaire DCT dans la compression JPEG, on applique une compression RLC et un codage VLC pour diminuer sans pertes la masse d'informations présentes.
On peut démontrer que la quantité d'informations Q transmise par un élément
est égale au logarithme en base 2 de l'inverse de sa probabilité d'apparition Dans
la formule ci-contre, H est l'entropie.
Le codage entropique est aussi connu sous le nom de codage de Huffman. En voici le principe général :
On reclasse les éléments par ordre de probabilité d'apparition
On prend ensuite les 2 éléments de probabilité les plus faibles et on les regroupe en un seul de probabilité égale à la somme des probabilités des 2 éléments. On attribue le bit 0 à celui de plus faible probabilité et 1 à l'autre.
On recommence jusqu'à épuiser toute la liste (probabilité cumulée = 100%).
On construit ainsi un arbre de codage de Huffman où on attrbue à chaque élément le code obtenu en mettant bout à bout les bits rencontrés en chemin.
Les codes les plus fréquemment utilisés ont donc des 'noms' binaires très courts, comme '010' par exemple, alors que des éléments rarement employés sont codés sur plus de bits (par exemple 00100100).
La norme de compression d'images fixes JPEG comprend de nombreuses options et nous renvoyons le lecteur aux sites officiels (www.mpeg.org et autres). Elle peut être avec ou sans pertes de qualité (sans perte = réversible) La méthode avec pertes permet évidemment des taux de compression de beaucoup supérieurs (typiquement 10 à 20).
La compression JPEG se décompose en sept étapes reprises ci-dessous.
La compression JPEG peut s'appliquer à des images monochromes (luminance seule) ou à des images couleurs RGB (3x8 bits pour les trois composantes rouge, vert et bleu). Elle est toutefois le plus souvent appliquée au images codées en YUV, comme les images PAL de nos TV, car le taux de compression obtenu est meilleur. la correspondance entre RGB et YUV est univoque et réversible : Y = luminance, U = R-Y, V=B-Y. Toutefois, on constate que les signaux de chrominance renferment le plus souvent beaucoup moins d'informations que la luminace et on ne les code donc que sur une résolution inférieure de moitié en vertical. Ce codage particulier est appelé 4:2:2, ce qui décrit la proportion de bits utilisés pour décrire les trois composantes YUV à l'intérieur du signal. Cette décimation des informations de couleur est en général assez peu perceptible (on l'utilise en studio). On utilise ausii un codage 4:2:0 qui réserve encore moitié moins de place aux informations de couleur. La dégradation de qualité étant plus importante, cette compression n'est utilisée que pour la diffusion finale quand le signal ne doit plus être considéré comme une 'source' d'information susceptibler d'être réutilisée.
L'image est découpée en blocs carrés de 8 pixels. Une image TV PAL standard (dite aussi CCIR 601) de 720x576 pixels codée en YUV 4:2:2 donnera donc 6480 (90x72) blocs pour la luminance Y et 3240 (90x36) blocs pour chacune des composantes U et V. Les images fixes JPEG de taille quelconque seront coupées de la même manière, après arrondi de leur taille au multiple de 8 le plus proche.
On obtient donc par image 6480 blocs de valeurs de 0 à 255 pour la luminance Y et 3240 blocs de valeurs de -128 à +127 pour les signaux de chrominance U et V.
La transformée DCT (Direct Cosine Transform) est un cas particulier de la transformée de Fourier, qui dans certaines conditions, décompose le signal en une série de fonctions uniquement cosinus et en phase avec le signal d'origine, ce qui réduit de moitié le nombre des coefficients nécessaires. Dans le cas des images, on utilise une DCT bidirectionnelle qui transformera un bloc de NxN pixels (de luminance ou de chrominance) en un autre bloc de NxN coefficients correspondant à l'amplitudes des fonctions harmoniques dans l'espace transformé
Les compressions JPEG et MPEG ont choisi de toujours travailler sur des blocs
de 8x8 pixels. Le premier coefficient, en haut à gauche de la matrice, représente la
composante continue. L'élément en bas à droite, celui de fréquence la plus élevée
dans les deux directions. En général, l'élément (0,0 a une valeur élevée et les
autres des valeurs beaucoup plus faibles, voire nulles. Ceci dépend bien sûr de contenu
de l'image. On constate très généralement que la quasi totalité de l'information
contenue dans l'image se concentre dans le coin supérieur gauche de la matrice des coefficients.
On notera que la DCT est réversible et ne réduit pas la qualité de l'image, mais elle la rend beaucoup plus facile à comprimer par les étapes suivantes.
C'est ici que l'on réduit vraiment la quantité d'information de l'image et donc que l'on dégrade le signal original. Le seuillage consiste à mettre à zéro toutes les valeurs de la matrice inférieures à un seuil donné. Plus celui-ci est élevé, plus la compression sera forte. La quantification réduit les nombres restant à un petit nombre de valeurs discrètes. La composante continue (coin supérieur gauche de la matrice) est codé différemment car on lui demande une beaucoup meilleure précision que les autres. Il est codé en DPCM (Differential Pulse Code Modulation) c'est à dire en ne traitant que la différence par rapport à la valeur au bloc précédent.
Dans l'exemple de la figure ci-dessus, si le seuil est à 10, il ne reste que 11 coefficients non nuls sur les 64. La quantification diminuera le nombre de valeurs différentes présentes dans la matrice, ainsi par exemple, 12 sera assimilé à 14 et 20 et 21 seront considérés comme identiques. La composante continue (987 dans l'exemple) sera codée comme valant un nombre de petite taille, différence entre 987 et la luminosité moyenne du bloc précédent dans l'image.
Les valeurs de la matrice sont ensuite lues et rangées dans une table à une seule colonne. On lit les valeurs en zigzags inclinés à 45° en commençant par le coin supérieur gauche et en finissant en bas à droite. De cette façon le vecteur des valeurs contient presque toutes ses valeurs non nulles au début et presque toujours un grand nombre de zéros à la fin. Ceci facilite de nouveau les étapes de compression suivantes.
On code le vecteur des coefficients sous forme de couples (nombre, valeur) comme décrit ci-dessus.
Cette dernière étape utilise le codage entropique et code les valeurs numériques les plus fréquentes avec un nombre de bits faible et les valeurs les plus rares avec un nombre de bits plus élevé. Le taux de compression des deux étapes RLC et VLC est de l'ordre de 60 à 70% dans les cas usuels. Cette compression se fait sans pertes (les pertes sont faites lors du seuillage et de la qualtification).
Résumé de la méthode JPEGJPEG est une méthode basée sur la transformation mathématique DCT (Discrete Cosine Transform) qui permet des taux de compression sans perte de qualité d'un facteur 3 environ, et avec une perte de qualité acceptable d'un facteur de 10 à 30.
La compression JPEG applique la transformée DCT à des carrés de 8x8 pixels, applique une décimation plus ou moins forte des paramètres obtenus, puis une étape de compression sans perte de type Lempel-Zipf (comme les fichiers ZIP). Le tout donne une qualité variable et un taux de compression atteignant 30. Certains logiciels de compression JPEG sont meilleurs que d'autres. Un bon est JPEG Optimizer. |
 |
MPEG est une extrapolation du précédent, appliquée à des groupes d'images successives (films, vidéo 'live'). Les taux de compression atteignent 100 environ, car on bénéficie de la redondance entre deux images successives : les parties identiques de deux images consécutives ne sont pas recopiées en mémoire, on se contente de repérer leur déplacement relatif et de mémoriser les coordonnées de la zone et son déplacement.
Une application pratique du MPEG associé à la compression du son se retrouvait déjà dans les maintenant défunts Vidéo-CD ou CDI (Compact Disc Inter–actif) développés par Philips et commercialisés à partir de 1993. L’encodage MPEG-1 était à débit fixe (150 KBytes/s). Mais il y a surtout les DVD qui ont fait leurs débuts en 1998, encodés en MPEG-2 (débit variable de l'ordre de 8 Mbits/s, haute résolution, son multilingue surround).
La méthode de compression MPEG-2 est devenue une norme (la norme DVB, voir www.dvb.org) pour la télévision digitale en europe et au japon. La variante américaine, fort proche, s'appelle ATSC. Cette même norme couvre aussi les images de haute résolution de la TVHD (en 1920x1080 pixels à 24, 25, 50 ou 60 images/seconde). Cette variante est utilisée pour les premiers cinémas électroniques. Les débits de la télévision numérique non comprimées sont de l'ordre de 270 Mbits/seconde. Après compression MPEG-2, ce débit tombe entre 4 et 15 Mbits/s. Le cinéma électronique (e-Cinéma) voit son débit passer de 1 Gbit/s à environ 50 ou 80 Mbit/s lors de la compression. La société liégeoise EVS se lance dans le cinéma électronique avec de la compression "MPEG-2 High Definition" ( www.evs-cinema.com ).
Il existe aussi des méthodes de compression par ondelettes (wavelets) et les compressions Fractales (d’Iterated systems) qui compriment des photos de 200:1 avec un temps de calcul important à l'encodage, mais faible à la restitution. C'est l'outil de compression idéal pour les CD-ROM comme Encarta de Microsoft qui l’utilise. On trouve aussi la compression wavelet dans les expériences de DISNEY en cinéma électronique (avec la société Quvis pour les images animées); la première salle commerciale de ce type en Belgique a démarré le 2 février 2000 avec la projection de 'TOY STORY 2' à Kinepolis Bruxelles en Février 2000. La compression wavelet fera partie de la nouvelle norme JPEG2000 qui est devenue officielle en l'an 2000 (d'où son nom).
Petit dictionnaire des termes MPEG-2I-frame : image complète encodée avec une méthode de type JPEG. P-frame : image encodée en temps que différence avec l'image I-frame ou P-frame précédente. On ne mémorise que la différence entre les deux images (tel bloc de cette image est le même que tel bloc de l'image précédente, etc...) B-frame : image (B=bidirectionnel) encodée en temps que différence avec une combinaison de l'image I ou P précédente et de l'image I ou P suivante. On ne peut donc la décoder qu'après avoir lu un peu plus loin le fichier. GOP : Group Of Pictures, groupe d'images consitué d'une image I et de
plusieurs images P ou B. Un GOP typique en transmission TV est composé d'images
IBPBPBPBPBPB. On l'appelle un GOP12. Ce type de codage donne un bon compromis entre débit
et qualité. |
La TV digitale a vu ses premiers concepts émerger au début des années 90. Maintenant, on parle de suprimer les dernières émissions non-digitales d'ici 2005 à 2008 suivant les pays. Pourquoi ? Simplement parce qu'on peut placer 5 fois plus de canaux dans les mêmes bandes passantes sur cable, satellite ou émetteur hertzien. Ceci n'est possible que grâce à l'avènement de la compression MPEG-2 qui a fait passer la bande passante d'un signal vidéo de 270 Mbps (non comprimé) à 4, 6 ou 8 Mbps après compression.
A l'origine, MPEG-1 était une norme de compression d'images sur CD-ROM (les défunts CD-I et les VidéoCD encore forts populaires en Asie). Le débit était celui du CD audio, soit 1,5 Mbps pourl'image et le son. Outre la redondance spatiale utilsée par JPEG pour comprimer les images fixes, MPEG exploite la forte redondance temporelle des images pour réduire la quantité d'informations à transmettre. On sacrifie d'abord la résolution qui passe de 720x576 pixels en TV à 360x288 pixels en format SIF. MPEG-1 consacre 1,15 Mbps à la vidéo et 350 kbps à l'audio.
Le codage qui tient compte de l'élément temporel nécessite un dispositif d'estimation de mouvement qui est la partie la plus complexe d'un encodeur MPEG. Ce codage doit se faire en temps réel si on veut encoder des images en direct (en 'live'). Il est donc le plus souvent effectué par une combinaison logiciel/matériel pour disposer de la puissance de calcul nécessaire à coût raisonnable. Pour les application non-temps réel, comme le codage MPEG-2 pour les DVD, l'encodage peut être logiciel uniquement et muli-passe. Un première passe analyse la complexité des mouvements, les changements de scènes ,etc.. et la seconde passe se charge de l'encodage proprement dit.
La réalisation pratique d'un encodeur est donc un art qui doit mettre en balance rapidité, taux de compression, qualité et complexité. De plus, la nécessité d'un temps de synchronisation sur un flux pris 'au vol' qui ne doit pas dépasser la seconde limite le nombre d'images pouvant dépendre d'une même première à une douzaine (12,5 images = 1/2 seconde à 25 images par seconde).
MPEG définit trois types d'images (en fait, 4, mais le type D n'est jamais utilsé dans les applications TV usuelles)
Codées comme des images JPEG sans référence à d'autres images du même flux vidéo. Taux de compression faible.
Codées par rapport à l'image I ou P qui la précède, grâce aux techniques de prédiction avec compensation de mouvement. Cette technique prédictive n'étant pas parfaite, on limite le nombre d'images P suivant une I à un nombre faible (typiquement 3 à 6). Taux de compression plus important que pour les images I.
Codées par interpolation entre les images I ou P qui les encadrent. Elles ne servent de référence à aucune autre image, donc les erreurs qu'elles contiennent ne se propagent pas. Taux de compression très élevé.
Le groupe d'image définit la structure du flux MPEG. Ainsi un
GOP long, comme ceux des flux TV des bouquets satellites sera par exemple structuré comme
suit : IBBPBBPBBPBB. On l'appelle un GOP 12,3. Les deux paramètres indiquent le nombre
d'images du groupe et le nombre d'images d'un sous groupe se terminant par une image P.
On remarque que pour calculer au décodage le contenu d'une image B, on a besoin de l'image qui suit. Les images sont donc transmises dans un ordre différent de celui de leur apparition à l'écran : les images B sont toujours transmises après l'image P qui les suit logiquement.
Exemple :
Ordre d'affichage : I1, B2, B3, P4, B5, B6, P7, I2, ...
Ordre de transmission : I1, P4, B2, B3, P7, B5, B6, I2, ...
On remarque que le taux de compression supérieur apporté par les images B se paie en taille mémoire dans le décodeur (on doit stocker plus d'images pour re-créer les B) et un temps de décodage plus long (au minmum quelques images de décalage avant de pouvoir afficher dans l'ordre correct).
L'estimation de mouvement consiste à trouver un vecteur assurant la correspondance entre une zone de départ sur une image et une zone d'arrivée sur la suivante. Les zones de recherches sont des carrés de 16 pixels de côté appellés 'Macroblocs'.
On déplace le bloc de départ dans une fenêtre de recherche de manière à trouver le macrobloc le plus ressembalnt (Block matching), ce qui donne un vecteur de mouvement qui s'appliquera à tous les pixels du macroblocs dans les trois plans Y, U et V de l'image. Cette comparaison se faisant entre deux images I ou entre une I et une P, les vecteurs peuvent être de taille assez importante (parfois il y a trois images ou plus entre les images comparées). Pour les images B, les vecteurs de mouvements sont obtenus par interpolation entre les valeurs des images I ou P qui les encadrent.
On calcule ensuite la différence entre le bloc à coder et le bloc que l'estimation de mouvement a trouvé le plus ressemblant et cette différence est soumise à un codage similaire à celui des images I.
Dans le but de simplifier le logiciel et le matériel, le débit est le plus souvent fixe en sortie du décodeur. Les exceptions à cette règle générale sont certains bouquets numériques et les DVD dont le débit peut être variable dans certaines limites précises. Le processus de compression décrit ci-dessus ne garantit absolument pas un taux de compression fixe, ni donc un débit constant. On peut réguler le débit en utilisant une mémoire tampon en sortie de l'encodeur dont on surveille l'état de remplissage de façon à le maintenir dans certaines limites raisonnables. Pour ce faire, on joue sur les coefficients de quantification dont l'influence sur le débit est très importante.
Cette page est copyright B.Michel, 2009