Reconnaissance de lieux sémantiques en robotique 

Télécharger le fichier pdf d’un mémoire de fin d’études

Sources d’informations pour la navigation

Un robot dispose de deux sources d’information principales pour se localiser et naviguer :
– Les informations proprioceptives (ou idiothétiques) qui sont fournies par des capteurs internes au robot et qui le renseignent sur son déplacement dans l’espace.
– Les informations extéroceptives (ou allothétiques) ou plus simplement les perceptions qui sont des informations à propos de l’environnement et qui sont caractéristiques d’une position. Ces informations peuvent être de nature très variée. Par exemple, un robot peut mesurer la distance à laquelle se trouvent des obstacles avec des capteurs infrarouges ou utiliser une caméra.
Informations proprioceptives Il existe deux types de capteurs proprioceptifs qui peuvent renseigner un robot sur son déplacement :
les capteurs mesurant la rotation de ses roues (ces capteurs sont appelés « capteurs odométriques ») .
En accumulant ces informations au cours du temps, on peut estimer la position relative de deux points grâce à un processus d’intégration.
Ces informations ont l’avantage de ne pas être perturbées par l’environnement extérieur et de fournir directement la position du robot dans un repère euclidien. En revanche, les erreurs à chaque pas de temps sont accumulées et l’estimation de la position devient de moins en moins fiable au cours du temps. Il est notoire en robotique que les informations d’odométrie sont entachées d’une erreur importante et que l’estimation de la position du robot sur la base de ces seules données n’est pas fiable.
Informations extéroceptives Les informations extéroceptives renseignent le robot sur son environnement. Il existe plusieurs types de capteurs extéroceptifs :
– capteurs infrarouges .
– télémètres lasers ou à ultrasons .
– caméras (simples ou panoramiques) et éventuellement système de vision stéréoscopique. Ces informations permettent au robot de se positionner dans l’espace indépendamment de ses déplacements et donc ne sont pas soumises à l’accumulation d’erreurs.

Stratégies de navigation

Trullier et al. [Tru+97] distinguent deux grands types de stratégies de navigation que nous allons détailler : les stratégies sans modèle interne et les stratégies avec modèle interne.
Parmi les stratégies sans modèle interne, on distingue :
L’approche d’un objet par des actions réflexes. L’exemple le plus connu est sans doute les véhicules de Braitenberg (voir [Bra84]) capables de s’orienter vers une source de lumière. Ces véhicules réalisent simplement une remontée ou une descente de gradient sur l’intensité de la lumière. Ils correspondent à un simple contrôleur proportionnel en automatique et sont donc sujets à des oscillations dans le comportement du robot.
La stratégie de guidage par des amers qui permet d’atteindre un lieu défini par une configuration spatiale d’objets remarquables ; cette stratégie utilise une descente de gradient pour reproduire la configuration mémorisée. Ce type de stratégie est par exemple utilisé par les abeilles.
Ces stratégies permettent de naviguer vers un point sous condition que le but ou les amers décrivant le but soient perceptibles.
Les stratégies basées sur un modèle interne sont :
La stratégie d’action associée à un lieu (recognition-triggered response) : dans cette stratégie, à chaque lieu est associée une action permettant de rejoindre le but ; lorsqu’un lieu est reconnu, l’action associée est déclenchée ; le robot va donc suivre des routes fixées qui le mènent vers un but .
La navigation topologique : le modèle interne est un graphe qui mémorise des lieux (définis comme un ensemble de zones de l’espace dans lesquelles les perceptions sont similaires) et les relations d’accessibilité entre ces lieux ; le robot est ainsi capable de composer un nouveau chemin à partir de segments connus ; cependant, le robot ne peut pas atteindre des endroits qu’il n’a pas encore visités ou emprunter des chemins qu’il n’a pas déjà parcourus.

Robotique cognitive

