abstract: Image understanding has been playing an increasingly crucial role in vision applications. Sparse models form an important component in image understanding, since the statistics of natural images reveal the presence of sparse structure. Sparse methods lead to parsimonious models, in addition to being efficient for large scale learning. In sparse modeling, data is represented as a sparse linear combination of atoms from a "dictionary" matrix. This dissertation focuses on understanding different aspects of sparse learning, thereby enhancing the use of sparse methods by incorporating tools from machine learning. With the growing need to adapt models for large scale data, it is important to design dictionaries that can model the entire data space and not just the samples considered. By exploiting the relation of dictionary learning to 1-D subspace clustering, a multilevel dictionary learning algorithm is developed, and it is shown to outperform conventional sparse models in compressed recovery, and image denoising. Theoretical aspects of learning such as algorithmic stability and generalization are considered, and ensemble learning is incorporated for effective large scale learning. In addition to building strategies for efficiently implementing 1-D subspace clustering, a discriminative clustering approach is designed to estimate the unknown mixing process in blind source separation. By exploiting the non-linear relation between the image descriptors, and allowing the use of multiple features, sparse methods can be made more effective in recognition problems. The idea of multiple kernel sparse representations is developed, and algorithms for learning dictionaries in the feature space are presented. Using object recognition experiments on standard datasets it is shown that the proposed approaches outperform other sparse coding-based recognition frameworks. Furthermore, a segmentation technique based on multiple kernel sparse representations is developed, and successfully applied for automated brain tumor identification. Using sparse codes to define the relation between data samples can lead to a more robust graph embedding for unsupervised clustering. By performing discriminative embedding using sparse coding-based graphs, an algorithm for measuring the glomerular number in kidney MRI images is developed. Finally, approaches to build dictionaries for local sparse coding of image descriptors are presented, and applied to object recognition and image retrieval. / Dissertation/Thesis / Ph.D. Electrical Engineering 2013

La ''super-résolution'' est définie comme une classe de techniques qui améliorent la résolution spatiale d’images. Les méthodes de super-résolution peuvent être subdivisés en méthodes à partir d’une seule image et à partir de multiple images. Cette thèse porte sur le développement d’algorithmes basés sur des théories mathématiques pour résoudre des problèmes de super-résolution à partir d’une seule image. En effet, pour estimer un’image de sortie, nous adoptons une approche mixte : nous utilisons soit un dictionnaire de « patches » avec des contraintes de parcimonie (typique des méthodes basées sur l’apprentissage) soit des termes régularisation (typiques des méthodes par reconstruction). Bien que les méthodes existantes donnent déjà de bons résultats, ils ne prennent pas en compte la géométrie des données dans les différentes tâches. Par exemple, pour régulariser la solution, pour partitionner les données (les données sont souvent partitionnées avec des algorithmes qui utilisent la distance euclidienne comme mesure de dissimilitude), ou pour apprendre des dictionnaires (ils sont souvent appris en utilisant PCA ou K-SVD). Ainsi, les méthodes de l’état de l’art présentent encore certaines limites. Dans ce travail, nous avons proposé trois nouvelles méthodes pour dépasser ces limites. Tout d’abord, nous avons développé SE-ASDS (un terme de régularisation basé sur le tenseur de structure) afin d’améliorer la netteté des bords. SE-ASDS obtient des résultats bien meilleurs que ceux de nombreux algorithmes de l’état de l’art. Ensuite, nous avons proposé les algorithmes AGNN et GOC pour déterminer un sous-ensemble local de données d’apprentissage pour la reconstruction d’un certain échantillon d’entrée, où l’on prend en compte la géométrie sous-jacente des données. Les méthodes AGNN et GOC surclassent dans la majorité des cas la classification spectrale, le partitionnement de données de type « soft », et la sélection de sous-ensembles basée sur la distance géodésique. Ensuite, nous avons proposé aSOB, une stratégie qui prend en compte la géométrie des données et la taille du dictionnaire. La stratégie aSOB surpasse les méthodes PCA et PGA. Enfin, nous avons combiné tous nos méthodes dans un algorithme unique, appelé G2SR. Notre algorithme montre de meilleurs résultats visuels et quantitatifs par rapport aux autres méthodes de l’état de l’art. / Image super-resolution is defined as a class of techniques that enhance the spatial resolution of images. Super-resolution methods can be subdivided in single and multi image methods. This thesis focuses on developing algorithms based on mathematical theories for single image super-resolution problems. Indeed, in order to estimate an output image, we adopt a mixed approach: i.e., we use both a dictionary of patches with sparsity constraints (typical of learning-based methods) and regularization terms (typical of reconstruction-based methods). Although the existing methods already perform well, they do not take into account the geometry of the data to: regularize the solution, cluster data samples (samples are often clustered using algorithms with the Euclidean distance as a dissimilarity metric), learn dictionaries (they are often learned using PCA or K-SVD). Thus, state-of-the-art methods still suffer from shortcomings. In this work, we proposed three new methods to overcome these deficiencies. First, we developed SE-ASDS (a structure tensor based regularization term) in order to improve the sharpness of edges. SE-ASDS achieves much better results than many state-of-the-art algorithms. Then, we proposed AGNN and GOC algorithms for determining a local subset of training samples from which a good local model can be computed for reconstructing a given input test sample, where we take into account the underlying geometry of the data. AGNN and GOC methods outperform spectral clustering, soft clustering, and geodesic distance based subset selection in most settings. Next, we proposed aSOB strategy which takes into account the geometry of the data and the dictionary size. The aSOB strategy outperforms both PCA and PGA methods. Finally, we combine all our methods in a unique algorithm, named G2SR. Our proposed G2SR algorithm shows better visual and quantitative results when compared to the results of state-of-the-art methods.

