Le présent manuscrit est composé de deux parties relativement indépendantes.La première partie est consacrée au problème de la stéréovision binoculaire, et plus particulièrement au traitement de l'occultation. En partant d'une analyse de ce phénomène, nous en déduisons un modèle de régularité qui inclut une contrainte convexe de visibilité. La fonctionnelle d'énergie qui en résulte est minimisée par relaxation convexe. Les zones occultées sont alors détectées grâce à la pente horizontale de la carte de disparité avant d'être densifiées.Une autre méthode gérant l'occultation est la méthode des graph cuts proposée par Kolmogorov et Zabih. L'efficacité de cette méthode justifie son adaptation à deux problèmes auxiliaires rencontrés en stéréovision, qui sont la densification de cartes éparses et le raffinement subpixellique de cartes pixelliques.La seconde partie de ce manuscrit traite de manière plus générale de deux algorithmes d'optimisation convexe, pour lequels deux variantes accélérées sont proposées. Le premier est la méthode des directions alternées (ADMM). On montre qu'un léger relâchement de contraintes dans les paramètres de cette méthode permet d'obtenir un taux de convergence théorique plus intéressant.Le second est un algorithme de descentes proximales alternées, qui permet de paralléliser la résolution approchée du problème Rudin-Osher-Fatemi (ROF) de débruitage pur dans le cas des images couleurs. Une accélération de type FISTA est également proposée. / This thesis is splitted into two relatively independant parts. The first part is devoted to the binocular stereovision problem, specifically to the occlusion handling. An analysis of this phenomena leads to a regularity model which includes a convex visibility constraint. The resulting energy functional is minimized by convex relaxation. The occluded areas are then detected thanks to the horizontal slope of the disparity map and densified. Another method with occlusion handling was proposed by Kolmogorov and Zabih. Because of its efficiency, we adapted it to two auxiliary problems encountered in stereovision, namely the densification of sparse disparity maps and the subpixel refinement of pixel-accurate maps.The second part of this thesis studies two convex optimization algorithms, for which an acceleration is proposed. The first one is the Alternating Direction Method of Multipliers (ADMM). A slight relaxation in the parameter choice is shown to enhance the convergence rate. The second one is an alternating proximal descent algorithm, which allows a parallel approximate resolution of the Rudin-Osher-Fatemi (ROF) pure denoising model, in color-image case. A FISTA-like acceleration is also proposed.

