Rémi Fusade Visualisation dynamique d arbres hiérarchiques de très grande taille resultats

De Ensiwiki
Aller à : navigation, rechercher


Visualisation dynamique d'arbres hiérarchiques de très grande taille

Labo INRIA
Equipe ARTIS
Encadrants thomas.hurtut@gmail.com,thierry.stein@inrialpes.fr

Etudiant

Fusade, Rémi

Introduction

Le principe de ce TER était de trouver un moyen de représenter et de naviguer facilement dans des "grands" arbres hiérarchiques (plus de 50 000 nœuds). Cette problématique a été posée par Thomas Hurtut, qui avait besoin de ce type de représentation dans le cadre de ses travaux de recherche sur les cartes topographiques.
Il existe de nombreuses représentations de graphes et d'arbres hiérarchiques. Il existe également plusieurs logiciels permettant de naviguer dans ce type de structures. Néanmoins, la taille de l'ensemble des données finit toujours par poser problème: au niveau de la vitesse de navigation comme au niveau de la clarté de l'information.
Nous avons choisi d'utiliser le logiciel TULIP, qui est très complet dans ce domaine et qui est en plus modulable (il est prévu pour accueillir facilement d'éventuels plug-in). Pour résoudre le problème de la taille des arbres, nous avons choisi d'utiliser un procédé bien connu du domaine: la clusterisation de graphes (regrouper les noeuds semblables en "clusters").
Le travail effectué durant ce TER a donc été d'implémenter un plug-in pour TULIP permettant la clusterisation d'arbres. La problématique a été étendue à tout type d'arbre, et non plus seulement à ceux représentant des lignes de niveau.
Le plug-in obtenu à l'issu de ce TER rend la navigation dans les très grands graphes plus fluide, et parfois l'affichage plus clair (car plus léger).
Il se place comme un outil dans le domaine de l'étude d'arbres, et, s'il est développé, pourra sans doute servir à plusieurs problématiques de recherche d'informations dans ce type de données.

Éléments de pré-requis

La carte topographique d'une image

La problématique a été posée par Thomas Hurtut, qui utilise dans ses travaux de grands arbres hiérarchiques pour représenter des cartes topographiques.
Une carte topographique est l'ensemble des lignes de niveaux d'une image en niveau de gris. Chaque ligne de niveau est une séparation entre deux niveaux de gris.

Carte topographique simple.jpg
Une carte topographique simple et sa représentation sous forme d'arbre hiérarchique

La structure des lignes de niveaux est particulièrement bien adaptée à la représentation sous forme d'arbres hiérarchiques: chaque nœud représente une ligne de niveau, un nœud n1 est le "fils" d'un nœud n2 si la ligne de niveau de n1 est inclue dans la ligne de niveau de n2.
Dans cet exemple, les nœuds noirs représentent les lignes à contraste négatif (niveau de gris plus sombre à l'intérieur de la ligne), les nœuds blancs représentent les lignes à contraste positif (niveau de gris plus clair à l'intérieur).

La clusterisation

