Adaption des Levenshtein-Abstandes zur Online-Handschriftauthentifikation

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

1 Einleitung

2 Biometrie – Überblick
2.1 Verschiedene biometrische Merkmale
2.2 Handschrift als biometrisches Merkmal
2.2.1 Offline-Authentifikation
2.2.2 Online-Authentifikation
2.2.3 Vergleich von Offlineund Online-Verfahren
2.2.4 Handschrifterkennung
2.2.5 Forensische Schriftuntersuchung
2.2.6 Terminologie und Definitionen
2.3 Performance und Fehlerraten

3 Grundlagen und Adaption
3.1 Handschriftliche Eingaben als Zeichenketten
3.2 Levenshtein-Abstand
3.3 Adaption des Levenshtein-Abstandes
3.3.1 Längenabhängigkeit
3.3.2 Kurze Segmente
3.3.3 Simultanereignisse
3.3.4 Enrollment und Authentifikation
3.4 Vergleich mit anderen Verfahren

4 Tests
4.1 Ausgangsdaten
4.2 Voruntersuchung – Gleichzeitigkeit
4.3 Test-Ziele
4.4 Erwartungen
4.5 Tests mit Wacom-Geräten
4.5.1 Enrollment
4.5.2 Verifikation
4.5.3 Identifikation
4.6 Geräteübergreifende Tests

5 Ergebnisse und Vergleich mit anderen Verfahren
5.1 Ergebnisse
5.2 Vergleichbare Verfahren
5.2.1 Schriftdatenbank
5.2.2 Statistische Unterschriftenanalyse
5.2.3 Strukturelle Unterschriftenanalyse
5.2.4 Zeit-Frequenz-Analyse von Unterschriften
5.3 Vergleich

6 Zusammenfassung und Ausblick

A Testergebnisse
A.1 Verifikation – Wacom
A.2 Identifikation – Wacom
A.3 Verifikation – geräteübergreifend
A.4 Identifikation – geräteübergreifend

Literaturverzeichnis

Index

Abbildungsverzeichnis

2.1 Statische Informationen einer Unterschrift [Bal]

2.2 Online-Rohdaten

2.3 Intervall-Band für -Funktion [Vie00]

2.4 Unistroke-Alphabet

2.5 Überblick: Enrollment, Verifikation, Identifikation

2.6 FAR-FRR- sowie ROC-Kurven [Bro]

3.1 Beispiel einer Schriftprobe

3.2 Diagramme der zeitabhängigen Größen einer Schriftprobe

3.3 Ereigniskette zur Schriftprobe

3.4 Zeichenketten-Abstände

3.5 Bestimmung des Levenshtein-Abstandes

3.6 Durchschnittlicher Levenshtein-Abstand in Abhängigkeit von der Länge der Eingaben

4.1 Die fünf untersuchten Semantikklassen

4.2 Verteilung der Datensätze auf die Personen

4.3 Verifikationsfehlerraten für Unterschriften auf Wacom-Geräten

4.4 Identifikationsfehlerraten für Unterschriften auf Wacom-Geräten

5.1 Statistische und strukturelle Unterschriftenanalyse. [Sch99]

5.2 Spezialpunkte und Markanzwerte. [Sch99]

5.3 Vergleich des Zeit-Frequenz-Verfahrens mit anderen Verfahren. [Sch99]

Tabellenverzeichnis

3.1 Ereigniskodes

3.2 Liste möglicher Einzel-Ereignisse

4.1 Liste der Eingabegeräte

4.2 Verteilung der Testdatensätze

4.3 Häufigkeit von gleichzeitigen Ereignissen

4.4 Verteilung der Testdatensätze mit Wacom-Eingabegeräten

4.5 Equal-Error-Rates der Verifikation auf Wacom-Geräten

4.6 Equal-Error-Rates der Identifikation auf Wacom-Geräten

4.7 Equal-Error-Rates der Verifikation – geräteübergreifend

4.8 Equal-Error-Rates der Identifikation – geräteübergreifend

Kapitel 1 Einleitung

[Abbildung in dieser Leseprobe nicht enthalten], die; - ([Lehre von der] Zählung u. [Körper]messung an Lebewesen)

Besonders in jüngster Zeit ist Biometrie wieder im Fokus der ö ffentlichkeit. Insbesondere, wenn es darum geht, die Innere Sicherheit, zumindest jedoch das subjektive Sicherheitsempfinden der Bürger, zu erhöhen, gilt Biometrie als eines der Mittel der Wahl. So ist die Rede von Überwachungskameras, die mit Personenund Gesichtserkennungssystemen gekoppelt sind, von Fingerabdruckdaten in Personaldokumenten und ä hnlichem mehr. Im selben Maße, wie die Planungen zum Einsatz von biometrischen Methoden im Alltag voranschreiten, wachsen jedoch auch die Bedenken einer Vielzahl von Bürgern vor dem Neuen, Unbekannten, das eventuell in der Lage sein könnte, ihre persönliche Freiheit einzuschränken.

