3 Fingerprint

3.1 Sensoren

Der Fingerprint-Scanner auf den wir uns geeinigt haben, ist der Bird 3, der Firma TST-Biometircs. Er basiert auf berührungsloser Technologie für High-End Sicherheitssysteme. Zudem verfügt er über ein intelligentes Beleuchtungsboard und Modul für Falschfingererkennung, Fingerführung und ist optional mit Heizung erhältlich.

Der Scanner arbeitet mit einem CMOS Bildsensor und erreicht eine Auflösung von maximal 500 dpi, die Bildaufnahmezeit liegt unter einer Sekunde. Die API des Scanners liefert die Daten als Bitmap zurück. Es besteht die Auswahlmöglicheit zwischen verschiedenen Merkmalen.

  1. LFD (Life Finger Detection): Ermöglicht das an- und ausschalten der LFD Funktion.
  2. ImageMode: Stamp- und Photo-Modus. Der Stamp Modus lässt das Bild wie einen mit Tinte auf Papier erzeugten Fingerabbdruck erscheinen, und liefert somit ein Spiegelverkehrtes Bild.
  3. FastMode: im FastMode wird die LFD Funktion ausgeschaltet, und im Gegensatz zum normalen Modus nur ein Bild vom Scanner aufgenommen.
  4. PictureSize: Half und Full, ermöglicht die Konfiguration der ausgegebenen Bildgröße.
  5. Inverted: Liefert das Negativ des Bildes.

Der Bird 3 verfügt über eine USB 2.0 Schnittstelle, über die wir den Scanner mit einem Rechner, auf dem das Frontend unseres Systems läuft verbinden[?]. Als Ausweichmöglichkeit sei noch der BIRD IIi gegeben, der Vorgänger des BIRD 3. Er ist soweit Baugleich, verfügt aber über eine Ethernet (10 Base-T) Schnittstelle.

Die im Lieferumfang enthaltene API (Application Programming Interface), wird unter Windows XP Professional betrieben und eine Inbetriebnahme unter einer anderen Windows-Version ist nicht vorgesehen. Da auch keine passende API für alternative Betriebssysteme ( eq. Linux ) für diesen Scanner existiert und wir desshalb auch auf die Verwendung von Visual C++ angewiesen sind, bestimmt dieser Umstand maßgeblich unsere Entscheidung mit, dass das Terminal unter WindowsXP betrieben wird.

Darüber hinaus ist optional der TST Biometrics-Manager vorhanden, der bereits über einige Algorithmen verfügt. Diese Option wäre aufgrund unserer Aufgabe eher unnötig, könnte uns aber eine Vergleichsbasis für unser eigenes System liefern. Der TST Biometrics-Manager basiert auf der TST-API. Eine ausführliche Beschreibung der TST-API ist im zweiten Abschnitt gegeben. Eine Auflistung und Beschreibung der einzelnen Funktionen findet sich unter [?].


PIC

Abbildung 11: Abbild eines Bird 3 Scanners

3.1.1 TST-API

Die TST-API ermöglicht die Kommunikation mit dem TST Fingerprint Sensor. Sie erlaubt Anwendungen auf Sensor-Informationen wie Fingerprint Bilder und lebenderkennungs Informationen zuzugreifen. Die API synchronisiert den Zugriff auf den Sensor und verwaltet angeschlossene Clients.

Die API besteht aus zwei Hauptmodulen, dem TST-Device-Manager und dem TST-Core-Service.

Der TST Device-Manager erhält die Verbindung zu den angeschlossenen TST Sensoren, mittels dem TST-USB-Treiber bei USB-Sensoren oder via Ethernet bei den Ethernet-Sensoren, aufrecht. Er stellt dem TST-CoreService Informationen über die angeschlossenen Geräte zur Verfügung und überwacht den Datentransfer zu den Sensoren.

Der TST-CoreService ist der Knotenpunkt für sämtliche externe Clients. Er überwacht den Informationsfluss zwischen Sensoren und Client-Anwendungen. Darüber hinaus wird eine Anbindung an den optionalen TST-BiometricsManager angeboten.

Der TST-BiometricsManager ist eine Ergänzung zur TST-API. Er bietet eine einfache Möglichkeit biometrische Algorithmen in auf der TST-API basierenden Anwendungen zu integrieren. Eine Sammlung verschiedener Algorithmen für unterschiedliche Anwendungsanforderungen ist verfügbar. Diese werden über eine interne Schnittstelle verwaltet. Verfügbare Funktionalitäten sind Enroll-Sample und Identify-Sample. In unserem Fall ist der TST-BiometricsManager nicht erforderlich, da wir bekannterweise unsere eigenen Algorithmen entwickeln werden.


PIC

Abbildung 12: Die Architektur der TST-API

Relevant für uns ist, dass sämtliche Kommunikation zwischen Anwendung und TST-API über den TST CoreService abgewickelt wird.

