Search

International audience; Image synthesis in the context of radio interferometric data can be expressed as a signal reconstruction from incomplete Fourier measurements. Most imaging techniques for radio interferometry lie in minimizing the least square error between the reconstructed image and the observed data assuming an additive white gaussian noise. In this paper, we derive an expectation-maximization based imaging algorithm that handles the presence of outliers in the observed data. Subsequently, we propose a new generic image synthesis algorithm based on the expectation-maximization algorithm, leading to a computationally efficient method.

International audience; We are presenting the application of an optical and computational pipeline FAMOUS for revealing the presence of free viral particles named "virions". The idea of such a protocol is to give rise to images of virions in their environment with a soft solution for recording the native image, contrary to the standard solution of imaging virions with electron microscopy (EM) for visualizing viral particles. The final aim of the current work is to observe free viral particles of SARS-CoV-2, the virions responsible for the worldwide pandemic of Covid-19. But such particles have diameters between 80 and 120 nm, a dimension smaller than the resolution limit of optical-only microscopy solutions. We have chosen to start with the biggest free virions, cytomegalovirus (CMV), a virus from the herpesvirus family also named "Human Herpes Virus 5". Two kinds of cultures were involved: a fluorescent culture (BAD) and a label-free one (VHLE), both being collected from infected cell culture. VHLE virions were first observed after secondary immunostaining and concentrated with magnetic nanoparticles and then without labelling. The optical protocol rests on a standard solution of multiphoton microscopy combined with a computational strategy based on the point-spread-function (PSF) recordings, its mathematical modeling and the restauration of the image resting on the PSF model. A test with free viral particles of SARS-CoV-2 is led, delivering an optical visualization of the free-viral particles. The visualization of objects aggregates obtained in both situations confirm the relevance of the pipeline FAMOUS for imaging free virions.

On-board restoration of underwater images on embedded platforms such as marine drones is faced with many obstacles including image quality and real-time constraints. Confrontations met on the way vary from views to solution methods depending on the goals, such as underwater vehicle realtime control and positioning or underwater object recognition. In this research, five algorithms for underwater image restoration were studied and evaluated. In order to evaluate the quality of the performing algorithms nine evaluation criteria were used. Split into two types, the no reference metrics assesses only the quality of the image results, while the full reference criterion uses a reference image to estimate it. The calculation of these criteria allows each algorithm to be compared. Furthermore, the possibility to optimise algorithms in order to make them applicable to meet real-time requirements on embedded platforms was investigated., La restauration embarquée d'images sous-marines sur des plates-formes embarquées telles que les drones marins est confrontée à de nombreux obstacles dont la qualité des images et les contraintes de temps réel. Les confrontations rencontrées en cours de route varient des points de vue aux méthodes de solution en fonction des objectifs, tels que le contrôle et le positionnement en temps réel du véhicule sous-marin ou la reconnaissance d'objets sous-marins. Dans cette recherche, cinq algorithmes de restauration d'images sous-marines ont été étudiés et évalués. Afin d'évaluer la qualité des algorithmes performants, neuf critères d'évaluation ont été utilisés. Divisés en deux types, le critère sans référence évalue uniquement la qualité des résultats de l'image, tandis que le critère avec référence complète utilise une image de référence pour l'estimer. Le calcul de ces critères permet de comparer chaque algorithme. En outre, la possibilité d'optimiser les algorithmes afin de les rendre applicables pour répondre aux exigences du temps réel sur les plateformes embarquées a été étudiée.

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, 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.

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., 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.

