Feature tracking for space-filling structures

Schnorr, Andrea; Garth, Christoph; Kuhlen, Torsten

doi:HT020872849

Feature tracking for space-filling structures = Feature Tracking für raumfüllende Strukturen

Schnorr, Andrea^RWTH*

2021

Verantwortlichkeitsangabevorgelegt von Andrea Schnorr, M.Sc.

ImpressumAachen : RWTH Aachen University 2021

Umfang1 Online-Ressource : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2021

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Kuhlen, Torsten (Thesis advisor)^RWTH* ; Garth, Christoph (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2021-02-19

Online
DOI: 10.18154/RWTH-2021-02122
URL: https://publications.rwth-aachen.de/record/814232/files/814232.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
dissipation elements (frei) ; feature tracking (frei) ; flow visualization (frei) ; graph optimization (frei) ; space-filling structures (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Eine Möglichkeit, die massiven Datenmengen, die aus zeitvarianten Simulationen resultieren, zu analysieren, ist die merkmalsbasierte Visualisierung. Die Analyse konzentriert sich dabei auf aussagekräftige Strukturen, sogenannte Features. Algorithmen für die zeitliche Verfolgung (Tracking) derartiger Strukturen zielen darauf ab, die zeitliche Entwicklung der Features zu rekonstruieren, indem sie automatisch zusammengehörige Strukturen in benachbarten Zeitschritten einander zuordnen. Bisherige Verfahren gehen davon aus, dass die untersuchten Strukturen nur einen geringen Teil des Datenraumes ausfüllen. Bei ausreichender zeitlicher Auflösung sind sie in der Lage, automatisch zeitliche Zusammenhänge zu bestimmen. Die im Rahmen unserer Forschung untersuchten Strukturen sind raumfüllend definiert, d.h. sie partitionieren die gesamte Domäne. Motiviert ist dies durch die Forschung unserer Kooperationspartner. Sie arbeiten an der statistischen Analyse von Dissipationselementen -- Strukturen, die per Definition raumfüllend sind. Ihr Ziel ist, die Analyse auf ein zeitvariantes Szenario auszuweiten. In dieser Arbeit stellen wir ein Verfahren vor, das die effiziente zeitliche Verfolgung beider Arten von Features ermöglicht. Dazu entwickeln wir ein Framework für die automatische Evaluierung von Tracking-Verfahren, ein algorithmisches Tracking-Framework und eine effiziente Implementierung dieses Frameworks. Zunächst entwickeln wir ein Evaluierungsframework, das mithilfe von algorithmischen Generatoren synthetische Datensätze und die zugehörigen Ground-Truth-Daten erzeugt. Auf diese Weise lässt sich die Genauigkeit einer Methode strukturiert quantifizieren und ein Vergleich verschiedener Ansätze anhand der Messungen wird ermöglicht. Anschließend stellen wir ein neues Verfahren für die zeitliche Verfolgung beliebiger Strukturen vor. Der zeitliche Zusammenhang zwischen benachbarten Zeitschritten wird durch sukzessives Lösen zweier Graphoptimierungsprobleme ermittelt. Zuerst werden lineare Zuordnungen durch ein gewichtsmaximales Matching maximaler Kardinalität auf einem bipartiten Graphen berechnet. In der zweiten Phase detektiert der Algorithmus Events. Dazu wird ein gewichtsmaximales Independent Set auf einem Graphen aller möglichen, potentiell widersprüchlichen Evolutionen bestimmt. Außerdem stellen wir eine optimierte Version der zweiten Phase des Algorithmus vor, die die modellspezifische Graphstruktur des Trackingproblems nutzt. Die Anwendbarkeit der Methode wird anhand mehrerer Fallstudien demonstriert, die sowohl die Evaluierung mithilfe des Frameworks als auch die Analyse verschiedener Simulationsdatensätze umfassen.

Feature-based visualization is a proven strategy to deal with the massive amounts of data emerging from time-dependent simulations: the analysis focuses on meaningful structures, i.e., said features. Feature tracking algorithms aim at automatically finding corresponding objects in successive time steps of these time-dependent data sets in order to assemble the individual objects into spatio-temporal features. Classically, feature-based visualization has focused on sparse structures, i.e. structures which cover only a small portion of the data domain. Given a sufficiently high temporal resolution, existing tracking approaches are able to reliably resolve the correspondence between feature objects of successive time steps. Our research is motivated by our collaborators' work on the statistical analysis of structures that are space-filling by definition: dissipation elements. Space-filling structures partition the entire domain. Our collaborators aim at extending their statistical analysis to a time-dependent setting. In this thesis, we introduce an efficient approach for general feature tracking which handles both sparse and space-filling data. To this end, we develop a framework for automatic evaluation of tracking approaches, an algorithmic framework for feature tracking, and an efficient implementation of this framework. First, we propose a novel evaluation framework based on algorithmic data generators, which provide synthetic data sets and the corresponding ground truth data. This framework facilitates the structured quantitative analysis of an approach's feature tracking performance and the comparison of different approaches based on the resulting measurements. Second, we introduce a novel approach for tracking both sparse and space-filling features. The correspondence between neighboring time-steps is determined by successively solving two graph optimization problems. In the first phase, one-to-one assignments are resolved by computing a maximum-weight, maximum-cardinality matching on a bi-partite graph. In its second phase, the algorithm detects events by finding a maximum weight independent set in a graph of all possible, potentially conflicting event explanations. Third, we show an optimized version of the second stage of the tracking framework which exploits the model-specific graph structure arising for the tracking problem. The method's effectiveness is demonstrated by a set of case studies including the use of the evaluation framework as well as the analysis of miscellaneous real-world simulation data sets.

OpenAccess:
PDF
(additional files)