Cette thèse présente de nouvelles méthodes pour l'application de la prédiction structurée en vision numérique et en imagerie médicale.Nos nouvelles contributions suivent quatre axes majeurs.La première partie de cette thèse étudie le problème d'inférence d'ordre supérieur.Nous présentons une nouvelle famille de problèmes de minimisation d'énergie discrète, l'étiquetage parcimonieux, encourageant la parcimonie des étiquettes.C'est une extension naturelle des problèmes connus d'étiquetage de métriques aux potentiels d'ordre élevé.Nous proposons par ailleurs une généralisation du modèle Pn-Potts, le modèle Pn-Potts hiérarchique.Enfin, nous proposons un algorithme parallélisable à proposition de mouvements avec de fortes bornes multiplicatives pour l'optimisation du modèle Pn-Potts hiérarchique et l'étiquetage parcimonieux.La seconde partie de cette thèse explore le problème de classement en utilisant de l'information d'ordre élevé.Nous introduisons deux cadres différents pour l'incorporation d'information d'ordre élevé dans le problème de classement.Le premier modèle, que nous nommons SVM binaire d'ordre supérieur (HOB-SVM), optimise une borne supérieure convexe sur l'erreur 0-1 pondérée tout en incorporant de l'information d'ordre supérieur en utilisant un vecteur de charactéristiques jointes.Le classement renvoyé par HOB-SVM est obtenu en ordonnant les exemples selon la différence entre la max-marginales de l'affectation d'un exemple à la classe associée et la max-marginale de son affectation à la classe complémentaire.Le second modèle, appelé AP-SVM d'ordre supérieur (HOAP-SVM), s'inspire d'AP-SVM et de notre premier modèle, HOB-SVM.Le modèle correspond à une optimisation d'une borne supérieure sur la précision moyenne, à l'instar d'AP-SVM, qu'il généralise en permettant également l'incorporation d'information d'ordre supérieur.Nous montrons comment un optimum local du problème d'apprentissage de HOAP-SVM peut être déterminé efficacement grâce à la procédure concave-convexe.En utilisant des jeux de données standards, nous montrons empiriquement que HOAP-SVM surpasse les modèles de référence en utilisant efficacement l'information d'ordre supérieur tout en optimisant directement la fonction d'erreur appropriée.Dans la troisième partie, nous proposons un nouvel algorithme, SSVM-RP, pour obtenir un chemin de régularisation epsilon-optimal pour les SVM structurés.Nous présentons également des variantes intuitives de l'algorithme Frank-Wolfe pour l'optimisation accélérée de SSVM-RP.De surcroît, nous proposons une approche systématique d'optimisation des SSVM avec des contraintes additionnelles de boîte en utilisant BCFW et ses variantes.Enfin, nous proposons un algorithme de chemin de régularisation pour SSVM avec des contraintes additionnelles de positivité/negativité.Dans la quatrième et dernière partie de la thèse, en appendice, nous montrons comment le cadre de l'apprentissage semi-supervisé des SVM à variables latentes peut être employé pour apprendre les paramètres d'un problème complexe de recalage déformable.Nous proposons un nouvel algorithme discriminatif semi-supervisé pour apprendre des métriques de recalage spécifiques au contexte comme une combinaison linéaire des métriques conventionnelles.Selon l'application, les métriques traditionnelles sont seulement partiellement sensibles aux propriétés anatomiques des tissus.Dans ce travail, nous cherchons à déterminer des métriques spécifiques à l'anatomie et aux tissus, par agrégation linéaire de métriques connues.Nous proposons un algorithme d'apprentissage semi-supervisé pour estimer ces paramètres conditionnellement aux classes sémantiques des données, en utilisant un jeu de données faiblement annoté.Nous démontrons l'efficacité de notre approche sur trois jeux de données particulièrement difficiles dans le domaine de l'imagerie médicale, variables en terme de structures anatomiques et de modalités d'imagerie. / This thesis develops novel methods to enable the use of structured prediction in computer vision and medical imaging. Specifically, our contributions are four fold. First, we propose a new family of high-order potentials that encourage parsimony in the labeling, and enable its use by designing an accurate graph cuts based algorithm to minimize the corresponding energy function. Second, we show how the average precision SVM formulation can be extended to incorporate high-order information for ranking. Third, we propose a novel regularization path algorithm for structured SVM. Fourth, we show how the weakly supervised framework of latent SVM can be employed to learn the parameters for the challenging deformable registration problem.In more detail, the first part of the thesis investigates the high-order inference problem. Specifically, we present a novel family of discrete energy minimization problems, which we call parsimonious labeling. It is a natural generalization of the well known metric labeling problems for high-order potentials. In addition to this, we propose a generalization of the Pn-Potts model, which we call Hierarchical Pn-Potts model. In the end, we propose parallelizable move making algorithms with very strong multiplicative bounds for the optimization of the hierarchical Pn-Potts model and the parsimonious labeling.Second part of the thesis investigates the ranking problem while using high-order information. Specifically, we introduce two alternate frameworks to incorporate high-order information for the ranking tasks. The first framework, which we call high-order binary SVM (HOB-SVM), optimizes a convex upperbound on weighted 0-1 loss while incorporating high-order information using joint feature map. The rank list for the HOB-SVM is obtained by sorting samples using max-marginals based scores. The second framework, which we call high-order AP-SVM (HOAP-SVM), takes its inspiration from AP-SVM and HOB-SVM (our first framework). Similar to AP-SVM, it optimizes upper bound on average precision. However, unlike AP-SVM and similar to HOB-SVM, it can also encode high-order information. The main disadvantage of HOAP-SVM is that estimating its parameters requires solving a difference-of-convex program. We show how a local optimum of the HOAP-SVM learning problem can be computed efficiently by the concave-convex procedure. Using standard datasets, we empirically demonstrate that HOAP-SVM outperforms the baselines by effectively utilizing high-order information while optimizing the correct loss function.In the third part of the thesis, we propose a new algorithm SSVM-RP to obtain epsilon-optimal regularization path of structured SVM. We also propose intuitive variants of the Block-Coordinate Frank-Wolfe algorithm (BCFW) for the faster optimization of the SSVM-RP algorithm. In addition to this, we propose a principled approach to optimize the SSVM with additional box constraints using BCFW and its variants. In the end, we propose regularization path algorithm for SSVM with additional positivity/negativity constraints.In the fourth and the last part of the thesis (Appendix), we propose a novel weakly supervised discriminative algorithm for learning context specific registration metrics as a linear combination of conventional metrics. Conventional metrics can cope partially - depending on the clinical context - with tissue anatomical properties. In this work we seek to determine anatomy/tissue specific metrics as a context-specific aggregation/linear combination of known metrics. We propose a weakly supervised learning algorithm for estimating these parameters conditionally to the data semantic classes, using a weak training dataset. We show the efficacy of our approach on three highly challenging datasets in the field of medical imaging, which vary in terms of anatomical structures and image modalities.

