Back to Search
Start Over
Approximation and estimation of integral operatorsApplications to the restoration of images degraded by spatially varying blurs
- Source :
- Numerical Analysis [math.NA]. ISAE-Institut Supérieur de l'Aéronautique et de l'Espace, 2016. English, Numerical Analysis [math.NA]. ISAE-Institut Supérieur de l'Aéronautique et de l'Espace, 2016. English. ⟨NNT : ⟩
- Publication Year :
- 2016
- Publisher :
- HAL CCSD, 2016.
-
Abstract
- 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.
- Subjects :
- [ INFO.INFO-TS ] Computer Science [cs]/Signal and Image Processing
[ INFO.INFO-NA ] Computer Science [cs]/Numerical Analysis [cs.NA]
numerical analysis
deblurring
fast algorithms
operateur integral
ondelettes
integral operator
imaging processing
analyse harmonique
compression de matrice
algorithmes rapides
[ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
[INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing
defloutage
wavelet
[ INFO.INFO-TI ] Computer Science [cs]/Image Processing
traitement d'images
flous variables
estimation
matrix compression
spatially varying blurs
[ MATH.MATH-NA ] Mathematics [math]/Numerical Analysis [math.NA]
[INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA]
analyse numerique
[INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV]
harmonic analysis
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
[MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Numerical Analysis [math.NA]. ISAE-Institut Supérieur de l'Aéronautique et de l'Espace, 2016. English, Numerical Analysis [math.NA]. ISAE-Institut Supérieur de l'Aéronautique et de l'Espace, 2016. English. ⟨NNT : ⟩
- Accession number :
- edsair.dedup.wf.001..5ac983e36b5b45b0e780e00d779a2760