Im Vergleich zu anderen biometrischen Merkmalen besitzt die Handschrift ein eher geringes Überwachungspotential und hat deshalb, vor allem aber auch aufgrund ihrer bereits langen Verwendung im Alltag, einen großen Akzeptanzbonus. Anders als bei der Unterschriftenerkennung wittert der Datenschützer im Zusammenhang mit etwa Gesichtserkennungssystemen Gefahren und fühlt sich der Bürger bei Fingerabdruckverfahren an eine kriminalistische, erkennungsdienstliche Behandlung erinnert.

Unter Biometrie wird generell die Zählung und Vermessung von lebenden Objekten verstanden. Das kann beispielsweise bedeuten, dass Biologen die Stichlingspopulation in einem See auszählen. Es bedeutet aber mitunter auch die Vermessung separater biologischer Merkmale einzelner Personen zum Zwecke der Authentifikation. Zu diesen Merkmalen können physiologische Eigenschaften des Menschen zählen, wie die Form seiner Fingerund Handlinien, der Blutgefäße seiner Retina oder die Ausprägung seiner Iriden.

Neben der Physiologie untersucht die Biometrie auch verhaltenstypische Eigenschaften. Die Art, wie ein Mensch geht, spricht oder mit einem Stift schreibt, zeichnet ihn aus und macht ihn von anderen Menschen unterscheidbar.

Die Handschrift als biometrisches Merkmal wird nicht nur zur Authentifizierung von Personen, sondern auch zur Computersteuerung eingesetzt. Dabei ist die Erkennung des Schriftinhaltes zentral. Verfahren zur Handschrifterkennung sind insbesondere für solche Anwendungsfälle denkbar und sinnvoll, in denen computerunkundige Personen mit der Technik in Berührung kommen und ihnen die Möglichkein eingeräumt wird, auf Tastatureingaben zu verzichten.

Die vorliegende Diplomarbeit befasst sich mit dem biometrischen Merkmal Handschrift zur Personenauthentifizierung. Es wird unterschieden zwischen so genannten Offlineund Online-Verfahren der Handschriftuntersuchung. Erstere nutzen Schriftbilder auf Papier, letztere dynamische Schreibsignale, welche mittels spezieller Geräte während des Schreibvorgangs gemessen werden. In dieser Diplomarbeit liegt das Augenmerk auf den Online-Verfahren. Es wird ein neues Verfahren der Authentifikation mittels dynamischer Schreibdaten vorgestellt. Dieses Verfahren greift auf Mittel zurück, die aus anderen Disziplinen der Informatik bekannt sind, etwa der Bioinformatik. Ziel ist es, zu untersuchen, ob mit diesem neuen Verfahren die Fehlerraten bisheriger Verfahren verbessert werden können. Um möglichst realistische Resultate zu erzielen, soll dabei eine große Testdatenbank zum Einsatz kommen, etwas, das häufig in fremden Arbeiten nur unzureichend berücksichtigt wird.

Zuerst soll in Kapitel 2 ein kurzer Überblick über biometrische Verfahren im Allgemeinen und handschriftliche Verfahren im Speziellen gegeben werden. Im Anschluss daran werden wichtige Begriffe definiert und Fehler diskutiert, die in biometrischen Systemen messbar sind. In Kapitel 3 wird das Konzept des neuen Verfahrens, basierend auf dem Levenshtein-Abstand, im Detail vorgestellt. Der Levenshtein-Abstand ist eine Möglichkeit, die ä hnlichkeit zweier Zeichenketten zu bestimmen und wird seit langem an verschiedenen Gebieten der Informatik, etwa der Textanalyse und der Bioinformatik, verwendet. In Kapitel 4 werden Tests präsentiert, die mit Hilfe einer umfangreichen Datenbasis durchgeführt werden. Es folgen die Resultate der Tests sowie ein Vergleich mit anderen Verfahren in Kapitel 5 sowie schließlich ein Ausblick, wie das Verfahren in Zukunft verbessert werden kann.

KAPITEL 2. BIOMETRIE – ÜBERBLICK 3

Unter biometrischen Verfahren versteht man im Zusammenhang mit Identifikation und Verifikation die Feststellung oder Bestätigung der Identität einer Person anhand von Merkmalen, die dieser Person aufgrund physiologischer, verhaltenstypischer und ähnlicher Umstände eigen sind. Für die meisten Menschen ist eine Identifikation anderer Personen anhand des Gesichtsbildes möglich – wir sind in der Lage, eine uns bekannte Person beispielsweise auf einer Fotografie wiederzuerkennen. Ebenfalls fällt das Wiedererkennen einer bereits gehörten Stimme oft leicht. Biometrie im Sinne dieser Diplomarbeit befasst sich damit, solch ein Wiederkennen von menschlichen Merkmalen mit Hilfe von Computern zu leisten.

2.1 Verschiedene biometrische Merkmale