V oblasti zpracování signálů se v současné době čím dál více využívají tzv. řídké reprezentace signálů, tzn. že daný signál je možné vyjádřit přesně či velmi dobře aproximovat lineární kombinací velmi malého počtu vektorů ze zvoleného reprezentačního systému. Tato práce se zabývá využitím řídkých reprezentací pro rekonstrukci poškozených zvukových záznamů, ať už historických nebo nově vzniklých. Především historické zvukové nahrávky trpí zarušením jako praskání nebo šum. Krátkodobé poškození zvukových nahrávek bylo doposud řešeno interpolačními technikami, zejména pomocí autoregresního modelování. V nedávné době byl představen algoritmus s názvem Audio Inpainting, který řeší doplňování chybějících vzorků ve zvukovém signálu pomocí řídkých reprezentací. Zmíněný algoritmus využívá tzv. hladové algoritmy pro řešení optimalizačních úloh. Cílem této práce je porovnání dosavadních interpolačních metod s technikou Audio Inpaintingu. Navíc, k řešení optimalizačních úloh jsou využívány algoritmy založené na l1-relaxaci, a to jak ve formě analyzujícího, tak i syntetizujícího modelu. Především se jedná o proximální algoritmy. Tyto algoritmy pracují jak s jednotlivými koeficienty samostatně, tak s koeficienty v závislosti na jejich okolí, tzv. strukturovaná řídkost. Strukturovaná řídkost je dále využita taky pro odšumování zvukových nahrávek. Jednotlivé algoritmy jsou v praktické části zhodnoceny z hlediska nastavení parametrů pro optimální poměr rekonstrukce vs. výpočetní čas. Všechny algoritmy popsané v práci jsou na praktických příkladech porovnány pomocí objektivních metod odstupu signálu od šumu (SNR) a PEMO-Q. Na závěr je úspěšnost rekonstrukce poškozených zvukových signálů vyhodnocena.

This Master's Thesis deals with the issue of audio clipping and the application of sparse represenations model for the task of declipping. First, a general theory of clipping is described, followed by a brief overview of existing methods and a description of the general theory concerning sparse representations of signals and bases, respectively frames. Subsequently, two methods solving declipping problem based on sparse representations are intruduced. The first method uses the Generic proximal algorithm for convex optimization, the second one uses the Douglas-Rachford algorithm. The above mentioned methods have been programmed in the Matlab environment. The results of the declipping methods are evaluated according to SNR, PEMO-Q and also by subjective listening tests.

Le suivi multi-objets, malgré les avancées récentes en détection d'objets, présente encore plusieurs difficultés spécifiques et reste ainsi une problématique difficile. Au cours de cette thèse nous proposons d'examiner l'emploi de représentations parcimonieuses au sein de méthodes de suivi multi-objets, dans le but d'améliorer les performances de ces dernières. La première contribution de cette thèse consiste à employer des représentations parcimonieuses collaboratives dans un système de suivi en ligne pour distinguer au mieux les cibles. Des représentations parcimonieuses structurées sont ensuite considérées pour s'adapter plus spécifiquement aux approches de suivi à fenêtre glissante. Une dernière contribution consiste à employer des dictionnaires denses, prenant en considération un grand nombre de positions non détectées au sein des images, de manière à être plus robuste vis-à-vis de la performance du détecteur d'objets employé. / Despite recent advances in object detection, multi-object tracking still raises some specific issues and therefore remains a challenging problem. In this thesis, we propose to investigate the use of sparse representations within multi-object tracking approaches in order to gain in performances. The first contribution of this thesis consists in designing an online tracking approach that takes advantage of collaborative sparse representations to better distinguish between the targets. Then, structured sparse representations are considered in order to be more suited to traking approaches based on a sliding window. In order to rely less on the object detector quality, we consider for the last contribution of this thesis to use dense dictionaries that are taking into account a large number of undetected locations inside each frame.

