Dans cette thèse, nous étudions des problèmes algorithmiques dans les complexes CAT(0) planaires et rectangulaires munis d'une m ́etrique intrinsèque l_2. Nous proposons des algorithmes de calcul du plus court chemin dans les complexes CAT(0) planaires et rectangulaires et de construction de l'enveloppe convexe d'un ensemble fini de points dans les complexes CAT(0) planaires. E ́tant donné un complexe CAT(0) rectangulaire 2-dimensionnel K à n sommets, nous proposons un algorithme qui, pour toute paire de points calcule la distance et le plus court chemin en temps sous-lin ́eaire en nombre de sommets de K, en utilisant une structure de données de taille O(n^2). Le deuxième problème étudié est celui du plus court chemin entre un point-source donné et tout autre point dans un complexe CAT(0) planaire K a n sommets. Pour cela, nous proposons un algorithme qui, pour tout point y de K, étant donnée le point source x et la carte géodésique SPM(x), construit le plus court chemin γ(x,y) en temps O(n), en utilisant une structure de données de taille O(n^2). Enfin, nous nous intéressons au calcul de l'enveloppe convexe d'un ensemble de k points dans un complexe CAT(0) planaire à n sommets. Nous proposons un algorithme qui construit l'enveloppe convexe en temps O(n^2 + nk log k) en utilisant une structure de données de taille O(n^2 + k). / In this thesis, we study algorithmic problems in CAT(0) planar and rectangular complexes with an intrinsic l_2−metric. We present algorithms for some algorithmic problems, such as computing the shortest path and the convex hull of a finite set of points in CAT(0) planar and rectangular complexes. We present an efficient algorithm for answering two-point distance queries in a given CAT(0) rectangular complex K with n vertices. Namely, we show that for a CAT(0) rectangular complex K with n vertices, one can construct a data structure of size O(n^2) so that, given any two points in K, the shortest path can be computed in subliniar time of n. The second problem presented is computing shortest path from a single-source to the query point in a CAT(0) planar complex. We propose an algorithm which computes in O(n) time the shortest path between a given point and the query point in a CAT(0) planar complex with n vertices, using a given shortest path map and data structure of size O(n^2). Finally, we study the problem of computing the convex hull of a set of k points in a CAT(0) planar complex with n vertices. We describe an algorithm which computes the convex hull in O(n^2 + nk log k) time, using a data structure of size O(n^2 + k).

On étudie le comportement topologique du flot horocyclique sur des surfaces hyperboliques géométriquement infinies. Cette étude est intimement liée à celle du flot géodésique sur ces surfaces. Le premier chapitre commence par introduire les objets de géométrie hyperbolique que nous utiliserons. Il présente ensuite une classe de surfaces, les flûtes hyperboliques, qui couvrent une grande partie de la complexité des surfaces géométriquement infinies. Enfin, il aborde la notion de finesse asymptotique d'une demi-géodésique, qui donne la limite inférieure du rayon d'injectivité de la surface le long de la demi-géodésique. Le deuxième chapitre est consacré aux propriétés classiques du flot horocyclique sur lesquelles nous baserons nos preuves. Le troisième chapitre concerne l'étude de l'intersection entre l'adhérence de l'orbite horocyclique issue d'un vecteur u d'une surface hyperbolique et la demi orbite géodésique issue de ce même vecteur. Nous montrons que si la finesse asymptotique de la demi-orbite géodésique issue de u est finie et si u n'est pas périodique pour le flot horocyclique, cette intersection contient une infinité divergente de points. Par ailleurs, si la finesse asymptotique est nulle, alors cette intersection est égale à toute la demi-orbite géodésique positive. Nous montrons cependant que même si la finesse asymptotique n'est pas nulle, la demi-orbite géodésique peut tout de même être contenue dans cette intersection. Le quatrième chapitre étudie les liens entre une orbite horocyclique issue d'un vecteur u et la feuille fortement stable associée. Nous commençons par montrer que les adhérences de ces deux ensembles coïncident toujours. Cependant, cette propriété ne s'étend pas aux ensembles eux-mêmes et nous donnons ensuite une condition suffisante pour que qu'ils ne coïncident pas. Nous montrons qu'alors la feuille fortement stable est une union d'une quantité non dénombrable d'orbites horocycliques. / We study the topological behavior of the horocycle flow on geometrically infinite hyperbolic surfaces. This study and that of the geodesic flow are deeply interwoven. The first chapter introduces the basic objects of hyperbolic geometry that we will use. Next, it presents a class of surfaces, the hyperbolic flutes, which carries most of the complexity of geometrically infinite surfaces. Then, it details the notion of asymptotic thinness for a half-geodesic, which determines the size of the most thin parts that this half-geodesic crosses. The second chapter focuses on the classical properties of the horocycle flow on which we will base our proofs. The third chapter presents the study of the intersection between the closure of a horocyclic orbit stemming from a vector u on a hyperbolic surface and the positive half-geodesic stemming from the same vector. We show that if the asymptotic thinness of the half-orbit stemming from u is finite and if u is not periodic for the horocycle flow, then this intersection contains an unbounded sequence of points. Moreover, if the asymptotic thinness is zero, then all the halfgeodesic orbit is included in the intersection. However, we also prove that the half-geodesic orbit can be included in the intersection and even if the asymptotic thinness is not zero. The fourth chapter studies the links between a horocyclic orbit starting from a vector u and the strong stable manifold associated to u. We first show that the closure of these two sets are always the same. However, we then give a sufficient condition for these two sets to be different and we prove that in this case, the strong stable manifold is a reunion of an uncountable number of horocyclic orbits.

