Cette thèse développe de nouvelles approches pour l'effacement et la révélation de la présence humaine en utilisant des techniques de réalité augmentée. Elle se concentre sur les systèmes projecteur-caméra (ProCams) et leur application dans les «projections intelligentes», où le contenu virtuel projeté est adapté en fonction de l'environnement. Nous nous appuyons sur les travaux antérieurs sur la compensation photométrique pour projeter sur une surface colorée fixe qui permet au spectateur d'observer la même image telle qu'elle apparaîtrait sur une surface blanche. Malgré les différentes méthodes de compensation des couleurs qui ont été proposées au cours de décennie, la compensation appliquée à monde réel avec des couleurs saturées et vives est encore une question ouverte. L'objectif principal de ce travail est la compensation photométrique sur un objet 3D en mouvement en utilisant un ProCam, ce qui est un scénario considérablement plus difficile. Une nouvelle méthode pour la compensation de couleur à l'aide d'une image d'entrée unique est proposée. Elle consiste à estimer la réflectance spectrale de la surface afin de compenser celle-ci en supposant que les réponses du projecteur sont connues ou mesurées précédemment. Cette méthode a été entièrement développée sur GPU pour permettre une compensation en temps réel. Les méthodes antérieures sur la compensation couleur sont discutées et comparées afin d'évaluer la performance de notre technique. L'étalonnage photométrique et géométrique précis d'un ProCam est essentiel pour une compensation précise. Une nouvelle technique de calibration géométrique entre un capteur de profondeur et un ProCam est présentée dans le but de réaliser la projection sur un objet en mouvement. Une calibration photométrique est décrite pour la transformation des valeurs RGB de la caméra et du projecteur (dépendantes du périphérique) vers l'espace couleur CIE XYZ 1931 (indépendantes du périphérique). Le potentiel artistique des techniques de réalité augmentée proposées est en outre exploré à travers l'installation interactive artistique “Gardien du Temple”. La révélation et l'effacement ont toujours été un terrain d'expérimentation commun aux artistes et aux scientifiques. Cette installation audiovisuelle utilise la réalité augmentée pour effacer la présence d'un poème écrit sur un tapis invitant le spectateur à le révéler. Dans de telles applications, la précision et la robustesse des méthodes utilisées sont cruciales. Cette installation artistique a donc permis de tester et d'évaluer les travaux de cette thèse dans un contexte collaboratif et exigeant. / This thesis develops new approaches for human presence concealment and revelation using augmented reality techniques. It focuses on projector-camera systems (ProCams) and their application in “smart projections”, where the projected virtual content is adapted according to the environment. One previously-studied problem is the photometric compensation for projecting on a colored fixed surface that allows the viewer to observe the same image as it would appear on a white surface. Despite the various methods for color compensation that have been proposed the last decade, compensation on a real-world surface with saturated colors and sharp color boundaries is still an open issue. The main objective of this work is the color compensation on a moving 3D object using a ProCam, which is a dramatically more challenging scenario. A novel method for color compensation using a single input frame is proposed. It consists in estimating the spectral reflectance of the surface in order to compensate for it under the assumption that the projector responses are known or previously measured. This method was fully developed on GPU to enable real-time compensation. Previous methods on color compensation are discussed and compared in order to evaluate the performance of our technique. The accurate photometric and geometric calibration of a ProCam is essential for precise compensation. A new geometric calibration technique between a depth sensor and a ProCam is presented in order to make the projection on a moving object feasible. A photometric calibration is described for the transformation of the device-dependent camera and projector values to the device-independent CIE XYZ 1931 color space. The artistic potential of the proposed augmented reality techniques is further explored through the interactive art installation “Gardien du Temple”. Revelation and concealment has always been a common experimentation ground for both artists and scientists. This audio visual installation uses augmented reality to hide the presence of a written poem on a carpet inviting the spectator to reveal it. In such applications, the accuracy and robust performance of the methods employed is crucial and, thus, it offered a challenging ground for testing and evaluation.

