Vegetation is present all around us and we are accustomed to see trees and other plants everyday. Its accurate representation is thus an essential part of the realistic depiction of natural scenes in a virtual environment. Due to the complexity of both vegetation and its reaction to wind load, such representation are still being unresolved issues of research in computer graphics. In a first step to the development of suitable models of animated plants, it is thus essential to understand as much as possible all the phenomena which produce the observable motion of trees. This thesis is organized in two parts. The first is on the acquisition and the reproduction of the motion of real plants and contains three chapters. The second is on mechanical simulation of plants dynamics and is divided in two chapters. In the first part, chapter 2 describes experimental work I have done and participated to within the Chene-Roseau project and shows the obtained data on plants response to natural wind load and manual excitation. We also discuss how features observable in a video can be automatically tracked along the sequence and presents some methods I have developed. These algorithms have been put in a software I developed that also focus on user interaction to compensate for the limitation of automatic techniques. An explanation is given in chapter 3 of how manual input can be used to extract reliable motion data from video. At the end of the first part, chapter 4 presents our results on structure extraction from 2D motion data (previously extracted from a video) and its retargeting. The statistical study of 2D motion data I have developed is discussed. We show how it can be used to extract a valid hierarchical branches structure that holds the plants motion and how it is used to reproduce the observed motion on a virtual model. In the second part, simulation method of tree response to wind load is discussed. In chapter 5, a state of the art of existing real-time animation technique is given. We introduce several concept of mechanics and simulation of elastic structure dynamics in order to compare all described methods. Finally chapter 6 presents the methods developed in collaboration with Mathieu Rodriguez on the real-time simulation of thousands of trees in response to interactive wind.

Présentation d'un langage formel pour la spécification des processus communicants. On propose 3 interprétations possibles (modèles) de ce langage: la présentation d'une variété d'algèbres, un système de transition de termes, un arbre (fini ou infini). Introduction d'un calcul pour la construction de réseaux de processus

Les travaux présentés dans cette thèse ont pour thème la transformation des documents structurés. Un document structuré est une collection d'éléments typés organisée par un ensemble de relations logiques définissant une structure hiérarchique. Ces relations sont définies par des grammaires hors-contexte qui décrivent des classes de documents. L'utilisation des documents structurés permet d'automatiser une partie des traitements effectués sur les documents et contribue également à améliorer leur portabilité en proposant une syntaxe commune définie par des normes (SGML, XML). Les applications utilisant cette représentation souffrent néanmoins de limites liées aux contraintes impliquées par la structuration des documents. L'objectif de ce travail est de répondre à ces limites par des techniques de transformation. Ces techniques ont pour but de modifier la structure d'un ensemble d'éléments typés pour le conformer à d'autres types ou à une nouvelle classe de documents. Cette thèse est articulée en trois parties : 1. Une étude des applications de traitement de documents identifiant les besoins de transformation, plus particulièrement dans le domaine de l'édition interactive. 2. Une évaluation des techniques et outils existant conduisant à une classific- ation des approches (filtres, transformation explicite ou automatique). Chaque classe fait l'objet d'une étude théorique, d'une étude des systèmes disponibles et d'une expérimentation. 3. Une proposition de méthode de transformation combinant les différentes techniques pour tirer parti de leurs points forts et répondre aux limitations de chacune. Cette méthode est fondée sur un algorithme de transformation automatique paramétré à l'aide de pré-couples explicites. Ce travail a conduit au développement des systèmes de transformation aujourd'h- ui intégrés dans des logiciels du projet Opéra (Thot, Byzance) et du consortiu- m W3C (Amaya).

