This thesis investigates the removal of spatially-variant blur from photographs degraded by camera shake, and the removal of large occluding objects from photographs of popular places. We examine these problems in the case where the photographs are taken with standard consumer cameras, and we have no particular information about the scene being photographed. Most existing deblurring methods model the observed blurry image as the convolution of a sharp image with a uniform blur kernel. However, we show that blur from camera shake is in general mostly due to the 3D rotation of the camera, resulting in a blur that can be significantly non-uniform across the image. We model this blur using a weighted set of camera poses, which induce homographies on the image being captured. The blur in a particular image is parameterised by the set of weights, which provides a compact global descriptor for the blur, analogous to a convolution kernel. This descriptor fully captures the spatially-variant blur at all pixels, and is able to model camera shake more accurately than previous methods. We demonstrate direct estimation of the blur weights from single and multiple blurry images captured by conventional cameras. This permits a sharp image to be recovered from a blurry "shaken" image without any user interaction or additional infor- mation about the camera motion. For single image deblurring, we adapt an existing marginalisation-based algorithm and a maximum a posteriori-based algorithm, which are both compatible with our model of spatially-variant blur. In order to reduce the computational cost of our homography-based model, we introduce an efficient approximation based on local-uniformity of the blur. By grouping pixels into local regions which share a single PSF, we are able to take advantage of fast, frequency domain convolutions to perform the blur computation. We apply this approximation to single image deblurring, obtaining an order of magnitude reduction in computation time with no visible reduction in quality. For deblurring images with saturated pixels, we propose a modification of the forward model to include this non-linearity, and re-derive the Richardson-Lucy algorithm with this new model. To prevent ringing artefacts from propagating in the deblurred image, we propose separate updates for those pixels affected by saturation, and those not affected. This prevents the loss of information caused by clipping from propagating to the rest of the image. In order to remove large occluders from photos, we automatically retrieve a set of exemplar images of the same scene from the Internet, using a visual search engine. We extract multiple homographies between each of these images and the target image to provide pixel correspondences. Finally we combine pixels from several exemplars in a seamless manner to replace the occluded pixels, by solving an energy minimisation problem on a conditional random field. Experimental results are shown on both synthetic images and real photographs captured by consumer cameras or downloaded from the Internet.

This thesis addresses the problem of human action recognition in realistic video data, such as movies and online videos. Automatic and accurate recognition of human actions in video is a fascinating capability. The potential applications range from surveillance and robotics to medical diagnosis, content-based video retrieval, and intelligent human- computer interfaces. The task is highly challenging due to the large variations in person appearances, dynamic backgrounds, view-point changes, lighting conditions, action styles and other factors. Statistical video representations based on local space-time features have been recently shown successful for action recognition in realistic scenarios. Their success can be at- tributed to the mild assumptions about the data and robustness to several variations in the video. Such representations, however, often encode videos by disordered collection of low-level primitives. This thesis extends current methods by developing more discrimi- native features and integrating additional supervision into Bag-of-Features based video representations, aiming to improve action recognition in unconstrained and challenging video data. We start by evaluating a range of available local space-time feature detectors and descriptors under the standard Bag-of-Features framework. We then propose to improve the basic Bag-of-Features model by integrating additional supervision in the form of non-local region-level information. We further investigate an attribute-based representation, wherein the attributes range from objects (e.g., car, chair, table, etc.) to human poses and actions. We demonstrate that such representation captures high-level information in video, and provides complementary information to the low-level features. We finally propose a novel local representation for human action recognition in video, denoted as Actlets. Actlets are body part detectors undergoing characteristic motion patterns. We train Actlets using a large synthetic video dataset of rendered avatars and demonstrate the advantages of Actlets for action recognition in realistic data. All methods proposed and developed in this thesis represent alternative ways of construct- ing supervised video representations and demonstrate improvements of human action recognition in realistic settings.

