Organisation perceptuelle de structures curvilignes Laurent Alquier Directeur de thèse : Chabane...

Organisation perceptuelle de Organisation perceptuelle de structures curvilignesstructures curvilignes

Laurent AlquierLaurent Alquier

Directeur de thèse : Directeur de thèse :

Chabane Oussalah

Professeur

Responsable :Responsable :

Philippe Montesinos

Maître assistant

- UNIVERSITE MONTPELLIER II -- Thèse menée au Laboratoire de Génie Informatique et d ’Ingénierie de Production, Nîmes -

- 30 Septembre 1998 -

30 Septembre 1998Laurent ALQUIER -

Analyse d ’imagesAnalyse d ’images

ImageIntensité

ImageContours

Détection d ’indicesvisuels

Construction d ’unereprésentation symbolique

30 Septembre 1998Laurent ALQUIER -

Perception visuellePerception visuelle

Théories de la perception visuelleThéories de la perception visuelleFlot d ’informations visuelles importantFlot d ’informations visuelles importantNécessité de guider la perceptionNécessité de guider la perception

30 Septembre 1998Laurent ALQUIER -

Groupement perceptuelGroupement perceptuel

PrincipesPrincipes

Phénomène d ’organisation pré-attentive Phénomène d ’organisation pré-attentive  Propriétés globales émergentes : Propriétés globales émergentes : SaillanceSaillance S ’impose à la perception avant interprétationS ’impose à la perception avant interprétation Groupements élémentairesGroupements élémentaires

Principe de « bonne forme »Principe de « bonne forme » Simplicité, fermeture, familiarité : Simplicité, fermeture, familiarité : StabilitéStabilité

Propriétés intéressantesPropriétés intéressantes Généricité, robustesse - Organisation qualitative Généricité, robustesse - Organisation qualitative

Théorie Gestaltiste : Wertheimer, Koffka - 1923Théorie Gestaltiste : Wertheimer, Koffka - 1923

Références

30 Septembre 1998Laurent ALQUIER -

Plan de l’exposéPlan de l’exposé

Introduction.Introduction. Présentation globale.Présentation globale. Groupement par réseaux de saillance.Groupement par réseaux de saillance. Niveaux supérieurs de groupement.Niveaux supérieurs de groupement. ContributionsContributions et perspectives.et perspectives.

30 Septembre 1998Laurent ALQUIER -

ObjectifsObjectifs

Système complet d ’analyse d ’imagesSystème complet d ’analyse d ’imagesSegmentation - hypothèses - interprétationSegmentation - hypothèses - interprétationApplication de principes de psycho-visionApplication de principes de psycho-vision

Organisation perceptuelle de scènes complexesOrganisation perceptuelle de scènes complexesRestriction aux structures issues des contoursRestriction aux structures issues des contoursValidation sur des images synthétiquesValidation sur des images synthétiquesApplication à des images de scènes réellesApplication à des images de scènes réelles

But :But :Extraire un ensemble d’éléments de représentationExtraire un ensemble d’éléments de représentationRester ouvert aux besoins spécifiques d’applications futuresRester ouvert aux besoins spécifiques d’applications futures

30 Septembre 1998Laurent ALQUIER -

Vue d’ensemble du systèmeVue d’ensemble du système

Détection de contoursDétection de contours

Trois niveaux de groupementTrois niveaux de groupementSélection des structures saillantesSélection des structures saillantesExtraction d’hypothèses intermédiairesExtraction d’hypothèses intermédiairesOrganisation d’hypothèses complexesOrganisation d’hypothèses complexes

Relations hiérarchiques entre hypothèsesRelations hiérarchiques entre hypothèses

Application Application Détection de jonctionsDétection de jonctionsMise en correspondanceMise en correspondance

30 Septembre 1998Laurent ALQUIER -

Plan de l’exposéPlan de l’exposé

Introduction.Introduction. Présentation globale.Présentation globale. Groupement par réseaux de saillance.Groupement par réseaux de saillance. Niveaux supérieurs de groupement.Niveaux supérieurs de groupement. Contributions et perspectives.Contributions et perspectives.

30 Septembre 1998Laurent ALQUIER -

Recherche de structures curvilignesRecherche de structures curvilignes

But :But :Isoler les contours les plus réguliersIsoler les contours les plus réguliersCompléter les discontinuitésCompléter les discontinuitésExtraire des structures stablesExtraire des structures stables

30 Septembre 1998Laurent ALQUIER -

Groupement par saillanceGroupement par saillance PrincipesPrincipes