Les relaxations en problème d’optimisation linéaire jouent un rôle central en inférence du maximum a posteriori (map) dans les champs aléatoires de Markov discrets. Nous étudions ici les avantages offerts par les méthodes de Newton pour résoudre efficacement le problème dual (au sens de Lagrange) d’une reformulation lisse du problème. Nous comparons ces dernières aux méthodes de premier ordre, à la fois en terme de vitesse de convergence et de robustesse au mauvais conditionnement du problème. Nous exposons donc un cadre général pour l’apprentissage non-supervisé basé sur le transport optimal et les régularisations parcimonieuses. Nous exhibons notamment une approche prometteuse pour résoudre le problème de la préimage dans l’acp à noyau. Du point de vue de l’optimisation, nous décrivons le calcul du gradient d’une version lisse de la norme p de Schatten et comment cette dernière peut être utilisée dans un schéma de majoration-minimisation. / Numerical optimization and machine learning have had a fruitful relationship, from the perspective of both theory and application. In this thesis, we present an application oriented take on some inference and learning problems. Linear programming relaxations are central to maximum a posteriori (MAP) inference in discrete Markov Random Fields (MRFs). Especially, inference in higher-order MRFs presents challenges in terms of efficiency, scalability and solution quality. In this thesis, we study the benefit of using Newton methods to efficiently optimize the Lagrangian dual of a smooth version of the problem. We investigate their ability to achieve superior convergence behavior and to better handle the ill-conditioned nature of the formulation, as compared to first order methods. We show that it is indeed possible to obtain an efficient trust region Newton method, which uses the true Hessian, for a broad range of MAP inference problems. Given the specific opportunities and challenges in the MAP inference formulation, we present details concerning (i) efficient computation of the Hessian and Hessian-vector products, (ii) a strategy to damp the Newton step that aids efficient and correct optimization, (iii) steps to improve the efficiency of the conjugate gradient method through a truncation rule and a pre-conditioner. We also demonstrate through numerical experiments how a quasi-Newton method could be a good choice for MAP inference in large graphs. MAP inference based on a smooth formulation, could greatly benefit from efficient sum-product computation, which is required for computing the gradient and the Hessian. We show a way to perform sum-product computation for trees with sparse clique potentials. This result could be readily used by other algorithms, also. We show results demonstrating the usefulness of our approach using higher-order MRFs. Then, we discuss potential research topics regarding tightening the LP relaxation and parallel algorithms for MAP inference.Unsupervised learning is an important topic in machine learning and it could potentially help high dimensional problems like inference in graphical models. We show a general framework for unsupervised learning based on optimal transport and sparse regularization. Optimal transport presents interesting challenges from an optimization point of view with its simplex constraints on the rows and columns of the transport plan. We show one way to formulate efficient optimization problems inspired by optimal transport. This could be done by imposing only one set of the simplex constraints and by imposing structure on the transport plan through sparse regularization. We show how unsupervised learning algorithms like exemplar clustering, center based clustering and kernel PCA could fit into this framework based on different forms of regularization. We especially demonstrate a promising approach to address the pre-image problem in kernel PCA. Several methods have been proposed over the years, which generally assume certain types of kernels or have too many hyper-parameters or make restrictive approximations of the underlying geometry. We present a more general method, with only one hyper-parameter to tune and with some interesting geometric properties. From an optimization point of view, we show how to compute the gradient of a smooth version of the Schatten p-norm and how it can be used within a majorization-minimization scheme. Finally, we present results from our various experiments.