La navigation métrique : le modèle interne stocke les positions dans un repère commun ; le robot peut donc calculer les positions relatives entre deux lieux, ce qui permet de calculer des déplacements même s’ils n’ont pas été mémorisés sous forme d’un lien.
Les stratégies 1 à 3 sont basées sur des actions réflexes et ne nécessitent pas une représenta-tion globale du monde. On les regroupe sous le terme de navigation réactive. Les stratégies 4 et 5 nécessitent la construction d’une carte i.e. d’un modèle détaillé du monde. L’utilisation d’une carte n’est pas réservée aux êtres humains. En effet, de nombreux auteurs ont montré l’existence de cellules spécialisées dans la représentation de l’espace chez les mammifères (voir [OC78]) formant de véritables cartes cognitives (voir [ON78 ; GC96]) 2.
Nous détaillons dans la section suivante les différents types de cartes utilisées en robotique.

Les différents types de cartes

Suivant [TBF05], nous définissons une carte comme une collection « d’objets », pris au sens très général : m = fm1; m2; : : : ; mN g.
On distingue généralement deux types de cartes selon la nature des informations spatiales qu’elles incorporent : les cartes métriques et les cartes topologiques. Ces cartes ne doivent pas être confondues avec les stratégies de navigation définies à la page 8.
Une définition un peu plus précise consiste à parler de cartes basées sur les coordonnées (location-based maps) et de cartes basées sur les points de repères (feature-based maps) :
– Dans les cartes basées sur les coordonnées, chaque position est étiquetée. Autrement dit, l’indice n correspond à la position (x; y) dans un repère absolu ; ce sont ces cartes que l’on désigne sous le nom de cartes métriques.
– Dans les cartes basées sur les points de repère, l’objet mn contient la position et les propriétés d’un point de repère particulier (landmark ou feature) ; ces cartes sont désignées sous le nom de cartes topologiques. Contrairement à ce que le nom pourrait faire penser, les cartes topologiques contiennent aussi la position des points dans un repère global (ce qui est indispensable pour les stratégies de navigation évoluées)
Ces deux types de cartes se différencient par la manière de discrétiser l’environnement. Dans les approches basées sur les coordonnées, l’environnement est découpé densément en cellules, en général de taille fixe. Un exemple classique d’une telle représentation est la grille d’occupation (voir figure I.2a) dans laquelle chaque cellule est représentée par une variable binaire dont la valeur code l’occupation (0=libre, 1=occupé). Le but de la cartographie est donc de déterminer, sur la base des mesures, la probabilité pour une cellule d’être libre.

Le problème du SLAM

Pour les environnements simples, il est possible de fournir une carte au robot, par exemple partir des plans du bâtiment. Cependant, ces plans ne sont pas toujours précis et ne répertorient pas les divers objets à l’intérieur du bâtiment qui peuvent gêner la progression du robot (et dont la position peut varier au cours du temps). De plus, ces cartes ne sont pas toujours disponibles (qu’on songe par exemple à des robots devant opérer après une catastrophe naturelle). Il est donc nécessaire pour le robot de cartographier son environnement en même temps qu’il l’explore. Ce problème est connu sous le nom de « cartographie et localisation simultanées » (en anglais, Simultaneous Location And Mapping (SLAM)).
Ce problème est difficile car la construction d’une carte implique de localiser les différents objets par rapport à soi, ce qui suppose de se localiser, donc d’avoir une carte. Le problème du SLAM semble donc se ramener à un problème du type « l’œuf ou la poule ? ».
Nous étudierons dans la Section I.1.4 les approches probabilistes de ce problème. La section suivante est consacrée à l’étude des grands paradigmes de la robotique et à leurs applications en navigation.

Approche probabiliste du SLAM

Les techniques probabilistes ([Thr01 ; TBF05]) ont été introduites en robotique dans le sillage de l’approche située. Cette approche se base sur des modèles statistiques des capteurs et des effecteurs. De même, les modèles internes sont probabilistes. Ces modèles intègrent donc naturellement l’incertitude dont sont affectés les capteurs et les effecteurs et l’aspect stochastique du monde extérieur. Ainsi, dans un problème de navigation, au lieu de donner une seule estimation de la localisation, les algorithmes probabilistes se basent sur la distribution de probabilité de toutes les localisations. De plus, ces modèles sont capables d’intégrer plusieurs sources d’information (voir Section I.1.2.1), car ces sources sont représentées de manière unifiée sous forme de probabilité.
Cette approche s’est imposée grâce à sa robustesse dans le monde réel et au fait qu’on dispose d’algorithmes efficaces. De ce point de vue, on peut dire qu’elle augmente le caractère situé de la robotique. Notons cependant qu’il n’y a en général qu’un seul contrôleur monolithique. De plus, d’un point de vue philosophique, les probabilités sont une forme de représentation.
En terme de navigation, ces modèles utilisent une carte et donc les stratégies de navigation topologique ou métrique.
Nous présentons tout d’abord les grands principes des méthodes probabilistes avant de parler de leur apport au problème du SLAM.