Evaluer la qualité d ’un groupement éventuelEvaluer la qualité d ’un groupement éventuelOptimiser de cette fonction de qualitéOptimiser de cette fonction de qualité

Mesure directeMesure directeChamps d ’extension (Guy et Medioni, 1996)Champs d ’extension (Guy et Medioni, 1996)Champs stochastiques de fermeture (Williams et Jacobs, 1994)Champs stochastiques de fermeture (Williams et Jacobs, 1994)

Approches par optimisationApproches par optimisationRéseaux de neurones (F. Mangin, 1994)Réseaux de neurones (F. Mangin, 1994)Optimisation par recuit simulé (L. Hérault, 1991)Optimisation par recuit simulé (L. Hérault, 1991)Réseaux de saillance (Shashua et Ullman, 1989) Réseaux de saillance (Shashua et Ullman, 1989)

30 Septembre 1998Laurent ALQUIER -

Réseaux de saillance Réseaux de saillance

30 Septembre 1998Laurent ALQUIER -

Réseaux de saillance (2)Réseaux de saillance (2)

Choix d’une primitive de groupementChoix d’une primitive de groupement

Définition de ses attributsDéfinition de ses attributs

Définition d’un voisinage localDéfinition d’un voisinage localRéseau de primitives localement connectéesRéseau de primitives localement connectées

Fonction de qualité pour un groupementFonction de qualité pour un groupementEvaluation de la compatibilité entre primitivesEvaluation de la compatibilité entre primitivesFonctions « extensibles »Fonctions « extensibles »

Mesure de saillanceMesure de saillanceQualité du meilleur groupement Qualité du meilleur groupement

30 Septembre 1998Laurent ALQUIER -

Définition du voisinageDéfinition du voisinage

Relations entre primitives.Relations entre primitives.Primitives reliées entre elles par un élément de Primitives reliées entre elles par un élément de

connexionconnexionCritères de proximité et compatibilitéCritères de proximité et compatibilitéMéthode adaptée à des structures curvilignesMéthode adaptée à des structures curvilignes

Importance du voisinage.Importance du voisinage.Initialise l’optimisation du réseauInitialise l’optimisation du réseauDétermine la taille du réseauDétermine la taille du réseauInfluence sur la qualité des groupementsInfluence sur la qualité des groupements

30 Septembre 1998Laurent ALQUIER -

Fonction de qualitéFonction de qualité

Critères de régularitéCritères de régularitéProximité, continuité, similaritéProximité, continuité, similarité

FormalismeFormalismeCombinaison linéaire de contraintes antagonistesCombinaison linéaire de contraintes antagonistesRelations « internes »Relations « internes »

Propres aux groupement recherchésPropres aux groupement recherchésRelations « externes »Relations « externes »

Imposées par l ’image de contoursImposées par l ’image de contours

