Nous abordons le problème de la mise en correspondance de points dans des images pour calculer la pose d'une caméra par l'algorithme Perspective-n-Point (PnP). Nous calculons la carte 3D, c'est-à-dire les coordonnées 3D et les caractéristiques visuelles de quelques points dans l'environnement grâce à une procédure d'apprentissage hors ligne utilisant un ensemble d'images d'apprentissage. Étant donné une nouvelle image nous utilisons PnP à partir des coordonnées 2D dans l'image de points 3D détectés à l'aide de la carte 3D. Pendant la phase d'apprentissage nous groupons les descripteurs SIFT extraits des images d'apprentissage pour obtenir des collections de positions 2D dans ces images de quelques-uns des points 3D dans l'environnement. Le calcul de SFM (Structure From Motion) est effectué pour obtenir les coordonnées des points correspondants 3D. Pendant la phase de test, les descripteurs SIFT associés aux points 2D projection d'un point 3D de la carte sont utilisés pour reconnaître le point 3D dans une image donnée. Le cadre de travail est semblable à celui des mots visuels utilisés dans différents domaines de la vision par ordinateur. Pendant l'apprentissage, la formation des mots visuelle est effectuée via l'identification de groupes et pendant les tests des points 3D sont identifiés grâce à la reconnaissance des mots visuels. Nous menons des expériences avec des méthodes de formation différentes (k-means et mean-shift) et proposons un nouveau schéma pour la formation des mots visuels pour la phase d'apprentissage. Nous utilisons différentes règles de mise en correspondance, y compris quelques-unes des méthodes standards de classification supervisée pour effectuer la reconnaissance des mots visuels pendant la phase de test. Nous évaluons ces différentes stratégies dans les deux étapes. Afin d'assurer la robustesse aux variations de pose entre images d'apprentissage et images de test, nous explorons différentes façons d'intégrer les descripteurs SIFT extraits de vues synthétiques générées à partir des images d'apprentissage. Nous proposons également une stratégie d'accélération exacte pour l'algorithme mean-shift / We address the problem of establishing point correspondences in images for computing camera pose through Perspective-n-Point (PnP) algorithm. We compute the 3D map i.e. 3D coordinates and visual characteristics of some of the points in the environment through an offline training stage using a set of training images. Given a new test image we apply PnP using the 2D coordinates of 3D points in the image detected by using the 3D map. During the training stage we cluster the SIFT descriptors extracted from training images to obtain 2D-tracks of some of the 3D points in the environment. Each 2D-track consists of a set of 2D image coordinates of a single 3D point in different training images. SfM (Structure from Motion) is performed on these 2D-tracks to obtain the coordinates of the corresponding 3D points. During the test stage, the SIFT descriptors associated the 2D-track of a 3D point is used to recognize the 3D point in a given image. The overall process is similar to visual word framework used in different fields of computer vision. During training, visual word formation is performed through clustering and during testing 3D points are identified through visual word recognition. We experiment with different clustering schemes (k-means and mean-shift) and propose a novel scheme for visual word formation for training stage. We use different matching rules including some of the popular supervised pattern classification methods to perform visual word recognition during test stage. We evaluate these various matching strategies in both stages. In order to achieve robustness against pose variation between train and test images, we explore different ways of incorporating SIFT descriptors extracted from synthetic views generated from the training images. We also propose an exact acceleration strategy for mean-shift computation

