Les méthodes classiques de compression d’image sont communément basées sur des transformées fréquentielles telles que la transformée en Cosinus Discret (DCT) ou encore la transformée discrète en ondelettes. Nous présentons dans ce document une méthode originale basée sur une transformée combinatoire celle de Burrows-Wheeler(BWT). Cette transformée est à la base d’un réagencement des données du fichier servant d’entrée au codeur à proprement parler. Ainsi après utilisation de cette méthode sur l’image originale, les probabilités pour que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte sont alors augmentées. Cette technique est utilisée pour la compression de texte, comme le format BZIP2 qui est actuellement l’un des formats offrant un des meilleurs taux de compression. La chaîne originale de compression basée sur la transformée de Burrows-Wheeler est composée de 3 étapes. La première étape est la transformée de Burrows-Wheeler elle même qui réorganise les données de façon à regrouper certains échantillons de valeurs identiques. Burrows et Wheeler conseillent d’utiliser un codage Move-To-Front (MTF) qui va maximiser le nombre de caractères identiques et donc permettre un codage entropique (EC) (principalement Huffman ou un codeur arithmétique). Ces deux codages représentent les deux dernières étapes de la chaîne de compression. Nous avons étudié l’état de l’art et fait des études empiriques de chaînes de compression basées sur la transformée BWT pour la compression d’images sans perte. Les données empiriques et les analyses approfondies se rapportant aux plusieurs variantes de MTF et EC. En plus, contrairement à son utilisation pour la compression de texte,et en raison de la nature 2D de l’image, la lecture des données apparaît importante. Ainsi un prétraitement est utilisé lors de la lecture des données et améliore le taux de compression. Nous avons comparé nos résultats avec les méthodes de compression standards et en particulier JPEG 2000 et JPEG-LS. En moyenne le taux de com-pression obtenu avec la méthode proposée est supérieur à celui obtenu avec la norme JPEG 2000 ou JPEG-LS / Common image compression standards are usually based on frequency transform such as Discrete Cosine Transform or Wavelets. We present a different approach for loss-less image compression, it is based on combinatorial transform. The main transform is Burrows Wheeler Transform (BWT) which tends to reorder symbols according to their following context. It becomes a promising compression approach based on contextmodelling. BWT was initially applied for text compression software such as BZIP2 ; nevertheless it has been recently applied to the image compression field. Compression scheme based on Burrows Wheeler Transform is usually lossless ; therefore we imple-ment this algorithm in medical imaging in order to reconstruct every bit. Many vari-ants of the three stages which form the original BWT-based compression scheme can be found in the literature. We propose an analysis of the more recent methods and the impact of their association. Then, we present several compression schemes based on this transform which significantly improve the current standards such as JPEG2000and JPEG-LS. In the final part, we present some open problems which are also further research directions