Interaction robot-environnement

Le formalisme probabiliste permet d’intégrer les mesures et les actions du robot au cours du temps de manière efficace. Plus formellement, les croyances du robot sur son état interne et l’état du monde au temps t sont représentées par une variable aléatoire Y t 5. Cette variable représente tout ce qui peut influer sur l’évolution du monde. Dans un problème de localisation, cette variable contiendra les coordonnées (x; y) et l’orientation du robot dans un repère global. Dans un problème de SLAM, cette variable contiendra aussi la carte m (voir Section I.1.4). De même, les actions et les mesures effectuées par le robot au temps t sont représentées par une variable aléatoire (Ut pour les actions, Xt pour les mesures). Le robot doit estimer la séquence des état cachés Y 1:t. Pour cela, il connaît uniquement la séquence des observations, X1:t, et des actions qu’il a effectuées, U1:t. Les croyances (beliefs) du robot au temps t sont représentées par la densité de probabilité p (Y tjX1:t; U1:t), qu’on note bel (Y t) 6.
L’approche probabiliste repose sur les deux hypothèses suivantes :
1. L’hypothèse markovienne de l’évolution de l’état stipule que la connaissance de l’état au temps t dépend uniquement de l’état précédent : p (Y tjY 0:t 1; X 1:t 1; U1:t) = p (Y tjY t 1; U t). Cette distribution de probabilité est appelée modèle de transition car elle représente l’évolution de l’état du monde en fonction des actions du robot (notons cependant qu’elle dépend aussi de la dynamique propre du monde).
L’hypothèse de l’état complet stipule que l’état courant explique complètement l’obser-vation courante : p (XtjY 0:t; X1:t 1; U1:t) = p (XtjY t). De plus, cette distribution de probabilité est souvent indépendante de t : p (XtjY t) = p (XjY ). On parle alors de modèle de capteur bien que la réponse du modèle dépend de l’état du monde.
Les relations entre les variables sont représentées graphiquement par le réseau bayésien de la figure I.6. Ce formalisme entretient une relation profonde avec les modèles de Markov cachés.

Vision par ordinateur

Lorsqu’on présente une image à un être humain, il l’interprète spontanément en terme d’objets, de texte, de personnes, voire d’intentions. Ce processus est en général inconscient et très rapide (quelques centaines de millisecondes).
Informatiquement, une image est représentée par une matrice de pixels, chaque pixel étant codé par un ou plusieurs nombres. Par exemple, la Figure I.8 montre une image et sa représen-tation informatique. Là où nous interprétons spontanément le contenu sémantique de l’image, l’ordinateur n’a accès qu’à la valeur des pixels 9 . Cette différence entre l’interprétation d’une image et l’information contenue dans la valeur des pixels est appelée « gouffre sémantique ».
L’image informatique est obtenue à partir d’un processus complexe de projection de la scène 3D (par l’appareil optique), de quantification spatiale (pixel) et de quantification de l’intensité (niveau discret de luminance). On appelle pré-image la scène 3D telle qu’elle est réellement.
La vision par ordinateur vise à extraire de l’information d’une ou plusieurs images afin de résoudre une tâche. Les tâches classiques de vision par ordinateur sont :
– la segmentation d’image et l’extraction de contours .
– la reconnaissance d’objets, de scènes et de visages .
– plus récemment, l’indexation de larges bases de données d’images, appelé Content Based Image Retrieval (CBIR) en anglais, en vue de retrouver des images similaires.
La question fondamentale de la vision par ordinateur, qui distingue cette discipline du domaine voisin du traitement d’image, peut être vue comme un problème inverse : comment reconstituer la scène en 3D à partir de l’image en 2D ? De ce point de vue, la plupart des problèmes de vision sont des problèmes mal-posés. C’est pourquoi la plupart ne peuvent pas être résolus dans une approche purement ascendante (data-driven ou bottom-up). Ce problème est particulièrement important dans les applications de la vision par ordinateur pour un robot, celui-ci étant intrinsèquement situé dans la scène 3D. La difficulté principale est qu’une légère modification des conditions de prise de vue (angle de prise de vue, luminance, zoom) génère une image très différente d’un point de vue informatique.
L’importance des connaissances a priori peut être illustrée à l’aide de la Figure I.9. Cette figure est interprétée de façon stable par les individus : la première et la troisième ligne sont perçues convexes (à l’exception du 5e hémisphère de la 3e ligne), tandis que les deux autres sont perçues concaves. Cependant, cette figure est intrinsèquement ambiguë : si l’on retourne la feuille, une ligne interprétée comme concave est maintenant convexe. L’interprétation de cette figure repose sur la connaissance acquise, lors de nos expériences quotidiennes, que les sources lumineuses sont situées en hauteur et donc la partie basse d’un objet convexe est sombre. Ainsi, les parties dont la partie basse est plus sombre sont interprétées comme convexes et celles dont la base est plus claire sont interprétées comme concaves.

