3.1 Introduction

La présentation de l'état de l'art en synthèse d'images de paysages a été faite au chapitre 2. Dans ce chapitre, nous proposons une modélisation combinatoire d'un arbre séparant sa forme de son développement. Les travaux présentés dans ce chapitre et les techniques de rendu associées présentées au chapitre 7, ont été publiés dans [Ey86], [VE89a,b], [VJ90] et [AJ90a,b].

Dans le but d'obtenir un meilleur contrôle de la forme finale de l'arbre modélisé, nous insistons d'abord sur la nécessité de définir des paramètres numériques permettant une certaine caractérisation de cette forme, c'est à dire permettant par exemple d'évaluer numériquement des caractéristiques telles que le caractère épineux ou touffu ou encore effilé, bien charpenté ou broussailleux de l'arbre.

La forme de l'arbre est mesurée par l'introduction de la notion de matrice de ramification. Cette matrice est triangulaire stochastique, associée à chaque arbre ou structure ramifiée binaire. Elle dépend seulement de l'arbre topologique sous-jacent. Cette matrice est définie à partir des notions combinatoires d'ordre d'une branche et de biordre d'un nœud interne.

Ces notions apportent une extension de concepts introduits par les hydrogéologistes Horton [Ho45] et Strahler [St52]. L'utilisation de l'analyse d'Horton-Strahler pour la synthèse d'images d'arbres a été suggérée mais non développée dans [EF86]. Ici nous développons cette approche en introduisant le concept de matrice de ramification permettant de séparer la forme de l'arbre de son histoire, et en montrant que beaucoup d'aspects visuels liés à l'aspect de l'arbre combinatoire, sont présents dans la matrice associée. Récemment, cette notion a été utilisée pour l'étude physique de structures ramifiées fractales, Vannimenus, Viennot [Va87], [VV89].

Notre méthode consiste à choisir une matrice de ramification et ensuite à effectuer la génération aléatoire d'un arbre combinatoire binaire dont la matrice de ramification est identique (ou très proche) de la matrice choisie. Enfin, la géométrie est définie. L'idée principale est de contrôler l'épaisseur et la longueur des arêtes et des angles d'embranchement par des lois linéaires, polynomiales ou exponentielles des ordres et biordres.

La méthode est simple et rapide, tout en préservant une grande variété de formes possibles. Bien que ce modèle soit différent des modèles botaniques, un rendu réaliste peut être obtenu. Dans ce but, nous introduirons au chapitre 7 un algorithme rapide de dessin de feuilles. L'aspect réaliste est également développé dans [VE89a].

3.2.1 Arbre topologique, arbre géométrique et arbre botanique

Afin d’éviter toute confusion entre arbre botanique, topologique ou géométrique nous rappelons les quelques notions suivantes (voir par exemple Knuth [Kn73]).

Figures 3B et 3C : Arbre parfait et arbre très fin

Ces rapports donnent une information très partielle sur la forme de l’arbre binaire topologique: les arbres des figures 3B et 3C montrent des cas extrêmes. L’arbre parfait de profondeur 3 (chaque nœud terminal a la même profondeur) (Figure 3B) a tous ses segments réduits à des arêtes uniques : chaque rapport de bifurcation est égal à 2 (valeur minimale possible quelque soit l'arbre). Pour l’arbre très fin (Figure 3C), il n'y a qu'un seul segment d’ordre 2, et chaque arête terminale est un segment d’ordre 1. Le rapport de bifurcation d’ordre 2 est égal au nombre de nœuds terminaux, il n'est donc pas limité car l'arbre peut être de profondeur tendant vers l'infini.

Les géologistes ont établi que les rapports de bifurcation sont habituellement compris entre 3 et 5 dans la nature. Nous définissons un arbre binaire aléatoire comme étant un arbre binaire choisi aléatoirement avec équi-probabilité parmi les Cn = (2n)! / n! / (n+1)! arbres binaires à n nœuds internes. Il est connu que tous les rapports de bifurcation d'un arbre binaire aléatoire approchent 4 quand le nombre de nœuds devient grand (cf Meier et Moon [MM80]). Des études similaires ont été effectuées pour d'autres structures ramifiées, comme en botanique par MacMahon [Ma75] ou en anatomie par Woldenberg [Wo70] et neurophysiologie par Percheron [Pe82]. Prud'homme et Vigneaux [PV70] ont prouvé qu'il existe une certaine corrélation entre l'analyse de Horton-Strahler et la structure tectonique du sous-sol. Cette analyse a aussi été faite sur les réseaux de vallées des montagnes sous-marines (Naudin et Prud'homme [NP71]). Curieusement, le nombre de Strahler d'un arbre est aussi apparu en informatique pour évaluer le nombre minimum de registres nécessaires au calcul d'une expression arithmétique, (Flajolet, Raoult et Vuillemin [FR79], Kemp [Ke79]), et en biologie moléculaire pour l'étude de la "complexité" de la forme et pour le calcul de l'énergie des structures secondaires d'acides nucléiques (ARN) (Vauchaussade de Chaumont et Viennot [VV85]).