Ce mémoire de thèse présente de nouvelles méthodologies pour l’analyse de données Poissoniennes sur la sphère, dans le cadre de la mission Fermi. Les objectifs principaux de la mission Fermi, l’étude du fond diffus galactique et l’établissement du catalogue de source, sont com pliqués par la faiblesse du flux de photons et les effets de l’instrument de mesure. Ce mémoire introduit une nouvelle représentation mutli-échelles des données Poissoniennes sur la sphère, la Transformée Stabilisatrice de Variance Multi-Echelle sur la Sphère (MS-VSTS), consistant à combiner une transformée multi-échelles sur la sphère (ondelettes, curvelets), avec une transformée stabilisatrice de variance (VST). Cette méthode est appliquée à la suppression du bruit de Poisson mono et multicanale, à l’interpolation de données manquantes, à l’extraction d’un modèle de fond et à la déconvolution multicanale. Enfin, ce mémoire aborde le problème de la séparation de composantes en utilisant des représentations parcimonieuses (template fitting). / This thesis presents new methods for spherical Poisson data analysis for the Fermi mission. Fermi main scientifical objectives, the study of diffuse galactic background et the building of the source catalog, are complicated by the weakness of photon flux and the point spread function of the instrument. This thesis proposes a new multi-scale representation for Poisson data on the sphere, the Multi-Scale Variance Stabilizing Transform on the Sphere (MS-VSTS), consisting in the combination of a spherical multi-scale transform (wavelets, curvelets) with a variance stabilizing transform (VST). This method is applied to mono- and multichannel Poisson noise removal, missing data interpolation, background extraction and multichannel deconvolution. Finally, this thesis deals with the problem of component separation using sparse representations (template fitting ).

Les travaux menés lors de cette thèse s’inscrivent dans le cadre général de la détection de cibles en utilisant une forme d’onde non-conventionnelle large bande. L’utilisation d’une forme d’onde large bande à faible PRF a été proposée par le passé une alternative aux traitements multi-PRF qui limitent le temps d’illumination de la scène. En effet, l’augmentation de la bande instantanée permet d’obtenir une meilleure résolution distance ; les cibles rapides sont alors susceptibles de migrer lors du temps de traitement, mais ce phénomène de couplage distance-vitesse peut être mis à profit pour lever les ambiguïtés. L’objectif de la thèse est alors de développer, pour une forme d’onde large bande avec faible PRF, des traitements prenant en compte la migration des cibles et capables de lever les ambiguïtés vitesse dans des scénarios réalistes. Les travaux se basent sur un algorithme de représentation parcimonieuse non-ambigüe de cibles migrantes, dans un cadre algorithmique Bayésien. Cet algorithme est en revanche développé sous certaines hypothèses, et des travaux de robustification sont alors entrepris afin de l’utiliser sur des scénarios plus réalistes. Dans un premier temps, l’algorithme est robustifié au désalignement des cibles par rapport à la grille d’analyse, puis modifié pour prendre également en compte une possible composante diffuse de bruit. Il est également remanié pour estimer correctement une scène comportant une forte diversité de puissance, où des cibles fortes masquent potentiellement des cibles faibles. Les différents algorithmes sont validés à la fois sur des données synthétiques et expérimentales. / The work conducted during this PhD falls within the general context of radar target detection using a non-conventional wideband waveform. More precisely, the use of a low-PRF wideband waveform has been proposed in the past as an alternative to the classical staggered-PRF processing used to mitigate velocity ambiguities that limits dwell time. Increasing the instantaneous bandwidth improves range resolution; fast moving targets are then likely to migrate during the coherent processing interval. This range-velocity coupling can then be used to mitigate velocity ambiguities. This PhD thesis aims at developing an algorithm able to provide unambiguous estimation of migrating targets using a low-PRF wideband waveform. It is based on a sparse representation algorithm able to unambiguously estimate migrating targets, within a Bayesian framework. However, this algorithm is developed under some hypothesis, and then requires robustification to be used on more realistic scenarii. First, the algorithm is robustified to the case of off-grid targets, and then upgraded to take into account a possible diffuse clutter component. On the other hand, the reference algorithm is modified to accurately estimate high dynamic range scenes where weak targets compete with strong targets. All the developed algorithms have been validated on synthetic and experimental data recorded by the PARSAX radar from the Technical University of Delft, The Netherlands.

