Estimation de la Forme Volumique à Partir des Images

Motivation

     Dans ce contexte, ce travail de thèse a pour but de réaliser une des tâches assurée par le système visuel humain. On travaille sur les trois capacités de la vision par ordinateur pour analyser une scène et pouvoir estimer la forme des objets présents et les distances qui les sépares. L’objectif est d’arriver a une reconstruction tridimensionnelle d’une scène observée par une ou plusieurs caméras. Le modèle utilisé dans tout ce document est le modèle sténopé (Pinhole model). Le processus de reconstruction des formes volumiques est composé de plusieurs sous-tâches. La thèse est composée d’une introduction, de cinq chapitre dont quatre explique ces différentes étapes de la reconstruction et une conclusion. Le document se résume comme suit :
— Ayant utilisé des métaheuristiques, le deuxième chapitre introduit ces approches appelées approches bio-inspirées qui s’inspirent des systèmes biologiques, et des comportements des êtres vivants. Cette partie va se concentrer sur l’optimisation par essaims de particules (PSO) qui nous intéressent dans ce travail. On a utilisé cette dernière pour résoudre l’Homographie qui est un des problèmes rencontrés durant le processus la reconstruction 3D.
— Le troisième chapitre consiste a la Stéréovision : C’est l’analyse de deux ou plusieurs images d’une même scène prises sous des différents angles. Le chapitre explique tous ce qui est nécessaire pour calculer les correspondances entre ces images, faire la liaison entre les points d’intérêts, ensuite corriger ces images pour faciliter le processus d’appariement et de reconstruction. Des résultats sont présentés illustrant les sorties du logiciel élaboré à partir de ce travail.
— Le quatrième chapitre est dédié à une transformation projective très importante utilisée dans toute les étapes du processus de reconstruction. Cette projection est dite Homographie. On expliquera le concept d’homographie, ainsi que la méthode classique analytique du calcul de cette projection. Ensuite, on propose une méthode pour résoudre ce problème en utilisant l’optimisation par essaim de particules. Une comparaison est alors effectuée entre les résultats traditionnels et ceux obtenus par notre approche.
— La calibration des caméras est l’étape suivante dans le processus de reconstruction. Dans le cinquième chapitre on explique le procédé de calcul des paramètres de la caméra. Ces paramètres sont utilisé par l’appareil à photo pour capturer l’image (les paramètres intrinsèque, les paramètres extrinsèques). Le chapitre explique essentiellement la méthode présenté par Zhang dans [104]. Des résultats seront inclus.
— Le dernier chapitre est l’utilisation de tout les résultats présentés auparavant pour effectuer la reconstruction 3D de la scène à partir de plusieurs images prises de la même scène.
— On conclu notre travail avec quelques points et observations concernant la reconstruction 3D et les difficultés rencontrés durant ce processus. On propose quelques perspectives qui reste à réaliser dans le future.

Les approches à base de population de solutions “évolutionnaires”

       Elles consistent à travailler avec un ensemble de solutions simultanément, que l’on fait évoluer graduellement. L’utilisation de plusieurs solutions simultanément permet naturellement d’améliorer l’exploration de l’espace des configurations. cette catégorie regroupe :
