Soutenance mémoire
La visualisation de graphes est un domaine de recherche très actif avec de nombreuses publications chaque année dans les conférences majeures du domaine de l’InfoVis, SciVis, Graph Drawing et du Visual Analytics [45][4]. Parmi l’ensemble des techniques de visualisation de graphes, il existe le sous-ensemble des simplifications de graphe. Les techniques d’agrégation que nous présentons dans ce papier font partie de ce sous-ensemble. Le bundling, que l’on peut traduire en français par « agrégation visuelle », permet la simplification visuelle de graphes en regroupant plusieurs liens en tronçons principaux qui se ramifient comme des rivières vers la source. Cette agrégation forme des zones plus denses au profit de zones plus clairsemées et diminue le rapport de surface encre/fond (ink ratio) introduit par Tufte [46]. Le bundling permet par exemple l’émergence d’informations dans un graphe à forte densité dont la visualisation sans traitement n’affiche qu’une forme compacte (figure 1). L’agrégation de tels graphes fait apparaître des structures visuelles auparavant occultées par la forte densité de ses liens. Aujourd’hui, plusieurs techniques de bundling existent, et le domaine est devenu plus mature grâce à de nombreux exemples d’applications. Cependant, aucun des travaux précédemment publiés n’ont, jusqu’à présent, essayé de structurer l’espace de design. Cet article est une version étendue du tutoriel sur la simplification visuelle de graphes [44]. Nous y présentons et structurons les différents algorithmes de bundling existants. Notre but est de clarifier les possibilités offertes par les outils de bundling existants et de discuter de leurs avantages et de leurs faiblesses. L’ensemble des techniques de bundling se fondant sur d’autres techniques d’infographie, nous expliquerons dans un premier temps, les différents concepts nécessaires à la compréhension des différents algorithmes de bundling. Puis nous décrirons de manière synthétique chaque algorithme dont nous résumons les caractéristiques dans un tableau récapitulatif (table 1). Ensuite, nous discuterons des possibilités offertes par ces techniques. Pour finir, nous ouvrirons cette discussion sur les futurs défis du bundling.
DEFINITIONS
Un graphe G est composé d’un ensemble de sommets S et d’une liste d’arrêtes A les connectant (G = {S, A}). Au cours de notre analyse, nous noterons N le nombre de nœuds d’un graphe et L le nombre de liens de ce dernier.
Spline
Une cerce (Spline) est une courbe lisse définie en mettant bout à bout plusieurs courbes lisses définies par des points de contrôles. Il s’agit d’une fonction polynomiale définie par morceaux Les techniques de bundling utilisent principalement les B-Splines [3] qui sont la généralisation des courbes de Bézier.
Clustering de Graphes
La fragmentation (Clustering) de graphes consiste à regrouper les nœuds et les liens d’un graphe selon des critères de compatibilité préalablement définis. Ces critères peuvent porter sur tout attribut d’un nœud ou d’un lien (poids, distance, direction, etc…). L’objectif de la fragmentation de graphes consiste à faire en sorte que la distance entre les différents sous-ensembles (Cluster) formés soit la plus grande possible.
Bump-Mapping
La topographie d’aspérité (Bump Mapping) introduite par Blinn [6] permet de modifier le rendu d’une surface. Elle ajoute du relief à une surface grâce à l’interaction de la lumière et d’une texture irrégulière. Il s’agit d’une ombre pixelaire permettant de rendre la surface bosselée en modifiant la normale de la surface sur laquelle le bumpmapping est appliqué.
Pipeline Graphique des Algorithmes de Bundling
Le bundling est une technique de visualisation graphique dont le pipeline graphique est variable d’une implémentation à l’autre. Néanmoins, nous proposons de généraliser ce pipeline afin de saisir le principe fondateur de tout algorithme de bundling. Ce pipeline, similaire à celui d’Infovis [17], introduit les deux notions suivantes :
Advection
Nous utiliserons la notion d’advection pour caractériser les algorithmes de bundling. Le terme d’advection désigne, dans notre cas, le transport d’une quantité de matière selon un champ vectoriel.
Structure de Contrôle
Le terme « structure de contrôle » désigne un guide servant à l’advection des liens du graphe agrégé. Il peut regrouper des règles d’agrégation selon un critère donné [21][36], un maillage [10][29] ou encore des cartes de densité [24][36].
Notre généralisation du pipeline graphique des algorithmes de bundling est montrée en figure 2 et comporte les étapes suivantes :
❖ la création d’une structure de contrôle,
❖ l’advection des liens du graphe,
❖ le lissage,
❖ l’amélioration du rendu graphique,
❖ la visualisation du graphe.
Les techniques de bundling se résument par la suite d’actions suivantes. L’analyse d’un jeu de données permet la construction d’une structure de contrôle qui définit les règles d’agrégation à appliquer sur le graphe. A partir de ces règles, l’advection des liens du graphe est réalisée. Ensuite, l’algorithme lisse les liens entre chaque nœud et améliore le rendu graphique. Enfin, le résultat agrégé est affiché. Selon la technique de bundling, il est possible d’itérer entre les différentes étapes (liens en pointillés de la figure 2). Nous proposons d’utiliser ce pipeline graphique comme cadre d’analyse de l’état de l’art.
ETAT DE L’ART
Dans cette partie, nous décrivons des techniques permettant le calcul de graphes agrégés. Ces techniques opèrent toutes une déformation des liens entre les nœuds d’un graphe. Dickerson et al. ont été les premiers à introduire le principe d’agrégation de liens dans un graphe pour en améliorer sa lisibilité. Ils utilisent un algorithme d’heuristique pour illustrer leur concept [11]. Plusieurs algorithmes ont été élaborés pour agglomérer les liens d’un graphe [38][49] ; Dwyer et al. ont utilisé des liens courbes avec un algorithme à base de force et d’anticroisement [12]. En règle générale, peu d’implémentations du bundling modifient la position des nœuds du graphe. On peut néanmoins citer Gansner et Koren qui ont été les premiers à changer la position des nœuds dans un graphe circulaire pour optimiser l’agrégation visuelle [13]. Plus récemment Bothorel et al. [7] ont appliqué la même technique pour optimiser la visualisation des résultats de l’algorithme « apriori » [1].
Techniques de Calcul des Structures de Contrôles
Parmi l’ensemble des techniques de bundling étudiées (visibles en figure 3), nous différencions deux types d’implémentations : les techniques dites géométriques et celles pixelaires. Cette dichotomie s’opère principalement sur l’implémentation de la structure de contrôle.
Techniques Géométriques
Ces techniques se basent sur les relations géométriques entre les nœuds du graphe.
HEB (Hierachical Edge Bundling) [22]. Cette technique se fonde sur l’analyse de données hiérarchiques. La structure hiérarchique à agréger permet de positionner des points de contrôles de B-Splines (chaque nœud est un point de contrôle). Ainsi, elle agrège visuellement les liensdu graphe. Il s’agit d’une technique simple à implémenter puisqu’il suffit d’assigner chaque nœud du graphe à une B-Spline (figure 5). Sa complexité de calcul dépend du nombre de liens présents dans le graphe (i.e. en O(L)). Les paramètres sont réduits à ceux des B-Splines .
FDEB (Force-Directed Edge Bundling) [21]. Très populaire, FDEB utilise la notion de compatibilité de liens pour déterminer leur pouvoir d’attraction mutuelle. Cette notion de compatibilité englobe un très grand nombre de paramètres comme par exemple la direction des liens. Très flexible et simple à implémenter, elle a le revers de disposer d’une complexité de l’ordre de O(L²) (des optimisations sont néanmoins possibles). Les paramètres de ce bundling sont définis par les fonctions de compatibilité.
GBEB (Geometry-Based Edge bundling) [10]. Cette technique utilise un maillage (méthode de fragmentation de graphe) selon la direction des liens du graphe. Ce maillage permet de définir la position des points de contrôle de B-Splines. Le calcul de ce maillage possède une complexité en O(L.log(L)) ainsi que de nombreux paramètres.
WR (Winding Road) [29]. Utilisant le même principe que GBEB, cet algorithme fonde le calcul du maillage sur un diagramme de Delaunay et Voronoï [48]. Il s’agit d’une implémentation GPU. La complexité de cette technique est similaire à celle de GBEB en O(L.log(L)). Elle possède les mêmes paramètres que GBEB.
Mingle [14]. Grâce à un prétraitement des données pour construire un graphe de proximité, le traitement des liens du graphe est parallélisé pour calculer rapidement les déplacements à opérer. L’ensemble des liens est ainsi agrégé pour former un ensemble de lignes brisées (Polyline). L’implémentation de l’algorithme est complexe avec de nombreux paramètres. Cette technique est sans doute une des plus rapides, mais visuellement ne produit pas la version la plus simplifiée (figure 3). Sa complexité est de l’ordre de O(L.log(L)).
Techniques Pixelaires
Ces techniques exploitent les capacités de parallélisation des GPU modernes afin d’améliorer les performances du bundling.
SBEB (Skeleton-Based Edge Bundling) [13]. SBEB utilise un squelette de graphe qui doit être auparavant fragmenté. Ce squelette attire les liens du graphe et densifie ainsi ce dernier autour de cette structure. La complexité de cet algorithme réside dans le calcul de ce squelette. Cette technique ne nécessite que deux paramètres : un taux d’attraction ainsi qu’un taux de lissage. Sa complexité est proche de O(L) sans prendre en compte le calcul du squelette.
KDEEB (Kernel Density Estimation Edge Bundling) [24]. KDEEB calcule une carte de densité à partir des nœuds et des liens du graphe pour définir une carte de gradient pour l’advection. Ainsi, les liens du graphe sont attirés dans les zones de fortes densités. Cette technique est sans doute la plus rapide puisque sa complexité est en O(L) et ne nécessite pas de post-traitement de données. Les paramètres utilisés sont la taille de la carte de densité, le taux d’attraction et le taux de lissage.
ADEB (Attribute Driven Edge Bundling) [36]. Similaire à KDEEB, cette technique se différencie par la réutilisation des critères de compatibilité introduit par FDEB. Ainsi, ADEB intègre les critères de compatibilité de liens (pour exemple la direction d’un lien ou encore l’horodatage d’une trajectoire) pour créer différentes carte de densité. Les paramètres utilisés sont ceux de KDEEB (taille de la carte, taux d’attraction et taux de lissage) auxquels s’ajoutent les critères de compatibilité. Sa complexité reste en O(L).
Advection des Liens du Graphe
L’advection des liens du graphe s’opère selon deux techniques distinctes.
La première technique, principalement liée aux techniques géométriques, obtient l’advection des nœuds grâce à des B-Spline dont les points de contrôles ont été calculés dans l’étape précédente du pipeline. C’est le cas pour HEB, GDEB et Mingle. La seconde technique réalise l’advection des liens du graphe par interpolation Eulérienne. Les liens du graphe sont échantillonnés (resampling) en lignes brisées. Ensuite, chaque point d’une ligne brisée (à l’exception de ses extrémités) est déplacé par interpolation linéaire à partir d’un vecteur de déplacement défini par la structure de contrôle. Cette technique est utilisée par FDEB, SBEB, KDEEB et ADEB. Enfin, WR utilise une technique comparable à l’interpolation d’Euler. Chaque lien est échantillonné en ligne brisée à partir d’une implémentation de l’algorithme de Dijkstra. Les liens sont redéfinis comme le plus court chemin entre deux nœuds.
|
Table des matières
I)INTRODUCTION
II) GENERALITES
III) METHODOLOGIE
IV) RESULTATS
V) COMMENTAIRES ET DISCUSSION
VI) CONCLUSION
VII) REFERENCES
ANNEXES
RESUME