Stereo reconstruction serves many outdoor applications, and thus sometimes faces foggy weather. The quality of the reconstruction by state of the art algorithms is then degraded as contrast is reduced with the distance because of scattering. However, as shown by defogging algorithms from a single image, fog provides an extra depth cue in the grey level of far away objects. Our idea is thus to take advantage of both stereo and atmospheric veil depth cues to achieve better stereo reconstructions in foggy weather. To our knowledge, this subject has never been investigated earlier by the computer vision community. We thus propose a Markov Random Field model of the stereo reconstruction and defogging problem which can be optimized iteratively using the ±-expansion algorithm. Outputs are a dense disparity map and an image where contrast is restored. The proposed model is evaluated on synthetic images. This evaluation shows that the proposed method achieves very good results on both stereo reconstruction and defogging compared to standard stereo reconstruction and single image defogging.; Nous nous sommes intéressés au problème de la reconstruction 3D à partir de paires stéréoscopiques en présence de brouillard. De nombreux algorithmes existent pour effectuer la reconstruction stéréoscopique, mais peu sont adaptés aux conditions dégradées et en particulier, au brouillard. De ce fait, ils produisent des résultats incorrects à partir d'une certaine distance. L'une des principales causes de cette limitation est la diminution du contraste avec la distance due au brouillard. La restauration du contraste dans une image en présence de brouillard connaît un intérêt croissant en traitement d'image ces dernières années, en particulier pour des applications destinées aux aides à la conduite. De nombreux algorithmes ont été proposés et permettent d'apporter des solutions approchées à ce problème. Un grand nombre d'entre eux sont fondés sur la loi de Koschmieder qui permet de faire le lien entre l'intensité de l'image, l'intensité originale de la scène et la profondeur. L'un des problèmes de la restauration du contraste monoculaire est l'ambiguïté entre l'épaisseur du voile atmosphérique liée à la profondeur et la couleur plus ou moins claire de la scène, qui fait que ce problème est mal posé. Des contraintes arbitraires doivent donc être ajoutées et cela fait que la solution est approchée. Souvent, la profondeur estimée est très différente de la profondeur exacte de la scène, en particulier à courte distance où le voile est faible.. A partir de ce constat, la complémentarité de la reconstruction stéréo et de la restauration apparaît et un algorithme de reconstruction et de restauration simultanées a été proposé pour la première fois. Pour cela, nous proposons une approche probabiliste fondée sur les champs de Markov. Le modèle proposé permet, grâce à l'indice de profondeur de la stéréovision, de restaurer le contraste avec précision à courte distance. De plus, les images restaurées facilitent la reconstruction à longue distance. Une évaluation qualitative de l'algorithme proposé montre une amélioration significative de la qualité de la carte de profondeur générée par rapport aux algorithmes classiques ne prenant pas en compte le brouillard. L'évaluation montre aussi que les restaurations obtenues sont de qualité proche de celles de l'état de l'art.

Inverse problems are to recover the data that has been processed or corrupted. Since they are ill-posed they require a regularization. In image processing, the total variation as a regularization tool has the advantage of preserving the discontinuities while creating smooth regions. These results are established in this thesis in a continuous setting for general energies. In addition, we propose and examine a variant of the total variation. We establish a dual formulation that allows us to prove that this variant coincides with the total variation for sets of finite perimeter. Nowadays, non-local methods exploiting the self-similarities of images is particularly successful. We adapt this approach to the problem of spectrum completion, which has applications for general inverse problems. The final part is devoted to the algorithmic aspects inherent to the optimization of the convex energies we considered. We study the convergence and the complexity of the recently developed Primal-Dual algorithms., Les problèmes inverses consistent à retrouver une donnée qui a été transformée ou perturbée. Ils nécessitent une régularisation puisque mal posés. En traitement d'images, la variation totale en tant qu'outil de régularisation a l'avantage de préserver les discontinuités tout en créant des zones lisses, résultats établis dans cette thèse dans un cadre continu et pour des énergies générales. En outre, nous proposons et étudions une variante de la variation totale. Nous établissons une formulation duale qui nous permet de démontrer que cette variante coïncide avec la variation totale sur des ensembles de périmètre fini. Ces dernières années les méthodes non-locales exploitant les auto-similarités dans les images ont connu un succès particulier. Nous adaptons cette approche au problème de complétion de spectre pour des problèmes inverses généraux. La dernière partie est consacrée aux aspects algorithmiques inhérents à l'optimisation des énergies convexes considérées. Nous étudions la convergence et la complexité d'une famille récente d'algorithmes dits Primal-Dual.