Etat de l’art sur la compression d’images médicales

Codage de Huffman

Les codes de Huffman, mis au point en 1952[6], [7], sont parmi les premiers à avoir émergés et sont donc également parmi les plus répandus.
Le principe est d’attribuer un code court à un symbole fréquent et un code plus long à un symbole plus rare. En se plaçant dans le cas d’un alphabet de sortie binaire, l’attribution du nombre de bits pour chaque symbole se fait par le biais d’un arbre binaire, construit en fonction de la fréquence d’apparition des symboles.

A chaque noeud de l’arbre est associé la fréquence d’apparition de l’ensemble des symboles présents dans son sous arbre. L’arbre est construit de manière ascendante à partir de ses feuilles. Chaque feuille correspond à un symbole, et à sa fréquence d’apparition. Itérativement, jusqu’à l’obtention de la racine, un noeud père est généré pour le couple des deux noeuds ayant la fréquence d’apparition la plus faible.

Le code de chacun des symboles est alors le chemin partant de la racine jusqu’à la feuille lui correspondant (bit 0 pour aller au fils gauche, et bit 1 pour aller au fils droit par exemple). Ce code est donc défini de telle sorte qu’aucun des symboles de l’alphabet ne soit le préfixe d’un autre : chaque symbole étant associé à une feuille de l’arbre, le chemin qui permet d’y accéder ne peut en aucun cas être le sous-chemind’un autre. Ainsi, le codage est non ambigu.
Le code Huffman peut être statique, transmis ou adaptatif. Lorsqu’il est statique, le code est fixé pour le codeur et le décodeur et n’a donc pas besoin d’être transmis.
Cependant, il n’est pas toujours adapté aux données.

Lorsqu’il est transmis, l’arbre doit être construit par le codeur à partir des fréquences d’apparition des symboles : un parcours supplémentaire des données est donc nécessaire (sur la totalité, ou un échantillon représentatif). Il a également un coût pour la compression puisqu’il doit être transmis.
Enfin lorsqu’il est adaptatif, en partant d’un arbre particulier les fréquences des symboles sont mises à jour au fur et à mesure de leur apparition. L’arbre doit donc être mis à jour régulièrement, ce qui demande un temps de calcul important. L’arbre de départ peut également être statique ou transmis.

Le principe est le suivant

Les probabilités d’occurrence de chaque message sont placées dans une liste dans un ordre décroissant. Nous dirons que la liste est composée d’enfants.
Les deux probabilités les plus faibles sont identifiées en fin de liste.
La somme des deux probabilités est placée à sa place dans la liste triée. Elle constitue un noeud parent. Les deux enfants sont retirés de la liste.
Le chemin «enfant de plus faible probabilité, parent» est codé par un 1, l’autre par un 0.
La procédure reprend à l’étape 2 jusqu’à ce qu’il ne reste plus qu’une probabilité dans la liste.

Codage Arithmétique