Für alle eben beschriebenen Module wird bei der TST-API-Installation, ein entsprechender Microsoft Windows Service installiert. Jeder dieser Services wird durch eine ausführbare Datei im Installationsverzeichnis repräsentiert.

c:\Programme\TST Biometrics\TST Service\TST DeviceManager.exe+

und

c:\Programme\TST Biometrics\TST Service\TST CoreServer.exe+

Um die Anbindung und Fehlersuche an und in unsere Anwendung zu erleichtern, empfiehlt sich ein Zugriff auf die Logfiles der API. Diese sind in ihrer größe beschränkt und deren Inhalt hängt vom erstellenden Modul, sowie von den Konfigurationen ab. Die Einstellungen können in den entsprechenden .ini Files angepasst werden.

Die TSTBasic-API ist eine im Funktionsumfang reduzierte API, welche in Form einer DLL vorliegt. Im Gegensatz zur TST-API stellt sie keine Biometrischen Algorithmen zur verfügung. Sie bietet einen einfachen Zugriff auf die TST-Bird-Sensoren und deren Funktionalität. Lediglich die Bildaufnahme ist implementiert.


PIC

Abbildung 13: Synchrone Kommunikation

Die Kommunikation verläuft nach folgendem Prinzip:
Die Client-Anwendung startet und initialisiert den TST-DeviceManager. Daraufhin fordert der Client eine Liste verfügbarer Geräte (Sensoren) an. Aus dieser Liste wird ein Scanner gewählt und die Bildaufnahme wird angefordert. Zum Schluss muss der Client stoppen und den TST-DeviceManager bereinigen.

Generell gibt es zwei Möglichkeiten ein Bild aufzuzeichnen:

Synchron Bei einer synchronen Anforderung wird das Bild umgehend aufgezeichnet und das Ergebnis wird dem Client sofort zurückgeliefert. Die Bildaufnahme wird durch den Aufruf selber ausgelöst.


PIC

Abbildung 14: Synchrone Kommunikation

Asynchron Eine asynchrone Anforderung wartet bis der Sensor einen aufgelegten Finger erkennt. Der Unterschied zum synchronen Aufruf ist die Angabe eines Timeout. Der Aufruf einer asynchronen Bildaufnahme wird umgehend zurückgegeben, jedoch werden keine Bilddaten zum Client übermittelt. Der Rückgabewert übermittelt lediglich ob die Anforderung einer asynchronen Aufnahme erfolgreich war. Das Ergebnis des Aufrufs wird mittels einer Nachricht an eine anwendungsdefinierte Callback-Funktion übergeben. Durch diese Nachricht bekommt der Client entweder das Bild oder die Information, dass das Zeitlimit der Anforderung überschritten oder die Anforderung abgebrochen wurde.


PIC

Abbildung 15: Asynchrone Kommunikation

Nachrichten Neben synchronen Aufrufen bietet die TSTBasic API asynchrone Kommunikation durch Nachrichten an. Diese asynchronen Nachrichten werden genutzt, um beispielsweise über gewisse Ereignisse zu informieren (z. B. der Anschluss eines Sensors). Der Client erhält die Nachricht mittels einer Callback-Funktion. In folgenden Situationen erhält der Client Nachrichten:

Hinzugefügte/nicht mehr aktive Geräte Erkennt der TST-DeviceManager das neue Geräte angeschlossen werden oder Geräte nicht mehr verfügbar sind, wird die Callback-Funktion der Anwendung mit einer Nachricht aufgerufen.

Bildaufzeichnung Ein von der Anwendung angefordertes Bild wird als Teil einer Bildnachricht an die Anwendung übermittelt.

Timeout Im Fall einer Überschreitung des Timeout bei einer asynchronen Bildanforderung, wird der Anwendung eine Timeout-Nachricht übermittelt.

Abbruch der Aufnahme Im Fall eines Abbruchs der Aufnahme, wird mittels der Callback-Funktion eine „Aufnahme abgebrochen“ -Nachricht an die Anwendung übergeben.

Wenn eine Anwendung Nachrichten empfangen will, so muss sie dem TST-DeviceManager beim Start die Adresse der Callback-Funktion übergeben. Liegt eine Nachricht vor, so wird die Callback-Funktion aufgerufen. Da der TST-DeviceManager in einem anderen Thread läuft, muss der Client die Callback-Funktionsaufrufe im Allgemeinen serialisieren.

Eine Callback-Funtion muss nicht zwingend implementiert werden. Einfache Anwendungen, welche sich z. B. lediglich auf die synchrone Aufzeichnung von Bilddaten beschränken wollen, können darauf verzichten. Will man jedoch asynchrone Aufzeichnungen ermöglichen, oder ad-hoc Informationen über hinzugefügte oder ausgefallene Geräte erhalten, ist diese zwingend erforderlich. Die Callback-Funktion wird stets im Kontext des TST-DeviceManagers aufgerufen. Verarbeitet wird die Nachricht jedoch im Kontext des Anwendungs-Threads.