3.2.4.1 Biordre d’un nœud interne

Figure 3D : Biordres

- pour 1 = i = k, pk,i = bk,j / ak.

On ne peut donc prendre en compte que les lignes qui restent quasiment identiques quelle que soit la taille de l'arbre. Une conséquence importante est que des arbres de très grande taille (plusieurs dizaines de milliers de nœuds internes, voire plus) auront généralement à être analysés statistiquement pour obtenir une réponse fiable et précise sur un nombre important de lignes de la matrice limite extraite.

Table 3B : Matrice statistique extraite sur les arbres binaires aléatoires croissants de taille 10000 et de nombre de Strahler 10

Table 3C : Matrice statistique extraite sur les arbres binaires aléatoires croissants de taille 32000 et de nombre de Strahler 10

3.2.4.4.1 Arbre parfait

La matrice de ramification calculée pour les arbres binaires parfaits (arbres dont tous les nœuds terminaux sont de la même profondeur, Photographie 3A) est donnée à la table 3D. Toute arête d'ordre k doit se ramifier en deux arêtes d'ordres k-1. On a donc obligatoirement une diagonale composée uniquement de 1 et les coefficients de la partie inférieure de la matrice égaux à 0.

Table 3D : Matrice de ramification des arbres parfaits.

Photographie 3A : Arbre binaire parfait (taille égale à 511, nombre de Strahler égal à 10)

3.2.4.4.2 Arbre binaire aléatoire

On appelle arbre binaire aléatoire de taille n un arbre binaire de n nœuds internes tiré au hasard parmi les Cn = arbres existants de taille n [Re84] (Photographie 3B, planches 2A et 6C). La table 3E montre la matrice de ramification moyenne extraite à partir d'un grand nombre d'arbres binaires aléatoires de taille 10000 (2000 arbres). De toute évidence, cette matrice converge, quand la valeur n tend vers l'infini, vers la matrice donnée à la table 3F. Ce résultat a été prouvé mathématiquement par Penaud [Pe88].

Comme il a été précisé au paragraphe 3.2.4.3, les deux dernières lignes de la table 3E ne sont pas représentatives de la convergence vers une matrice limite. Toutefois les six premières lignes mettent bien en évidence l'évolution des lignes ce qui permet d'établir la table 3F, matrice limite pour les arbres binaires aléatoires.

Photographie 3B : Arbre binaire aléatoire (taille égale à 500, nombre de Strahler égal à 5)

Table 3E : Matrice statistique des arbres binaires aléatoires de taille 10000

Table 3F : Matrice limite des arbres binaires aléatoires

Un arbre binaire aléatoire croissant de taille n peut être généré au moyen de l'algorithme suivant :

Photographie 3C : Arbre binaire aléatoire croissant (taille égale à 500, nombre de Strahler égal à 7)

Table 3G' : Matrice limite des arbres binaires aléatoires croissants

Sur cette matrice on constate la présence de valeurs assez fortes sur la diagonale, tandis que les valeurs vont en décroissant depuis la diagonale en descendant les colonnes et en parcourant les lignes de droite à gauche.

