Organisation perceptuelle de structures curvilignes Laurent Alquier Directeur de thèse : Chabane Oussalah Professeur Responsable : Philippe Montesinos

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


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


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


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.


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


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



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.


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


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)


Réseaux de saillance Réseaux de saillance


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


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


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


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


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



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



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


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

Chaînage classiqueChaînage classique

Groupement de chaînesGroupement de chaînes


Détection de groupes saillantsDétection de groupes saillants


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


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



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.


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


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)


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


Segments (avant groupement)Segments (avant groupement)


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


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


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


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



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.


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


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


Détection de jonctions doublesDétection de jonctions doubles


Groupement de jonctions multiplesGroupement de jonctions multiples


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


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







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.


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


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


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


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


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


Application : Imagerie satellitaireApplication : Imagerie satellitaire


Mise en correspondance Mise en correspondance


Mise en correspondanceMise en correspondance


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


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


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

Documents

Organisation perceptuelle de structures curvilignes Laurent Alquier Directeur de thèse : Chabane Oussalah Professeur Responsable : Philippe Montesinos