La beauté mathématique et algorithmique des arbres
ou
de l'hydrogéologie à la synthèse d'images, en passant par les mathématiques, la physique des fractals, l'informatique théorique et la biologie moléculaire.
Ce résumé est tiré d'une présentation de ces travaux à: SIGGRAPH '89 (Boston, USA), PIXIM '89 (Paris), IMAGINA '90 (Monte-Carlo) et EUROGRAPHICS'90 (Montreau).
Ces arbres photographiés n'ont jamais existé ailleurs que sur un écran d'ordinateur. Ces images ont été synthétisées par un procédé identique pour tous. Pour chaque arbre, nous nous sommes donné un certain tableau d'une vingtaine de nombres. Le programme ou algorithme générant ces arbres, feuilles ou paysages fait tout le reste. L'algorithme de génération nécessite de profondes théories mathématiques relatives aux formes des arbres.
Aujourd'hui, les ordinateurs sont capables d'acquérir, grâce à une caméra des images. Ils peuvent les transformer et les restituer sur un écran. Mieux encore les ordinateurs peuvent en créer de nouvelles; c'est ce que les informaticiens appellent la "synthèse d'images". Bien sûr, pour qu'un ordinateur puisse créer une image, il faut, comme pour toutes les autres de ses fonctions, qu'un programmeur ait écrit auparavant en détail les différentes opérations permettant d'accomplir ce travail. Les algorithmes pour créer des formes élémentaires comme les polygones, cercles, sphères, cubes et autres surfaces ou volumes géométriques, sont relativement simples. Bien plus complexes sont ceux permettant de créer des formes de la nature comme des nuages, montagnes, arbres et paysages.
Un algorithme est donc nécessaire pour pouvoir, à partir d'un petit nombre de paramètres, reconstituer la totalité de l'image d'un être vivant (en l'occurence un arbre). Les arbres visualisés sur ces photos ont plusieurs milliers de branches et de branchements. Chaque branche a une largeur et une longueur (en supposant pour simplifier que chaque brache est dessinée par un rectangle). A chaque branchement, il faut définir deux angles. Ainsi le dessin de chaque arbre nécessite la donnée de plusieurs dizaines de milliers de nombres. Il faut aussi rajouter le dessin des milliers de feuilles. Et pourtant, l'utilisateur aimerait générer des arbres en ne donnant qu'une dizaine ou vingtaine de nombres au programme. La difficulté est d'arriver à construire un tel algorithme, demandant très peu de paramètres de la part de l'utilisateur, tout en produisant une très grande variété de formes et d'arbres. Des théories mathématiques sophistiquées sont nécessaires. C'est là un des intérêts scientifiques de la synthèse d'images.
Tout arbre de la nature, ou plus généralement toute structure ramifiée comme un éclair, un poumon animal ou un bassin fluvial, contient de façon sous-jacente un arbre abstrait, ou arbre mathématique: on a oublié la géométrie exacte de la structure et retenu uniquement l'"arrangement" des divers branchements. Ces arbres abstraits font partie des mathématiques combinatoires (appelées aussi mathématiques discrètes). Notre algorithme relève de méthodes provenant de ces mathématiques combinatoires.
Il est surprenant de constater que des hydrogéologues ont déjà introduit certaines méthodes combinatoires pour l'analyse et l'étude de la forme des bassins fluviaux. Ces travaux ont été intitialisés par Horton et Strahler. Les théories combinatoires à la base de notre algorithme de génération de synthèes d'images d'arbres constitue une extension aux arbres abstraits de l'analyse de Horton-Strahler. A chaque arbre botanique, structure ramifiée de la nature, ainsi qu'aux arbres mathématiques, nous associons un tableau de nombres, que nous appelons matrice de ramification.
Il est tout à fait remarquable que ce tableau de nombres, ridiculement petit par rapport au nombre de paramètres nécessaires à définir un dessin d'arbre, contienne des informations numériques essentielles pour apprécier l'aspect visuel de l'arbre: arbre touffu, effilé, bien équilibré, épineux, broussailleux, etc ... L'algorithme fait pousser l'arbre tout en étant guidé par ce tableau de nombres. En quelque sorte ce tableau joue un peu le rôle de l'ADN de nos molécules. Une part de hasard est gardé dans la génération. Avec exactement les mêmes paramètres d'entrées, l'algorithme produira des millions d'arbres différents. Ces arbres auront entre eux des ressemblances, ils seront de la même espèce, un peu comme les espèces naturelles: sapin, chêne, bouleau, etc ... En faisant varier les paramètres d'entrées, on obtiendra une grande variété de formes et espèces différentes. En somme, sur l'ordinateur comme dans la nature, la richesse, la variété et la beauté proviennent d'un judicieux mélange des lois et du hasard.
Il y a beaucoup d'autres surprises derrière ces images d'arbres synthétisés. D'une part, les paramètres combinatoires relatifs à l'analyse de Horton-Strahler et aux matrices de ramification, ont de très belles propriétés mathématiques. De profonds théorèmes d'arithmétique apparaissent dans ces théories. Ces paramètres sont réapparus dans des travaux en Informatique Théorique: problème d'optimisation relatif au nombre minimum de "registres" pour calculer une expression arithmétique. De manière encore plus inattendue, ils sont réapparaus dans des travaux de Biologie Moléculaire sur l'étude des structures secondaires d'acides nucléiques monobrins (ARN, ARN de transfert, ARN messager, ...): prédiction des structures secondaires et étude des homologies entre structures secondaires. Très récemment, certains d'entre nous ont introduits ces méthodes combinatoires dans l'analyse des structures ramifiées en Physique des fractals: digitation visqueuse, modèle DLA, ...
Ainsi, ces photos d'arbres symbolisent la beauté abstraite des théories mathématiques et la nécessaire pluridisciplinarité de la science en mouvement. Mathématiques, Physique, Botanique, Informatique, Biologie moléculaire, Hydrogéologie sont réunis dans ces photos. Bibliographie
Le sujet de cette conférence fera l'objet d'un cours qui occupera six séances du vendredi matin de la Petite Ecole de Combinatoire (qui fait aussi partie des activités de l'école doctorale):