Otto-von-Guericke-Universität Magdeburg
Fakultät für Informatik
Institut für Technische und Betriebliche Informationssysteme
Arbeitsgruppe Advanced Multimedia and Security

Adaption des Levenshtein-Abstandes zur Online-Handschriftauthentifikation

Sascha Schimke

Inhaltsverzeichnis

Abbildungsverzeichnis ... iii

Tabellenverzeichnis ... iv

1 Einleitung ... 1

2 Biometrie – Überblick ... 3

2.1 Verschiedene biometrische Merkmale ... 3
2.2 Handschrift als biometrisches Merkmal ... 4
2.2.1 Offline-Authentifikation ... 4
2.2.2 Online-Authentifikation ... 6
2.2.3 Vergleich von Offline- und Online-Verfahren ... 8
2.2.4 Handschrifterkennung ... 9
2.2.5 Forensische Schriftuntersuchung ... 10
2.2.6 Terminologie und Definitionen ... 11
2.3 Performance und Fehlerraten ... 12

3 Grundlagen und Adaption ... 17

3.1 Handschriftliche Eingaben als Zeichenketten ... 17
3.2 Levenshtein-Abstand ... 20
3.3 Adaption des Levenshtein-Abstandes ... 23
3.3.1 Längenabhängigkeit ... 23
3.3.2 Kurze Segmente ... 26
3.3.3 Simultanereignisse ... 27
3.3.4 Enrollment und Authentifikation ... 29
3.4 Vergleich mit anderen Verfahren ... 30

4 Tests ... 33

4.1 Ausgangsdaten ... 33
4.2 Voruntersuchung – Gleichzeitigkeit ... 37
4.3 Test-Ziele ... 37
4.4 Erwartungen ... 39
4.5 Tests mit Wacom-Geräten ... 39
4.5.1 Enrollment ... 40
4.5.2 Verifikation ... 40
4.5.3 Identifikation ... 42
4.6 Geräteübergreifende Tests ... 45

5 Ergebnisse und Vergleich mit anderen Verfahren ... 47

5.1 Ergebnisse ... 47
5.2 Vergleichbare Verfahren ... 50
5.2.1 Schriftdatenbank ... 50
5.2.2 Statistische Unterschriftenanalyse ... 51
5.2.3 Strukturelle Unterschriftenanalyse ... 51
5.2.4 Zeit-Frequenz-Analyse von Unterschriften ... 53
5.3 Vergleich ... 54

6 Zusammenfassung und Ausblick ... 55

A Testergebnisse ... 57

A.1 Verifikation – Wacom ... 59
A.2 Identifikation – Wacom ... 61
A.3 Verifikation – geräteübergreifend ... 63
A.4 Identifikation – geräteübergreifend ... 65

Literaturverzeichnis ... 67

Index ... 71

Kapitel 1: Einleitung

Biometrie, Biometrik, 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 Personen- und 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 Finger- und 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 Offline- und 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

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 Hand- oder Unterschriftserkennung lassen sich unterteilen in statische und dynamische Verfahren; auch Offline- bzw. 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.

[...]