La transformée en ondelettes a été introduite ces dernières années dans le domaine du traitement des données multimédia car elle permet une représentation compacte des informations. Cette transformée conçue initialement pour les signaux 1D, ne s'appuie pas sur les spécificités des signaux 2D. Afin de prendre en compte ces spécificités, plusieurs transformées en ondelettes géométriques ont été proposées : nous en étudions deux propositions dans cette thèse. Plus particulièrement, nous allons présenter deux transformées en ondelettes géométriques adaptatives, c'est à dire, deux transformées en ondelettes dont l'ensemble des fonctions d'analyse et de synthèse est défini à partir de l'identification des singularités de l'image. La première transformée, définie par Le Pennec, s'appuie sur une détection des contours pour extraire et traiter séparément des bandes de l'image. La deuxième transformée s'appuie quand à elle, sur un ensemble de mesures de la distance géodésique spécifique au signal traité. Cet ensemble de mesures est ensuite exploité à travers un schéma de lifting pondéré. Ces deux transformées sont confrontées aux applications de suppression de bruit et de suppression de l'effet de bloc lié à la compression JPEG. Nous commenterons ces résultats afin de mettre en évidence les apports ainsi que les limites de ces approches.

On présentera des techniques de mise en correspondance de divers types d'objets. On s'intéressera dans un premier temps à la mise en correspondance géodésique d'objets qui consiste, par le biais de l'action d'un groupe de déformation sur un ensemble d'objets, à définir une distance géodésique sur la variété riemannienne formée par l'ensemble en question, qui soit invariante par l'action de groupe considérée. Dans un premier temps, on s'intéressera à la mise en correspondance d'images sur lesquelles agissent des difféomorphismes. On en déduira un algorithme que l'on perfectionnera par une stratégie multi échelle. On adaptera cette technique de mise en correspondance géodésique à des objets tels que des points ou des vecteurs grâce à une modélisation de la déformation à base de splines. Enfin, on présentera des techniques de mise en correspondance d'ensembles de primitives avec appariement des primitives une à une.