Neben den zwei erwähnten Beispielen aus der Alltagswelt ist der Fingerabdruck das bekannteste biometrische Merkmal. Die Erkennung einer Person anhand ihres Fingerabdrucks beruht auf der Annahme, dass sich a) die Fingerlinienbilder verschiedener Personen voneinander unterscheiden und b) die Fingerlinien einer Person im Laufe ihres Lebens nicht wesentlich verändern. Diese zwei Kriterien – Einzigartigkeit sowie Stabilität über die Zeit – sind entscheidend für die Qualität eines biometrischen Merkmals. Die genannten Beispiele lassen sich unterscheiden in aktive und passive biometrische Verfahren. Die Erkennung von Gesichtern und Fingerabdrücken sind Beispiele für passive Verfahren. Ihnen gemein ist, dass sie Eigenschaften der Physiologie des Menschen zum Ausgangspunkt haben. Weitere passive biometrische Merkmale sind etwa die Handgeometrie, das Wärmebild (Thermogramm) des Körpers sowie speziell des Gesichts, die Regenbogenhaut (Iris) und Netzhaut (Retina).

Im Kontrast zu diesem passiven Merkmalen handelt es sich bei den aktiven um solche Merkmale, die verhaltensbasierte Eigenschaften der Trägers berücksichtigen. Der Klang der menschlichen Stimme ist solch ein verhaltensbasiertes Merkmal, das geeignet ist, einen Sprecher von anderen Sprechern zu unterscheiden. Ebenfalls zu den aktiven Merkmalen gehören etwa die Lippenbewegung beim Sprechen, die Ausprägung von bestimmten Bewegungen, wie etwa des Ganges, die Anschlagdynamik bei der Bedienung von Tastaturen und die Dynamik der Handschrift. Letzteres, die Handschrift als biometrisches Merkmal, steht im Mittelpunkt dieser Arbeit.

2.2 Handschrift als biometrisches Merkmal

Die Verknüpfung der Identität einer Person mit ihrer Handschrift, insbesondere mit ihrer Unterschrift, ist seit langem bekannt und weiträumig akzeptiert. So kann etwa bei Gericht ein Sachverständiger aus der Unterschrift auf einem Dokument den Urheber feststellen. (Vgl. ZPO § 441) Die Verfahren zur Handoder Unterschriftserkennung lassen sich unterteilen in statische und dynamische Verfahren; auch Offlinebzw. Online-Verfahren genannt [PL89][LP94].

Neben der Erkennung oder Bestätigung der Identität des Urhebers einer Schriftprobe ist es auch möglich, den Schriftinhalt zu ermitteln. Dies wird zur automatischen Verarbeitung von handschriftlichen Informationen benutzt. Ein Beispiel dafür ist die automatische Erkennung der Anschrift auf einem Brief.

2.2.1 Offline-Authentifikation

Unter statischen oder Offline-Verfahren zur Handschrift-Authentifikation werden solche Verfahren verstanden, bei denen die handschriftlichen Rohdaten allein in Form des Schriftbildes vorliegen. Dies ist in den meisten Fällen eine Schriftprobe auf einem Blatt Papier, also zum Beispiel eine Tintenspur. Zur automatischen Verarbeitung wird diese Schriftprobe gescannt und liegt danach normalerweise als 2D-Abbild vor. Da für eine genaue Ermittlung des Urhebers einer Schriftprobe die Dynamik der Handschrift, insbesondere die Druckinformation, sehr wichtig ist, müssen diese Daten aus den zweidimen- Am Schriftstück selbst kann der Entstehungsdruck ” bzw. die Kraft nicht mehr gemessen werden. Möglich ist nur die Erfassung von Parametern wie Linienbreite oder Druckrillentiefe. Sofern eine Eichtabelle für die erkennbaren Schreibbedingungen existiert, können diese Parameter in Druckwerte umgerechnet werden.“ [Mau01]

In Abbildung 2.1 ist die mikroskopierte Aufnahme einer Schriftprobe dargestellt, geleistet mit einen Stift ohne Tinte. Zu sehen ist das Resultat einer für den Schreiber charakteristischen Druckerzeugung während des Schreibvorganges.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Statische Informationen einer Unterschrift [Bal]

Für Zwecke der biometrischen Identifikation und Verifikation in Zugangsund Zugriffskontrollszenarien sind Offline-Verfahren eher ungeeignet. Zu aufwändig ist es, erst auf einem Blatt Papier zu unterschrieben und dieses dann in den Computer einzuscannen. Für solche Zwecke deutlich besser geeignet sind die dynamischen Verfahren.

Sinnvoll sind Offline-Verfahren jedoch in solchen Fällen, in denen typischerweise bereits statische Schriftinformationen vorliegen, wie etwa bei der automatischen Überprüfung der Unterschriften auf Schecks und Überweisungsformularen, Szenarien also, in denen sonst üblicherweise ein Mensch die Überprüfung vornehmen würde, etwa ein Bankangestellter. [PS00]

