User Tools

Site Tools

Trace:
algo:start

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
algo:start [2021/05/16 09:53] – louisalgo:start [2021/06/22 22:18] (current) – antoine
Line 18: Line 18:
 {{:algo:triskele-array.png?nolink&}} {{:algo:triskele-array.png?nolink&}}
  
-{{:algo:triskele-array.svg?800|}} 
  
 ====== Présentation de l'Algorithmes de construction d’un arbre : ====== ====== Présentation de l'Algorithmes de construction d’un arbre : ======
Line 25: Line 24:
  
 ^Étape actuelle  ^Explication du fonctionnement de l'étape en détails  | ^Étape actuelle  ^Explication du fonctionnement de l'étape en détails  |
-|{{:algo:algo-tree-1.jpg?direct&600  |algo-tree-1.jpg}}  | \\ 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-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.jpg?nolink&600  |algo-tree-2.jpg}}  | \\  \\ 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, 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-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.jpg?nolink&600  |algo-tree-3.jpg}}  | \\  \\ 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-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.jpg?nolink&600  |algo-tree-4.jpg}}  | \\ Pour la suite de la construction de l'arbre, on sélectionne le couple de pixel suivant dans le tableau triés, 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. \\  \\ Dans tableau short-cut on peut relever les liaisons entre les pixels utilisé qui désigne le leader (en position 10) \\   | +|{{: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.jpg?nolink&600  |algo-tree-5.jpg}}  |   | +|{{: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.jpg?nolink&600  |algo-tree-6.jpg}}  |   | + 
-|{{:algo:algo-tree-7.jpg?nolink&600  |algo-tree-7.jpg}}  |   | +|{{: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-8.jpg?nolink&600  |algo-tree-8.jpg}}  |   | +|{{: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-9.jpg?nolink&600  |algo-tree-9.jpg}}  |   | +|{{:algo:algo-tree-8.png?nolink&600  |algo-tree-8.png}}  |Pour le cinquième couple,   | 
-|{{:algo:algo-tree-26.jpg?nolink&600  |algo-tree-26.jpg}}  |   | +|{{: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-27.jpg?nolink&600  |algo-tree-27.jpg}}  |   | +|{{:algo:algo-tree-26.png?nolink&600  |algo-tree-26.png}}  |   | 
-|{{:algo:algo-tree-28.jpg?nolink&600  |algo-tree-28.jpg}}  |   |+|{{: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}}  |   |
  
  
algo/start.1621158780.txt.gz · Last modified: 2021/05/16 09:53 by louis

Page Tools

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki