The objective of this thesis is to explore the use of graph matching in object recognition systems. In the continuity of the previously described articles, rather than using descriptors invariant to misalignment, this work directly tries to find explicit correspondences between prototypes and test images, in order to build a robust similarity measure and infer the class of the test images. In chapter 2, we will present a method that given interest points in two images tries to find correspondences between them. It extends previous graph matching approaches [Leordeanu and Hebert, 2005a] to handle interactions between more than two feature correspondences. This allows us to build a more discriminative and/or more invariant matching method. The main contributions of this chapter are: The introduction of an high-order objective function for hyper-graph matching (Section 2.3.1). The application of the tensor power iteration method to the high-order matching task, combined with a relaxation based on constraints on the row norms of assignment matrices, which is tighter than previous methods (Section 2.3.1). An l1-norm instead of the classical l2-norm relaxation, that provides solutions that are more interpretable but still allows an efficient power iteration algorithm (Section 2.3.5). The design of appropriate similarity measures that can be chosen either to improve the invariance of matching, or to improve the expressivity of the model (Section 2.3.6). The proposed approach has been implemented, and it is compared to stateof-the-art algorithms on both synthetic and real data. As shown by our experiments (Section 2.5), our implementation is, overall, as fast as these methods in spite of the higher complexity of the model, with better accuracy on standard databases. In chapter 3, we build a graph-matching method for object categorization. The main contributions of this chapter are: Generalizing [Caputo and Jie, 2009; Wallraven et al., 2003], we propose in Section 3.3 to use the optimum value of the graph-matching problem associated with two images as a (non positive definite) kernel, suitable for SVM classification. We propose in Section 3.4 a novel extension of Ishikawa's method [Ishikawa, 2003] for optimizing MRFs which is orders of magnitude faster than competing algorithms (e.g., [Kim and Grauman, 2010; Kolmogorov and Zabih, 2004; Leordeanu and Hebert, 2005a]) for the grids with a few hundred nodes considered in this article). In turn, this allows us to combine our kernel with SVMs in image classification tasks. We demonstrate in Section 3.5 through experiments with standard benchmarks (Caltech 101, Caltech 256, and Scenes datasets) that our method matches and in some cases exceeds the state of the art for methods using a single type of features. In chapter 4, we introduce our work about object detection that perform fast image alignment. The main contributions of this chapter are: We propose a novel image similarity measure that allows for arbitrary deformations of the image pattern within some given disparity range and can be evaluated very efficiently [Lemire, 2006], with a cost equal to a small constant times that of correlation in a sliding-window mode. Our similarity measure relies on a hierarchical notion of parts based on simple rectangular image primitives and HOG cells [Dalal and Triggs, 2005a], and does not require manual part specification [Felzenszwalb and Huttenlocher, 2005b; Bourdev and Malik, 2009; Felzenszwalb et al., 2010] or automated discovery [Lazebnik et al., 2005; Kushal et al., 2007].

Telling cow from sheep is effortless for most animals, but requires much engineering for computers. In this thesis, we seek to tease out basic principles that underlie many recent advances in image recognition. First, we recast many methods into a common unsu- pervised feature extraction framework based on an alternation of coding steps, which encode the input by comparing it with a collection of reference patterns, and pooling steps, which compute an aggregation statistic summarizing the codes within some re- gion of interest of the image. Within that framework, we conduct extensive comparative evaluations of many coding or pooling operators proposed in the literature. Our results demonstrate a robust superiority of sparse coding (which decomposes an input as a linear combination of a few visual words) and max pooling (which summarizes a set of inputs by their maximum value). We also propose macrofeatures, which import into the popu- lar spatial pyramid framework the joint encoding of nearby features commonly practiced in neural networks, and obtain significantly improved image recognition performance. Next, we analyze the statistical properties of max pooling that underlie its better perfor- mance, through a simple theoretical model of feature activation. We then present results of experiments that confirm many predictions of the model. Beyond the pooling oper- ator itself, an important parameter is the set of pools over which the summary statistic is computed. We propose locality in feature configuration space as a natural criterion for devising better pools. Finally, we propose ways to make coding faster and more powerful through fast convolutional feedforward architectures, and examine how to incorporate supervision into feature extraction schemes. Overall, our experiments offer insights into what makes current systems work so well, and state-of-the-art results on several image recognition benchmarks.