La clusterisation d'un arbre ou d'un graphe consiste à regrouper ensemble certains noeuds. Un groupe de noeuds est alors appelé un "cluster". Le but est de réduire l'information visible, et donc l'information à traiter, tout en conservant la structure générale du graphe. En général, il est possible de récupérer cette information facilement (par exemple, en réaffichant le contenu d'un cluster quand on zoome dessus).

Cluster.gif
Animation illustrant le principe de la clusterisation


Il existe plusieurs type de clusterisations, celle dont nous allons nous servir fonctionne ainsi:
- Il faut d'abord définir une distance (comprise entre 0 et 1) entre les nœuds
- Ensuite, on rassemble les nœuds dont la distance est inférieure à un seuil (lui aussi compris entre 0 et 1)

Présentation du logiciel TULIP

Il existe plusieurs logiciels d'affichage de graphes, l'un des plus aboutis est TULIP.
Le logiciel TULIP (http://tulip.labri.fr/) permet l'affichage et la navigation dans les très grands graphes. Il contient de nombreux algorithmes d'affichage, de tests, de coloration de graphes, etc... Il gère également la présence d'attributs sur les noeuds d'un graphes (attributs entiers, flottants, de couleur, etc...). De plus, il offre la possibilité d'y intégrer de nouvelles fonctionnalités à l'aide de plug-in (un manuel est disponible à l'attention des développeurs).
Toutefois, TULIP n'est pas parfaitement adapté pour la représentation de très grands graphes: leur traitement est couteux, et la navigation dans ce type de graphes n'est donc pas totalement fluide (du moins pas sur ma machine).

Travail réalisé

J'ai choisi durant ce TER d'implémenter d'un plug-in pour TULIP permettant la clusterisation d'arbres selon des paramètres choisis par l'utilisateur. La distance entre les nœuds prendra en compte certains attributs de ces nœuds. Le principe est de regrouper les nœuds dont les attributs sont proches.
Le but était de fournir un outil permettant une navigation plus fluide dans les très grands arbres, et qui puisse s'adapter aux différentes problématiques.

Calcul de la distance

La méthode de calcul de la distance dépend de la problématique. Dans le cadre des lignes de niveaux par exemple, il serait pertinent de rassembler les nœuds ayant un contraste positif ensemble, et les nœuds ayant un contraste négatif ensemble, car ces nœuds se succèdent souvent. Pour d'autres arbres, il doit être possible de définir une formule du calcul de la distance. Pour le moment, ce plug-in proposera simplement de choisir les attributs considérés et leur poids.
TULIP permet la gestion d'attributs booléens, entiers, flottants, de couleur, de taille, de position, et de chaine de caractère. Il faut donc définir une distance entre chacun de ces types d'attributs. Pour la plupart d'entre eux, on applique une simple différence (entier-entier, flottant-flottant, volume-volume), pour les attributs de position, on utilise une distance euclidienne, et pour les attributs de couleur, la différence des niveaux de gris.
Les distances sont toujours ramenées entre 0 et 1 à l'aide des valeurs maximum et minimum de l'attribut considéré dans le graphe.

Algo Distance clusterisationdegraphes.jpgAlgo Distance clusterisationdegraphes.gif
Algorithme du calcul de distance + animation expliquant l'algorithme sur un arbre contenant un attribut entier

Une fois la distance entre les nœuds connues, nous allons nous en servir pour calculer les clusterisations (il en existe une infinité puisque le seuil varie entre 0 et 1).

Calcul de la clusterisation

Il existe plusieurs algorithmes de clusterisation de graphes. Mais ici, étant donné qu'on se restreint à la clusterisation d'arbres, leur structure simple permet d'utiliser un algorithme simple (en O(N), N étant le nombre de nœuds).
L'idée est la suivante: en partant de la racine, on cherche tous les nœuds atteignables et à une distance inférieure au seuil. Une fois que tous les nœuds ont été trouvés, on les "clusterise" ensemble, c'est à dire que l'on ne conserve qu'un seul nœud pour les représenter. On réapplique ensuite l'algorithme sur les nœuds restants.

Algo Clusterisation clusterisationdegraphes.jpgAlgo Clusterisation clusterisationdegraphes.gif
Algorithme de clusterisation d'un arbre hiérarchique + animation expliquant l'algorithme sur le même arbre que précédemment, et pour un seuil de 0.15

Résultats obtenus

Le plug-in a été créé puis ajouté à TULIP, puis baptisé "Interactive Clustering" (il permet de modifier les attributs et le seuil de façon interactive grâce à des fenêtres Qt). Ce plug-in utilise plusieurs paramètres, parmis lesquels il y a:
- L'apparence des clusters
- Les attributs utilisés à l'initialisation
- Les seuils pour lesquels on pré calcule une clusterisation (pour le zoom)
Ces paramètres pourraient être laissés au choix de l'utilisateur. Par manque de temps, ils ont été définis arbitrairement, et ne sont modifiables que directement dans le code source.
Les seuls paramètres modifiables par l'utilisateur sont donc les attributs, leurs poids, et le seuil.

TulipCouleursp.jpg
Screenshot du plug-in Interactive Clustering, à gauche le graphe original, à droite le graphe clusterisé à l'aide du plug-in

Pour plus de détails, une vidéo de démonstration est disponible en bas de cette page.

Conclusion

Le plug-in réalisé à l'issu de ce TER permet effectivement de rendre la navigation dans les très grands graphes plus fluide (vidéo à la fin de cette page). Il permet également de rendre l'affichage plus clair en diminuant le nombre de noeuds, mais également de rajouter de l'information, en rassemblant les noeuds selon des attributs au départ invisibles.
En l'état, ce plug-in apporterait une aide pour les travaux de Thomas Hurtut sur les cartes topographiques. Mais il y a encore plusieurs améliorations qu'il faudrait apporter pour qu'il soit d'une réelle efficacité pour d'autres problématiques.
Voici quelques exemples d'améliorations possibles:
- Etendre l'algorithme à tout type de graphes
- Proposer différentes manières de représenter les clusters (pour le moment ce sont de simples sphères)
- Proposer un choix d'attributs pertinents automatiquement
Enfin, le programme fourni n'est pas garanti en terme de bugs ou fuites de mémoire. Il serait important d'effectuer ces corrections pour que le plug-in soit utilisable de façon sûre.

Références

Hurtut Thomas : "Analyse et recherche d'oeuvres d'art 2D selon le contenu pictural", Thèse de Doctorat, 2008. [1]
Munzner Tamara : "H3: laying out large directed graphs in 3D hyperbolic space" [2]
Herman Ivan, Guy Melançon, M. Scott Marshall : "Graph Visualization and Navigation in Information Visualization: A Survey" [3]
Michael Balzer, Oliver Deussen : "Level-of-Detail Visualization of Clustered Graph Layouts" [4]
Frank van Ham, Jarke J. van Wijk : "Interactive Viualization of Small World Graphs" [5]

Documents additionnels