Nous présentons une nouvelle méthode pour la restauration d'images sismiques. Quand on l'observe, une image sismique est le résultat d'un système de dépôt initial qui a été transformé par un ensemble de déformations géologiques successives (flexions, glissement de la faille, etc) qui se sont produites sur une grande période de temps. L'objectif de la restauration sismique consiste à inverser les déformations pour fournir une image résultante qui représente le système de dépôt géologique tel qu'il était dans un état antérieur. Classiquement, ce procédé permet de tester la cohérence des hypothèses d'interprétations formulées par les géophysiciens sur les images initiales. Dans notre contribution, nous fournissons un outil qui permet de générer rapidement des images restaurées et qui aide donc les géophysiciens à reconnaître et identifier les caractéristiques géologiques qui peuvent être très fortement modifiées et donc difficilement identifiables dans l'image observée d'origine. Cette application permet alors d'assister ces géophysiciens pour la formulation d'hypothèses d'interprétation des images sismiques. L'approche que nous introduisons est basée sur un processus de minimisation qui exprime les déformations géologiques en termes de contraintes géométriques. Nous utilisons une approche itérative de Gauss-Newton qui converge rapidement pour résoudre le système. Dans une deuxième partie de notre travail nous montrons différents résultats obtenus dans des cas concrets afin d'illustrer le processus de restauration d'image sismique sur des données réelles et de montrer comment la version restaurée peut être utilisée dans un cadre d'interprétation géologique.

Les approches bayésiennes sont largement utilisées dans le domaine du traitement du signal. Elles utilisent des informations a priori sur les paramètres inconnus à estimer ainsi que des informations sur les observations, pour construire des estimateurs. L'estimateur optimal au sens du coût quadratique est l'un des estimateurs les plus couramment employés. Toutefois, comme la loi a posteriori exacte a très souvent une forme complexe, il faut généralement recourir à des outils d'approximation bayésiens pour l'approcher. Dans ce travail, nous nous intéressons particulièrement à deux types de méthodes: les algorithmes d'échantillonnage Monte Carlo par chaînes de Markov (MCMC) et les approches basées sur des approximations bayésiennes variationnelles (VBA).La thèse est composée de deux parties. La première partie concerne les algorithmes d'échantillonnage. Dans un premier temps, une attention particulière est consacrée à l'amélioration des méthodes MCMC basées sur la discrétisation de la diffusion de Langevin. Nous proposons une nouvelle méthode pour régler la composante directionnelle de tels algorithmes en utilisant une stratégie de Majoration-Minimisation ayant des propriétés de convergence garanties. Les résultats expérimentaux obtenus lors de la restauration d'un signal parcimonieux confirment la rapidité de cette nouvelle approche par rapport à l'échantillonneur usuel de Langevin. Dans un second temps, une nouvelle méthode d'échantillonnage basée sur une stratégie d'augmentation des données est proposée pour améliorer la vitesse de convergence et les propriétés de mélange des algorithmes d'échantillonnage standards. L'application de notre méthode à différents exemples en traitement d'images montre sa capacité à surmonter les difficultés liées à la présence de corrélations hétérogènes entre les coefficients du signal.Dans la seconde partie de la thèse, nous proposons de recourir aux techniques VBA pour la restauration de signaux dégradés par un bruit non-gaussien. Afin de contourner les difficultés liées à la forme compliquée de la loi a posteriori, une stratégie de majoration est employée pour approximer la vraisemblance des données ainsi que la densité de la loi a priori. Grâce à sa flexibilité, notre méthode peut être appliquée à une large classe de modèles et permet d'estimer le signal d'intérêt conjointement au paramètre de régularisation associé à la loi a priori. L'application de cette approche sur des exemples de déconvolution d'images en présence d'un bruit mixte Poisson-gaussien, confirme ses bonnes performances par rapport à des méthodes supervisées de l'état de l'art. / Bayesian approaches are widely used in signal processing applications. In order to derive plausible estimates of original parameters from their distorted observations, they rely on the posterior distribution that incorporates prior knowledge about the unknown parameters as well as informations about the observations. The posterior mean estimator is one of the most commonly used inference rule. However, as the exact posterior distribution is very often intractable, one has to resort to some Bayesian approximation tools to approximate it. In this work, we are mainly interested in two particular Bayesian methods, namely Markov Chain Monte Carlo (MCMC) sampling algorithms and Variational Bayes approximations (VBA).This thesis is made of two parts. The first one is dedicated to sampling algorithms. First, a special attention is devoted to the improvement of MCMC methods based on the discretization of the Langevin diffusion. We propose a novel method for tuning the directional component of such algorithms using a Majorization-Minimization strategy with guaranteed convergence properties.Experimental results on the restoration of a sparse signal confirm the performance of this new approach compared with the standard Langevin sampler. Second, a new sampling algorithm based on a Data Augmentation strategy, is proposed to improve the convergence speed and the mixing properties of standard MCMC sampling algorithms. Our methodological contributions are validated on various applications in image processing showing the great potentiality of the proposed method to manage problems with heterogeneous correlations between the signal coefficients.In the second part, we propose to resort to VBA techniques to build a fast estimation algorithm for restoring signals corrupted with non-Gaussian noise. In order to circumvent the difficulties raised by the intricate form of the true posterior distribution, a majorization technique is employed to approximate either the data fidelity term or the prior density. Thanks to its flexibility, the proposed approach can be applied to a broad range of data fidelity terms allowing us to estimate the target signal jointly with the associated regularization parameter. Illustration of this approach through examples of image deconvolution in the presence of mixed Poisson-Gaussian noise, show the good performance of the proposed algorithm compared with state of the art supervised methods.

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

