--- title: "Arbres quaternaires et compression" date: "2022-03-30" patat: eval: tai: command: fish fragment: false replace: true ccc: command: fish fragment: false replace: true images: backend: auto --- # Le cours précédent ## Questions * Qu'est-ce qu'un arbre quaternaire? . . . * Un arbre où chaque noeud a soit **4 enfants** soit **aucun**. * A quoi peut servir un arbre quaternaire? . . . * Compression # Les arbres quaternaires ## Définition Arbre dont chaque nœud a 4 enfants ou aucun.  # Les arbres quaternaires ## Cas d'utilisation Typiquement utilisés pour représenter des données bidimensionnelles. Son équivalent tri-dimensionnel est l'octree (chaque nœud a 8 enfants ou aucun). ## Cas d'utilisation: images * Stockage: compression. * Transformations: symétries, rotations, etc. ## Cas d'utilisation: simulation * Indexation spatiale. * Détection de collisions. * Simulation de galaxies, Barnes-Hut. # Exemple de compression ::: columns :::: {.column width=30%} ## Comment représenter l'image  :::: :::: {.column width=70%} ## Sous la forme d'un arbre quaternaire (5min, matrix)? . . .  **Économie?** . . . Image 64 pixels, arbre 25 noeuds. :::: ::: # Structure de données ::: columns :::: {.column width=50%} ## Pseudocode? . . . ```python struct node info node sup_gauche, sup_droit, inf_gauche, inf_droit ```  :::: :::: {.column width=50%} ## En C? . . . ```C struct _node { int info; struct _node *sup_left; struct _node *sup_right; struct _node *inf_left; struct _node *inf_right; }; ``` * Pourquoi le `*` est important? . . . * Type récursif => taille inconnue à la compilation. :::: ::: # Une fonctionnalité simple \footnotesize ## La fonction `est_feuille(noeud)` * Problème avec cette implémentation? ```pyrhon bool est_feuille(noeud) retourne est_vide(sup_gauche(noeud)) && est_vide(sup_droit(noeud)) && est_vide(inf_gauche(noeud)) && est_vide(inf_droit(noeud)) ``` . . . * Inutile d'avoir 4 conditions (soit 4 enfants soit aucun!) * Facile d'en oublier un! * Comment changer la structure pour que ça soit moins terrible? . . . ```python struct node info node enfant[4] ``` # Structure de données ## En C? . . . ```C typedef struct _node { int info; struct _node *child[4]; } node; ``` ## Fonction `is_leaf(node *tree)`? . . . ```C bool is_leaf(node *tree) { return (NULL == tree->child[0]); // only first matters } ``` # Problème à résoudre * Construire un arbre quaternaire à partir d'une image: * Créer l'arbre (allouer la mémoire pour tous les nœuds), * Le remplir avec les valeurs des pixels. * Compression de l'image: * Si les pixels sont les mêmes dans le quadrant on supprime le sous-arbre (sans perte) * Si les pixels dévient pas trop on supprime le quadrant (avec perte) # Fonctions utiles (1/N) ## Comment créer un arbre de profondeur `prof` (3min)? . . . ```python arbre creer_arbre(prof) n = nouveau_noeud() # alloue la mémoire si prof > 0 pour i = 0 à 3 n.enfant[i] = creer_arbre(prof-1) retourne n ``` ## En `C` (3 min, matrix)? . . . ```C node *qt_create(int depth) { node *n = calloc(1, sizeof(node)); if (depth > 0) { for (int i = 0; i < 4; ++i) { n->child[i] = qt_create(depth-1); } } return n; } ``` # Le nombre de noeuds? ## Comment implémenter la fonction (pseudo-code, 5min, matrix)? . . . ```C entier nombre_noeuds(arbre) si est_feuille(arbre) retourne 1 sinon somme = 1 pour i de 0 à 3 somme += nombre_noeuds(arbre.enfant[i]) retourne somme ``` # Le nombre de noeuds? ## Comment implémenter la fonction en C (3min, matrix)? . . . ```C int size(node *qt) { if (is_leaf(qt)) { return 1; } else { int sum = 1; for (int i = 0; i < 4; ++i) { sum += size(qt->child[i]); } return sum; } } ``` # La profondeur en C? ## Implémentation (5min, matrix) . . . \footnotesize ```C int max(int x, int y) { return (x >= y ? x : y); } int max_depth(int depths[4]) { int m = depths[0]; for (int i = 1; i < 4; ++i) { m = max(m, depths[i]); } return m; } int depth(node *qt) { int depths[] = {0, 0, 0, 0}; if (is_leaf(qt)) { return 0; } else { for (int i = 0; i < 4; ++i) { depths[i] = depth(qt->child[i]); } return 1 + max_depth(depths); } } ``` # Fonctions utiles (2/N) ## Comment remplir un arbre depuis une matrice? ``` SG=0 | SD=1 21 | 12 | 4 | 4 9 | 7 | 4 | 4 ----------------- 1 | 1 | 0 | 31 1 | 1 | 3 | 27 IG=2 | ID=3 ``` ## Quel arbre cela représente? . . .  # Fonctions utiles (3/N) * On veut transformer une ligne/colonne en feuille. * Comment? ::: columns :::: {.column width=40%} ## Soit `ligne=2`, `colonne=3` ``` SG=0 | SD=1 21 | 12 | 4 | 4 9 | 7 | 4 | 4 ----------------- 1 | 1 | 0 | 31 1 | 1 | 3 | 27 IG=2 | ID=3 ``` :::: :::: {.column width=70%} ## Trouver un algorithme  * Quelle feuille? * Plus important: quel chemin? . . . * `co -> G/D`, `li -> S/I`, * `2 * (li / 2) + co / 2 -> 2 * 1 + 1 = 3` * `2 * ((li % 2) / 1) + (co % 2) / 1 -> 2 * 0 + 1 = 1` * Comment généraliser? :::: ::: # Fonctions utiles (4/N) ::: columns :::: {.column width=40%} ## Soit `ligne=2`, `colonne=3` ``` SG=0 | SD=1 21 | 12 | 4 | 4 9 | 7 | 4 | 4 ----------------- 1 | 1 | 0 | 31 1 | 1 | 3 | 27 IG=2 | ID=3 ``` :::: :::: {.column width=70%} ## Trouver un algorithme (prendre plusieurs exemples, 15min, matrix)  * Comment généraliser? . . . ```C noeud position(li, co, arbre) d = profondeur(arbre); tant_que (d > 1) index = 2 * ((li % 2^d) / 2^(d-1)) + (col % 2^d) / 2^(d-1) arbre = arbre.enfant[index] d -= 1 retourn arbre ``` :::: ::: # Fonctions utiles (4/N) \footnotesize ## Pseudocode ```C noeud position(li, co, arbre) d = profondeur(arbre); tant_que (d > 1) index = 2 * ((li % 2^d) / 2^(d-1)) + (col % 2^d) / 2^(d-1) arbre = arbre.enfant[index] d -= 1 retourn arbre ``` ## Écrire le code `C` correspondant (5min, matrix) ```C ``` # Remplir l'arbre ## A partir d'une matrice (pseudo-code, 5min, matrix)? . . . ```C arbre matrice_à_arbre(matrice) arbre = creer_arbre(profondeur) pour li de 0 à nb_lignes(matrice) pour co de 0 à nb_colonnes(matrice) noeud = position(li, co, arbre) noeud.info = matrice[co][li] retourne arbre ``` . . . ## A partir d'une matrice (C, 5min, matrix)? . . . \footnotesize ```C node *matrix_to_qt(int nb_li, int nb_co, int matrix[nb_li][nb_co], int depth) node *qt = qt_create(depth); for (int li = 0; li < nd_li; ++li) { for (int co = 0; co < nd_co; ++co) { node *current = position(li, co, qt); current->info = matrix[li][co]; } } return qt; } ``` <!-- Deja fait plus haut # La profondeur? ## Comment implémenter la fonction profondeur? * Quelle signature? . . . ```C entier profondeur(arbre) ``` * Quel pseudo-code (3min, matrix)? . . . ```C entier profondeur(arbre) profondeurs = [0, 0, 0, 0]; si est_feuille(arbre) retourne 0 sinon pour i 0 à 3 profondeurs[i] = 1 + profondeur(arbre.enfant[i]) retourn max(p) ``` # La profondeur en C? ## Implémentation (5min, matrix) . . . ```C int max(int x, int y) { return (x >= y ? x : y); } int max_depth(int depths[4]) { int m = depths[0]; for (int i = 1; i < 4; ++i) { m = max(m, depths[i]); } return m; } int depth(node *qt) { int depths[] = {0, 0, 0, 0}; if (is_leaf(qt)) { return 0; } else { depths[i] = 1 + depth(qt->child[i]); return max_depth(depths); } } ``` --> # Remplir la matrice ## A partir de l'arbre (pseudo-code, 3min, matrix)? . . . ```C matrice arbre_à_matrice(arbre) pour li de 0 à nb_lignes(matrice) pour co de 0 à nb_colonnes(matrice) noeud = position(li, co, arbre) matrice[co][li] = noeud.info retourne arbre ``` . . . ## A partir de l'arbre (C, 3min, matrix)? . . . \footnotesize ```C void qt_to_matrix(node *qt, int nb_li, int nb_co, int matrix[nb_li][nb_co]) for (int li = 0; li < nd_li; ++li) { for (int co = 0; co < nd_co; ++co) { node *current = position(li, co, qt); matrix[li][co] = current->info; } } ``` # Transformations avec un arbre quaternaire ## A faire * Symétrie axiale (horizontale/verticale). * Rotation quart de cercle (gauche/droite). * Compression. # La symétrie verticale ## Que donne la symétrie verticale de ``` SG=0 | SD=1 21 | 12 | 4 | 4 9 | 7 | 4 | 4 ----------------- 1 | 1 | 0 | 31 1 | 1 | 3 | 27 IG=2 | ID=3 ``` . . . ``` SG=0 | SD=1 4 | 4 | 12 | 21 4 | 4 | 7 | 9 ------------------ 31 | 0 | 1 | 1 27 | 3 | 1 | 1 IG=2 | ID=3 ``` # La symétrie d'axe vertical ## Comment faire sur une matrice (3min, matrix)? . . . \footnotesize ```C matrice symétrie(matrice) pour i de 0 à nb_colonnes(matrice) / 2 pour j de 0 à nb_lignes(matrice) échanger(matrice[i][j], matrice[nb_colonnes(matrice)-1-i][j]) retourne matrice ``` # La symétrie d'axe vertical ## Comment faire sur un arbre? * Faire un dessin de l'arbre avant/après (5min, matrix) ``` SG=0 | SD=1 SG=0 | SD=1 21 | 12 | 4 | 4 4 | 4 | 12 | 21 9 | 7 | 4 | 4 4 | 4 | 7 | 9 ----------------- => ---------------- 1 | 1 | 0 | 31 31 | 0 | 1 | 1 1 | 1 | 3 | 27 27 | 3 | 1 | 1 IG=2 | ID=3 IG=2 | ID=3 ``` * Écrire le pseudo-code (3min, matrix) . . . \footnotesize ```C arbre symétrie(arbre) si !est_feuille(arbre) échanger(arbre.enfant[0], arbre.enfant[1]) échanger(arbre.enfant[2], arbre.enfant[3]) pour i de 0 à 3 symétrie(arbre.enfant[i]) retourne arbre ``` # La symétrie d'axe horizontal * Trivial de faire l'axe horizontal (exercice à la maison) # Rotation d'un quart de cercle ## Comment faire sur un arbre? * Faire un dessin de l'arbre avant/après (5min, matrix) ``` SG=0 | SD=1 SG=0 | SD=1 21 | 12 | 4 | 4 4 | 4 | 31 | 27 9 | 7 | 4 | 4 4 | 4 | 0 | 3 ----------------- => ----------------- 1 | 1 | 0 | 31 12 | 7 | 1 | 1 1 | 1 | 3 | 27 21 | 9 | 1 | 1 IG=2 | ID=3 IG=2 | ID=3 ``` * Écrire le pseudo-code (3min, matrix) . . . ```C rien rotation_gauche(arbre) si !est_feuille(arbre)) échange_cyclique_gauche(arbre.enfant) pour i de 0 à 3 rotation_gauche(arbre.enfant[i]) ``` # Rotation d'un quart de cercle \footnotesize ## Comment faire sur un arbre? ``` SG=0 | SD=1 SG=0 | SD=1 21 | 12 | 4 | 4 4 | 4 | 31 | 27 9 | 7 | 4 | 4 4 | 4 | 0 | 3 ----------------- => ----------------- 1 | 1 | 0 | 31 12 | 7 | 1 | 1 1 | 1 | 3 | 27 21 | 9 | 1 | 1 IG=2 | ID=3 IG=2 | ID=3 ``` * Écrire le vrai (5min, matrix) . . . ```C void rotate(node *qt) { if (!is_leaf(qt)) { node *tmp = qt->child[2]; qt->child[2] = qt->child[0]; qt->child[0] = qt->child[1]; qt->child[1] = qt->child[3]; qt->child[3] = tmp; for (int i=0;i < 4; i++) { rotate(qt->child[i]); } } } ```