Feature Tracking Utilizing a Maximum-Weight Independent Set Problem

Andrea Schnorr, Dirk Norbert Helmrich, Hank Childs, Torsten Wolfgang Kuhlen, Bernd Hentschel
The 9th IEEE Symposium on Large Data Analysis and Visualization

Tracking the temporal evolution of features in time-varying data remains a combinatorially challenging problem. A recent method models event detection as a maximum-weight independent set problem on a graph representation of all possible explanations [35]. However, optimally solving this problem is NP-hard in the general case. Following the approach by Schnorr et al., we propose a new algorithm for event detection. Our algorithm exploits the modelspecific structure of the independent set problem. Specifically, we show how to traverse potential explanations in such a way that a greedy assignment provides reliably good results. We demonstrate the effectiveness of our approach on synthetic and simulation data sets, the former of which include ground-truth tracking information which enable a quantitative evaluation. Our results are within 1% of the theoretical optimum and comparable to an approximate solution provided by a state-of-the-art optimization package. At the same time, our algorithm is significantly faster.

» Show BibTeX

@InProceedings{Schnorr2019,
author = {Andrea Schnorr, Dirk Norbert Helmrich, Hank Childs, Torsten Wolfgang Kuhlen, Bernd Hentschel},
title = {{Feature Tracking Utilizing a Maximum-Weight Independent Set Problem}},
booktitle = {9th IEEE Symposium on Large Data Analysis and Visualization},
year = {2019}
}




Disclaimer Home Visual Computing institute RWTH Aachen University