Segmentation morphologique guidée par des exemplesSegmentation morphologique guid ee par des...

Segmentation morphologiqueguidee par des exemples

Sebastien Lefevre Sebastien Derivaux

Laboratoire des Sciences de l’Image, de l’Informatique et de la TeledetectionLSIIT - UMR 7005 - CNRS / Universite Louis Pasteur, Strasbourg

lefevre,derivaux@lsiit.u-strasbg.fr

GDR-ISIS, GT SCATI27 mars 2008

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Question :comment resoudre un probleme d’analyse d’image entenant compte des connaissances disponibles des lespremiers traitements a realiser ?

En guise de reponse . . . quelques contributions ou :

traitement = segmentation morphologique+

connaissances = zones exemples etiquetees

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 2

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Outline

1 Segmentation morphologique

2 Connaissances fournies par les exemples

3 Segmentation guidee

4 Resultats

5 Conclusion

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 3

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Outline

1 Segmentation morphologique

2 Connaissances fournies par les exemples

3 Segmentation guidee

4 Resultats

5 Conclusion

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 4

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Outline

1 Segmentation morphologique

2 Connaissances fournies par les exemples

3 Segmentation guidee

4 Resultats

5 Conclusion

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 5

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Outline

1 Segmentation morphologique

2 Connaissances fournies par les exemples

3 Segmentation guidee

4 Resultats

5 Conclusion

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 6

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Outline

1 Segmentation morphologique

2 Connaissances fournies par les exemples

3 Segmentation guidee

4 Resultats

5 Conclusion

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 7

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Morphologie mathematique et segmentation

Morphologie mathematique (MM)

Introduite dans les annees 1960 par Matheron et Serra.Permet l’analyse des structures spatiales dans les images.Approche non-lineaire basee sur la theorie des treillis.Fournit un ensemble d’operateurs pour filtrer les images.

Segmentation morphologique

Differentes methodes de segmentation sont issues de la MM :

ligne de partage des eaux

nivellements

profils morphologiques differentiels

filtres alternes sequentiels

. . .

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 8

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Morphologie mathematique et segmentation

Morphologie mathematique (MM)

Introduite dans les annees 1960 par Matheron et Serra.Permet l’analyse des structures spatiales dans les images.Approche non-lineaire basee sur la theorie des treillis.Fournit un ensemble d’operateurs pour filtrer les images.

Segmentation morphologique

Differentes methodes de segmentation sont issues de la MM :

ligne de partage des eaux

nivellements

profils morphologiques differentiels

filtres alternes sequentiels

. . .

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 9

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Ligne de partage des eaux (LPE)

Principe general de l’approche par immersion

l’image a segmenter est consideree comme un relief

ce relief est innonde a partir de ses minima locaux (=bassins)

si les eaux de 2 bassins se rejoignent, on construit une digue

lorsque le relief est totalement innonde, les digues sont les LPE

Quelques commentaires

l’algorithme est souvent applique sur un gradient de l’image

la methode tend a sursegmenter l’image, deux solutions :

utiliser des marqueurs (bassins initiaux), limitant ainsi lenombre de regions creeesintegrer des techniques de reduction de sursegmentation

comment guider cet algorithme par des connaissances ?

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 10

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Ligne de partage des eaux (LPE)

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 11

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Connaissances et segmentation

Comment l’expert peut-il guider la segmentation ?

selection d’un algorithme

reglage des parametres

choix d’un pre/post-traitement

mais ces taches sont tres souvent delicates . . .

Un autre type de connaissance

L’expert peut egalement identifier des zones de l’imageauxquelles il est capable d’associer une semantique.

Ces zones forment un ensemble d’apprentissage exploitable parune approche de type classification supervisee.

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 12

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Connaissances exemples

Quelles connaissances dans les exemples ?

Des informations de differentes natures sont donnees parl’ensemble d’apprentissage :

spatiale

spectrale

texturale

. . .

Cet ensemble peut etre utilise dans un processus de classificationsupervisee dure ou floue.

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 13

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Connaissances exemples

Vers un nouvel espace de representation

En appliquant une classification supervisee floue, on obtient :

pour chaque pixel, une valeur d’appartenance a chaque classe

aux valeurs spectrales / couleurs s’ajoutent les appartenances

Exemple avec les classes : bati, route, vegetation

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 14

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Connaissances exemples

Vers un nouvel espace de representation

En appliquant une classification supervisee floue, on obtient :

pour chaque pixel, une valeur d’appartenance a chaque classe

aux valeurs spectrales / couleurs s’ajoutent les appartenances

Exemple avec les classes : bati, route, vegetation

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 15

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Connaissances exemples

Vers un nouvel espace de representation

En appliquant une classification supervisee floue, on obtient :

pour chaque pixel, une valeur d’appartenance a chaque classe

aux valeurs spectrales / couleurs s’ajoutent les appartenances

Exemple avec les classes : bati, route, vegetation

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 16

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Segmentation guidee par les exemples