Par opposition à la Réalité Augmentée qui consiste à ajouter des éléments virtuels à un environnement réel, la Réalité Diminuée consiste à supprimer des éléments réels d'un environnement. Le but est d'effectuer un rendu visuel d'une scène 3D où les éléments "effacés" ne sont plus présents : la difficulté consiste à créer une image de sorte que la diminution ne soit pas perceptible par l'utilisateur. Il faut donc venir compléter la scène initialement cachée par ces éléments, en effectuant une opération d'inpainting qui prenne en compte la géométrie de la pièce, sa texture (structurée ou non), et la luminosité ambiante de l'environnement. Par exemple, l’œil humain est sensible à la régularité d'une texture. L'un des objectifs d'Innersense, entreprise spécialisée dans l'aménagement virtuel d’intérieurs, est de développer un produit capable d'enlever des éléments présents dans une pièce d'intérieur. Une fois la suppression virtuelle des meubles existants effectuée , il sera alors possible d'ajouter des meubles virtuels dans l'espace laissé vacant. L'objectif de cette thèse CIFRE est donc de mettre en place un scénario de réalité diminuée pouvant être exécuté sur un système mobile (tablette IOS ou Android) qui génère des images photo-réalistes de la scène diminuée. Pour cela, à partir d’un modèle géométrique de la pièce d'intérieur que l'on veut altérer, nous adaptons et améliorons des procédures d'effacement d'éléments d'une image appelées inpainting dans une image 2D. Ensuite, nous appliquons ces techniques dans le contexte 3D intérieur pour tenir compte de la géométrie de la scène. Enfin, nous analysons la luminosité pour augmenter le réalisme des zones complétées.Dans cette thèse, nous rappelons d'abord les différents travaux académiques et les solutions industrielles existantes. Nous évoquons leurs avantages et leurs limites. Nous abordons ensuite les différentes techniques d'inpainting existantes pour introduire notre première contribution qui propose d'adapter une des méthodes de l’état de l’art pour prendre en compte de la structure du motif de la texture. La problématique de la luminosité est ensuite abordée en proposant un processus qui traite séparément la texture et la variation de la luminosité. Nous présentons ensuite une troisième contribution qui propose un critère de confiance basé sur des considérations radiométriques pour sélectionner une information selon sa qualité dans le processus d'inpainting. Nous proposons une dernière contribution basée sur la complétion de texture de modèles 3D non planaires reconstruits à partir de peu d’images et donc présentant une texture incomplète. Enfin, nous montrons les applications développées grâce à ces travaux dans le contexte des scènes d'intérieur considérées par Innersense / In contrast to Augmented Reality, which consists in adding virtual elements to a real environment,Diminished Reality consists in removing real elements from an environment. The goal is to visuallyrender a 3D scene where the "deleted" elements are no longer present: the difficulty is to createan image so that the processing is not perceptible to the user. It is therefore necessary tocomplete the scene initially hidden by these elements, by performing an inpainting operation thattakes into account the geometry of the part, its texture (structured or not), and the ambientbrightness of the environment. For example, the human eye is sensitive to the regularity of atexture. One of the objectives of Innersense, a company specializing in virtual interior design, is todevelop a product that can remove elements from an interior room. Once the virtual removal ofexisting furniture has been completed, it will then be possible to add virtual furniture in the vacantspace. The objective of this CIFRE thesis is therefore to set up a scenario of diminished realitythat can be executed on a mobile system (IOS or Android tablet) that generates photorealisticimages of the diminished scene. To do this, based on a geometric model of the interior part thatwe want to alter, we adapt and improve procedures for erasing elements of an image calledinpainting in a 2D image. Then, we apply these techniques in the 3D indoor context to take intoaccount the geometry of the scene. Finally, we analyze the brightness to increase the realism ofthe completed areas. In this thesis, we first review the various academic works and existingindustrial solutions. We discuss their advantages and limitations. We then discuss the differentexisting inpainting techniques to introduce our first contribution which proposes to adapt one of thestate of the art methods to take into account the structure of the texture pattern. The problem ofbrightness is then discussed by proposing a process that deals separately with texture andvariation of brightness. We then present a third contribution that proposes a confidence criterionbased on radiometric considerations to select information according to its quality in the inpaintingprocess. We propose a last contribution based on the texture completion of non-planar 3D modelsreconstructed from few images and therefore presenting an incomplete texture. Finally, we showthe applications developed through this work in the context of the interior scenes considered byInnersense.