2.2.2 Online-Authentifikation

Den Gegensatz zu statischen Verfahren der Handschrifterkennung stellen die dynamischen Verfahren dar. Der größte Unterschied zwischen statischen und dynamischen Handschriftuntersuchnungen ist, dass bei der statischen Analyse nur das Resultat eines Schreibvorgangs vorliegt, also das Schriftbild, wohingegen bei der dynamischen Analyse darüber hinaus auch Informationen über die Entstehung des Schriftbildes vorhanden sind, also Daten über die Reihenfolge, in der einzelne Teile des Gesamtbildes entstanden sind, in welcher Richtung der Stift geführt wurde und vieles mehr. Das wesentliche Merkmal dynamischer Verfahren ist, dass die Schreibinformationen mit Hilfe spezieller Geräte bereits während des Schreibvorgangs elektronisch erfasst werden. Dies erfolgt in den meisten Fällen mittels spezieller Schreibunterlagen (Tabletts) und/oder Stifte, die direkt oder indirekt über die Position der Stiftspitze auf der Schreiboberfläche Auskunft geben. In vielen Fällen werden dabei weitere Daten, wie etwa der Stiftdruck (bzw. die Kraft, mit der die Stiftspitze auf die Schreiboberfläche wirkt) und die Stiftneigung erfasst. In Abbildung 2.2 sind die für Verfahren der dynamichen Handschrifterkennung am häufigsten erfassten Ausgangsdaten skizziert.

Die diskreten Rohdaten werden dabei in mehr oder minder festen zeitlichen Intervallen erfasst. Zu den signifikantesten dynamischen Merkmalen einer Unterschrift zählen laut [LP94] die Schreibgeschwindigkeit und -beschleunigung. Diese Werte können zum einen mathematisch aus den Positionsdaten in Abhängigkeit von der Zeit bestimmt werden, zum anderen gibt es aber auch spezielle Geräte, die Sensoren für diese physikalischen Größen besitzten. Die gegenwärtig für dynamische Handschrifterkennung am häufigsten eingesetzten Geräte sind handelsübliche Grafiktabletts sowie PDA-Geräte mit Stifteingabe.

Wie bei allen Verfahren zur biometrischen Authentifikation steht auch bei der Online- Handschriftanalyse ein Vergleich von mehreren erfassten biometrischen Daten im Mittelpunkt. Es geht also darum, mindestens zwei Schriftproben miteinander zu vergleichen und einen Wert für ihre ä hnlichkeit zu bestimmen. Dabei soll die ä hnlichkeit dann besonders groß sein, wenn sie von ein und demselben Urherber stammen. Um zwei Schriftproben miteinander vergleichen zu können, müssen sie in eine mathematische Repräsentation überführt werden. In [PL89] wird dabei zwischen einer Funktionsund einer Parameterrepräsentation unterschieden.

Die Funktionsrepräsentation interpretiert die erfassten und abgeleiteten Daten als komplexe Funktion über die Zeit. Die Menge der zeitäbhängigen Parameter [Abbildung in dieser Leseprobe nicht enthalten] (etwa die xund y-Position, Druck, Stiftneigung, Geschwindigkeit, . . . ) ließe sich so als Funktionen [Abbildung in dieser Leseprobe nicht enthalten]. . . auffassen. Zum Vergleich von Schriftproben mittels einer Funktionsrepräsentation ist es fast immer nötig, die Zeit-Achsen der Funktionen der zu untersuchenden Schriftproben aneinander anzupassen (dynamic time warp), da in den seltensten Fällen zwei Unterschriften ein genau gleiches Zeitverhalten haben [HYH00]. Zwei Schriftproben sind einander umso ähnlicher, je ähnlicher sich die Funktionen sind. Häufig wird für diese ä hnlichkeitsbewertung um die Funktionen der Enrollment-Schreibproben ein Intervall definiert in dem sich die Funktionswerte einer neuerlichen Schreibprobe aufhalten müssen. In Abbildung 2.3 ist dies exemplarisch für [Abbildung in dieser Leseprobe nicht enthalten] zu sehen. Statt des Begriffs funktionsbasierte Analyse findet sich in der Literatur häufig auch die Bezeichnung strukturelle Analyse.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Online-Rohdaten

Im Gegensatz dazu werden bei der Parameterrepräsentation lokale oder globale Werte untersucht wie die minimale und maximale Schreibgeschwindigkeit, der Schreibweg, die Schreibzeit oder das Höhen-Seiten-Verhältnis von Schreibproben oder Teilen davon. In der Literatur werden eine Vielzahl solcher statistischen Parameter behandelt, die aus Unterschriftsdaten ermittelt und abgeleitet werden können [LBA96]. Zwei Schreibproben werden dann als ähnlich betrachtet, wenn die Parameter der einen ähnlich den Parametern der anderen sind.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Intervall-Band für -Funktion [Vie00]