Comment exploiter les appartenances ?

Plusieurs solutions :

avant : modifier l’image a segmenter

pendant : redefinir le comportement de l’algorithme

apres : optimiser les parametres de segmentation

Notations

f est l’image a segmenter, p un pixelwi (p) est l’appartenance de p a la classe Ci

Mi (p) est l’ensemble d’apprentissage pour la classe Ci

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 17

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

1. Modification de l’image a segmenter

Synopsis

Changement d’espace depuis f vers w

Construction du relief par calcul du gradient sur w

Application de la LPE

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 18

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

2. Redefinition du comportement de l’algorithme

Motivations

f (p) est faible → p n’est pas une LPE

f (p) est eleve mais ∃i : wi (p) est eleve→ p ne devrait pas etre une LPE

sinon → p est et doit etre une LPE

=⇒ on definit fi = (1− wi ) · f

Synopsis

Utilisation des zones d’exemples M comme des marqueurs

Creation d’un relief par classe, fi = (1− wi ) · fChaque bassin Mi s’etend selon le relief fi

p est affecte au marqueur Mi qui l’atteint en premier

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 19

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

2. Redefinition du comportement de l’algorithme

Illustration

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 20

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

2. Redefinition du comportement de l’algorithme

Illustration

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 21

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

2. Redefinition du comportement de l’algorithme

Illustration

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 22

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

2. Redefinition du comportement de l’algorithme

Illustration

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 23

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

3. Optimisation des parametres de segmentation

Reduction de sursegmentation

Seuillage des minim locaux inferieurs a hmin

Non immersion des bassins a faible profondeur inferieure a d

Fusion de regions connexes a valeurs moyennes proches

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 24

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

3. Optimisation des parametres de segmentation

Selection des parametres optimaux par algorithme genetique

individu = jeu de parametres normalises

fonction d’evaluation= precision d’une classification supervisee des regions

zones exemples exploitees en validation croisee

a chaque iteration, calcul de n segmentations !

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 25

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Experimentations sur la base Berkeley

LPE supervisee avec marqueurs vs. LPE classique avec marqueurs

marqueurs LPE classique LPE amelioree

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 26

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Influence du nombre de marqueurs

2 marqueurs

marqueurs et classification

LPE normale et amelioree

3 marqueurs

marqueurs et classification

LPE normale et amelioree

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 27

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Segmentation sans marqueur

Zones d’apprentissage

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 28

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Segmentation sans marqueur

Resultats

LPE Optimisationclassique genetique

Changement Changement d’espaced’espace et optimisation

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 29

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Segmentation avec marqueurs

LPE classique avec marqueurs LPE amelioree

avec un marqueur par batiment(une seule classe)

et un seul marqueur(en bas a droite)

pour le fond

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 30

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Segmentation avec marqueurs

Image initiale Resultat obtenu

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 31

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Conclusions et Perspectives

Problematique

Guider la segmentation morphologique . . .. . . par des zones exemples etiquetees par l’utilisateur

Contributions

3 approches pour integrer cette connaissance a la LPE :

en tant que pre-traitement (segmentation dans l’espace desappartenances)

via une modification interne de l’algorithme (LPE avecmarqueurs)

par une encapsulation de l’algorithme dans un cadred’optimisation supervisee

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 32

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Conclusions et Perspectives

Problematique

Guider la segmentation morphologique . . .. . . par des zones exemples etiquetees par l’utilisateur

Contributions

3 approches pour integrer cette connaissance a la LPE :

en tant que pre-traitement (segmentation dans l’espace desappartenances)

via une modification interne de l’algorithme (LPE avecmarqueurs)

par une encapsulation de l’algorithme dans un cadred’optimisation supervisee

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 33

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Conclusions et Perspectives

Perspectives

Combiner ces differentes approches

Utiliser non pas des zones exemples mais des resultatsexemples

Calculer d’autres informations a partir des exemples

Merci pour votre attention . . .

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 34

Introduction Connaissances exemples Segmentation guidee Resultats Conclusion

Quelques references disponibles surhttp://dpt-info.u-strasbg.fr/~lefevre

LPE dans l’espace des appartenances

Derivaux et al (2006) Watershed Segmentation of Remotely Sensed ImagesBased on a Supervised Fuzzy Pixel Classification, IEEE IGARSS

Derivaux et al (2007) Segmentation par ligne de partage des eaux basee sur desconnaissances texturales, Colloque GRETSI

Optimisation genetique des parametres de la LPE

Derivaux et al (2007) Parametrisation de methodes de segmentation parutilisation de connaissances et approche genetique, Atelier ECOI

Derivaux et al (2007) On machine learning in watershed segmentation, IEEEMLSP

LPE amelioree avec marqueurs

Lefevre (2007), Knowledge from markers in watershed segmentation, IAPR CAIP

Sebastien Lefevre, Sebastien Derivaux LSIIT, ULP-CNRS

Segmentation morphologique guidee par des exemples 35