La fusion par confinement magnétique est prometteuse en tant que future source d’énergie. Son efficience est cependant limitée par le transport de particules et de chaleur résultant de la turbulence du plasma. Une compréhension approfondie de la turbulence et des mécanismes qui la tempère est donc nécessaire. Le mode géo-acoustique (GAM) est une oscillation de l’écoulement du plasma, radialement localisée, qui contribue à la réduction du transport turbulent en cisaillant le champ de vitesse. Dans cette thèse on étudie le comportement fondamental du GAM par une étude expérimentale systématique de ses propriétés dans le tokamak ASDEX Upgrade. En particulier, le rôle de la géométrie du plasma sur les lois d’évolution de la fréquence et de l’amplitude du GAM, ainsi que sa structure radiale sont étudiés en détail. Les données expérimentales ont été obtenues à l'aide du diagnostic de réflectométrie Doppler par micro-ondes. Le type d’évolution de la fréquence du GAM est comparé à de multiples modèles qui reproduisent la loi de comportement fondamental attendu, mais sans fournir de prédiction précise de manière satisfaisante. L'amplitude GAM est étudiée en relation avec les taux d'amortissement prédits par les modèles pour les processus d'amortissement collisionnel et Landau non collisionnel. On trouve que les effets de largeur d'orbite finie doivent être pris en compte et que les effets d'amortissement collisionnel ne peuvent pas être négligés. En étudiant la structure radiale du GAM, trois états distincts sont identifiés pour différentes conditions de plasma. Les transitions entre ces états sont observées en variant la géométrie du plasma / Magnetic confinement fusion is a promising candidate for a future energy source. Its efficiency is limited by particle and heat transport due to plasma turbulence. A thorough understanding of the turbulence and turbulence moderation mechanisms, is therefore needed. The geodesic acoustic mode (GAM) is a radially localised plasma flow oscillation which contributes to the reduction of turbulent transport through velocity shearing. This thesis investigates the fundamental behaviour of the GAM through a systematic experimental study of its properties in the ASDEX Upgrade tokamak. In particular, the role of the plasma geometry on the scaling of the GAM frequency and amplitude, as well as the GAM radial structure are investigated in detail. The experimental data was obtained with the aid of the microwave Doppler reflectometry diagnostic. The GAM frequency scaling is compared with multiple models which reproduce the expected fundamental scaling behaviour, but do not give a satisfyingly accurate prediction. The GAM amplitude is studied in connection with damping rates predicted by models for collisional and collisionless Landau damping processes. It is found that finite orbit width effects need to be considered and that collisional damping effects cannot be neglected. In studying the GAM radial structure, three distinct states are identified for different plasma conditions. Transitions between these states are observed under variations of the plasma geometry

Grâce au théorème d'hyperbolisation, nous savons précisément quand une variété de dimension trois compacte admet une métrique hyperbolique. Par ailleurs, d'après le théorème de rigidité de Mostow, cette structure géométrique est unique. Cependant, trouver des liens pratiques entre la géométrie et la topologie est un problème difficile. La plupart des résultats décrits dans cette thèse visent à concrétiser ces liens. Toute géodésique fermée orientée dans une surface hyperbolique admet un relèvement canonique dans le fibré tangent unitaire de la surface, et on peut donc le voir comme un nœud dans une variété de dimension trois. Les extérieurs des nœuds ainsi construits admettent une structure hyperbolique. Cette thèse a pour objet d'estimer le volume des extérieurs des relèvements canoniques. Pour toute surface hyperbolique on construit une suite de géodésique sur la surface, tel que les extérieurs associées ne sont pas homéomorphes entre elles et dont la suite des volumes respectifs est bornée. Aussi on minore le volume de l'extérieur à l'aide d'un réel explicite qui décrit une relation entre la géodésique et une décomposition en pantalons de la surface. Ceci donne une méthode pour construire une suite de géodésiques dont les volumes des extérieurs associées sont minorées en termes de la longueur de la géodésique correspondant. Dans le cas particulier de la surface modulaire, on obtient des estimations du volume de l'extérieur en termes de la période de la fraction continue associée à la géodésique. / Due to the Hyperbolization Theorem, we know precisely when does a given compact three dimensional manifold admits a hyperbolic metric. Moreover, by the Mostow's Rigidity Theorem this geometric structure is unique. However, finding effective and computable connections between the geometry and topology is a challenging problem. Most of the results on this thesis fit into the theme of making the connections more concrete. To every oriented closed geodesic on a hyperbolic surface has a canonical lift on the unit tangent bundle of the surface, and we can see it as a knot in a three dimensional manifold. The knot complement given in this way has a hyperbolic structure. The objective of this thesis is to estimate the volume of the canonical lift complement. For every hyperbolic surface we give a sequence of geodesics on the surface, such that the knot complements associated are not homeomorphic with each other and the sequence of the corresponding volumes is bounded. We also give a lower bound of the volume of the canonical lift complement by an explicit real number which describes a relation between the geodesic and a pants decomposition of the surface. This give us a method to construct a sequence of geodesics where the volume of the associated knot complements is bounded from below in terms of the length of the corresponding geodesic. For the particular case of the modular surface, we obtain estimations for the volume of the canonical lift complement in terms of the period of the continuous fraction expansion of the corresponding geodesic.