Description phénoménologique des images naturelles

Les images naturelles sont définies par opposition aux images fabriquées ou manipulées par l’homme (images de synthèse, tableaux, dessins, etc.). La figure I.10 présente des exemples d’images naturelles et d’images non-naturelles. Le chapitre II se concentrera sur une sous-classe des images naturelles : les scènes. L’étude des images naturelles présente un grand intérêt parce que, bien que représentant une fraction infime de l’ensemble des images possibles, elles forment une part non-négligeable de l’ensemble des images que nous rencontrons quotidiennement 10. C’est à ce type d’images que sera confronté notre système robotique, aussi, nous nous intéresserons uniquement à celles-ci.
Nous présentons les grandeurs perceptuelles utilisées à la fois par les humains et par les algorithmes de vision par ordinateur pour accéder au contenu des images.

Intensité

La valeur des pixels code en général l’intensité lumineuse locale d’une zone de la pré-image 11. C’est l’information de base utilisée par les algorithmes de vision par ordinateur. La valeur enregistrée par un pixel dépend de l’imageur, de ses réglages, de la luminosité ambiante, etc. Ainsi, la valeur brute en niveau de gris est rarement utilisée telle quelle, la plupart des algorithmes utilisant des gradients de niveau de gris.

Couleur

Il existe différents moyens de représenter la couleur dans une image informatique. Le codage le plus courant est le codage RGB où chaque pixel est représenté par 3 valeurs indépendantes, chacune représentant un canal (une couleur est donc représentée par un point dans un espace euclidien à 3 dimensions). La couleur finale est obtenue par synthèse additive. L’inconvénient majeur de ce modèle de couleur est qu’il dépend de l’appareil utilisé pour représenter l’image. D’autres descriptions plus proches de la perception humaine des couleurs existent (appelées espaces perceptifs). L’idée principale est de séparer les informations de couleur et de luminance. C’est d’ailleurs ainsi que procède le cortex visuel (voir [SLC90]). On peut citer ([Pra07]) :
– L’espace HSV (Hue, Saturation, Value) qui code les couleurs selon un système de coordonnées cylindriques : l’angle autour de l’axe central est la teinte (hue), qui représente la sensation de couleur, indépendamment de la luminosité ; la distance à l’axe correspond à la saturation qui représente le degré de couleur (pâle ou foncé) ; enfin la distance le long de l’axe principal correspond à la brillance (value ou brightness). La séparation entre la couleur et la teinte est intéressante mais l’espace HSV a été critiqué car les 3 composantes sont perceptivement corrélées.
– L’espace Lab : L représente la luminosité, a et b représentent la position de la couleur sur des axes d’opposition de couleurs (rouge/magenta versus vert pour a, bleu versus jaune pour b). Ce système de mesure est très proche de la perception humaine des couleurs.
Le passage du codage RGB à l’un de ces codages s’effectue indépendamment pour chaque pixel, sans tenir compte du voisinage.
La notion de couleur est liée à la longueur d’onde des radiations lumineuses reçues. Cependant, la couleur ne se réduit pas à la longueur d’onde. On sait par exemple que deux sources ayant des caractéristiques spectrales différentes peuvent être perçues comme étant de la même couleur (ce phénomène est appelé métamérisme ; voir [Pra07, p. 25]). À l’opposé, d’autres expériences reportent que nous percevons un objet de la même couleur à différents moments de la journée alors que les propriétés spectrales de la source et donc les longueurs d’ondes réfléchies changent. Certains algorithmes ont cherché à reproduire ce phénomène.
Il existe des images pour lesquelles la valeur du pixel code pour tout à fait autre chose. Par exemple, dans une image échographique, la valeur d’un pixel code l’intensité du signal sonore réfléchi par les tissus et donc leur densité.