Im Vergleich zu funktionsbasierten Systemen sind parameterbasierte Systeme algorithmisch häufig einfacher, da nichtlineare Transformationen der Achsen (vor allem der Zeitachse), entfallen. Stattdessen muss lediglich eine Reihe von Merkmalswerten verglichen werden.

2.2.3 Vergleich von Offlineund Online-Verfahren

Wie bereits dargestellt sind die Ausgangsdaten für Offlineund Online-Verfahren verschieden. Während bei den Offline-Verfahren Bildinformationen die Grundlage der weitere Verarbeitung sind, also Helligkeitsoder Farbwerte, verteilt über eine Fläche, nutzen Online-Verfahren zeitdiskrete Werte verschiedener physikalischer Größen, wie die Position und der Druck der Stiftspitze. Die Rohdaten sind also für Offline-Verfahren deutlich umfangreicher, was ihren Speicherbedarf anbelangt.

Es ist evident, dass aus dynamischen Merkmalen sehr leicht statische Merkmale gewonnen werden können. Dazu ist es lediglich nötig, aus den diskreten Abtastpunkten der dynamisch erlangten Ausgangsdaten kontinuierliche Verläufe zu interpolieren und diese in eine Ebene zu projizieren. Soll in den so generierten statischen Rohdaten“, mehr also ” nur die Stiftposition ersichtlich sein, so muss die dargestellte Linienbreite und -färbung den Tintenfluss wiedergeben. Dafür muss die Schreibgeschwindigkeit, der Schreibdruck sowie die Beschaffenheit simulierten Schreiboberfläche berücksichtigt werden.

Der umgekehrte Weg, also die Ermittlung von dynamischen Informationen aus statischen Ausgangsdaten, ist ebenfalls möglich, wie bereits in Abschnitt 2.2.1 kurz angedeutet. In [BCCM93] werden Möglichkeiten aufgezeigt, die Reihenfolge und Richtungen von Linienzügen aus statischen Ausgangsdaten zu ermitteln. [PS00, 64f] schreibt in diesem Zusammenhang: The success of on-line systems makes it attractive to consider develo- ” ping off-line systems that first estimate the trajectory if the writing from off-line data and then use on-line recognition algorithms“.

2.2.4 Handschrifterkennung

Neben den erwähnten Möglichkeiten, die Identität des Urhebers einer Schriftprobe zu ermitteln oder zu verifizieren, sind auch Verfahren entwickelt worden, die versuchen, den Inhalt von handschriftlichen Informationen zu erkennen. Zum einen ist das Ziel, vorhandene handschriftliche Dokumente, etwa Kirchenbücher [Fel00], oder Formulare wie Banküberweisungen, Schecks, Postanschriften auf Briefen [PS00], elektronisch zu verarbeiten.

Zum anderen wird die Handschrifterkennung für stiftbasierte Benutzerschnittstellen zu elektronischen Systemen, wie etwa PDA-Geräten und Tablett-PCs, eingesetzt. Dabei erfolgt die Dateneingabe nicht über eine Tastatur, sondern handschriftlich. Viele Anstrengungen sind unternommen worden, um die Zuverlässigkeit und Erkennungsgenauigkeit solcher Eingabesysteme auf ein Niveau zu bringen, das dem Benutzer eine bequeme Handhabung ermöglicht. Erste Versuche gingen in die Richtung, den Benutzer vereinfachte Alphabete, zum Beispiel Unistroke (siehe Abbildung 2.4) oder Graffiti^[1], lernen zu lassen. Später war auch die Eingabe von gewöhnlichen separaten Buchstaben möglich. Die jüngsten Bestrebungen gehen jedoch dahin, dem Benutzer eine flüssige Eingabe in seiner eigenen Handschrift zu gestatten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Unistroke-Alphabet

2.2.5 Forensische Schriftuntersuchung

Ein weiterer verwandter wissenschaftlicher Forschungsgegenstand neben der biometrischen Handschriftauhthentifikation und -erkennung ist die forensische Schriftuntersuchung.

Die Forensische Schriftuntersuchung beschäftigt sich mit schriftlichen Erzeugnis- ” sen aller Art zur Ermittlung ihrer Echtheit oder Unechtheit, sowie zur Identifizierung des Schrifturhebers bzw. der Herstellungstechnik und der dazu verwendeten Hilfsmittel im Dienste der Rechtsprechung. . .“^[2] Im Gegensatz zur Handschriftidentifikation im Sinne dieser Arbeit beschäftigt sich die Forensik auch und gerade mit der Identifikation von Schrifturhebern anhand beliebiger Schriftinhalte. Der Schriftsachverständige ist beispielsweise in der Lage, einem Täter die Urheberschaft an einem Erpresserbrief nachzuweisen, auch wenn das Vergleichsmaterial nicht den gleichen handschriftlichen Inhalt hat. In den meisten Fällen erfolgt die forensische Untersuchung von Schriftproben nicht automatisiert. Stattdessen kommen hauptsächlich visuelle mikroskopische Untersuchungen unter verschiedensten Lichtund Beleuchtungsverhältnissen zum Einsatz. Dass sich Möglichkeiten und Verfahren der Forensik auch für automatische Handschriftauthentifikationssysteme adaptieren lassen, zeigt [Sch03].