La localisation est un problème récurrent de la vision par ordinateur, avec des applications dans des domaines multiples tels que la robotique ou la réalité augmentée. Dans cette thèse on considère en particulier le problème d'initialisation de la pose, c'est-à-dire la localisation sans information a priori sur la position de la caméra. Nous nous intéressons à la localisation à partir d'une image monoculaire et d'un nuage de points reconstruit à partir d'une séquence d'images. Puisque nous n'avons pas d'a priori sur la position de la caméra, l'estimation de la pose s'appuie sur la recherche de correspondances entre des points de l'image et des points du modèle de la scène. Cette mise en correspondance est difficile en raison de sa combinatoire élevée. Elle peut être mise en défaut lorsque l'image dont on cherche la pose est très différente de celles ayant servi à la construction du modèle, en particulier en présence de forts changements de point de vue. Cette thèse développe une approche permettant la mise en correspondance image-modèle dans ces situations complexes. Elle consiste à synthétiser localement l'apparence de la scène à partir de points de vue virtuels puis à ajouter au modèle des descripteurs extraits des images synthétisées. Comme le modèle de scène est un nuage de points, la synthèse n'est pas faite par rendu 3D mais utilise des transformations 2D locales des observations connues de la scène. Les contributions suivantes sont apportées. Nous étudions différents modèles de transformation possibles et montrons que la synthèse par homographie est la plus adaptée pour ce type d'application. Nous définissons une méthode de positionnement des points de vue virtuels par rapport à une segmentation de la scène en patchs plans. Nous assurons l'efficacité de l'approche proposée en ne synthétisant que des vues utiles : elles sont éloignées de celles existantes et elles ne se recouvrent pas. Nous vérifions également que la scène est visible à partir des points des vue virtuels pour ne pas produire des vues aberrantes à cause d’occultations. Enfin, nous proposons une méthode de recherche de correspondances image-modèle qui est à la fois rapide et robuste. Cette méthode exploite la répartition non-uniforme des correspondances correctes dans le modèle, ce qui permet de guider leur recherche. Les résultats expérimentaux montrent que la méthode proposée permet de calculer des poses dans des configurations défavorables où les approches standard échouent. De façon générale la précision des poses obtenues augmente significativement lorsque la synthèse de vue est utilisée. Enfin nous montrons que, en facilitant la mise en correspondance image-modèle, cette méthode accélère le calcul de pose / Localisation is a central problem of computer vision which has numerous applications such as robotics or augmented reality. In this thesis we consider the problem of pose initialisation, which is pose computation without prior knowledge on the camera position. We are interested in pose computation from a single image and a point cloud that has been reconstructed from a set of images. As we do not have prior knowledge on the camera position, pose estimation entirely rely on finding correspondences between the image and the model. The search for these correspondences is a difficult problem because of its high combinatorial complexity. It can fail if the image is very different from the ones we used to construct the model, in particular when there is a large viewpoint change between them. This thesis proposes an approach to make matching possible in such difficult scenarios. It consists in synthesising locally the appearance of the scene from virtual viewpoints and add descriptors extracted from these synthetic views to the model. Because the scene model is a point cloud, the synthesis is not a 3D rendering but a local 2D transform of existing observations of the scene. The following contributions have been proposed. We study different transform models and show that homographic transformations are the best suited for this application. We define a method to position the virtual viewpoints with respect to a planar segmentation of the scene model. We ensure time efficiency by only synthesising useful views, i.e. views that are far from the existing one and don't overlap. Furthermore we verify that the synthesized surface is visible from the virtual viewpoint to avoid producing aberrant views due to occlusions. Finally, we propose a robust and time efficient method to research image-model correspondences. It uses geometric cues in a guided matching framework to efficiently identify sets of correct correspondences. Experimental results show that the proposed approach makes possible pose computation in situation where standard methods fail. In general the precision and repeatability of computed poses is significantly improved by the use of view synthesis. We also show that it also reduce the pose computation times by making image-model matching easier