La représentation visuelle est un problème fondamental en vision par ordinateur. Le but est de réduire l'information au strict nécessaire pour une tâche désirée. Plusieurs types de représentation existent, comme les caractéristiques de couleur (histogrammes, attributs de couleurs...), de forme (dérivées, points d'intérêt...) ou d'autres, comme les bancs de filtres.Les caractéristiques bas-niveau (locales) sont rapides à calculer. Elles ont un pouvoir de représentation limité, mais leur généricité présente un intérêt pour des systèmes autonomes et multi-tâches, puisque les caractéristiques haut-niveau découlent d'elles.Le but de cette thèse est de construire puis d'étudier l'impact de représentations fondées seulement sur des caractéristiques locales de bas-niveau (couleurs, dérivées spatiales) pour deux tâches : la poursuite d'objets génériques, nécessitant des caractéristiques robustes aux variations d'aspect de l'objet et du contexte au cours du temps; la détection d'objets, où la représentation doit décrire une classe d'objets en tenant compte des variations intra-classe. Plutôt que de construire des descripteurs d'objets globaux dédiés, nous nous appuyons entièrement sur les caractéristiques locales et sur des mécanismes statistiques flexibles visant à estimer leur distribution (histogrammes) et leurs co-occurrences (Transformée de Hough Généralisée). La Transformée de Hough Généralisée (THG), créée pour la détection de formes quelconques, consiste à créer une structure de données représentant un objet, une classe... Cette structure, d'abord indexée par l'orientation du gradient, a été étendue à d'autres caractéristiques. Travaillant sur des caractéristiques locales, nous voulons rester proche de la THG originale.En poursuite d'objets, après avoir présenté nos premiers travaux, combinant la THG avec un filtre particulaire (utilisant un histogramme de couleurs), nous présentons un algorithme plus léger et rapide (100fps), plus précis et robuste. Nous présentons une évaluation qualitative et étudierons l'impact des caractéristiques utilisées (espace de couleur, formulation des dérivées partielles...). En détection, nous avons utilisé l'algorithme de Gall appelé forêts de Hough. Notre but est de réduire l'espace de caractéristiques utilisé par Gall, en supprimant celles de type HOG, pour ne garder que les dérivées partielles et les caractéristiques de couleur. Pour compenser cette réduction, nous avons amélioré deux étapes de l'entraînement : le support des descripteurs locaux (patchs) est partiellement produit selon une mesure géométrique, et l'entraînement des nœuds se fait en générant une carte de probabilité spécifique prenant en compte les patchs utilisés pour cette étape. Avec l'espace de caractéristiques réduit, le détecteur n'est pas plus précis. Avec les mêmes caractéristiques que Gall, sur une même durée d'entraînement, nos travaux ont permis d'avoir des résultats identiques, mais avec une variance plus faible et donc une meilleure répétabilité. / Visual representation is a fundamental problem in computer vision. The aim is to reduce the information to the strict necessary for a query task. Many types of representation exist, like color features (histograms, color attributes...), shape ones (derivatives, keypoints...) or filterbanks.Low-level (and local) features are fast to compute. Their power of representation are limited, but their genericity have an interest for autonomous or multi-task systems, as higher level ones derivate from them. We aim to build, then study impact of low-level and local feature spaces (color and derivatives only) for two tasks: generic object tracking, requiring features robust to object and environment's aspect changes over the time; object detection, for which the representation should describe object class and cope with intra-class variations.Then, rather than using global object descriptors, we use entirely local features and statisticals mecanisms to estimate their distribution (histograms) and their co-occurrences (Generalized Hough Transform).The Generalized Hough Transform (GHT), created for detection of any shape, consists in building a codebook, originally indexed by gradient orientation, then to diverse features, modeling an object, a class. As we work on local features, we aim to remain close to the original GHT.In tracking, after presenting preliminary works combining the GHT with a particle filter (using color histograms), we present a lighter and fast (100 fps) tracker, more accurate and robust.We present a qualitative evaluation and study the impact of used features (color space, spatial derivative formulation).In detection, we used Gall's Hough Forest. We aim to reduce Gall's feature space and discard HOG features, to keep only derivatives and color ones.To compensate the reduction, we enhanced two steps: the support of local descriptors (patches) are partially chosen using a geometrical measure, and node training is done by using a specific probability map based on patches used at this step.With reduced feature space, the detector is less accurate than with Gall's feature space, but for the same training time, our works lead to identical results, but with higher stability and then better repeatability.