3.2.4.4.4 Tries

Photographie 3D : Trie généré avec s = 12 et card(w) = 1000

Bs = {0,1}s étant l'ensemble des mots binaires de taille s, on associe à tout sous-ensemble w de Bs un arbre binaire noté Trie (w) selon l'algorithme :

- Si card(w) = 0, alors Trie(w) est l'arbre vide.

- Si card(w) = 1, alors Trie(w) est formé d'une unique feuille étiquetée w.

- Si card(w) = 2, alors Trie(w) est constitué d'une racine dont les sous-arbres gauche et droit sont respectivement les Tries associés aux sous-ensembles w0 et w1 de Bs-1 définis par : wi = {v Œ Bs-1 / iv Œ w}.

On contrôle la taille des Tries générés en jouant sur les deux paramètres numériques s et card(w) (= 2s), il n'est pas possible de fixer a priori cette taille. Plus card(w) est grand avec une valeur s fixe, plus la taille de l'arbre créé est grande (tableau 3H).

Tableau 3H : Taille moyenne d'un Trie en fonction de s et de card(w)

En effectuant un calcul de moyenne sur 2500 tries avec s = 13 et card(w) = 8000, on trouve la matrice de ramification de la table 3I. Il est à signaler que tous les arbres obtenus ont eu pour nombre de Strahler la valeur 12. Quels que soient s et card(w), la dispersion des nombres de Strahler est toujours très faible, ce qui se traduit bien dans la forme très équilibrée des arbres.

Table 3I : Matrice de ramification statistique des tries avec s = 13 et card(w) = 8000

Table 3J : Matrice de ramification statistique des tries avec s = 18 et card(w) = 500

On remarque que cette matrice est concentrée sur la diagonale et sa sous-diagonale, ce qui, du point de vue de la répartition des probabilités sur les lignes, la place entre la matrice des arbres parfaits et celle des arbres binaires aléatoires. La forme de la matrice varie en fonction des valeurs card(w) et s. Si s augmente avec une même valeur de card(w), ou si card(w) diminue avec une même valeur de s, les sous-diagonales suivantes (la 3ème et éventuellement la 4ème) peuvent adopter des valeurs qui ne seront pas toutes nulles (comparer les tables 3I et 3J). Même avec des valeurs de s très grande et de card(w) très petite, toutes les sous-diagonales à partir de la 5ème si elles existent sont nulles.

A partir d'un point de diffusion unique (la racine de l'arbre binaire topologique en construction) composé d'une seule particule, une nouvelle particule vient s'agglutiner à chaque étape de la génération de telle manière que celle-ci (la particule) ne touche en tout et pour tout qu'une seule autre particule (Photographie 3E). L'emplacement d'implantation est choisi au hasard parmi toutes les positions ayant une seule particule adjacente.

Photographie 3E : Représentation écran d’un arbre généré par le modèle d’Eden 2D.

Photographie 3F : Arbre de la photographie 3E dessiné avec notre modèle géométrique

- Pour obtenir un arbre binaire mathématique, l'adjonction d'une particule ne devra pas créer de nœud d'arité trois (une particule possède une autre particule dans toutes ses positions adjacentes).

Tableau 3K : Taille des arbres générés par modèle d'Eden 2D

Le calcul de la matrice de ramification moyenne pour un grand nombre d’arbres générés au moyen du modèle d'Eden en 2D (Photographie 3F) donne la matrice 3L (arbres de 10000 particules et donc de d'environ 2500 nœuds internes, 82% d'arbres de nombre de Strahler 7 et 18% de nombre de Strahler 8).

Table 3L : Matrice statistiques des arbres générés par modèle d'Eden 2D avec 10000 particules

