cours_21.md

title: "Arbres quaternaires, compression et Barnes-Hut"
date: "2022-04-06"
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

• Structure de données d'un arbre quaternaire?

. . .

typedef struct _node {
    int info;
    struct _node *child[4];
} node;

. . .

• Dessin d'un noeud d'arbre quaternaire (avec correspondance node)?

. . .

graph TD;
    id0(("    "))-->|"child[0]"| id1(("info"));
    id0-->|"child[1]"| id2(("info"));
    id0-->|"child[2]"| id3(("info"));
    id0-->|"child[3]"| id4(("info"));

Le cours précédent

Questions

• Comment faire la symétrie d'axe horizontal?

. . .

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

Compression sans perte (1/N)

Idée générale

• Regrouper les pixels par valeur

   SG=0  |  SD=1        SG=0   |  SD=1   
 21 | 12 | 4 |  4      21 | 12 |   4
  9 |  7 | 4 |  4       9 |  7 |  
-----------------  => ----------------- 
  1 |  1 | 0 | 31         1    |  0 | 31
  1 |  1 | 3 | 27              |  3 | 27
   IG=2  |  ID=3        IG=2   |  ID=3

• Comment faire?

Compression sans perte (2/N)

Que devient l'arbre suivant?

. . .

Arbre compressé

Compression sans perte (3/N)

• Si un noeud a tous ses enfants égaux:
  • Donner la valeur au noeud,
  • Supprimer les enfants.
• Remonter jusqu'à la racine.

Écrire le pseudo-code (5min, matrix)

rien compression_sans_perte(arbre)
    si !est_feuille(arbre)
        pour i de 0 à 3
            compression_sans_perte(arbre.enfant[i])
        si derniere_branche(arbre)
            valeur, toutes_égales = valeur_enfants(arbre)
            si toutes_egales
                arbre.info = valeur
                detruire_enfants(arbre)

Compression sans perte (4/N)

\footnotesize

Écrire le code C (5min, matrix)

. . .

void lossless_compression(node *qt) {
    if (!is_leaf(qt)) {
        for (int i = 0; i < CHILDREN; i++) {
            lossless_compression(qt->child[i]);
        }
        if (is_last_branch(qt)) {
            int val = -1;
            if (last_value(qt, &val)) {
                qt->info = val;
                for (int i = 0; i < 4; ++i) {  
                    free(qt->child[i]);
                    qt->child[i] = NULL;
                }
            }
        }
    }
}

Compression sans perte (5/N)

\footnotesize

bool is_last_branch(node *qt) {
    for (int i = 0; i < 4; ++i) {
        if (!is_leaf(qt)) {
            return false;
        }
    }
    return true;
}
bool last_value(node *qt, int *val) {
    int info = qt->child[0];
    for (int i = 1; i < 4; ++i) {
        if (info != qt->child[i]) {
            return false;
        }
    }
    *val = info;
    return true;
}

Compression avec perte (1/N)

Idée générale

• Regrouper les pixels par valeur sous certaines conditions

   SG=0  |  SD=1        SG=0   |  SD=1   
 21 | 12 | 4 |  3      21 | 12 |    4
  9 |  7 | 4 |  4       9 |  7 |  
-----------------  => ------------------
  1 |  1 | 0 | 31         1    |  0 | 31
  2 |  1 | 3 | 27              |  3 | 27
   IG=2  |  ID=3        IG=2   |  ID=3

• On enlève si l'écart à la moyenne est "petit"?

Compression avec perte (2/N)

Que devient l'arbre suivant si l'écart est petit?

. . .

Arbre compressé

Compression avec perte (3/N)

Comment mesurer l'écart à la moyenne?

. . .

• Avec l'écart-type

\begin{equation*} \mu = \frac{1}{4}\sum_{i=0}^{3} p[i],\quad \sigma = \sqrt{\frac{1}{N}\sum_{i=0}^3 (\mu-p[i]) ^2} \end{equation*}

Que devient l'algorithme?

. . .

• Si
  $\sigma<\theta$
  ,
  $\theta$
  est la tolérance:
  • Remplacer la valeur du pixel par la moyenne des enfants.
  • Remonter les valeurs dans l'arbre.

Quelle influence de la valeur de

\theta

sur la compression?

. . .

• Plus
  \theta
  est grand, plus l'image sera compressée.

Compression avec perte (4/N)

Que devient l'arbre avec

\theta=0.5

?

. . .