Evaluation von Algorithmen zur Positionsdatenkompression

BearbeiterIn:Jonathan Reuss
Titel:Evaluation von Algorithmen zur Positionsdatenkompression
Typ:bachelor thesis
Betreuer:Mutschler, C.; Philippsen, M.
Status:abgeschlossen am 2. Oktober 2012
Vorausetzungen:
Thema:

Voraussetzungen:
Programmierkenntnisse in C/C++ oder Java, o.Ä.

Thema:
Die Gruppe „Sensorfusion und Ereignisverarbeitung" am Fraunhofer Institut für Integrierte Schaltungen in Nürnberg arbeitet an der Generierung und Verarbeitung von Positionsdatenströmen in Echtzeit. Hierbei werden verschiedene Verfahren eingesetzt, die die aktuelle Position eines Objekts in euklidischen Koordinaten zu errechnen. Die so erzeugten Daten werden derzeit unkomprimiert abgespeichert. Dies führt (je nach verwendetem Lokalisierungssystemen) zu einer Datenmenge von mehreren Gigabyte für weniger als eine Stunde an aufgezeichnetem Material, abhängig von der Anzahl der georteten Sender und der Trackingraten. Je nach Datenrate liegt in den Positionen jedoch eine gewisse Redundanz an Information vor, sodass zu einer gegeben Positionskurve der nächste Punkt nicht durch eine vollständige Beschreibung seiner Koordinaten gespeichert werden müsste. Unterschieden werden kann hierbei (wie bei allen Kompressionsverfahren) zwischen verlustfreier und verlustbehafteter Komprimierung. Letzteres gewann nicht zuletzt wegen der Errungenschaften in der Audio-, Videound Bildkomprimierung stark an Popularität. Verlustbehaftete Komprimierung von Positionsdaten kann bis zu einem gewissen Fehleranteil unter Abwägung der Datenrate durchaus toleriert werden. Ziel dieser Arbeit ist es, vorhandene Algorithmen zur Positionsdatenkompression zu recherchieren und zu implementieren. In Betracht kommende Verfahren sollen gegenseitig evaluiert werden, um einen guten Vergleich vermitteln zu können. Bewertungsfaktoren könnten hierbei beispielsweise die Fähigkeit zur Anwendung auf Datenströmen (Online-Verfahren) oder der benötigte Rechenaufwand sein.

Meilensteine:

  • Litaturrecherche und Einarbeitung in Kompressionsalgorithmen
  • Implementierung passender Algorithmen
  • Ausarbeiten von vergleichbaren Bewertungsfaktoren (Laufzeit, Fehler, etc.)
  • Evaluierung der Algorithmen
  • Ausarbeitung

Literatur:

  • Meratnia, N., Rold A. De By: A New Perspective on Trajectory Compression Techniques
  • Frentzos, E., Theodoridis, Y.: On the Effect of Trajectory Compression in Spatiotemporal Querying
  • Kellaris, G., Pelekis, N., Theodoridis, Y.: Trajectory Compression under Network Constraints
  • Lin, C., Chen, L.: Compressing Trajectories Using Inter-Frame Coding
watermark seal