Les hommes et la plupart des animaux ont une capacité naturelle à voir le monde et à le comprendre sans effort. La simplicité apparente avec laquelle un humain perçoit ce qui l'entoure suggère que le processus impliqué ne nécessite pas, dans une certaine mesure, un haut degré de réflexion. Cette observation suggère que notre perception visuelle du monde peut être simulée sur un ordinateur. La vision par ordinateur est le domaine de la recherche consacré au problème de la création d'une forme de perception visuelle pour des ordinateurs. Les premiers travaux dans ce domaine remontent aux années cinquante, mais la puissance de calcul des ordinateurs de cette époque ne permettait pas de traiter et d'analyser les données visuelles nécessaires à l'elaboration d'une perception visuelle virtuelle. Ce n'est que récemment que la puissance de calcul et la capacité de stockage ont permis à ce domaine de vrai- ment émerger. Depuis maintenant deux décennies, la vision par ordinateur a permis de répondre à problèmes pratiques ou industrielles comme par exemple, la détection des visages, de personnes au comportement suspect dans une foule ou de défauts de fabrication dans des chaînes de production. En revanche, en ce qui concerne l'émergence d'une perception visuelle virtuelle non spécifique à une tâche donnée, peu de progrès ont été réalisés et la communauté est toujours confrontée à des problèmes fondamentaux. Un de ces problèmes est de segmenter une image ou une video en régions porteuses de sens, ou en d'autres termes, en objets ou actions. La segmentation de scène est non seulement naturelle pour les humains, mais aussi essentielle pour comprendre pleinement son environnement. Malheureusement elle est aussi extrêmement difficile à reproduire sur un ordinateur. Une des raisons est qu'il n'existe pas de définition claire de ce qu'est une région "significative". En effet, en fonction de la scène ou de la situation, une région peut avoir des interprétations différentes. Par exemple, étant donnée une scène se passant dans la rue, on peut considérer que distinguer un piéton est important dans cette situation, par contre ses vêtements ne le semblent pas nécessairement. Si maintenant nous considérons une scène ayant lieu pendant un défilé de mode, un vêtement devient un élément important, donc une région significative. Dans cette thèse, nous nous concentrons sur ce problème de segmentation et nous l'abordons sous un angle particulier afin d'éviter cette difficulté fondamentale. Nous allons considérer la segmentation comme un problème d'apprentissage faible- ment supervisé, c'est-à-dire qu'au lieu de segmenter des images selon une certaine définition prédéfinie de régions "significatives", nous développons des méthodes per- mettant de segmenter simultanément un ensemble d'images en régions qui apparais- sent régulièrement. En d'autres termes, nous définissons une région "significative" d'un point de vue statistique: Ce sont les régions qui apparaissent régulièrement dans l'ensemble des images données. Pour cela nous concevons des modèles ayant une portée qui va au-delà de l'application à la vision. Notre approche prend ses racines dans l'apprentissage statistique, dont l'objectif est de concevoir des méthodes efficaces pour extraire et/ou apprendre des motifs récurrents dans des jeux de données. Ce domaine a récemment connu une forte popularité en raison de l'augmentation du nombre, de la taille des bases de données disponibles et la nécessité de traiter les données automatiquement. Dans cette thèse, nous nous concentrons sur des méthodes conçues pour découvrir l'information "cachée" dans une base de données à partir d'annotations incomplètes ou inexistantes. Enfin, nos travaux prennent aussi racines dans le domaine de l'optimisation numérique afin d'élaborer des algorithmes efficaces et adaptés spécialement à nos prob- lèmes. En particulier, nous utilisons et adaptons des outils récemment développés afin de relaxer des problèmes combinatoires complexes en des problèmes convexes pour lesquels il est garanti de trouver la solution optimale à l'aide de procedures developpees en optimisation convexe. Nous illustrons la qualité de nos formulations et algorithmes aussi sur des problèmes tirés de domaines autres que la vision par ordinateur. En particulier, nous montrons que nos travaux peuvent être utilisés dans la classification de texte et en biologie cellulaire.

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.