De nombreuses applications en vision par ordinateur comme le filtrage, la segmentation d'images, et la stéréovision peuvent être formulées comme des problèmes d'optimisation. Récemment les méthodes discrètes, convexes, globalement optimales ont reçu beaucoup d'attention. La méthode des "graph cuts'", très utilisée en vision par ordinateur est basée sur la résolution d'un problème de flot maximum discret, mais les solutions souffrent d'un effet de blocs,notamment en segmentation d'images. Une nouvelle formulation basée sur le problème continu est introduite dans le premier chapitre et permet d'éviter cet effet. La méthode de point interieur employée permet d'optimiser le problème plus rapidement que les méthodes existantes, et la convergence est garantie. Dans le second chapitre, la formulation proposée est efficacement étendue à la restauration d'image. Grâce à une approche du à la contrainte et à un algorithme proximal parallèle, la méthode permet de restaurer (débruiter, déflouter, fusionner) des images rapidement et préserve un meilleur contraste qu'avec la méthode de variation totale classique. Le chapitre suivant met en évidence l'existence de liens entre les méthodes de segmentation "graph-cuts'", le "randomwalker'', et les plus courts chemins avec un algorithme de segmentation par ligne de partage des eaux (LPE). Ces liens ont inspiré un nouvel algorithme de segmentation multi-labels rapide produisant une ligne de partage des eaux unique, moins sensible aux fuites que la LPE classique. Nous avons nommé cet algorithme "LPE puissance''. L'expression de la LPE sous forme d'un problème d'optimisation a ouvert la voie à de nombreuses applications possibles au delà de la segmentation d'images, par exemple dans le dernier chapitre en filtrage pour l'optimisation d'un problème non convexe, en stéréovision, et en reconstruction rapide de surfaces lisses délimitant des objets à partir de nuages de points bruités / Many computer vision applications such as image filtering, segmentation and stereovision can be formulated as optimization problems. Recently discrete, convex, globally optimal methods have received a lot of attention. Many graph-based methods suffer from metrication artefacts, segmented contours are blocky in areas where contour information is lacking. In the first part of this work, we develop a discrete yet isotropic energy minimization formulation for the continuous maximum flow problem that prevents metrication errors. This new convex formulation leads us to a provably globally optimal solution. The employed interior point method can optimize the problem faster than the existing continuous methods. The energy formulation is then adapted and extended to multi-label problems, and shows improvements over existing methods. Fast parallel proximal optimization tools have been tested and adapted for the optimization of this problem. In the second part of this work, we introduce a framework that generalizes several state-of-the-art graph-based segmentation algorithms, namely graph cuts, random walker, shortest paths, and watershed. This generalization allowed us to exhibit a new case, for which we developed a globally optimal optimization method, named "Power watershed''. Our proposed power watershed algorithm computes a unique global solution to multi labeling problems, and is very fast. We further generalize and extend the framework to applications beyond image segmentation, for example image filtering optimizing an L0 norm energy, stereovision and fast and smooth surface reconstruction from a noisy cloud of 3D points

Made available in DSpace on 2017-07-21T20:56:33Z (GMT). No. of bitstreams: 1 Pedro Kiochi Kondo.pdf: 1227541 bytes, checksum: daffb8a8bc299356bce288603753944c (MD5) Previous issue date: 2014-09-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this work some topics of the Discrete or Finite Calculus are developed. In particular, we study difference operators, factorial powers, Stirling numbers of the first and second type, the Newton’s formula of differences, the fundamental theorem of the Finite Calculus, the summation process, and the Bernoulli numbers and Bernoulli polynomials. Then we show the effectiveness of the theory for the calculation of closed formulas for the value of many finite sums. We also study the classical problem of obtaining the polynomials which express the value of the sums of powers of natural numbers. / Neste trabalho desenvolvemos alguns tópicos do Cálculo Discreto ou Finito. Em particular, estudamos operadores de diferenças, potências fatoriais, números de Stirling do primeiro e do segundo tipo, a fórmula de diferenças de Newton, o teorema fundamental do Cálculo Finito, o processo de somação e os números e polinômios de Bernoulli. Mostramos então a eficácia da teoria no cálculo de fórmulas fechadas para o valor de diversas somas finitas. Também estudamos o problema clássico de obter os polinômios que expressam o valor de somas de potências de números naturais.

