[Back]

O. Dietzel:
"Combinatorial Optimization for the Compression of Biometric Templates";
Supervisor: G. Raidl, A Chwatal; Institut für Computergraphik und Algorithmen, 2008; final examination: 2008-05.

Biometrische Templates enthalten die zu einer Person gehörenden biometrischen Daten,
wie z. B. Fingerabdrücke oder Gesichtsmerkmale, die vor allem zu Verifikationszwecken
immer mehr an Bedeutung gewinnen. Damit eine Person jedoch anhand ihrer biometrischen
Merkmale erkannt werden kann, muss stets ein Referenztemplate zur Verfügung
stehen. Dieses kann in einer Datenbank, aber z. B. auch auf einem RFID-Chip gespeichert
sein. Gerade im Hinblick auf mobile Speichermedien und damit verbundene geringe
Speicherkapazitäten besteht ein Bedarf an der Kompression von biometrischen Templates.
Diese Kompression kann verlustbehaftet sein, sollte dabei jedoch mögliche Fehler
bei der Verifikation so gering wie möglich halten. Im Speziellen wird in dieser Masterarbeit
ein neuer Ansatz zur Kompression von Fingerabdrucktemplates entwickelt. Diese
Templates enthalten dabei Informationen zur Lage und Orientierung der so genannten
Minutien, d. h. den Endungen und Verzweigungen von Papillarlinien. Diese Informationen
werden als Punkte in einem d-dimensionalen Koordinatensystem dargestellt und
können auch als Knoten eines Graphen aufgefasst werden. Der Schwerpunkt dieser Arbeit
liegt daher auf der Betrachtung von graphenbasierten Kompressionsansätzen. Die
zugrunde liegende Idee dabei ist, anstelle von Punktkoordinaten die Differenzvektoren
zwischen jeweils zwei Punkten zu speichern. Gerichtete Spannbäume ermöglichen dafür
eine effiziente Kodierung. Im Zuge dieser Arbeit wurden daher Ansätze basierend auf
speziellen Spannbäumen, wie z. B. dem gerichteten Minimum Spanning Tree, dem
gerichteten Minimum Label Spanning Tree oder auch dem gerichteten Weight Balanced
Spanning Tree, untersucht und somit eine Kompression von bis zu circa 20% erreicht.