Dans cette thèse, nous proposons une méthode de résolution des problèmes de la géométrie algorithmique posés pour des objets courbes (par opposition aux objets "linéaires" : ensembles de points, segments, polygones ...). Les objets que nous étudions sont des courbes de Bézier composites, choisies, d'une part, pour le réalisme qu'elles assurent dans la modélisation géométrique, et d'autre part, pour la facilité du traitement algorithmique que leurs propriétés offrent. Notre approche met l'accent sur les aspects topologiques des problèmes abordés, en évitant les incohérences que la résolution en arithmétique flottante d'équations algébriques de degré élevé (générées par le traitement direct des courbes) peut le plus souvent introduire. Cet objectif est atteint par l'utilisation d'approximations polygonales convergentes, qui dans le cas des courbes de Bézier sont naturellement fournies par les polygones de controle par l'intermédiaire de la subdivision de de Casteljau. Deux des problèmes fondamentaux de la géométrie algorithmique sont traités ici, l'enveloppe convexe et les arrangements, les deux en dimension 2. Dans le cas des arrangements, la notion de topologie (combinatoire) est bien connue ; dans celui de l'enveloppe convexe, nous la définissons rigoureusement. Pour les deux problèmes, nous montrons qu'il est possible d'obtenir toute l'information topologique définissant (de manière, il est vrai, implicite, mais correcte et complète) la solution exacte en travaillant exclusivement sur les approximations polygonales des objets donnés. Les résultats théoriques obtenus sont concrétisés par des algorithmes dont la convergence et la correction sont démontrées et pour lesquels des études de cout sont réalisées. Des exemples illustrent le fonctionnement de ces algorithmes, validant la méthode proposée.

Dans cette thèse nous développons une technique de déformation pour l'optimisation de formes. Les formes sont représentées par leur frontière, paramétrée par des courbes de Bézier par morceaux. En tant que courbes polynomiales, elles sont définies par leurs coefficients que l'on appelle plutôt points de contrôle. Bouger les points de contrôle revient à modifier la courbe et donc déplacer la frontière des formes. Dans un contexte d'optimisation de formes, ce sont alors les points de contrôle qui sont les variables du problème et l'on a transformé ce dernier en un problème d'optimisation paramétrique. Notre méthode de déformation consiste en un premier temps à paramétrer les frontières par des courbes de Bézier comme indiqué plus haut et dans un second temps à calculer une déformation des points de contrôle à partir d'une direction de descente de la fonction objectif. Notre méthode est de nature géométrique mais l'on propose un moyen de changer la topologie des formes en mesurant la distance entre les points de contrôle : on peut scinder une forme en deux ou inversement en réunir deux en une. Nous avons testé la méthode sur trois problèmes qui sont la conception d'un filtre micro-ondes, la détection d'inclusions et les trajectoires optimales. / We develop a deformation technique for shape optimization problems. The shapes are described only by their boundary, parameterized by piecewise Bézier curves. They are polynomial curves hence entirely defined by their coefficients which are called control points. By moving these control points the curves change and so is the boundary of the shape. Used in a shape optimization problem, the control points become the optimization variables meaning that the problem is a parametric optimization problem. Our method consists in first parameterizing the boundary of a shape by Bézier curves as stated above and then compute a deformation of the control points from a descent direction for the objective function. The method is almost purely geometric but we add a way to include topological changes by diving a shape into two or conversly merging two shapes into one. We tested our method on three particular shape optimization problems which are microwave filter design, inclusions detection and optimal trajectories.

Les artistes apprécient les images vectorielles car elles sont compactes et facilement manipulables. Cependant, beaucoup d’artistes expriment leur créativité en dessinant, en peignant ou encore en prenant des photographies. Digitaliser ces contenus produit des images rasterisées. L’objectif de cette thèse est de convertir des images rasterisées en images vectorielles qui sont facilement manipulables. Nous avons formulé le problème de vectorisation comme un problème de minimisation d’énergie que nous avons défini par deux termes. Le premier terme, plutôt classique, mesure la fidélité de l’image vectorielle générée avec l’image rasterisée d’origine. La nouveauté principale est le second terme qui mesure la simplicité de l’image vectorielle générée. Le terme de simplicité est global et contient des variables discrètes, ce qui rend sa minimisation difficile. Nous avons proposé deux algorithmes de vectorisation : un pour la vectorisation de croquis et un autre pour la vectorisation multicouches d’images couleurs. Ces deux algorithmes commencent par extraire des primitives géométriques (un squelette pour les croquis et une segmentation pour les images couleurs) qu’ils assemblent ensuite pour former l’image vectorielle. Dans la dernière partie de la thèse, nous proposons un nouvel algorithme qui est capable de vectoriser des croquis sans étapes préliminaires : on extrait et assemble les primitives simultanément. Nous montrons le potentiel de ce nouvel algorithme pour une variété de problèmes de vision par ordinateur comme l’extraction de réseaux linéiques, l’extraction d’objets et la compression d’images. / Artists appreciate vector graphics for their compactness and editability. However many artists express their creativity by sketching, painting or taking photographs. Digitizing these images produces raster graphics. The goal of this thesis is to convert raster graphics into vector graphics that are easy to edit. We cast image vectorization as an energy minimization problem. Our energy is a combination of two terms. The first term measures the fidelity of the vector graphics to the input raster graphics. This term is a standard term for image reconstruction problems. The main novelty is the second term which measures the simplicity of the vector graphics. The simplicity term is global and involves discrete unknowns which makes its minimization challenging. We propose two stochastic optimizations for this formulation: one for the line drawing vectorization problem and another one for the color image vectorization problem. These optimizations start by extracting geometric primitives (skeleton for sketches and segmentation for color images) and then assembling these primitives together to form the vector graphics. In the last chapter we propose a generic optimization method for the problem of geometric shape extraction. This new algorithm does not require any preprocessing step. We show its efficiency in a variety of vision problems including line network extraction, object contouring and image compression.