Vision par ordinateur

appelé « constance des couleurs », sans y arriver totalement, le plus connu étant Retinex (voir [MPS10]) : dans ces algorithmes, la notion de couleur est définie en fonction des pixels voisins.

Texture

Une texture est une zone de l’image qui a des caractéristiques homogènes, ces caractéristiques ne se réduisant pas uniquement à la couleur ou à la luminance, par exemple, un motif basique qui se répète ou des caractéristiques fréquentielles. La notion de texture est difficile à définir formellement ; il y a plusieurs approches de cette notion.
La description perceptuelle (voir [TMY78]) cherche à exprimer les propriétés des textures de la même manière que le ferait un humain. Ces descripteurs sont donc basés sur des expériences psycho-physiques qui ont permis de définir trois caractéristiques fortement corrélées avec la manière utilisée par les sujets pour classer des textures et les algorithmes pour les calculer :
Le contraste qui dépend de la dynamique des niveaux de gris, de la netteté des contours et de la période des motifs répétés.
La directionnalité (directionality), c’est-à-dire la présence d’une orientation dominante (quelle qu’elle soit) dans la texture.
La rugosité (coarseness) c’est-à-dire la taille des éléments de texture.
L’approche statistique (voir [HSD73]) se base sur la matrice de co-occurrence des valeurs de niveau de gris, c’est-à-dire une approximation de la statistique d’ordre 2. Cette matrice de co-occurrence est collectée dans un voisinage autour de chaque pixel. Différentes valeurs statistiques (que nous décrivons en Appendice C) sont ensuite calculées pour exprimer les propriétés de la texture pour chaque pixel.
On peut aussi utiliser la sortie d’un banc de filtres orientés et multi-échelles pour caractériser les textures (voir [Des03]). On obtient alors plusieurs valeurs pour chaque pixel. Il existe plusieurs techniques pour réduire la quantité d’information :
calculer la moyenne (énergie) et l’écart-type de chaque filtre, ce qui offre une description compacte. calculer la sortie uniquement pour certains points d’intérêt.
Les filtres de Gabor (voir plus bas) ont été les plus utilisés dans ce contexte.

Table des matières