La génération débute à partir d’un arbre T1 réduit à une seule arête (l’arête racine de l’arbre généré) étiquetée S. Une séquence Tn d’arbres binaires étiquetés va être construite. L’arbre Tn+1 de taille n+1 est obtenu à partir de l'arbre Tn en choisissant une arête terminale de Tn étiquetée k (k ? 1) et en créant sur cette arête deux arêtes filles étiquetées respectivement k et i (i < k) ou k-1 et k-1. Le choix (k,i) ou (k-1,k-1) est effectué par sélection aléatoire en accord avec la distribution des probabilités des biordres donnée sur la kième ligne de la matrice R. L’algorithme prend fin quand toutes les arêtes terminales sont étiquetées 1.

Figure 3E : Matrices de ramifications auto-similaires

Cet algorithme peut être implanté sous la forme de la fonction récursive GENERATION suivante qui rend un nœud correspondant à la racine de l'arbre généré (ST est le nombre de Strahler de l'arbre binaire à générer, MAT est la matrice de ramification devant guider la génération) :

Figure 3F : Variation de la taille d’un arbre de nombre de Strahler 7 généré à partir de la table 3G

Dans la pratique, le modèle géométrique nous donne (Figure 3G) :

Figure 3G : Epaisseur, longueur, 2 angles de branchement

- Pour chaque nœud interne n, deux angles qg(n) et qd(n), le premier en valeur positive, le second en valeur négative, définissant la déviation des arêtes filles gauche et droite associées à n par rapport à leur arête mère.

L’idée directrice de notre démarche est de faire dépendre les lois de longueur et d'épaisseur d'une arête uniquement de son ordre k, et les deux angles de déviation qg et qd relatifs à un nœud interne uniquement du biordre de ce nœud.

Pour ces quatre paramètres nous avons choisi des lois en correspondance avec les effets esthétiques que l’on est en droit d’attendre de l’image de l’arbre vis à vis de la réalité. Pour une étude plus précise voir Honda [Hon71], Leopold [Le71], Mendes-France [Me81], Stevens [St74],.... Pour les arbres, comme pour beaucoup d’autres structures ramifiées naturelles, l’épaisseur des arêtes décroît assez régulièrement de la racine aux nœuds terminaux. En général il en est de même pour la longueur des arêtes. Il est naturel de choisir les lois d’épaisseur et de longueur comme des fonctions croissantes E(k) et L(k) de l’ordre k de l’arête concernée.

        Loi quadratique                              Loi linéaire                                     Loi constante

Photographie 3G : Influence du type de lois de longueur sur l'aspect de l'arbre

                    Loi exponentielle                                         Loi constante

Photographies 3H : Influence du type de lois d'épaisseur sur l'aspect de l'arbre

E(k) = ce * ka ou E(k) = ce * ßk

avec cl1, cl2, cl3, ce, a et ß des constantes numériques.

Des lois présentant des effets esthétiques analogues à la nature ont été choisies pour les angles qg et qd. Ces lois vérifient la propriété suivante :

Dans notre modèle l’importance d’une branche est mesurée par son ordre. Plus il est grand, plus la branche est importante. Les lois suivantes ont donc été utilisées (Figure 3H ) :

Figure 3H : Angles qf,qp et qs

- Pour un embranchement de biordre (k-1, k-1) que nous appellerons fourche, les deux branches filles sont d’égale importance, leurs déviations sont égales en valeur absolue et qg = -qd = qf, qf est une constante réelle positive.

- Pour un nœud avec un biordre (k,i) i<k, les angles de déviation respectifs qp et qs de la branche principale et de la branche secondaire vis à vis de leur branche mère sont donnés par :

où cp et cs sont des constantes réelles positives. Dans le cas où la branche fille gauche est la branche principale du biordre alors qg = qp, sinon qg = qs. Si la branche fille droite est la branche principale alors qd = -qp, sinon qd = -qs.

De bons résultats visuels sont obtenus avec cs et qf égaux à 30° et cp égal à 10°. Bien sûr il est possible d’adopter toute autre paramètrisation en fonction de l’image voulue (Photographie 3I). Il est important de signaler que ces formules vérifient obligatoirement la propriété (1), toutefois pour certaines valeurs des coefficients cp et cs et du biordre (i,k) la déviation de la branche principale peut être plus importante que celle de l'autre branche (en valeur absolue). Si l'on veut obtenir une stricte observation de (1) et une déviation toujours moins importante pour la branche principale que pour la branche secondaire, on peut choisir :

