Arbres k-dimensionnels

INF411 · TD5

 Login :  Mot de passe :

Exprimez-vous

1 Introduction

Ce sujet aborde les arbres k-dimensionnels, ou arbres kd. Cette structure de données permet de trouver, parmi un ensemble de points de k, le plus proche voisin d’un autre point.

Un arbre k-dimensionnel est un arbre binaire dont les nœuds contiennent chacun un point de k tel que pour tout point p = (p0, …, pk − 1) stocké dans un nœud n à profondeur i, et tout point q = (q0, …, qk − 1) stocké dans le sous-arbre gauche (resp. droit) issu de n, qi mod k < pi mod k (resp. qi mod k ≥ pi mod k), où i mod k désigne le reste de la division euclidienne de i par k.

C’est très similaire aux arbres binaires de recherche, à la différence que l’ordre utilisé pour trier les nœuds dépend de la profondeur. Cela permet de relier la proximité dans k à la proximité dans l’arbre.

Pour commencer:

2 Construction d’un arbre kd

class KDTree {
    int depth;
    double[] point;
    KDTree left;
    KDTree right;
   
    // Construit une feuille
    KDTree(double[] point, int depth) {
        this.point = point;
        this.depth = depth;
    }
}

De manière classique, on représente un arbre ou un sous-arbre par son nœud racine. Un nœud contient un point de k, de type double[], et des pointeurs vers les sous-arbres gauche et droit. On ajoute à chaque noeud l’indication de sa profondeur dans l’arbre (champ depth).

Comme dans le cours, l’arbre vide est représenté par null.

2.1 compare

class KDTree {
   ...
   double compare(double[] a) { ... }
}

Écrire une méthode compare qui renvoie un nombre négatif ( < 0) ou positif ( ≥ 0) selon que le point a doit être rangé dans le sous-arbre left ou right du nœud courant this.

2.2 insert

class KDTree {
   ...
   static KDTree insert(KDTree tree, double[] a) { ... }
}

Écrire une méthode insert(tree, a) qui ajoute à l’arbre tree un nœud contenant le point a et renvoie la racine du nouvel arbre. Bien sûr, la méthode doit préserver la propriété définissant les arbres kd.

Vous pourrez prendre l’implémentation de BST.insert vue en amphi 5 comme point de départ. Il faut bien suivre la profondeur tout au long de l’insertion ; c’est la différence principale avec l’insertion dans un arbre binaire de recherche. Une méthode auxilliaire insert(tree, a, depth) pourra être utile.

Testez votre code en lançant Test22 et InteractiveClosest. Appuyez sur n’importe quelle touche pour choisir de nouveaux points. Tapez '+' ou '-' pour avoir plus ou moins de points.

Deposer KDTree.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Image de référence avec 1016 points

3 Point le plus proche

On s’intéresse maintenant à la recherche du point d’un arbre kd qui est le plus proche d’un point a donné, au sens de la distance euclidienne.

3.1 dist

class KDTree {
   ...
   static double dist(double[] a, double[] b) { ... }
}

Écrire une méthode dist qui calcule le carré de la distance entre deux points.

Testez votre code avec Test31.java.

3.2 closest

class KDTree {
    ...
    static double[] closest(KDTree tree,
                            double[] a,
                            double[] champion) {
        if (tree == null)
            return champion;

        if (dist(a, champion) > dist(a, tree.point))
            champion = tree.point;
        champion = closest(tree.left, a, champion);
        return closest(tree.right, a, champion);
    }
    
    static double[] closest(KDTree tree, double[] a) {
        if (tree == null) return null;
        return closest(tree, a, tree.point);
    }

}

La méthode naïve pour retrouver le point le plus proche consiste simplement à parcourir tous les points de l’arbre, tout en maintenant une variable champion qui pointe vers le point le plus proche rencontré jusque-là. La complexité est linéaire en la taille de l’arbre. (Voir ci-contre.)

On peut faire beaucoup mieux : si la distance entre a et champion est plus petite que la distance entre a et l’hyperplan de coupure qui sépare les deux sous-arbres du nœud courant tree, alors il n’y a besoin d’explorer que le sous-arbre du côté de a. En effet, dans ce cas, tous les points de l’autre sous-arbre sont nécessairement plus éloignés de a que ne l’est champion. On notera que la distance à l’hyperplan de coupure est donnée (au signe près) par:

Par ailleurs, on prendra soin d’explorer d’abord le sous-arbre du côté où a se trouve, car c’est probablement là qu’est le point le plus proche. Le critère précédent n’en sera que plus efficace.