Le trafic routier est devenu de plus en plus intense. Une telle situation avec le manque de prudence des piétons constituent deux causes majeures de l’augmentation des accidents routiers. En France, 16% des accidents de la route en 2016 impliquent au moins un piéton et chaque année, environ de 800 piétons sont tués dans un accident de la circulation. De plus, la part des plus de 65 ans dans la mortalité piétonne est en hausse de 13% entre 2014 et 2016. Ainsi, par ce projet de thèse nous proposons une approche probabiliste pour inférer le type de comportement (à risque ou sécurisé) des piétons lors de la traversé de la rue. Cette approche se compose de 2 couches principales : Une couche basse, basée sur les techniques de vision par ordinateur, pour la collecte des paramètres des piétons, du trafic et des aménagements urbains et une couche haute, basée sur le Réseau Bayésien (RB), pour l’inférence du type de comportement. Plusieurs contributions et améliorations sont proposées pour la construction d’une telle approche que ce soit au niveau de la couche basse (techniques de détection et de suivi utilisées) ou au niveau de la couche haute (gestion des incertitudes des capteurs de vision et la mise en relation des paramètres hétérogènes et variées). / Road traffic has become more and more intense. Such as situation with thelack of attention of pedestrians are the two major causes of the increase in road accidents. In France, 16% of road accidents in 2016 involve at least one pedestrian and each year about 800 pedestrians are killed in a traffic accident. In addition, the proportion of pedestrian deaths having over 65 years old is up to 13% between 2014 and 2016. In fact, this thesis proposes a probabilistic approach to recognize pedestrians’ behavior (risky or secure) when crossing the street. This approach consists of two main layers: a low layer, based on computer vision techniques, for collecting pedestrian and traffic parameters and a high layer, based on the Bayesian Network, for behavior prediction. Several contributions and improvements are proposed for the construction of such an approach, whether at the level of the low layer (detection and tracking process) or at the level of the upper layer (management of the uncertainties of the vision sensors and the correlation of heterogeneous and varied parameters).

Dans cette thèse, nous avons étudié le problème de l'estimation de mouvement chez les mammifères et nous proposons que passer à l’échelle des modèles ancrés dans la biologie pour les applications du monde réel peut nous donner de nouvelles perspectives en vision biologique. En utilisant un modèle classique qui décrit l'activité des neurones dans les aires corticales V1 et MT du cerveau des primates, nous avons proposé une architecture montante pour l'estimation de mouvement et l’avons évaluée sur des exemples de référence de vision par ordinateur (une première pour ce type de modèles), révélant des lacunes telles que le manque de sélectivité au niveau des frontières de mouvement et l'absence d'association spatiale du champ de vitesses. Pour y remédier, nous avons proposé deux extensions, une stratégie d’intégration modulée par la forme pour minimiser les erreurs aux discontinuités de texture et un schéma de régression pour le décodage. Ces extensions ont amélioré la précision de l'estimation, mais aussi souligné à nouveau le débat sur le rôle des différents types de cellules dans le codage mouvement, par exemple le rôle relatif des cellules “pattern” par rapport aux cellules “component”. Pour comprendre cela, nous avons utilisé un modèle de champs neuronaux représentant une population de cellules MT pour comprendre le rôle des récurrences. Nos résultats montrent qu'une variété de comportements peuvent être reproduits, ils expliquent les changements dynamiques en fonction des stimuli, et nous conduisent à remettre en cause les régimes élevés d'inhibition généralement choisis dans la littérature. / In this thesis, we studied the problem of motion estimation in mammals and propose that scaling up models rooted in biology for real world applications can give us fresh insights into the biological vision. Using a classic model that describes the activity of directionally-selective neurons in V1 and MT areas of macaque brain, we proposed a feedforward V1-MT architecture for motion estimation and benchmarked it on computer vision datasets (first publicly available evaluation for this kind of models), revealing interesting shortcomings such as lack of selectivity at motion boundaries and lack of spatial association of the flow field. To address these, we proposed two extensions, a form modulated pooling strategy to minimize errors at texture boundaries and a regression based decoding scheme. These extensions improved estimation accuracy but also reemphasized the debate about the role of different cell types (characterized by their tuning curves) in encoding motion, for example relative role of pattern cells versus component cells. To understand this, we used a phenomenological neural fields model representative of a population of directionally tuned MT cells to check whether different tuning behaviors could be reproduced by a recurrently interacting population or if we need different types of cells explicitly. Our results indicated that a variety of tuning behavior can be reproduced by a minimal network, explaining dynamical changes in the tuning with change of stimuli leading us to question the high inhibition regimes typically considered by models in the literature.