qp(k,i) = ,          qs(k,i) = ,          qf =

Ces lois sont plus simples dans leur formulation, mais elles permettent des variations géométriques moins importantes. L'angle entre les deux branches filles d'un nœud interne est constant égal au coefficient c quel que soit le nœud considéré.

Photographie 3I : Influence des coefficients angulaires sur l'aspect de l'arbre

Le modèle de calcul des angles d'orientation dans le cas d'un modèle en deux dimensions est bien adapté à l'étude visuelle des propriétés caractéristiques d'arbres topologiques binaires. L'obtention d'un dessin réaliste est toutefois tributaire de la définition d'un modèle géométrique 3D. Un angle de phyllotaxie (angle de déviation en projection dans le plan orthogonal à l'axe de la branche mère) doit être défini à chaque embranchement pour l'orientation de chacune des branches filles. Il apparaît possible de modifier notre modèle 2D pour en conserver les principales caractéristiques géométriques (propriété (1)).

Figure 3I : Définition des angles d'orientation 3D

Par rapport au modèle 2D, la modélisation géométrique en 3D nécessite l'utilisation de deux angles au lieu d'un seul pour définir la déviation que subit une arête fille par rapport à son arête mère. Le modèle 3D comprend les formules de calcul permettant d'évaluer ces deux angles de déviation à chacun des embranchements.

- Les angles D1d et D1g des filles droite et gauche représenteront les angles de déviation par rapport à la mère dans le plan de la verticale. Plus précisément, pour la branche fille droite par exemple, si a1m (resp a1d) est l'angle de la mère (resp. fille droite) avec la verticale, alors D1d = a1d - a1m.

- Les angles D2d et D2g des filles droite et gauche donneront les angles de déviation en projection dans le plan xOy (Figure 3I).

Le calcul des épaisseurs et des longueurs des branches s'effectuera d'une manière identique au modèle 2D. Les formules de calcul des deux angles de déviation ainsi que de l'épaisseur et de la grosseur d'une arête permettent de définir la position dans l'espace de n'importe quelle branche fille à partir de la position de sa branche mère.

3.4.3.1 Angle de déviation par rapport à la verticale

L'angle ?1 nous donne une déviation par rapport à la branche mère par rapport à la verticale. Intuitivement cette déviation suit les mêmes lois que celles adoptées pour les déviations des branches dans le modèle 2D, qui nous permettaient d'obtenir de bons résultats visuels. C'est à dire qu'une branche fille sera d'autant moins déviée qu'elle est importante. Les formules données pour les déviations du modèle 2D restent donc valables pour l'angle de déviation ?1 du modèle 3D. A partir de la branche racine verticale, on définit récursivement les déviations ?1 des branches filles vis à vis de leurs branches mères.

Les formules utilisées sont fonction des biordres (les indices p, s et f signifiant "principale", "secondaire" et "fourche", voir paragraphe 3.4.2):

ou bien, comme il a été signalé précédemment :

3.4.3.2 Angle de déviation en projection dans le plan xOy

En revanche, pour l'angle de déviation en projection sur le plan xOy, les lois de calcul du modèle 2D ne peuvent pas être appliquées directement. En effet quelques constatations simples les réfutent (on parle ici d'angles en projection dans le plan xOy):

- Il est possible de trouver dans un arbre botanique des branches filles droites et gauches adoptant des directions diamétralement opposées comme il est possible de trouver des branches filles droites et gauches suivant des directions quasiment identiques (Figure 3J).

- L'importance respective des branches filles ne nous apporte pas toujours d'informations pertinentes sur leurs déviations respectives.