Aspekte der Forensik sowie der Erkennung des Handschriftinhaltes sollen ausdrücklich nicht Bestandteil dieser Arbeit sein. Hier soll ausschließlich die Authentifikation behandelt werden.

2.2.6 Terminologie und Definitionen

Auch wenn an anderer Stelle in der Literatur [Mau01] zwischen Schriftund Schreibdaten unterschieden wird, sollen in dieser Arbeit beide Begriffe synonym verwendet werden. Unter einer Schriftprobe bzw. einem Schreibdatensatz soll die Gesamtheit der verarbeitbaren Daten verstanden werden, die für beispielsweise eine einzelne Unterschrift als Rohdaten der Hardware vorliegen oder aus diesen Rohdaten abgeleitet werden können.

Entsprechend des Inhaltes der Schriftprobe werden in dieser Arbeit fünf so genannte Semantikklassen unterschieden[Vie00]: Unterschrift, vorgegebenes Wort, vorgegebene Ziffernfolge (PIN), Passphrase und Symbol. Wenn nicht aus dem Zusammenhang klar erkennbar ist, dass von einer bestimmten Semantikklasse die Rede ist, wird ” allgemein für beliebige Schriftproben verwendet.

Wie bei allen biometrischen Verfahren wird bei der Nutzung eines Unterschrifterkennungssystems zwischen dem Enrollment und der Authentifikation unterschieden. Unter Enrollment wird das Ermitteln von Referenzdatensätzen verstanden. Dabei registriert sich ein Benutzer einmalig mit mindestens einer Schriftprobe. Für die meisten Systeme sind jedoch mehrere Eingaben nötig. Eingaben sind im Falle der Online- Handschriftauthentifikation Signale (Rohdaten), die mittels Sensoren in speziellen Stiftund/oder Tablettgeräten aufgenommen werden. Aus diesen Rohdaten werden, je nach verwendetem Authentifikationsverfahren, unterschiedliche Merkmale (engl. features) der Handschrift extrahiert. Bei einigen Verfahren und Systemen werden die Enrollmenteingaben einer Qualitätskontrolle unterzogen, die je nach Ausprägung des Systems unterschiedlich komplex sein kann. (Vgl. etwa [VSM01]) Diese Referenzdatensätze können in Abhängigkeit vom konkreten Verfahren des Unterschriftenerkennungssystems zu einem komplexen Enrollmentdatensatz zusammengefasst werden oder separat gespeichert werden. Nach Ermittlung und Qualitätssicherung werden die Referenzdaten gespeichert. Dies geschieht in den meisten Fällen in Datenbanken oder auf Chipkarten.

Die beiden Verfahren der biometrischen Handschrift authentifikation sind die Verifikation und die Identifikation.

Im Falle der Verifikation (1:1) behauptet der Urheber einer Schriftprobe, eine be-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: Überblick: Enrollment, Verifikation, Identifikation

stimmte Identität zu besitzen. Diese Schriftprobe wird mit dem Enrollmentdatensatz dieser behaupteten Identität verglichen. Da in den allerseltensten Fällen zwei biometrische Datensätze genau gleich sind, erfolgen diese Vergleiche, indem ein Abstandsmaß (engl. distance) zwischen den Datensätzen bestimmt und geprüft wird, ob dieser Abstand einen Schwellwert (engl. threshold) nicht überschreitet. Das Resultat einer Verifikation ist die Bestätigung (Akzeptanz) der behaupteten Identität oder die Zurückweisung.

Bei der Identifikation (1:n) ist es das Ziel, den Urheber einer Schriftprobe zu ermitteln. Dazu wird diese Schriftprobe mit den Enrollmentdatensätzen einer Vielzahl von Urhebern verglichen. Das Resultat einer Identifikation ist die Ausgabe der Identität oder die Abweisung für den Fall, dass die Schriftprobe allen bereits vorhandenen Schriftproben zu unähnlich ist. In Abbildung 2.5 ist die generelle Funktionsweise des Enrollmentvorganges sowie der beiden Möglichkeiten der Authentifikation zu sehen.

2.3 Performance und Fehlerraten

Die Qualität oder Leistungsfähingkeit (Performance^[3]) von biometrischen Verfahren bemisst sich an ihren Fehlerraten. Es wird hauptsächlich unterschieden in Fehler vom Typ I und solche vom Typ II [PL89].