Cette thèse étudie les problèmes posés par l’estimation automatique de modèles numériques d’élévation de la surface terrestre à partir de photographies prises par des satellites. Ce travail a bénéficié d’une collaboration avec le CNES (Centre National d’Etudes Spatiales) sur le développement d’outils de vision stéréoscopique pour Pléiades, le premier satellite d’observation de la Terre capable de produire des paires ou triplets d’images quasi-simultanées. Le premier chapitre de la thèse décrit un modèle simplifié de caméra pushbroom destiné aux satellites d’observation de la Terre, et aborde le problème de la correction des données de calibration en faisant intervenir des mesures externes. Ce chapitre propose un nouvel algorithme pour affiner les paramètres d’orientation du satellite à partir d’un jeu de points de contrôle. Il est utilisable pour tous les satellites munis de caméras pushbroom. Dans le but d’appliquer aux images satellitaires les nombreux algorithmes de mise en correspondance stéréoscopique développés en traitement d’images et en vision par ordinateur, le deuxième chapitre explore l’adaptation de la théorie de la rectification épipolaire aux images prises par des caméras pushbroom. La rectification épipolaire est utilisée habituellement pour réduire la complexité du problème de mise en correspondance stéréoscopique, et permet d’appliquer les algorithmes les plus récents à des images satellitaires. Le chapitre suivant étudie les effets des erreurs de calibration géométrique sur la rectification et propose une méthode pour éliminer leur impact sur la mise en correspondance. Le quatrième chapitre décrit et analyse en détails une implémentation de l’algorithme Semi-Global Matching (SGM), classé actuellement parmi les meilleurs algorithmes de mise en correspondance stéréoscopique. En se fondant sur une réinterprétation récente de SGM, ce chapitre en propose une variante qui permet de réduire d’un facteur cinq son écart en énergie par rapport aux algorithmes de référence pour la minimisation de champs aléatoires de Markov. En assemblant les blocs algorithmiques décrits dans les chapitres précédents, le cinquième chapitre décrit S2P, une chaîne stéréoscopique complète qui produit des modèles numériques d’élévation à partir d’images satellitaires. Un modèle d’évolution de paysage est présenté dans le sixième chapitre comme exemple d’application. Le modèle est utilisé pour simuler numériquement la structure fine du réseau hydrographique sur des modèles numériques d’élévation obtenus à partir d’images prises par Pléiades. Le code source de la chaîne S2P2 est distribué en tant que logiciel open source. Afin d’assurer la reproductibilité des résultats obtenus, les algorithmes implémentés dans S2P sont en cours de publication dans le journal IPOL, accompagnés de descriptions et d’analyses détaillées, de codes sources documentés et de démonstrateurs en ligne. / This thesis deals with the problem of computing accurate digital elevationmodels of the Earth's surface from optical images taken by pushbroomobservation satellites. It takes advantage of the collaboration of thedefendant with CNES (the French Space Agency) on the development ofstereo vision tools for Pléiades, the first Earth observation satelliteproducing quasi simultaneous stereo pairs or triplets with small baseline.The first chapter describes a simple pushbroom camera model for observationsatellites orbiting around the Earth and addresses the correction of theacquisition geometry by involving extrinsic information. This chapter proposesa new algorithm to refine the orientation parameters from a set of groundcontrol points, applicable to all pushbroom satellites.With the goal of testing for satellite imaging the thriving exploration ofstereo matching by the computer vision community, the second chapter exploresthe adaptation of the theory of epipolar resampling to pushbroom images.Epipolar resampling is traditionally used in stereo to reduce the matchingcomputational cost, and permits to test for satellite imaging the mostcompetitive computer vision algorithms. The third chapter discusses the effectsof geometric calibration inaccuracies and proposes a method to cancel itsimpact on stereo matching.The fourth chapter analyzes and describes a detailed implementation of theSemi-Global Matching (SGM) algorithm, which is currently among the top-rankedstereo vision algorithms. Based on a recently proposed interpretation of SGM asa min-sum Belief Propagation algorithm, a variant is proposed that allows toreduce by a factor five the energy gap of SGM with respect to referencealgorithms for Markov Random Fields with truncated smoothness terms.By wrapping together the algorithmic blocks described in the previous chapters,the fifth chapter describes S2P, a complete stereo pipeline for producingdigital elevation models from satellite images. As an application, a landscapeevolution model is presented in the sixth chapter. The model is used tosimulate numerically the fine structure of the river networks on digitalelevation models obtained from Pléiades Earth observation images.The source code of the S2P stereo pipeline is distributed as open source. Toensure reproducibility, the algorithms implemented in each step of the S2Ppipeline are submitted to the IPOL journal, with detailed descriptions of thealgorithms, documented source codes and online demonstrations for each block ofthe pipeline.