This work addresses the problem of recognizing actions and interactions in realistic video settings such as movies and consumer videos. The first contribution of this thesis (Chapters 2 and 4) is concerned with new video representations for action recognition. We introduce local space-time descriptors and demonstrate their potential to classify and localize actions in complex settings while circumventing the difficult intermediate steps of person detection, tracking and human pose estimation. The material on bag-of-features action recognition in Chapter 2 is based on publications [L14, L22, L23] and is related to other work by the author [L6, L7, L8, L11, L12, L13, L16, L21]. The work on object and action localization in Chapter 4 is based on [L9, L10, L13, L15] and relates to [L1, L17, L19, L20]. The second contribution of this thesis is concerned with weakly-supervised action learning. Chap- ter 3 introduces methods for automatic annotation of action samples in video using readily-available video scripts. It addresses the ambiguity of action expressions in text and the uncertainty of tem- poral action localization provided by scripts. The material presented in Chapter 3 is based on publications [L4, L14, L18]. Finally Chapter 5 addresses interactions of people with objects and concerns modeling and recognition of object function. We exploit relations between objects and co-occurring human poses and demonstrate object recognition improvements using automatic pose estimation in challenging videos from YouTube. This part of the thesis is based on the publica- tion [L2] and relates to other work by the author [L3, L5].

Les circuits reconfigurables de type FPGA (Field Programmable Gate Arrays) peuvent désormais surpasser les processeurs généralistes pour certaines applications offrant un fort degré de parallélisme intrinsèque. Ces circuits sont traditionnellement programmés en utilisant des langages de type HDL (Hardware Description Languages), comme Verilog et VHDL. L'usage de ces langages permet d'exploiter au mieux les performances offertes par ces circuits mais requiert des programmeurs une très bonne connaissance des techniques de conception numérique. Ce pré-requis limite fortement l'utilisation des FPGA par la communauté des concepteurs de logiciel en général. Afin de pallier cette limitation, un certain nombre d'outils de plus haut niveau ont été développés, tant dans le monde industriel qu'académique. Parmi les approches proposées, celles fondées sur une transformation plus ou moins automatique de langages de type C ou équivalent, largement utilisés dans le domaine logiciel, ont été les plus explorées. Malheureusement, ces approches ne permettent pas, en général, d'obtenir des performances comparables à celles issues d'une formulation directe avec un langage de type HDL, en raison, essentiellement, de l'incapacité de ces langages à exprimer le parallélisme intrinsèque des applications. Une solution possible à ce problème passe par un changement du modèle de programmation même. Dans le contexte qui est le notre, le modèle flot de données apparaît comme un bon candidat. Cette thèse explore donc l'adoption d'un modèle de programmation flot de données pour la programmation de circuits de type FPGA. Plus précisément, nous évaluons l'adéquation de CAPH, un langage orienté domaine (Domain Specific Language) à la description et à l'implantation sur FPGA d'application opérant à la volée des capteurs (stream processing applications). L'expressivité du langage et l'efficacité du code généré sont évaluées expérimentalement en utilisant un large spectre d'applications, allant du traitement d'images bas niveau (filtrage, convolution) à des applications de complexité réaliste telles que la détection de mouvement, l'étiquetage en composantes connexes ou l'encodage JPEG.

Une des techniques alternatives au GPS pour le développement d'un système d'assistance à la navigationpédestre en milieux urbains est la vision embarquée. La localisation du porteur de la caméra s'appuie alorssur l'estimation de la pose à partir des images acquises au cours du cheminement. En s'inspirant destravaux antérieurs sur la navigation autonome de robots, cette thèse explore deux approches dans le cadrespécifique de la localisation pédestre. La première méthode de localisation s'appuie sur des appariementsde primitives images avec une cartographie 3D pré-estimée de l'environnement. Elle permet une estimationprécise de la pose complète de la caméra (6 ddl), mais les expérimentations montrent des limitationscritiques de robustesse et temps de calcul liées à l'étape de mise en correspondance. Une solutionalternative est proposée en utilisant les points de fuite. L'orientation de la caméra (3ddl) est estimée defaçon robuste et rapide par le suivi de 3 points de fuites orthogonaux dans une séquence vidéo. L'algorithmedéveloppé permet une localisation pédestre indoor en deux étapes : une phase d'apprentissage hors lignedéfinit un itinéraire de référence en sélectionnant des images clef au long du parcours, puis, en phase delocalisation, une position approximative mais réaliste du porteur est estimée en temps réel en comparant lesorientations de la caméra dans l'image courante et celle de référence.

