Tesis sobre el tema "Recherche du plus proche voisin"

La classification non supervisée a pour objectif de définir dans un ensemble de données des classes permettant de caractériser la structure interne des données. C’est une technique très utile dans de nombreux domaines technologiques comme en diagnostic des systèmes complexes (pour la mise en évidence de modes de fonctionnement) et en vision par ordinateur (pour la segmentation d'image). Les méthodes traditionnelles de la classification non supervisée présentent plusieurs problèmes en pratique, par exemple, la nécessité de préfixer le nombre de classes, le manque de stratégie appropriée pour le réglage de paramètres et la difficulté de valider le résultat obtenu. Dans cette thèse nous tentons d'apporter une solution à ces problèmes en développant une nouvelle approche basée sur la notion des K plus proches voisins. Alliant la détection de mode et la recherche de graphe reflétant la proximité des données, cette approche identifie d'abord les centres de classe, puis construit une classe autour de chaque centre. Elle n'emploie aucune connaissance a priori sur les données et ne possède qu'un seul paramètre. Une stratégie de réglage de ce paramètre a été établie après une étude théorique et une analyse expérimentale. L’idée est de rechercher la stabilité du résultat de classification. Des tests présentés dans ce mémoire montrent une bonne performance de l'approche proposée ; elle est libre d'hypothèse sur la nature des données, relativement robuste et facile à utiliser

Les codes correcteurs d'erreurs sont des outils ayant pour fonction originale de corriger les erreurs produites par des canaux de communication imparfaits. Dans un contexte non coopératif, se pose le problème de reconnaître des codes inconnus à partir de la seule connaissance de mots de code bruités. Ce problème peut s'avérer difficile pour certaines familles de codes, notamment pour les codes LDPC qui sont très présents dans nos systèmes de télécommunication modernes. Dans cette thèse, nous proposons de nouvelles techniques pour reconnaître plus facilement ces codes. À la fin des années 70, McEliece eu l'idée de détourner la fonction première des codes pour les utiliser dans des chiffrements, initiant ainsi une famille de solutions cryptographiques alternative à celle fondée sur la théorie des nombres. Un des avantages de la cryptographie fondée sur les codes est qu'elle semble résister au paradigme de calcul quantique ; notamment grâce à la robustesse du problème de décodage générique. Ce dernier a été profondément étudié ces 60 dernières années. Les dernières améliorations utilisent toutes des algorithmes de recherche de couples de points proches dans une liste. Dans cette thèse, nous améliorons le décodage générique en proposant notamment une nouvelle façon de rechercher des couples proches. Notre méthode repose sur l'utilisation de décodages en liste de codes polaires pour construire des fonctions de hachage floues. Dans ce manuscrit, nous traitons également la recherche de couples de points éloignés. Notre solution peut être utilisée pour améliorer le décodage en grandes distances qui a récemment trouvé des applications dans des designs de signature
Error correcting codes are tools whose initial function is to correct errors caused by imperfect communication channels. In a non-cooperative context, there is the problem of identifying unknown codes based solely on knowledge of noisy codewords. This problem can be difficult for certain code families, in particular LDPC codes which are very common in modern telecommunication systems. In this thesis, we propose new techniques to more easily recognize these codes. At the end of the 1970s, McEliece had the idea of ​​redirecting the original function of codes to use in ciphers; thus initiating a family of cryptographic solutions which is an alternative to those based on number theory problems. One of the advantages of code-based cryptography is that it seems to withstand the quantum computing paradigm; notably thanks to the robustness of the generic decoding problem. The latter has been thoroughly studied for more than 60 years. The latest improvements all rely on using algorithms for finding pairs of points that are close to each other in a list. This is the so called near-collisions search problem. In this thesis, we improve the generic decoding by asking in particular for a new way to find close pairs. To do this, we use list decoding of Arikan's polar codes to build new fuzzy hashing functions. In this manuscript, we also deal with the search for pairs of far points. Our solution can be used to improve decoding over long distances. This new type of decoding finds very recent applications in certain signature models

Les travaux présentés dans cette thèse ont porté sur l'étude de faisabilité technique et logicielle du système i-GUIDE, système interactif de guidage des personnes dans les hypermarchés. Nous avons détaillé l'analyse fonctionnelle du besoin du système. Ensuite, nous avons étudié l'impact de l'intégration du système dans le magasin à travers le diagramme BPMN. Nous avons opté pour l'approche UML pour décrire les principales fonctionnalités de notre système ainsi que les objets nécessaires pour son bon fonctionnement. Une architecture du système i-GUIDE, basée sur la technologie RFID avec une application sous Android, a été présentée. Par ailleurs, nous avons proposé des approches d'optimisation de parcours dans un hypermarché basées sur la méthode de recherche tabou pour deux problèmes. Pour le premier problème, nous avons choisi le critère de la plus courte distance pour la détermination du chemin et pour le deuxième nous avons ajouté une contrainte de temps pour des articles en promotion. Avant de chercher le chemin le plus court à parcourir pour trouver les articles existants dans la liste de courses, nous avons proposé une méthode pour ladétermination des distances entre les articles de l'hypermarché pris deux à deux

Les tailles des bases d’images ont connu une croissance rapide. Elles peuvent se chiffrer actuellement en millions d’objets ce qui nécessite l’utilisation d’un système de recherche d’images par le contenu. Un tel système consiste tout d’abord en la description automatique des images de la base. Les propriétés visuelles de chaque image sont représentées sous forme de vecteurs multidimensionnels appelés descripteurs. Ensuite, trouver les images similaires à une image requête revient à chercher pour chaque descripteur de l’image requête les descripteurs les plus proches. Dans ce travail de thèse nous proposons une nouvelle méthode d’indexation de bases multidimensionnelles avec une évolution de l’algorithme de recherche de plus proches voisins. L’originalité de notre index multidimensionnel est la création de formes englobantes évitant le chevauchement. En effet, le chevauchement est l’un des principaux inconvénients qui ralentissent la recherche de plus proches voisins. Le nouvel index créé et son algorithme de recherche spécifique permettent d’accélérer la recherche de plus proches voisins tout en effectuant une recherche à l’exact. La méthode que nous avons conçue a été intégrée et évaluée dans un système réel de recherche d’images par le contenu. Les résultats des expérimentations effectuées montrent sa robustesse en termes de précision et de rapidité en temps de recherche
The increasing of image databases requires the use of a content-based image retrieval system (CBIR). A such system consist first to describe automatically the images, visual properties of each image are represented as multidimensional vectors called descriptors. Next, finding similar images to the query image is achieved by searching for the nearest neighbors of each descriptor of the query image. In this thesis, we propose a new method for indexing multidimensional bases with the search algorithm of nearest neighbors adapted. The originality of our multidimensional index is the disposition of the bounding forms avoiding overlapping. Indeed, the overlapping is one of the main drawbacks that slow the search of nearest neighbors search. Our index with its search algorithm speeds the nearest neighbors search while doing an exact search. Our method has been integrated and tested within a real content-based image system. The results of tests carried out show the robustness of our method in terms of accuracy and speed in search time

Cette thèse s'intéresse aux systèmes de recherche d'images par le contenu, où le but est de rechercher les images les plus similaires à une image requête fournie en exemple. Pour cela, il est d'abord nécessaire de décrire les images stockées dans la base. L'objectif est de traduire la similarité visuelle entre images en une simple notion de proximité spatiale entre descripteurs. Ainsi, pour retrouver les images similaires à l'image requête, il suffit de retrouver les descripteurs les plus proches du descripteur de l'image requête. Ce mode de recherche, appelé recherche de plus proches voisins, est cependant extrêmement coûteux même lorsque les techniques s'indexation multidimensionnelles sont utilisées. Les performances de celles-ci se dégradent exponentiellement lorsque la dimension des descripteurs augmente (phénomène de la malédiction de la dimension). Il s'avère toutefois que l'on peut fortement réduire le coût de ces recherches en effectuant des recherches approximatives. Le principe est alors de négocier une réduction du temps de réponse contre l'introduction d'imprécisions durant la recherche. Ce travail reprend ce principe et propose une nouvelle méthode de recherche approximative de plus proches voisins qui permet un contrôle fin et intuitif de la précision de la recherche. Ce contrôle s'exprime au travers d'un seul paramètre qui indique la probabilité maximale de ne pas trouver un des plus proches voisins recherchés. Dans le but d'évaluer rigoureusement ses performances dans le cadre d'un système réel, la méthode proposée a été ensuite intégrée dans un système de recherche d'images pour la détection de copies. Les expérimentations effectuées montrent que la méthode proposée est efficace, fiable et son imprécision n'a qu'un impact mineur sur la qualité des résultats finaux.

Dans la premiere partie de cette thèse, nous nous intéressons à la recherche rapide de plus proches voisins de descripteurs locaux d'images. Nous nous sommes concentrés sur la recherche de descripteurs SIFT en raison de leur efficacité. Nous appliquons nos résultats à la recherche d'images similaires, notamment dans des grandes bases. Nous comparons d'abord les performances de la recherche linéaire sur CPU et sur GPU (processeurs des cartes graphiques), ainsi que les résultats obtenus en utilisant une distance partielle. Ensuite, nous proposons un algorithme de recherche approximative des voisins. L'algorithme proposé est basé sur des fonctions de hachage qui construisent des clés de hachage à partir d'un sous ensemble de dimensions de l'espace, sélectionné pour chaque point. Pour la recherche d'images similaires, cet algorithme s'avère être plus performant que les algorithmes de l'etal de l'art. Nous montrons l'efficacite de cet algorithme en l'utilisant pour chercher des images similaires dans une base de 500. 000 images, avec des requêtes effectuées en moins de 300 ms. Enfin, nous montrons que cet algorithme s'adapte tout à fait à un cadre « Bag-Of-Features » et qu'il est plus performant, sur des bases d'images similaires, que des vocabulaires k-means. Dans une seconde partie, nous concentrons nos travaux sur la reconstruction 3D à partir de plusieurs images. Nous proposons une méthode pour reconstruire de manière robuste une voiture en 3D a partir d'une acquisition vidéo. Le système proposé fait l'hypothèse que les voitures sont en translation rectiligne pour ensuite reconstruire le vehicule filmé par extrusion de polynômes. Enfin, nous introduisons un algorithme de reconstruction 3D multi-vues qui utilise les descripteurs SIFT pour trouver des correspondances entre des images de l'objet et des rendus virtuels de l'objet temporaire en cours de reconstruction. Cette méthode permet de faire converger une surface 3D vers la surface réelle de l'objet
In the first part of this thesis, we are concerned by the nearest neighbour problem, applied on local image descriptors. We restricted ourselves to the SIFT descriptors because of its efficiency. The application of this work is the retrieval of similar images in large databases. First, we compare performances of linear search, on CPU and on GPU (graphic processors), and also when using partial distances. Then, we propose new hash functions t solve the approximate nearest neighbours problem. The hash functions we propose are based on a selection of a few distinctive dimensions per point. For the application of near duplicate retrieval, our algorithm is more efficient than state-of-the-art algorithms. Tested on a database containing 500. 000 images, it finds similar images in less than 300ms. Eventually, we show that it fits very simply within a Bag-Of-Features approach, and it retrieves mor images than kmeans based vocabularies. In a second part, we propose several results on the problem of multi-view 3D reconstruction. We first propose a robust method to obtain the 3D reconstruction of a car from a video sequence. Our system uses the hypothesis that the car is in linear translation in order to fit a point cloud with polynomial surfaces. Then, we propose an algorithm, not dedicated to cars, that uses SIFT descriptors to obtain the 3D surface from images of an object. The descriptors correspondences are searched between input images and virtual images of the temporary object. With this method, the reconstructed surface converges to the true surface object

Les travaux présentés dans cette thèse ont porté sur l’étude de faisabilité technique et logicielle du système i-GUIDE, système interactif de guidage des personnes dans les hypermarchés. Nous avons détaillé l’analyse fonctionnelle du besoin du système. Ensuite, nous avons étudié l’impact de l’intégration du système dans le magasin à travers le diagramme BPMN. Nous avons opté pour l’approche UML pour décrire les principales fonctionnalités de notre système ainsi que les objets nécessaires pour son bon fonctionnement. Une architecture du système i-GUIDE, basée sur la technologie RFID avec une application sous Android, a été présentée. Par ailleurs, nous avons proposé des approches d’optimisation de parcours dans un hypermarché basées sur la méthode de recherche tabou pour deux problèmes. Pour le premier problème, nous avons choisi le critère de la plus courte distance pour la détermination du chemin et pour le deuxième nous avons ajouté une contrainte de temps pour des articles en promotion. Avant de chercher le chemin le plus court à parcourir pour trouver les articles existants dans la liste de courses, nous avons proposé une méthode pour ladétermination des distances entre les articles de l’hypermarché pris deux à deux
The present work focuses on the technical feasibility study of i-GUIDE system which is a real time indoor navigation system dedicated to assist persons inside hypermarkets. We detailed its functional analysis. Then, we studied the impact of integrating the system inside hypermarkets. We opted for an UML design to describe its main functionalities and objects required. We presented architecture of i-GUIDE system based on RFID technology with an Android application. Furthermore, we introduced optimization approaches based on tabu search to compute the route visiting items existing in a shopping list for two problems. The first one treats the shortest path to pick up items and the second one adds a time constraint for promotional items. Before computing the shortest path, we introduced a method to determine distance between each two items existing in the hypermarket

L’évolution du web, de ce qui était typiquement connu comme un moyen de communication à sens unique en mode conversationnel, a radicalement changé notre manière de traiter l’information. Des sites de médias sociaux tels que Flickr et Facebook, offrent des espaces d’échange et de diffusion de l’information. Une information de plus en plus riche, mais aussi personnelle, et qui s’organise, le plus souvent, autour d’événements de la vie réelle. Ainsi, un événement peut être perçu comme un ensemble de vues personnelles et locales, capturées par différents utilisateurs. Identifier ces différentes instances permettrait, dès lors, de reconstituer une vue globale de l’événement. Plus particulièrement, lier différentes instances d’un même événement profiterait à bon nombre d’applications tel que la recherche, la navigation ou encore le filtrage et la suggestion de contenus. L’objectif principal de cette thèse est l’identification du contenu multimédia, associé à un événement dans de grandes collections d’images. Une première contribution est une méthode de recherche d’événements basée sur le contenu visuel. La deuxième contribution est une approche scalable et distribuée pour la construction de graphes des K plus proches voisins. La troisième contribution est une méthode collaborative pour la sélection de contenu pertinent. Plus particulièrement, nous nous intéresserons aux problèmes de génération automatique de résumés d’événements et suggestion de contenus dans les médias sociaux
The ease of publishing content on social media sites brings to the Web an ever increasing amount of user generated content captured during, and associated with, real life events. Social media documents shared by users often reflect their personal experience of the event. Hence, an event can be seen as a set of personal and local views, recorded by different users. These event records are likely to exhibit similar facets of the event but also specific aspects. By linking different records of the same event occurrence we can enable rich search and browsing of social media events content. Specifically, linking all the occurrences of the same event would provide a general overview of the event. In this dissertation we present a content-based approach for leveraging the wealth of social media documents available on the Web for event identification and characterization. To match event occurrences in social media, we develop a new visual-based method for retrieving events in huge photocollections, typically in the context of User Generated Content. The main contributions of the thesis are the following : (1) a new visual-based method for retrieving events in photo collections, (2) a scalable and distributed framework for Nearest Neighbors Graph construction for high dimensional data, (3) a collaborative content-based filtering technique for selecting relevant social media documents for a given event

Notre travail est consacré à la méthode des plus proches voisins, en tant qu'outil d'analyse de la dispersion spatiale, et à sa généralisation multidimensionnelle. Analyser la dispersion d'individus placés dans un domaine-plan est un problème classique des biologistes, des géographes, des économistes ou de l'analyse d'image. Pour ce faire, la méthode des plus proches voisins utilise un échantillon de distances entre un point pris au hasard dans le plan et le plus proche individu d'ordre k. Le modèle de référence est le modèle au hasard, dont le rejet peut se faire en direction d'un modèle régulier, ou d'un modèle agrégatif (agrégativité vraie ou hétérogénéité). A la suite d'une introduction qui formalise la notion de dispersion spatiale, nous étudions les statistiques de distances sous les hypothèses de dispersion évoquées. Le problème du choix de la taille des agrégats, lors de la construction du modèle d'agrégativité vraie, nous a amené à construire un modèle général de loi discrète, fondé sur la notion de loi récurrente, qui intègre les lois usuelles, et qui soit stable par translation et troncature. Puis nous nous intéressons à la mise en oeuvre de la méthode, de la constitution d'un échantillon de distances, aux procédures de test et d'estimation. Enfin, nous procédons à la généralisation multi dimensionnelle des résultats obtenus, et nous abordons divers problèmes, tels que la prise en compte exacte des effets des bords du domaine, ou le recours à une métrique de Minkowski. Nous montrons alors l'intérêt de nos résultats pour la méthode des plus proches voisins utilisée en classification, avec les plus proches voisins réciproques, et en reconnaissance des formes, à travers l'étude de la complexité des algorithmes de recherche de plus proches voisins

Cette thèse est consacrée à l'étude de la quantification optimale et ses applications. Nous y abordons des aspects théoriques, algorithmiques et numériques. Elle comporte cinq chapitres. Dans la première partie, nous étudions liens entre la réduction de variance par stratification et la quantification optimale. Dans le cas ou la variable aléatoire considérée est un processus Gaussien, un schéma de simulation de complexité linéaire est développé pour la loi conditionnelle à une strate du processus en question. Le second chapitre est consacré à l'évaluation numérique de la base de Karhunen-Loève d'un processus Gaussien par la méthode de Nyström. Dans la troisième partie, nous proposons une nouvelle approche de la quantification de solutions d'EDS, dont nous étudions la convergence. Ces résultats conduisent à un nouveau schéma de cubature pour les solutions d'équations différentielles stochastiques, qui est développé dans le quatrième chapitre, et que nous éprouvons sur des problèmes de valorisation d'options. Dans le cinquième chapitre, nous présentons un nouvel algorithme de recherche rapide de plus proche voisin par arbre, basé sur la quantification de la loi empirique du nuage de points considéré.

L’évolution du web, de ce qui était typiquement connu comme un moyen de communication à sens unique en mode conversationnel, a radicalement changé notre manière de traiter l’information. Des sites de médias sociaux tels que Flickr et Facebook, offrent des espaces d’échange et de diffusion de l’information. Une information de plus en plus riche, mais aussi personnelle, et qui s’organise, le plus souvent, autour d’événements de la vie réelle. Ainsi, un événement peut être perçu comme un ensemble de vues personnelles et locales, capturées par différents utilisateurs. Identifier ces différentes instances permettrait, dès lors, de reconstituer une vue globale de l’événement. Plus particulièrement, lier différentes instances d’un même événement profiterait à bon nombre d’applications tel que la recherche, la navigation ou encore le filtrage et la suggestion de contenus. L’objectif principal de cette thèse est l’identification du contenu multimédia, associé à un événement dans de grandes collections d’images. Une première contribution est une méthode de recherche d’événements basée sur le contenu visuel. La deuxième contribution est une approche scalable et distribuée pour la construction de graphes des K plus proches voisins. La troisième contribution est une méthode collaborative pour la sélection de contenu pertinent. Plus particulièrement, nous nous intéresserons aux problèmes de génération automatique de résumés d’événements et suggestion de contenus dans les médias sociaux
The ease of publishing content on social media sites brings to the Web an ever increasing amount of user generated content captured during, and associated with, real life events. Social media documents shared by users often reflect their personal experience of the event. Hence, an event can be seen as a set of personal and local views, recorded by different users. These event records are likely to exhibit similar facets of the event but also specific aspects. By linking different records of the same event occurrence we can enable rich search and browsing of social media events content. Specifically, linking all the occurrences of the same event would provide a general overview of the event. In this dissertation we present a content-based approach for leveraging the wealth of social media documents available on the Web for event identification and characterization. To match event occurrences in social media, we develop a new visual-based method for retrieving events in huge photocollections, typically in the context of User Generated Content. The main contributions of the thesis are the following : (1) a new visual-based method for retrieving events in photo collections, (2) a scalable and distributed framework for Nearest Neighbors Graph construction for high dimensional data, (3) a collaborative content-based filtering technique for selecting relevant social media documents for a given event

Cette thèse aborde le problème de la recherche d'images à grande échelle. Pour aborder la recherche d'images à grande échelle, il est nécessaire de coder des images avec des représentations compactes qui peuvent être efficacement utilisées pour comparer des images de manière significative. L'obtention d'une telle représentation compacte peut se faire soit en comprimant des représentations efficaces de grande dimension, soit en apprenant des représentations compactes de bout en bout. Le travail de cette thèse explore et avance dans ces deux directions. Dans notre première contribution, nous étendons les approches de quantification vectorielle structurée telles que la quantification de produit en proposant une représentation somme pondérée de codewords. Nous testons et vérifions les avantages de notre approche pour la recherche approximative du plus proche voisin sur les caractéristiques d'image locales et globales, ce qui est un moyen important d'aborder la recherche d'images à grande échelle. L'apprentissage de la représentation compacte pour la recherche d'images a récemment attiré beaucoup d'attention avec diverses approches basées sur le hachage profond proposées. Dans de telles approches, les réseaux de neurones convolutifs profonds apprennent à coder des images en codes binaires compacts. Dans cette thèse, nous proposons une approche d'apprentissage supervisé profond pour la représentation binaire structurée qui rappelle une approche de quantification vectorielle structurée telle que PQ. Notre approche bénéficie de la recherche asymétrique par rapport aux approches de hachage profond et apporte une nette amélioration de la précision de la recherche au même débit binaire. L'index inversé est une autre partie importante du système de recherche à grande échelle en dehors de la représentation compacte. À cette fin, nous étendons nos idées pour l'apprentissage de la représentation compacte supervisée pour la construction d'index inversés. Dans ce travail, nous abordons l'indexation inversée avec un apprentissage approfondi supervisé et essayons d'unifier l'apprentissage de l'indice inversé et de la représentation compacte. Nous évaluons minutieusement toutes les méthodes proposées sur divers ensembles de données accessibles au public. Nos méthodes surpassent ou sont compétitives avec l'état de l'art
This thesis addresses the problem of large-scale image search. To tackle image search at large scale, it is required to encode images with compact representations which can be efficiently employed to compare images meaningfully. Obtaining such compact representation can be done either by compressing effective high dimensional representations or by learning compact representations in an end-to-end manner. The work in this thesis explores and advances in both of these directions. In our first contribution, we extend structured vector quantization approaches such as Product Quantization by proposing a weighted codeword sum representation. We test and verify the benefits of our approach for approximate nearest neighbor search on local and global image features which is an important way to approach large scale image search. Learning compact representation for image search recently got a lot of attention with various deep hashing based approaches being proposed. In such approaches, deep convolutional neural networks are learned to encode images into compact binary codes. In this thesis we propose a deep supervised learning approach for structured binary representation which is a reminiscent of structured vector quantization approaches such as PQ. Our approach benefits from asymmetric search over deep hashing approaches and gives a clear improvement for search accuracy at the same bit-rate. Inverted index is another important part of large scale search system apart from the compact representation. To this end, we extend our ideas for supervised compact representation learning for building inverted indexes. In this work we approach inverted indexing with supervised deep learning and make an attempt to unify the learning of inverted index and compact representation. We thoroughly evaluate all the proposed methods on various publicly available datasets. Our methods either outperform, or are competitive with the state-of-the-art

L'identification d'images (ou la détection des copies) consiste à retrouver l'original d’où est issue une image requête ainsi que les metadonnées associées, telles que titres, auteurs, droits de reproduction, etc. . . La tâche est difficile en raison de la variété des transformations que l'image originale peut avoir subi. Les systèmes d'identification d'images basées sur des descripteurs locaux ont montré une excellente efficacité, mais souffrent souvent des problèmes de rapidité d'exécution car, des centaines, voire des milliers de descripteurs, doivent être appariés afin de trouver une seule image. L'objectif de notre travail est de fournir des méthodes rapides pour l’appariement des descripteurs, basées sur la recherche rapide des k-plus proches voisins dans des espaces de grandes dimensions. De cette façon, nous pouvons gagner les avantages d’efficacité amenés par l'utilisation des descripteurs locaux, pendant qu’on minimise les problèmes d’efficience. Nous proposons trois nouvelles pour la recherche des k-plus proches voisins ; les 3-way trees, qui améliorent les KD-trees travers l’utilisation des noeuds chevauchants redondants ; les projection KD-forests, qui utilisent des multiples KD-trees à dimensionnalité modérée ; et les multicurves, qui utilisent des multiples courbes d’Hilbert remplissantes de l’espace. Ces techniques cherchent à réduire le nombre d’accès aléatoires, pour être bien adaptées à l’implémentation en mémoire secondaire
Image identification (or copy detection) consists in retrieving the original from which a query image possibly derives, as well as any related metadata, such as titles, authors, copyright information, etc. The task is challenging because of the variety of transformations that the original image may have suffered. Image identification systems based on local descriptors have shown excellent efficacy, but often suffer from efficiency issues, since hundreds, even thousands of descriptors, have to be matched in order to find a single image. The objective of our work is to provide fast methods for descriptor matching, by creating efficient ways to perform the k-nearest neighbours search in high-dimensional spaces. In this way, we can gain the advantages from the use of local descriptors, while minimising the efficiency issues. We propose three new methods for the k-nearest neighbours search: the 3-way trees — an improvement over the KD-trees using redundant, overlapping nodes; the projection KD-forests — a technique which uses multiple moderate dimensional KD-trees; and the multicurves, which is based on multiple moderate dimensional Hilbert space-filling curves. Those techniques try to reduce the amount of random access to the data, in order to be well adapted to the implementation in secondary memory

Avec l’évolution des technologies numériques et la prolifération d'internet, la quantité d’information numérique a considérablement évolué. La recherche par similarité (ou recherche des plus proches voisins) est une problématique que plusieurs communautés de recherche ont tenté de résoudre. Les systèmes de recherche par le contenu de l’information constituent l’une des solutions prometteuses à ce problème. Ces systèmes sont composés essentiellement de trois unités fondamentales, une unité de représentation des données pour l’extraction des primitives, une unité d’indexation multidimensionnelle pour la structuration de l’espace des primitives, et une unité de recherche des plus proches voisins pour la recherche des informations similaires. L’information (image, texte, audio, vidéo) peut être représentée par un vecteur multidimensionnel décrivant le contenu global des données d’entrée. La deuxième unité consiste à structurer l’espace des primitives dans une structure d’index, où la troisième unité -la recherche par similarité- est effective.Dans nos travaux de recherche, nous proposons trois systèmes de recherche par le contenu de plus proches voisins. Les trois approches sont non supervisées, et donc adaptées aux données étiquetées et non étiquetées. Elles sont basées sur le concept du hachage pour une recherche efficace multidimensionnelle des plus proches voisins. Contrairement aux approches de hachage existantes, qui sont binaires, les approches proposées fournissent des structures d’index avec un hachage réel. Bien que les approches de hachage binaires fournissent un bon compromis qualité-temps de calcul, leurs performances en termes de qualité (précision) se dégradent en raison de la perte d’information lors du processus de binarisation. À l'opposé, les approches de hachage réel fournissent une bonne qualité de recherche avec une meilleure approximation de l’espace d’origine, mais induisent en général un surcoût en temps de calcul.Ce dernier problème est abordé dans la troisième contribution. Les approches proposées sont classifiées en deux catégories, superficielle et profonde. Dans la première catégorie, on propose deux techniques de hachage superficiel, intitulées Symmetries of the Cube Locality sensitive hashing (SC-LSH) et Cluster-Based Data Oriented Hashing (CDOH), fondées respectivement sur le hachage aléatoire et l’apprentissage statistique superficiel. SCLSH propose une solution au problème de l’espace mémoire rencontré par la plupart des approches de hachage aléatoire, en considérant un hachage semi-aléatoire réduisant partiellement l’effet aléatoire, et donc l’espace mémoire, de ces dernières, tout en préservant leur efficacité pour la structuration des espaces hétérogènes. La seconde technique, CDOH, propose d’éliminer l’effet aléatoire en combinant des techniques d’apprentissage non-supervisé avec le concept de hachage. CDOH fournit de meilleures performances en temps de calcul, en espace mémoire et en qualité de recherche.La troisième contribution est une approche de hachage basée sur les réseaux de neurones profonds appelée "Unsupervised Deep Neuron-per-Neuron Hashing" (UDN2H). UDN2H propose une indexation individuelle de la sortie de chaque neurone de la couche centrale d’un modèle non supervisé. Ce dernier est un auto-encodeur profond capturant une structure individuelle de haut niveau de chaque neurone de sortie.Nos trois approches, SC-LSH, CDOH et UDN2H, ont été proposées séquentiellement durant cette thèse, avec un niveau croissant, en termes de la complexité des modèles développés, et en termes de la qualité de recherche obtenue sur de grandes bases de données d'information
The amount of media data is growing at high speed with the fast growth of Internet and media resources. Performing an efficient similarity (nearest neighbor) search in such a large collection of data is a very challenging problem that the scientific community has been attempting to tackle. One of the most promising solutions to this fundamental problem is Content-Based Media Retrieval (CBMR) systems. The latter are search systems that perform the retrieval task in large media databases based on the content of the data. CBMR systems consist essentially of three major units, a Data Representation unit for feature representation learning, a Multidimensional Indexing unit for structuring the resulting feature space, and a Nearest Neighbor Search unit to perform efficient search. Media data (i.e. image, text, audio, video, etc.) can be represented by meaningful numeric information (i.e. multidimensional vector), called Feature Description, describing the overall content of the input data. The task of the second unit is to structure the resulting feature descriptor space into an index structure, where the third unit, effective nearest neighbor search, is performed.In this work, we address the problem of nearest neighbor search by proposing three Content-Based Media Retrieval approaches. Our three approaches are unsupervised, and thus can adapt to both labeled and unlabeled real-world datasets. They are based on a hashing indexing scheme to perform effective high dimensional nearest neighbor search. Unlike most recent existing hashing approaches, which favor indexing in Hamming space, our proposed methods provide index structures adapted to a real-space mapping. Although Hamming-based hashing methods achieve good accuracy-speed tradeoff, their accuracy drops owing to information loss during the binarization process. By contrast, real-space hashing approaches provide a more accurate approximation in the mapped real-space as they avoid the hard binary approximations.Our proposed approaches can be classified into shallow and deep approaches. In the former category, we propose two shallow hashing-based approaches namely, "Symmetries of the Cube Locality Sensitive Hashing" (SC-LSH) and "Cluster-based Data Oriented Hashing" (CDOH), based respectively on randomized-hashing and shallow learning-to-hash schemes. The SC-LSH method provides a solution to the space storage problem faced by most randomized-based hashing approaches. It consists of a semi-random scheme reducing partially the randomness effect of randomized hashing approaches, and thus the memory storage problem, while maintaining their efficiency in structuring heterogeneous spaces. The CDOH approach proposes to eliminate the randomness effect by combining machine learning techniques with the hashing concept. The CDOH outperforms the randomized hashing approaches in terms of computation time, memory space and search accuracy.The third approach is a deep learning-based hashing scheme, named "Unsupervised Deep Neuron-per-Neuron Hashing" (UDN2H). The UDN2H approach proposes to index individually the output of each neuron of the top layer of a deep unsupervised model, namely a Deep Autoencoder, with the aim of capturing the high level individual structure of each neuron output.Our three approaches, SC-LSH, CDOH and UDN2H, were proposed sequentially as the thesis was progressing, with an increasing level of complexity in terms of the developed models, and in terms of the effectiveness and the performances obtained on large real-world datasets

Cette thèse étudie deux tâches fondamentales d'apprentissage non supervisé: la recherche des plus proches voisins et le clustering de données massives en grande dimension pour respecter d'importantes contraintes de temps et d'espace.Tout d'abord, un nouveau cadre théorique permet de réduire le coût spatial et d'augmenter le débit de traitement du Cross-polytope LSH pour la recherche du plus proche voisin presque sans aucune perte de précision.Ensuite, une méthode est conçue pour apprendre en une seule passe sur des données en grande dimension des codes compacts binaires. En plus de garanties théoriques, la qualité des sketches obtenus est mesurée dans le cadre de la recherche approximative des plus proches voisins. Puis, un algorithme de clustering sans paramètre et efficace en terme de coût de stockage est développé en s'appuyant sur l'extraction d'un arbre couvrant minimum approché du graphe de dissimilarité compressé auquel des coupes bien choisies sont effectuées
This thesis focuses on how to perform efficiently unsupervised machine learning such as the fundamentally linked nearest neighbor search and clustering task, under time and space constraints for high-dimensional datasets. First, a new theoretical framework reduces the space cost and increases the rate of flow of data-independent Cross-polytope LSH for the approximative nearest neighbor search with almost no loss of accuracy.Second, a novel streaming data-dependent method is designed to learn compact binary codes from high-dimensional data points in only one pass. Besides some theoretical guarantees, the quality of the obtained embeddings are accessed on the approximate nearest neighbors search task.Finally, a space-efficient parameter-free clustering algorithm is conceived, based on the recovery of an approximate Minimum Spanning Tree of the sketched data dissimilarity graph on which suitable cuts are performed

Cette thèse étudie deux tâches fondamentales d'apprentissage non supervisé: la recherche des plus proches voisins et le clustering de données massives en grande dimension pour respecter d'importantes contraintes de temps et d'espace.Tout d'abord, un nouveau cadre théorique permet de réduire le coût spatial et d'augmenter le débit de traitement du Cross-polytope LSH pour la recherche du plus proche voisin presque sans aucune perte de précision.Ensuite, une méthode est conçue pour apprendre en une seule passe sur des données en grande dimension des codes compacts binaires. En plus de garanties théoriques, la qualité des sketches obtenus est mesurée dans le cadre de la recherche approximative des plus proches voisins. Puis, un algorithme de clustering sans paramètre et efficace en terme de coût de stockage est développé en s'appuyant sur l'extraction d'un arbre couvrant minimum approché du graphe de dissimilarité compressé auquel des coupes bien choisies sont effectuées
This thesis focuses on how to perform efficiently unsupervised machine learning such as the fundamentally linked nearest neighbor search and clustering task, under time and space constraints for high-dimensional datasets. First, a new theoretical framework reduces the space cost and increases the rate of flow of data-independent Cross-polytope LSH for the approximative nearest neighbor search with almost no loss of accuracy.Second, a novel streaming data-dependent method is designed to learn compact binary codes from high-dimensional data points in only one pass. Besides some theoretical guarantees, the quality of the obtained embeddings are accessed on the approximate nearest neighbors search task.Finally, a space-efficient parameter-free clustering algorithm is conceived, based on the recovery of an approximate Minimum Spanning Tree of the sketched data dissimilarity graph on which suitable cuts are performed

Cette thèse s'inscrit dans la problématique générale de l'inférence géométrique. Étant donné un objet qu'on ne connaît qu'à travers un échantillon fini, à partir de quelle qualité d'échantillonage peut-on estimer de manière fiable certaines de ses propriétés géométriques ou topologique? L'estimation de la topologie est maintenant un domaine assez mûr. La plupart des méthodes existantes sont fondées sur la notion de fonction distance. Nous utilisons cette approche pour estimer certaines notions de courbure dues à Federer, définies pour une classe assez générale d'objets non lisses. Nous introduisons une version approchée de ces courbures dont nous étudions la stabilité ainsi que calcul pratique dans le cas discret. Une version anisotrope de ces mesures de courbure permet en pratique d'estimer le lieu et la direction des arêtes vives d'une surface lisse par morceaux échantillonnée par un nuage de point. En chemin nous sommes amenés à étudier certaines propriétés de régularité de la fonction distance, comme le volume de l'axe médian. Un défaut des méthodes qui utilisent la fonction distance est leur extrême sensibilité aux points aberrants. Pour résoudre ce problème, nous sortons du cadre purement géométrique en remplaçant les compacts par des mesures de probabilité. Nous introduisons une notion de fonction distance à une mesure, robuste aux perturbations Wasserstein (et donc aux points aberrants) et qui partage certaines propriétés de régularité et de stabilité avec la fonction distance usuelle. Grâce à ces propriétés, il est possible d'étendre de nombreux théorèmes d'inférence géométrique à ce cadre.

Une nouvelle structure de dictionnaire adaptés aux décompositions itératives de type poursuite, appelée un Iteration-Tuned Dictionary (ITD), est présentée. Les ITDs sont structurés en couche, chaque couche se composant d'un ensemble de dictionnaires candidats. Les décompositions itératives basées ITD sont alors réalisées en sélectionnant, à chaque itération i, l'un des dictionnaires de la i-ième couche. Une structure générale des ITDs est proposée, ainsi qu'une variante structurée en arbre appelée Tree-Structured Iteration-Tuned Dictionary (TSITD) et une version contrainte de cette dernière, appelée Iteration-Tuned and Aligned Dictionary (ITAD). Ces structures sont comparées à plusieurs méthodes de l'état de l'art et évaluées dans des applications de débruitage et de compression d'images. Un codec basé sur le schéma ITAD est également présenté et comparé à JPEG2000 dans des évaluations qualitatives et quantitatives. Dans le contexte de l'indexation d'images, un nouveau système de recherche approximative des plus proches voisins est également introduit, qui utilise les représentations parcimonieuses pour réduire la complexité de la recherche. La méthode traite l'instabilité dans la sélection des atomes lorsque l'image est soumise à de faibles transformations affines. Un nouveau système de conditionnement des données est également introduit, permettant de mieux distribuer les données sur la sphère unitaire tout en préservant leurs distances angulaires relatives. Il est montré que cette méthode améliore le compromis complexité/performance de la recherche approximative basée décompositions parcimonieuses.

La principale contribution de cette thèse est le développement d'une méthode fiable, robuste, et rapide pour la prédiction des pré-miARNs. Deux objectifs avaient été assignés : efficacité et flexibilité. L'efficacité a été rendue possible au moyen d'un algorithme quadratique. La flexibilité repose sur deux aspects, la nature des données expérimentales et la position taxonomique de l'organisme (en particulier plantes ou animaux). Mirinho accepte en entrée des séquences de génomes complets mais aussi les très nombreuses séquences résultant d'un séquençage massif de type NGS de “RNAseq”. “L'universalité” taxonomique est obtenu par la possibilité de modifier les contraintes sur les tailles de la tige (double hélice) et de la boule terminale. Dans le cas de la prédiction des miARN de plantes la plus grande longueur de leur pré-miARN conduit à des méthodes d'extraction de la structure secondaire en tige-boule moins précises. Mirinho prend en compte ce problème lui permettant de fournir des structures secondaires de pré-miARN plus semblables à celles de miRBase que les autres méthodes disponibles. Mirinho a été utilisé dans le cadre de deux questions biologiques précises l'une concernant des RNAseq l'autre de l'ADN génomique. La première question a conduit au traitement et l'analyse des données RNAseq de Acyrthosiphon pisum, le puceron du pois. L'objectif était d'identifier les miARN qui sont différentiellement exprimés au cours des quatre stades de développement de cette espèce et sont donc des candidats à la régulation des gènes au cours du développement. Pour cette analyse, nous avons développé un pipeline, appelé MirinhoPipe. La deuxieme question a permis d'aborder les problèmes liés à la prévision et l'analyse des ARN non-codants (ARNnc) dans la bactérie Mycoplasma hyopneumoniae. Alvinho a été développé pour la prédiction de cibles des miRNA autour d'une segmentation d'une séquence numérique et de la détection de la conservation des séquences entre ncRNA utilisant un graphe k-partite. Nous avons finalement abordé un problème lié à la recherche de motifs conservés dans un ensemble de séquences et pouvant ainsi correspondre à des éléments fonctionnels
The main contribution of this thesis is the development of a reliable, robust, and much faster method for the prediction of pre-miRNAs. With this method, we aimed mainly at two goals: efficiency and flexibility. Efficiency was made possible by means of a quadratic algorithm. Flexibility relies on two aspects, the input type and the organism clade. Mirinho can receive as input both a genome sequence and small RNA sequencing (sRNA-seq) data of both animal and plant species. To change from one clade to another, it suffices to change the lengths of the stem-arms and of the terminal loop. Concerning the prediction of plant miRNAs, because their pre-miRNAs are longer, the methods for extracting the hairpin secondary structure are not as accurate as for shorter sequences. With Mirinho, we also addressed this problem, which enabled to provide pre-miRNA secondary structures more similar to the ones in miRBase than the other available methods. Mirinho served as the basis to two other issues we addressed. The first issue led to the treatment and analysis of sRNA-seq data of Acyrthosiphon pisum, the pea aphid. The goal was to identify the miRNAs that are expressed during the four developmental stages of this species, allowing further biological conclusions concerning the regulatory system of such an organism. For this analysis, we developed a whole pipeline, called MirinhoPipe, at the end of which Mirinho was aggregated. We then moved on to the second issue, that involved problems related to the prediction and analysis of non-coding RNAs (ncRNAs) in the bacterium Mycoplasma hyopneumoniae. A method, called Alvinho, was thus developed for the prediction of targets in this bacterium, together with a pipeline for the segmentation of a numerical sequence and detection of conservation among ncRNA sequences using a kpartite graph. We finally addressed a problem related to motifs, that is to patterns, that may be composed of one or more parts, that appear conserved in a set of sequences and may correspond to functional elements

Les caractéristiques locales sont essentielles dans de nombreux domaines de l’analyse d’images comme la détection et la reconnaissance d’objets, la recherche d’images, etc. Ces dernières années, plusieurs détecteurs dits locaux ont été proposés pour extraire de telles caractéristiques. Ces détecteurs locaux fonctionnent généralement bien pour certaines applications, mais pas pour toutes. Prenons, par exemple, une application de recherche dans une large base d’images. Dans ce cas, un détecteur à base de caractéristiques binaires pourrait être préféré à un autre exploitant des valeurs réelles. En effet, la précision des résultats de recherche pourrait être moins bonne tout en restant raisonnable, mais probablement avec un temps de réponse beaucoup plus court. En général, les détecteurs locaux sont utilisés en combinaison avec une méthode d’indexation. En effet, une méthode d’indexation devient nécessaire dans le cas où les ensembles de points traités sont composés de milliards de points, où chaque point est représenté par un vecteur de caractéristiques de grande dimension
Local features are of central importance to deal with many different problems in image analysis and understanding including image registration, object detection and recognition, image retrieval, etc. Over the years, many local detectors have been presented to detect such features. Such a local detector usually works well for some particular applications but not all. Taking an application of image retrieval in large database as an example, an efficient method for detecting binary features should be preferred to other real-valued feature detection methods. The reason is easily seen: it is expected to have a reasonable precision of retrieval results but the time response must be as fast as possible. Generally, local features are used in combination with an indexing scheme. This is highly needed for the case where the dataset is composed of billions of data points, each of which is in a high-dimensional feature vector space

La présente thèse s'intéresse à l'utilisation de méta-données textuelles pour l'analyse d'image. Nous cherchons à utiliser ces informations additionelles comme supervision faible pour l'apprentissage de modèles de reconnaissance visuelle. Nous avons observé un récent et grandissant intérêt pour les méthodes capables d'exploiter ce type de données car celles-ci peuvent potentiellement supprimer le besoin d'annotations manuelles, qui sont coûteuses en temps et en ressources. Nous concentrons nos efforts sur deux types de données visuelles associées à des informations textuelles. Tout d'abord, nous utilisons des images de dépêches qui sont accompagnées de légendes descriptives pour s'attaquer à plusieurs problèmes liés à la reconnaissance de visages. Parmi ces problèmes, la vérification de visages est la tâche consistant à décider si deux images représentent la même personne, et le nommage de visages cherche à associer les visages d'une base de données à leur noms corrects. Ensuite, nous explorons des modèles pour prédire automatiquement les labels pertinents pour des images, un problème connu sous le nom d'annotation automatique d'image. Ces modèles peuvent aussi être utilisés pour effectuer des recherches d'images à partir de mots-clés. Nous étudions enfin un scénario d'apprentissage multimodal semi-supervisé pour la catégorisation d'image. Dans ce cadre de travail, les labels sont supposés présents pour les données d'apprentissage, qu'elles soient manuellement annotées ou non, et absentes des données de test. Nos travaux se basent sur l'observation que la plupart de ces problèmes peuvent être résolus si des mesures de similarité parfaitement adaptées sont utilisées. Nous proposons donc de nouvelles approches qui combinent apprentissage de distance, modèles par plus proches voisins et méthodes par graphes pour apprendre, à partir de données visuelles et textuelles, des similarités visuelles spécifiques à chaque problème. Dans le cas des visages, nos similarités se concentrent sur l'identité des individus tandis que, pour les images, elles concernent des concepts sémantiques plus généraux. Expérimentalement, nos approches obtiennent des performances à l'état de l'art sur plusieurs bases de données complexes. Pour les deux types de données considérés, nous montrons clairement que l'apprentissage bénéficie de l'information textuelle supplémentaire résultant en l'amélioration de la performance des systèmes de reconnaissance visuelle.

La présente thèse s'intéresse à l'utilisation de méta-données textuelles pour l'analyse d'image. Nous cherchons à utiliser ces informations additionelles comme supervision faible pour l'apprentissage de modèles de reconnaissance visuelle. Nous avons observé un récent et grandissant intérêt pour les méthodes capables d'exploiter ce type de données car celles-ci peuvent potentiellement supprimer le besoin d'annotations manuelles, qui sont coûteuses en temps et en ressources. Nous concentrons nos efforts sur deux types de données visuelles associées à des informations textuelles. Tout d'abord, nous utilisons des images de dépêches qui sont accompagnées de légendes descriptives pour s'attaquer à plusieurs problèmes liés à la reconnaissance de visages. Parmi ces problèmes, la vérification de visages est la tâche consistant à décider si deux images représentent la même personne, et le nommage de visages cherche à associer les visages d'une base de données à leur noms corrects. Ensuite, nous explorons des modèles pour prédire automatiquement les labels pertinents pour des images, un problème connu sous le nom d'annotation automatique d'image. Ces modèles peuvent aussi être utilisés pour effectuer des recherches d'images à partir de mots-clés. Nous étudions enfin un scénario d'apprentissage multimodal semi-supervisé pour la catégorisation d'image. Dans ce cadre de travail, les labels sont supposés présents pour les données d'apprentissage, qu'elles soient manuellement annotées ou non, et absentes des données de test. Nos travaux se basent sur l'observation que la plupart de ces problèmes peuvent être résolus si des mesures de similarité parfaitement adaptées sont utilisées. Nous proposons donc de nouvelles approches qui combinent apprentissage de distance, modèles par plus proches voisins et méthodes par graphes pour apprendre, à partir de données visuelles et textuelles, des similarités visuelles spécifiques à chaque problème. Dans le cas des visages, nos similarités se concentrent sur l'identité des individus tandis que, pour les images, elles concernent des concepts sémantiques plus généraux. Expérimentalement, nos approches obtiennent des performances à l'état de l'art sur plusieurs bases de données complexes. Pour les deux types de données considérés, nous montrons clairement que l'apprentissage bénéficie de l'information textuelle supplémentaire résultant en l'amélioration de la performance des systèmes de reconnaissance visuelle
This dissertation delves into the use of textual metadata for image understanding. We seek to exploit this additional textual information as weak supervision to improve the learning of recognition models. There is a recent and growing interest for methods that exploit such data because they can potentially alleviate the need for manual annotation, which is a costly and time-consuming process. We focus on two types of visual data with associated textual information. First, we exploit news images that come with descriptive captions to address several face related tasks, including face verification, which is the task of deciding whether two images depict the same individual, and face naming, the problem of associating faces in a data set to their correct names. Second, we consider data consisting of images with user tags. We explore models for automatically predicting tags for new images, i. E. Image auto-annotation, which can also used for keyword-based image search. We also study a multimodal semi-supervised learning scenario for image categorisation. In this setting, the tags are assumed to be present in both labelled and unlabelled training data, while they are absent from the test data. Our work builds on the observation that most of these tasks can be solved if perfectly adequate similarity measures are used. We therefore introduce novel approaches that involve metric learning, nearest neighbour models and graph-based methods to learn, from the visual and textual data, task-specific similarities. For faces, our similarities focus on the identities of the individuals while, for images, they address more general semantic visual concepts. Experimentally, our approaches achieve state-of-the-art results on several standard and challenging data sets. On both types of data, we clearly show that learning using additional textual information improves the performance of visual recognition systems