Cette thèse présente un ensemble d'outils ou cadre de développement (paradigme) pour suivre le mouvement de personnages humains dans les films. Beaucoup d'applications en forte demande, telle que la surveillance pour la sécurité ou l'interaction homme-machine, profiteraient d'un système qui pourrait détecter et suivre automatiquement des humains. L'exécution de séquences de film réelles pose un défi particulier compte tenu de la non-rigidité du mouvement du corps humains, ainsi que l'influence qu'ont plusieurs facteurs sur son apparence. Parmi eux se trouvrent la différence dans la gamme de conditions d'acquisition, la variation de l'environnement et de l'illumination, le mouvement de caméra et le peu de connaissances a priori dans le positionnement de la caméra. En tant que complément à l'analyse du mouvement humain, ce système vise à aider son utilisateur à détecter de façon automatique le mouvement de la caméra, à diviser la séquence de film en petits segments appelés "prises de vue" et à extraire des informations du mouvement humain en présence d'un arrière-scène complexe. Pour atteindre cet objectif, une estimation précise du flux optique est employée. Un processus d'image par image peut identifier six différents mouvements de la caméra, incluant une camera statique, en utilisant des gabarits prédéterminés. Il peut ensuite fournir une base de données de mouvements de caméra pour la séquence du film. Ces données sont très utiles pour l'annotation, l'indexage et la recherche de séquences vidéos. De plus, une Mixture de Gaussiennes (MoG) dotée d'un espace de couleur RGB normalisé est utilisée pour soustraire un arrière-scène statique, qui permet d'éviter les effets d'ombres. Lors d'un mouvement de caméra, nous optons pour une technique appelée "codage de couleur" pour convertir les champs de vecteurs de mouvement en image colorée et appliquer la soustraction d'arrière-plan conventionnelle à cette image de flux optique de couleurs. Ceci dit, un système de suivi multicouches déployé dans deux directions (d'ordre chronologique et d'ordre anti-chronologique) est aussi décrit dans la thèse. Finalement, l'évaluation de la performance du système est réalisée sur plusieurs séquences extraites des films réels. Les séquences ont été entièrement analysées indépendamment par un observateur humain pour fournir une base de référence réelle sur les mouvements de caméra aussi bien que sur le mouvement humain dans les séquences vidéos. La comparaison entre les résultats et la base de référence indique une performance très prometteuse des approches proposées tant par l'analyse de films que par les applications de surveillance.