Neben den Fingerprints stellen die TST Biometric Sensoren auch eine „Life Finger Detection“ (LFD) zur Verfügung. Für jede Aufnahme wird automatisch ein LFD-Wert ermittelt und an die Anwendung übermittelt. Es liegt an der Anwendung diesen LFD-Wert zu verwenden oder zu verwerfen. Der Wert selber wird von keiner sonstigen API Funktion verwendet.

Um zu entscheiden, ob ein Finger als lebend angesehen wird, muss die Anwendung den LFD-Wert auswerten. Dieser nimmt Werte von 0 bis 5 an und wird im Zusammenhang mit der Bildstruktur verwendet.

Die genauen Funktionen können der TSTBasic-API-Reference entnommen werden.

3.2 Algorithmen

Die folgenden Unterabschnitte beschäftigen sich mit den Algorithmen zum Fingerprint-Matching die implementiert und getestet werden sollen. Es gibt eine vielzahl von Verfahren zum Fingerprint-Matching und monatlich gibt es Veröffentlichungen die neue oder optimierte Verfahren vorstellen. Diese Vielfalt ist der Hauptgrund warum wir entschieden haben, uns nicht vorweg auf ein konkretes Verfahren festzulegen, sondern mehrgleisig zu fahren. Wir haben exemplarisch drei Verfahren herausgesucht, die aus verschiedenen Gründen interessant scheinen.

Als erstes wird ein speziell für große Fingerabdruck-Datenbanken entworfenes Clustering-Verfahren vorgestellt, was selbst riesige Datenbanken durch wenige Vergleiche schnell zu durchsuchen.

Zusätzlich zum Clustering wollen wir zwei Verfahren verwenden, die direkt zwei Fingerabdrücke vergleichen und somit zur Verifizierung als auch Identifizierung einsetzbar sind. Durch die Verwendung von FPGAs zur Unterstützung bei den Vergleichen wollen wir auch mit diesen Verfahren einen hohen Durchsatz erzielen. Wir verwenden zwei Verfahren mit verschiedenen Ansätzen. Zum einen das klassisch Erprobte, welches die Minutienpunkte vergleicht, zum anderen ein relativ neues, welches sich in die Gruppe der Filterbank-basierten Verfahren einreiht.

Durch die Verwendung von verschiedenen Verfahren erhoffen wir uns, dass wir während der Implementierung mehr Optionen haben und somit, wenn sich ein Verfahren als nicht oder nur schlecht umsetzbar erweist, einige Alternativen vorhanden sind. Ein weiterer Vorteil der Betrachtung mehrerer Algorithmen ist, dass man die Option hat, diese zu kombinieren. Dadurch können noch besser Erkennungsraten erzielt werden. Mit diesem Thema beschäftigt sich der letzte Unterabschnitt genauer.

3.2.1 Bildverbesserung

Bevor aus einem Fingerabdruckbild die Merkmale extrahiert werden können, muss das Bild erst einmal überarbeitet werden. Das Erscheinungsbild sollte jedoch von Bearbeitungsschritt zu Bearbeitungsschritt ähnlich sein und nicht verfälscht werden. Dabei ist hauptsächlich die Bildhelligkeit sowie der Kontrast gefragt. Durch den Fingerprint Enhancement Algorithmus von Hong, Wan und Jain ist es möglich, das Bild qualitativ zu verbessern.

Dabei sind fünf Schritte notwendig, um ein optimiertes Bild zu erhalten:

  1. Durch Normalisierung wird der Grauwert an einen Standard angepasst. Ähnlich einer Transformation einer Normalverteilung in eine Standardnormalverteilung. Zunächst wird der Grauwert jedes Pixels aufsummiert und anschließend durch die Pixelanzahl geteilt (Mittelwert). Danach wird die Standardabweichung vom Mittelwert errechnet. Abschließend wird der Grauwert jedes Pixels in die Standardform transformiert.
  2. Danach folgt die Berechnung des Orientierungsfeldes, welches den Rillenverlauf innerhalb kleiner Bereiche wiedergeben soll. Das Bild wird daher in Blöcke (z. B. 16x16 Pixel) unterteilt. Nun wird für jeden Pixel der Grauverlauf sowohl in x- als auch in y-Richtung ermittelt. Daraus lässt sich dann eine ungefähre Richtung ermitteln, die senkrecht zum Fourier Spektrum verläuft.
  3. Anschließend erfolgt die Berechnung der Rillenfrequenz. Anhand des zuvor berechneten Orientierungsfeldes wird nun für jeden Block die Rillenfrequenz orthogonal zum Orientierungsvektor berechnet. Dazu werden die Peaks entlang einer Geraden in Rillenrichtung gezählt und somit eine Frequenz ermittelt. Durch gegebene Auflösung und Erfahrungswerte kann an dieser Stelle schon entschieden werden, ob die ermittelte Rillenfrequenz realistisch ist und somit der Block verwendbar ist.
  4. Bevor nun das Ergebnis zusammengerechnet wird, wird noch eine Regionsmaske erstellt. Sie ist dazu da, um unkenntliche Bereiche vom weiteren Processing auszuschließen. Es werden für jeden Block drei Werte zusammengefasst, die zuvor schon teilweise berechnet wurden: 1. Anzahl der Rillen in einem definierten Fenster, sowie (2.) die daraus resultierende Frequenz und 3. die Standardabweichung der Helligkeit der einzelnen Rillen. Diese Werte werden in ein dreidimensionales Koordinatensystem eingetragen. Liegt der Wert in einem bestimmten Bereich (der durch Tests ermittelt wird), so wird dem Block entweder der Wert brauchbar (true) oder unbrauchbar (false) zugewiesen.
  5. Zu guter Letzt wird das Ausgangsbild aufgewertet: Durch die Anwendung eines Gaborfilters als Bandpassfilter lässt sich die Rillenstruktur einfach hervorheben. Da der Gaborfilter zwei Parameter benötigt (Frequenz und Richtung) ist er der ideale Filter, um die Struktur zu verbessern.