Contrairement à l’algorithme de Huffman qui associe aux symboles des motifs binaires dont la taille dépend de leur distribution. Le codeur arithmétique traite le vecteur de données dans son ensemble, en lui associant un unique nombre décimal rationnel varie entre 0 et 1 [9].
Ce nombre code est construit par subdivisions récursives d’intervalles. Un intervalle est subdivisé pour chaque nouveau symbole qui appartient à la séquence.
On obtient, à la fin, un sous-intervalle de l’intervalle [0, 1[. Tel que tout nombre réel appartenant à cet intervalle représente la séquence à coder. Ce nombre compris entre 0 et 1, possède d’autant moins de chiffres après la virgule que la redondance du vecteur de données. Ces chiffres décimaux dépendent non seulement des symboles du vecteur dans l’ordre où ils apparaissent, mais aussi de leur distribution statistique.

Codage par plages de zéros (RLE)

Toutefois, il est courant qu’en sortie du quantificateur, la source ne soit pas totalement dé-corrélée, c’est le phénomène de mémoire. Par exemple dans le cas des coefficients d’ondelettes, les coefficients de faible amplitude ont tendances à s’agglutiner. Les codeurs entropiques évoqués ci-dessus ne peuvent exploiter cette mémoire de la source quantifiée. Il existe néanmoins des codeurs capables d’exploite les statistiques d’ordre supérieures : les codeurs entropiques adaptatifs et les codeurs par plages de zéros. Les codeurs par plages [10](ou run-length en anglais) sont particulièrement adaptés pour coder les coefficients d’ondelettes.
L’idée de base consiste à coder la longueur d’une série d’échantillons nuls plutôt que de coder chaque échantillon indépendamment. Le code run-length doit être associé ensuite à un codeur entropique classique.
Le principe de compression RLE (Run Length Encoding, parfois notée RLC pour Run Length Coding) est assez simple à mettre en oeuvre. Il repose sur le fait que dansune image, il existe de nombreuses répétitions d’un même pixel, ou d’une même séquence de pixels, tous juxtaposés.

Ainsi, au lieu de coder chaque pixel d’une image, le RLE regroupe les valeurs voisines identiques et ne transmet la valeur qu’une seule fois, précédée par le nombre de répétitions.
La compression RLE est régie par des règles particulières permettant de compresser lorsque cela est nécessaire et de laisser la chaîne telle quelle lorsque la compression induit un gaspillage lors que dans la redondance des caractères est faible.

Codage Lempel-Zif-Welsh (LZW)

Le codage LZW [8] est une technique de compression réversible qui peut être appliquée à tout type de fichier de données, que ce soit : texte, image, fichier informatique…elle a été adoptée pour la mise en oeuvre du format de compression d’images ‘GIF’.
Le principe général de cette méthode consiste à créer un dictionnaire contenant toutes les répétitions.
Il doit être construit de la même manière, à la compression et à la décompression, et contenir les mêmes informations.
Tous les ensembles de lettres qui sont lus sont placés dans le dictionnaire, et sont numérotés.
A chaque fois qu’un ensemble est lu, on regarde s’il en existe déjà un qui est identique. Si c’est le cas, on émet son numéro vers le fichier compressé. Sinon, on le rajoute à la fin du dictionnaire, et on écrit chacune des lettres dans le fichier compressé.
Quand on écrit un numéro au lieu d’écrire des lettres, il y a un gain de place, mais pour cela, il faut déjà avoir beaucoup de chaînes dans le dictionnaire.
L’apprentissage est donc nécessaire pour que la méthode soit efficace.

Les caractéristiques essentielles de LZW sont :
 Il n’existe pas de table d’en-tête : le dictionnaire est construit au fur et à mesure de la lecture du fichier tant à la compression qu’à la décompression.
 L’algorithme ne fonctionne pas sur un nombre fixe de motifs mais apprend les motifs du fichier durant la lecture du fichier à comprimer.
 La compression se fait en une seule lecture.

COMPRESSION AVEC PERTE D’INFORMATIONS

Contrairement aux méthodes de compressions sans pertes d’informations, ce type de compression comporte une perte de données pendant le processus. Le résultat qu’on peut en obtenir est une version dégradée de l’ image originale. Le but de ce type de compression est d’éliminer le plus d’informations possible sans atténuer la qualité de l’image perçue par le système visuel humain. On peut distinguer deux grands types de compression pouvant générer des pertes: le codage prédictif et le codage par transformée, ce dernier est de loin le plus utilisé dans la compression d’image.

Un codeur avec pertes idéal [3] est composé d’un module de transformée, un module de quantification et un codeur entropique (Figure (І-2)).

Quantification

La quantification est un processus qui permet d’associer à un nombre réel (resp. vecteur de réels) un nombre entier (resp. vecteur d’entiers). Dans un certain sens on peut considérer qu’elle réalise une compression implicite (passage des réels aux entiers) en réduisant le nombre de bits nécessaires à la représentation de l’information image. On distingue en général deux types de quantification: la quantification scalaire et la quantification vectorielle [4].

Compression par transformation

Les méthodes de compression par transformation n’agissent pas directement sur l’image numérique dans sa représentation canonique, mais sur le domaine de sa transformée.
Cette transformation peut être linéaire ou non.
Il est bien connu qu’une transformation peut permettre de mettre en évidence certaines propriétés de l’image que la représentation originale ou canonique ne laisse pas apparaître.
En partant d’un ensemble de valeurs numériques corrélées d’une image, le but est d’obtenir un autre ensemble de valeurs le moins corrélées possible dans l’espace transformé.

En général, les schémas de codage par transformation subdivisent l’image de taille NxN en sous-images de taille plus petites avant de faire subir à chacune de ces sous images une transformation.

On privilégie les transformations qui sont unitaires et qui conservent l’énergie. La transformation consiste en la décomposition de l’image selon une base adéquate de fonctions telles que:
 Les coefficients de la transformation soient indépendants
 Qu’un nombre minimum de ces coefficients contienne une proportion importante de l’énergie de l’image.
Ainsi, on pourra mettre à zéro certains d’entre eux sans nuire de manière significative ni à la quantité d’énergie, ni à l’aspect visuel de l’image reconstruite.

On peut distinguer plusieurs transformées dont [11]:
 Transformation de Karhunen-Loeve (TKL).
 Transformation de Fourrier discrète (TFD).
 Transformation de Hadamard (TH).
 Transformation de Haar (THA).
 Transformation en cosinus discrète (DCT).
 Transformation par ondelette discrète (DWT).

La transformation de Fourier et celles qui en découlent, telles la transformation en sinus, la transformation en cosinus, sont très utilisées en analyse et en filtrage du signal [12].

Ces transformations peuvent être mises en oeuvre à l’aide d’algorithmes rapides comme la FFT et ses variantes.

La variable de l’espace transformé étant la fréquence, une telle décomposition permet de mieux observer la répartition fréquentielle de l’image.

Étant donné que ce sont les premières harmoniques qui contiennent la quasi-totalité de l’énergie, il est donc possible de mettre à zéro une proportion importante des coefficients et de coder l’image à moindre coût.

Table des matières

Introduction générale
Chapitre І : Etat de l’art sur la compression d’images médicales
I. Introduction
II. But de la compression d’image
III. Compression sans perte d’informations
1. Codage entropique
i. Codage de Huffman
ii. Codage Arithmétique
2. Codage par Plages De Zéros (RLE)
3. Codage Lempel-Zif-Welsh (LZW)
IV. Compression avec perte d’informations
1. Quantification
i. Quantification scalaire
ii. Quantification vectorielle
2. Compression par transformation
3. Codage par prédiction
4. Codage des sous-bandes
i. Algorithme EZW
ii. Algorithme SPIHT
iii. Algorithmes EQ
V. Evaluation de la qualité de compression
i. Taux de compression
ii. Taux d’information
iii. Mesures de distorsion
VI. Etat de l’art sur la compression d’images médicales
VII. Conclusion
Chapitre II : Transformée en Ondelettes
I. Introduction
II. Principe des ondelettes
III. Transformée en ondelettes
1. Transformée en ondelettes continue CWT
2. Transformée en ondelettes discrète DWT
IV. Analyse Multi Résolution
1. Définition
2. Construction d’Ondelettes à partir de l’analyse multi résolution
a. Fonction d’échelle
b. Ondelette
c. Les filtre H et G
3. Propriétés Fondamentales d’une Ondelette
V. Extension de la transformée en ondelettes aux signaux bidimensionnels
VI. Analyse
1. Décomposition
2. Reconstruction des lignes
3. Quelques exemples d’ondelettes
i. Ondelette de Haar
ii. Ondelette de Morlet
iii. Ondelette de Mexican Hat
iv. Ondelette de Shannon
VII. Ondelettes Bi orthogonales
1. Intérêt
2. Inconvénient
VIII. Conclusion
Chapitre III : Transformée en Paquets d’ondelettes
I. Introduction
II. Analyse Multi Résolution
III. Théorie de l’AMR
a) Définition
b) Interprétations
IV. Ondelettes et fonctionsd’échelle
a) Espaces de détails
b) Bancs de filtres à reconstruction parfaite et algorithme à trous
c) De l’algorithme à trous aux fonctions d’échelle
V. Algorithme
VI. Avantages et applications
VII. Application aux images
a) Algorithme pyramidal
b) Filtrage par bande
VIII. Conclusion
Chapitre VI : Résultats des expériences
I. Introduction
II. Résultats de simulations
1. Performances du SPIHT et EZW
2. Choix de la meilleure ondelette
a) Application 1 : Ondelettes Debauchies
b) Application 2 : Ondelette Coiflet et Symlet
c) Application 3: Ondelette Biorthogonale
Comparaison des résultats
3. Influence du niveau de compression d’ondelette couplé avec le SPIHT
Interpretation
4. Compression d’images médicales par PWT couplée avec SPIHT
III. Conclusion
Conclusion Générale
Annexes
Bibliographie

Télécharger le rapport complet