Nous présentons une nouvelle méthode pour la restauration d'images sismiques. Quand on l'observe, une image sismique est le résultat d'un système de dépôt initial qui a été transformé par un ensemble de déformations géologiques successives (flexions, glissement de la faille, etc) qui se sont produites sur une grande période de temps. L'objectif de la restauration sismique consiste à inverser les déformations pour fournir une image résultante qui représente le système de dépôt géologique tel qu'il était dans un état antérieur. Classiquement, ce procédé permet de tester la cohérence des hypothèses d'interprétations formulées par les géophysiciens sur les images initiales. Dans notre contribution, nous fournissons un outil qui permet de générer rapidement des images restaurées et qui aide donc les géophysiciens à reconnaître et identifier les caractéristiques géologiques qui peuvent être très fortement modifiées et donc difficilement identifiables dans l'image observée d'origine. Cette application permet alors d'assister ces géophysiciens pour la formulation d'hypothèses d'interprétation des images sismiques. L'approche que nous introduisons est basée sur un processus de minimisation qui exprime les déformations géologiques en termes de contraintes géométriques. Nous utilisons une approche itérative de Gauss-Newton qui converge rapidement pour résoudre le système. Dans une deuxième partie de notre travail nous montrons différents résultats obtenus dans des cas concrets afin d'illustrer le processus de restauration d'image sismique sur des données réelles et de montrer comment la version restaurée peut être utilisée dans un cadre d'interprétation géologique. / We present a new method for seismic image restoration. When observed, a seismic image is the result of an initial deposit system that has been transformed by a set of successive geological deformations (folding, fault slip, etc) that occurred over a large period of time. The goal of seismic restoration consists in inverting the deformations to provide a resulting image that depicts the geological deposit system as it was in a previous state. With our contribution, providing a tool that quickly generates restored images helps the geophysicists to recognize geological features that may be too strongly altered in the observed image. The proposed approach is based on a minimization process that expresses geological deformations in terms of geometrical constraints. We use a quickly-converging Gauss-Newton approach to solve the system. We provide results to illustrate the seismic image restoration process on real data and present how the restored version can be used in a geological interpretation framework.

.

Cette thèse est consacrée à la résolution de problèmes d'analyse non linéaire multivoque dans lesquels plusieurs variables interagissent. Le problème générique est modélisé par une inclusion vis-à-vis d'une somme d'opérateurs monotones sur un espace hilbertien produit. Notre objectif est de concevoir des nouveaux algorithmes pour résoudre ce problème sous divers jeux d'hypothèses sur les opérateurs impliqués et d'étudier le comportement asymptotique des méthodes élaborées. Une propriété commune aux algorithmes est le fait qu'ils procèdent par éclatement en ceci que les opérateurs monotones et, le cas échéant, les opérateurs linéaires constitutifs du modèle agissent indépendamment au sein de chaque itération. Nous abordons en particulier le cas où les opérateurs monotones sont des sous-différentiels de fonctions convexes, ce qui débouche sur de nouveaux algorithmes de minimisation. Les méthodes proposées unifient et dépassent largement l'état de l'art. Elles sont appliquées aux inclusions monotones composites en dualité, aux problèmes d'équilibre, au traitement du signal et de l'image, à la théorie des jeux, à la théorie du trafic, aux équations d'évolution, aux problèmes de meilleure approximation et à la décomposition de domaine dans les équations aux dérivées partielles.