En raison de l'augmentation du volume et de la complexité des systèmes de transport, de nouveaux systèmes avancés d'assistance à la conduite (ADAS) sont étudiés dans de nombreuses entreprises, laboratoires et universités. Ces systèmes comprennent des algorithmes avec des techniques qui ont été étudiés au cours des dernières décennies, comme la localisation et cartographie simultanées (SLAM), détection d'obstacles, la vision stéréoscopique, etc. Grâce aux progrès de l'électronique, de la robotique et de plusieurs autres domaines, de nouveaux systèmes embarqués sont développés pour garantir la sécurité des utilisateurs de ces systèmes critiques. Pour la plupart de ces systèmes, une faible consommation d'énergie ainsi qu'une taille réduite sont nécessaires. Cela crée la contrainte d'exécuter les algorithmes sur les systèmes embarqués avec des ressources limitées. Dans la plupart des algorithmes, en particulier pour la vision par ordinateur, une grande quantité de données doivent être traitées à des fréquences élevées, ce qui exige des ressources informatiques importantes. Un FPGA satisfait cette exigence, son architecture parallèle combinée à sa faible consommation d'énergie et la souplesse pour les programmer permet de développer et d'exécuter des algorithmes plus efficacement que sur d'autres plateformes de traitement. Les composants virtuels développés dans cette thèse ont été utilisés dans trois différents projets: PICASSO (vision stéréoscopique), COMMROB (détection d'obstacles à partir d'une système multicaméra) et SART (Système d'Aide au Roulage tous Temps).

Cette thèse porte sur la réalisation des tâches avec la locomotion sur des robots humanoïdes. Grâce à leurs nombreux degrés de liberté, ces robots possèdent un très haut niveau de redondance. D'autre part, les humanoïdes sont sous-actionnés dans le sens où la position et l'orientation ne sont pas directement contrôlées par un moteur. Ces deux aspects, le plus souvent étudiés séparément dans la littérature, sont envisagés ici dans un même cadre. En outre, la génération d'un mouvement complexe impliquant à la fois des tâches de manipulation et de locomotion, étudiée habituellement sous l'angle de la planification de mouvement, est abordée ici dans sa composante réactivité temps réel. En divisant le processus d'optimisation en deux étapes, un contrôleur basé sur la notion de pile de tâches permet l'adaptation temps réel des empreintes de pas planifiées dans la première étape. Un module de perception est également conçu pour créer une boucle fermée de perception-décision-action. Cette architecture combinant planification et réactivité est validée sur le robot HRP-2. Deux classes d'expériences sont menées. Dans un cas, le robot doit saisir un objet éloigné, posé sur une table ou sur le sol. Dans l'autre, le robot doit franchir un obstacle. Dans les deux cas, les condition d'exécution sont mises à jour en temps réel pour faire face à la dynamique de l'environnement : changement de position de l'objet à saisir ou de l'obstacle à franchir.

La thèse s'inscrit dans le domaine de la vision par ordinateur. Il s'agit, dans un environnement intérieur inconnu, partiellement connu ou connu de trouver la position et l'orientation d'une camera mobile en temps réel à partir d'une séquence vidéo prise par cette même camera. Le sujet implique également la reconstruction 3D de l'environnement. Les algorithmes de vision seront implémentés et testés sur des plateformes massivement parallèles. Processing the video sequence of a indoor camera in motion we have to find the position and angle of the camera in real time. We will use a single prime lens camera. It may involve an unknown, partially known or well known environment. A big part of the computation is the 3D reconstruction of the scene. The algorithms used to locate the camera will be implemented and tested on GPU.

Ce manuscrit présente mes activités de recherche sur les comportements basés vision pour des robots complexes comme les robots humanoïdes. La question scientifique sous-jacente qui structure ce travail est la suivante: " Quels sont les processus de décisions qui permettent à un robot humanoïde de générer des mouvements en temps réel basés sur des informations visuelles ?" Au football, les êtres humains peuvent décider de frapper une balle alors qu'ils courent et que tous les autres joueurs sont constamment en train de bouger. Reformuler comme un problème d'optimisation pour un robot humanoïde, trouver une solution pour un tel comportement est généralement très difficile du point de vue calculatoire. Par exemple, le problème de la recherche visuelle a été démontré comme étant NP-complet. La première partie de ce travail concerne la génération de mouvements temps réel. Partant des contraintes générales qu'un robot humanoïde doit remplir pour générer un mouvement faisable, des problèmes fondamentaux sont présentés. A partir de ceux-ci, plusieurs contributions permettant à un robot humanoïde de réagira à des changements de l'environnement sont présentés. Ils concernent la génération de la marche, les mouvements corps complets pour éviter des obstacles, et la planification de pas en temps réel dans des environnements contraints. La deuxième partie de ce travail concerne l'acquisition temps-réel de connaissance sur l'environnement à partir de la vision par ordinateur. Deux comportements principaux sont considérés: la recherche visuelle et la construction d'un modèle visuel d'un objet. Ils sont considérés tout en prenant compte le modèle du capteur, le coût du mouvement, les contraintes mécaniques du robot, la géométrie de l'environnement ainsi que les limitations du processus de vision. De plus des contributions sur le couplage de l'auto-localisation basé cartes avec la marche, la génération de pas basé sur l'asservissement visuel seront présentés. Finalement les technologies centrales développées dans les contextes précédents ont été utilisées dans différentes applications: l'interaction homme-robot, la téléopération, l'analyse de mouvement humains. Basé sur le retour d'expérience de plusieurs démonstrateurs intégrés sur le robot humanoïde HRP-2, la dernière partie de cette thèse proposent des pistes pour des idées permettant de lever les verrous technologiques actuels de la robotique humanoïde.

Cette thèse décrit de nouveaux modèles pour la reconnaissance de catégories d'actions comme "ouvrir une porte" ou "courir" dans des vidéos réalistes telles que les films. Nous nous intéressons tout particulièrement aux propriétés structurelles des actions : comment les décomposer, quelle en est la structure caractéristique et comment utiliser cette information afin de représenter le contenu d'une vidéo. La difficulté principale à laquelle nos modèles s'attellent réside dans la satisfaction simultanée de deux contraintes antagonistes. D'une part, nous devons précisément modéliser les aspects discriminants d'une action afin de pouvoir clairement identifier les différences entre catégories. D'autre part, nos représentations doivent être robustes en conditions réelles, c'est-à-dire dans des vidéos réalistes avec de nombreuses variations visuelles en termes d'acteurs, d'environnements et de points de vue. Dans cette optique, nous proposons donc trois modèles précis et robustes à la fois, qui capturent les relations entre parties d'actions ainsi que leur contenu. Notre approche se base sur des caractéristiques locales --- notamment les points d'intérêts spatio-temporels et le flot optique --- et a pour objectif d'organiser l'ensemble des descripteurs locaux décrivant une vidéo. Nous proposons aussi des noyaux permettant de comparer efficacement les représentations structurées que nous introduisons. Bien que nos modèles se basent tous sur les principes mentionnés ci-dessus, ils différent de par le type de problème traité et la structure sur laquelle ils reposent. Premièrement, nous proposons de modéliser une action par une séquence de parties temporelles atomiques correspondant à une décomposition sémantique. De plus, nous décrivons comment apprendre un modèle flexible de la structure temporelle dans le but de localiser des actions dans des vidéos de longue durée. Deuxièmement, nous étendons nos idées à l'estimation et à la représentation de la structure spatio-temporelle d'activités plus complexes. Nous décrivons un algorithme d'apprentissage non supervisé permettant de dégager automatiquement une décomposition hiérarchique du contenu dynamique d'une vidéo. Nous utilisons la structure arborescente qui en résulte pour modéliser une action de manière hiérarchique. Troisièmement, au lieu de comparer des modèles structurés, nous explorons une autre alternative : directement comparer des modèles de structure. Pour cela, nous représentons des actions de courte durée comme des séries temporelles en haute dimension et étudions comment la dynamique temporelle d'une action peut être utilisée pour améliorer les performances des modèles non structurés formant l'état de l'art en reconnaissance d'actions. Dans ce but, nous proposons un noyau calculant de manière efficace la similarité entre les dépendances temporelles respectives de deux actions. Nos trois approches et leurs assertions sont à chaque fois validées par des expériences poussées sur des bases de données publiques parmi les plus difficiles en reconnaissance d'actions. Nos résultats sont significativement meilleurs que ceux de l'état de l'art, illustrant ainsi à quel point la structure des actions est importante afin de bâtir des modèles précis et robustes pour la reconnaissance d'actions dans des vidéos réalistes.