Nachdem das Bild optimiert wurde, kann es nun zur Feature Extraction weitergereicht werden. Dabei müssen jedoch nicht alle bisher berechneten Werte verworfen werden. Im Gegenteil: das schon berechnete Orientierungsfeld lässt sich beim Matching gut als Kategorisierungsmerkmal nutzen.

3.2.2 Algorithmen zur Feature Extraction

Die am Häufigsten verwendete Methode der Feature Extraction sind die Minutien. Da es über 18 verschiedene Minutientypen gibt, wobei die meisten eher selten sind, beschränkt sich unser Algorithmus auf zwei Typen: Rillenende und Gabelung.

Das praktische daran ist die recht leichte Identifikation: Ausgehend vom Fingerprint sind zunächst einige Bearbeitungsschritte erforderlich, um schließlich in der Lage zu sein die gewünschten Minutien extrahieren zu können. Bei der Binarisierung wird das Bild in ein reines Schwarz-Weiß-Bild umgewandelt, um anschließend die Ridges auf eine Breite von 1-Pixel zu trimmen. Das Ergebnis ist das Skeletton-Bild des Fingerprints. In diesem Skeletton-Bild ist es nun mittels einfacher Bildscans möglich, die Minutien zu extrahieren. Man sucht jedes schwarze Pixel dieses Bildes ab und vergleicht seine nächsten acht Nachbarn hinsichtlich Ihrer Farbe. Dabei werden folgende Fälle als Minutien erkannt: Ist genau ein Umgebungspixel schwarz, so handelt es sich bei dem gefundenen Pixel um ein Ridge-Ende. Sind jedoch mindestens 3 Nachbarpixel schwarz, so handelt es sich um eine Bifurkation. Andernfalls liegt keine Minutie vor.

Zu jeder Minutie gehört neben den x-, y-Koordinaten und dem Typ, noch ein Winkel. Beim Ridgeending ist es der Winkel, in welche Richtung die Ridge weiter verlaufen würde. Bei der Bifurkation ist es die Richtung der Öffnung der Gabelung. Der FOMFE-Algorithmus (Fingerprint Orientation Model based on 2D Fourier Expansion) von Wang, Hu und Phillips ist ein Algorithmus, mit dem man sehr genau das Orientierungsfeld eines Fingerabdrucks sowie sehr genau Singular Points ermitteln kann. Hinter diesem Algorithmus steht – wie der Name schon sagt – einiges an Mathematik, denn der Fingerabdruck, genauer gesagt die Rillenstruktur, soll durch ein dreidimensionales Modell mit Hilfe von Fourierreihen angenähert werden.

Der eigentliche Durchlauf erfolgt in zwei Schritten. Der erste Schritt ist die Trainingsphase. Hier werden aufgrund einer groben Analyse des Graubildes zwei komplexe Koeffizientenmatrizen für die Fourierexpansion berechnet. Einmal für den Sinus- und einmal für den Cosinusanteil. Dieser aufwendige Schritt benötigt zwar etwas Zeit, jedoch lassen sich diese Matrizen wiederverwenden. Im zweiten Schritt wird mit Hilfe der berechneten Matrizen das Orientierungsfeld ermittelt. Aus Gründen der guten Verarbeitbarkeit werden die extrahierten Informationen in eine neue zweidimensionale Vektormatrix gespeichert, die jeweils den Sinus- und Cosinusanteil der eigentlichen Orientierungsvektoren repräsentiert. Damit kann nun für jeden einzelnen Pixel eine charakteristische Matrix A ermittelt werden. Anhand dieser Matrix lassen sich nun die Singular Points lokalisieren: Ist die Determinante von A gleich 0, so gibt es entweder keinen kritischen Punkt in der Nachbarschaft des untersuchten Pixels mit der Matrix A, oder alle Punkte in der Nachbarschaft sind kritisch. Was heißt kritisch? Kritisch ist ein Punkt dann, wenn er die Orientierungsvektoren in seiner Umgebung stark beeinflusst. Das ist zum Beispiel der Fall bei einem Core-Point, denn dort existiert eine große Krümmung im Orientierungsfeld und die einzelnen Orientierungsvektoren haben eine hohe Abweichung zu ihren Nachbarn. Ist die Determinante von A negativ, so befindet sich in der informationshaltenden Matrix ein Sattelpunkt. Daraus folgt, dass im Ursprungsbild an dieser Stelle ein Delta-Point liegt. Ist die Determinante von A positiv, so befindet sich in der informationshaltenden Matrix kein Sattelpunkt und im Ursprungsbild ist an dieser Stelle ein Core-Point. Anregung: Die Koeffizientenmatrix lässt sich noch weiter für die Indexierung von Fingerprints benutzen.

