Embed Size (px)
Citation preview
MARTIN Benjamin Master MAD 1ere anneeUniversite d’Orleans 2005-2006
Etude statistique
d’histogrammes en image
Maıtre de stage : Maitine BERGOUNIOUX Tuteur : Jean-Pierre LAMARCHEUniversite d’Orleans - Faculte des Sciences1, Rue de Chartres BP 675945067 Orleans cedex 2
Telephone : (+33) 02.38.41.73.16 Telephone : ( +33) 02.38.41.71.71
1
1
Remerciements
Je tiens a remercier particulierement Madame Maitine Bergounioux,sans qui je n’aurais jamais pu faire ce stage, pour sa disponibilite et sonaide continuelle durant ces deux mois.
Je remercie egalement Monsieur ROZENBAUM et Monsieur ROUET,pour m’avoir fait decouvrir leur travail au sein de l’ISTO.
Et un grand merci a Amandine, Caroline et Xavier pour toutes lespauses durant le stage.
2
Table des matieres
1 Introduction 4
2 Analyse des images 5
2.1 Preliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1.1 Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.2 Probleme de contraste . . . . . . . . . . . . . . . . . . 62.1.3 Probleme du cache . . . . . . . . . . . . . . . . . . . . 9
2.2 Algorithme de demelange . . . . . . . . . . . . . . . . . . . . 112.3 Test de Kolmogorov-Smirnov . . . . . . . . . . . . . . . . . . 182.4 Automatisation . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Conclusion 22
4 References 23
5 Annexes 24
3
1 Introduction
Ce rapport presente le travail effectue durant 2 mois au sein dulaboratoire MAPMO (Mathematiques et Applications, PhysiqueMathematique d’Orleans) pour l’ISTO (Institut des Sciences de la Terred’Orleans) dans le cadre du stage de premiere annee de MasterMathematiques pour l’Aide a la Decision, qui s’est deroule du 10 mai au 10juillet 2006.
Le travail effectue contribue a l’etude de l’Alteration des pierres dupatrimoine bati, sujet de recherche au sein de l’ISTO. Le but de ce stageetait d’analyser les histogrammes des images de coupe de tuffeau, estimerles parametres statistiques des histogrammes et ainsi, fournir les basespour une segmentation en regions de la pierre.
4
2 Analyse des images
2.1 Preliminaires
Pour l’ensemble du stage, on va analyser des microtomographies detuffeaux obtenues a l’ESRF. Toutes les images de tuffeaux sont de memeresolution 512x512 pour une question de rapidite des algorithmes. Cellesd’origine sont en 2048x2048.Les resultats seront les memes que sur les images non retaillees, lacompression etant quasi-sans perte.Toutes les fonctions ont ete ecris sous MATLAB.
Le logiciel MATLAB
Le nom MATLAB provient de la contraction de MATrix LABoratory.C’est un langage de calcul scientifique base sur le type de variablematricielle. Ses grandes capacites de calcul numerique lui permet d’etreapplique a differents domaines scientifiques tels traitement du signal,automatisme, etc.
L’utilisation de MATLAB peut se faire de facon interactive en executantdes commandes directement apres le prompt ou par des scripts. Cesdernier peuvent etre des simples programmes ou des fonctions avec desparametres d’appel et de retour.
Malgre un prix eleve et une concurrence des logiciels gratuits (scilab entete) grandissante, MATLAB reste le plus complet, et surtout leperformant des logiciels de calcul matriciel.
Les fonctions sont places en annexe mais sont aussi en ligne :http://alainparaponaris.free.fr/stageisto/
5
2.1.1 Rappels
Chaque image (en niveau de gris) peut etre representee comme unematrice ou chaque element correspond au niveau de gris du pixel (pictureelement) de l’image. Une image de resolution 512x512 est donc une matricede dimension 512x512 ou le premier pixel est le premier element de lamatrice. Chaque element sont compris en 0 (correspondant au noir) a 255(correspondant au blanc)Pour eviter les confusions, element, pixel ou encore niveau de gris designela meme chose.Par convention on va appeller M la matrice image.
2.1.2 Probleme de contraste
On suppose que les photos des coupes de tuffeaux ont ete prise en memetemps. Malgre cela, on peut avoir des images avec un contraste different.
Exemple d’une meme image avec deux contrastes differents :
M(1,1)=102 M(1,1)=161
6
Histogramme associe aux deux images :
−50 0 50 100 150 200 250 3000
1
2
3
4
5
6x 10
4
−50 0 50 100 150 200 250 3000
1
2
3
4
5
6x 10
4
On remarque que pour deux contrastes differents sur une meme imageon obtient deux histogrammes differents. On va donc utiliser une fonctiond’uniformisation du contraste sur toutes les images :
autocontraste(nom,type)
Ou nom est le nom de base de l’image (ici ′ndrp_′) et type est le format del’image (ici ′png′) .
Pour etre certain d’avoir le meme niveau de gris, on prend comme reperele premier element de la matrice de chaque image. Il correspond a celui ducache.
On fait fait la moyenne sur toutes les images et on ajuste le contrastepour celles qui n’ont pas le meme que le niveau de gris moyen. Puis onecrase les anciennes images en les remplacant par les nouvelles.
Exemple d’utilisation
On prend deux images dont on change le contraste :
7
Puis on lance la fonction d’autocontraste :
On verifie maintenant que toutes les images sont au meme contraste :
8
2.1.3 Probleme du cache
Comme on a pu le constater sur les histogrammes precedent, il y a unpic sur un niveau de gris. C’est celui qui correspond au cache.L’analyse de l’image sera faussee si on garde ce cache, on propose donc unefonction qui transforme la matrice image en un vecteur dont on auraenleve au prealable les elements du cache :
[H,N]=histogramme3(M,cadre)
Ou M est la matrice image, cadre est le premier element de la matrice (iciM(1,1)) , N est le vecteur de la matrice image sans le cache et H est unvecteur de taille 256 qui comptabilise les niveaux de gris pour afficherl’histogramme.
Etant limite par les capacites de la machine, au prealable on fait un testpour connaitre la taille moyenne du vecteur image (sans le cache). Cevecteur moyen a 204774 elements. En initialisant le vecteur on gagne plusde temps que si l’on cree le vecteur au fur et a mesure.On part toujours du principe que le premier et dernier element de lamatrice fait partie du cache (ce qui est toujours le cas).
On parcourt donc chaque vecteur ligne de la matrice des deux cotes etprend en compte les element des qu’ils sont different du cadre. Comme onparcourt de chaque cote, les element restant ne font pas parti du cadredonc on passe a la ligne suivante.De plus si l’image possede plus d’element que le vecteur initialise, onrajoute a la fin du vecteur les elements manquant. Au contraire si levecteur initialise est trop grand, on le tronque a la bonne taille (donneepar un compteur).
Exemple d’utilisation
On teste la fonction sur une image :
9
ici le vecteur image est de taille 204772, on affiche l’histogramme del’image sans le cache avec bar(H) :
0 50 100 150 200 250 3000
500
1000
1500
2000
2500
10
En comparrant aux histogrammes precedent, on voit bien la disparitiondu pic due au cache. Sur cet histogramme, on remarque trois bosses dumelange des trois gaussiennes. On va maintenant etudier les histogrammesde toutes les images.
2.2 Algorithme de demelange
On va maintenant supposer que l’histogramme est issue d’un melange detrois gaussiennes.C’est a dire l’histogramme est une fonction d’une somme de densites de 3gaussiennes :
11
C’est a dire : f(x) =3
∑
i=1αi N (µi , σ2
i )
On va estimer les parametres :
- αi qui correspond au poids de la la gaussienne i.
- µi qui correspond a la moyenne de la gaussienne i.- σ2
i qui correspond a l’ecart type au carre de la gaussienne i.On utilise la methode du maximum de vraissemblance :
On pose : P (x, θj) = N (µi , σ2i )
et pour chaque iteration k = 1..3 on calcule
P k(j, xi) =αk
j P (xi,θkj )
3P
l=1
αklP (xi,θ
kl)
avec θkj = (µi , (σk
i )2)
αk+1i = 1
nP k(j, xi) avec j = 1..3 et n = card(N)
µk+1i =
nP
i=1
xiPk(j,xi)
nP
i=1
P k(j,xi)avec j = 1..3 et n = card(N)
(σk+1i )2 =
nP
i=1
(xi−µk+1
i )2P k(j,xi)
nP
i=1
P k(j,xi)avec j = 1..3 et n = card(N)
ϕk+1 = (αk+1i , µk+1
j , (σk+1i )2)
On s’arrete quand∥
∥ϕk+1 − ϕk∥
∥ ≤ ǫ
On propose un algorithme sous MATLAB pour estimer les differentsparametres :
[a,mu,sigma]= demelange(a0,mu0,sig0,N)
Avec N le vecteur image, a0,mu0,sig0 les parametres de depart, leurvaleur n’a pas reellement d’importance, mais la limitation de la machinefait qu’on se doit de les choisir.
12
Dans ce cas on pose :
- a0=[0.45,0.25,0.3]- mu0=[104,132,172]- sig0=[8,9,6]
Exemple d’utilisation
On teste l’algorithme sur une image :
13
Maintenant que l’on a les trois gaussiennes :
0.4761 ∗ N (131.4743, 46.1035)0.3662 ∗ N (103.6867, 18.9493)0.1577 ∗ N (172.1166, 13.2387)
On peut desormais comparer le graphe des gaussiennes avec l’histogramme :
0 50 100 150 200 250 3000
500
1000
1500
2000
2500
0 50 100 150 200 250 3000
0.002
0.004
0.006
0.008
0.01
0.012
14
On remarque que les deux graphes sont similaires. on peut ainsi testerl’algorithme de demelange sur l’ensemble des images pour savoir s’il estrobuste et surtout si l’ensemble des histogrammes des images suit unmelange de gaussiennes.
Pour cela, on va le tester sur 10 lots de 15 images contigues et en faire lamoyenne (en tout 150 images), puis sur la concatenation de ses memes lotsd’images. on propose donc la fonction suivante :
[amoy,mumoy,sigmamoy,a,mu,sigma]=compare2
Ou amoy, mumoy, sigmamoy sont les moyennes des parametres α, µ etσ, et a, mu, sigma sont les memes parametres des concatenations desimages.
15
Les moyennes des parametres sont proches, voir les memes que lesparametres des concatenations des images.On va le mettre en evidence en faisant la moyenne des ecarts de chaqueparametre des gaussiennes :
ecarta = -0.0974 0.0628 0.0346
ecartmu = 0.2237 1.6306 -1.0458
ecartsigma = 1.5585 2.1616 1.8364
Pour les 3 gaussiennes on voit bien que si l’on concatene les images ou sil’on fait la moyenne, on obtient quasiment les memes parametres.L’algorithme de demelange est bien robuste. On peut ainsi faire uneclassification en trois dimensions des images de tuffeaux.
Pour verifier si l’algorithme de demelange est robuste pour les 150images, il faut environ 2h (sur un pc portable de puissance moyenne). Enimaginant que l’on manque de temps ou plus que 150 images, on aurait putirer au hasard (par exemple suivant une loi uniforme) un nombre d’imagedefinie. Par exemple 60 images pour un lot total de 300 images. Mais il nefaut pas oublier que le but de cette etude est de pouvoir recreer en 3 D lereseau poreaux. Il faut donc que les images soient contigues. On peut tireralors une image au hasard puis de tester un nombre d’image donne paravance (au choix de l’utilisateur).
16
On propose la fonctions suivant :[amoy,mumoy,sigmamoy,a,mu,sigma]=comparehasard
Ou amoy, mumoy, sigmamoy sont les moyennes des parametres α, µ etσ, et a, mu, sigma sont les memes parametres des concatenations desimages. Exemple d’utilisation
On le teste sur 30 images
On obtient les memes resultats que precedement. C’est suffisant pour
17
verifier la robustesse de l’algorithme de demelange tant que le nombre d’imagea tester est suffisament grand.
Depuis le debut on a suppose que l’histogramme des images suivait unmelange de gaussiennes. Maintenant que l’on a determine les parametres,montrons que les histogrammes suivent bien les 3 gaussiennes en utilisantun test statistique.
2.3 Test de Kolmogorov-Smirnov
Le but est de calculer, pour un lot d’image tire au hasard, la distancemaximale entre les 3 gaussiennes avec les parametres estimes et sonhistogramme.
On compare cette distance avec une certaine valeur, que l’on calcule,alors on peut accepter ou non que l’echantillon (l’histogramme) est issud’un melange gaussien.
1) On tire une image au hasard parmi 1502) On calcule la distance maximale Dsk3) On determine la valeur critique Dn suivant le seuil α = 5%4) Si Dsk < Dn , on peut accepter que l’echantillon est un melange
gaussien.
Pour cela on va utiliser la fonction suivant :[I]=gaussiennehasard
Ou I est le vecteur qui garde en memoire les differentes images testees.
Exemple d’utilisation
18
Pour gagner du temps on fait le test sur 30 images tirees au hasardsuivant une loi uniforme sur un paquet de 150 images contigues.
19
Au seuil α = 5% on peut accepter l’hypothese Ho : Les images sontissues d’un melange gaussien.
2.4 Automatisation
Pour finir, on a fait un script qui utilise toutes les fonctions precedents.il suffit de lancer :
automatisme
L’utilisateur suit les instructions pour obtenir les parametres des imageset la verification des resultats.
20
Exemple d’utilisation
21
3 Conclusion
Ce stage est une petite pierre a l’edifice du projet de recherche :”Alteration des pierres du patrimoine bati”. Ce travail sera utilise pourfaire une segmentation en region des pierres. Une fois cette etape effectuee,on pourra quantifier le milieu a l’aide de differents estimateurs : porosite,surface specifique etc. Ces outils permettront de comparerquantitativement une zone alteree d’une zone intacte (ou provenantdirectement d’une carriere) et ainsi de caracteriser l’evolution du reseauporeux causee par l’alteration.
Pour realiser ce stage, j’ai eu l’opportunite de travailler sous MATLAB.Cette experience enrichissante m’a donne gout a ce type de logiciel et sesdifferents domaines d’utilisation.
Enfin, ce stage m’a offert la possibilite de decouvrir une autre dicipline queles mathematiques et la passion qui peut en decouler.
22
4 References
[1] J-T. LAPRESTE. Introduction a MATLAB. ED. ellipses.
[2] J-T. LAPRESTE. aide-memoire MATLAB. ED. ellipses.
[3] M. Rautureau. Tendre comme la pierre. ED. Region Centre.
[3] Wikipedia. Algorithme esperance-maximisation.http://fr.wikipedia.org/wiki/Expectation-Maximization.
23
5 Annexes
Programmation
autocontraste
function autocontraste(nom,type)
code=zeros(1,150);
for i=0:149
if i<10
M=imread([nom,’00’,int2str(i),’.’,type]);
elseif i>9 & i<100
M=imread([nom,’0’,int2str(i),’.’,type]);
else
M=imread([nom,int2str(i),’.’,type]);
end
code(i+1)=M(1,1);
end
moy=sum(code)/150
cont=find(code==int8(moy));
test=0;
if max(size(cont))~=max(size(code))
test=1;
cont=find(code~=int8(moy));
texte=[’Il y a ’,int2str(max(size(cont))),’ image(s) mal contrastees’];
disp(texte);
for j=1:max(size(cont))
i=cont(j)-1
if i<10
M=imread([nom,’00’,int2str(i),’.’,type]);
elseif i>9 & i<100
M=imread([nom,’0’,int2str(i),’.’,type]);
else
M=imread([nom,int2str(i),’.’,type]);
end
diff=double(int8(moy)-int8(M(1,1)))
M(:,:)=M(:,:)+diff;
p=find(M<0);
M(p)=0;
24
g=find(M>255);
M(g)=255;
if i<10
image=[nom,’00’,int2str(i),’.’,type];
elseif i>9 & i<100
image=[nom,’0’,int2str(i),’.’,type];
else
image=[nom,int2str(i),’.’,type];
end
imwrite(M,image,type);
end
end
if test==0
[’Les images sont bien contrastees’]
end
25
histogramme3
function [H,N]=histogramme3(M,cadre)
H=zeros(256,1);
nblig=size(M,1);
nbcol=size(M,2);
N=zeros(1,204774);
l=0;
for u=1:nblig
stop=0;
i=1;
while(i<=nbcol & M(u,i)==cadre)
i=i+1;
end;
if i<nbcol
k=i;
while (k<=nbcol & stop==0)
j=k;
if M(u,k)==cadre
while (j<nbcol & M(u,j)==cadre)
j=j+1;
end;
if j<nbcol
l=l+1;
if l>max(size(N));
N=[N M(u,k)];
else
N(l)=M(u,k);
end;
H(M(u,k)+1)=H(M(u,k)+1)+1;
else
stop=1;
end;
else
l=l+1;
if l>max(size(N))
N=[N M(u,k)];
26
else
N(l)=M(u,k);
end;
H(M(u,k)+1)=H(M(u,k)+1)+1;
end;
k=k+1;
end;
end;
end;
if l<max(size(N))
N=N(1:l);
end;
H=H’;
bar(H);
N=double(N);
27
demelange
function [a,mu,sigma]= demelange(a0,mu0,sig0,N)
n=size(N,2);
k=3;
it=0;
itmax=300;
tol=1/100;
erreur=1;
Proba=zeros(k,n);
a=a0;
mu=mu0;
sigma=sig0;
while (it < itmax)&( erreur > tol)
sp=0;
for j=1:k
Proba(j,:)= a0(j)*normpdf(N,mu0(j),sig0(j) );
sp=sp+Proba(j,:);
end;
for j=1:k
Proba(j,:)=Proba(j,:)./sp;
S=sum(Proba(j,:));
a(j)=S/n ;
mu(j)=sum(N.*Proba(j,:))/S ;
sigma(j)=sum((N-mu(j)).^2.*Proba(j,:))/S;
sigma(j)=sqrt(sigma(j));
end;
e=[norm(mu -mu0) norm(sigma-sig0) norm(a-a0)];
erreur=norm(e);
a0=a;
mu0=mu;
sig0=sigma;
it=it+1;
end
y=0;
for j=1:k
y=y+a(j)*normpdf([0:255],mu(j),sigma(j) );
28
end;
clf();
plot([0:255],y)
a
mu
sigma
29
compare2
function [amoy,mumoy,sigmamoy,a,mu,sigma]=compare2
amoy=[];
a=[];
mumoy=[];
mu=[];
sigmamoy=[];
sigma=[];
depart=0;
arrive=14;
for j=1:10
j
aD =[0.45,0.25,0.3];
muD=[104,130,172];
sigmaD=[8,9,6];
tempa=[];
tempmu=[];
tempsigma=[];
Ntemp=[];
it=0;
a0=aD;
mu0=muD;
sigma0=sigmaD;
for i=depart:arrive
it=it+1;
if i<10
M=imread([’ndrp_00’,int2str(i),’.png’]);
elseif i>9 & i<100
M=imread([’ndrp_0’,int2str(i),’.png’]);
else
M=imread([’ndrp_’,int2str(i),’.png’]);
end
[H,N]=histogramme3(M,M(1,1));
[a0,mu0,sigma0]= demelange(a0,mu0,sigma0,N);
tempa=[tempa;a0];
tempmu=[tempmu;mu0];
30
tempsigma=[tempsigma;sigma0];
Ntemp=[Ntemp,N];
end
aa=[sum(tempa(:,1)),sum(tempa(:,2)),sum(tempa(:,3))]/15
amu=[sum(tempmu(:,1)),sum(tempmu(:,2)),sum(tempmu(:,3))]/15
asigma=[sum(tempsigma(:,1)),sum(tempsigma(:,2)),sum(tempsigma(:,3))]/15
amoy=[amoy;aa];
mumoy=[mumoy;amu];
sigmamoy=[sigmamoy;asigma];
[ademel,mudemel,sigmademel]= demelange(aD,muD,sigmaD,Ntemp)
a=[a;ademel];
mu=[mu;mudemel];
sigma=[sigma;sigmademel];
depart=arrive+1;
arrive=arrive+15;
end;
erreura=a-amoy
erreurmu=mu-mumoy
erreursigma=sigma-sigmamoy
31
comparehasard
function [a,mu,sigma,amoy,mumoy,sigmamoy]=comparehasard
image=input(’Nombre d"image a tester : ’);
aD =[0.45,0.25,0.3];
muD=[104,130,172];
sigmaD=[8,9,6];
tempa=[];
tempmu=[];
tempsigma=[];
it=0;
tempN=[];
i=int8(rand*(149-image));
for j=i:(i+image-1)
j
if i<10
M=imread([’ndrp_00’,int2str(j),’.png’]);
elseif i>9 & i<100
M=imread([’ndrp_0’,int2str(j),’.png’]);
else
M=imread([’ndrp_’,int2str(j),’.png’]);
end
[H,N]=histogramme3(M,M(1,1));
[a0,mu0,sigma0]= demelange(aD,muD,sigmaD,N);
tempa=[tempa;a0];
tempmu=[tempmu;mu0];
tempsigma=[tempsigma;sigma0];
tempN=[tempN,N];
end
amoy=[sum(tempa(:,1)),sum(tempa(:,2)),sum(tempa(:,3))]/image;
mumoy=[sum(tempmu(:,1)),sum(tempmu(:,2)),sum(tempmu(:,3))]/image;
sigmamoy=[sum(tempsigma(:,1)),sum(tempsigma(:,2)),sum(tempsigma(:,3))]/image;
[a,mu,sigma]= demelange(aD,muD,sigmaD,tempN);
32
gaussiennehasard
function [I]=gaussiennehasard
compte=0;
I=[];
it=0;
image=input(’Nombre d"image a tester : ’);
alpha= 0.05;
for j=1:image
toto=0;
i=int8(rand*149);
if j>1
while toto==0
toto=1;
i=int8(rand*149);
for k=1:max(size(I))
if I(k)==i
toto=0*toto;
end;
end;
end;
end;
I=[I,i];
numimage=I(j)
it=it+1;
if i<10
M=imread([’ndrp_00’,int2str(i),’.png’]);
elseif i>9 & i<100
M=imread([’ndrp_0’,int2str(i),’.png’]);
else
M=imread([’ndrp_’,int2str(i),’.png’]);
end
[H,N]=histogramme3(M,M(1,1));
a0 =[0.45,0.25,0.3];
mu0=[104,134,174];
sigma0=[8,9,6];
[a,mu,sigma]= demelange(a0,mu0,sigma0,N);
33
[Dn,Dsk]=Smirnov_Kolmogorov(a,mu,sigma,alpha,H,N)
if Dsk<=Dn
compte=compte+1;
end;
end;
if compte==image
disp(’Pour toutes les images on obtient un melange de 3 gaussiennes’);
else
erreur=image-compte;
if erreur>1
texte=[’Il y a ’,int2str(erreur),’ images qui ne sont pas un melange gaussien’];
else
texte=[’Il y a une image qui n"est pas un melange gaussien’];
end;
disp(texte);
end;
34
automatisme
function automatisme
disp(’1 . Placez les images dans le meme dossier que la fonction ’);
pause
type=input(’2 . Donnez le type d"image (entre apostrophes) : ’);
nom=input(’3 . Donnez le nom commun a images (entre apostrophes) : ’);
autocontraste(nom,type)
[amoy,mumoy,sigmamoy,a,mu,sigma]=autocompare(nom,type)
[I]=gaussiennehasard
35
