Travaux pratiques de traitement d'images numériques - L2TI

Institut Galilée
Télécom 3

Travaux pratiques de traitement d'images numériques
Deuxième séance
Institut Galilée
2010-2011

G. Dauphin & A. Beghdadi

Préambule
Les programmes nécessaires pour faire ce TP sont huff2norm.m, norm2huff.m,
frequency.m qui sont des fonctions réalisées par Giuseppe Ridinò
(http://www.mathworks.com/matlabcentral/fileexchange/4900).
Les images sont disponibles dans Matlab

A. Codage sans perte : l'algorithme de Huffman
Introduction - Rappels
Le codage de Huffman est un algorithme de compression de données sans
perte élaboré par David Albert Huffman et publié en 1952. Le code est
déterminé à partir d'une estimation des probabilités d'apparition des
symboles de source, un code court étant associé aux symboles de source les
plus fréquents. Le principe du codage de Huffman repose sur la création
d'un arbre binaire, c'est-à-dire un arbre où chaque n?ud a deux fils, le
fils de gauche est étiqueté par un zéro et le fils de droite est étiqueté
par un 1. Chaque terminaison représente un des symboles à coder. Le code
associé au symbole est une succession de 0 et de 1, la succession qui
correspond au parcours depuis la racine jusqu'à la terminaison
correspondant au symbole. Une implémentation du code de Huffman est donnée
par les programmes huff2norm.m et norm2huff.m
Cet algorithme est en un certain sens optimal c'est-à-dire que la
longueur statistiquement nécessaire pour coder un des symboles est presque
égale à l'entropie

[pic] (1)
où [pic] et [pic]et [pic]est la probabilité du symbole i et [pic]est la
longueur du code associé au symbole i.

1. Application sur des données synthétiques


En utilisant la simulation d'un ensemble de données aléatoires ayant
une distribution de probabilités choisie préalablement suivant une
fonction déterministe ou de façon aléatoire, montrez que le codage
puis le décodage de ces données se fait sans dégradations et que la
relation (1) est respectée.

Instructions Matlab à tester pour réaliser le programme :
Simulation de données aléatoires suivant une loi uniforme à valeurs dans un
alphabet à 256 éléments :
>>x=ceil(255*rand(1,2000)) ;
On mesure l'histogramme des données x en le mettant sous la forme d'un
vecteur x(:) puis en appliquant la fonction Matlab hist.
>>histogrammeObserve=hist(x(:),0:255);
L'axe des abscisses est l'ensemble des éléments de l'alphabet et l'axe des
ordonnées est le nombre d'occurrences.
>>figure(1) ; plot(0:255,histogrammeObserve);
Choix aléatoire d'une distribution de probabilité :
>>rand(1,256) ; histogrammeDemande=ans/sum(ans) ;
Distribution de probabilité choisie à partir d'une fonction :
>>sin(pi*(1:256)/257) ; histogrammeDemande=ans/sum(ans) ;
A partir de ces histogrammes demandés on peut construire les fonctions de
répartitions associées que l'on note [pic] qui est à valeurs dans [0,1]:
>>figure(1) ; plot(0:255,cumsum(histogrammeDemande));
Soit U une variable aléatoire qui suit une loi uniforme sur [0,1]. Alors
[pic]est une variable aléatoire qui suit la loi de B. En effet :
[pic]
Il nous suffit donc de trouver une fonction qui inverse la fonction de
répartition, c'est-à-dire une fonction qui retrouve l'indice d'un élément
d'un vecteur à partir d'une valeur approchée de sa valeur et ce en
supposant seulement que ce vecteur est bien ordonné. La fonction CptAsyn
réalise ceci, t désigne les valeurs approchées recherchées et A désigne le
vecteur bien ordonné. Dans cette longue instruction, ce qui apparaît comme
des guillemets est en fait une juxtaposition de deux apostrophes et est
interprété lors de l'exécution en Matlab comme une transposition de la
matrice, ce qui apparaît comme une apostrophe est en fait une indication de
début ou de fin de chaîne de caractères.
>>CptAsyn=inline('reshape(sum(ones(length(t(:).''),1)*(A(:).'')> CptAsyn([-1; 4; 1],[0 3])
La variable aléatoire peut donc être simulé par
>>x=CptAsyn(rand(1,20000),cumsum(histogrammeDemande));
On peut contrôler que la variable aléatoire simulée est bien conforme à la
distribution de probabilité demandée :
>>histogrammeObserve= hist(x(:),0:255);
>>histogrammeObserve=histogrammeObserve/sum(histogrammeObserve);
>>figure(1) ;
plot(0:255,histogrammeObserve,'b',0:255,histogrammeDemande,'r');
La fonction norm2huff fournit le code correspondent aux données dans x
suppose à valeurs entières entre 0 et 255. info est l'ensemble des
informations nécessaires pour décoder la séquence. Le code ainsi obtenu est
une succession d'entiers entre 0 et 255, chacun code sur 8 bits.
>>[code,info]=norm2huff(uint8(x));
Longueur du code moyen par symbole
>>length(code)*8/length(x)
Dans la pratique on est oblige aussi de stocker info, mais alors le lien
avec l'entropie est un peu modifié.
Pour calculer l'entropie, on peut utiliser la fonction Matlab entropy ou
calculer l'histogramme observé hO et évaluer
>> H=sum(hO(hO~=0)/sum(hO).*log2(sum(hO)./hO(hO~=0)));

2. Application à des images numériques bruitées et filtrées
On se propose, dans ce qui suit, d'analyser les effets de quelques
traitements sur le signal image en étudiant l'entropie associée à la
distribution des niveaux de gris.
2.1. Choisir une image en niveau de gris. Cette image sera notée A. Mettre
cette image au format double et à valeurs sur l'ensemble 0...255 (pour
l'affichage avec imshow, il faudra au préalable diviser à 255).
a. Déterminez et tracez l'histogramme des niveaux de gris de cette
image. En déduire l'entropie associée à cet histogramme.
b. Ajoutez un bruit blanc gaussien à l'image A. Soit B l'image ainsi
obtenue. Déterminez et tracez l'histogramme de B. Déduisez l'entropie
associée. Comparez à l'image A ; que peut-on en dire ?
c. On applique maintenant un filtre passe-bas à l'image A. Soit C
l'image résultante. Calculez l'histogramme et l'entropie associée. Comparez
aux deux cas précédents. Expliquez les résultats obtenus.
2.2. Dans chacun des trois cas (A,B et C) appliquez le code de Huffman.
Comparez les taux de compression et l'efficacité.

B. Transformée en cosinus discrète sur une image entière

B1. Application de la DCT globale
La transformée en cosinus discrète est utilisée dans la compression jpeg
parce qu'elle permet de concentrer l'information pertinente sur un petit
nombre de coefficients.

Choisissez une image entière en niveaux de gris, appliquez la
transformée en cosinus discrète. Où se trouvent, au sens de la valeur
absolue, les coefficients élevés et les coefficients faibles, si on
voulait lire les coefficients du plus élevés au plus faible quel
parcours parmi les coefficients faudrait-il faire ? Calculez le PSNR
entre l'image originale et l'image reconstruite en ne conservant que
les coefficients de la DCT dont les coordonnées vérifient i+j