Tempêtes et ouragans causent des dégâts considérables dans les forêts de plantation du globe, entraînant ainsi des pertes économiques sévères. La question de la tenue aérodynamique du système aérien de l'arbre est centrale pour déterminer les risques de ruine lors de tels événements. Un modèle de dynamique non-linéaire des structures basé sur la Méthode des Eléments Finis a été développé afin d'évaluer le comportement mécanique de l'arbre soumis à l'écoulement atmosphérique, de nature turbulente en milieu forestier. L'analyse numérique est nécessaire pour appréhender toute la variabilité et la complexité de l'architecture aérienne des arbres. Les oscillations libres de trois jeunes Pins maritimes (Pinus Pinaster Ait.) sont caracterisées experimentalement et par des simulations numériques. L'influence de la morphologie des sujets est prise en compte. En outre, le modèle est appliqué à un Epicéa de Sitka (Picea Sitchensis) sous forçage aérodynamique. Enfin, la méthode des plans d'expérience est employée pour identifier les facteurs clés affectant la stabilité d'un Pin maritime soumis à un vent simulé. Les paramètres étudiés sont les caractéristiques géométriques et matérielles de la structure. Les résultats mettent en évidence l'aptitude du modèle à prédire les caractéristiques dynamiques d'arbres réels. Ils confirment de plus l'incidence de l'architecture aérienne sur les mouvements de l'arbre induits par le vent.

Nous etudions la perte de masse par formation de poussiere dans certains processus de fragmentation. Nous caracterisons en fonction du taux de fragmentation l'existence de poussiere et decrivons les comportements asymptotiques de sa masse. Puis, lorsque la fragmentation est auto-similaire d'indice negatif, nous analysons la regularite de la formation de poussiere et decrivons la genealogie de la fragmentation a l'aide d'un arbre continu aleatoire au sens d'Aldous. Nous calculons alors la dimension de Hausdorff de cet arbre, ainsi que le coefficient de Holder maximal de sa fonction de hauteur. Nous nous interessons ensuite a des processus de fragmentation avec une immigration Poissonnienne. Nous etudions en particulier l'existence et la nature d'un etat d'equilibre pour de tels systemes. Des etudes analogues sont entreprises pour des modeles deterministes de fragmentation.

Dans cette thèse, nous étudions le routage multicast tout optique (AOMR) dans les réseaux WDM. Notre objectif est de trouver un ensemble de structures de diffusion, par exemple un arbre optique ou une forêt optique, pour distribuer des messages multicast vers toutes les destinations en même temps, soit en tenant compte du délai de bout en bout et du stress des liens soit en minimisant le coût total ou le budget en puissance. En ce qui concerne l'AOMR qui tient compte à la fois du délai et du stress des liens, un algorithme efficace évitant les nœuds de branchement ne pouvant pas dupliquer la lumière dans des arbres optiques est proposé. Cet algorithme améliore le délai de bout en bout sur les arbres optiques et trouve un bon compromis entre le délai, le stress des liens et le coût total. En ce qui concerne l'AOMR qui considère la puissance, un nouveau modèle plus précis et plus réaliste de la perte de puissance est introduit lors de la mise en œuvre d'une session multicast. Il distingue deux types de perte de puissance : la partie ponctionnée par les nœuds optiques intermédiaires pour un éventuel monitorage et la partie ponctionnée par les destinations pour la récupération des messages multicast. Basé sur ce nouveau modèle, nous proposons un calcule des arbres optiques optimisant la puissance de l'émetteur réalisé à partir d'une programmation linéaire mixte en nombres d'entiers (MILP). Pour y parvenir, un ensemble d'équations linéaires est introduit pour remplacer les équations non-linéaires induites par les coupleurs optiques. Pour analyser les algorithmes heuristiques de l'AOMR et évaluer leurs performances, nous proposons une analyse mathématique des résultats. Dans notre analyse, nous établis- sons les bornes de coût des routes et les ratios d'approximation des algorithmes dans les réseaux maillés WDM pondérés et non-pondérés. Pour le routage multicast optique de coût minimal, une nouvelle structure appelée hiérarchie optique est proposée. Il est prouvé que la structure optimale n'est pas toujours un arbre optique, mais une hiérarchie optique. Le calcul de la hiérarchie optique est modélisé sous forme d'une ILP. Ce calcul exact permet d'obtenir la solution optimale pour les petites instances. Dans les réseaux WDM à grande échelle, une heuristique efficace utilisant une stratégie de renouvellement du graphe est proposée. Les résultats de simulation justifient l'emploi de la hiérarchie optique pour l'AOMR dans les réseaux WDM avec une capacité clairsemée de duplication.