La classification des images revêt un intérêt majeur dans de nombreuses tâches de reconnaissance visuelle, en particulier pour la reconnaissance de véhicules au sol via les systèmes aéroportés, où les images traitées sont de faible résolution du fait de la large distance entre le porteur et la scène observée. Durant l'apprentissage, des données complémentaires peuvent être disponibles, qu'il s'agisse de connaissances sur les conditions de prise de vue ou de la version haute-résolution des images. Dans nos travaux, on s'intéresse au problème de la reconnaissance d'images faiblement résolues en prenant en compte des informations complémentaires pendant l'apprentissage. On montre d'abord l'intérêt des réseaux convolutionnels profonds pour la reconnaissance d'images faiblement résolues, en proposant notamment une architecture apprise sur les données. D'autre part, on s'appuie sur le cadre de l'apprentissage avec information privilégiée pour bénéficier des données d'entraînement complémentaires, ici les versions haute-résolution des images. Nous proposons deux méthodes d'intégration de l'information privilégiée dans l'apprentissage des réseaux de neurones. Notre premier modèle s'appuie sur ces données complémentaires pour calculer un niveau de difficulté absolue, attribuant un poids important aux images les plus facilement reconnaissables. Notre deuxième modèle introduit une contrainte de similitude entre les modèles appris sur chaque type de données. On valide expérimentalement nos deux modèles dans plusieurs cas d'application, notamment dans un contexte orienté grain-fin et sur une base de données contenant du bruit d'annotation. / Image classification has a prominent interest in numerous visual recognition tasks, particularly for vehicle recognition in airborne systems, where the images have a low resolution because of the large distance between the system and the observed scene. During the training phase, complementary data such as knowledge on the position of the system or high-resolution images may be available. In our work, we focus on the task of low-resolution image classification while taking into account supplementary information during the training phase. We first show the interest of deep convolutional networks for the low-resolution image recognition, especially by proposing an architecture learned on the targeted data. On the other hand, we rely on the framework of learning using privileged information to benefit from the complementary training data, here the high-resolution versions of the images. We propose two novel methods for integrating privileged information in the learning phase of neural networks. Our first model relies on these complementary data to compute an absolute difficulty level, assigning a large weight to the most easily recognized images. Our second model introduces a similarity constraint between the networks learned on each type of data. We experimentally validate our models on several application cases, especially in a fine-grained oriented context and on a dataset containing annotation noise.

Cette thèse s'intéresse au problème de la classification d'images, où l'objectif est de prédire si une catégorie sémantique est présente dans l'image, à partir de son contenu visuel. Pour analyser des images de scènes complexes, il est important d'apprendre des représentations localisées. Pour limiter le coût d'annotation pendant l'apprentissage, nous nous sommes intéressé aux modèles d'apprentissage faiblement supervisé. Dans cette thèse, nous proposons des modèles qui simultanément classifient et localisent les objets, en utilisant uniquement des labels globaux pendant l'apprentissage. L'apprentissage faiblement supervisé permet de réduire le cout d'annotation, mais en contrepartie l'apprentissage est plus difficile. Le problème principal est comment agréger les informations locales (e.g. régions) en une information globale (e.g. image). La contribution principale de cette thèse est la conception de nouvelles fonctions de pooling (agrégation) pour l'apprentissage faiblement supervisé. En particulier, nous proposons une fonction de pooling « max+min », qui unifie de nombreuses fonctions de pooling. Nous décrivons comment utiliser ce pooling dans le framework Latent Structured SVM ainsi que dans des réseaux de neurones convolutifs. Pour résoudre les problèmes d'optimisation, nous présentons plusieurs solveurs, dont certains qui permettent d'optimiser une métrique d'ordonnancement (ranking) comme l'Average Precision. Expérimentalement, nous montrons l'intérêt nos modèles par rapport aux méthodes de l'état de l'art, sur dix bases de données standard de classification d'images, incluant ImageNet. / This thesis studies the problem of classification of images, where the goal is to predict if a semantic category is present in the image, based on its visual content. To analyze complex scenes, it is important to learn localized representations. To limit the cost of annotation during training, we have focused on weakly supervised learning approaches. In this thesis, we propose several models that simultaneously classify and localize objects, using only global labels during training. The weak supervision significantly reduces the cost of full annotation, but it makes learning more challenging. The key issue is how to aggregate local scores - e.g. regions - into global score - e.g. image. The main contribution of this thesis is the design of new pooling functions for weakly supervised learning. In particular, we propose a “max + min” pooling function, which unifies many pooling functions. We describe how to use this pooling in the Latent Structured SVM framework as well as in convolutional networks. To solve the optimization problems, we present several solvers, some of which allow to optimize a ranking metric such as Average Precision. We experimentally show the interest of our models with respect to state-of-the-art methods, on ten standard image classification datasets, including the large-scale dataset ImageNet.