Le but de cette thèse est de développer de nouvelles techniques d'éclatement d'opérateurs multivoques pour résoudre des problèmes d'inclusion monotone structurés dans des espaces hilbertiens. La dualité au sens des inclusions monotones tient une place essentielle dans ce travail et nous permet d'obtenir des décompositions qui ne seraient pas disponibles via une approche purement primale. Nous développons plusieurs algorithmes à métrique fixe ou variable dans un cadre unifié, et montrons en particulier que de nombreuses méthodes existantes sont des cas particuliers de la méthode explicite--implicite formulée dans des espaces produits adéquats. Les méthodes proposées sont appliquées aux problèmes d'inéquations variationnelles, aux problèmes de minimisation, aux problèmes inverses, aux problèmes de traitement du signal, aux problèmes d'admissibilité et aux problèmes de meilleure approximation. Dans un second temps, nous introduisons une notion de suite quasi-fejérienne à métrique variable et analysons ses propriétés asymptotiques. Ces résultats nous permettent d'obtenir des extensions de méthodes d'éclatement aux problèmes où la métrique varie à chaque itération.

Le problème d'estimer une fonction de plusieurs variables à partir d'une observation corrompue surgit dans de nombreux domaines d'ingénierie. Par exemple, en imagerie médicale cette tâche a attiré une attention particulière et a, même, motivé l'introduction de nouveaux concepts qui ont trouvé des applications dans de nombreux autres domaines. Cet intérêt est principalement du au fait que l'analyse des données médicales est souvent effectuée dans des conditions difficiles car on doit faire face au bruit, au faible contraste et aux transformations indésirables inhérents aux systèmes d'acquisition. D'autre part , le concept de parcimonie a eu un fort impact sur la reconstruction et la restauration d'images au cours des deux dernières décennies. La parcimonie stipule que certains signaux et images ont des représentations impliquant seulement quelques coefficients non nuls. Cela est avéré être vérifiable dans de nombreux problèmes pratiques. La thèse introduit de nouvelles constructions d'a priori de parcimonie dans le cas des ondelettes et de la variation totale. Ces constructions utilisent une notion d'anisotopie généralisée qui permet de regrouper des variables ayant des comportements similaires : ces comportement peuvent peut être liée à la régularité de la fonction, au sens physique des variables ou bien au modèle d'observation. Nous utilisons ces constructions pour l'estimation non-paramétriques de fonctions. Dans le cas des ondelettes, nous montrons l'optimalité de l'approche sur les espaces fonctionnelles habituels avant de présenter quelques exemples d’applications en débruitage de séquences d'images, de données spectrales et hyper-spectrales, écoulements incompressibles ou encore des images ultrasonores. En suite, nous modélisons un problème déconvolution de données d'imagerie par résonance magnétique fonctionnelle comme un problème de minimisation faisant apparaître un a priori de variation totale structuré en espace-temps. Nous adaptons une généralisation de l'éclatement explicite-implicite pour trouver une solution au problème de minimisation. / The problem of estimating a multivariate function from corrupted observations arises throughout many areas of engineering. For instance, in the particular field of medical signal and image processing, this task has attracted special attention and even triggered new concepts and notions that have found applications in many other fields. This interest is mainly due to the fact that the medical data analysis pipeline is often carried out in challenging conditions, since one has to deal with noise, low contrast and undesirable transformations operated by acquisition systems. On the other hand, the concept of sparsity had a tremendous impact on data reconstruction and restoration in the last two decades. Sparsity stipulates that some signals and images have representations involving only a few non-zero coefficients. The present PhD dissertation introduces new constructions of sparsity priors for wavelets and total variation. These construction harness notions of generalized anisotropy that enables grouping variables into sub-sets having similar behaviour; this behaviour can be related to the regularity of the unknown function, the physical meaning of the variables or the observation model. We use these constructions for non-parametric estimation of multivariate functions. In the case of wavelet thresholding, we show the optimality of the procedure over usual functional spaces before presenting some applications on denoising of image sequence, spectral and hyperspectral data, incompressible flows and ultrasound images. Afterwards, we study the problem of retrieving activity patterns from functional Magnetic Resonance Imaging data without incorporating priors on the timing, durations and atlas-based spatial structure of the activation. We model this challenge as a spatio-temporal deconvolution problem. We propose the corresponding variational formulation and we adapt the generalized forward-backward splitting algorithm to solve it.