L'analyse et la comparaison intelligentes d'images sont parmi les sujets suscitant le plus d'intérêt dans les milieux académiques autant qu'industriels. Décrire et comparer automatiquement les images est en effet un enjeu critique pour le plein développement de la «société de l'information». Les moteurs de recherche fonctionnant sur le texte ont prouvé leur utilité de façon éclatante mais à l'heure actuelle il n'existe aucun système équivalent fonctionnant uniquement sur les images. Une explication possible est que nous ne disposons pas de langage permettant de décrire les images et que les comparaisons pertinentes sont ainsi beaucoup plus difficiles que dans le cas du texte. Cependant, le cas du texte nous montre qu'il n'est pas nécessaire que les machines comprennent ce qu'elles analysent pour renvoyer des résultats pertinents. Des méthodes simples d'analyse syntaxique associées à des règles de composition suffisent à piloter des moteurs de recherche d'une grande efficacité. Pour permettre à des machines de simuler l'interprétation des images, il faudrait donc créer des descripteurs faisant office de mots et des règles pour les regrouper, ce qui permettrait de comparer des scènes comme on compare des phrases. On dispose d'ores et déjà de nombreuses méthodes pour détecter automatiquement de petits objets et des régions dans des images, par leur couleur commune, leur mouvement identique, etc. Poursuivant l'analogie, on pourrait comparer ces petits objets à des syllabes. La difficulté consiste à les grouper en mots, puis en phrases et comparer celles-ci, tout en étant robuste face aux perturbations. Pour ce faire, nous utilisons des graphes pour stocker ces objets et leurs relations. Ces relations peuvent être de voisinage ou d'inclusion, ce qui conduit les graphes à être respectivement des graphes plans ou des arbres. Nous verrons ainsi plusieurs méthodes permettant de construire l'un ou l'autre type de représentation, ainsi que leurs avantages et inconvénients. Dans une première étape, nous avons utilisé les algorithmes d'appariement de graphes développés par Cristina Gomila à la fin de sa thèse au CMM (1998-2001). Profitant du projet européen MASCOT étudiant l'utilisation de «métadonnées» pour faciliter le codage vidéo, nous avons étudié en détail les forces et faiblesses de cette approche. Nous avons d'abord testé le remplacement de l'algorithme au coeur de l'appariement de graphes. Nous avons obtenu une légère amélioration de la stabilité et également de meilleurs temps de calcul. Puis nous avons cherché à améliorer notre robustesse face aux variations de segmentation en utilisant une projection dans le domaine spectral. Malgré de bons résultats sur des images simples, nos essais sur des images plus difficiles n'ont pas été couronnés de succès. Pour pallier cette fragilité dès que les graphes ne sont plus similaires, nous avons préféré revenir à notre matériau source, les images. La seconde étape de ce travail a porté sur le développement de techniques basées sur l'image pour réduire la sensibilité de nos algorithmes de segmentation au bruit et aux petites variations. Pour ce faire, nous avons développé une classe d'opérateurs de filtrage adaptatifs, les «amibes morphologiques », extrêmement efficaces pour réduire le bruit dans les images. Par ailleurs, nous avons également développé un opérateur de gradient couleur robuste permettant de mieux détecter les contours dans les images bruitées. Ces deux opérateurs ont amélioré de façon parfois impressionnante la stabilité de nos modélisations, puis de nos graphes et donc des résultats globaux. L'étape suivante dans ce travail a porté sur le développement de modélisations d'objets indépendamment du reste de l'image. La motivation derrière cette approche est de considérer que, dans certains scénarios, le contenu de l'image, hors de certains objets bien définis, n'est pas informatif. Il faut donc analyser directement et de la façon la plus précise possible les objets eux-mêmes. Nous avons dans un premier temps supposé que les segmentations des objets étaient connues, afin de nous concentrer sur le calcul d'une signature robuste de chaque objet. Pour l'obtenir, nous avons modifié un algorithme de ligne de partage des eaux pour effectuer une resegmentation «top-down» d'un espace d'échelle morphologique basé sur des nivellements. Ceci a donné lieu à une nouvelle modélisation robuste utilisant des arbres de régions imbriquées. Nous avons également développé une distance entre ces arbres et nous l'avons testée sur une base d'images classique dans le domaine de l'indexation. La dernière étape est centrée sur l'aspect applicatif. En premier lieu en comparant les différentes approches présentées dans ce travail, notamment aux niveaux de leur robustesse et de leur vitesse d'exécution. Enfin, nous avons cherché la meilleure combinaison de techniques pour concevoir une application de vidéosurveillance. En particulier, nous avons développé des techniques rapides et robustes de segmentation dans le cadre du projet PS26-27 «Environnement Intelligent» en collaboration avec ST Microelectronics et le groupe ORION de l'INRIA. Ce projet visait à construire un démonstrateur de technologies de vidéosurveillance appliquées à la détection d'accidents dans les cadres domestique et hospitalier. Notre part du travail consistait à la mise au point d'algorithmes de détection de silhouettes en mouvement dans des séquences vidéo. Ainsi, en couplant ces techniques à nos descripteurs d'objets par arbres, nous avons pu définir des signatures robustes de personnes, qui pourront être utilisées avec un grande efficacité dans des systèmes automatisés de vidéosurveillance.