Computational methods in single molecule localization microscopy Abstract Fluorescence microscopy is one of the chief tools used in biomedical research as it is a non invasive, non destructive, and highly specific imaging method. Unfortunately, an optical microscope is a diffraction limited system. Maximum achievable spatial resolution is approximately 250 nm laterally and 500 nm axially. Since most of the structures in cells researchers are interested in are smaller than that, increasing resolution is of prime importance. In recent years, several methods for imaging beyond the diffraction barrier have been developed. One of them is single molecule localization microscopy, a powerful method reported to resolve details as small as 5 nm. This approach to fluorescence microscopy is very computationally intensive. Developing methods to analyze single molecule data and to obtain super-resolution images are the topics of this thesis. In localization microscopy, a super-resolution image is reconstructed from a long sequence of conventional images of sparsely distributed single photoswitchable molecules that need to be sys- tematically localized with sub-diffraction precision. We designed, implemented, and experimentally verified a set of methods for automated processing, analysis and visualization of data acquired...

Computational methods in single molecule localization microscopy Abstract Fluorescence microscopy is one of the chief tools used in biomedical research as it is a non invasive, non destructive, and highly specific imaging method. Unfortunately, an optical microscope is a diffraction limited system. Maximum achievable spatial resolution is approximately 250 nm laterally and 500 nm axially. Since most of the structures in cells researchers are interested in are smaller than that, increasing resolution is of prime importance. In recent years, several methods for imaging beyond the diffraction barrier have been developed. One of them is single molecule localization microscopy, a powerful method reported to resolve details as small as 5 nm. This approach to fluorescence microscopy is very computationally intensive. Developing methods to analyze single molecule data and to obtain super-resolution images are the topics of this thesis. In localization microscopy, a super-resolution image is reconstructed from a long sequence of conventional images of sparsely distributed single photoswitchable molecules that need to be sys- tematically localized with sub-diffraction precision. We designed, implemented, and experimentally verified a set of methods for automated processing, analysis and visualization of data acquired...

Dans cette thèse, nous nous concentrons sur comment les représentations parcimonieuses peuvent aider à augmenter les performances pour réduire le bruit, extraire des régions de texte, reconnaissance des formes et localiser des symboles dans des documents graphiques. Pour ce faire, tout d'abord, nous donnons une synthèse des représentations parcimonieuses et ses applications en traitement d'images. Ensuite, nous présentons notre motivation pour l'utilisation de dictionnaires d'apprentissage avec des algorithmes efficaces pour les construire. Après avoir décrit l'idée générale des représentations parcimonieuses et du dictionnaire d'apprentissage, nous présentons nos contributions dans le domaine de la reconnaissance de symboles et du traitement des documents en les comparants aux travaux de l'état de l'art. Ces contributions s'emploient à répondre aux questions suivantes: La première question est comment nous pouvons supprimer le bruit des images où il n'existe aucune hypothèse sur le modèle de bruit sous-jacent à ces images ? La deuxième question est comment les représentations parcimonieuses sur le dictionnaire d'apprentissage peuvent être adaptées pour séparer le texte du graphique dans des documents? La troisième question est comment nous pouvons appliquer la représentation parcimonieuse à reconnaissance de symboles? Nous complétons cette thèse en proposant une approche de localisation de symboles dans les documents graphiques qui utilise les représentations parcimonieuses pour coder un vocabulaire visuel / In this thesis, we focus on how sparse representations can help to increase the performance of noise removal, text region extraction, pattern recognition and spotting symbols in graphical documents. To do that, first of all, we give a survey of sparse representations and its applications in image processing. Then, we present the motivation of building learning dictionary and efficient algorithms for constructing a learning dictionary. After describing the general idea of sparse representations and learned dictionary, we bring some contributions in the field of symbol recognition and document processing that achieve better performances compared to the state-of-the-art. These contributions begin by finding the answers to the following questions. The first question is how we can remove the noise of a document when we have no assumptions about the model of noise found in these images? The second question is how sparse representations over learned dictionary can separate the text/graphic parts in the graphical document? The third question is how we can apply the sparse representation for symbol recognition? We complete this thesis by proposing an approach of spotting symbols that use sparse representations for the coding of a visual vocabulary