Un paramètre important pour le calcul de l'angle de déviation en projection sur le plan xOy d'une branche fille apparaît être l'angle a1m par rapport à la verticale adoptée par sa branche mère. En effet, plus la branche mère est verticale plus l'orientation des branches filles dans le plan xOy semble être prise au hasard (Figure 3J). Il est relativement logique de penser que si une branche mère est quasiment verticale (son angle dans le plan xOy n'a alors guère d'influence sur son orientation globale dans l'espace), il sera difficile de calculer l'angle de déviation ?2 pour une de ses branches filles. On en prendra pour exemple toutes les espèces d'arbres qui possèdent un axe de croissance vertical (croissance apicale orthotropique) (sapin, épicéa, peuplier, ...), où sur la branche principale quasi verticale (le tronc) viennent se fixer toutes les autres qui partent dans toutes les directions (la répartition de toutes ces branches est globalement équilibrée pour que l'arbre ne tombe pas sur le coté). En revanche, si la branche mère est quasi-horizontale les branches filles suivent la direction initiée par la branche mère dans le plan xOy (Figure 3J). On considérera alors que, dans ce cas là, la déviation suit le même type de lois que celles du modèle géométrique 2D.

Figure 3J: angles de déviations dans le plan xOy.

Incertitude (a1m) = * RAND()

où RAND() est une fonction qui rend un entier positif pris au hasard entre 0 et 359.

                                  Géométrie 2D                                                       Géométrie 3D

Photographie 3J : Une même structure topologique avec les modèles géométriques 2D et 3D

Photographie 3K : Un arbre sous différents points de vue

3.5.1 Préliminaires

La matrice de ramification est liée à l’arbre topologique sous-jacent à un arbre géométrique binaire. La "forme" de cet arbre topologique est manifestement un concept purement abstrait, l’étude des relations entre les matrices de ramification et la forme de l’arbre ne pouvant être effectuée qu’à partir d'une représentation géométrique. Cependant quelle que soit la géométrie ajoutée sur les arbres des figures 3B et 3C, celui de gauche restera toujours bien équilibré et celui de droite aura toujours l'aspect d'une liane. Il semble donc possible de parler de "forme" de l'arbre topologique, indépendamment de toute géométrie. A cette fin, les images présentées dans la suite seront toutes réalisées avec les mêmes paramètres géométriques, en géométrie 2D avec rendu 3D. En se détachant ainsi au maximum de l'influence de la géométrie, on pourra mettre en évidence plus facilement les relations entre matrice de ramification et forme de l'arbre topologique.

3.5.2 Exemples caractéristiques

Deux matrices typiques conduisant à des résultats visuels manifestement très différents sont celles données aux tables 3M et 3N, c’est à dire les matrices de ramification des arbres binaires aléatoires et binaires aléatoires croissants.

Table 3M : Matrice limite des arbres binaires aléatoires

Table 3N : Matrice limite des arbres binaires aléatoires croissants