Typ-I-Fehler werden auch Falsch-Rückweisungen genannt. Das Verhältnis der fälschlicherweise zurückgewiesenen Authentifizierungsversuche zur Gesamtzahl der Authentifizierungsversuche ist die Falsch-Rückweisungs-Rate (engl. false rejection rate – FRR). Eine hohe FRR stellt in den meisten Fällen kein Sicherheitsproblem dar, jedoch wird ein biometrisches System als unkomfortabel empfunden, wenn es eine hohe Rate an Falschzurückweisungen hat [Bro]. Die FRR eines Systems ist ein persönlicher Wert (personal FRR). Für eine berechtigte Person mit der Identität ist die FRR definiert als:

Abbildung in dieser Leseprobe nicht enthalten

Die Typ-I-Fehlerrate für alle berechtigten Personen ist:

Abbildung in dieser Leseprobe nicht enthalten

Für Verifikationen bedeutet eine Falschabweisung, dass eine berechtigte Person angibt, eine bestimmte Identität zu besitzen und das System feststellt, dass die Übereinstimmung des aktuellen Datensatzes mit dem Referenzdatensatz der Person zu gering ist. Im Falle der Identifikation versteht man unter einer Falschabweisung, dass eine berechtigte Person vom System nicht erkannt wird, also dass die Übereinstimmung des aktuellen Datensatzes zu allen Referenzdatensätzen in der Datenbank zu gering ist.

Fehler vom Typ II werden auch Falschakzeptanz genannt. Von Falschakzeptanz ist die Rede, wenn eine Person vom System als eine andere Person erkannt wird. Das Verhältnis der fälschlicherweise akzeptierten Authentifizierungsversuche zur Gesamtzahl der Authentifizierungsversuche ist die Falsch-Akzeptanz-Rate (engl. false acceptance rate – FAR). Im Gegensatz zur FRR ist eine hohe FAR für ein System sicherheitskritisch, da

Falschakzeptanz, dass Personen sich als jemand anders ausgeben können. ä hnlich der FRR ist die FAR ein persönlicher Wert (personal FAR). Entsprechend ist die FAR für die Person mit der Identität definiert als:

Abbildung in dieser Leseprobe nicht enthalten

Die globale Falsch-Akzeptanzrate für Personen ist:

Abbildung in dieser Leseprobe nicht enthalten

Für die Verifikation ist unter Falschakzeptanz zu verstehen, dass eine Person vorgibt, die Identität (mit ) zu besitzen und das System eine ausreichende Übereinstimmung zwischen dem aktuellen Datensatz der Person und dem Referenzdatensatz der Person feststellt. Falschakzeptanz im Zusammenhang mit der Identifikation bedeutet, dass eine Person, für die im System keine Referenz gespeichert ist, als irgendeine berechtigte Person erkannt wird. Speziell für die Identifikation existiert eine weitere Fehlerart – die Falsch- Identifikations-Rate (engl. false identification rate – FIR). Von einer falschen Identifikation ist die Rede, wenn eine berechtigte Person vom System als eine andere berechtigte Person (mit ) erkannt wird. Also wenn die Übereinstimmung des aktuellen Datensatzes der Person mit dem Referenzdatensatz von größer ist als mit dem von.

Neben diesen Erkennungsfehlern FRR, FAR und FIR existieren unter anderem noch FTE, FTA, FMR und FNMR. Bei der FTE (engl. failure to enroll, auch FER: false enrollment rate) handelt es sich um den Anteil jener Personen, deren Enrollment fehlschlägt. Bei passiven biometrischen Merkmalen bedeutet dies in den meisten Fällen, dass für jene Personen dieses Merkmal (etwa der Fingerabdruck) dauerhaft oder temporär (beispielsweise durch Verletzungen) nicht auswertbar ist.

Die FTA (engl. failure to aquire) gibt an, wieviele bereits enrollte Personen sich auch nach mehrmaligen Versuchen fälschlicherweise vom System abgewiesen werden. Gründe für solche Fehler können die selben sein, die die FTE hervorrufen. Die FTA ist ein Bestanteil der FRR.

FMR beziehungsweise FNMR steht für false match rate beziehungsweise false nonmatch rate. In der Literatur werden zum Teil FMR und FAR sowie FNMR und FRR gleichgesetzt [fvc]. Andere Quellen machen eine Unterscheidung. So definiert [Way99] die FNMR als das Verhältnis der Anzahl fehlgeschlagenen Vergleiche (Distanzbestimmungen) zweier biometrischer Datenproben (Samples) zur Gesamtzahl der Vergleiche. Angenommen, für eine Person liegen als Referenz fünf Enrollmentdatensätze vor. Je nach Implementierung und Ausprägung des biometrischen Systems könnte es für eine erfolgreiche Verifikation hinreichend sein, dass die neuerliche biometrische Datenprobe lediglich zu einem der fünf Enrollmentdatensätze eine hohe ä hnlichkeit aufweist. In diesem Fall würde der Benutzer nicht zurückgewiesen (rejected) werden, jedoch gäbe es vier non-matches. Bei vielen Systemen findet ein solcher Vergleich jedoch dann nicht statt, wenn die Datenprobe keine ausreichende Qualität aufweist. Dieser Fall schlägt sich in der FRR nieder, da die Verifikation negativ verläuft, nicht jedoch in der FNMR, da kein Vergleichsvorgang stattfindet. ä hnlich verhält es sich, wenn die Verifikation einer Person erst nach mehreren Fehlversuchen endgültig fehlschlägt. Dann handelt es sich dabei um nur eine Zurückweisung, jedoch um mehrere non-matches. Analog dazu ist die FMR aufgrund von einzelnen biometrischen Vergleichen, im Gegensatz zu systemabhängigen Gruppen von Vergleichen, definiert. Daraus ergibt sich die Notwendigkeit, bei der Angabe von Falschakzeptanzund Falschzurückweisungsraten die genauen Umstände zu dokumentieren, unter denen eine Authentifikation erfolgt. Also ob beispielsweise im Test die Enrollmentdatensätze einer Person einzeln oder gemeinsam betrachtet werden.