Les plissements du cortex caractérisent de manière unique chaque être humain. Ils apparaissent pendant le dernier trimestre de grossesse, c’est-à-dire pendant la mise en place de l’architecture cérébrale. Les motifs de ces plis sont impactés par les spécificités de cette architecture propres à chaque individu. Ils pourraient donc dévoiler les signatures de certaines anomalies du développement à l’origine de pathologies psychiatriques. Le laboratoire d’analyse d’images de Neurospin développe depuis 25 ans un programme de recherche visant à mettre en évidence de telles signatures grâce à la conception d’outils de vision par ordinateur dédiés qu’il diffuse à la communauté (http://brainvisa.info).Cette thèse a permis l’émergence d’une nouvelle génération d’outils basés sur des techniques d’apprentissage automatique. Le premier outil proposé classifie automatiquement des motifs locaux de plissements du cortex, un problème qui n’avait jamais été abordé jusqu’ici. Le second outil vise l’étiquetage automatique des sillons corticaux en modélisant des mécanismes de reconnaissance « top-down » nécessaires pour pallier les faiblesses des démarches « bottom-up » développées jusqu’à présent. Ainsi, en plus d'avoir des taux de reconnaissances plus élevés et un temps d’exécution plus court, le nouveau modèle proposé est robuste aux erreurs de sous-segmentation, ce qui est l'une des plus grandes faiblesses de l'ancien système. Pour réaliser ces deux outils, plusieurs algorithmes d'apprentissage automatique ont été implémentés et comparés. Ces algorithmes s'inspirent d'une part des méthodes multi-atlas, en particulier de l'approche par patch, qui sont largement utilisées pour la segmentation anatomique d'images médicales et d'autre part des méthodes d'apprentissage profond qui révolutionnent aujourd'hui le monde de la vision par ordinateur. Les travaux de cette thèse confirment l'incroyable efficacité des techniques d'apprentissage profond pour s'adapter à des problèmes complexes. Cependant, les performances obtenues avec ces techniques sont généralement équivalentes à celles des approches par patch, voire moins bonnes si la base de données d'apprentissage est restreinte. Ce qui fait de l'apprentissage profond un outil particulièrement intéressant en pratique n'est autre que sa rapidité d'exécution, d'autant plus pour l'analyse des bases de données colossales aujourd'hui disponibles. / We are seven billion humans with unique cortical folding patterns. The cortical folding process occurs during the last trimester of pregnancy, during the emergence of cortical architecture. The folding patterns are impacted by architectural features specific to each individual. Hence, they could reveal signatures of abnormal developments that can lead to psychiatric syndroms. For the last 25 years, the image analysis lab of Neurospin has been designing dedicated computer vision tools to tackle the research of such signatures. The resulting tools are distributed to the community (http://brainvisa.info).This thesis has resulted in the emergence of a new generation of tools based on machine learning techniques. The first proposed tool automatically classifies local patterns of cortical folds, a problem that had never been addressed before. The second tool aims at the automatic labeling of cortical sulci by modeling the top-down recognition mechanisms necessary to overcome weaknesses of the current bottom-up systems. Thus, in addition to having higher recognition rates and shorter execution time, the proposed new model is robust to sub-segmentation errors, which is one of the greatest weaknesses of the old system. To realize these two tools, several machine learning algorithms were implemented and compared. These algorithms are inspired on the one hand by multi-atlas methods, in particular the patch approach, which are widely used for the anatomical segmentation of medical images and on the other hand by the deep learning methods that are revolutionizing the world of computer vision. The work of this thesis confirms the incredible effectiveness of deep learning techniques to adapt well to complex problems. However, the performances obtained with these techniques are generally equivalent to those of patch approaches, or even worse if the training database is limited. What makes deep learning a particularly interesting tool in practice is its fast execution, especially for the analysis of the huge databases now available.

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.