Cette thèse vise à la conception de nouveaux algorithmes rapides en calcul numérique via les matrices de Toeplitz. Tout d'abord, nous avons introduit un algorithme rapide sur le calcul de l'inverse d'une matrice triangulaire de Toeplitz en se basant sur des notions d'interpolation polynomiale. Cet algorithme nécessitant uniquement deux FFT(2n) est manifestement efficace par rapport à ses prédécésseurs. ensuite, nous avons introduit un algorithme rapide pour la résolution d'un système linéaire de Toeplitz bande. Cette approche est basée sur l'extension de la matrice donnée par plusieurs lignes en dessus, de plusieurs colonnes à droite et d'attribuer des zéros et des constantes non nulles dans chacune de ces lignes et de ces colonnes de telle façon que la matrice augmentée à la structure d'une matrice triangulaire inférieure de Toeplitz. La stabilité de l'algorithme a été discutée et son efficacité a été aussi justifiée. Finalement, nous avons abordé la résolution d'un système de Toeplitz bandes par blocs bandes de Toeplitz. Ceci étant primordial pour établir la connexion de nos algorithmes à des applications en restauration d'images, un domaine phare en mathématiques appliquées. / This thesis aims to design new fast algorithms for numerical computation via the Toeplitz matrices. First, we introduced a fast algorithm to compute the inverse of a triangular Toeplitz matrix with real and/or complex numbers based on polynomial interpolation techniques. This algorithm requires only two FFT (2n) is clearly effective compared to predecessors. A numerical accuracy and error analysis is also considered. Numerical examples are given to illustrate the effectiveness of our method. In addition, we introduced a fast algorithm for solving a linear banded Toeplitz system. This new approach is based on extending the given matrix with several rows on the top and several columns on the right and to assign zeros and some nonzero constants in each of these rows and columns in such a way that the augmented matrix has a lower triangular Toeplitz structure. Stability of the algorithm is discussed and its performance is showed by numerical experiments. This is essential to connect our algorithms to applications such as image restoration applications, a key area in applied mathematics.

