SEGMENTATION
PAR FUSION SELON
UN TEST STATISTIQUE
Projet de Méthodes
de Base en Analyse d'Image
par
François
Leroy et Thomas
Devichi
PLAN
Introduction
I
) Principe de la segmentation par fusion
II
) Principe des tests statistiques
1
) Qu'est-ce qu'un test statistique ?
2
) Description des différents test statistiques envisagés
III
) Algorithme
1
) Synoptique
2
) Commentaires
IV
) Résultats et interprétations
1
) Présentation de la base d'images de test
2
) Les images de synthèse
3
) Image Cellule
4
) Image Zone
Conclusions
Programmes
Sources
Bibliographie
Introduction
La segmentation par fusion s'inscrit dans les méthodes
de réunion de régions ( region merging ). Ces méthodes
tendent à améliorer la segmentation d'une image, en regroupant
les régions entre elles suivant un prédicat.
Dans notre étude, notre prédicat consiste en
un test statistique. Nous avons choisi de comparer certains de ces tests,
au vu de la qualité de la segmentation finale.
Ces dernières années, la segmentation par fusion
selon un test statistique a fait l'objet de recherches [1]
et d'applications [2].
I
) Principe de la segmentation par fusion
Cette méthode
vise à améliorer la segmentation d'une image. Elle procède
en regroupant les régions d'une image initialement sur-segmentée
suivant un prédicat fixé.
Nous partons donc d'une
image segmentée en très petites régions, de quelques
dizaines de pixels en moyenne.
La segmentation initiale
est représentée par un graphe d'adjacence de régions.
Chaque sommet du graphe représente une région, les arêtes
relient les régions voisines dans l'image.
Une fois ce graphe d'adjacence
construit, chaque paire de sommets adjacents est soumis au prédicat
de fusion. Lorsque le prédicat est vérifié, les deux
sommets sont remplacés par un seul et les régions correspondantes
fusionnent. Sinon les sommets et les régions sont laissés
tels quels.
Dans notre étude,
le prédicat est un test statistique.
II
) Principe des tests statistiques
1
) Qu'est-ce qu'un test statistique ?
L'ouvrage de Saporta
[3] donne la définition suivante :
" Un test statistique
est un mécanisme qui permet de trancher entre deux hypothèses
au vu des résultats d'un échantillon. "
La famille de tests statistiques
qui nous intéressent ici, traite de la comparaison de deux échantillons.
Chacun des échantillons est considéré comme la réalisation
d'une variable aléatoire. La comparaison porte sur certaines propriétés
de ces variables ( fonction de répartition, espérances, variances
). Elle se traduit par la formulation d'une hypothèse dépendante
du test envisagé : égalité des variances et des espérances
pour Fisher-Snedecor, égalité des espérances pour
Student, identité des populations pour le Chi2 et Wilcoxon.
Afin de valider l'hypothèse,
notée H0, chaque test introduit une variable aléatoire
X de décision : variable de Student, variable de Fisher ... L'hypothèse
H0 est vérifiée si cette variable de décision
prend une valeur dans un intervalle de confiance [-k;+k]. Les bornes de
l'intervalle sont fixées par l'utilisateur du test, a l'aide du
seuil d'erreur alpha . La relation liant k et alpha s'écrit :
En pratique, les valeurs
de k sont tabulées en fonction de alpha et du nombre de pixels de
chaque région.
Si cette probabilité
est supérieure à alpha , l'hypothèse H0
est vérifiée.
2
) Description des différents tests statistiques envisagés
Dans notre cas, les
échantillons sont les régions de l'image. Celles-ci fusionnent
lorsque l'hypothèse H0 du test statistique est vérifiée.
Les deux régions ont respectivement :
- des espérances
m1 et m2 et des variances s12
et s22.
- des moyennes empiriques
M1 et M2 et des variances empiriques S12
et S22.
- des populations n1
et n2 pixels.
- des fonctions de répartition
F1 et F2.
Pour les deux premiers
tests, nous supposons que les deux régions suivent des lois normales.
Par la suite, nous proposons
des tests plus généraux, où il n'y a pas de supposition
à faire sur la distribution des régions.
L'hypothèse
H0 est la suivante :
La variable de Fisher,
à ( n1-1 ; n2-1 ) degrés de liberté,
est donnée par l'équation :
Deux régions
de tailles n1 et n2 pixels, indépendantes
l'une de l'autre sont supposées provenir d'une même population
à distribution normale. L'hypothèse H0, qui prétend
que s1 et s2 des deux populations ne diffèrent
l'une de l'autre que de manière non significative et ceci avec une
probabilité d'erreur alphaF , est acceptée si
la valeur de la variable de Fisher F( n1 - 1 ; n2 - 1 ) est
inférieure à la valeur k, borne supérieure de l'intervalle
de confiance :
Si le test de Fisher-Snedecor
est vérifié, c'est-à-dire si l'hypothèse H0
est validée, nous aboutissons à la conclusion s1
= s2. On passe alors au test de Student sur les espérances.
L'hypothèse
H0 est la suivante :
La variable de Student,
à ( n1 + n2 - 2 ) degrés
de liberté, est donnée par l'équation :
Deux régions
de tailles n1 et n2 pixels, indépendantes
l'une de l'autre sont supposées provenir d'une même population
à distribution normale. L'hypothèse H0, qui prétend
que s1 et s2 des deux populations ne diffèrent
l'une de l'autre que de manière non significative et ceci avec une
probabilité d'erreur alphat, est acceptée si la
valeur de la variable de Student T( n1 + n2 - 2 ) est inférieure
à la valeur k, borne supérieure de l'intervalle de confiance
:
Les hypothèses
sont les mêmes que précédemment. Seulement, le test
de Fisher n'est plus valable. Cependant, lorsque la taille des régions
1 et 2 est assez grande ( typiquement quelques dizaines d'observations
), nous pouvons tester les moyennes m1 et m2 grâce
à la formule de Student, que s1 et s2 soient
différents ou non.
On peut alors dire que
le test de Student est "robuste", c'est-à-dire qu'il résiste
aux changements de loi des régions considérées.
Soient (x1,
x2, x3, …, xn1) et (y1, y2,
…, yn2) les niveaux de gris des pixels des régions 1
et 2. L'idée du test est d'ordonner les pixels par valeurs croissantes
de niveaux de gris et de fusionner si on obtient un mélange homogène
de pixels.
Les pixels de chaque région
sont ordonnés suivant leurs niveaux de gris ; Puis, pour chaque
pixel de la région 1, on compte le nombre de pixels de la région
2 dont le niveau de gris lui est inférieur. Ces nombres sont additionnés
pour donner la somme U.
La variable U varie de
0 à n1 * n2, et a une distribution gaussienne
asymptotiquement, de moyenne E(U) = n1 * n2 / 2 et
de variance V(U) = n1 * n2 * ( n1 + n2
+ 1 ) / 12.
Pratiquement, U est considérée
gaussienne dès que n1 et n2 sont supérieurs
à 8.
L'hypothèse H0
est la suivante :
L'hypothèse
H0, qui prétend que les deux populations suivent des
lois identiques, est acceptée si la valeur prise par la variable
U centrée réduite est dans l'intervalle de confiance [-k
+k], soit :
Soient (x1,
x2, x3, …, xn1) et (y1, y2,
…, yn2) les niveaux de gris des pixels des régions 1
et 2.
L'hypothèse H0
est la suivante :
La variable de décision
est la variable d2 suivante :
Elle suit une loi du
Chi2 à r degrés de liberté, où r est le nombre
de niveaux de gris pris réellement par un pixel d'une des deux régions.
L'hypothèse H0
selon laquelle les observations { xi }et { yi }appartiennent
à la même distribution normale avec une probabilité
d'erreur alphad², est acceptée si la valeur d2
est inférieure à k, borne supérieure de l'intervalle
de confiance :
III
) Algorithme
1
) Synoptique
Notons que le temps de calcul est fonction de la sur-segmentation
initiale. Pour nos images, il varie entre quelques dizaines de secondes
( Image de Synthèse ) à quelques minutes( Image Zone).
2
) Commentaires
a ) Sur-segmentation
La sur-segmentation
a été obtenue à l'aide d'outils de morphologie mathématique.
L'image est prétraitée par un Filtre Alterné Séquentiel
et par une reconstruction dynamique. Ce prétraitement permet de
contrôler la quantité de variations locales d'intensité
dans l'image, ainsi que de régler le nombre de régions en
fin de segmentation.
Enfin, une Ligne de Partage
des Eaux est appliquée sur le gradient de l'image prétraitée.
L'image devient segmentée en petites régions, de faibles
dynamiques. Chaque région se voit alors attribuer une étiquette
différente.
b ) Initialisation
du Graphe d'adjacence
Chaque région
de l'image est associée à un sommet du graphe. Les attributs
du sommet sont alors ceux de la région, à savoir son nombre
de pixels, sa moyenne, sa variance ou ses populations par niveau de gris.
Une matrice d'adjacence
représente les arêtes du graphe. De plus, une matrice d'équivalence
est initialisée afin de prendre en compte les futures équivalences
entre régions. Deux régions sont équivalentes si elles
ont fusionné.
c ) Balayage
du Graphe d'adjacence
Le balayage du graphe
s'effectue par étiquettes croissantes, c'est-à-dire par un
balayage du coin haut gauche au coin bas droit de l'image.
d ) Test statistique
Pour chaque paire de
sommets voisins ( Si, Sj ), nous appliquons le test
statistique envisagé. Celui-ci dépend de plusieurs paramètres
:
- Dans le cas de Fisher-Snedecor
et Student, respectivement des probabilités d'erreur alphaF
et alphat, ainsi que de la taille minimale des régions
pour sa mise en oeuvre. Nous rappelons que le test de Fisher-Snedecor s'appuie
pour une part sur celui de Student : il est possible d'effectuer uniquement
le test de Student en fixant alphaF à zéro.
- Dans le cas de Wilcoxon,
de la probabilité d'erreur alphau, ainsi que de la taille
minimale des régions pour sa mise en oeuvre.
- Dans le cas du Chi2,
de la probabilité d'erreur alphad².
Ceci se traduit par la validation ou non de l'hypothèse H0.
Le sommet d'étiquette
la plus basse récupère les attributs de l'autre sommet :
le nombre de pixels, la moyenne, la variance ou la population par niveau
de gris sont recalculées.
Les matrices d'adjacence
et d'équivalence sont mises à jour.
Si au cours d'un balayage,
aucune fusion n'a eu lieu, le programme prend fin.
g ) Image Finale
Nous pouvons alors
évaluer la qualité de l'image finale au vu des paramètres
du test statistique envisagé.
IV
) Résultats et interprétations
1
) Présentation de la base d'images de test
|
Image
|
Descriptif
|
Taille
|
Nature
|
Loi
|
|
Syn2s
|
Trame
de carrés 20 x 20. Il y a un dégradé de 5 niveaux
de gris entre 2 carrés consécutifs. Ajout
d'un bruit gaussien centré d'écart-type 2.
|
128 x 128
|
Synthèse
|
Normale
|
|
Syn8s
|
idem
mais avec un bruit gaussien centré d'écart-type 8.
|
128 x 128
|
Synthèse
|
Normale
|
|
Cellule
|
image
de petites cellules sombres sur fond clair.
|
128 x 128
|
Médicale
|
|
|
Zone
|
image
radar, traitée dès le départ en log, de champs
agricoles et routes.
|
340 x 380
|
SAR
|
Gamma
|
2
) Les images de synthèse
Le test de Fisher-Snedecor
n'est pas mis en oeuvre car la variance est constante à travers
l'image : alphaF = 0.
Les régions
sont des échantillons suivant une loi normale. Nous n'avons donc
pas de contrainte sur la taille minimale des régions.
|
Image
|
Nb de régions initiales
|
Nb de fusions attendues
|
alphat
|
Nb de fusions
|
Résultats
|
Image Finale
|
|
Syn2s
|
389
|
340
|
0.05
|
268
|
le maillage
carré est apparent, mais il reste un bon nombre de carrés
sur-segmentés.
|
image
|
|
|
|
|
0.01
|
322
|
Très
nette amélioration de la segmentation en carrés.
|
image
|
|
|
|
|
0.001
|
336
|
la grille est
presque entièrement restituée.
|
image
|
|
Syn8s
|
774
|
725
|
0.05
|
663
|
Bonne segmentation
dans l'ensemble, mais il reste de nombreux carrés sur-segmentés.
|
image
|
|
|
|
|
0.01
|
722
|
Meilleure segmentation
: l'aspect tramé est respecté. La plupart des carrés
sont bien segmentés.
|
image
|
|
|
|
|
0.001
|
728
|
Nous dépassons
le nombre de fusions idéales. Des carrés voisins s'agglomèrent.
Il y a une perte importante du tramage.
|
image
|
La variable de Student
est vraiment décisive : le seuil alphat est discriminant
sur la qualité de la restitution visuelle de l'image.
Il faut noter aussi qu'un
seuil trop bas peut conduire à une dégradation progressive
de l'image.
Dans un premier temps,
nous avons été conformes à la théorie, qui
nous impose un nombre de pixels égal à 8 par région.
Puis, en pratique, nous
avons élargi le test à toutes les régions sans critère
de taille. En effet, sur les images testées, il nous a semblé
que le test restait efficace pour des régions de toutes tailles.
|
Image
|
Nb de régions initiales
|
Taille des petites régions
|
Nb de régions
exclues
|
Nb de régions attendues
|
alphau
|
Nombre de fusions
|
Résultats
|
Image finale
|
|
Syn2s
|
389
|
8
|
147
|
196
|
0.05
|
93
|
Le maillage
carré est apparent. Seulement certains carrés sont déformés.
|
|
|
|
|
|
|
196
|
0.01
|
106
|
Le nombre de
fusions augmentent peu. La déformation des carrés s'accroît.
|
|
|
|
|
0
|
0
|
340
|
0.05
|
166
|
Le maillage
carré est respecté. La segmentation est trop fine.
|
image
|
|
|
|
|
|
340
|
0.01
|
191
|
Amélioration
de la segmentation. Premières dégradations de l'image.
|
|
|
|
|
|
|
340
|
0.001
|
226
|
Le tramage
se détériore nettement.
|
image
|
Le test de Wilcoxon
apparaît mal adapté à nos images de synthèse.
Le test sur l'image Siens donne de plus mauvais résultat.
|
Image
|
Nb de régions initiales
|
Nb de régions attendues
|
alphad²
|
Résultats
|
Image Finale
|
|
Syn2s
|
389
|
340
|
0.05
|
Le tramage
est déjà dégradé. Les carrés voisins
s'agglomèrent.
|
|
|
|
|
|
0.01
|
Le tramage
se dégrade encore
|
image
|
Le test du Chi2 donne
de mauvais résultat sur les images de synthèse. Après
l'avoir testé sur les autres images, il s'est avéré
mal adapté à la segmentation par fusion. Ceci s'explique
peut-être parce que le test ne prend pas en compte la proximité
entre niveaux de gris. Par exemple, deux régions aux niveaux de
gris très proches, mais ne se recouvrant pas, n'ont aucune chance
de fusionner.
Par conséquent,
le test du Chi2 ne sera pas présenté par la suite.
3
) Image Cellule
Dans un premier temps,
nous avons été conformes à la théorie, qui
nous impose une taille minimale de quelques dizaines pixels.
En effet, les régions
ne suivent pas à priori une distribution normale. Par la suite,
le test s'est avéré efficace pour des régions de toutes
tailles.
Image
initiale Cellule sur-segmentée.
|
Nb de régions initiales
|
Taille des petites régions
|
Nb de petites régions
|
alphaF
|
alphat
|
Nb de fusions
|
Résultats
|
Image Finale
|
|
606
|
20
|
220
|
0.05
|
0.05
|
32
|
L'image
reste très segmentée. Les contours des cellules sont néanmoins
respectés. La variation de alphaF n'a que peu d'impact
sur la fusion. Nous posons alphaF = 0.
|
image
|
|
|
|
|
0.01
|
0.05
|
38
|
|
|
|
|
|
|
0.001
|
0.05
|
40
|
|
|
|
|
|
|
0.0001
|
0.05
|
48
|
|
|
|
|
|
|
0
|
0.05
|
67
|
|
|
|
|
|
|
0
|
0.01
|
88
|
La segmentation
s'améliore sans dégrader la qualité des contours des
cellules. Alphat a plus d'impact que alphaF dans
la fusion. Nous restons limité par le nombre de petites régions.
|
|
|
|
|
|
0
|
0.001
|
116
|
|
|
|
|
|
|
0
|
10-4
|
135
|
|
|
|
|
|
|
0
|
10-5
|
151
|
|
image
|
|
606
|
0
|
0
|
0
|
0.05
|
182
|
La segmentation
s'améliore à mesure que alphat diminue. C'est
en atteignant la valeur limite de précision pour alphat
que nous réalisons la meilleure segmentation : Les cellules sont
bien dessinées tandis que le fond est bien aggloméré.
|
|
|
|
|
|
0
|
0.01
|
220
|
|
|
|
|
|
|
0
|
0.001
|
280
|
|
|
|
|
|
|
0
|
10-4
|
317
|
|
|
|
|
|
|
0
|
10-5
|
341
|
|
|
|
|
|
|
0
|
limite de précision
|
502
|
|
image
|
Le test de Fisher-Snedecor
ne limite pas de manière significative la fusion. Ceci est sans
doute dû à la faible variance des régions dans l'image.
Nous avons été
étonnés par la faible agglomération des régions
composant le fond de l'image. Ces régions sont pourtant homogènes.
Le fort rejet de fusion s'explique par la très faible variance de
ces régions.
|
Nb de régions initiales
|
alphau
|
Nb de fusions
|
Résultats
|
Image Finale
|
|
606
|
0.05
|
183
|
La segmentation est équivalente à
celle de Student
|
|
|
|
0.01
|
226
|
|
image
|
|
|
0.001
|
318
|
Les contours des cellules commencent à
se dégrader. La segmentation commence à agglomérer
les cellules et le fond.
|
image
|
Le test de Wilcoxon
est mal approprié à cette image. Il atteint rapidement le
seuil de dégradation de la segmentation.
4
) Image Zone
Nous avons appliqué
les tests statistiques au log de l'image pour atténuer le speckle.
|
Nb régions initiales
|
alphat
|
Nb de fusions
|
Résultats
|
Image Finale
|
|
7226
|
10-4
|
6906
|
L'image est bien segmentée. Les champs
sont divisés en régions uniformes. Les contours des routes
sont détectés. En revanche, les tracés des champs
ne sont pas linéaires et les routes sont morcelées.
|
image
|
La méthode proposée par Cook, MacConnell
et Oliver, semble effectivement bien adaptée pour les images SAR.
La segmentation initiale est obtenue de façon systématique
en prenant des carrés de petite taille ( 2x2 ) dans l'image. Ensuite,
ils appliquent le test de Student de manière hiérarchisée
: ils fusionnent les régions suivant un ordre qui minimise la variable
de Student. Enfin, ils ajoutent un coût de fusion qui tient compte
de la forme des régions. Celui-ci est intégré afin
de corriger l'écart pris avec la théorie sur la taille minimale
des régions.
Comparativement à l'article, nous avons implémenté
une sur-segmentation moins fine, mais plus respectueuse des contours des
régions. En revanche, nous n'avons pas tenu compte de l'ordre de
fusion, qui, nous le savons, est primordial. Enfin, nous nous sommes aussi
affranchis du coût de fusion, afin de nous borner uniquement à
la statistique des régions.
Nos résultats nous sont apparus équivalents
aux leurs. Leur segmentation finale respecte la forme carrée des
champs, tandis que nous suivons mieux les courbures, notamment celles des
routes.
|
Nb régions initiales
|
alphau
|
Nb de fusions
|
Résultats
|
Image finale
|
|
7226
|
10-4
|
6441
|
La segmentation est mauvaise : les champs et les
routes sont agglomérés, les régions ne sont pas de
niveaux de gris homogènes.
|
image
|
Là encore, le test de Wilcoxon ne donne pas de
bons résultats. Nous notons que deux régions composées
de niveaux de gris disparates, mais enchevêtrés, conduit à
une fusion : une région plutôt claire peut s'agglomérer
à une région plutôt sombre, pourvu que leur zone d'enchevêtrement
soit suffisamment grande.
Conclusions
Les tests statistiques ont eu des efficacités différentes
sur nos images.
Le test du Chi2 a donné de piètres résultats
: il ne prend pas en compte la proximité entre niveaux de gris,
ce qui est très pénalisant pour la segmentation par fusion.
Le test de Wilcoxon s'est avéré mal adapté
aux images. Pour des segmentations assez grossières, ses performances
sont acceptables : les contours sont préservés. Mais, dès
lors que nous cherchons une segmentation plus fine, ses performances se
dégradent nettement : il y a bien souvent perte de certains contours.
Il est à noter que l'homogénéité au sens de
Wilcoxon ne signifie pas que les régions ont des moyennes proches.
Le test de Student est apparu comme le plus efficace. D'une
part, il est robuste vis-à-vis de la distribution des observations
de l'image initiale. D'autre part, la segmentation converge vers une image
stable à mesure que alpha diminue, à l'exception des images
très bruitées. Enfin, il semble applicable aux petites régions
en dépit des contraintes théoriques.
L'ajout du test de Fisher à celui de Student n'a pas
été significatif.
Les propriétés des tests statistiques ne
suivent pas forcément les critères de la perception visuelle
: la segmentation finale n'est pas toujours celle que nous attendions visuellement.
Le test statistique ne prend pas en compte l'information
spatiale. Notre segmentation par fusion gagnerait beaucoup par l'ajout
d'un traitement basé sur la position relative des pixels dans les
régions.
Nous ne nous sommes pas attardés à la sur-segmentation
de l'image. Cependant, nous sommes très conscients que l'image sur-segmentée
joue un rôle important. La finesse de la segmentation finale est
liée à celle de la segmentation initiale.
Nous avons arbitrairement choisi un sens de parcours de l'image.
Implicitement, il favorise certains fusions : un parcours inverse aboutit
à une segmentation différente. D'autres approches sont possibles
: une approche aléatoire, où les régions sont tirées
une à une; une approche déterministe qui fixe l'ordre de
fusion selon un coût minimal.
Le choix de la probabilité d'erreur alpha est difficile.
Nous l'avons souvent déterminé par des essais successifs.
En conclusion, la réussite de la segmentation par
fusion dépend de trois facteurs :
- La segmentation initiale.
- L'ordre de fusion des régions.
- Le choix de la probabilité d'erreur.
Bibliographie
retour au début de la
page ....