Ein weiterer Algorithmus für die Verarbeitung globaler Level 1-Merkmale, ist der Gaborfilter. Der Gaborfilter ist ein linearer Bildfilter, dessen Impulsauswirkung durch eine harmonische Funktion multipliziert mit einer Gaußschen Funktion definiert wird. Ziel des Filters ist es die Grate zu verstärken und Täler weicher werden zu lassen. Dabei spielen die Abstände zwischen den Graten eine wichtige Rolle, da der Filter auf den durchschnittlichen Gratabstand reagiert. Sind diese gleich - laufen also die Grate parallel zueinander - werden sie verstärkt. Der Filter wird mit den Parametern Frequenz und Richtung auf das ganze Bild angewandt. Die Frequenz bleibt stets gleich, nur die Richtung wird geändert. Gehen wir von beispielsweise acht Schritten aus, so beginnen wir mit dem ersten Filter bei 0 und drehen dann nach jedem Schritt den Filter im Uhrzeigersinn um jeweils 22.5, so dass wir bei einem potentiellen neuen Einsatz bei einem Winkel von 180 ankommen, der jedoch identisch zu 0 ist und somit nicht berechnet wird.

Stimmen die Richtungen des angewandten Gaborfilters mit der Rillenrichtung im Fingerabdruck überein, so wird das Rillenmuster durch den Filter hervorgehoben und es entsteht ein erkennbares Wellenmuster. Die damit erhaltenen acht berechneten Filterbilder dienen dann als Grundlage für die Berechnung der Feature Maps.

Da lokale Charakteristika eines Fingerabdruckes beim Matching durch Minutien nicht ausreichend beachtet werden können, bietet sich dafür das Matching durch Filterbänke an, das globale wie auch lokale Merkmale berücksichtigt. Komplette Vergleiche von Fingerabdruckbildern ginge sehr zu Kosten der Performance, da es auf einen Pixelvergleich über das gesamte Bild hinauslaufen würde. Um weniger, aber trotzdem genügend genaue Vergleichskriterien zu erhalten, wird nach der Berechnung eines Gaborfilters eine Feature Map erstellt, welche in ihren Sektoren die durchschnittlichen Grauwerte des entsprechenden Sektors enthält und damit die zu vergleichenden Merkmale bietet. Die Feature Map ist ein kreisförmiges Mosaik, welches in Ringe und Sektoren unterteilt ist und dessen Mittelpunkt der Core Point ist.

Die Anzahl der Ringe und Sektoren bestimmen später die Merkmalsgenauigkeit der Feature Map. Über die folgende Formel werden die Sektoren der Feature Map mit den durchschnittlichen Grauwerten des Sektors gefüllt.

V iθ = 1 ni( ni|Fiθ(x,y) Piθ|)

Die Feature Map kann auch in quadratischen oder einer anderen geometrischen Form dargestellt und berechnet werden. In der Praxis hat sich herausgestellt, dass die Kreisform die beste Form für eine Feature Map ist, da die relevanten Informationen des Fingerabdruckes sich um den Core-Point herum befinden und dort auch die geringsten Verzerrungsfehler bei der Aufnahme des Fingerabdruckes entstehen. Je weiter sich der zu untersuchende Bereich von dem Core-Point entfernt, umso größer ist die Wahrscheinlichkeit, dass der Abdruck verzerrt, unsauber und unvollständig ist. Darum haben wir uns entschieden für unsere Implementierung der Feature Map, ein kreisförmiges Mosaik zu nutzen.

Die Feature Map wird für jeden Winkel des angewandten Gaborfilters berechnet und ergibt dann den Feature Vektor eines Fingerabdrucks. Der Feature Vektor enthält also die jeweiligen Grauwerte einer Feature Map für alle berechneten Winkel des Gaborfilter. Der Feature Vektor kann kostengünstig gespeichert werden, da für jeden Grauwert eines Sektors nur ein Byte benötigt wird. Dem entsprechend berechnet sich der Speicherplatz (in Byte) für den gesamten Feature Vektor wie folgt:

S = AnzahlRinge AnzahlSektoren AnzahlWinkel

Da Fingerabdrücke sehr wahrscheinlich nicht mit identischer Ausrichtung aufgenommen und gespeichert werden, wird die dadurch entstehende Winkelabweichung dadurch abgefangen, dass verschiedene Feature Vektoren berechnet werden. Der ursprüngliche Aufnahmewinkel und jeweils Drehungen positiver und negativer Richtung mit gleichem Winkelabstand.