— Les algorithmes génétiques.
— Les algorithmes par colonies de fourmis.
— L’optimisation par essaim de particules.
— Les algorithmes à estimation de distribution.
— Le path relinking (ou chemin de liaison).
On doit dire que ces métaheuristiques évolutionnaires sont probablement plus gourmandes en calcul, mais on peut dire aussi qu’elles se prêteront bien à leur parallélisation. Certains algorithmes peuvent se ranger dans les deux catégories à la fois, comme la méthode GRASP, qui construit un ensemble de solutions, qu’elle améliore ensuite avec une recherche locale. La plupart des méthodes développées ces dernières années sont d’ailleurs souvent à cheval sur ces deux approches. Une autre manière, plus intuitive, de classifier les métaheuristiques consiste à les séparer celles qui se sont inspirées d’un phénomène naturel appelées Bio-Inspirée, de celles qui ne le sont pas. Les algorithmes génétiques ou les algorithmes de colonies de fourmis entrent clairement dans le bio-inspiré, tandis que la méthode de descente, ou la recherche Tabou, entrent dans la seconde catégorie. On peut également raisonner par rapport à l’usage que font les métaheuristiques de la fonction objectif. Certaines la laissent “telle quelle” d’un bout à l’autre du processus de calcul, tandis que d’autres la modifient en fonction des informations collectées au cours de l’exploration – l’idée étant toujours de “s’échapper” d’un minimum local, pour avoir davantage de chance de trouver l’optimal. La recherche locale guidée est un exemple de métaheuristique qui modifie la fonction objectif. Enfin, il faut distinguer les métaheuristiques qui ont la faculté de mémoriser des informations à mesure que leur recherche avance, de celles qui fonctionnent sans mémoire, en aveugle, et qui peuvent revenir sur des solutions qu’elles ont déjà examinées. On distingue la mémoire à court terme (celles des derniers mouvements effectués), et la mémoire à long terme (qui concerne des paramètres synthétiques plus généraux). Le meilleur représentant des métaheuristiques avec mémoire reste la recherche Tabou. Dans les “sans mémoire”, on trouve le recuit simulé par exemple [8].

La recherche Tabou (Tabu Search)

        La recherche tabou (TS) est une méthode de recherche locale combinée avec un ensemble de techniques permettant d’éviter d’être piègé dans un minimum local ou la répétition d’un cycle. La recherche tabou est introduite principalement par Glover [39], Hansen [48], Glover et Laguna dans [40]. Cette méthode a montré une grande efficacité pour la résolution des problèmes d’optimisation difficiles. En effet, à partir d’une solution initiale s dans un ensemble de solutions local S, des sous-ensembles de solution N(s) appartenant au voisinage S sont générés. Par l’intermédiaire de la fonction d’évaluation nous retenons la solution qui améliore la valeur de f, choisie parmi l’ensemble de solutions voisines N(s). L’algorithme accepte parfois des solutions qui n’améliorent pas toujours la solution courante. Nous mettons en oeuvre une liste tabou (tabu list) T de longueur k contenant les k dernières solutions visitées, ce qui ne donne pas la possibilité a une solution déjà trouvée d’être acceptée et stockée dans la liste tabou. Alors le choix de la prochaine solution est effectué sur un ensemble des solutions voisines en dehors des éléments de cette liste tabou. Quand le nombre k est atteint, chaque nouvelle solution sélectionnée remplace la plus ancienne dans la liste. La construction de la liste tabou est basée sur le principe FIFO, c’est-à-dire le premier entré est le premier sorti. Comme critère d’arrêt on peut par exemple fixer un nombre maximum d’itérations sans amélioration de s*, ou bien fixer un temps limite après lequel la recherche doit s’arrêter [29]. La méthode Tabou est une technique de recherche dont les principe a été proposé pour la première fois par Fred Glover dans les années 80, et est devenue très classique en optimisation combinatoire. Elle se distingue des méthodes de recherche locale simples par le recours à un historique des solutions visitées, de façon à rendre la recherche un peu moins “aveugle”. Il devient donc possible de s’extraire d’un minimum local, mais, pour éviter d’y retomber périodiquement, certaines solutions sont bannies, elles sont rendues “taboues”. A l’inverse du recuit simulé qui génère de manière aléatoire une seule solution voisine à chaque itération, Tabou examine un échantillonnage de solutions de N(s) et retient la meilleure s’ même si f(s’)>f(s). La recherche Tabou ne s’arrête donc pas au premier optimum trouvé. Le danger serait alors de revenir à s immédiatement, puisque s est meilleure que s’. Pour éviter de tourner ainsi en rond, on crée une liste T qui mémorise les dernières solutions visitées et qui interdit tout déplacement vers une solution de cette liste. Cette liste T est appelée liste Tabou [8]. Avantages et inconvénients La méthode Tabou est une méthode de recherche locale, et la structure de son algorithme de base est finalement assez proche de celle du recuit simulé, donc on passe facilement de la première heuristique vers celle ci, avec l’avantage, par rapport au recuit simulé, d’avoir un paramétrage simplifié : dans un première temps, le paramétrage consistera d’abord à trouver une valeur indicative t d’itérations pendant lesquelles les mouvements sont interdits. Il faudra également décider d’une stratégie de mémorisation à long terme – sur la qualité des solutions, sur leur recense, ou sur leur qualité… En revanche, la méthode Tabou exige une gestion de la mémoire de plus en plus lourde à mesure que l’on voudra raffiner le procédé en mettant en place des stratégies de mémorisation complexe. L’efficacité de la méthode Tabou fait qu’elle est largement employée dans les problèmes d’optimisation combinatoire : elle a été testée avec succès sur les grands problèmes classiques (voyageur de commerce, ordonnancement d’ateliers) et elle est fréquemment appliquée sur les problèmes de constitution de planning, de routage, d’exploration géologique, etc [8].