Dans le premier cas (Table 3M), nous obtenons des arbres assez aérés avec une forme élancée, chevelue où l'on note la présence de quelques longs segments sur lesquels beaucoup d’épines (nœuds de biordre (k,1)) sont implantées (dans la réalité ces épines sont trop petites pour être bien vues sur la photographie 3L). Ces arbres ressemblent beaucoup à des lierres ou aux essences que l'on peut rencontrer dans les sous-bois et qui sont caractérisées par le fait qu'elles poussent tout droit vers le ciel sans générer beaucoup de feuilles du fait du manque de soleil. Les épines et les petits rameaux respectivement associés aux biordres (k,1) et (k,2) concentrent 75% des probabilités d'apparition des biordres, ce qui est important. La caractéristique fondamentale de ce type d'arbres est donc l'apparition de très longs segments quels que soient leurs ordres, segments sur lesquels se greffent une multitude de petits arbres (d'ordres très petits) (Planche 1A).

La seconde matrice (Table 3N) donne naissance à une classe d’arbres qui contiennent beaucoup plus de branches importantes et qui sont beaucoup mieux équilibrés (Photographie 3L), ils ressemblent d'ailleurs beaucoup plus aux arbres tels qu'on se les représente intuitivement. Dans cette matrice 60 à 70% des probabilités des biordres sont concentrées sur les deux dernières valeurs de chaque ligne (diagonale et première sous-diagonale). L’aspect "bien équilibré" est dû aux fortes probabilités des biordres (k-1,k-1) donnant ainsi naissance à un grand nombre de fourches comparativement au nombre total de nœuds internes (sans toutefois arriver à un rapport égal à 1 qui donne un aspect totalement bien équilibré dans le cas des arbres binaires parfaits). Très peu d’épines ou de petits rameaux apparaissent sur les branches d’ordres élevés. Les segments sont relativement courts.

3.5.3 Influence des coefficients sur la diagonale

Les valeurs présentes sur la diagonale d'une matrice de ramification ont une influence directe sur la longueur moyenne des segments de l'arbre généré au moyen de cette matrice. En effet, ces coefficients représentent la probabilité, pour un nœud d'ordre k quelconque d'évoluer en deux nœuds d'ordres k-1, ce qui représente la probabilité qu'un segment se finisse à chaque fois qu'on avance d'un nœud en le parcourant. La longueur moyenne d'un segment d'ordre k sera donc obtenue en calculant (paragraphe 3.5.6). Plus les valeurs sur la diagonale sont petites, plus les segments créés seront longs, et plus l'arbre semblera élancé et tourmenté (s'éloignant de la forme caractéristique de l'arbre binaire parfait). Pour les arbres binaires aléatoires croissants, la longueur moyenne des segments tend vers une limite voisine de 2,78 pour les grands ordres, pourtant l'arbre reste encore assez bien équilibré (Photographies 3C et 3L, planches). En revanche pour la matrice des arbres binaires aléatoires, la longueur moyenne de ces segments d'ordre k est égale à 2^(k-1). Elle croit donc très vite quand k augmente. Ces arbres présentent des segments qui deviennent rapidement très longs, la forme générale de l'arbre est assez caractéristique (Photographies 3B et 3L, planches).

Contrainte par segment

La photographie 3M montre les différences pouvant apparaître entre un arbre subissant une contrainte par segment lors de sa création et un arbre n'en subissant pas, la matrice de ramification utilisée au cours de la génération étant identique pour les deux arbres. La matrice employée est celle donnée à la table 3O. Avec cette matrice la longueur moyenne des segments est égale à 8. On constate que l'arbre avec contrainte par segment est beaucoup plus régulier que l'arbre sans contrainte. On tiendra compte du fait que sur l'arbre gauche, chaque branche entre deux fourches est en fait un segment de longueur 8, les épines dues aux biordres (k,1) inférieures à la taille du pixel, n'apparaissant pas. Un autre exemple est présenté à la planche 1A.

3.5.4 Influence de la répartition des coefficients sur les lignes

La répartition en valeur des coefficients sur chacune des lignes influence aussi la forme de l'arbre généré (à valeurs identiques sur la diagonale bien entendu). Plus les probabilités situées immédiatement sous la diagonale sont grandes plus les branches s'implantant sur les segments auront un ordre important. Deux conséquences sont directement issues de cette constatation.

- Il est évident que plus un arbre a un nombre de Strahler important, plus sa taille sera statistiquement grande. Avec des sous-diagonales fortes, pour un même segment d'ordre k, les ordres des branches implantées seront donc grands (ordres k-1, k-2, ...), et les tailles de ces sous-arbres seront grandes. Donc plus les coefficients sous les diagonales seront grands, plus la taille des arbres générés sera grande.

On voit que l'arbre avec sous-diagonale forte est beaucoup plus touffu que l'autre. L'arbre de droite possède en fait 1283 nœuds internes tandis que celui de gauche n'en possède que 160.

3.5.5 Mélange de lignes de matrices différentes

3.5.6 Taille moyenne d'un arbre généré par une matrice de ramification

Un problème théorique intéressant consiste à évaluer a priori la taille moyenne d'un arbre généré par une matrice de ramification. Cette information peut être utilisée à titre indicatif avant le lancement de l'algorithme de génération.

Longueur moyenne d'un segment d'ordre j

1) que les n-1 premiers biordres générés à partir de l'origine de ce segment soient du type (j,i) avec i < j (ils sont générés avec la probabilité qj = 1 - Pj,j)

