Pattern matching based on Hermann Weyl’s Discrepancy Norm

Autoren Christian Motz
Editoren
TitelPattern matching based on Hermann Weyl’s Discrepancy Norm
TypMaster-Arbeit
UniversitätFH Hagenberg, Embedded Systems Engineering
MonatAugust
Jahr2015
SCCH ID#1560
Abstract

In der heutigen Zeit zählt die Mustererkennung zu einem wichtigen Gebiet der Bildverarbeitung. Bei zeitkritischen Anwendungen spielen nicht nur die Qualität des Algorithmus, sondern auch sein Laufzeitverhalten und die Robustheit eine wichtige Rolle, um ein geeignetes Verfahren auswählen zu können. Das Diskrepanzmaß von Hermann Weyl zeigt in gewissen Punkten Vorteile gegenüber Standardmethoden wie der Korrelation. Betrachtet man eine Fehlausrichtung im Vergleich zum Optimum und variiert sie, so verhält sich das Diskrepanzmaß hier monoton. Zusätzlich erfordert die Berechnung keine typischen Filter Operationen wie die Faltung. Diese Arbeit konzentriert sich auf eine Implementierung des Diskrepanzmaßes kombiniert mit der Sliding Window Technik. Die Analyse erfolgt für den 1 und den 2-dimensionalen Fall. Für beide werden algorithmische Optimierungen gefunden, die eine schnelle Implementierung erlauben. Im 2- dimensionalen Fall für Bilder erfolgt eine Vektorisierung, die auf die SIMD Erweiterungen SSE und AVX nutzt. Praktische Tests zeigen hier einen Speedup von bis zu 16 auf den neuesten Haswell Prozessoren verglichen mit einer Referenzimplementierung. Da die Definition des Diskrepanzmaßes im 2-dimensionalen Fall stark mit Integralbildern zusammenhängt, wird der Ansatz für die Vektorisierung auf dieses Konzept übertragen. Auch hier gibt es eine deutliche Beschleunigung gegenüber aktuellen Implementierungen. Außerdem wird gezeigt, wie gleichzeitig zum Diskrepanzmaß gängige Normen wie die