3.2.3 Clustering

Bei der Suche nach Fingerabdrücken mittels Clustering, wird die Datenbank in Cluster eingeteilt und jeder einzelne wird mit einem Repräsentanten versehen. Dadurch wird die Anzahl der Vergleiche sehr stark minimiert, da nicht mit allen Templates verglichen werden muss. Weiterhin werden auch die Cluster nochmal in Gruppen aufgeteilt, die wiederum durch einen Vektor repräsentiert werden. Durch diese Art der Optimierung der Datenbank wird auch bei großen Datenmengen die Anzahl der Vergleiche stark minimiert.
Es werden die Verfahren (Database-Clustering und die entsprechende Suche) von [?] verwendet. Hierbei wird zunächst die Datenbank mittels eines modifizierten KMeans-Algorithmus in die entsprechenden Cluster eingeteilt. Von einem Fingerabdruck werden zwei Merkmalsvektoren extrahiert:

Zur Einteilung der Cluster wird θ benötigt. Es werden vom KMeans-Algorithmus am Anfang zufällig k Cluster-Centroids (Repräsentanten) ausgewählt. Mittels eines Distanzmaßes dC [?] wird die Distanz von jedem Orientierungsvektor und den Centroids berechnet. Mit Hilfe dieses Ergebnisses werden die Vektoren ihrem Cluster zugeordnet. Da Anfangs die Repräsentanten zufällig gewählt werden, wird nach jeder Zuteilungsphase noch einmal ein neuer Cluster-Centroid für jeden Cluster berechnet. Dieser wird dann mit dem alten verglichen. Wenn sich dieser als effektiver herausstellt, werden alle Vektoren nochmals entsprechend der neuen Centroids verteilt. Als letzten Schritt des modifizierten KMeans-Algorithmus wird Überprüft, ob es keine zu großen oder zu kleinen Cluster gibt.
Nach dieser Einteilung kommt der Average-Ridge-Distance-Vector zum Einsatz. Um innerhalb der Cluster nicht jeden θ mit dem Suchvektor zu vergleichen, reduziert man hier die Anzahl der Vergleiche, indem man die Cluster nochmal in Gruppen anhand der ω einteilt. Die Zuordnung zu den Gruppen wird über eine einfache Mittelwertberechnung realisiert.
Die modifizierte Version des KMeans-Algorithmus entspricht folgendem Pseudo-Code:

KMEANS ( Data, K)

initClusterCentroids();
do

do

for each X Data and k Centroids

distance = calculateDistance(X,k);
assignToClosestCluster(X,distance);

calculateNewCentroids();
compareOldAndNewCentroids();

While(MAX(compareOldAndNewCentroids()) > ϵ)

While(noSmallCluster()ANDnoBigCluster())

Der Parameter ϵ sollte durch Tests empirisch festgelegt werden.
Wie bereits erwähnt, werden die einzelnen Cluster danach in Gruppen eingeteilt. Die Anzahl der Gruppen wird vorher festgelegt. Die Zuordnung erfolgt über den Vergleich mit den Mittelwerten der Gruppen (Berechnung siehe [?]).
Bei der Suche muss nur noch die Distanz zwischen dem Suchvektor und den Cluster-Centroids berechnet werden. Es wird ein Parameter festgelegt der einen Grenzwert darstellt, wann ein Cluster als Ergebnis in Frage kommt. Auf dieser Ergebnismenge wird dann mit Hilfe von ω weitergesucht. Zum Schluss erhält man eine relativ kleine Menge, die dann nochmal mit dem θ verglichen werden, um den endgültigen Fingerabdruck zu identifizieren.

3.2.4 Minutien

Zum Fingerprint-Matching über Minutienpunkte gibt es viele verfügbare Algorithmen und Ansätze von denen einige seit Jahrzehnten erprobt sind. Als Algorithmus haben wir uns für den in [?] vorgestellten entschieden, da dieser zum einen eine mögliche Rotation des Fingerabdrucks ausgleicht und zum anderen laut Paper eine FRR1 von 0.1% und eine FAR2 von 0.001% erreicht.

Das neue an dem Algorithmus ist, dass er einige wenige Referenzpunkte um den Core-Point bestimmt und anhand dieser einige Rotationen durchprobiert. So wird mit einigen wenigen, logischen Rotationen eine beliebige Rotation ausgeglichen anstatt z.B. 360 verschiedene durchzuprobieren.

Nach jeder Rotation müssen die ausgerichteten Sets von Minutienpunkten verglichen werden. Hier gibt es zwar verschiedene Ansätze, die Grundidee ist aber immer dieselbe: Es wird jeder Punkt aus dem einen Set mit jedem aus dem anderen Set verglichen (Point Pattern Matching). Bei diesem Vergleich wird geprüft ob die beiden Punkte innerhalb einer gewissen Toleranz übereinstimmen oder nicht. Die übereinstimmenden Punkte werden gezählt und anschließend daraus ein Matchingscore berechnet.

