|
Informationsvisualisierung |
|
VU Informationsvisualisierung SS 08 |
|
Einführung: |
|
Die Visualisierung immer größer werdender Daten spielt in der Informationsvisualisierung eine wichtige Rolle. Speziell wenn es um große hierarchische Datensätze geht, entsteht das Problem diese sinnvoll in einer platzlimitierten Ausgabe, wie z.B. dem Monitor, anzuordnen.
Der erste intuitive Ansatz wäre, diese Daten in einem Baum bzw Graphen darzustellen, der aber bei mehr als hundert Knoten entarten würde und das Resultat wäre unübersichtlich. Dieses Problem ergibt sich durch ineffiziente Anordnung der Daten.
Hierzu gäbe es 3 mögliche Ansätze das Problem zu lösen:
Erhöhung um eine weitere Dimension im Ausgaberaum (also von 2D auf 3D bzw durch hyperbolischen Raum)
Reduzierung der Information durch Zusammenfassen bzw Verstecken von Knoten
Effiziente Nutzung jedes zur Verfügungen gestellten Pixels
Der dritte Lösungsansatz wird durch die sogenannten Treemaps gewährleistet.
Treemaps:
Treemaps wurden von Johnson und Shneidermann im Jahre 1991 publiziert. Der Fokus liegt in der Visualisierung der Knotengröße. Dies wird dadurch gewährleistet, indem jeder Knoten durch ein Rechteck repräsentiert wird. Kinderknoten werden durch horziontale bzw vertikale Aufteilung (alternierend) innerhalb dieses Rechtecks dargestellt. Die Proportionen der Kinder- und Elternknoten zueinander ergeben sich durch die Aufteilung implizit. Dieser Algorithmus wird nun rekursiv solange ausgeführt bis man einen Blattknoten erreicht hat.
Durch die Ausnutzung des gesamten Ausgaberaums ist die hierarchische Struktur implizit gegeben. Das große Manko von Treemaps ist, dass die hierachische Strukutr schwerer zu unterscheiden ist als bei den herkömmlichen Bäumen (siehe Abbildung 1). Der sinnvollste Ansatz, um dieses Problem zu umgehen, sind das Verschachteln und die Beleuchtung der Knoten (bzw Balken). Eine bessere Lösung bieten da die Beamtrees.
Abbildung 1: Treemap(links) vs Baum(rechts)
Beamtrees:
Beamtrees basieren auf den Treemaps, wobei hier noch zusätzlich eine dritte Dimension für die Tiefe herangezogen wird. Im Gegensatz zu den Treemaps, dessen Blattknoten den gesamten Raum einnehmen, skalieren Beamtrees die Rechtecke proportional zu der Größe ihrer Elternknoten (siehe Abbildung 2). Dabei werden die Kinderknoten nicht nur skaliert, sondern auch so verschoben, dass die linke obere Ecke des Elternknoten ausgefüllt wird. Diese zwei Techniken alleine führen schon zu guten Ergebnissen, jedoch müssen noch weitere daraus resultierende Probleme behandelt werden.
Abbildung 2: skalierter Blattknoten(links), Skalierung proportional zu den Elternknoten(Mitte), Verschiebung in die linke obere Ecke(rechts)
Beschränkte Skalierung:
Durch das Skalieren und Verschieben der Rechtecke kann es nun passieren, dass zwei unterschiedliche Verzweigungen eines Baums im Beamtree aneinander grenzen (siehe Abbildung 3a). Dies erschwert die Wahrnehmung unterschiedlicher visueller Einheiten.
Abbildung 3: aneinander grenzende Rechtecke(a), Überlappungen bzw Isolation (b)
Deswegen werden nicht nur die Blattknoten sondern auch die internen Knoten skaliert. Jedoch müssen diese Skalierungen so begrenzt werden, dass es zu keinen Überlappungen oder Isolation der Rechtecke kommt (siehe Abbildung 3b). Dies geschieht durch folgende Überlegungen:
Berechnung der Skalierungsbeschränkungen erfolgt durch Bottom-up Travesierung beginnend mit dem tiefsten internen Knoten. Es gibt nun 3 Unterscheidungsfälle:
1. N hat nur Blattknoten als Kinder: Führt zu keiner Berechnung
2. N hat nur interne Knoten als Kinder: Einführung zusätzlicher Linien an Anfang bzw. Ende des Knoten N, um ersten bzw. letzten Kinderknoten zu markieren
3. N hat Blatt- und interne Knoten als Kinder:
Für den letzten Kinderknoten wird ebenfalls eine zusätzliche Linie x3 wie in Fall 2 zur Markierung verwendet.
Für die Blattknoten von N muss ein bestimmter Platz reserviert werden, um Überlappungen zu verhindern. Dies geschieht durch Anpassung der Linie x2 an der umliegenden punktierten Boundingbox.
Die Linie x1 lässt sich durch Kenntnis über die absolute Größe aller Blattknoten und aller Kinderknoten errechnen.
Visualisierung:
Man kann nun durch zusätzliche Effekte wie Schattierung einen dreidimensionalen Eindruck erzeugen. Zusätzlich gewinnt man Kenntnis über die Aufteilungsrichtung, dh entweder horizontal oder vertikal.
Durch Projektion von Schatten und Lichtabschwächung kann auch die Tiefe visualisiert werden.
|
|
Implementierung: |
|
Unsere Applikation wurde in C++ (Visual Studio 2005) und OpenGL programmiert. Wir haben die Qt v4.3.2 Library für unsere GUI verwendet.
Implementierung basiert auf folgendem Paper:
"Beamtrees : Compact Visualization of Large Hierarchies" von Frank van Ham and Jarke J. van Wijk |