Situation 1 : après avoir trouvé le point le plus proche dans le sous-arbre où a se trouve, il n’y a pas besoin d’explorer l’autre sous-arbre.

Situation 1

Situation 2 : après avoir trouvé le point le plus proche dans le sous-arbre où a se trouve, on ne peut pas exclure la possibilié que le point le plus proche se trouve dans l’autre sous-arbre.

Situation 2

Réécrire la méthode closest(tree, a, champion) en réduisant (drastiquement) l’espace de recherche.

Testez votre code en lançant InteractiveClosest. Cliquez pour rechercher le point le plus proche du curseur. Maintenez appuyé pour actualiser en continu. En bleu s’affichent les nœuds parcourus, en orange les champions successifs. Si la ligne orange est très brisée (disons plus de 10 points), c’est qu’il y a un problème.

Deposer KDTree.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Image de référence avec 1016 points

4 Sélection d’une palette de couleur

void simplify(Picture pic, int maxpoints) {
    Random r = new Random();
    KDTree tree = null;
    for (int i = 0 ; i < 10000 ; i++) {
        int row = r.nextInt(pic.height())
        int col = r.nextInt(pic.width());
        double[] color = pic.getRGB(col, row);
        tree = KDTree.insert(tree, color);
    }

    tree = KDTree.cut(tree, maxpoints);

    for (int col = 0 ; col < pic.width() ; col++) {
        for (int row = 0 ; row < pic.height() ; row++) {
            double[] color = pic.getRGB(col, row);
            double[] ccol = KDTree.closest(tree, color);
            pic.setRGB(i, j, ccol);
        }
    }
}

Pour les applications courantes, les couleurs des images vues sur un écran sont codées avec 24 bits, 8 bits pour chacune des trois couleurs rouge, vert et bleu. Pour compresser une image, le format d’image GIF sélectionne 256 couleurs, parmi les 16777216 possibles, pour représenter au mieux l’image. La méthode consistant à fixer 256 couleurs indépendamment de l’image, comme la palette web, donne de très mauvais résultats. Il faut sélectionner une palette de couleurs adaptée à l’image.

Voici une méthode possible pour calculer une palette optimisée (le code est donné ci-contre) :

  1. insérer les coordonnées RGB de chaque pixel (ou un échantillon aléatoire) de l’image dans un arbre 3d ;
  2. simplifier cet arbre jusqu’à qu’il ne contienne plus que 256 points ;
  3. remplacer la couleur de chacun des pixels par son plus proche voisin dans l’arbre simplifié.

Vous écrirez la fonction cut qui simplifie l’arbre.

Photo témoin
Palette web
Palette optimisée

4.1 size et average

class KDTree {
    ...
    static int size(KDTree tree) { ... }
    static double[] average(KDTree tree) { ... }
}

Écrire la méthode size qui renvoie le nombre de nœuds de l’arbre tree et la méthode average qui renvoie l’isobarycentre des points de l’arbre, c’est-à-dire la valeur moyenne.

Deposer KDTree.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

4.2 cut

class KDTree {
    ...
    static KDTree cut(KDTree tree, int maxpoints) {
        ...
    }
}

Écrire une méthode cut(tree, maxpoints) qui parcourt l’arbre tree et élague certains sous-arbres de manière à ne conserver que maxpoints point au plus. Comme insert, cut renvoie le nouvel arbre. Élaguer un sous-arbre consiste à le remplacer par un nœud unique contenant la moyenne des points du sous-arbre. Plusieurs stratégies sont possibles.

Testez votre code en lançant ColorPalette. Un temps de calcul de plus d’une seconde ou un score supérieur à 10 indique un problème. L’auteur de ces lignes atteint un score généralement compris entre 4,8 et 5,1. Partagez votre méthode si vous faites moins !

Il est normal de tâtonner. Commencez par écrire une méthode qui élague naivement, puis raffinez-la progressivement. Au début, considérez maxpoints comme un ordre de grandeur plus qu’une contrainte stricte. Notez que dans notre application, l’arbre 3-dimensionnel à élaguer n’est pas équilibré, c’est un arbre aléatoire.

Deposer KDTree.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

4.3 Perspectives

Au-delà de la sélection de palette, les méthodes de diffusion d’erreur sont indispensables pour éviter les aplats inhérents aux méthodes remplaçant une couleur par son plus proche voisin dans une palette fixée. Mais c’est une autre histoire…


Nous vous proposons une solution. Bien sûr, ce n’est pas la seule.

L’affichage graphique utilise la librairie algs4 sous license GPLv3.