Dans ce mémoire, nous étudions l'entropie des systèmes dynamiques différentiables définis sur des variétés riemanniennes non compactes. Dans un premier temps, nous éclaircissons les liens entre différentes notions d'entropie dans ce cadre non compact. Ensuite, nous utilisons ces premiers résultats pour y étudier la validité de l'inégalité de Ruelle. Rappelons ici que cette inégalité, pour des difféomorphismes de variétés riemanniennes compactes, nous dit que l'entropie est majorée par la somme des exposants de Lyapounov positifs. Nous montrons que, lorsque nous enlevons l'hypothèse de compacité, l'inégalité de Ruelle n'est pas toujours satisfaite. Nous obtenons ce résultat en construisant une famille explicite de contre-exemples. En revanche, nous montrons, dans le cas d'un difféomorphisme de comportement asymptotique linéaire, ou du flot géodésique sur le fibré unitaire tangent d'une variété riemannienne à courbure négative, que l'inégalité de Ruelle est toujours satisfaite. Pour finir, nous nous intéressons au problème de la perte possible de masse d'une suite de mesures de probabilité d'une variété riemannienne non compacte. Dans le cas du flot géodésique, nous montrons que l'entropie permet de contrôler la masse d'une limite vague de mesures de probabilité invariantes par le flot pour une classe particulière de variétés géométriquement finies. Plus précisément, nous montrons qu'une suite de mesures d'entropie assez grande ne peut pas perdre la totalité de sa masse. De plus, le minorant optimal de l'entropie dans ce résultat est lié à la géométrie de la partie non compacte de la variété: c'est l'exposant critique maximal des sous-groupes paraboliques du groupe fondamental. / In this work, we study the entropy of smooth dynamical systems defined on non compact Riemannian manifolds. First, we clarify some relations between different notions of entropy in this setting. Second, we use these first results in order to study the validity of Ruelle's inequality. This inequality, for diffeomorphisms defined on compact Riemannian manifolds, says that the measure-theoretic entropy is bounded from above by the sum of the positive Lyapunov exponents. We show that without the compactness assumption, Ruelle's inequality is not always satisfied. We obtain this result by constructing an explicit family of counterexamples. On the other hand, we prove, in the case of diffeomorphisms with linear asymptotic behavior, or that one of the geodesic flow on the unit tangent bundle of a Riemannian manifold with negative curvature, that Ruelle's inequality is always satisfied. Finally, we are interested in the problem of the possible escape of mass of a sequence of probability measures on a non compact Riemannian manifold. In the case of the geodesic flow, we show that the entropy allows to control the mass of a weak$^\ast$-limit of a sequence of probability measures, on the unit tangent bundle of a particular class of geometrically finite manifolds, which are also invariant by the flow. More precisely, we show that a sequence of measures with large enough entropy cannot lose the whole mass. Moreover, the optimal lower bound of the entropy in this result is related to the geometry of the non compact part of the manifold: it is the maximal critical exponent of the parabolic subgroups of the fundamental group.

Les performances d’un système de reconnaissance de formes dépendent en bonne partie de la qualité de l’image segmentée. Malgré les progrès effectués, une segmentation complète (c’est-à-dire avec des contours entiers) ne peut pas être toujours atteinte. Dans un premier temps, nous nous plaçons dans le cas où seulement certaines parties de la forme entière sont disponibles. D’abord, afin d’assurer l’invariance des parties de formes aux transformations géométriques, nous développons une méthode d’optimisation de l’analyse procustéenne qui consiste à retrouver les points extrémités optimaux qui minimisent la distance de Procutse. Ensuite, nous proposons une approche de reconnaissance de parties de formes et une approche de reconnaissance de formes partielles. Ces deux approches, basées-contour, sont fondées sur un recalage robuste entre les parties de formes. La méthode de recalage proposée consiste à optimiser une mesure de similarité basée sur les géodésiques dans l’espace de formes. Ainsi, nous exploitons le résidu du recalage pour définir une nouvelle métrique pour la reconnaissance de parties de formes. Puis, nous décrivons une stratégie de combinaison avec cette même métrique pour la reconnaissance de formes partielles. Par la suite, nous proposons d’utiliser la distance géodésique proposée pour la reconnaissance des parties de formes dans la définition d’une métrique globale pour la reconnaissance de formes entières. Les tests de reconnaissance (classification et recherche) sont effectués sur des parties requêtes et des formes entières de la base d’images MPEG-7, puis sur des images réelles segmentées. Les résultats expérimentaux montrent la supériorité de nos méthodes par rapport aux autres méthodes de l’état de l’art. / The quality of the segmentation process directly affects the performance of the shape recognition. Despite the progress that has been made, it is often unreachable to segment the entire object (i.e. closed contour). In fact, only some parts/fragments of objects can be detected. We first develop a new alignment method based on Procrustes analysis in order to ensure invariance of shape parts to geometric transformations (translation, rotation and scale factor). The proposed method consists in finding optimal extremities which minimize the Procrustes distance. Then, we propose a shape part recognition approach and a partial shape recognition approach. These two contour-based approaches are based on matching between shape parts to compare. This matching process consists in establishing a robust registration between shape parts based on geodesics in the shape space. Thus, we exploit the registration residual to define a novel distance for shape part recognition. Later, for partial shape recognition, we describe a geodesics-based combining strategy with the same distance. As well, we propose to use the geodesics distance proposed for shape part recognition to define a global distance for entire shape recognition. Experiments are carried out on parts of shapes and entire shapes of theMPEG-7 database, then on parts issued from segmented real images. The obtained results demonstrate the effectiveness of our proposed recognition schemes. The proposed approaches are shown to significantly outperform previous works for classification and retrieval applications.