Alle diese Fehlerraten sind abhängig von einem oder mehreren verfahrensabhängigen Schwellwerten. Die Fehlerraten lassen sich als Funktion dieser Schwellwerte graphisch darstellen. In Abbildung 2.6(a) ist dies beispielhaft für FRR und FAR zu erkennen. Es lässt sich in dieser Abbildung gut erkennen, wie mit dem Anstieg der einen Fehlerart die andere sinkt und umgekehrt^[4]. Der idealste Fall, das heißt maximale Separierbarkeit der zwei Klassen Originalschriftproben und Fälschungen, sähe im Diagramm so aus, dass beide Kurven an mindestens einer Stelle den Wert null annehmen. Diese gemeinsame Abhängigkeit von FRR und FAR von den Schwellwerten schafft eine indirekte Abhängigkeit der einzelnen Fehlerraten voneinander. So ist es zum Beispiel möglich, das Verhalten der Falschakzeptanzrate bei Veränderung der Falschrückweisungsrate zu beobachten. Dies ist in Abbildung 2.6(b) zu sehen. Der Punkt, an dem die FAR und die FRR den gleichen Wert annehmen, wird EER (engl. equal error rate) genannt. Bei Darstellungen der Fehlerraten in Abhängigkeit von Schwellwerten entspricht die EER genau dem Schnittpunkt der Kurven. Wenn die Fehler als Funktionswert voneinander dargestellt sind, dann ist die EER der Schnittpunkt der Kurve mit der Hauptdiagonalen. Die EER lässt sich nicht ohne weiteres berechnen oder liegt direkt als Messwert vor. Stattdessen ist sie approximiert herleitbar [Bro].

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.6: FAR-FRR- sowie ROC-Kurven [Bro]

Kapitel 3
Grundlagen und Adaption

In diesem Kapitel wird das der Arbeit zugrunde liegende klassische Verfahren zur ä hnlichkeitsbestimmung von Zeichenketten erklärt: der Levenshtein-Abstand. Um dieses Verfahren für Zwecke der biometrischen Handschriftauthentifikation nutzbar zu machen, wird eine Möglichkeit aufgezeigt, wie handschriftliche Daten in Form von Zeichenketten dargestellt werden können. Schließlich werden spezielle Probleme behandelt, die sich bei der Adaption des Levenshtein-Abstandes für unsere Zwecke ergeben.

3.1 Handschriftliche Eingaben als Zeichenketten

Wie bei allen biometrischen Verfahren ist es auch bei der Handschriftauthentifikation das Ziel, ä hnlichkeiten zwischen verschiedenen Daten biometrischen Ursprungs zu erkennen und zu bewerten. Maße für die ä hnlichkeit von Daten, basierend auf anderen Medien, beispielsweise Zeichenketten, sind seit längerem bekannt. Verwendung finden solche Verfahren bisher beispielsweise zur automatischen Rechtschreibkorrektur, also zum Auffinden von ähnlichen Worten in Datenbanken im Falle eines Fehlers. Auch in der Bioinformatik – vor allem im Bereich der Genetik – werden Verfahren eingesetzt, die einen unscharfen Vergleich von Daten gestatten [GJ01].

Diese Arbeit wird untersuchen, inwieweit sich solche Verfahren für das Vergleichen von dynamischen Unterschriften adaptieren lassen.

[...]

---

^[1] Unistroke ist eine Entwicklung der Firma XEROX und Graffiti eine Entwicklung der Firma Palm Computing.

^[2] Statuten der Gesellschaft für forensische Schriftuntersuchung (GFS): http://www.gfs2000.de/ statut d.htm [Stand 2004-01-04]

^[3] Es soll darunter in diesem Zusammenhang nicht Performance im Sinne einer Verarbeitungsoder Ausführungsgeschwindigkeit eines Systems verstanden werden.

^[4] Welche der Kurven mit steigendem Schwellwert steigt oder fällt ist abhängig von der Art des Schwellwertes, also ob mit der abgetragenen Größe ein ä hnlichkeitsoder ein Unähnlichkeitsmaß dargestellt wird.