Cette thèse porte sur la mise en correspondance stéréoscopique ainsi que sur son application à la détection des obstacles routiers à partir d'un système de vision stéréoscopique. La mise en correspondance est une étape cruciale dans la reconstruction de la structure tridimensionnelle de la scène observée. Elle consiste à retrouver les pixels homologues dans deux images prises de deux points de vue différents, et se ramène à un problème d'estimation d'un champ de disparité. La première partie de ma thèse a porté sur l'estimation de la disparité, dans le cadre d'une approche ensembliste, en minimisant une fonction objective convexe sur l'intersection d'ensembles convexes, construits à partir des connaissances a priori et des observations. Dans la plupart des applications de stéréovision, le champ de disparité doit être lisse dans les zones homogènes et les zones faiblement texturées. L'une de nos contributions a consisté à proposer différentes contraintes de régularisation satisfaisant cette propriété. Pour résoudre le problème d'optimisation considéré, nous utilisons un algorithme efficace itératif par bloc. La deuxième partie traite du problème d'estimation de la disparité en présence de changements d'illumination dans la scène observée. Nous considérons pour cela un modèle d'illumination multiplicatif qui permet de compenser les variations spatiales de luminosité de la scène. Enfin, dans la troisième partie, nous appliquons notre méthode d'estimation de la disparité robuste aux variations d'illumination pour la détection des obstacles routiers.

Cette thèse porte sur le développement d'outils permettant le recalage d'images d'une surface déformable et la reconstruction tridimensionnelle de surfaces déformables à partir d'images prises par une seule caméra. Les surfaces que nous souhaitons traiter sont typiquement un visage ou une feuille de papier. Ces problématiques sont mal posées lorsque seule l'information présente dans les images est exploitée. Des informations a priori sur les déformations physiquement admissibles de la surface observée doivent être définies. Elles diffèrent en fonction du problème étudié. Par exemple, pour une feuille de papier, la courbure Gaussienne évaluée en chacun de ces points est nulle, cette propriété n'est pas valide pour un visage. Les applications visées sont l'insertion réaliste de logo 2D, de texte et aussi d'objets virtuels 3D dans des vidéos présentant une surface déformable. La première partie de cette thèse est consacrée au recalage d'images par modèles déformables. Après avoir brièvement introduit les notions de base sur les fonctions de déformation et sur leur estimation à partir de données images, nous donnons deux contributions. La première est un algorithme de recalage d'images d'une surface déformable, qui est efficace en terme de temps de calcul. Nous proposons une paramétrisation par primitives des fonctions de déformation permettant alors leur estimation par des algorithmes compositionnels habituellement réservés aux transformations formant un groupe. La deuxième contribution est la modélisation explicite des auto-occultations, en imposant la contraction de la fonction de déformation le long de la frontière d'auto-occultation. La deuxième partie de cette thèse aborde le problème de la reconstruction tridimensionnelle monoculaire de surfaces déformables. Nous nous basons sur le modèle de faible rang : les déformations sont approximées par une combinaison linéaire de modes de déformation inconnus. Nous supposons que ces derniers sont ordonnés par importance en terme d'amplitude de déformation capturée dans les images. Il en résulte une estimation hiérarchique des modes, facilitant l'emploi d'un modèle de caméra perspectif, la sélection automatique du nombre de modes et réduisant certaines ambiguïtés inhérentes au modèle. Nous explorons finalement la capture des déformations d'une surface peu texturée à partir de données issues d'un capteur 3D. L'information présente au niveau des contours de la surface est notamment utilisée. Nous avons implanté les différentes contributions décrites ci-dessous. Elles sont testées et comparées à l'état de l'art sur des données réelles et synthétiques. Les résultats sont présentés tout au long du tapuscrit.