I. Robotique et vision 
1. Robotique cognitive
1.1. Définition et objectifs
1.2. Navigation
1.3. Différentes approches en robotique cognitive
1.4. Approche probabiliste du SLAM
1.5. Conclusion
2. Vision par ordinateur
2.1. Description phénoménologique des images naturelles
2.2. Caractérisation globale des images
2.3. Extraction de zones d’intérêt
2.4. Caractérisation locale des images
2.5. Conclusion
3. Apprentissage artificiel
3.1. Introduction
3.2. Apprentissage génératif et discriminatif
3.3. Conclusion
4. Conclusion générale
II. État de l’art en reconnaissance de scènes 
1. Reconnaissance visuelle
1.1. Introduction
1.2. Reconnaissance d’objets
1.3. Reconnaissance de scènes
1.4. Vue d’ensemble des techniques utilisées en reconnaissance de scènes
2. Approches basées sur les caractéristiques bas-niveau
2.1. Approches globales
2.2. Approches locales
2.3. Approches statistiques
2.4. Conclusion
3. Approches basées sur les mots visuels
3.1. Principe de base
3.2. Avantages et inconvénients
3.3. Améliorations
4. Approches basées sur la modélisation sémantique
4.1. Modélisation sémantique des régions
4.2. Reconnaissance préalable des objets
4.3. Utilisation des propriétés perceptuelles
5. Conclusion
III. Reconnaissance de lieux sémantiques en robotique 
1. Introduction
1.1. Le concept de lieu sémantique
1.2. Reconnaissance visuelle de lieux sémantiques
1.3. Intérêt pour la robotique
2. Position du problème
2.1. Différences par rapport au SLAM
2.2. Différences par rapport à la reconnaissance de scènes
2.3. Position formelle du problème
3. Challenges
3.1. Variabilité des lieux
3.2. Difficultés liées aux images
3.3. Extension spatiale d’un lieu et continuité temporelle
3.4. Conclusion
4. État de l’art en reconnaissance de lieux sémantiques
4.1. Vue d’ensemble de l’état de l’art
4.2. Formats de description de l’image
4.3. Classification et confiance dans la décision
4.4. Intégration temporelle
5. Conclusion
IV.Reconnaissance de lieux avec des modèles sac de mots 
1. Introduction
2. Codages globaux et catégories sémantiques
3. Architecture du système
3.1. Vue d’ensemble
3.2. Signatures utilisées
3.3. Entraînement des cartes de Kohonen
3.4. Apprentissage et intégration temporelle
4. Résultats en reconnaissance d’instances
4.1. Protocole
4.2. Influence de la longueur d’intégration
4.3. Influence de la taille de la carte de Kohonen
4.4. Robustesse aux variations de luminosité
4.5. Comparaison avec l’état de l’art et conclusion
5. Résultats en catégorisation
5.1. Protocole
5.2. Influence de la longueur d’intégration
5.3. Influence de la taille de la carte de Kohonen
5.4. Comparaison avec l’état de l’art et conclusion
5.5. Conclusion
6. Conclusion
V. Détection visuelle des changements de lieux 
1. Introduction
2. Comportement au voisinage des seuils
2.1. Comportement moyen de l’entropie autour des transitions
3. Présentation des algorithmes
3.1. Seuillage de l’entropie
3.2. Détection des maximas locaux de l’entropie
3.3. Utilisation des changements de classification
4. Évaluation
4.1. Résultats en reconnaissance d’instances
4.2. Résultat en catégorisation
5. Conclusion
VI.Utilisation de l’ordre local pour la reconnaissance de lieux 
1. Introduction
2. Filtrage bayésien sur chaînes de Markov
2.1. Présentation générale du modèle
2.2. Algorithme de filtrage bayésien
2.3. Apprentissage des paramètres
3. Résultats en reconnaissance d’instances
3.1. Influence de la matrice de transition
3.2. Influence de la taille de la carte de Kohonen
3.3. Comparaison au filtrage bayésien classique
3.4. Détection des transitions
3.5. Comparaison avec l’état de l’art et conclusion
4. Résultats en catégorisation
4.1. Influence de la matrice de transition
4.2. Influence de la taille de la carte de Kohonen
4.3. Comparaison au filtrage bayésien classique
4.4. Détection des transitions
4.5. Comparaison à l’état de l’art et conclusion
5. Conclusion
VII.Conclusion et perspectives 
1. Contributions
2. Perspectives
2.1. Améliorations du système
2.2. Travaux futurs
A. Bases de données utilisées 
1. Base de données COLD
1.1. Environnements
1.2. Procédure d’acquisition
1.3. Problèmes connus
1.4. Protocole de reconnaissance d’instances de lieux
1.5. Protocole de catégorisation
2. Base de données VPC
2.1. Environnements
2.2. Procédure d’acquisition
2.3. Protocole de catégorisation
3. Stockage des données
B. Cartes auto-organisatrices 
1. Principe
1.1. Carte et cellules
1.2. Apprentissage compétitif et projection des données
2. Description détaillée
2.1. Algorithme d’apprentissage
2.2. Voisinage
3. Paramètres et ensemble d’apprentissage
3.1. Paramètres
3.2. Ensemble d’apprentissage
C. Fonctions de texture 
1. Fonctions de texture sur un histogramme du premier ordre
2. Fonctions de texture sur un histogramme du second ordre
3. Signatures basées sur les fonctions de textures
D. Théorie de la détection 
1. Cas de la classification binaire
1.1. Table de contingence
1.2. L’espace ROC
1.3. Courbe ROC
2. Cas d’un problème à plus de deux classes

Télécharger le rapport complet