algo:start [triskele]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Algorithme ======

Le cœur de Triskele est un algorithme de construction d'arbre en complexité linéaire.

Pour maintenir une complexité linaire Triskele utilise le [[:algo:sort:start|tri comptage]]

La construction d'un arbre utilise l'algorithme dérivé d'[[:algo:build-tree:start|union-find]]

Schématiquement, tout les pixels font référence à un nœud et les nœuds font référence à un nœud (sauf la racine).

{{:algo:triskele-image.png?nolink&}}

Représentation sous la forme de tableaux

  * le tableau des parents (pixels et nœuds)
  * les tableau des attributs (nœuds)

{{:algo:triskele-array.png?nolink&}}


====== Présentation de l'Algorithmes de construction d’un arbre : ======

Nous allons expliquer le fonctionnement de l'Algorithmes de construction d’un arbre par un exemple, en détaillant les différentes étapes.

^Étape actuelle  ^Explication du fonctionnement de l'étape en détails  |
|{{:algo:algo-tree-1.png?direct&600  |algo-tree-1.png}}  | \\ Comme exemple, nous allons prendre un tableau (dans le côté gauche de l'image) de dimensions 4×4, chaque case correspond à la valeur numérique d’un pixel \\  \\ Le tableau **weights **contiendras les poids des couples de pixels, leur pondération \\  \\ Le tableau parents correspondras au liens entre chaque couple de pixels, les noeuds de l'arbre \\  \\ Le tableau child-count compteras le nombre d'enfant reliés à un noeud|
|{{:algo:algo-tree-2.png?nolink&600  |algo-tree-2.png}}  | \\  \\ Comme expliqué dans le résumé, l’algorithme va balayer de façon linéaire l’image afin de créer des couples de pixels pour chaque pixel présent dans l’image \\  \\ Donc l’algorithme crée des couples de pixels A et B, et leur attribut leurs pondération (ici appelé W) qui correspond à leurs poids, la valeur la plus grande entre les deux pixels, ce poids correspond à la valeur \\  \\ d'obscurité du couple de pixels. \\  \\ Un fois tout les couples crées, ils sont triés par leur pondération, par ordre croissant, ce tableau sera utilisé pour créer l'arbre,  |
|{{:algo:algo-tree-3.png?nolink&600  |algo-tree-3.png}}  | \\  \\ Nous passons maintenant à la création de l'arbre, de façon linéaire, à commencer par la création du premier parent, puis du premier noeud. \\  \\ Pour ce premier parent, on sélectionne le premier couple de pixels du tableau (ici représenté en rouge) en l'ajoutant dans le tableau parents \\  \\ Ce premier parent correspond naturellement au couple de pixels avec le poids le plus faible (tableau triés par ordre décroissant) \\  \\ Sa position a - b est en 6 - 7 \\  \\ Le tableau short-cut permet de désigner le leader lors des étapes pour gagner du temps d'exécution \\  \\ La valeur du tableau child-count de la premiere case correspond au nombre de couple de pixel enfant appartenant au parent (ici pour l'instant 2)  |
|{{:algo:algo-tree-4.png?nolink&600  |algo-tree-4.png}}  | \\  \\ Pour la suite de la construction de l'arbre, on sélectionne le couple de pixel suivant dans le tableau trié, ici de valeur de pondération 3 représenté en jaune. \\  \\ On rajoute une case parents dans le tableau parents. \\  \\ Comme un pixel du couple de pixel actuelle appartient aussi au couple de pixel précédent, on raccorde le couple avec le couple précédent en créant un noeud. \\  \\ On peut remarquer que dans la première case du tableau parents, on intègre une case jaune pour représenter la liaison du noeud entre les deux couples. \\  \\ Le noeud n'est plus jamais remis en question. On peut avancer dans la liste. \\  \\ Dans tableau short-cut on peut relever les liaisons entre les pixels utilisé qui désigne le leader (en position 10)  |
|{{:algo:algo-tree-5.png?nolink&600  |algo-tree-5.png}}  | \\ Pour le troisième couple, \\  \\ Comme un pixel du couple de pixel actuel appartient aussi au couple de pixel précédent (le pixel en position 7), on raccorde le couple avec le couple précédent en créant un noeud. \\  \\ On peut remarquer que dans le tableau parent, le parent vert a été relié au parent jaune \\  \\  \\  \\ Comme pour chaque parent créé : \\  \\ - On ajoute le poid du couple dans le tableau weights \\  \\ - On ajoute le nombre d'enfant raccordé au parent dans le tableau child-count \\  \\ - Le short-cut désigne le leader \\  \\ - A la position du leader on insère la valeur correspondant au placement du noeud dans l'arbre (2éme tableau)|

|{{:algo:algo-tree-6.png?nolink&600  |algo-tree-6.png}}  | \\  \\ Pour le quatrième couple, aucun des deux pixels n'a déjà été ajoutés à l'arbre, on ajoute donc le parent au tableau parents en créant un noeud sans le raccorder a un autre parent. \\  \\ On créé ici une autre branche. \\  \\   \\  \\ Comme pour chaque parent créé : \\  \\ - On ajoute le poid du couple dans le tableau weights \\  \\ - On ajoute le nombre d'enfant raccordé au parent dans le tableau child-count \\  \\ - Le short-cut désigne le leader \\  \\ - A la position du leader on insère la valeur correspondant au placement du noeud dans l'arbre (2éme tableau) \\   |
|{{:algo:algo-tree-7.png?nolink&600  |algo-tree-7.png}}  | \\ Pour le cinquiéme couple, un des pixels est déjà utilisé par le parent 3 (vert), on ne crée pas de parent car la branche actuelle n'est pas reliée à l'arbre, on ajoute simplement le pixel qui n'est \\  \\ pas déjà utilisé, au parent 3, on incrément donc la valeur child-count de 1 (voir 4eme case du tableau child-count) \\   |
|{{:algo:algo-tree-8.png?nolink&600  |algo-tree-8.png}}  |Pour le cinquième couple,   |
|{{:algo:algo-tree-9.png?nolink&600  |algo-tree-9.png}}  |L'arbre se construit au fur et à mesure de cette manière.  |
|{{:algo:algo-tree-26.png?nolink&600  |algo-tree-26.png}}  |   |
|{{:algo:algo-tree-27.png?nolink&600  |algo-tree-27.png}}  |Voici le rendu final de l'arbre après le traitement de tout le tableau. Cet exemple est très simple mais il permet de bien comprendre la création d'un arbre.   |
|{{:algo:algo-tree-28.png?nolink&600  |algo-tree-28.png}}  |   |
Sidebar

User Tools

Site Tools

Page Tools
