Search

Obtaining guarantees on the convergence of the minimizers of empirical risks to the ones of the true risk is a fundamental matter in statistical learning. Instead of deriving guarantees on the usual estimation error, the goal of this paper is to provide concentration inequalities on the distance between the sets of minimizers of the risks for a broad spectrum of estimation problems. In particular, the risks are defined on metric spaces through probability measures that are also supported on metric spaces. A particular attention will therefore be given to include unbounded spaces and non-convex cost functions that might also be unbounded. This work identifies a set of assumptions allowing to describe a regime that seem to govern the concentration in many estimation problems, where the empirical minimizers are stable. This stability can then be leveraged to prove parametric concentration rates in probability and in expectation. The assumptions are verified, and the bounds showcased, on a selection of estimation problems such as barycenters on metric space with positive or negative curvature, subspaces of covariance matrices, regression problems and entropic-Wasserstein barycenters.

The anisotropic fractional Brownian field (AFBF) is a non-stationary Gaussian random field which has been used for the modeling of textured images. In this paper, we address the open issue of estimating the functional parameters of this field, namely the topothesy and Hurst functions. We propose an original method which fits the empirical semi-variogram of an image to the semi-variogram of a turning-band field that approximates the AFBF. Expressing the fitting criterion in terms of a separable non-linear least square criterion, we design a minimization algorithm inspired from the variable projection approach. This algorithm also includes a coarse-to-fine multigrid strategy based on approximations of functional parameters. Compared to existing methods, the new method enables to estimate both functional parameters on their whole definition domain. On simulated textures, we show that it has a low estimation error, even when the parameters are approximated with a high precision. We also apply the method to characterize mammograms and sample images with synthetic parenchymal patterns.

International audience; The main objective of this work is to estimate a low dimensional subspace of operators in order to improve the identifiability of blind inverse problems.We propose a scalable method to find a subspace $\widehat \H$ of low-rank tensors that simultaneously approximates a set of integral operators. The method can be seen as a generalization of tensor decomposition models, which was never used in this context. In addition, we propose to construct a convex subset of $\widehat \H$ in order to further reduce the search space. We provide theoretical guarantees on the estimators and a few numerical results.

International audience; Image deblurring is a fundamental problem in imaging, usually solved with compu-tationally intensive optimization procedures. The goal of this paper is to provide new efficient strategies to reduce computing times for simple 1 − 2 deblurring models. We show that the minimization can be significantly accelerated by leveraging the fact that images and blur operators are compressible in the same orthogonal wavelet basis. The proposed methodology consists of three ingredients: i) a sparse approximation of the blur operator in wavelet bases, ii) a diagonal preconditioner and iii) an implementation on massively parallel architectures. Combing the three ingredients leads to acceleration factors ranging from 30 to 250 on a typical workstation. For instance, a 1024 × 1024 image can be deblurred in 0.15 seconds.

Image deblurring is a fundamental problem in imaging, usually solved with computationally intensive optimization procedures. The goal of this paper is to provide new efficient strategies to reduce computing times for simple deblurring models regularized using orthogonal wavelet transforms. We show that the minimization can be significantly accelerated by leveraging the fact that images and blur operators are compressible in the same orthogonal wavelet basis. The proposed methodology consists of three ingredients: (i) a sparse approximation of the blur operator in wavelet bases, (ii) a diagonal preconditioner and (iii) an implementation on massively parallel architectures. Combining the three ingredients leads to acceleration factors ranging from 4 to 250 on a typical workstation. For instance, a 1024 1024 image can be deblurred in 0.15 s.