Depuis l'invention de la radiographie au début du vingtième siècle et des premiers radars lors la seconde guerre mondiale, le besoin de connaître notre environnement par différentes techniques d'imagerie n'a cessé de croître. Ce besoin a pris de multiples formes, allant de l'exploration d'une structure interne avec la prolifération des techniques d'imagerie non invasives à l'imagerie par satellite qui accompagna la conquête de l'espace. Nombre de systèmes d'imagerie ont donc été proposés pour arriver à créer les images les plus représentatives des milieux étudiés. Parmi eux la tomodensitométrie, ou scanner médical, a connu un succès remarquable depuis son invention. La raison de ce succès vient du fait que son principe de fonctionnement est fondé sur la transformée de Radon dont l'inversion permet de restituer une image fidèle de l'intérieur du milieu étudié.La transformée de Radon (TR) est une transformée géométrique intégrale, qui intègre une densité physique d'intérêt, le long d'une droite du plan. Il est donc naturel de penser qu'une généralisation de la TR, qui consiste à remplacer la droite, support d'intégration, par une courbe ou par une surface, peut amener à une nouvelle imagerie. Dans cette thèse, nous étudions deux types de transformées de Radon généralisées qui sont définies sur des lignes brisées en V du plan (appelées TRV) et des sphères centrées sur un plan fixe (appelées TRS) ainsi que leurs imageries correspondantes.Les transformées de Radon généralisées sur des lignes brisées (TRV) nous permettent de proposer trois nouvelles modalités tomographiques. La première, comme la tomodensitométrie, exploite le phénomène d'atténuation du rayonnement X lors de sa propagation dans un milieu mais utilise aussi le phénomène de réflexion du rayonnement sur une surface impénétrable. La deuxième exploite le phénomène de diffusion Compton du rayonnement émis par un objet. La troisième combine deux modalités d'imageries par transmission et par émission sous la forme d'une imagerie bimodale à partir du rayonnement ionisant diffusé. Cette étude permet non seulement de faire émerger de nouvelles imageries pouvant concurrencer celles existantes mais aussi d'établir de nouveaux algorithmes pour la correction de l'atténuation (un des facteurs physiques dégradant sérieusement la qualité d'image tomographique actuellement).La transformée de Radon sur des sphères centrées sur un plan fixe (TRS) est une généralisation connue de la transformée de Radon en trois dimensions. Elle a été proposée comme modèle mathématique de l'imagerie radar à synthèse d'ouverture (RSO). On montre par la construction d'algorithmes appropriés que l'inversion de cette TRS donne une solution efficace à la reconstruction d'images de l'environnement directement en 3D.La faisabilité théorique de ces nouvelles imageries modélisées par ces deux classes de transformées de Radon généralisées et la performance des algorithmes de reconstruction d'images basés sur les formules d'inversion de ces transformées ouvrent plusieurs perspectives : extension en 3D de l'imagerie bimodale par rayonnement ionisant diffusé, ou possibilité de détection de cibles mobiles en imagerie RSO par introduction d'autres généralisations de la TR. De plus, les méthodes développés dans cette thèse sont susceptibles d'application dans d'autres imageries : imagerie sismique modélisée par la transformée de Radon définie sur des paraboles, imagerie radar Doppler par la TR sur des hyperboles ou encore imagerie thermo-opto-acoustique modélisée par la TR sur des cercles centrés sur un cercle fixe. / Since the invention of radiography at the beginning of the 20th century and of the radar during the 2nd world war, the need of information on our environment is ever increasing. This goes from the exploration of internal structures using non-invasive numerous imaging techniques to satellite imaging which rapidly expands with space exploration. A huge number of imaging systems have been conceived to provide faithful images of the objects of interest. Computed Tomography (or the medical scanner) has experienced a tremendous success since it was invented. The reason for this success lies in the fact that its mathematical foundation is the Radon transform (RT), which has an inverse formula allowing the faithful reconstruction of the interior of an object.The Radon transform is a geometric integral transform which integrates a physical density of interest along a straight line in the plane. It is natural to expect that, when the line is replaced by a curve or a surface as an integration support, new imaging processes may emerge. In this thesis, we study two generalized Radon transforms which are defined on broken lines in the form of a letter V (called V-line RT or VRT) and on spheres centered on a fixed plane (called spherical RT or SRT), as well as their resulting imaging processes.The Radon transforms on V-lines (VRT) form the mathematical foundation of three tomographic modalities. The first modality exploits not only the attenuation of X-rays in traversed matter (as in Computed Tomography) but also the phenomenon of reflection on an impenetrable surface. The second modality makes use of Compton scattering for emission imaging. The third modality combines transmission and emission imaging modalities into a bimodal imaging system from scattered ionizing radiation. This study puts forward new imaging systems which compete with the existing ones and develops new algorithms for attenuation corrections (in emission imaging the attenuation is one of factors degrading seriously tomographic image quality up to now).The Radon transform on spheres centered on a fixed plane (SRT) is a generalization of the classical Radon transform in three dimensions. It has been proposed as a mathematical model for Synthetic Aperture Radar (SAR) imaging. We show through the setting up of appropriate algorithms that the inversion of the SRT yields an efficient solution to the landscape reconstruction problem, directly in three dimensions.The theoretical feasibility of these new imaging systems based on generalized Radon transforms and the good performance of inversion algorithms based on inversion formulas open the way to several perspectives: 3D extension of bimodal imaging by scattered radiation or SAR target motion detection through the introduction of other generalized Radon transforms. Moreover the algorithmic methods developed here may serve in other imaging activities such as: seismics with the parabolic Radon transform, Doppler radar with the hyperbolic Radon transform, thermo-opto-acoustic imaging with the Radon transform on circles centered on a fixed circle.

Les techniques avancées pour l’approximation de rang faible des matrices sont des outils de réduction de dimension fondamentaux pour un grand nombre de domaines du calcul scientifique. Les approches hiérarchiques comme les matrices H2, en particulier la méthode multipôle rapide (FMM), bénéficient de la structure de rang faible par bloc de certaines matrices pour réduire le coût de calcul de problèmes d’interactions à n-corps en O(n) opérations au lieu de O(n2). Afin de mieux traiter des noyaux d’interaction complexes de plusieurs natures, des formulations FMM dites ”kernel-independent” ont récemment vu le jour, telles que les FMM basées sur l’interpolation polynomiale. Cependant elles deviennent très coûteuses pour les noyaux tensoriels à fortes dimensions, c’est pourquoi nous avons développé une nouvelle formulation FMM efficace basée sur l’interpolation polynomiale, appelée Uniform FMM. Cette méthode a été implémentée dans la bibliothèque parallèle ScalFMM et repose sur une grille d’interpolation régulière et la transformée de Fourier rapide (FFT). Ses performances et sa précision ont été comparées à celles de la FMM par interpolation de Chebyshev. Des simulations numériques sur des cas tests artificiels ont montré que la perte de précision induite par le schéma d’interpolation était largement compensées par le gain de performance apporté par la FFT. Dans un premier temps, nous avons étendu les FMM basées sur grille de Chebyshev et sur grille régulière au calcul des champs élastiques isotropes mis en jeu dans des simulations de Dynamique des Dislocations (DD). Dans un second temps, nous avons utilisé notre nouvelle FMM pour accélérer une factorisation SVD de rang r par projection aléatoire et ainsi permettre de générer efficacement des champs Gaussiens aléatoires sur de grandes grilles hétérogènes. Pour finir, nous avons développé un algorithme de réduction de dimension basé sur la projection aléatoire dense afin d’étudier de nouvelles façons de caractériser la biodiversité, à savoir d’un point de vue géométrique. / Advanced techniques for the low-rank approximation of matrices are crucial dimension reduction tools in many domains of modern scientific computing. Hierarchical approaches like H2-matrices, in particular the Fast Multipole Method (FMM), benefit from the block low-rank structure of certain matrices to reduce the cost of computing n-body problems to O(n) operations instead of O(n2). In order to better deal with kernels of various kinds, kernel independent FMM formulations have recently arisen such as polynomial interpolation based FMM. However, they are hardly tractable to high dimensional tensorial kernels, therefore we designed a new highly efficient interpolation based FMM, called the Uniform FMM, and implemented it in the parallel library ScalFMM. The method relies on an equispaced interpolation grid and the Fast Fourier Transform (FFT). Performance and accuracy were compared with the Chebyshev interpolation based FMM. Numerical experiments on artificial benchmarks showed that the loss of accuracy induced by the interpolation scheme was largely compensated by the FFT optimization. First of all, we extended both interpolation based FMM to the computation of the isotropic elastic fields involved in Dislocation Dynamics (DD) simulations. Second of all, we used our new FMM algorithm to accelerate a rank-r Randomized SVD and thus efficiently generate multivariate Gaussian random variables on large heterogeneous grids in O(n) operations. Finally, we designed a new efficient dimensionality reduction algorithm based on dense random projection in order to investigate new ways of characterizing the biodiversity, namely from a geometric point of view.

Cette thèse examine la relation entre paysage et imaginaire national dans le contexte du paysage transformé des Trois Gorges du fleuve Yangzi en République Populaire de Chine à travers l’exploration de trois types de dimensions du paysage : politique, poétique et économique. Tout d’abord, l’étude des dimensions politiques met en évidence la marchandisation du paysage des Trois Gorges réalisée par l’Etat à travers l’invisibilisation de la disparition du paysage, ainsi que l’absence massive d’agentivité du peuple dans sa relation au paysage national, concluant ainsi à l’épuisement de l’appréciation paysagère. Ensuite, l’étude des dimensions poétiques analyse le livre Three Gorges Diary de Yan Changjiang 颜长江, journal intime littéraire et photographique décrivant les dernières années du paysage fluvial avant sa submersion et exprimant une intense émotion de regret menant à un sursaut de résistance. Puis, l’étude des dimensions économiques considère l’intérieur du paysage fluvial avec une étude ethnographique menée dans un village situé à l’entrée de la Gorge Qutang et s’interroge sur la question de l’absence du paysage due à un manque d’extériorité et donc de distanciation, et la question de l’apparition économique du paysage liée à la relation entre paysage et droits fonciers ruraux et à l’événement national de la traversée de la Gorge Qutang par un funambule canadien en 1995. Enfin, prenant pour bornes temporelles l’année 1994 avec le début de la construction du Barrage des Trois Gorges et l’année 2014 avec la gratuité de l’entrée au site touristique du barrage accordée à tous les visiteurs « chinois » (distingués en terme de définition raciale étendue au-delà de la Chine continentale), cette thèse se termine sur une longue conclusion en forme d’essai sur la question de la kitschification de la réalité dans le contexte de la postmodernité dans les années 2010 et sur le potentiel subversif de l’imagination d’une nouvelle appréciation paysagère dans l’opposition à la marchandisation de la réalité. / This thesis examines the relation between landscape and the national imaginary in the context of the Yangzi’s Three Gorges transformed riverscape in the People’s Republic of China through the exploration of three kinds of landscape dimensions: political, poetic and economic. First, the study of the political dimensions highlights the commodification of the Three Gorges landscape performed by the State through the invisibilisation of the landscape’s disappearance, as well as the massive absence of agency from the people in its relating to the national landscape, thus concluding in the exhaustion of landscape appreciation. Second, the study of the poetic dimensions analyses Yan Changjiang 颜长江’s book Three Gorges Diary, a literary and photographical diary recounting the last years of the riverscape before its submersion and expressing an intense emotion of regret leading to a burst of resistance. Third, the study of the economic dimensions considers the inside of the riverscape with an ethnographic study carried out in a village located at the entrance of the Qutang Gorge and reflects upon the issue of the absence of landscape due to the lack of distancing exteriority, and the issue of the economic appearance of landscape related to the question of the relation between landscape and rural land rights and to the context of the national event of the tightrope walk over the Qutang Gorge that took place in 1995. Finally, starting in 1994 with the beginning of the construction of the Three Gorges Dam and ending in 2014 with the free entrance to the Three Gorges Dam touristic spot granted to all the “Chinese” visitors (with a racial definition extended to non-mainlanders), this thesis ends on a long conclusion in the form of an essay on the question of the kitschification of reality in the context of postmodernity in the 2010’s and on the subversive potential of the imagining of a new landscape appreciation in opposing the commodification of reality.