Für den Schritt des Point Pattern Matching nehmen wir als Grundidee die aus [?], wo jeweils ein Punkt vom Set des Templateabdrucks gleichzeitig mit allen Punkten des Queryabdrucks verglichen wird. Dabei werden zu Beginn des Matchings alle Punkte des Queryabdrucks auf einen FPGA geladen und anschließend nacheinander alle Punkte des Templateabdrucks zum Vergleich hochgeladen. Über einen globalen Bus wird das Ergebnis des Matchings dem Host-Computer mitgeteilt. Durch den parallelen Vergleich wird die Laufzeit von quadratisch auf linear verbessert.

Es gibt bei den verwendeten Algorithmen viele Parameter an denen man tunen kann um eine bessere Erkennungsgenauigkeit zu erhalten oder die Performance zu verbessern. Dies wird im Laufe der Implementierung empirisch durch Tests geschehen. Die möglichen Parameter hierbei sind:

3.2.5 Filterbank

Eine weitere, sehr schnelle Möglichkeit Fingerabdrücke zu matchen ist der Vergleich ihrer Feature Vektoren. Nach deren Berechnung geschieht das Matching dadurch, dass die in den Sektoren enthaltenen Grauwerte des Queryabdruckes von den Sektorgrauwerten gleicher Position der Templateabdrücke subtrahiert und die Differenzen aufsummiert werden. Die Summe wird dann durch die Anzahl der Sektoren dividiert und bildet dadurch ein Scoringwert der die Abweichung der Grauwerte darstellt. Anhand der berechneten Scoringwerte, kann nun durch eine vorher noch zu bestimmtende Schranke festgestellt werden, ob sich zwei Fingerabdrücke ähneln oder nicht. Dadurch können dann zum Beispiel die zehn Templateabdrücke herausgefunden werden, bei denen die Scroringwerte und damit die Abweichungen der Grauwerte am geringsten sind.

Der Algorithmus für die Berechnung des Scoringwert lautet:

M = 1 b k i=0bk|D Q(i) DT (i)|

Die Performance und die Erkennungsgenauigkeit des Algorithmus hängt von den folgend, genannten Parametern entscheidend ab. Jedoch werden diese erst durch experimentelle Erprobung auf dem Zielsystem spezifiziert werden können. Die wichtigsten Parameter hierbei sind:

3.3 Kombinierung der Verfahren

Im Folgenden werden einige Möglichkeiten diskutiert, die es erlauben durch Kombination der drei Verfahren — Clustering, Minutien und Filter–Bank — die Erkennungsgenauigkeit zu verbessern. Ob sie durchführbar sind und den gewünschten Effekt haben, wird sich im Rahmen des Prototypings zeigen.

Die logischste Möglichkeit, bessere Erkennungsraten zu erzielen, ist auch zugleich die performancelastigste. Anstatt nur einen Matchingalgorithmus zur Suche zu verwenden, werden alle drei parallel ausgeführt. Die von allen zurückgelieferten Fingerabdrücke werden zum Schluss noch einmal miteinander verglichen und nur die, die bei allen geliefert wurden, werden dem User als Ergebnis zurückgeliefert. Wir hoffen, dass mit dieser Kombinationsweise mögliche False Positives mit hoher Wahrscheinlichkeit herausgefiltert werden können, da alle drei Verfahren grundlegend verschiedene Ansätze haben. Wenn man genügend Resourcen hat verlängert dies auch nicht die Laufzeit, da alle drei Matchingverfahren unabhängig voneinander ausgeführt werden können. Nur das anschließende Crosschecking verlängert die Dauer des Matchings. Da hier jedoch nur IDs miteinander verglichen werden ist dies vernachlässigbar.

Eine weitere Möglichkeit zur Kombination der Verfahren ist, zuerst das Clustering zu nutzen um mit wenigen Vergleichen schnell eine Gruppe von Fingerabdrücken zu finden, die anschließend noch mit einem anderen Verfahren, z.B. dem Filterbank–based, im Detail gematcht werden. Dies erlaubt auf jeden Fall einen Performancegewinn gegenüber der reinen Verwendung des Minutien– oder Filterbank–basierten Verfahrens, da die Anzahl der direkten Vergleiche drastisch reduziert wird. Ob es Auswirkungen auf die Erkennungsgenauigkeit vom Clustering haben wird ist noch nicht absehbar. Bei diesem Vorgehen ist es auch möglich, zum direkten Vergleich ein nicht so performantes Matchingverfahren zu verwenden, da es sich in der Regel nur um relativ wenige Abdrücke im Vergleich zur Gesamtmenge aller Abdrücke handelt.

3.4 Schnittstellen

In diesem Abschnitt werden die Schnittstellen und Datenformate vorgestellt, die zur Speicherung und Übertragung von Fingerabdruckrohdaten und –templates verwendet werden sollen. Es wird nur beschrieben wie die Struktur eines Templates aussieht, genauere Details zur physikalischen Speicherung der Templates sind unter 2.3 zu finden.