Les colonies de fourmis

       Les algorithmes de colonies de fourmis ont été proposés par Colorni, Dorigo et Maniezzo en 1992 [23] et appliquées la première fois au problème du voyageur de commerce. Ce sont des algorithmes itératifs à population où tous les individus partagent un savoir commun qui leur permet d’orienter leurs futurs choix et d’indiquer aux autres individus des choix à suivre ou à éviter. Le principe de cette métaheuristique repose sur le comportement particulier des fourmis, elles utilisent pour communiquer une substance chimique volatile particulière appelée phéromone grâce à une glande située dans leur abdomen. En quittant leur nid pour explorer leur environnement à la recherche de la nourriture, les fourmis arrivent à élaborer des chemins qui s’avèrent fréquemment être les plus courts pour aller du nid vers une source de nourriture. Chaque fourmi dépose alors une quantité de phéromones sur ces pistes qui deviendront un moyen de communication avec leurs congénères, les fourmis choisissent ainsi avec une probabilité élevée les chemins contenant les plus fortes concentrations de phéromones à l’aide des récepteurs situés dans leurs antennes [29]. La figure 2.5 illustre et confirme ce constat, une expérience a été faite par gauss et deneubourg en 1989 appelée expérience du pont à double branche, les fourmis qui retournent au nid rapidement, après avoir visité la source de nourriture, sont celles qui ont choisi la branche courte et les fourmis empruntant cette branche faisant plus d’aller retour, et par conséquent la quantité de phéromones déposée sur la plus courte branche est relativement supérieure que celle présente sur la plus longue branche. Puisque les fourmis sont attirées plus vers les pistes de plus grande concentration en phéromones, alors la branche courte sera la plus empruntée par la majorité des fourmis. Cette métaheuristique a permis de résoudre différents problèmes d’optimisation combinatoire à forte complexité, comme le problème du voyageur de commerce [28], le problème de coloration de graphe [24], le problème d’affectation quadratique [36] ou le problème de routage de véhicules [73], etc.

Algorithme de colonie d’abeilles artificielles

      Dans l’algorithme ABC, la position d’une source de nourriture représente une solution possible du problème de l’optimisation et la quantité de nectar d’une source alimentaire correspond à la qualité (fitness) de la solution associée. Le nombre des abeilles salariées ou les abeilles spectatrices est égale au nombre de solutions dans la population. À la première étape, l’ABC génère une population initiale distribuée au hasard P(C = 0) de SN solutions (positions de source de nourriture), où SN désigne la taille des abeilles salariés ou abeilles spectatrices. Chaque solution xi(i = 1, 2, …, SN) est un vecteur de dimension D. Ici, D est le nombre de paramètres d’optimisation. Après l’initialisation, la population des positions (solutions) est soumise à des cycles répétés, C = 1, 2, …, MCN, des processus de recherche des abeilles employées, des abeilles spectatrices et des éclaireuses. Une abeille employée produit une modification de la position (solution) dans sa mémoire en fonction de l’information locale (information visuelle) et teste la quantité de nectar (valeur de fitness) de la nouvelle source (nouvelle solution). Si la quantité de nectar de la nouvelle position est plus élevé que celle de la précédente, l’abeille mémorise la nouvelle position et oublie l’ancienne. Sinon, elle maintient la position de la précédente dans sa mémoire. Après que  toutes les abeilles salariés complètent le processus de recherche, elles partagent les informations du nectar des sources de nourriture et leurs informations de position avec les abeilles spectatrices. Une abeille spectatrice évalue les informations du nectar tirées de toutes les abeilles employées et choisit une source de nourriture avec une probabilité liée à son montant de nectar. Comme dans le cas de l’abeille employée, elle produit une modification de la position dans sa mémoire et vérifie la quantité de nectar de la source candidate. Si le nectar est plus élevée que celle de la précédente, l’abeille mémorise la nouvelle position et oublie l’ancienne. L’algorithme 1 résume le comportement des abeilles artificielles décrit ci-dessus.

