Optimisation variationnelle discrète et applications en vision par ordinateur
Variational optimization
Résumé
Many computer vision applications such as image filtering, segmentation and stereo-vision reconstruction may be formulated as optimization problems. Recently discrete, convex, globally optimal methods have received a lot of attention. However, a drawback of several graph-based methods is the presence of blockiness artifacts. 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 energy formulation is then adapted and extended to multi-label problems, and shows improvements over classical weighted total variation methods. Fast parallel proximal optimization tools have been tested and adapted for the optimization of restoration problems. 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 allows us to exhibit a new case, for which we develop a globally optimal optimization method: "power watershed''. Our proposed power watershed algorithm computes a unique global solution to multi-label 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, stereo-vision and fast and smooth surface reconstruction from a noisy cloud of 3D points.
De nombreuses applications en vision par ordinateur comme le filtrage, la segmentation d'images, et la stéréo-vision peuvent être formulées comme des problèmes d'optimisation. Récemment les méthodes discrètes et globalement optimales ont reçu beaucoup d'attention. La méthode des coupes minimales, 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 et permet d'éviter cet effet. La méthode de point intérieur employée permet d'optimiser le problème plus rapidement que les méthodes existantes, et la convergence est garantie. La formulation proposée est ensuite efficacement étendue à la restauration d'image. Grâce à une approche duale contrainte et à un algorithme proximal parallèle, cette nouvelle approche permet de restaurer des images et des données arbitraires modélisées par des graphes rapidement et préserve un meilleur contraste qu'avec la méthode de variation totale classique. La seconde partie de cette thèse met en évidence l'existence de liens entre les méthodes de segmentation des coupes minimales, le marcheur aléatoire, 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 en filtrage pour l'optimisation d'un problème non convexe, en stéréo-vision, et en reconstruction rapide de surfaces lisses délimitant des objets à partir de nuages de points bruités.