En informatique, la vision par ordinateur s’attache à extraire de l’information à partir de caméras. Les capteurs de celles-ci peuvent être produits avec la technologie CMOS que nous retrouvons dans les appareils mobiles en raison de son faible coût et d’un encombrement réduit. Cette technologie permet d’acquérir rapidement l’image en exposant les lignes de l’image de manière séquentielle. Cependant cette méthode produit des déformations dans l’image s’il existe un mouvement entre la caméra et la scène filmée. Cet effet est connu sous le nom de «Rolling Shutter» et de nombreuses méthodes ont tenté de corriger ces artefacts. Plutôt que de le corriger, des travaux antérieurs ont développé des méthodes pour extraire de l’information sur le mouvement à partir de cet effet. Ces méthodes reposent sur une extension de la modélisation géométrique classique des caméras pour prendre en compte l’acquisition séquentielle et le mouvement entre le capteur et la scène, considéré uniforme. À partir de cette modélisation, il est possible d’étendre le calcul de pose habituel (estimation de la position et de l’orientation de la scène par rapport au capteur) pour estimer aussi les paramètres du mouvement. Dans la continuité de cette démarche, nous présenterons une généralisation à des mouvements non-uniformes basée sur un lissage des dérivées des paramètres de mouvement. Ensuite nous présenterons une modélisation polynomiale du «Rolling Shutter» et une méthode d’optimisation globale pour l’estimation de ces paramètres. Correctement implémenté, cela permet de réaliser une mise en correspondance automatique entre le modèle tridimensionnel et l’image. Pour terminer nous comparerons ces différentes méthodes tant sur des données simulées que sur des données réelles et conclurons. / Computer Vision, a field of Computer Science, is about extracting information from cameras. Their sensors can be produced using the CMOS technology which is widely used on mobile devices due to its low cost and volume. This technology allows a fast acquisition of an image by sequentially exposin the scan-line. However this method produces some deformation in the image if there is a motion between the camera and the filmed scene. This effect is known as Rolling Shutter and various methods have tried to remove these artifacts. Instead of correcting it, previous works have shown methods to extract information on the motion from this effect. These methods rely on a extension of the usual geometrical model of cameras by taking into account the sequential acquisition and the motion, supposed uniform, between the sensor and the scene. From this model, it’s possible to extend the usual pose estimation (estimation of position and orientation of the camera in the scene) to also estimate the motion parameters. Following on from this approach, we will present an extension to non-uniform motions based on a smoothing of the derivatives of the motion parameters. Afterwards, we will present a polynomial model of the Rolling Shutter and a global optimisation method to estimate the motion parameters. Well implemented, this enables to establish an automatic matching between the 3D model and the image. We will conclude with a comparison of all these methods using either simulated or real data.

Dans le cadre de cette thèse, nous proposons un algorithme générique permettant de résoudre le problème de calcul de pose et le problème de reconstruction avec un modèle perspectif de caméra. Étant donnés une image et un modèle 3D de la scène (ou objet) visible dans l'image, le calcul de pose consiste à calculer la position et l'orientation de la caméra par rapport à la scène. Nous étudions successivement le cas de correspondances 2D 3D de points, et le cas des droites. La méthode proposée améliore de manière itérative la pose calculée avec un modèle affine de caméra (orthographique à l'échelle ou paraperspectif) pour converger, à la limite, vers une estimation de la pose calculée avec un modèle perspectif de caméra. Nous étudions les relations mathématiques et géométriques existant entre les modèles orthographique à l'échelle, paraperspectif et perspectif de caméra. Nous introduisons une façon simple de prendre en compte la contrainte d'orthogonalité associée à une matrice de rotation. Nous analysons la sensibilité de la méthode par rapport aux erreurs d'étalonnage de la caméra et nous définissons les conditions expérimentales optimales par rapport à un étalonnage imprécis. Nous étudions la convergence de la méthode sur la base de considérations numériques et expérimentales et nous testons son efficacité avec des données synthétiques et réelles. Dans un second temps, nous étendons les algorithmes de calcul de pose précédents au problème de la reconstruction euclidienne avec un modèle perspectif de caméra, à partir d'une séquence d'images. La méthode proposée converge en quelques itérations, est efficace du point de vue calculatoire, et ne souffre pas de la nature non linéaire du problème traité. Comparativement à des méthodes telles que la factorisation ou les invariants affines, notre méthode résout le problème de l'ambiguïté de signe d'une façon très simple et fournit des résultats bien plus précis. Nous décrivons la nouvelle méthode en détail, et comparons la complexité de la méthode proposée avec une méthode de minimisation non linéaire. Nous présentons ensuite une seconde approche du problème de reconstruction euclidienne en considérant un modèle affine de caméra non étalonnée montée sur le bras d'un robot. Nous montrons comment utiliser l'information euclidienne fournie par le déplacement du robot afin d'obtenir une reconstruction euclidienne, et expliquons comment obtenir l'étalonnage du modèle affine de caméra ainsi que l'étalonnage caméra-pince. Afin de pouvoir utiliser en pratique ces algorithmes de reconstruction, nous présentons une méthode de poursuite de points caractéristiques sur une séquence monoculaire d'images, puis sur une séquence stéréoscopique. Nous proposons également une méthode pour obtenir une précision sous-pixellique des positions des points dans les images pour un faible coût calculatoire.