Les méthodes d'algèbres linéaire classiques, pour le calcul de valeurs et vecteurs propres d'une matrice, ou des approximations de rangs inférieurs (low-rank approximations) d'une solution, etc..., ne tiennent pas compte des structures de matrices. Ces dernières sont généralement détruites durant le procédé du calcul. Des méthodes alternatives préservant ces structures font l'objet d'un intérêt important par la communauté. Cette thèse constitue une contribution dans ce domaine. La décomposition SR peut être calculé via l'algorithme de Gram-Schmidt symplectique. Comme dans le cas classique, une perte d'orthogonalité peut se produire. Pour y remédier, nous avons proposé deux algorithmes RSGSi et RMSGSi qui consistent à ré-orthogonaliser deux fois les vecteurs à calculer. La perte de la J-orthogonalité s'est améliorée de manière très significative. L'étude directe de la propagation des erreurs d'arrondis dans les algorithmes de Gram-Schmidt symplectique est très difficile à effectuer. Nous avons réussi à contourner cette difficulté et donner des majorations pour la perte de la J-orthogonalité et de l'erreur de factorisation. Une autre façon de calculer la décomposition SR est basée sur les transformations de Householder symplectique. Un choix optimal a abouti à l'algorithme SROSH. Cependant, ce dernier peut être sujet à une instabilité numérique. Nous avons proposé une version modifiée nouvelle SRMSH, qui a l'avantage d'être aussi stable que possible. Une étude approfondie a été faite, présentant les différentes versions : SRMSH et SRMSH2. Dans le but de construire un algorithme SR, d'une complexité d'ordre O(n³) où 2n est la taille de la matrice, une réduction (appropriée) de la matrice à une forme condensée (J(Hessenberg forme) via des similarités adéquates, est cruciale. Cette réduction peut être effectuée via l'algorithme JHESS. Nous avons montré qu'il est possible de réduire une matrice sous la forme J-Hessenberg, en se basant exclusivement sur les transformations de Householder symplectiques. Le nouvel algorithme, appelé JHSJ, est basé sur une adaptation de l'algorithme SRSH. Nous avons réussi à proposer deux nouvelles variantes, aussi stables que possible : JHMSH et JHMSH2. Nous avons constaté que ces algorithmes se comportent d'une manière similaire à l'algorithme JHESS. Une caractéristique importante de tous ces algorithmes est qu'ils peuvent rencontrer un breakdown fatal ou un "near breakdown" rendant impossible la suite des calculs, ou débouchant sur une instabilité numérique, privant le résultat final de toute signification. Ce phénomène n'a pas d'équivalent dans le cas Euclidien. Nous avons réussi à élaborer une stratégie très efficace pour "guérir" le breakdown fatal et traîter le near breakdown. Les nouveaux algorithmes intégrant cette stratégie sont désignés par MJHESS, MJHSH, JHM²SH et JHM²SH2. Ces stratégies ont été ensuite intégrées dans la version implicite de l'algorithme SR lui permettant de surmonter les difficultés rencontrées lors du fatal breakdown ou du near breakdown. Rappelons que, sans ces stratégies, l'algorithme SR s'arrête. Finalement, et dans un autre cadre de matrices structurées, nous avons présenté un algorithme robuste via FFT et la matrice de Hankel, basé sur le calcul approché de plus grand diviseur commun (PGCD) de deux polynômes, pour résoudre le problème de la déconvolution d'images. Plus précisément, nous avons conçu un algorithme pour le calcul du PGCD de deux polynômes bivariés. La nouvelle approche est basée sur un algorithme rapide, de complexité quadratique O(n²), pour le calcul du PGCD des polynômes unidimensionnels. La complexité de notre algorithme est O(n²log(n)) où la taille des images floues est n x n. Les résultats expérimentaux avec des images synthétiquement floues illustrent l'efficacité de notre approche. / The classical linear algebra methods, for calculating eigenvalues and eigenvectors of a matrix, or lower-rank approximations of a solution, etc....do not consider the structures of matrices. Such structures are usually destroyed in the numerical process. Alternative structure-preserving methods are the subject of an important interest mattering to the community. This thesis establishes a contribution in this field. The SR decomposition is usually implemented via the symplectic Gram-Schmidt algorithm. As in the classical case, a loss of orthogonality can occur. To remedy this, we have proposed two algorithms RSGSi and RMSGSi, where the reorthogonalization of a current set of vectors against the previously computed set is performed twice. The loss of J-orthogonality has significantly improved. A direct rounding error analysis of symplectic Gram-Schmidt algorithm is very hard to accomplish. We managed to get around this difficulty and give the error bounds on the loss of the J-orthogonality and on the factorization. Another way to implement the SR decomposition is based on symplectic Householder transformations. An optimal choice of free parameters provided an optimal version of the algorithm SROSH. However, the latter may be subject to numerical instability. We have proposed a new modified version SRMSH, which has the advantage of being numerically more stable. By a detailes study, we are led to two new variants numerically more stables : SRMSH and SRMSH2. In order to build a SR algorithm of complexity O(n³), where 2n is the size of the matrix, a reduction to the condensed matrix form (upper J-Hessenberg form) via adequate similarities is crucial. This reduction may be handled via the algorithm JHESS. We have shown that it is possible to perform a reduction of a general matrix, to an upper J-Hessenberg form, based only on the use of symplectic Householder transformations. The new algorithm, which will be called JHSH algorithm, is based on an adaptation of SRSH algorithm. We are led to two news variants algorithms JHMSH and JHMSH2 which are significantly more stable numerically. We found that these algortihms behave quite similarly to JHESS algorithm. The main drawback of all these algorithms (JHESS, JHMSH, JHMSH2) is that they may encounter fatal breakdowns or may suffer from a severe form of near-breakdowns, causing a brutal stop of the computations, the algorithm breaks down, or leading to a serious numerical instability. This phenomenon has no equivalent in the Euclidean case. We sketch out a very efficient strategy for curing fatal breakdowns and treating near breakdowns. Thus, the new algorithms incorporating this modification will be referred to as MJHESS, MJHSH, JHM²SH and JHM²SH2. These strategies were then incorporated into the implicit version of the SR algorithm to overcome the difficulties encountered by the fatal breakdown or near-breakdown. We recall that without these strategies, the SR algorithms breaks. Finally ans in another framework of structured matrices, we presented a robust algorithm via FFT and a Hankel matrix, based on computing approximate greatest common divisors (GCD) of polynomials, for solving the problem pf blind image deconvolution. Specifically, we designe a specialized algorithm for computing the GCD of bivariate polynomials. The new algorithm is based on the fast GCD algorithm for univariate polynomials , of quadratic complexity O(n²) flops. The complexitiy of our algorithm is O(n²log(n)) where the size of blurred images is n x n. The experimental results with synthetically burred images are included to illustrate the effectiveness of our approach