Un chemin géodésique entre deux points sur une surface de R³ est un plus court chemin local. Nous proposons deux méthodes de calcul de géodésiques qui ont l'originalité d'utiliser des outils de modélisation géométrique dans ce contexte de géométrie différentielle. La méthode de minimisation propose de travailler sur des surfaces paramétrées et d'étudier le problème en se placant dans l'espace des paramètres. Les courbes considérées y sont les courbes de Bézier et les courbes splines.Leurs points de contrôle constituent les variables par rapport auxquelles la longueur du chemin image sur la surface est minimisée. L'implémentation de cette méthode d'approximation et sa validation sont développées.La méthode de subdivision propose de travailler sur des surfaces de subdivision, limites d'une suite de réseaux générés par un schéma de subdivision. Une méthode itérative de calcul exact de chemin géodésique sur une surface polyédrique est développée. Celle-ci permet ainsi de calculer une suite de chemins géodésiques sur les surfaces polyédriques issues des réseaux de contrôle successifs.La convergence de cette suite de chemins géodésiques est traitée et de nombreux exemples sont présentés.Quelques applications sont enfin proposées : la génération de maillages surfaciques et la modélisation des fibres du myocarde pour l'imagerie médicale.

La géostatistique fournit de nombreux outils pour caractériser et traiter des données réparties dans l'espace. La plupart de ces outils sont basés sur l'analyse et la modélisation d'une fonction appelée variogramme qui permet de construire différents opérateurs spatiaux : le krigeage et les simulations. Les modèles variographiques sont relativement intuitifs : certains paramètres variographiques peuvent être directement interprétés en termes de caractéristiques structurales. Ces approches sont cependant limitées car elles ne permettent pas de prendre correctement en compte la structuration locale des données. Plusieurs types de modèles géostatistiques non-stationnaires existent. Ils requièrent généralement un paramétrage compliqué, peu intuitif, et ils n'apportent pas de réponse satisfaisante quant à certains de types de non-stationnarité. C'est pour répondre au besoin d'une prise en compte efficace et opérationnelle de la non-stationnarité dans un jeu de données que, dans le cadre de cette thèse, nous prenons le parti de déterminer des paramètres variographiques locaux, appelés M-Paramètres par des méthodes de traitement d'images. Notre démarche se fonde principalement sur la détermination des paramètres morphologiques de dimensions et d'orientations de structures. Il résulte de la détermination de M-Paramètres une meilleure adéquation entre modèles variographiques et caractéristiques structurales des données. Les méthodes de détermination de M-Paramètres développées ont été appliquées sur des données bathymétriques, sur des jeux de données laissant apparaître des corps géologiques complexes ou encore sur des jeux de données environnementaux, liés au domaine de la pollution en zone urbaine par exemple. Ces exemples illustrent les améliorations de résultats de traitement géostatistique obtenus avec M-Paramètres. Enfin, partant du constat que certains phénomènes ne respectent pas une propagation euclidienne, nous avons étudié l'influence du choix de la distance sur les résultats de krigeage et de simulation. En utilisant des distances géodésiques, nous avons pu obtenir des résultats d'estimation impossible à reproduire avec des distances euclidiennes.