Cette thèse s’inscrit dans le cadre de l’évolution des Systèmes d’Informations Géographiques (SIG) et de leur capacité à répondre à des problématiques environnementales qui s’expriment de manière globale et transversale. Dans un contexte ou l’information géographique est en plein essor et où la quantité de données disponible ne cesse de croitre, le besoin en terme d’outil d’aide a la décision n’a jamais été aussi fort. Cette étude s’attache tout particulièrement au cadre de la résolution de problématiques liées à l’eau et l’environnement lorsque les données deviennent trop volumineuses pour être traitées par des moyens de calculs séquentiels classiques. Nous proposons une plateforme de calculs répartis sur une grappe d’ordinateurs qui parallélise le calcul de la délimitation des bassins versants des grands fleuves et la détermination des flots d’accumulation. A cette fin nous introduisons une technique de calcul parallèle d’une forêt d’arbres couvrants minimums représentant le parcours de l’eau de chaque point du Modèle Numérique de Terrain (MNT) vers la mer. Cette technique débute par une délimitation des cuvettes (ensemble de points allant vers le même minimum local) contenues dans le MNT. Ensuite une hiérarchie de déversement des cuvettes les unes dans les autres est construite jusqu'à obtenir les bassins versants des fleuves. L’étude se poursuit par la description d’un algorithme parallèle pour le calcul très couteux des flots d’accumulation en chaque point du MNT. Enfin cette thèse présente une version ≪out-of-core≫ de nos algorithmes parallèles afin d’étendre la portée de nos travaux a des grappes de dimensions modestes qui ne peuvent pas charger en mémoire la totalité du MNT traite. / My thesis is part of the development of Geographic Information Systems (GIS) and their ability to respond to environmental challenges that are expressed in a global and transversal way. We consider a context in which geographical information is growing, in addition the amount of data available continues to grow. Therefore, the need a tool for decision support has never been stronger. This study aim to solve problems related to water and the environment when the data become too large for sequential computing. The main objective of the thesis proposes a platform for distributed computing on a cluster of computers that parallelizes the watershed computing of major rivers and the determination of the flow accumulation. The idea is based on the construction of a minimal spanning tree, via a hierarchy of graphs, modeling the water route on the DEM toward the ocean. The technique begins from computing catchment basins that are set of pixels for which a drop of water will end the same local minimum. After that, a hierarchy of basins is computed in order to give the catchment basins of the rivers in the DEM. The study continues with a description of a parallel algorithm for computing the global flow accumulation for automatic drainage network extraction in large digital elevation models. Finally, the thesis presents a version ≪out-of-core≫ of our parallel algorithms to extend the scope of our work in clusters of size small that cannot load into memory the entire treated DEM.

De nos jours la protection des données numériques est un problème très important. Que ce soit pour des applications de confidentialité, de communication, de traçabilité ou d'identification par exemple, il est nécessaire de développer des techniques adaptées. Dans le cadre de cette thèse en collaboration avec la société STRATEGIES S.A., la méthode choisie pour la protection de maillages 3D est l'insertion de données cachées, également appelée tatouage numérique. Pour des données 3D, un des problèmes les plus importants est la phase de synchronisation qui intervient dans les algorithmes d'insertion et d'extraction des données. Cette phase permet de repérer, de sélectionner et d'ordonner les « zones » qui sont privilégiées pour la dissimulation d'information. Nous avons choisi d'orienter le manuscrit sur cette phase. Ainsi, nous proposons une classification des méthodes de tatouages en fonction de leur méthode de synchronisation. Puis en se basant sur des techniques de synchronisation par des structures de données, telle que les arbres couvrants de poids minimum, nous proposons une analyse théorique de cette structure. Dans un premier temps nous expliquons les raisons de la sensibilité des arbres à la mobilité des points. Puis connaissant ses faiblesses, nous proposons une autre technique de synchronisation toujours basée sur les arbres couvrants de poids minimum. / Data security is one of the main issue in computer science. We need to develop solutions for confidentiality, communication, fingerprinting or identification applications for exemple. In this thesis made with STRATEGIES S.A., the chosen method to protect 3D meshes is watermarking.Watermarking is divided in two steps, the embedding and the extraction. In both of them a synchronization phase is needed. It is one of the most important step for 3D mesh because it permits to look for areas available to embed information, and order them. All the thesis is devoted to the synchronization step. First of all, we propose a classification of watermarking techniques based on the type of synchronization method instead of evaluation criterions such as robustness or capacity.Then, from methods based on Euclidean minimum spanning tree, we propose a theoritical analysis of the mobility of the vertices in that kind of structure. First, we explain the reasons of the sensibility of the structure. Secondly, we propose another scheme based on the Euclidean minimum spanning tree knowing its fragility.

Cette thèse s'inscrit dans le cadre de l'évolution des Systèmes d'Informations Géographiques (SIG) et de leur capacité à répondre à des problématiques environnementales qui s'expriment de manière globale et transversale. Dans un contexte ou l'information géographique est en plein essor et où la quantité de données disponible ne cesse de croitre, le besoin en terme d'outil d'aide a la décision n'a jamais été aussi fort. Cette étude s'attache tout particulièrement au cadre de la résolution de problématiques liées à l'eau et l'environnement lorsque les données deviennent trop volumineuses pour être traitées par des moyens de calculs séquentiels classiques. Nous proposons une plateforme de calculs répartis sur une grappe d'ordinateurs qui parallélise le calcul de la délimitation des bassins versants des grands fleuves et la détermination des flots d'accumulation. A cette fin nous introduisons une technique de calcul parallèle d'une forêt d'arbres couvrants minimums représentant le parcours de l'eau de chaque point du Modèle Numérique de Terrain (MNT) vers la mer. Cette technique débute par une délimitation des cuvettes (ensemble de points allant vers le même minimum local) contenues dans le MNT. Ensuite une hiérarchie de déversement des cuvettes les unes dans les autres est construite jusqu'à obtenir les bassins versants des fleuves. L'étude se poursuit par la description d'un algorithme parallèle pour le calcul très couteux des flots d'accumulation en chaque point du MNT. Enfin cette thèse présente une version ≪out-of-core≫ de nos algorithmes parallèles afin d'étendre la portée de nos travaux a des grappes de dimensions modestes qui ne peuvent pas charger en mémoire la totalité du MNT traite.