Table des matières

1 Introduction 
1.1 Problématique
1.2 Motivation
2 Heuristique et Métaheuristique 
2.1 Création et origine
2.2 Classification des métaheuristiques 
2.2.1 Les approches à base de solution unique “trajectoire”
2.2.2 Les approches à base de population de solutions “évolutionnaires”
2.3 Approches trajectoires
2.3.1 Le recuit simulé (simulated annealing)
2.3.2 La recherche Tabou (Tabu Search)
2.3.3 La recherche à voisinage variable
2.4 Approches populations “évolutionnaires” 
2.4.1 Les algorithmes génétiques
2.4.2 Les colonies de fourmis
2.4.3 L’optimisation par colonies d’abeilles
2.4.4 L’optimisation par essaim de particules
3 Stéréovision 
3.1 Géométrie Épipolaire
3.2 La Matrice Fondamentale 
3.2.1 Dérivation Géométrique
3.2.2 Dérivation Algébrique
3.2.3 Représentation algébrique de la géométrie épipolaire – La matrice fondamentale
3.2.4 Condition de Correspondance
3.2.5 Propriétés de la Matrice Fondamentale
3.2.6 Quelques détails sur la matrice fondamentale
3.2.7 L’Homographie de la ligne épipolaire
3.3 Géométrie épipolaire calibrée et matrice essentielle 
3.3.1 La matrice essentielle
3.3.2 Les propriétés de la matrice essentielle
3.4 Estimation de la géométrie épipolaire – Méthode de base
3.4.1 Combien de correspondances faut-il avoir ?
3.5 Rectification des images 
3.5.1 Préliminaires
3.5.2 Projection de l’épipôle à l’infini
3.5.3 La mise en correspondances des transformations
3.5.4 Transformations Quasi affine
3.5.5 Rééchantillonnage
3.6 Expérimentations
4 Homography 
4.1 Définition Générale 
4.2 Description Mathématique
4.3 L’estimation de l’Homography
4.4 Résolution analytique de l’Homographie 
4.5 Résolution de l’Homographie basée sur les essaims de particules
4.5.1 Principe
4.5.2 Première estimation de la matrice H
4.6 Expérimentations 
4.6.1 Application sur des images synthèses
4.6.2 Application sur l’échiquier
4.6.3 Application sur la base de données INRIA
4.6.4 Discussion
4.7 Conclusion 
5 Calibration de Caméra 
5.1 Définition
5.1.1 Calibration Photogrammétrique
5.1.2 Auto-Calibrage
5.2 Modèle de caméra Sténopé
5.3 Équations de base 
5.3.1 Notation
5.3.2 Homographie entre le plan du modèle et son image
5.3.3 Contraintes sur les paramètres intrinsèques
5.4 Résolution du calibrage de caméra
5.4.1 Solution de forme fermée
5.4.2 Extraction des paramètres intrinsèques depuis la matrice B
5.4.3 Estimation du maximum de vraisemblance
5.4.4 Traitement de la distorsion radiale
5.5 Expérimentations
6 Reconstruction 3D 
6.1 Méthodes actives 
6.1.1 Utilisation du Scanner Laser pour la reconstruction
6.2 Méthodes passives 
6.2.1 Méthodes monoculaires
6.2.2 Approches multi-vues
6.2.3 Reconstruction à partir du mouvement
6.3 Reconstruction 3D à partir des caméras non calibrées 
6.4 Reconstruction à partir des caméras calibrées 
6.4.1 Interprétation géométrique des quatre solutions
6.5 Théorème de la reconstruction projective
6.6 Reconstruction stratifié 
6.6.1 L’étape de reconstruction métrique
6.6.2 Reconstruction métrique directe en utilisant ω
6.6.3 La reconstruction directe – en utilisant la réalité de terrain
6.6.4 Expérimentations
Conclusion
Perspectives
Bibliographie

Télécharger le rapport complet