Le problème de restauration d'images dégradées par des flous variables connaît un attrait croissant et touche plusieurs domaines tels que l'astronomie, la vision par ordinateur et la microscopie à feuille de lumière où les images sont de taille un milliard de pixels. Les flous variables peuvent être modélisés par des opérateurs intégraux qui associent à une image nette u, une image floue Hu. Une fois discrétisé pour être appliqué sur des images de N pixels, l'opérateur H peut être vu comme une matrice de taille N x N. Pour les applications visées, la matrice est stockée en mémoire avec un exaoctet. On voit apparaître ici les difficultés liées à ce problème de restauration des images qui sont i) le stockage de ce grand volume de données, ii) les coûts de calculs prohibitifs des produits matrice-vecteur. Ce problème souffre du fléau de la dimension. D'autre part, dans beaucoup d'applications, l'opérateur de flou n'est pas ou que partialement connu. Il y a donc deux problèmes complémentaires mais étroitement liés qui sont l'approximation et l'estimation des opérateurs de flou. Cette thèse a consisté à développer des nouveaux modèles et méthodes numériques permettant de traiter ces problèmes. The restoration of images degraded by spatially varying blurs is a problem of increasing importance. It is encountered in many applications such as astronomy, computer vision and fluorescence microscopy where images can be of size one billion pixels. Variable blurs can be modelled by linear integral operators H that map a sharp image u to its blurred version Hu. After discretization of the image on a grid of N pixels, H can be viewed as a matrix of size N x N. For targeted applications, matrices is stored with using exabytes on the memory. This simple observation illustrates the difficulties associated to this problem: i) the storage of a huge amount of data, ii) the prohibitive computation costs of matrix-vector products. This problems suffers from the challenging curse of dimensionality. In addition, in many applications, the operator is usually unknown or only partially known. There are therefore two different problems, the approximation and the estimation of blurring operators. They are intricate and have to be addressed with a global overview. Most of the work of this thesis is dedicated to the development of new models and computational methods to address those issues.

