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 nœud l’indication de sa profondeur dans l’arbre (champ depth).

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

2.1 difference et compare


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

On souhaite ajouter une méthode qui insère un point a dans un arbre tout en préservant la propriété définissant les arbres kd. Pour cela, on a besoin de savoir si on doit placer le point a dans le sous-arbre gauche ou dans le sous-arbre droit. Dans la classe KDTree, complétez les méthodes suivantes :

  • double difference(double[] a)) qui renvoie la différence entre les coordonnées des points a et this.point qui interviennent dans le choix (en utilisant le champ depth du nœud courant),

  • boolean compare(double[] a)) qui renvoie true si le point a doit être inséré dans le sous-arbre droit, et false s’il doit être inséré dans le sous-arbre gauche.

Testez votre code avec Test21.

2.2 insert

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

Dans la classe KDTree, complétez la méthode :

KDTree insert(KDTree tree, double[] a) qui ajoute à l’arbre tree un nœud contenant le point a et renvoie la racine de l’arbre obtenu. La méthode d’insertion doit préserver la propriété définissant les arbres kd. On s’autorise à insérer plusieurs copies d’un même points.

Vous pourrez prendre l’implémentation de BST.add 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 auxiliaire insert(tree, a, depth) pourra être utile.

Testez votre code avec Test22 et InteractiveClosest. La fenêtre produite par InteractiveClosest représente l’arbre 2-dimensionnel obtenu après avoir inséré successivement 50 points choisis uniformément dans [0,1]×[0,1]. Tapez '+' ou '-' pour avoir plus ou moins de points.

Déposez TD5.java.

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

Voici par exemple ce que l’on obtient avec 1016 points :

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 sqDist

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

Complétez la méthode :

double sqDist(double[] a, double[] b) qui calcule le carré de la distance entre deux points.

Testez votre code avec Test31.java.

3.2 closestNaive

L’algorithme naïf pour retrouver le point le plus proche consiste simplement à parcourir tous les points de l’arbre, tout en maintenant dans une variable champion le point le plus proche rencontré jusque-là.

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

}

Complétez les méthodes :

  • double[] closestNaive(KDTree tree,double[] a, double[] champion) qui recherche, par l’algorithme naïf, le point le plus proche de a dans l’ensemble constitué par les points de l’arbre tree et champion ;

  • double[] closestNaive(KDTree tree, double[] a) qui renvoie le point le plus proche du point a dans l’arbre tree ; si l’arbre est vide, on renvoie null.

Testez votre code avec Test32.

Déposez TD5.java.

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

3.3 closest optimisée

La complexité de la méthode closestNaive précédente est linéaire en la taille de l’arbre. On peut faire beaucoup mieux en utilisant la structure de l’arbre kd.

On observe que pour tout sous-arbre t à profondeur i dans notre arbre kd, les points dans le sous-arbre gauche de t sont séparés des points dans le sous-arbre droit de t par l’hyperplan de coupure défini par x[i%k] = t.point[i%k].

Pour chercher le plus proche voisin d’un point a dans t, on peut donc commencer par chercher le plus proche voisin p dans le sous-arbre de t situé du même côté de l’hyperplan de coupure que a. Si a est plus proche de p que de l’hyperplan de coupure, alors il est inutile d’explorer l’autre sous-arbre de t (situation 1). Sinon, on doit considérer également t.point et les points dans le sous-arbre droit de t (situation 2).

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

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

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

Complétez les méthodes :

  • double[] closest(KDTree tree, double[] a, double[] champion) qui recherche le point le plus proche point de a dans l’ensemble constitué par l’arbre tree et champion comme décrit ci-dessus ;

  • double[] closest(KDTree tree, double[] a) qui renvoie le point le plus proche point de a ; si l’arbre est vide, on renvoie null.

Testez votre code avec les classes Test33 et InteractiveClosest.

La classe InteractiveClosest vous permet de visualiser le déroulement de l’algorithme. 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.

Déposez TD5.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 optimisée

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, ce qui donne un point. 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.

L’objectif de cette partie est d’écrire la fonction palette qui renvoie un objet de type Vector<double[]> contenant un nombre prescrit de points à même d’approcher les points d’un arbre kd donné.

Photo témoin
Palette web
Palette optimisée

4.1 size et average

On commence par quelques fonctions auxiliaires.

class KDTree {
  ...
  static int size(KDTree tree) { ... }
  static void sum(KDTree tree, double [] acc) { ... }
  static double[] average(KDTree tree) { ... }
}

Complétez les méthodes suivantes :

  • int size(KDTree tree) qui renvoie le nombre de nœuds de l’arbre tree;
  • void sum(KDTree tree, double[] acc) qui calcule la somme des points de l’arbre tree et l’ajoute à acc.
  • double[] average(KDTree tree) qui renvoie le point isobarycentre (c’est-à-dire la valeur moyenne) des points de l’arbre, ou null pour un arbre vide.

Testez votre code avec Test41.

Déposez TD5.java.

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

4.2 palette

La palette est composée à partir d’un arbre 3d contenant les couleurs de 20000 pixels choisis aléatoirement dans l’image. Les 256 couleurs seront obtenues en calculant l’isobarycentre des points de sous-arbres bien choisis.

class KDTree {
  ...
  static Vector<double> palette(KDTree tree, int maxpoints) {...}
}

Complétez la méthode :

static Vector<double[]> palette(KDTree tree, int maxpoints) qui renvoie un tableau de maxpoints couleurs en s’appuyant sur tree (qui dans nos tests contient 20000 points). Plusieurs stratégies sont possibles.

Testez votre code avec la classe 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 d’environ 4,7. Partagez votre méthode si vous faites moins !

Il est normal de tâtonner. Commencez par une méthode naïve pour choisir maxpoints sous-arbres dont on prendra l’isobarycentre, puis raffinez. 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 tree dont on extrait une palette n’est pas forcément équilibré (c’est un arbre aléatoire).

Déposez TD5.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…