Le LPC est un complément à la lecture labiale qui facilite la communication des malentendants. Sur le principe, il s'agit d'effectuer des gestes avec une main placée à côté du visage pour désambigüiser le mouvement des lèvres, qui pris isolément est insuffisant à la compréhension parfaite du message. Le projet RNTS TELMA a pour objectif de mettre en place un terminal téléphonique permettant la communication des malentendants en s'appuyant sur le LPC. Parmi les nombreuses fonctionnalités que cela implique, il est nécessaire de pouvoir reconnaître le geste manuel du LPC et de lui associer un sens. L'objet de ce travail est la segmentation vidéo, l'analyse et la reconnaissance des gestes de codeur LPC en situation de communication. Cela fait appel à des techniques de segmentation d'images, de classification, d'interprétation de geste, et de fusion de données. Afin de résoudre ce problème de reconnaissance de gestes, nous avons proposé plusieurs algorithmes originaux, parmi lesquels (1) un algorithme basé sur la persistance rétinienne permettant la catégorisation des images de geste cible et des images de geste de transition, (2) une amélioration des méthodes de multi-classification par SVM ou par classifieurs unaires via la théorie de l'évidence, assortie d'une méthode de conversion des probabilités subjectives en fonction de croyance, et (3) une méthode de décision partielle basée sur la généralisation de la Transformée Pignistique, afin d'autoriser les incertitudes dans l'interprétation de gestes ambigus.

La construction d'algorithmes classifiant des images à grande échelle est devenue une tache essentielle du fait de la difficulté d'effectuer des recherches dans les immenses collections de données visuelles inetiquetées présentes sur Internet. Nous visons à classifier des images en fonction de leur contenu pour simplifier la gestion de telles bases de données. La classification d'images à grande échelle est un problème complèxe, de par l'importance de la taille des ensembles de données, tant en nombre d'images qu'en nombre de classes. Certaines de ces classes sont dites "fine-grained" (sémantiquement proches les unes des autres) et peuvent même ne contenir aucun représentant étiqueté. Dans cette thèse, nous utilisons des représentations état de l'art d'images et nous concentrons sur des méthodes d'apprentissage efficaces. Nos contributions sont (1) un banc d'essai d'algorithmes d'apprentissage pour la classification à grande échelle et (2) un nouvel algorithme basé sur l'incorporation d'étiquettes pour apprendre sur des données peu abondantes. En premier lieu, nous introduisons un banc d'essai d'algorithmes d'apprentissage pour la classification à grande échelle, dans le cadre entièrement supervisé. Il compare plusieurs fonctions objectifs pour apprendre des classifieurs linéaires, tels que "un contre tous", "multiclasse", "ranking", "ranking pondéré moyen" par descente de gradient stochastique. Ce banc d'essai se conclut en un ensemble de recommandations pour la classification à grande échelle. Avec une simple repondération des données, la stratégie "un contre tous" donne des performances meilleures que toutes les autres. Par ailleurs, en apprentissage en ligne, un pas d'apprentissage assez petit s'avère suffisant pour obtenir des résultats au niveau de l'état de l'art. Enfin, l'arrêt anticipé de la descente de gradient stochastique introduit une régularisation qui améliore la vitesse d'entraînement ainsi que la capacité de régularisation. Deuxièmement, face à des milliers de classes, il est parfois difficile de rassembler suffisamment de données d'entraînement pour chacune des classes. En particulier, certaines classes peuvent être entièrement dénuées d'exemples. En conséquence, nous proposons un nouvel algorithme adapté à ce scénario d'apprentissage dit "zero-shot". notre algorithme utilise des données parallèles, comme les attributs, pour incorporer les classes dans un espace euclidien. Nous introduisons par ailleurs une fonction pour mesurer la compatibilité entre image et étiquette. Les paramètres de cette fonction sont appris en utilisant un objectif de type "ranking". Notre algorithme dépasse l'état de l'art pour l'apprentissage "zero-shot", et fait preuve d'une grande flexibilité en permettant d'incorporer d'autres sources d'information parallèle, comme des hiérarchies. Il permet en outre une transition sans heurt du cas "zero-shot" au cas où peu d'exemples sont disponibles.