The restoration of images degraded by spatially varying blurs is a problem of increasing importance. It is encountered in many applications such as astronomy, computer vision and fluorescence microscopy where images can be of size $1000 \times 1000 \times 1000$ pixels. Variable blurs can be modelled by linear integral operators $H$ that map a sharp image $u$ to its blurred version $Hu$ defined by\[ Hu(x) = \int_{\Omega} K(x,y) u(y) dy, \quad \forall x \in \Omega = [0,1]^d\]where $K : \Omega \times \Omega \to \mathbb{R}$ is called the kernel. After discretization of the image on a grid of $N$ pixels, $H$ can be viewed as a matrix of size $N \times N$. For targeted applications, matrices contain $10^{18}$ coefficients. This simple observation illustrates the difficulties associated to this problem: i) the storage of a huge amount of data, ii) the prohibitive computation costs of matrix-vector products. This problems suffers from the challenging curse of dimensionality. In addition, in many applications, the operator is usually unknown or only partially known. There are therefore two different problems, the approximation and the estimation of blurring operators. They are intricate \emph{and} have to be addressed with a global overview. Most of the work of this thesis is dedicated to the development of new models and computational methods to address those issues.In a first part, this work studied the approximation methods of integral operators. Existing approaches in the literature can be separated in two classes. The most developed approaches consists in constructing a low rank decomposition of the kernel $K$. Similarly to the seminal work of Beylkin, Coifman and Rokhlin, we studied the representation of blurring operators in wavelet bases. We showed that matrix-vector products can be rapidly computed in $O(N\epsilon^{-M/d})$ with a precision $\epsilon$ in spectral norm where $M$ is a scalar describing the regularity of the kernel. This type of approximations can be used to design restoration algorithms that are two orders of magnitude faster than current methods.The second class contains methods commonly used in the imaging community. They consist in constructing a low rank decomposition of the Time Varying Impulse Response (TVIR) $T : \Omega \times \Omega \to \mathbb{R}$ defined by $T(x,y) = K(x+y,y)$. Until now, those methods were partially studied and this work bridges the gap in the comprehension of their performances. Moreover, it allowed the identification of a representation that ``super'' compresses the operator. This representation appeals for the development of new identification strategies.In a second part, this work addresses the challenging problem of the estimation of operators. Recent theoretical works studied this problem but none of them can be implemented in targeted applications. In the specific case where some scattered impulse responses are observed, this work proposes the construction of an estimator of the operator that can be evaluated numerically in large dimensions. Theoretical guarantees on the performance of the estimator are also provided. \\Finally, this thesis studied other imaging problems. Images from light-sheet microscopy are degraded by stripe shaped attenuations. These phenomena can be modelled by multiplicative structured noises. This work proposes to solve a convex optimization and convincing results are obtained on real data.The development of quantitative indices that measure the similarity of images is a challenging question in imaging.The illumination of a scene can vary between two moments. Most indices are non invariant to these variations and will fail to assess the similarity of the same scene between the two instants. We proposed a similarity measure that is invariant to illumination changes.; Le problème de restauration d'images dégradées par des flous variables connaît un attrait croissant et touche plusieurs domaines tels que l'astronomie, la vision par ordinateur et la microscopie à feuille de lumière où les images sont de taille $1000 \times 1000 \times 1000$ pixels. Les flous variables peuvent être modélisés par des opérateurs intégraux qui associent à une image nette $u$, une image floue $Hu$ définie par\[ Hu(x) = \int_{\Omega} K(x,y) u(y) dy, \quad \forall x \in \Omega = [0,1]^d\]où $K : \Omega \times \Omega \to \mathbb{R}$ est appelé le noyau. Une fois discrétisé pour être appliqué sur des images de $N$ pixels, l'opérateur $H$ peut être vu comme une matrice de taille $N \times N$. Pour les applications visées, la matrice contient $10^{18}$ coefficients. On voit apparaître ici les difficultés liées à ce problème de restauration des images qui sont i) le stockage de ce grand volume de données, ii) les coûts de calculs prohibitifs des produits matrice-vecteur. Ce problème souffre du fléau de la dimension. D'autre part, dans beaucoup d'applications, l'opérateur de flou n'est pas ou que partialement connu. Il y a donc deux problèmes complémentaires mais étroitement liés qui sont l'approximation et l'estimation des opérateurs de flou.Cette thèse a consisté à développer des nouveaux modèles et méthodes numériques permettant de traiter ces problèmes. Dans une première partie, ce travail a étudié les méthodes d'approximation des opérateurs intégraux. Elles peuvent être distinguées en deux groupes. Le plus étoffé contient les méthodes qui construisent une décomposition de rang faible du noyau $K$. Similairement aux travaux fondateurs du groupe de Beylkin, Coifman et Rokhlin, nous avons étudié les représentations des opérateurs de flou dans des bases d'ondelettes. Nous avons montré que les produits matrice-vecteur $Hu$ peuvent être appliqués en $O(N\epsilon^{-M/d})$ avec une précision $\epsilon$ où $M$ est un scalaire décrivant la régularité du noyau. Ces approximations peuvent donner lieu à des temps de restauration des images réduits de deux ordres de grandeurs.Les méthodes du deuxième groupe, couramment utilisées dans la communauté du traitement d'image, construisent une décomposition de rang faible de la Time Varying Impulse Response (TVIR) $T : \Omega \times \Omega \to \mathbb{R}$ définie par $T(x,y) = K(x+y,y)$. Elles sont restées jusqu'à présent non-étudiées et ce travail a permis de combler un manque dans la compréhension de leurs performances. De plus, il a permis d'identifier des représentations qui compressent considérablement les opérateurs et rendent possible l'estimation de l'opérateur.Dans une deuxième partie, ce travail aborde le délicat problème d'estimation des opérateurs. Récemment, de nouveaux travaux théoriques s'y sont intéressés, cependant aucun d'eux ne peut être implémenté en pratique. Dans le cas où quelques réponses impulsionnelles arbitrairement réparties dans l'espace sont connues, ce travail propose une construction d'un estimateur de l'opérateur qui soit numériquement applicable en grande dimension. Nous donnons aussi des garanties théoriques sur ses performances.Dans un troisième temps, cette thèse étudie d'autres types de dégradation. Les images issues de la microscopie à feuille de lumière sont altérées par des atténuations en forme de raies. Ce phénomène peut-être modélisé par un bruit multiplicatif structuré. Ce travail propose un modèle de résolution convexe qui rend le problème soluble aisément et qui donne des résultats probants sur des données réelles.Les indices de comparaison de deux images consistent une question délicate. Entre deux instants, une scène peut être illuminée différemment. Beaucoup d'indices sont sensibles à ces variations et échoueront à reconnaître la similarité de la scène entre deux instants. Nous avons proposé une mesure de similarité des images qui est invariante aux changements d'illumination.