Le nombre moyen de segments d'ordre j est d'une part égal au nombre nj,j de biordres (j-1,j-1) (qui sont les biordres terminaux de ces segments) et est d'autre part égal à la somme des nombres d'apparition des biordres (k,i) tels que j = k ou j = i, biordres qui donnent naissance aux segments d'ordre j (On comptera double un biordre (j,j) donnant naissance à deux segments d'ordre j). On comptabilise ainsi le nombre de nœuds d'ordre j qui sont les premiers nœuds d'un segment d'ordre j. Les nombres recherchés sont donc nj+1,j+1 correspondant au biordre (j,j) (ce nombre est compté deux fois car le biordre contient deux j et donne naissance à deux segments d'ordre j), nj+1,j, nj+2,j, ..., nS,j (voir figure 3K).

La valeur nS,S n'est pas calculable par cette formule. Elle est égale à 1 car nS,S représente le nombre de segments d'ordre S.

Nombre total moyen de nœuds internes

nj,j dépend donc de nj+1,j+1, nj+2,j+2, ..., nS,S. Toutes ces valeurs doivent être connues avant le calcul de nj,j.

A titre indicatif, les arbres présentés dans les exemples de cette thèse possèdent des nombres de Strahler variant de 5 à 10 suivant le type de matrice de ramification, le nombre de nœuds obtenus varie de quelques centaines à quelques milliers.

Remarque

Si l'on a extrait la matrice de ramification d'un arbre donné quelconque, les formules précédentes donnent exactement (les calculs sont à résultats entiers) les nombres nj,i de nœuds internes de biordre (j,i) de l'arbre de départ. Il est donc possible de retrouver à partir de cette matrice de ramification la taille exacte de l'arbre pour lequel elle a été déterminée.

Par simple somme des nombres de biordres on retrouve le nombre de nœuds internes contenus dans l'arbre qui était 200.

3.6 Conclusion

La topologie est essentielle dans la méthode présentée qui autorise l'analyse d'une structure ramifiée indépendamment de son histoire. Ceci conduit aux matrices de ramification qui sont l' expression des caractéristiques principales de la forme d'une structure ramifiée. Comme nous l'avons vu, ces matrices permettent un fort contrôle de la forme finale et sont un outil pour la synthèse d'images de structures arborescentes présentant de telles caractéristiques. A partir d'une méthode de génération d'une classe d'arbres, il est possible d'extraire de façon simple la matrice de ramification représentant cette classe d'arbres. Cette association entre l'analyse de l'image et la synthèse d'image est l'un des points intéressants de cette méthode.

L'association d'une géométrie dépendant seulement des paramètres combinatoires ordre et biordre, avec un algorithme rapide de dessin de feuilles (cf chapitre 7 et annexe 1) est un bon compromis entre la vitesse et le rendu final, tout en conservant une grande diversité de formes possibles. Une telle méthode simple et rapide est d'un intérêt pratique pour l'implémentation d'un environnement interactif de génération et d'animation d'arbres dans des domaines variés (botanique, arts graphiques, architecture, …). On en donnera un exemple en synthèse d'images de paysages au chapitre 8 : Des milliers d'arbres synthétisés par les techniques décrites dans ce chapitre seront implantés dans un bassin montagneux de façon à générer des images réalistes de montagnes. L'efficacité de ces méthodes permet alors (cf chapitre 8 pour les détails) la création de plusieurs centaines d'images d'un tel bassin montagneux muni de milliers d'arbres pour la réalisation d'un survol animé du paysage (voir logiciel "Survol" en annexe d'animation sur Macintosh). Ce résultat est intéressant puisque réalisé sur un micro-ordinateur IBM PS/2 8580, cf chapitre 8 et annexe 1 pour les détails.

L'intérêt scientifique se rencontre alors dans l'analyse et la synthèse de structures ramifiées qui ne sont pas nécessairement botaniques, par exemple en physique (éclairs électriques, "digitation visqueuse", DLA, …) et en biologie moléculaire (structures secondaires d'ARN). En particulier, le modèle des matrices de ramification a été appliqué récemment en physique aux structures fractales ramifiées [Va87] [VV89].