Apprentissage de variétés et applications au traitement de formes et d'images

The amount of data is continuously increasing through online databases such as Flicker1. Not only is the amount of stored data increasing constantly but also the data itself is highly complex. The need for smart algorithms is obvious. Recently, manifold learning has made a strong entry into the computer vision community. This method provides a powerful tool for the analysis of high-dimensional complex data. Manifold learning is based on the assumption that the degrees of freedom of the data are much smaller than the dimension of the data space itself. More specifically, these methods try to recover a submanifold embedded in a high-dimensional space which can even be dimensionally infinite as in the case of shapes. The output of such an algorithm is a mapping into a new space (commonly referred to as feature space) where the analysis of data becomes easier. Often this mapping can be thought of as a parameterization of the dataset. In the first part of this thesis, we introduce the concepts and theory of metric spaces providing the theoretical background to manifold learning. Once the necessary tools are introduced, we will present a survey on linear and non-linear manifold learning algorithms and compare their weak and strong points. In the second part, we will develop two applications using manifold learning techniques. In both applications manifold learning is applied to recover or approximate the metric on the original space data space. In this way distance between points in the original space can be computed using the metric in the feature space. This allows the formulation of distance based optimization problems. In this spirit, we tackle a first problem known under the name of Pre-image problem. We will look at this problem in the context of Kernel PCA and diffusion maps. It turns out, that previous Pre-image methods based on Kernel PCA used a wrong normalization in centred feature space. We propose a more subtle normalization improving previously proposed algorithm for the computation of the Pre-image. We then look at the same problem in the context of diGrâce aux bases de données en ligne, le volume de données ne cesse d accroitre. Non seulement la quantité de donnes augmente mais aussi la complexité des donnes est hautement complexe. Ce fait nécessite le développement d algorithmes performants. Récemment, une nouvelle classe de méthodes connue sous le nom de: "apprentissage de variétés" a été introduite. Ces méthodes présentent un formalisme intéressant et performant pour l analyse de données à très haute dimension. Ces méthode assument que les degrés de liberté dans les données sont bien plus petit que la dimension de l espace des données. Le but de ces algorithmes est retrouve une variété plongée dans un espace à haute dimension (voire infinie). La sortie d un tel algorithme est une fonction transformant les données dans un espace (espace de feature) où l'analyse devient plus facile. Souvent cette fonction est considère comme une para métrisation de la variété. Dans la première partie de ce manuscrit, nous allons introduire les idées principales ainsi que la théorie des espaces métriques. Ceci nous fournira les outils de bases pour les méthodes d'apprentissage de variétés. Par la suite nous présenterons des méthodes linéaires et non- linéaires pour l'apprentissage de variétés et analyserons leurs points forts et faibles. La deuxième partie développera deux applications en utilisant l'apprentissage des variétés. Dans les deux cas l'apprentissage de variétés est appliqué pour approximer le métrique dans l espace initiale. Ainsi la distance entre points dans l'espace originale peut être approximé en utilisant la métrique dans l'espace feature. Ainsi nous pouvant résoudre des problèmes d optimisation basée sur les distances entre points. Dans cette idée nous regardons le premier problème connu sous le nom "problème de la pré-image". Nous analyserons ce problème dans le contexte de la ACP a noyau and la technique des d