We design an image quality measure independent of local contrast changes, which constitute simple models of illumination changes. Given two images, the algorithm provides the image closest to the first one with the component tree of the second. This problem can be cast as a specific convex program called isotonic regression. We provide a few analytic properties of the solutions to this problem. We also design a tailored first order optimization procedure together with a full complexity analysis. The proposed method turns out to be practically more efficient and reliable than the best existing algorithms based on interior point methods. The algorithm has potential applications in change detection, color image processing or image fusion. A Matlab implementation is available at http://www.math.univ-toulouse.fr/ ∼ weiss/PageCodes.html.

We consider a class of linear integral operators with impulse responses varying regularly in time or space. These operators appear in a large number of applications ranging from signal/image processing to biology. Evaluating their action on functions is a computation-ally intensive problem necessary for many practical problems. We analyze a technique called convolution-product expansion: the operator is locally approximated by a convolution, allowing to design fast numerical algorithms based on the fast Fourier transform. We design various types of expansions, provide their explicit rates of approximation and their complexity depending on the time varying impulse response smoothness. This analysis suggests novel wavelet based implementations of the method with numerous assets such as optimal approximation rates, low complexity and storage requirements as well as adaptivity to the kernels regularity. The proposed methods are an alternative to more standard procedures such as panel clustering, cross approximations, wavelet expansions or hierarchical matrices.

Restoring images degraded by spatially varying blur is a problem encountered in many disciplines such as astrophysics, computer vision or biomedical imaging. Blurring operators are modelled using integral operators with some regularity and decrease conditions on the kernel. Recently, we studied the approximation of these operators in wavelet bases in which operators are highly compressible. They also allow to fastly compute matrix-vector products with a complexity $O(N\epsilon^{-d/M})$ for a precision $\epsilon$ in spectral norm, where N is the number of pixels of a d-dimensional image and M describes the kernel regularity. Additionnaly, we have shown that the sparsity pattern of the matrix can be pre-defined. We exploit these results to study the estimation/reconstruction of the operator from the knwoledge of few point spread functions located at arbitrary positions in the image domain. We propose an original formulation directly in the wavelet domain and a fast algorithm.

Image deblurring is a fundamental problem in imaging, usually solved with com-putationally intensive optimization procedures. We show that the minimization can be significantly accelerated by leveraging the fact that images and blur operators are compressible in the same orthogonal wavelet basis. The proposed methodology consists of three ingredients: i) a sparse approximation of the blur operator in wavelet bases, ii) a diagonal preconditioner and iii) an implementation on massively parallel architectures. Combing the three ingredients leads to acceleration factors ranging from 30 to 250 on a typical workstation. For instance, a 1024 x 1024 image can be deblurred in 0.15 seconds, which corresponds to real-time.

Today, Light Sheet Fluorescence Microscopy (LSFM) makes it possible to image fluorescent samples through depths of several hundreds of microns. However, LSFM also suffers from scattering, absorption and optical aberrations. Spatial variations in the refractive index inside the samples cause major changes to the light path resulting in loss of signal and contrast in the deepest regions, thus impairing in-depth imaging capability. These effects are particularly marked when inhomogeneous, complex biological samples are under study. Recently, chemical treatments have been developed to render a sample transparent by homogenizing its refractive index (RI), consequently enabling a reduction of scattering phenomena and a simplification of optical aberration patterns. One drawback of these methods is that the resulting RI of cleared samples does not match the working RI medium generally used for LSFM lenses. This RI mismatch leads to the presence of low-order aberrations and therefore to a significant degradation of image quality. In this paper, we introduce an original optical-chemical combined method based on an adaptive SPIM and a water-based clearing protocol enabling compensation for aberrations arising from RI mismatches induced by optical clearing methods and acquisition of high-resolution in-depth images of optically cleared complex thick samples such as Multi-Cellular Tumour Spheroids.