Zur archivierten Speicherung der Rohdaten, also der Fingerabdruckbilder, gehen wir nach der Empfehlung vom NIST3 vor und verwenden ein modifiziertes JPEG Kompressionsverfahren, welches für Fingerabdrücke angepasst wurde. Der verwendete Algorithmus nutzt das Wavelet Scalar Quantization (WSQ) Kompressionsverfahren um die Graustufenbilder der Fingerabdrücke dauerhaft zu archivieren[?].

Im folgenden werden die Datenstrukturen zur Speicherung und Übertragung der extrahierten Features genauer beschrieben. Wir haben uns für feste Bitlängen bei den einzelnen Daten entschieden. Zum einen um Speicherplatz und Netzwerkbandbreite zu sparen, zum anderen weil auf diese Art und Weise kein Pre–Processing mehr nötig ist um die Daten für den FPGA aufzubereiten. Die nächsten drei Abschnitte geben die Datenstruktur für den jeweiligen Matchingalgorithmus an.

Clustering Bei jedem Template wird eine 32 bit lange ID mitgespeichert, die eine Zuordnung zu weiteren Daten ermöglicht. Die für das Clustering benötigte Datenstruktur für ein Template sieht wie folgt aus:

    id                 ::= 32bit unsigned integer  
    angle              ::= 9bit unsigned integer  
    orientation_vector ::= angle^156  
    ard_vector         ::= 8bit unsigned integer  
    template           ::= id orientation_vector ard_Vector

Genauere Details zu dem Orientierungsvektor (orientation_vector) und dem Average-Ridge-Distance-Vector (ard_vector) sind dem Abschnitt 3.2.3 zu entnehmen. Die fixe Gesamtlänge des Templates beträgt 1444 bit.

Minutien Die von den Sensoren oder Fingerabdruckkarten gescannten Bilder haben nach dem aktuellen Stand der Technik eine Auflösung von 500 dpi. Dieser Wert wird auch vom FBI als Standard verwendet[?]. Nur für Testzwecke oder manuelle Vergleiche am Bildschirm werden Auflösungen von 1000 dpi oder mehr verwendet[?]. Da bei dieser Auflösung kein Fingerabdruck die Größe von 1024x1024 Pixeln überschreiten wird, reicht ein 10 bit breiter Integer zur Speicherung von Koordinaten. Der Winkel eines Minutienpunktes wird als 9 bit Integer gespeichert (wobei nur die Werte 0-360 genutzt werden). Es macht hier keinen Sinn auch Nachkommastellen zu berücksichtigen, weil beim Matching Toleranzbereiche > 1 üblich sind und auch bereits ein verschobener Pixel ausreicht um eventuelle Nachkommastellen stark zu verändern. Der Typ eines Minutienpunktes, also ob Gabelung oder Rillenende, wird offensichtlich als 1 bit Integer abgespeichert, wobei die 0 eine Gabelung repräsentiert und 1 ein Rillenende. Ein sehr gut gescannter Fingerabdruck hat im Schnitt 60 Minutien. Da wir für die Datenstruktur eine feste Größe brauchen setzen wir eine Maximalanzahl von Minutien, die im Template gespeichert werden. Sollten mehr Minutien extrahiert werden, lassen wir die fallen, die sich am weitesten aussen befinden. Daraus ergibt sich folgende Datenstruktur für die extrahierten Minutien mit einer fixen Gesamtlänge von 2152 bit:

    id         ::= 32bit unsigned integer  
    pixel      ::= 10bit unsigned integer  
    angle      ::= 9bit unsigned integer  
    type       ::= 1bit unsigned integer  
    coordinate ::= pixel pixel  
    core       ::= coordinate  
    minutia    ::= coordinate angle type  
    template   ::= id core minutia^70

Filterbank Für das Filterbank basierte Verfahren werden die Grauwerte der einzelnen Sektoren abgespeichert. Wie sich die Gesamtanzahl der Sektorfelder zusammensetzt ist in 3.2.5 beschrieben und wird hier mit numsectors bezeichnet. Die Datenstruktur ist somit in Abhängigkeit der Anzahl der Sektorfelder 32 + (numsectors 8 + 9) 5 bit gross. Für die laut Paper optimale Anzahl von 80 Sektorfelder ergibt sich somit eine feste Größe von 3277 bit. Die Datenstruktur des Templates setzt sich wie folgt zusammen:

    id             ::= 32bit unsigned integer  
    gray_value     ::= 8bit unsigned integer  
    angle          ::= 9bit unsigned integer  
    feature_map    ::= gray_value^num_sectors  
    feature_vector ::= angle feature_map^8  
    template       ::= id feature_vector^5

Sollten wir im Laufe der Implementierung feststellen, dass ein Wertebereich nicht ausreicht, kann es sein, dass sich die Bitbreite einzelner Werte minimal ändert. Die Struktur ist hiervon jedoch unberührt.