externe interne

)F(j

jjk

kk RR

30 Septembre 1998Laurent ALQUIER -

Mesure de saillanceMesure de saillance

Définition formelle de la saillanceDéfinition formelle de la saillanceMeilleure somme des fonctions de qualité d ’un Meilleure somme des fonctions de qualité d ’un

groupement selon deux directions.groupement selon deux directions.

)()(Max )( vv)( )v (v,

FFPSPV 2

Ecriture récursiveEcriture récursiveOn suppose que la fonction F est « extensible »On suppose que la fonction F est « extensible »

)),,(Max,(Max),,(Max 21)(

11)(

1)( 2

111

NNee

NNe

eeeeeNN

30 Septembre 1998Laurent ALQUIER -

Mesure de saillance (2)Mesure de saillance (2)

Optimisation itérativeOptimisation itérativeRecherche des meilleurs voisinsRecherche des meilleurs voisinsMise à jour des contributionsMise à jour des contributions

)(),(

)(),(

)(

)(3

13

2

221

eRevP

eRevP

vQ

vRnkk

nkk

nk

nk

Exemple d ’écriture récursiveExemple d ’écriture récursiveTerme localTerme localContributions des voisinsContributions des voisins

30 Septembre 1998Laurent ALQUIER -

Mesure de saillance (2)Mesure de saillance (2)

PropriétésPropriétésMesures locales - Optimisation globaleMesures locales - Optimisation globaleElimination des discontinuitésElimination des discontinuitésCarte de saillanceCarte de saillanceGroupement possible par suivi des connexionsGroupement possible par suivi des connexions

Un seul groupement optimal par primitiveUn seul groupement optimal par primitive

30 Septembre 1998Laurent ALQUIER -

Mesure de saillance (3)Mesure de saillance (3)

ApplicationApplicationGroupement de pixelsGroupement de pixels

Voisinage fixeVoisinage fixe Calculs lourdsCalculs lourds Optimisation lenteOptimisation lente

Groupement de chaînes de Groupement de chaînes de pixelspixels Voisinage adaptatifVoisinage adaptatif Complexité réduiteComplexité réduite Optimisation rapide Optimisation rapide

30 Septembre 1998Laurent ALQUIER -

Intérêt du groupementIntérêt du groupement

Chaînage classiqueChaînage classique

Groupement de chaînesGroupement de chaînes

30 Septembre 1998Laurent ALQUIER -

Détection de groupes saillantsDétection de groupes saillants

30 Septembre 1998Laurent ALQUIER -

Groupements élémentairesGroupements élémentaires

Classes de groupementsClasses de groupementsPoint de départ le long d ’une même structurePoint de départ le long d ’une même structurePhénomène « d ’attraction »Phénomène « d ’attraction »

Critères d’évaluationCritères d’évaluation

Saillance localeSaillance localeSaillance globale ( somme des saillances des Saillance globale ( somme des saillances des

primitives )primitives )Accumulation de votesAccumulation de votes

SélectionSélectionSeuillage par rapport aux critèresSeuillage par rapport aux critères

30 Septembre 1998Laurent ALQUIER -

Groupements élémentaires (2)Groupements élémentaires (2)

30 Septembre 1998Laurent ALQUIER -

Plan de l’exposéPlan de l’exposé

Introduction.Introduction. Présentation globale.Présentation globale. Groupement par réseaux de saillance.Groupement par réseaux de saillance. Niveaux supérieurs de groupement.Niveaux supérieurs de groupement.

Groupements intermédiairesGroupements intermédiairesGroupements complexes et applicationGroupements complexes et application

Contributions et perspectives.Contributions et perspectives.

30 Septembre 1998Laurent ALQUIER -

Groupements intermédiaires Groupements intermédiaires

Hypothèses structurellesHypothèses structurelles

Parties rectilignes : SegmentsParties rectilignes : SegmentsParties courbes : ArcsParties courbes : ArcsPoints particuliers : Jonctions, points d’inflexion, Points particuliers : Jonctions, points d’inflexion,

coinscoins

Principes d ’extractionPrincipes d ’extractionDétection à partir de chaque groupement élémentaireDétection à partir de chaque groupement élémentaire

Paramètre d ’échelle, sensibilitéParamètre d ’échelle, sensibilitéAgglomération des hypothèses primairesAgglomération des hypothèses primaires

Critère de similarité - élimination des redondancesCritère de similarité - élimination des redondances

30 Septembre 1998Laurent ALQUIER -

Groupements intermédiaires (2)Groupements intermédiaires (2)

Eléments de représentation symboliques de la scène.Eléments de représentation symboliques de la scène.

Ensemble d’hypothèsesEnsemble d’hypothèsesPart d'ambiguïtés et d’erreursPart d'ambiguïtés et d’erreursRedondances toléréesRedondances tolérées

Problèmes à résoudreProblèmes à résoudreDiscrétisationDiscrétisationStructures de taille différentes dans une même scèneStructures de taille différentes dans une même scèneConséquence des groupements élémentairesConséquence des groupements élémentaires

Superposition de groupements semblablesSuperposition de groupements semblables Critères de régularité insuffisants (occlusions et jonctions)Critères de régularité insuffisants (occlusions et jonctions)

30 Septembre 1998Laurent ALQUIER -

Hypothèses de segments Hypothèses de segments

Groupements saillantsGroupements saillantsGroupements saillantsGroupements saillants

Points d ’intérêtPoints d ’intérêtPoints d ’intérêtPoints d ’intérêt

Découpage récursif Découpage récursif (écart Es)(écart Es)Découpage récursif Découpage récursif (écart Es)(écart Es)

Fusion de segments similaires Fusion de segments similaires (longueur,orientation)(longueur,orientation)

Fusion de segments similaires Fusion de segments similaires (longueur,orientation)(longueur,orientation)

Segments groupésSegments groupésSegments groupésSegments groupés

Segments élémentaires

30 Septembre 1998Laurent ALQUIER -

Segments (avant groupement)Segments (avant groupement)

30 Septembre 1998Laurent ALQUIER -

Segments ( après groupement )Segments ( après groupement )

30 Septembre 1998Laurent ALQUIER -

Hypothèses d ’arcs Hypothèses d ’arcs

Groupements saillantsGroupements saillantsGroupements saillantsGroupements saillants

Points d ’intérêtPoints d ’intérêtPoints d ’intérêtPoints d ’intérêt

Découpage selon extrema de courbure Découpage selon extrema de courbure (échelle Ea)(échelle Ea)

Découpage selon extrema de courbure Découpage selon extrema de courbure (échelle Ea)(échelle Ea)

Fusion d ’arcs similaires Fusion d ’arcs similaires (classe,superposition)(classe,superposition)

Fusion d ’arcs similaires Fusion d ’arcs similaires (classe,superposition)(classe,superposition)

Arcs groupésArcs groupésArcs groupésArcs groupés

Classes d ’arcs élémentaires

30 Septembre 1998Laurent ALQUIER -

Arcs ( après groupement )Arcs ( après groupement )

30 Septembre 1998Laurent ALQUIER -

Points d ’intérêtPoints d ’intérêt

30 Septembre 1998Laurent ALQUIER -

Plan de l’exposéPlan de l’exposé

Introduction.Introduction. Présentation globale Présentation globale Groupement par réseaux de saillance.Groupement par réseaux de saillance. Niveaux supérieurs de groupement.Niveaux supérieurs de groupement.

Groupements intermédiairesGroupements intermédiairesGroupements complexes et applicationGroupements complexes et application

Contributions et perspectives.Contributions et perspectives.

30 Septembre 1998Laurent ALQUIER -

Groupements complexesGroupements complexes

Exemple d’applicationExemple d’applicationExtraction de jonctions multiplesExtraction de jonctions multiplesMise en correspondance de jonctionsMise en correspondance de jonctions

Intérêt des jonctionsIntérêt des jonctions

Information structurelle richeInformation structurelle riche Position du centre, orientation des branchesPosition du centre, orientation des branches Mise en correspondance robusteMise en correspondance robuste Localisation précise a posterioriLocalisation précise a posteriori

Difficiles à obtenirDifficiles à obtenir Altérations dues au détecteur de contoursAltérations dues au détecteur de contours

Peu de travaux sur le groupement de jonctionsPeu de travaux sur le groupement de jonctions

30 Septembre 1998Laurent ALQUIER -

Groupement de jonctionsGroupement de jonctions

SegmentsSegmentsSegmentsSegments PointsPointsPointsPoints

Détection de jonctions doublesDétection de jonctions doublesDétection de jonctions doublesDétection de jonctions doubles

Groupement de jonctions doublesGroupement de jonctions doubles(proximité des centres, branches similaires)(proximité des centres, branches similaires)

Groupement de jonctions doublesGroupement de jonctions doubles(proximité des centres, branches similaires)(proximité des centres, branches similaires)

Jonctions multiplesJonctions multiplesJonctions multiplesJonctions multiples

Intersections deux à deuxConfirmation

du centre

30 Septembre 1998Laurent ALQUIER -

Détection de jonctions doublesDétection de jonctions doubles

30 Septembre 1998Laurent ALQUIER -

Groupement de jonctions multiplesGroupement de jonctions multiples

30 Septembre 1998Laurent ALQUIER -

Mise en correspondanceMise en correspondance

PrincipePrincipeEtiquetage cohérent entre Etiquetage cohérent entre

deux ensembles de jonctionsdeux ensembles de jonctions

NécessiteNécessiteMesure de comparaison directe entre jonctionsMesure de comparaison directe entre jonctionsMesure de déplacement (transformation)Mesure de déplacement (transformation)

Entre deux imagesEntre deux images Dans une même imageDans une même image

Comparaison conditionnelleComparaison conditionnelle

30 Septembre 1998Laurent ALQUIER -

Mise en correspondance (2)Mise en correspondance (2)

Méthode en deux étapesMéthode en deux étapesAppariement temporelAppariement temporel

Elimination des appariements improbablesElimination des appariements improbablesAppariement spatialAppariement spatial

Elimination des groupements improbables Elimination des groupements improbables

PropriétésPropriétésAppariement en tant que groupement perceptuelAppariement en tant que groupement perceptuelAdmet des écarts importants entre imagesAdmet des écarts importants entre imagesRenforcement mutuel de deux types de groupementsRenforcement mutuel de deux types de groupements

30 Septembre 1998Laurent ALQUIER -

Mise en correspondance (3)Mise en correspondance (3)

30 Septembre 1998Laurent ALQUIER -

Mise en correspondance (4)Mise en correspondance (4)

30 Septembre 1998Laurent ALQUIER -

Plan de l’exposéPlan de l’exposé

Introduction.Introduction. Présentation globale.Présentation globale. Groupement par réseaux de saillance.Groupement par réseaux de saillance. Niveaux supérieurs de groupement.Niveaux supérieurs de groupement. Contributions et perspectives.Contributions et perspectives.

30 Septembre 1998Laurent ALQUIER -

ContributionsContributions

Réseaux de saillanceRéseaux de saillanceFormalisme génériqueFormalisme générique

Généralisation au groupement de chaînesGénéralisation au groupement de chaînesFonction de qualité plus soupleFonction de qualité plus soupleOptimisation plus stableOptimisation plus stable

Choix des meilleures connexions Choix des meilleures connexions Critères de groupementCritères de groupement

Sélection des structures les plus saillantesSélection des structures les plus saillantes

Shashua et Ullman, 1991 - Alter et Basri, 1997Shashua et Ullman, 1991 - Alter et Basri, 1997

Références

30 Septembre 1998Laurent ALQUIER -

Contributions (2)Contributions (2)

Groupement d’hypothèsesGroupement d’hypothèsesSegmentsSegmentsArcsArcsPoints d’intérêtPoints d’intérêt

Approche modulaireApproche modulaireStratégie de groupement génériqueStratégie de groupement génériqueModules spécialisésModules spécialisés

Hypothèses selon une échelle donnéeHypothèses selon une échelle donnée Utilisation de nombreuses images réellesUtilisation de nombreuses images réelles

Mohan et Nevatia, 1992 - Sarkar et Boyer, 1993 - Gao et Wong, 1993Mohan et Nevatia, 1992 - Sarkar et Boyer, 1993 - Gao et Wong, 1993

Références

30 Septembre 1998Laurent ALQUIER -

Contributions (3)Contributions (3)

Organisation perceptuelle de jonctionsOrganisation perceptuelle de jonctionsDétection de jonctions élémentairesDétection de jonctions élémentairesGroupement en jonctions multiplesGroupement en jonctions multiples

Mise en correspondance structurelleMise en correspondance structurelleCouplage entre groupement perceptuel et Couplage entre groupement perceptuel et

appariementappariement

Matas and Kittler, 1993 - Chang and Aggarwal, 1997Matas and Kittler, 1993 - Chang and Aggarwal, 1997

Références

30 Septembre 1998Laurent ALQUIER -

RésultatsRésultats

Résultats stables Résultats stables Paramètres génériques pour des classes d’imagesParamètres génériques pour des classes d’imagesRobuste en cas de perturbationsRobuste en cas de perturbations

Temps raisonnables sur systèmes usuelsTemps raisonnables sur systèmes usuelsExemple typique Exemple typique (ordres de grandeur)(ordres de grandeur)

PC - Pentium 100 - 65 Mo RAMPC - Pentium 100 - 65 Mo RAM Image 800x600 pixelsImage 800x600 pixels 500 chaînes environ500 chaînes environ Etape de groupement par saillance : 30sEtape de groupement par saillance : 30s Temps de calcul global : 5 minTemps de calcul global : 5 min

30 Septembre 1998Laurent ALQUIER -

Application : Scènes d ’extérieurApplication : Scènes d ’extérieur

30 Septembre 1998Laurent ALQUIER -

Application : Imagerie satellitaireApplication : Imagerie satellitaire

30 Septembre 1998Laurent ALQUIER -

Mise en correspondance Mise en correspondance

30 Septembre 1998Laurent ALQUIER -

Mise en correspondanceMise en correspondance

30 Septembre 1998Laurent ALQUIER -

Prolongements à court termeProlongements à court terme

Groupement d’objets génériquesGroupement d’objets génériques

Evaluation quantitative des résultatsEvaluation quantitative des résultatsRésultats qualitatifs uniquementRésultats qualitatifs uniquement

Nombreux paramètres à réglerNombreux paramètres à réglerDéfinition empirique pour l’instantDéfinition empirique pour l’instant

Validation automatique des hypothèsesValidation automatique des hypothèses Détection multi-échelleDétection multi-échelle Mise en correspondance hiérarchique Mise en correspondance hiérarchique

Approche descendanteApproche descendante

30 Septembre 1998Laurent ALQUIER -

PerspectivesPerspectives

Intégration avec d ’autres indices visuelsIntégration avec d ’autres indices visuelsAttention visuelle et suiviAttention visuelle et suivi

Laurent Iti, 1997 Caltech - Roch et Ullman, 1985Laurent Iti, 1997 Caltech - Roch et Ullman, 1985

Références

30 Septembre 1998Laurent ALQUIER -

Perspectives (2)Perspectives (2)

Aide à l ’indexation automatique de modèlesAide à l ’indexation automatique de modèlesGraphes d ’aspect - Pope et Lowe, 1996Graphes d ’aspect - Pope et Lowe, 1996