Les aires de répartition des arbres pourraient être grandement affectées par le changement climatique. Les résultats d'analyses paléogéographiques ont montré que ces dernières se sont déjà déplacées avec les variations passées du climat. Ces études ont permis de déterminer la direction et la vitesse de migration des espèces, données utilisées actuellement pour générer des prédictions sur l'évolution de l'aire de répartition des espèces forestières en réponse au réchauffement du climat. Cependant, le contexte écologique dans lequel les arbres font face à ces changements est très différent par rapport aux changements climatiques passés : l'augmentation actuelle des températures est plus rapide, les surfaces susceptibles d'être colonisées sont occupées par des écosystèmes très différents et variés (forêts, surfaces agricoles, zones urbaines). Par conséquent, les arbres pourront-ils faire face à la rapidité des changements globaux actuels ? Auront-ils la capacité de migrer pour trouver des conditions plus favorables ou pourront-ils s'adapter et survivre à de nouvelles conditions environnementales ? Dans un premier temps, l'analyse de données historiques (plans d'aménagements de l'Office Nationale des Forêts et Inventaires Forestiers Espagnols) a permis de mettre en évidence des évènements de colonisation et d'extirpation et de quantifier la vitesse de migration de populations situées au cœur ou aux marges de leur aire de répartition. Une colonisation massive de Quercus ilex dans les dunes boisées atlantiques (limite Nord d'aire de répartition) a été mise en évidence au cours des 130 dernières années, confirmant les tendances prédites par les modèles. Cependant, les vitesses de colonisation de cette espèce restent bien inférieures aux déplacements de son bioclimat estimés à partir de modèles de niche. Les espèces localisées en limite Sud d'aire de répartition présentent des remontées altitudinales plus importantes que pour celles situées au cœur de leur aire. En conclusion, nos résultats montrent que les changements globaux ont déjà impactés la répartition des arbres malgré l'existence d'un décalage temporel entre les réponses migratoires des espèces forestières et le déplacement de leur bioclimat. Le stress hydrique est le facteur prépondérant pouvant expliquer le dépérissement des arbres dans un milieu dont la disponibilité en eau est limitée, notamment en marge chaude d'aire de répartition. Nous avons, par conséquent, étudié la résistance à la sécheresse et ses mécanismes chez les plusieurs espèces d'Angiospermes. Nos résultats montrent qu'un seuil de 90% d'embolie mène à des dommages physiologiques irréversibles de la plante et à la mort par déshydratation. Ce seuil est considérablement plus élevé que celui précédemment observé chez les conifères. L'étude du fonctionnement hydraulique d'espèces de chênes co-occurrentes nous a permis de montrer que la survie de Q. robur pourrait être menacée dans les forêts atlantiques dans un contexte de sécheresses de plus en plus intenses car il y subit des taux d'embolie native élevés. Au contraire, Q. ilex présente des taux d'embolie négligeables sur ce même site d'étude.Les vitesses réelles de migrations constituent des données empiriques essentielles qui nous renseignent sur les capacités migratoires effectives des arbres. Elles pourront être intégrées dans les modèles de répartition, tout comme les seuils d'embolie induisant la mort des arbres.

Le tracé de rayons est désormais un algorithme classique pour la visualisation en synthèse d'images. Nous nous sommes cependant efforcés de ne pas le considérer comme un simple algorithme de visualisation mais comme un algorithme plus général de simulation de transfert d'énergie au sein d'un environnement géométrique. Ce choix a conduit à la définition d'un modèle géométrique indépendant du modèle de rendu qui lui est associé. Ce modèle utilise une méthode par arbre de construction (CSG) avec deux améliorations essentielles: l'utilisation d'un graphe au lieu d'un arbre ainsi que la possibilité d'associer des propriétés à n'importe quel objet du modèle. L'algorithme de calcul d'intersection entre un rayon et un objet est spécialement adapte à ce modèle, et il utilise une technique d'accélération nouvelle, basée sur l'utilisation d'englobant appelés boites englobantes généralisées, palliant certains inconvénients des techniques classiques. L'algorithme de rendu a été rendu générique, ce qui permet de changer facilement d'implémentation de l'algorithme de rendu. Les modèles classiques (Lambert et Phong) sont présentés en détail. Enfin, nous présentons trois applications de notre environnement: l'utilisation de nouveaux systèmes de perspectives, la visualisation de densités volumiques et de primitives de lumière, ainsi qu'une version parallèle de notre algorithme.

La détection de la peau constitue une phase primordiale de prétraitement dans plusieurs applications telles que la vidéo surveillance et le filtrage d'Internet. Toutefois, c'est une tâche difficile à accomplir étant donné la diversité des couleurs de la peau et la variété des conditions de prise de vue. Dans l'objectif de surmonter ces dernières contraintes, nos travaux de thèse consistent à définir un modèle robuste de la distribution de la peau capable de différencier les pixels de peau de ceux de non-peau dans des images variées. Notre modélisation est fondée sur le concept des modèles graphiques probabilistes connus par leur intuitivité et efficacité pour la représentation d'une distribution jointe de probabilités sur un ensemble de variables aléatoires, plus particulièrement les arbres indexant des probabilités. En vue de définir le modèle de l'arbre idéal indexant la distribution de la peau, nous avons proposé trois approches différentes : le modèle d'arbre de dépendances à b probabilité peau et non peau, le modèle de mélange des arbres et celui de leur combinaison. Le modèle d'arbre de dépendances à bi-probabilité peau et non peau proposé, exploite les propriétés d'interclasse et d'intra classe entre les deux classes peau et non peau ainsi que les interactions entre un pixel et ses voisins que nous traduisons par un arbre de dépendance optimal. L'arbre élaboré est un arbre idéal unique indexant conjointement les distributions de probabilités peau et non peau. Le modèle de mélange des arbres est proposé pour remédier à la multiplicité des arbres de dépendances optimaux possibles sur un graphe. L'entité du mélange proposée concerne aussi bien les structures des arbres considérés que les probabilités portées par ces dernières. Ainsi, l'arbre idéal indexant probabilité peau est l'arbre résultant du mélange portant la probabilité du mélange. Quant au modèle de combinaison des arbres élaboré, il constitue une approche alternative au mélange proposé visant l'exploitation des différent informations emmagasinées dans les différents arbres de dépendances optimaux possibles. Un fondement théorique est présenté dans cette thèse pour déterminer la meilleure approche à adopter, le mélange des arbres ou la combinaison des arbres, et ce en fonction des arbres de dépendances optimaL considérés. Les expérimentations réalisées sur la base Compaq montrent l'efficacité et la faisabilité de nos approches. En outre, des études comparatives entre n< modèles de peau et l'existant prouvent qu'en termes de qualité et de quantité des résultats obtenus, les modèles proposés permettent de discriminer les pixels de peau et ceux de non peau dans des images couleurs variées.