Many computer vision applications such as image filtering, segmentation and stereovision can be formulated as optimization problems. Recently discrete, convex, globally optimal methods have received a lot of attention. Many graph-based methods suffer from metrication artefacts, segmented contours are blocky in areas where contour information is lacking. In the first part of this work, we develop a discrete yet isotropic energy minimization formulation for the continuous maximum flow problem that prevents metrication errors. This new convex formulation leads us to a provably globally optimal solution. The employed interior point method can optimize the problem faster than the existing continuous methods. The energy formulation is then adapted and extended to multi-label problems, and shows improvements over existing methods. Fast parallel proximal optimization tools have been tested and adapted for the optimization of this problem. In the second part of this work, we introduce a framework that generalizes several state-of-the-art graph-based segmentation algorithms, namely graph cuts, random walker, shortest paths, and watershed. This generalization allowed us to exhibit a new case, for which we developed a globally optimal optimization method, named "Power watershed''. Our proposed power watershed algorithm computes a unique global solution to multi labeling problems, and is very fast. We further generalize and extend the framework to applications beyond image segmentation, for example image filtering optimizing an L0 norm energy, stereovision and fast and smooth surface reconstruction from a noisy cloud of 3D points

Dans cette thèse, nous nous intéressons à la fois aux aspects théoriques et à la résolution numérique du problème de Mumford-Shah avec anisotropie pour la restauration et la segmentation d'image. Cette fonctionnelle possède en effet la particularité de reconstruire une image dégradée tout en extrayant l'ensemble des contours des régions d'intérêt au sein de l'image. Numériquement, on utilise l'approximation d'Ambrosio-Tortorelli pour approcher un minimiseur de la fonctionnelle de Mumford-Shah. Elle Gamma-converge vers cette dernière et permet elle aussi d'extraire les contours. Les implémentations avec des schémas aux différences finies ou aux éléments finis sont toutefois peu adaptées pour l'optimisation de la fonctionnelle d'Ambrosio-Tortorelli. On présente ainsi deux nouvelles formulations discrètes de la fonctionnelle d'Ambrosio-Tortorelli à l'aide des opérateurs et du formalisme du calcul discret. Ces approches sont utilisées pour la restauration d'images ainsi que pour le lissage du champ de normales et la détection de saillances des surfaces digitales de l'espace. Nous étudions aussi un second problème d'optimisation de forme similaire avec conditions aux bords de Robin. Nous démontrons dans un premier temps l'existence et la régularité partielle des solutions, et dans un second temps deux approximations par Gamma-convergence pour la résolution numérique du problème. L'analyse numérique montre une nouvelle fois les difficultés rencontrées pour la minimisation d'approximations par Gamma-convergence. / In this work, we study both theoretical and numerical aspects of an anisotropic Mumford-Shah problem for image restoration and segmentation. The Mumford-Shah functional allows to both reconstruct a degraded image and extract the contours of the region of interest. Numerically, we use the Amborsio-Tortorelli approximation to approach a minimizer of the Mumford-Shah functional. It Gamma-converges to the Mumford-Shah functional and allows also to extract the contours. However, the minimization of the Ambrosio-Tortorelli functional using standard discretization schemes such as finite differences or finite elements leads to difficulties. We thus present two new discrete formulations of the Ambrosio-Tortorelli functional using the framework of discrete calculus. We use these approaches for image restoration and for the reconstruction of normal vector field and feature extraction on digital data. We finally study another similar shape optimization problem with Robin boundary conditions. We first prove existence and partial regularity of solutions and then construct and demonstrate the Gamma-convergence of two approximations. Numerical analysis shows once again the difficulties dealing with Gamma-convergent approximations.