Suche in on-line erfassten digitalen Handschriftdokumenten

Inhaltsverzeichnis

Zusammenfassung

Abstract

Danksagung

Tabellenverzeichnis

Abbildungsverzeichnis

Algorithmenverzeichnis

1 Einleitung
1.1 Historische Entwicklung der Schrift
1.2 Überblick über Schrift am Computer
1.3 Ziel dieser Arbeit
1.4 Aufbau dieser Arbeit Verwandte Arbeiten

2 Verwandte Arbeiten
2.1 Fremde Suchansätze
2.1.1 Rubines Algorithmus
2.1.2 ScriptSearch
2.1.3 Scribble Matching
2.1.4 Scribbler
2.1.5 Automatische Indexgenerierung für Handschrift
2.1.6 Word-Spotting nach Jain & Namboodiri
2.1.7 Suche mittels Texterkennung
2.1.8 Stiftbasierte Bildersuche
2.1.9 Zusammenfassung
2.2 Beispielanwendungen des Pen-Computing
2.2.1 Audio Notebook
2.2.2 Interaktive Whiteboards
2.2.3 E-Book- und digitale Notizsysteme
2.2.4 Stiftbasiertes Prototyping
2.2.5 Zusammenfassung

3 Gerätetypen und Datenformate
3.1 Optische Positionsbestimung
3.2 Elektrostatische und elektromagnetische Positionsbestimmung
3.3 Akustische Positionsbestimmung
3.4 Resistive-Film-Technologie
3.5 Elektromechanische Positionsbestimmung
3.6 Dateiformate für On-line Handschriftdaten
3.6.1 JOT
3.6.2 UNIPEN
3.6.3 InkML
3.6.4 Weitere Standards und Datenformate
3.7 Zusammenfassung

4 Aufbau des Systems
4.1 Auswahl der Handschriftgeräte
4.2 Modulbeschreibung

5 Merkmalsgewinnung
5.1 Datenvorverarbeitung
5.1.1 Entfernen doppelter Abtastpunkte
5.1.2 Strokesegmentierung
5.1.3 Neuabtastung der Handschrift
5.2 Gitterbasierte Richtungsmerkmale
5.2.1 Quadratische Gitter
5.2.2 Dreiecksgitter
5.3 Lokale Schriftrichtung
5.4 Lokale Schriftkrümmung
5.5 Lokale Schriftneigung
5.6 Zusammenfassung

6 Suche mit Fehlern
6.1 Ähnlichkeiten von Zeichenketten
6.1.1 Editierabstand
6.1.2 Varianten des Editierabstandes
6.2 Approximative Stringsuche mittels dynamischer Programmierung
6.3 Alternative Suchalgorithmen
6.4 Zusammenfassung

7 Fusion
7.1 Überblick über Biometrie und biometrische Fusion
7.2 Fusionsstrategien der Handschriftsuche
7.2.1 Multi-Sample-Fusion
7.2.2 Multialgorithmische Fusion
7.3 Zusammenfassung

8 Evaluation
8.1 Grundlagen
8.2 Datenbank
8.3 Vorgehen bei der Evaluation
8.3.1 Evaluation der Systemteile ohne Fusion
8.3.2 Evaluation der Fusionsstrategien
8.3.3 Automatische Bestimmung individueller Schwellwerte
8.4 Zusammenfassung

9 Diskussion der Resultate
9.1 Resultate der Suche ohne Fusion
9.1.1 Quadratische Gitter
9.1.2 Dreiecksgitter
9.1.3 Lokale Schriftrichtung
9.1.4 Lokale Schriftkrümmung
9.1.5 Lokale Schriftneigung
9.2 Resultate für Multi-Sample-Fusion
9.2.1 Fusion auf Vergleichsebene
9.2.2 Fusion auf Entscheidungsebene
9.3 Resultate für multialgorithmische Fusion
9.3.1 Fusion auf Merkmalsebene
9.3.2 Fusion auf Vergleichsebene
9.3.3 Fusion auf Entscheidungsebene
9.4 Versuch der automatischen Bestimmung individueller Schwellwerte
9.5 Resultate verwandter Suchverfahren
9.6 Zusammenfassung

10 Fazit und Ausblick
10.1 Fazit
10.2 Erweiterungen und Verbesserungen
10.3 Ausblick

A Notation

B Plan zur Schriftdatenerfassung

C Datenbankschema der Evaluationsumgebung

D Resultate – tabellarisch
D.1 Ohne Fusion
D.2 Multi-Sample-Fusion
D.2.1 Fusion auf Vergleichsebene
D.2.2 Fusion auf Entscheidungsebene
D.3 Multialgorithmische Fusion
D.3.1 Fusion auf Merkmalsebene
D.3.2 Fusion auf Vergleichsebene
D.3.3 Fusion auf Entscheidungsebene

E Resultate – grafisch
E.1 Ohne Fusion
E.2 Multi-Sample-Fusion
E.2.1 Fusion auf Vergleichsebene
E.2.2 Fusion auf Entscheidungsebene
E.3 Multialgorithmische Fusion
E.3.1 Fusion auf Merkmalsebene
E.3.2 Fusion auf Vergleichsebene
E.3.3 Fusion auf Entscheidungsebene

F Zeitaufwand der Merkmalsgewinnung

G Entropie-τEER-Diagramme

Literaturverzeichnis

Sonstige Quellen

Eigene Veröffentlichungen

Index

Zusammenfassung

In dieser Arbeit entwickelt und analysiert der Autor neue Techniken und Verfahren, die es ermöglichen, innerhalb von digital erfassten, handschriftlichen Texten zu suchen. Einen ent-scheidenden Unterschied zu verwandten Arbeiten stellt der Umstand dar, dass für das hier entwickelte Verfahren auf eine inhaltliche, textuelle Erkennung der Handschrift verzichtet wird und stattdessen ausschließlich die geometrische Gestalt des Schriftbildes die Grundlage für die Suche bildet. Dadurch wird es möglich, nicht nur nach handschriftlichen Passagen zu suchen, sondern auch Symbole, Skizzen und Zeichnungen zu berücksichtigen.

Die hier entwickelten Verfahren wurden auf einer eigenen Datenbasis, bestehend aus Hand-schriftdokumenten in verschiedenen Sprachen und von verschiedenen Autoren, experimentell evaluiert. Für die digitale Erfassung dieser Dokumente kamen drei unterschiedliche Stiftge-räte zum Einsatz. Die Vermessung der Stiftbewegungen erfolgt bei jedem dieser Stifte auf-grund eines anderen physikalischen Phänomens. Die Evaluierung ergab Fehlerraten von zum Teil unter 5 % bei der Suche innerhalb der Handschriftdokumente. Zur Erreichung dieser ver-gleichsweise geringen Fehlerraten werden erstmals so genannte Fusionsverfahren verwendet, die auch aus dem Bereich der biometrischen Benutzerauthentifikation bekannt sind.

Die vorliegende Arbeit stellt somit einen Beitrag zu den Forschungsgebieten der Handschrift-verarbeitung und des Dokument-Retrieval dar. Sie greift dabei zurück auf Techniken aus den Bereichen der Handschrifterkennung, der biometrischen Benutzerauthentifikation, dort insbe-sondere der Unterschriftserkennung und der biometrischen Fusionierung, sowie der Textalgo-rithmen, speziell der so genannten unscharfen Suchalgorithmen.

Abstract

In this thesis, we develop and analyze new techniques and methods for searching within di­gitally captured handwritten text. Unlike related approaches, the new method abstains from performing textual recognition. Instead, the searching procedure is based on the geometrical shape of the handwritten text. Thence it is also possible, to search not only for words and phrases but also for drawn symbols and sketches.

The new handwriting retrieval system was experimentally evaluated using a data set of hand­written documents, written by different authors and in different various languages. These documents were digitally captured using three different pen devices with disparate physical techniques for measuring pen movement during the writing process. These evaluations resul­ted in error rates of less than 5 % for retrieval in handwritten documents. To achieve these comparatively low error rates, for the first time we adapt so called fusion techniques from biometric authentication for the handwriting retrieval problem.

This thesis is a contribution to, inter alia, the scientific domains of handwriting processing and document retrieval. It draws on ideas and techniques from the fields of handwriting recog­nition, biometric user authentication, especially signature analysis and biometric fusion, as well as text algorithms, in particular fuzzy string searching.

Danksagung

Diese Dissertation ist während meiner Zeit als Promotionsstipendiat am Institut für Tech-nische und Betriebliche Informationssysteme der Otto-von-Guericke-Universität entstanden. Insbesondere der Arbeitsgruppe Multimedia and Security sowie besonders deren Leiterin, Prof. Jana Dittmann, bin ich zu großem Dank verpflichtet für die Chancen und Möglichkei-ten, aber auch für die Freiheiten, die mir im Rahmen meiner Arbeit gewährt wurden.

Herzlich bedanken möchte ich mich auch bei meinem Betreuer Prof. Claus Vielhauer für sei­ne Geduld und konstruktive Kritik. Seine Erfahrungen, Ideen und Ratschläge waren mir eine große Hilfe während der Arbeit an meiner Dissertation, aber auch darüber hinaus bei meiner Forschung.

Ein besonderer Dank gilt dem von der EU geförderten Network of Excellence SIMILAR (FP6-507609), einerseits für die Finanzierung meines Forschungsvorhabens und andererseits für die Möglichkeit des Austausches mit Wissenschaftlern aus ganz Europa. Dies gewährte mir interessante Einblicke in fremde Forschungsgebiete und bot Chancen für wertvolle Diskus-sionen.

Mein Dank gilt auch Prof. Jean Vanderdonckt von der Université catholique de Louvain sowie Prof. Klaus Tönnies vom Institut für Simulation und Grafik für die freundliche Übernahme der Begutachtung meiner Arbeit.

Bedanken will ich mich auch bei meinem Kollegenkreis am Institut für Technische und Be-triebliche Informationssysteme und hier ganz besonders bei Tobias, Ingolf und Anke für die Diskussionen und ihre Unterstützung beim Verfassen dieser Arbeit. Gleichfalls bin ich denen zu Dank verpflichtet, die mir bei der zum Teil recht zeitraubenden Sammlung von Hand-schriftdaten behilflich gewesen sind.

Schließlich geht ein großer Dank an meine Freundin Susanne Krüger und an meine Familie. Sie unterstützten mich in jeder Hinsicht während der langwierigen Arbeit an meiner Disserta­tion und trugen so maßgeblich zu deren Fertigstellung bei.

Tabellenverzeichnis

2.1 Vergleich der durch verschiedene Verfahren und Algorithmen akzeptierten Stifteingaben

3.1 Übersicht über die in dieser Arbeit verwendeten Gerätetypen sowie ihre tech- nischen Parameter

5.1 Übersicht über die fünf in dieser Arbeit untersuchten Merkmalstypen sowie ihrer Parameter

8.1 Übersicht der Evaluationsdatenbasis

9.1 Evaluationsmaße (P – Precision, R – Recall, F 1 und AUG) und durchschnittli- che Suchdauer (Zeit (ms) pro Dokument) für quadratische Gittermerkmale in Abhängigkeit von der Gitterweite w

9.2 Evaluationsmaße (P – Precision, R – Recall, F 1 und AUG) und durchschnitt- liche Suchdauer für Dreiecksgittermerkmale in Abhängigkeit von der Gitter- weite w

9.3 Evaluationsmaße (P – Precision, R – Recall, F 1 und AUG sowie durchschnitt- liche Suchdauer) für richtungsbasierte Merkmale in Abhängigkeit von der Resamplingweite w für q = 8

9.4 Evaluationsmaße (P – Precision, R – Recall, F 1 und AUG sowie durchschnitt-liche Suchdauer) für richtungsbasierte Merkmale in Abhängigkeit vom Quan- tisierungsgrad q der Richtungsdaten für w = 7

9.5 Evaluationsmaße (P – Precision, R – Recall, F 1 und AUG sowie durchschnitt-liche Suchdauer) für krümmungsbasierte Merkmale in Abhängigkeit von der Resamplingweite w für q = 8

9.6 Evaluationsmaße (P – Precision, R – Recall, F 1 und AUG sowie durchschnittli-che Suchdauer) für krümmungsbasierte Merkmale in Abhängigkeit vom Quan- tisierungsgrad q der Richtungsdaten für w = 10

9.7 Evaluationsmaße (P – Precision, R – Recall, F 1 und AUG) und durchschnitt-liche Suchdauer (Zeit (ms) pro Dokument) für den Merkmalstyp der lokalen Schriftneigung in Abhängigkeit vom Grad q der Quantisierung

9.8 F 1-Werte für quadratische Gittermerkmale bei Multi-Sample-Fusion auf Ver-gleichsebene sowie die Unterschiede zu den F 1-Werten für das System ohneFusion (n = 0)

9.9 F 1-Werte für quadratische Gittermerkmale bei Multi-Sample-Fusion auf Ent- scheidungsebene

9.10 F 1-Werte für die multialgorithmische Fusion auf der Entscheidungsebene so- wie Differenzen gegenüber unfusionierten Quadratgittermerkmalen

9.11 Vergleich verschiedener Suchverfahren hinsichtlich ihrer Precison und ihres

Abbildungsverzeichnis

1.1 Vergleich verschiedener Alphabete

1.2 Illustration der drei Dimensionen stiftbasierter Systeme (Art der Daten, Art der Erfassung, Zeitpunkt der Verarbeitung)

2.1 Merkmalsberechnung nach Dean Rubine

2.2 Textpassage aus einem Beispieldokument für Tests in [JN03]

2.3 Prototyp des Audio-Notebook-Gerätes

2.4 Zwei Beispiele für E-Book-Geräte

3.1 Off-line und on-line Schriftprobe

3.2 SketchPad-System vom Sutherland und Funktionsweise von Lichtgriffeln .

3.3 Memo-Pen – Prototyp, schematischer Aufbau und Sicht der Stiftkamera . .

3.4 Anoto-Technologie – Funktionsweise und Punktanordnung

3.5 Alternative zur Anoto-Technologie nach [Sek98]

3.6 Optisches Stiftgerät i-pen Mouse

3.7 Elektrostatische Bestimmung der Stiftposition beim RAND Tablet

3.8 Tablettgerät für die Digitalisierung von Zeichnungen

3.9 Schematischer Aufbau eines TabletPCs

3.10 Ultraschallbasierte Bestimmung der Stiftposition

3.11 Bestimmung der Stiftposition mittels Acoustic Pulse Recognition

3.12 Bestimmung der Stiftposition mittels Messung des Spannungsabfalls auf einer leitfähigen Oberfläche

3.13 Bestimmung der Stiftposition durch Messung des Spannungsabfalls in einer leitfähigen Flüssigkeit

3.14 Bestimmung der Stiftposition bei Verwendung zweier paralleler leitfähiger Folien

3.15 Aufbau eines Handschriftenerfassungsgerätes mit vier Kraftsensoren unter der Schreiboberfläche sowie vier Beispielsignale dieser Sensoren

3.16 Biometric Smart Pen (BiSP), ausgestattet mit Beschleunigungssensoren zur Messung der Schreibbewegung

3.17 Druckmessstift MechPen

3.18 Detail eines Unterschriftenautomaten

3.19 Fernschreibsystem Telautograph

3.20 Aufbau eines haptischen Interfacegerätes und Einsatz zur Schrifteingabe . .

3.21 Auszug aus einer einfachen UNIPEN-Datei

3.22 Beispiel einer einfachen InkML-Datei sowie die zugehörige grafische Dar- stellung

3.23 Beispiel einer UPX-Datei zur hierarchischen Annotation von InkML-Daten .

3.24 Beispiel einer einfachen WandaML-WInk-Datei

4.1 Schematischer Aufbau des Handschriftsuchsystems

5.1 Schematischer Aufbau des Handschriftsuchsystems

5.2 Signale der horizontalen und vertikalen Stiftbewegung

5.3 Schriftbild der Signale aus Abbildung 5.2

5.4 Vergleich von linearer und polynomieller Interpolation sowie stückweise ku- bischer Splineinterpolation

5.5 Grundidee der Kodierung nach Freeman

5.6 Anwendung der Gitterkodierung nach Freeman auf ein Handschriftdokument

5.7 Unterschiedliche Arten der Gitter-Quantisierung

5.8 Darstellung eines quadratischen Gitters sowie der Quantisierungskreise der Gitterknoten

5.9 Darstellung eines dreieckigen Gitters sowie des Kodierungsschemas der Nach- barschaftsbeziehung von Knoten

5.10 Zusammenhang zwischen Gittern auf Basis von gleichseitigen Dreiecken und Quadraten

5.11 Bestimmung der lokalen Schriftrichtung mittels des Sekantenverfahrens . .

5.12 Bestimmung der lokalen Schriftkrümmung mittels des Sekantenverfahrens (links) sowie des Tangentenverfahrens (rechts)

5.13 Bestimmung der lokalen Schriftkrümmung mittels Krümmungsradius . . .

5.14 Bestimmung der lokalen Schriftneigung

6.1 Schematischer Aufbau des Handschriftsuchsystems

6.2 Zusammenhang zwischen der Alphabetlänge und der durchschnittlichen Ähn- lichkeit zweier Zeichenketten derselben Länge

6.3 Beispiel einer Distanzmatrix für die Suche eines Wortes in einem Text . . .

6.4 Beispiel einer Distanzmatrix D, dargestellt als Graph und durch Farbwerte .

7.1 Verarbeitungsschritte beim biometrischen Enrollment, der Verifikation und der Identifikation

7.2 Die vier diskutierten Ebenen der biometrischen Fusion

7.3 Schematischer Ablauf der Handschriftsuche mit Multi-Sample-Fusion . . .

7.4 Grafische Darstellung der Ähnlichkeitsvektoren bei der Suche mittels Multi- Sample-Fusion

7.5 Fusion der Ähnlichkeitsvektoren aus Abbildung 7.4 mittels Maximum-, Mi- nimum- und Durchschnittsfunktion

7.6 Schematischer Ablauf der Handschriftsuche mit multialgorithmischer Fusion

8.1 Precision, Recall und Fallout als Venn-Diagramme

8.2 Grafische Darstellung der Precision und des Recalls zweier Retrievalsysteme als Funktionen eines Ähnlichkeitsschwellwertes sowie als Precision-Recall- Diagramm

8.3 Berechnung der Fläche unter einer Precision-Recall-Kurve mittels der Trapez- und der Rechteckmethode

8.4 Ground-Truth-Manager Modul des Retrievalsystems

8.5 Angepasstes Systemschema für die Evaluation der Handschriftsuche

8.6 Precision- und Recallwerte, ermittelt für quadratische Gittermerkmale, darge-stellt als Funktionen des Ähnlichkeitsschwellwertes und als Precision-Recall- Diagramm

8.7 Exemplarische Precision- und Recallflächen bei der multialgorithmischen Fu- sion zweier Systeme auf der Entscheidungsebene mittels Mengenvereinigung

8.8 Exemplarische F 1-Fläche bei der multialgorithmischen Fusion zweier Syste- me auf der Entscheidungsebene mittels Mengenvereinigung

8.9 Precision und Recall als Funktion des Ähnlichkeitsschwellwertes, individuell für 13 Personen aus der Testdatenbasis dargestellt

8.10 Zusammenhang zwischen den individuellen Ähnlichkeitsschwellwerten t EER und der Entropie der jeweiligen Merkmalszeichenketten

9.1 Precision-Recall-Diagramm für quadratische Gittermerkmale für den Geräte- typ ioPen

9.2 Precision-Recall-Diagramm für Dreiecksgittermerkmale für den Gerätetyp ioPen

9.3 Precision-Recall-Diagramm für richtungsbasierte Merkmale bei Verwendung von 8 Richtungen (links) sowie bei einer Punktweite von 7 Längeneinheiten (rechts)

9.4 Precision-Recall-Diagramm für Merkmale auf Basis der Schriftkrümung bei Verwendung von 8 Richtungen (links) sowie bei einer Punktweite von 7 Län- geneinheiten (rechts)

9.5 Qualitätsmaß F 1 als Funktion des Quantisierungsparameters q für den Merk- malstyp der lokalen Schriftneigung

9.6 Precision-Recall-Diagramm für quadratische Gittermerkmale für den Geräte- typ ioPen bei Multi-Sample-Fusion auf Vergleichsebene

9.7 Precision-Recall-Diagramm für quadratische Gittermerkmale für den Geräte- typ ioPen bei Multi-Sample-Fusion auf Entscheidungsebene

9.8 Precision-Recall-Diagramm für die multialgorithmische Fusion von Schrift-richtungs- und -krümmungsmerkmalen auf der Merkmalsebene sowie fusions-lose Verwendung von Schriftrichtungsmerkmalen für den Gerätetyp ioPen (w = 10)

9.9 Precision-Recall-Diagramm für die multialgorithmische Fusion von Schrift- richtungs- und -krümmungsmerkmalen auf der Vergleichsebene sowie fusions-lose Verwendung von Schriftrichtungsmerkmalen für den Gerätetyp ioPen (w = 10)

9.10 t EER -Entropie-Streudiagramm für Quadratgittermerkmale mit wg = 7, 10, 20, 30

9.11 Vergleich verschiedener Suchverfahren hinsichtlich ihrer Precison- und Re- callwerte

9.12 Originales Precision-Recall-Diagramm des Verfahrens von Jain und Namboo- diri aus [JN03]

C.1 Schema der Evaluationsdatenbank

Algorithmenverzeichnis

1 Funktion zur Entfernung doppelter Abtastpunkte

2 Extraktion von Quadratgittermerkmalen aus Sequenzen von Abtastpunkten mittels Circular Quantisierung

3 Vereinfachter Bresenham-Linienalgorithmus

4 Verfahren zur Kodierung von Nachbarschaftsbeziehungen in Sequenzen von Gitterpunkten

5 Verfahren zur Kodierung von Nachbarschaftsbeziehungen in Sequenzen von Knotenpunkten in Dreiecksgittern

6 Implementierung der Suche nach einer Zeichenkette r in einer Menge von l Zeichenketten s1 bis sl unter Berücksichtigung des Ähnlichkeitsschwellwertes τ

1 Einleitung

Handwriting is civilization’s casual encephalogram

(Lance Morrow)

In jüngster Zeit gewinnt mit den so genannten TabletPCs eine Klasse von mobilen Computern zunehmend an Bedeutung, welche dem Benutzer die Verwendung von Stiften zur Datenein-gabe ermöglichen. Statt den Computer wie bisher nur mit der gewohnten Kombination aus Tastatur und Maus zu bedienen, können nun insbesondere auch handschriftliche und handge-zeichnete Eingaben vorgenommen werden. Neben diesen TabletPCs existieren weitere Arten von auf Stiften basierenden Computern sowie Computerzubehör, wie etwa PDAs (engl. per­sonal digital assistant), Digitalisiertabletts oder mit speziellen Sensoren ausgestattete papier-basierte Klemmbretter als autonome Geräte.

All diese Geräte gestatten es dem Benutzer, von den Vorteilen der handschriftlichen gegen-über der tastaturbasierten Texterfassung zu profitieren. Insbesondere für Notizen oder Mit-schriften in Diskussionen und ähnlichen Situationen kann die Verwendung von Tastaturen als störend empfunden werden. Auch sind die Möglichkeiten, ad hoc grafische Skizzen anzufer-tigen, mit der Tastatur beschränkt.

Neben den genannten Vorteilen, die stiftbasierte Geräte bieten, existiert eine Reihe von Herausforderungen, die in unterschiedlichem Umfang bereits gelöst wurden, für die zum Teil aber noch keine praktikablen Lösungen existieren. Speziell für die Speicherung und Weiter-gabe handschriftlicher digitaler Dokumente mussten entsprechende Datenformate entwickelt werden, deren allgemeine Verbreitung mangels Standardisierung bislang nicht umfassend ist. Desweiteren sind Techniken der Volltextsuche, wie sie für mit Tastaturen erfasste Dokumente existieren, als Mittel des schnellen Zugriffs innerhalb großer Datenbestände für Handschrift-dokumente bisher kaum vorhanden. Insbesondere dieses zuletzt genannte Problem einer leis-tungsfähigen Volltextsuche für digital erfasste handschriftliche Dokumente ist Gegenstand dieser Arbeit.

1.1 Historische Entwicklung der Schrift

Die Erfindung der Schrift vor etwa fünf- bis sechstausend Jahren versetzte den Menschen in die Lage, Wissen in einfacher Weise aufzubewahren und weiterzugeben ^[1] . Insbesondere in der Verwaltung, etwa der Landwirtschaft in Mesopotamien, kamen frühe Formen der Schrift (Keilschrift) erstmals zum Einsatz, wie archäologische Funde etwa aus Uruk im heutigen Irak belegen.

Aus den figürlichen Darstellungen in den ältesten Schriftsystemen wurden im Laufe der Zeit zuerst abstraktere Zeichen entwickelt, welche anfangs noch für konkrete Worte der jewei-ligen Sprache standen. Später entstanden in vielen Sprachen daraus Zeichensysteme (sowohl Silben- als auch Alphabetschriften), durch welche sich die Lautwerte der Worte ausdrücken ließen. Einerseits verringerte sich auf diese Weise der Vorrat an benötigten und zu erlernen-den Zeichen drastisch (beispielsweise 22 Zeichen des phönizischen Alphabetes im Vergleich zu mehreren tausend ägyptischen Hieroglyphen) [Fau80]. Zum anderen wurde es so leichter möglich, neue und unbekannte Worte sowie beliebige Eigennamen schriftlich zu fixieren.

Neben der Schrift wurden im Laufe der Zeit die Techniken zur Schrifterzeugung verfei-nert und vereinfacht. Während die Keilschrift dadurch ihre typische Form erhielt, dass die Zeichen mit einem Holzgriffel in noch feuchten Ton gedrückt wurden, ging man später da-zu über, Schriftzeichen als Tintenspuren mithilfe von zugespitzten Federkielen auf Papyrus, Pergament oder Papier zu schreiben. Ungefähr im zehnten Jahrhundert wurde mit der chi-nesischen Erfindung des Buchdruckes die massenhafte Vervielfältigung von Schriftstücken ermöglicht [Tsi86]. Dieses Druckverfahren wurde unter anderem durch Johannes Gutenbergs so genannten Mobilletterndruck (Buchdruck mit beweglichen Metall-Lettern) weiter verein-facht. Gewissermaßen als Nachfolger dieser Erfindung kann die moderne Schreibmaschine angesehen werden, deren Idee zumeist Henry Mill (1683-1771) zugeschrieben wird und als deren älteste vermarktete Variante die Skrivekugle des Dänen Hans Rasmus Johan Malling Hansen (1835-1890) ist. Mit den heute allgegenwärtigen Personalcomputern samt zugehö-rigen Druckern als technologische Nachfahren dieser frühen Schreibmaschine existiert eine große Verbreitung von Drucktechnik.

Jedoch, weder die Erfindung der Schreibmaschine noch die flächendeckende Verbreitung von Personalcomputern und Druckern konnten die Handschrift als Mittel der individuellen Schriftkommunikation gänzlich verdrängen. Im Gegenteil werden mit der aktuellen Vermark-tung von stift-basierten PDA-Geräten oder stift-unterstützten Notebooks, so genannten Tablet-PC-Geräten, die Möglichkeiten der Handschrift auch für den Computereinsatz nutzbar ge-macht. Daher ist auch zukünftig eine wissenschaftliche Beschäftigung mit dem Thema Hand-schrift relevant, auch unter dem Gesichtspunkt aktueller technischer Möglichkeiten.

1.2 Überblick über Schrift am Computer

Die Beschäftigung mit Handschrift aus Sicht der Computerwissenschaft hat eine aus heuti-ger Sicht vergleichsweise lange Tradition. Bereits 1956 wurde mit dem RAND Tablet (siehe Abschnitt 3.2) das erste Zusatzgerät für Computer entwickelt, das dem Benutzer die Daten-eingabe mittels Stift ermöglichte. Im Jahr 1957 meldete Thomas L. Dimond seinen Stylator zum Patent an, ein System zur automatischen Erkennung einzelner handgeschriebener Buch-staben [Dim63]. 1962 veröffentlichte L. D. Earnest eine der ersten Arbeiten über die Erken-nung kursiv geschriebener Texteingaben [Ear62]. Im folgenden Jahr entwickelte Ivan Edward Sutherland in seiner Doktorarbeit das SketchPad-System, das eine frühe Form des Lichtgrif- fels war und das es dem Benutzer gestattete, direkt auf einem Bildschirm zu zeichnen [Sut63]. Im Jahr 1966 beschrieb G. F. Groner in [Gro66] ein System auf Basis des RAND Tablet zur Erkennung von Zeichen, Symbolen und Stiftgesten. Bereits zwei Jahre zuvor hatte Teitelman einen ersten trainierbaren Erkennungsalgorithmus für Stiftgesten vorgestellt [Mye96].

Neben diesen Systemen werden für die automatische Verarbeitung von in Papierform vor-liegenden Handschriften seit langem spezielle Verfahren entwickelt. Insbesondere die Erken-nung von Adressen auf Briefen sowie von handschriftlichen Daten in Volkszählungsformu-laren, auf Bankschecks und -überweisungen steht dabei im Vordergrund; im Falle von Bank-formularen kommt neben der textuellen Erkennung der Datenfelder auch die Verifikation der Unterschrift als Ziel hinzu [NR77, MGR+95]. Desweiteren gibt es Ansätze, die automati-schen Erkennungsverfahren auch für die Analyse und Verwaltung historischer Handschriften einzusetzen [GX04, Fel06].

Ein weiterer Bereich der digitalen Analyse handschriftlicher Daten ist die automatische oder computerunterstützte Handschriftforensik, die zum Beispiel die Bestimmung des Urhe-bers handgeschriebener Dokumente auf der Basis charakteristischer Unterschiede der Schrift umfasst [KP89, SHSS07]. Eine gewisse Verwandschaft zu diesem Gebiet der Handschrift-forensik besitzt der Bereich der biometrischen Unterschriftenanalyse zum Zwecke der Benut-zerauthentifikation [LP94, SVD04, Vie06], etwa für Zugangskontrollsysteme.

Dieser exemplarische Überblick über mehr als 50 Jahre der Entwicklung zeigt die Vielfalt der Möglichkeiten sowie die Komplexität der Ziele beim Umgang mit den verschiedensten Arten von Schreibdaten am Computer. Eine gewisse Systematik lässt sich schaffen, wenn fol-gende Fragen betrachtet werden: Auf welche Weise erfolgt die Erfassung der Handschriftda-ten? Um welche Art von Handschriftdaten handelt es sich? Zu welchem Zeitpunkt geschieht die Interpretation der Daten?

Die Art der Erfassung der Handschriftdaten wird klassischerweise unterschieden in off-line und on-line Verfahren. Off-line Verfahren betreffen solche handschriftlichen Daten, die in Form von Bildern der Dokumente vorliegen, welche zumeist mittels Digitalfotografie oder Scannertechnik digitalisiert wurden. Die on-line Verfahren, als Gegensatz zu diesen bildba-sierten Verfahren, beruhen auf der Analyse der Daten der Stiftbewegung. Während also im Falle der off-line Verfahren das Resultat eines Schreibvorgangs zentral ist, liegt der Fokus der on-line Verfahren auf der Entstehung von Schreibdaten.

Die Frage nach der Art der Handschriftdaten beantwortet sich auf unterschiedliche Wei-sen für verschiedene Anwendungen und Systeme. Der Begriff der »Handschriftdaten« soll im Folgenden nicht zu eng gefasst werden; neben textuellen Daten können auch Stiftgesten, gezeichnete Symbole oder Skizzen sowie beispielsweise Unterschriften unterschieden werden.

- Unter textuellen Daten werden normalerweise Buchstaben, Ziffern und Interpunktion verstanden [SNC+95]. Die Art der Eingabe textueller Daten kann weiter unterschieden werden in:

– spezielle, durch den Benutzer zu lernende und möglichst einfach automatisch er-kennbare Alphabete (beispielsweise Unistroke, Graffiti oder EdgeWrite; siehe Ab-bildung 1.1),
– separate Zeicheneingabe mittels Standardalphabet (etwa Graffiti2; für den deut-schen Sprachraum beispielsweise die Schulausgangsschrift), wobei zum Teil die

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1: Vergleich verschiedener Alphabete; links: EdgeWrite [Wob06], Mitte oben: Unistroke [Xerox], Mitte unten: Graffiti und Graffiti2 [Palm], rechts: eine deutsche Schulausgangsschrift

Position der einzelnen Symbole durch Linien oder Kästchen vorgegeben ist, – Kursivschrift (miteinander verbundene Buchstaben in Worten).

- Stiftgesten werden (ähnlich wie Mausgesten) genutzt, um dem Computer Kommandos zu übermitteln. Hierbei kann es sich beispielsweise um das Selektieren oder Löschen von Objekten auf dem Bildschirm durch Einkreisen oder Durchstreichen handeln, aber auch um das Aufrufen einer Hilfe-Funktion eines Programmes oder das Vor- und Zu-rückspringen innerhalb von Hypertextumgebungen durch die entsprechenden Stiftbe-wegungen. Stiftgesten hinterlassen, im Gegensatz zu Textdaten, typischerweise keine Tintenspuren auf dem Bildschirm.^[2]

- Anders als Stiftgesten ist das Ziel von Symbolen und Skizzen zumeist nicht das Auslösen einer Aktion, sondern die Eingabe einer tatsächlichen geometrischen Form, welche in interaktiven Anwendungen auch auf dem Bildschirm erscheinen soll. Die Ziele reichen dabei von der Erkennung linguistischer Zeichen beim Korrekturlesen von Dokumen-ten [Col69, AR99] bis hin zur Interpretation von gezeichneten grafischen Benutzer-oberflächen und der automatischen Generierung des entsprechenden Programmcodes [CSVV07] oder der Interpretation und Simulation gezeichneter elektrischer Schaltkrei-se [Dav07].

- Die Eingabe der Unterschrift erfolgt normalerweise mit dem Ziel, diese mit einer be-reits im System vorhandenen Referenz zu vergleichen und aufgrund des Grades der Ähnlichkeit die Identität des Schreibers zu überprüfen. Neben der Unterschrift können zum Teil auch beliebige Worte, Wortgruppen und Symbole verwendet werden, da hier-bei zumeist nicht der textuelle Inhalt, sondern die geometrische Form und die Art der Schreibausführung (in Hinblick auf den Schreibdruck und die Schreibdynamik) ausge-wertet werden [KHH02, SVD07b].

Die dritte Frage ist die nach dem Zeitpunkt der Verarbeitung der Handschriftdaten. Hier-bei kann unterschieden werden zwischen der unmittelbaren Erkennung für interaktive An-wendungen und der verzögerten Erkennung (immediate recognition vs. deferred recognition [Mey95]). Die unmittelbare Erkennung der Eingaben findet unter anderem bei der Stiftbe-dienung von PDA-Geräten Anwendung. Ein Beispiel für die verzögerte Erkennung ist die automatische Auswertung von handschriftlich ausgefüllten Papierformularen.

Hinsichtlich dieser drei »Dimensionen« (Art der Daten, Art der Erfassung und Zeitpunkt der Verarbeitung) stellen beispielsweise das bereits erwähnte Szenario der Erkennung von Schrift- und Unterschriftsdaten auf Papierformularen einerseits, sowie die Computerbedie-nung mittels Stiftgesten andererseits zwei gegenüberliegende Pole im Spektrum der Mög-lichkeiten und Techniken dar. Zum einen handelt es sich um off-line Text- und Unterschrif-tendaten, die verzögert verarbeitet werden und zum anderen um on-line erfasste Daten, die zum Zwecke der Benutzerinteraktion unmittelbar nach der Eingabe erkannt werden. Ande-re Anwendungen, wie etwa biometrische Login-Systeme auf Basis der Unterschrift oder die nachträgliche Erkennung von, am Computer mittels on-line Techniken erfassten, Handschrift-dokumenten ordnen sich zwischen diesen beiden Polen ein.

Die Abbildung 1.2 versucht den Zusammenhang zwischen den Dimensionen zu veran-schaulichen. Die Eigenschaften möglicher stiftbasierter Systeme sind durch die Position von Quadern dargestellt. Der Fokus der vorliegenden Arbeit richtet sich auf die hervorgehobenen Bereiche, das heißt, auf die verzögerte Verarbeitung von on-line erfassten Text- und Symbo-leingaben.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.2: Illustration der drei Dimensionen stiftbasierter Systeme (Art der Daten, Art der Erfassung, Zeitpunkt der Verarbeitung)

1.3 Ziel dieser Arbeit

Das Thema dieser Arbeit, also die Volltextsuche für digitale Handschriftdokumente, basiert auf on-line erfassten Daten, deren Verarbeitung nicht unmittelbar nach der Erfassung, son-dern verzögert zu einem späteren Zeitpunkt geschieht. Die Daten selbst sind hierbei textueller Natur, jedoch können ohne Veränderungen am System im gleichen Maße auch nicht-textuelle Daten gesucht werden, da die Art der Daten für die in dieser Arbeit untersuchten und entwi-ckelten Algorithmen vollständig transparent sind – es wird lediglich auf Basis geometrischer Formen der Stifteingaben gearbeitet.

Damit grenzt sich diese Arbeit ebenso von der Suche in Handschriftdokumenten auf Papier ab (beispielsweise Handschriftensammlungen in Archiven und Bibliotheken), welche natur-gemäß den Charakter von off-line Daten besitzen, wie auch von den Zielen der klassischen Texterkennung. Gleichwohl wird in dieser Arbeit auf bestimmte Techniken aus dem Gebiet der Texterkennung zurückgegriffen.

Als wissenschaftliche Vorarbeit untersucht der Autor in Kapitel 3 relevante technische Sys-teme und Geräte zur Handschrifterfassung und versucht, diese anhand der ihnen zugrunde liegenden physikalischen Prinzipien und Wirkungsweisen zu unterscheiden, um so eine ent-sprechende Klassifikation zu entwickeln.

Neben der Entwicklung eines Suchsystems für Handschriftdokumente stellt die experimen-telle Evaluation der zugrundeliegenden Algorithmen einen wesentlichen Bestandteil dieser Arbeit dar. Ein weiterer wichtiger Aspekt besteht in dem Versuch, Verfahren der, unter ande-rem aus dem Bereich der Biometrie bekannten, Fusion auf ihre Eignung für die Handschrift-verarbeitung zu untersuchen. Diese Verwendung von Fusionsverfahren zielt darauf ab, die Anzahl der Fehler, welche beispielsweise bei der Suche in zum Teil unsauber geschriebenen Dokumenten auftreten können, zu verringern und somit die Suchergebnisse zu optimieren.

1.4 Aufbau dieser Arbeit

Das Kapitel 2 geht auf verwandte Arbeiten ein und fasst im ersten Teil den Stand der For-schung (engl. state of the art) im Bereich der Suche in on-line Handschriftdokumenten zusam-men. Im zweiten Teil des Kapitels werden Systeme vorgestellt, die auf verschiedene Weisen mit solchen Handschriftdokumenten in Berührung kommen und die mit dem in dieser Arbeit entwickelten Suchverfahren kombiniert werden können.

Kapitel 3 verschafft dem Leser einen Überblick über die möglichen technischen Realisie-rungen der on-line Erfassung von Handschrift. Die verschiedenen Techniken werden hierbei hinsichtlich ihrer physikalischen Wirkungsweise strukturiert. Der zweite Teil dieses Kapitels widmet sich aktuell verfügbaren Datenformaten zur Speicherung und Weitergabe von On-line-Handschriftdaten.

Die Kapitel 4, 5 und 6 beschreiben den globalen Aufbau sowie die eigentlichen Algorith-men des in dieser Arbeit entwickelten Suchsystems und bilden den Kern der vorliegenden Arbeit. Kapitel 4 stellt dabei den globalen Aufbau des Systems vor, Kapitel 5 geht auf die Aspekte der Datenvorverarbeitung sowie die für die Suche nötigen Merkmale ein und im Ka-pitel 6 wird der konkrete Suchalgorithmus präsentiert.

Das Kapitel 7 beschreibt Möglichkeiten zur Verbesserung der Leistungsfähigkeit von Sys-temen aus dem verwandten Gebiet der biometrischen Benutzerauthentifikation durch so ge-nannte Fusionsstrategien, das heißt, Kombinationen verschiedener Einzelsysteme. Basierend auf einer aus der Biometrie bekannten Systematik dieser Fusionsstrategien wird im Folgenden eine Adaption für das eigene Suchsystem diskutiert.

Um die Leistungsfähigkeit des Systems zur Suche in Handschriftdokumenten zu bestimmen und mit der verwandter Systeme zu vergleichen, wurden umfangreiche Tests auf Grundlage einer selbst gesammelten Datenbasis durchgeführt. Das Vorgehen bei dieser Evaluation ist in Kapitel 8 beschrieben. Die Evaluation schließt unter anderem auch die Überprüfung etwaiger Leistungsverbesserungen aufgrund der erwähnten Fusion mit ein.

In Kapitel 9 werden die bei der Evaluation gewonnenen Resultate ausgewertet und unter Hinzunahme der Resultate verwandter Ansätze diskutiert.

Kapitel 10 schließlich fasst die Ergebnisse dieser Arbeit zusammen und gibt einen Ausblick auf zukünftige Entwicklungsmöglichkeiten im durch diese Arbeit berührten Bereich.

2 Verwandte Arbeiten

I have seen the future and it is spelled P-E-N. (Edward N. Yourdon, 1991)

In diesem Kapitel sollen im ersten Abschnitt verschiedene verwandte Arbeiten im Bereich der Suche in Handschriftdaten vorgestellt und vom eigenen, in dieser Arbeit entwickelten, System abgegrenzt werden. Im zweiten Abschnitt liegt der Fokus auf der Präsentation von existieren-den Pen-Computing-Systemen, die bislang über keine explizite Suchfunktion verfügen und die von dem hier entwickelten System profitieren könnten.

2.1 Fremde Suchansätze

In den folgenden Unterabschnitten finden sich einige wesentliche Verfahren aus der Literatur, die in bestimmter Weise mit dem in dieser Arbeit entwickelten System der Handschriftsuche verwandt oder vergleichbar sind. Dabei handelt es sich zum einen um Rubines Algorithmus, ein Verfahren für die Erkennung von Stiftgesten (bestehend aus lediglich einem Stroke) und zum anderen um Verfahren, die explizit für die Suche in handschriftlichen Daten konzipiert sind. Trotz einer gewissenhaften Litraturrecherche durch den Autor kann an dieser Stelle nicht ausgeschlossen werden, dass weitere relevante Verfahren und Ansätze existieren.

2.1.1 Rubines Algorithmus

Große Beachtung erlangte die Arbeit von Dean Rubine über die Wiedererkennung von Stift-oder Mausgesten [Rub91a]: Specifying Gestures by Example. Das Verfahren von Rubine ist in der Lage, aus mehreren Realisierungen derselben Geste^[1] ein Modell zu generieren, mit dem eine Wiedererkennung dieser Geste möglich ist. Hierzu werden für jede Geste die statistischen Merkmale f 1 bis f 13 aus Abbildung 2.1 bestimmt.

Die eigentliche Wiedererkennung einer Geste g anhand ihrer Merkmale f 1 bis f 13 wird dadurch erreicht, dass diese Merkmale mit denen aller C (C ∈ N) dem System bekannten Klassen c ˆ von Gesten verglichen werden. Dabei wird jenes c ˆ bestimmt, welchesv[Abbildung in dieser Leseprobe nicht enthalten] maximiert^[2] mit

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Merkmalsberechnung nach Dean Rubine [Rub91a]

Hierbei sind[Abbildung in dieser Leseprobe nicht enthalten] die Gewichtungen, die im System für die Gestenklasse [Abbildung in dieser Leseprobe nicht enthalten] gelten. Die Bestimmung dieser Gewichte der einzelnen Klassen erfolgt in der so genannten Trai-ningsphase. Sei [Abbildung in dieser Leseprobe nicht enthalten] cei der i -te Merkmalswert [Abbildung in dieser Leseprobe nicht enthalten] der e -ten Beispielrealisierung der Gestenklasse [Abbildung in dieser Leseprobe nicht enthalten] und sei E [Abbildung in dieser Leseprobe nicht enthalten] die Anzahl der Beispiele dieser Klasse [Abbildung in dieser Leseprobe nicht enthalten] . Sei weiterhin [Abbildung in dieser Leseprobe nicht enthalten]i der Mittelwert der i -ten Merkmalswerte der Klasse [Abbildung in dieser Leseprobe nicht enthalten]:

Abbildung in dieser Leseprobe nicht enthalten

Mit diesen Werten wird die Kovarianzmatrix Σ [Abbildung in dieser Leseprobe nicht enthalten] der Klasse [Abbildung in dieser Leseprobe nicht enthalten] bestimmt^[3]:

Abbildung in dieser Leseprobe nicht enthalten

woraus die gemeinsame Kovarianzmatrix Σ aller Klassen abgeschätzt wird:

Abbildung in dieser Leseprobe nicht enthalten

2.1 Fremde Suchansätze

Die Gewichte [Abbildung in dieser Leseprobe nicht enthalten] 13 werden wie folgt berechnet^[4]:

Abbildung in dieser Leseprobe nicht enthalten

Hierbei ist [Abbildung in dieser Leseprobe nicht enthalten] das Inverse der gemeinsamen Kovarianzmatrix aller Klassen.

Rubine gibt in [Rub91a] die Erkennungsgüte seines Systems mit 98 % an bei bis zu 15 ver-schiedene Klassen von Gesten und mindestens 15 Beispielgesten pro Klasse. Bei 30 Klassen mit jeweils 40 Beispielen erhält er 97 % und mit nur 15 Beispielen 96 % korrekte Erkennun-gen.

Dieser bereits 1991 veröffentlichte Algorithmus ist auch heutzutage noch relevant. Dies zeigt sich zum einen an der großen Zahl aktueller Veröffentlichungen, die auf Rubines Al-gorithmus verweisen und zum anderen in seiner weitverbreiteten Verwendung zur Lösung von Problemen der stiftbasierten Mustererkennung [LM01, TBBB02, BC02, Bou02, CMP05, HL06].

2.1.2 ScriptSearch

Der ScriptSearch -Algorithmus wurde von Daniel Lopresti und Andrew Tomkins 1994 in ihrem Aufsatz » On the Searchability of Electronic Ink veröffentlicht [LT94]. Ihr Ziel war unter an-derem die Suche nach handgezeichneten und handgeschriebenen Stifteingaben. Die Idee der Suche nach handgezeichneten Eingaben war es, Dateien auf PDA-Geräten mit Piktogrammen anstelle von Dateinamen zu versehen und die Dateien mittels erneuter Eingabe des jeweiligen Piktogramms automatisch wiederzufinden [LT93]. Die Suche nach handgeschriebenen Stif-teingaben verfolgte das selbe Ziel wie die vorliegende Arbeit: nämlich die benutzerabhängige Suche nach Textstellen mit einem bestimmten Wortvorkommen.

Im Falle des SkriptSearch-Algorithmus erfolgte eine Zerlegung der Texte in so genannte Strokes, die in [LT94] dadurch definiert waren, dass sie durch zwei aufeinanderfolgende ver-tikale Minima der Stiftbewegung begrenzt sind. Für jeden dieser Strokes wurde mittels des Algorithmus von Rubine [Rub91a] ein Merkmalsvektor mit 13 Elementen bestimmt (siehe Abschnitt 2.1.1). Der dadurch definierte 13-dimensionale Vektorraum wurde mittels Vektor-quantisierung in 64 Cluster aufgeteilt und somit jedem Stroke einer dieser Cluster zugewie-sen. Auf Basis der Abfolge von Clusterbezeichnungen aller Strokes eines Piktogramms oder Wortes wurde die Suche dadurch realisiert, dass die Editierabstände (siehe Abschnitt 6.1) zwischen dem gesuchten Piktogramm und denen im System bestimmt wurden. Für die Su-che in Dokumenten, bestehend aus größeren Mengen an Worten, wurde eine Zerlegung der Texte in Zeilen und Worte durchgeführt und die Suche mittels Editierabstand auf Basis der segmentierten Worte durchgeführt.

Die in [LT94] angegebene Genauigkeit des SkriptSearch-Algorithmus bei einer personen-abhängigen Suche lag nur bei etwa 55 bis 60 % sowohl für die Precision, als auch den Recall (siehe Kapitel 8) bei einer Testmenge von nur zwei Personen.

2.1.3 Scribble Matching

Die Suche in Handschriftdaten wurde von Richard Hull, Dave Reynolds und Dipankar Gupta in [HRG94] am Beispiel eines digitalen Adressbuches entwickelt. Die Idee dieses Adressbu-ches ist es, Namenseinträge auch handschriftlich zu speichern (als virtual ink) und auf die Adressbucheinträge mittels erneuten Schreibens des Namens zuzugreifen. Die Bezeichnung Scribble (deut. Gekritzel) bezieht sich auf diese handgeschriebenen Einträge, deren Schreibstil dem Benutzer komplett freigestellt ist.

Für die Suche wurden in [HRG94] drei verschiedene Verfahren verwendet, die testweise auch miteinander kombiniert wurden. Zwei der drei Verfahren basieren darauf, entlang der Spur der Stiftbewegung so genannte Knotenpunkte (engl. knot points) zu definieren, jeden dieser Knotenpunkte entsprechend bestimmter lokaler Eigenschaften zu kodieren und somit für eine handschriftliche Eingabe, etwa in Form eines Wortes, eine Abfolge von Kodezeichen zu erhalten. Die Suche wird realisiert durch einen wiederholten Vergleich des Kodewortes der Sucheingabe mit den Kodeworten der Adressbucheinträge mithilfe des Editierabstandes. Als Knotenpunkte werden in [HRG94] jene Positionen definiert, an denen die Schreibgeschwin-digkeit ein lokales Minimum besitzt.

Das erste der drei Verfahren (syntactic matcher) unterscheidet solche Knotenpunkte, die in Anfangs - oder Endpunkten von Strokes, Spitzen, offenen Kurven, geschlossenen Kurven/Schlei-fen oder an sonstigen Stellen der virtuellen Tintenspur liegen sowie zusätzlich diakritische Zeichen wie i-Punkte. Diese verschiedenen Arten von Knotenpunkten werden weiterhin da-nach unterschieden, ob etwa eine Spitze eher nach oben, unten, links oder rechts weist.

Im zweiten Verfahren (word shape matcher) wird die grobe Form der Worte berücksichtigt, indem Ober- und Unterlängen der Buchstaben an den jeweiligen Stellen bestimmt werden. Dies wird erreicht, indem für jeden Knotenpunkt der relative Abstand zur horizontalen Mit-tellinie des Wortes bestimmt wird. Hierbei wird zusätzlich eine Normalisierung bezüglich des mittleren Abstandes aller Knotenpunkte von dieser Mittellinie vorgenommen.

Das dritte beschriebene Verfahren (elastic matcher) basiert darauf, die ursprünglichen Da-ten der Stiftbewegung durch Neuabtastung der Strokes zu verringern und für jeden dadurch entstehenden Abtastpunkt die relative Höhe h (Verhältnis der y-Koordinate des Punktes zur Höhe der bounding box der Stifteingabe) und den Winkel der Tangente e in diesem Punkt zu bestimmen. Statt einer Kodierung dieser Werte in Form diskreter Kodezeichen werden die kontinuierlichen Werte y und e für den Editierabstand verwendet, dessen Ersetzungsoperation (siehe Abschnitt 6.1) entsprechend angepasst wurde: statt der festen Operationskosten von 1 im Falle der Ersetzung ungleicher Symbole gilt nun die Kostenfunktion m ( y p − yq ) + n ( e p − e q ) (m und n sind hierbei Gewichte, y p, yq, e p und e q sind die Höhen- und Winkelwerte der zu ersetzenden Abtastpunkte).

Für die Kombination der drei einzelnen Verfahren werden die Einzelergebnisse (Editierab-stände) normalisiert zu einem Gesamtergebnis summiert. Getestet wurde das System mit einer Datenbank, bestehend aus 100 Namen in sechs Wiederholungen (aufgezeichnet von insgesamt 33 Personen in drei über mehrere Wochen verteilten Durchgängen). Die Tests mit dieser auf Adressbucheinträge beschränkten Datenbank ergaben Erkennungsraten von 84,4 bis 99,8 %, wobei durch die Kombination der Einzelverfahren jeweils die besten Ergebnisse erzielt wur-den.

2.1.4 Scribbler

Im Jahr 1995 veröffentlichten Alex Poon, Karon Weber und Todd Cass ihren Beitrag Scribbler: A Tool for Searching Digital Ink [PWC95]. Der Suchalgorithmus von Scribbler war eingebet-tet in ein System namens Marquee [WP94] zur stiftbasierten Annotation von Videoaufzeich-nungen. Benutzer von Marquee konnten zu ablaufenden Videofilmen digitale Notizen anfer-tigen, die über eine Synchronisation mit den jeweiligen Zeitpunkten innerhalb der Videofilme verknüpft wurden. Das Ziel war die einfachere Navigation innerhalb der Filme anhand dieser handgeschriebenen Markierungsinformationen. Das System Scribbler sollte das spätere Auf-finden von relevanten Markierungsinformationen ermöglichen, mittels erneuter Stifteingabe durch den Benutzer und einer Ähnlichkeitssuche innerhalb der gespeicherten Annotationen.

Für die Suche wird für die Stiftdaten der Annotationen sowie der Suchanfrage, das heißt, für die Sequenzen von Abtastpunkten, eine Strokesegmentierung sowie für jeden Stroke eine Neuabtastung durchgeführt, mit dem Ziel, die Abstände aufeinanderfolgender Abtastpunkte zu vereinheitlichen. Anschließend werden Gruppen nahe beieinanderliegender Strokes gebil-det, wodurch gewissermaßen eine Wortsegmentierung erreicht wird. Die Sequenz der Abtast-punkte der Suchanfrage wird mit den Sequenzen aller Strokegruppen mittels Dynamic Time Warping verglichen; mithilfe eines Schwellwertes werden die Treffer bestimmt.

Das Verfahren wurde für die Suche nach Text sowie nach Symbolen getestet. Die Suchge-nauigkeit wurde in [PWC95] angegeben mit 75,2 % für einen ersten Test mit Daten von sechs Personen.

2.1.5 Automatische Indexgenerierung für Handschrift

Anders als die zuvor beschriebenen Systeme verfolgt das Verfahren in [UW99] von Shingo Uchihashi und Lynn Wilcox nicht das Ziel, Ähnlichkeiten zwischen handgeschriebenen Daten zu bestimmen oder solche Daten in handschriftlichen Dokumenten zu finden. Vielmehr ist ihr Ziel, in Handschriftdokumenten solche Worte zu bestimmen, deren Vorkommen auf den Seiten des Dokumentes eher selten ist, um damit einen Index zu schaffen, welcher Verknüp-fungen mit den Stellen des jeweiligen Vorkommens im Dokument enthält und somit einen einfachen Zugriff im Dokument ermöglicht.

Nach einer wortweisen Segmentierung der Dokumente erfolgt eine Neuabtastung der Da-ten der Schreibbewegung mit dem Ziel, eine feste Abtastfrequenz zu erlangen (der Zeitabstand zweier aufeinanderfolgender Punkte ist konstant). Für die Abtastpunkte werden der Tangen-tenwinkel 0 an der Schriftkurve, die erste und zweite Ableitung von 0 sowie der Sinus und Cosinus von 0 als Merkmale bestimmt. Mittels dynamischer Programmierung wird auf Basis dieser fünf Merkmale die paarweise Ähnlichkeit aller im Dokument vorkommenden Worte berechnet. Mithilfe hierarchischen Clusterings werden solche Worte zusammengefasst, de-ren Ähnlichkeit einen bestimmten Schwellwert übersteigt. Cluster, die nur eine kleine Anzahl von Worten enthalten, bilden die potentiellen Indexterme. Mittels statistischer Tests wird über-prüft, ob die Verteilung dieser potentiellen Indexterme im gesamten Dokument stark von der Normalverteilung abweicht, was sie zu Indextermen qualifiziert.

Getestet wurde das System mit digitalen handschriftlichen Notizen von drei Personen. Da-zu wurde bei unterschiedlichen Schwellwerten überprüft, wie oft diese Cluster der Indexterme falsche Worte enthielten, also solche, die ungleich waren zu den restlichen Worten eines Clus­ters. Dabei ergaben sich im Durchschnitt Precision- und Recallwerte im Bereich von 40 bis 60 %.

2.1.6 Word-Spotting nach Jain & Namboodiri

Die Forscher A. K. Jain und A. M. Namboodiri beschreiben in [JN03] ein weiteres System für die Wortsuche (engl. word spotting) in handschriftlichen Dokumenten. Es basiert, wie die zuvor beschriebenen Verfahren, darauf, aus den Signalen der Schreibbewegung bestimmte charakteristische Merkmale zu extrahieren und die Wortsuche auf Grundlage dieser Merkmale durchzuführen. Wie bei dem Verfahren von Uchihashi und Wilcox (Abschnitt 2.1.5) erfolgt auch bei Jain und Namboodiri in einem ersten Verabreitungsschritt eine Wortsegmentierung der Handschriftdaten. Der Vergleich zweier handschriftlicher Worte geschieht mittels DTW (dynamic time warping).

Die Evaluierung ihres Systems führten Jain und Namboodiri mit zwei Datenbasen durch, bestehend aus 3.872 Worten, geschrieben von einer Person, sowie 6.672 Worten, geschrie-ben von 10 Personen. In Abbildung 2.2 ist beispielhaft eine Textpassage aus der Datenbasis von Jain und Namboodiri dargestellt. Wie hier zu erkennen ist, sind die einzelnen Textzei-len und die Worte klar voneinander getrennt und damit leicht automatisch segmentierbar. Für die elektronische Erfassung dieser Daten wurde ein Cross-Pad -Gerät benutzt, das aus einem Schreibblock besteht, unter dem sich eine elektromagnetische Sensorfläche befindet, welche die Spitze eines speziellen Stiftes erkennen kann (siehe hierzu auch Abschnitt 3.2). Die Au-toren geben für den besten Fall eine Precision von 93,2 % und einen Recall von 90 % an.

2.1.7 Suche mittels Texterkennung

Einen gänzlich anderen Ansatz für die Suche in handschriftlichen Dokumenten wählten Rus­sel, Perrone et al. in [PRZ02, RPCZ02]. Sie stützten sich auf die Ausgaben einer automati-schen textuellen Erkennung der Stifteingaben. Statt hier jedoch direkt in den, zum Teil feh-lerhaft erkannten, Textdaten nach bestimmten Worten zu suchen, verwendeten sie als Aus-gangsdaten die so genannten N -Best-Listen. Dies sind die vom Erkennungssystem den ein-zelnen handschriftlichen Worten zugeordneten potentiellen Bedeutungen, mitsamt dem jewei-ligen Wert für die Wahrscheinlichkeit. Durch die Verwendung dieser N -Best-Listen werden die Probleme umgangen, die aus den zum Teil sehr hohen Fehlerraten aktueller Handschrif-terkennungsalgorithmen bei unsauberen und schwer lesbaren Handschriften resultieren. Für Einzelwortanfragen besitzt dieses System laut [PRZ02] eine Precision und einen Recall von etwa 70 %. Für die Suche nach Wortgruppen anstelle von einzelnen Worten steigen diese Wer-te in einigen Fällen auf bis etwa 90 %.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Textpassage aus einem Beispieldokument für Tests in [JN03]

2.1.8 Stiftbasierte Bildersuche

Während die zuvor beschriebenen Systeme und Verfahren zumeist eine Form der Suche mit-tels Stifteingaben innerhalb von handgeschriebenen oder -gezeichneten Daten ermöglichen sollen, diskutieren Fonseca et al. in [FBRJ04] ein Verfahren für die stiftbasierte Suche nach vektorbasierten ClipArt-Grafiken. Der Benutzer soll die Möglichkeit haben, mit dem Stift ein Bild zu skizzieren, welches mit einer Datenbank von ClipArt-Grafiken verglichen wird. Die Basis dieser Vergleiche ist die Lagebeziehung (Nachbarschaft oder Einschluss) von Bild-teilen zueinander. Diese Beziehungen der Bildteile werden für jede Grafik als so genannter Topologiegraph (engl. topology graph) beschrieben; die Suche erfolgt durch eine Ähnlich-keitsbestimmung dieser Topologiegraphen.

Ein Verfahren mit sehr ähnlicher Technik, aber für die stiftbasierte Suche nach handgezeich-neten Skizzen beschreiben Leung und Chen in [LC03]. Carduff und Egenhofer beschreiben in [CE07] mit »Geo-Mobile Query-by-Sketch« ein System für die mobile stiftbasierte Suche innerhalb von Geodaten, etwa in Karten. Sie erwähnen ebenfalls die Berücksichtigung der Lagebeziehungen von Objekten innerhalb der gezeichneten Eingaben und der Kartendaten, gehen jedoch nicht näher auf das technisch zugrundeliegende System für die Verarbeitung dieser Daten ein.

2.1.9 Zusammenfassung

Die in diesem Abschnitt vorgestellten Verfahren zur Auswertung von handschriftlichen on­line Daten eignen sich nicht für das in dieser Arbeit entworfene System einer Volltextsuche in handschriftlichen und handgezeichneten Dokumenten. Der Algorithmus von Rubine et-wa erlaubt nur die Wiedererkennung von aus einem einzigen Linienzug (engl. single stroke) bestehenden Stifteingaben und scheidet damit aus für die Suche nach Worten, die beinahe zwangsläufig aus mehreren Linienzügen bestehen. Die Verfahren in den Abschnitten 2.1.2 bis 2.1.6 berücksichtigen im Gegensatz dazu zwar die Verarbeitung kompletter Worte, jedoch basieren sie auf einer strikten Segmentierung dieser Worte. Hierdurch ist es nicht möglich, nach Teilen von Worten (im Deutschen insbesondere nach Teilen von zusammengesetzten Worten) oder Wortgruppen zu suchen. Zudem treten Probleme bei der Segmentierung auto-matisch auf, wenn der Autor eines Dokumentes Worte am Ende einer Zeile trennt; hierdurch entstehen zwei separate Segmente. Verfahren, die auf der Texterkennung beruhen, wie jenes in Abschnitt 2.1.7, sind naturgemäß beschränkt auf die Verarbeitung von textuellen Daten und scheitern an der Erkennung von nicht-textuellen Inhalten, wie etwa Symbolen und Skizzen. Weiterhin sind sie mit dem Problem konfrontiert, dass die Erkennung von Texten außerhalb der Welt der lateinischen, der kyrillischen und der chinesischen Schriftkultur auch heute noch nur mangelhaft unterstützt wird. In Tabelle 2.1 ist eine Übersicht von durch die verschiedenen Verfahren erkennbaren Stifteingaben dargestellt. Es wird deutlich, dass keines der in diesem Abschnitt vorgestellten Verfahren jede mögliche Eingabe verarbeiten kann.

All diesen Problem versucht die vorliegende Arbeit mit der Entwicklung eines Systems zur Handschriftvolltextsuche zu begegenen. Wie die Evaluation des hier entwickelten Systems zeigen wird, gelingt dieser Versuch.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1: Vergleich der durch verschiedene Verfahren und Algorithmen akzeptierten Stift-eingaben

2.2 Beispielanwendungen des Pen-Computing

In diesem Abschnitt sollen Systeme sowie Geräte aus der Literatur vorgestellt werden, die dem Bereich des Pen-Computing zugeordnet werden können und die über keine spezielle Suchfunktionalität verfügen. Diese Systeme sind potentielle Kandidaten für einen Einsatz des in dieser Arbeit entwickelten Suchverfahrens für Handschriftdaten und -dokumente.

2.2.1 Audio Notebook

Das Audio Notebook von Lisa Stifelman [Sti96, Sti97, SAS01] ist ein stiftbasiertes Gerät, welches der Navigation in Audiodaten diente. Die Idee hinter dem Audio Notebook war, dass in Vortragssituationen, bei denen eine Audioaufzeichnung stattfindet, Zuhörer Mitschrif-ten, Notizen oder Kommentare schriftlich festhalten und dazu spezielle Geräte verwenden. Durch eine zeitliche Synchronisierung der dabei aufgezeichneten Audio- und Schreibdaten war es möglich, festzustellen, zu welchem Zeitpunkt der Audioaufzeichnung welche Schreib-daten produziert wurden, und umgekehrt. Damit konnte man durch ein Auswählen bestimmter Schreibdaten an die jeweiligen Stellen der Audioaufzeichnung springen. In Abbildung 2.3 ist ein Prototyp dieses Audio-Notebook-Gerätes dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Prototyp des Audio-Notebook-Gerätes [ Sti97]

Technisch wurde dieses System realisiert, indem sich unter der Schreiboberfläche ein Sen-sor, das Digitalisiertablett (siehe Abschnitt 3.2), befand und zum Schreiben ein spezieller Stift verwendet wurde, dessen Position durch das Digitalisiertablett ermittelt werden konnte. Bei Verwendung mehrerer Blätter für die Mitschriften werden die einzelnen Blätter mit einer Art einfachem Barcodes versehen, welcher durch optische Bauteile im Gerät erkannt und unter-schieden werden.

Ähnliche Handschriftsysteme, die eine Synchronisation zwischen Schreib- und Audio- oder Videodaten verwenden, um dadurch den gezielten Zugriff auf bestimte Daten zu vereinfa- chen, sind etwa das Marquee -System (siehe Abschnitt 2.1.4), Dynomite [WSS97], das Sys­tem von Ozan Cakmakci und François Bérard [CB05] oder der Smartpen der Firma Livescribe [Liv07]. Letzteres Gerät ist eine Umsetzung der Anoto-Technologie (siehe Abschnitt 3.1) und integriert die Funktionalitäten für Audioaufzeichnung und Schreibdatenspeicherung direkt im Stift.

2.2.2 Interaktive Whiteboards

Stiftbasierte Systeme, die für Vorträge oder Präsentationen zunehmend an Bedeutung gewin-nen, sind die so genannten interaktiven elektronischen Whiteboards. Hierbei handelt es sich gewissermaßen um die elektronischen Nachfolger klassischer Kreidetafeln, wobei die Stif-teingaben während des Schreibvorgangs digital erfasst und gespeichert werden können. Ge-schrieben wird hierbei, abhängig vom verwendeten Gerät, entweder a) mit Tintenstiften auf ei-nem klassischen analogen Whiteboard, welches um Sensoren zur Verfolgung der Stiftposition erweitert wird (siehe Abschnitt 3.3), b) mit speziellen elektronischen Stiften auf tafelgroßen Bildschirmen (beispielsweise das Liveboard-System der Firma Xerox [EBG+92]) oder c) auf kleineren Digitalisiertabletts oder TabletPCs, während die Ausgabe mittels Projektor erfolgt.

Während die Systeme der Gruppe (a) lediglich die digitale Erfassung von geschriebenen oder skizzierten Eingaben ermöglichen, ist bei den Geräten der Gruppen (b) und (c) eine echte Interaktion des Benutzers mit dem System möglich. Das bedeutet etwa, dass Präsen-tationsfolien ergänzt oder annotiert werden können. Beispiele für solche Anwendungen sind etwa das Tivoli -System, welches eine Anwendung des Xerox-Liveboard [PMMH93] ist, oder die Systeme E-Chalk [JKRS06], Lecturnity der Firma imc Advanced Learning Solutions und CrePCaR ( Cre ation, P resentation, Ca pture and R eplay of Freehand Writings in e-Lecture Scenarios) [BMO04].

2.2.3 E-Book- und digitale Notizsysteme

Unter E-Book-Geräten werden tragbare Computersysteme verstanden, deren Hauptzweck es ist, digitale Bücher und ähnliche Dokumente zu speichern und dem Benutzer zu präsentieren^[5]. Zumeist verfügen Geräte dieses Typs nicht über vollständige, integrierte Tastaturen, sondern werden mithilfe weniger Tasten sowie insbesondere mittels Stifteingabe bedient. Hierzu zäh-len beispielsweise die Geräte Rocket eBook der Firma NuvoMedia oder iLiad der Firma iRex Technologies (siehe Abbildung 2.4). Verwandte Systeme sind in diesem Rahmen auch Tablet-PCs sowie PDA-Geräte, welche ebenfalls in der Lage sind, dem Benutzer entsprechende di-gitale Dokumente zu präsentieren.

Unter anderem Götze et al. haben in [GSS02a, GSS02b, Göt06] mit dem Intelligent Pen eine Metapher entwickelt, die einen ähnlichen Umgang mit digitalen E-Books ermöglicht, wie der Benutzer dies von klassischen Büchern kennt. Insbesondere die Möglichkeit, digitale Dokumente mit Markierungen, Unterstreichungen oder Notizen zu versehen, sind wichtige Elemente dieser Metapher.

Ähnliche Ansätze wie der Intelligent Pen wurden in der Literatur untersucht, etwa das XLi-bris -System [MPGS99, MPGS01], die Systeme Livenotes und NotePals [Lan99, LD99], das Inkteractors-System [ CTR+08] oder die Webseiten-Annotationssysteme von Ramachandran und Kashi [RK03] sowie von Hiraki et al. [HYS05]. Desweiteren existieren Systeme für die Erfassung von Notizen in digitalen Umgebungen, wie etwa das Virtual Notepad [PTW98], welches für dreidimensionale Virtual-Reality-Umgebungen konzipiert ist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Zwei Beispiele für E-Book-Geräte, links das Rocket eBook [NuvoMedia] und rechts der iLiad [iRex Technologies]

2.2.4 Stiftbasiertes Prototyping

Eine weitere Klasse von Systemen nutzt Stifteingaben für das Entwerfen beispielsweise von Internetauftritten, bestehend aus miteinander vernetzten Webseiten [NLHL03] oder von gra-fischen Benutzerschnittstellen für Computerprogramme [Coy07, CSVV07]. Andere Systeme erlauben die Erkennung und Interpretation von mit dem Stift gezeichneten UML-Diagrammen, analogen elektrischen Schaltkreisen oder chemischen Molekülstrukturen [Dav07]. Einen Über-blick der aktuellen Entwicklung in diesem Bereich liefern [PF07, Ren07]. Viele dieser Syste-me belassen solche Teile der Stifteingaben, die nicht erkannt werden können, unverändert als eine Art von handschriftlichem Kommentar.

2.2.5 Zusammenfassung

Auch wenn das eigentliche Ziel vieler in diesem Abschnitt erwähnten Systeme und Anwen-dungen ein anderes ist, so könnten sie doch von den Möglichkeiten der in dieser Arbeit entwi-ckelten Suchfunktionalität für Handschriftdaten profitieren und wären ideale Kandidaten für einen praktischen Einsatz dieser Technik. So ließe sich die stiftbasierte Navigation in Audi-odaten, wie sie etwa durch das Audio Notebook realisiert wurde, leicht um eine suchbasierte Navigation erweitern. Hierdurch könnte der schnelle Zugriff auf größeren Datenmengen, wie sie im Laufe der Zeit bei konsequentem Einsatz der entsprechenden Technik zwangsläufig an-fallen, verbessert werden. Gleiches gilt auch und gerade für die anderen erwähnten Systeme, wie elektronische Whiteboards, digitale Notizsysteme oder stiftbasierte E-Book-Geräte.

Der Nutzen der Handschriftsuche für die erwähnten Prototypingsysteme aus dem Abschnitt 2.2.4 ist ähnlich. Zum einen könnte nach eventuell vorhandenen handschriftlichen Kommen-taren etwa in handgezeichneten Entwürfen für Benutzerschnittstellen gesucht werden. Zum anderen könnte die Suchfunktion auch für die noch uninterpretierten Eingaben selbst, also beispielsweise für gezeichnete Molekülformen oder Diagramme, verwendet werden.

[...]

---

^[1] A. Meyer erklärt die Schrift zum wichtigsten Kommunikationsmittel überhaupt: Communication is possible only when individuals communicate their ideas and visions by writing them down for other people and for other times and places, pointing out the super-personal nature of culture. [...] Off all the means of cultural exchange, writing is the most specific and precise, as well as the most flexible. [Mey95, S. 47] R. Plamondon schreibt in [Pla95]: Handwriting was invented centuries ago to expand the human memory and to facilitate communication.

^[2] Unter Umständen können auch die Texteingaben mittels der Graffiti-Technik auf PDA-Geräten des Typs Palm-Pilot als Stiftgesten interpretiert werden; eine bestimmte Geste (in Form eines nach unten geöffneten Drei-ecks) dient als Kommando, im Text das Zeichen A einzufügen; zudem wird die Form der Stifteingabe graphisch nicht dargestellt.

^[1] Der Begriff Stiftgeste (oder allgemeiner Geste) soll hier für einen einzelnen Linienzug stehen, welcher beispielsweise mit einem Stift geformt wird. Dabei kann es sich um beliebige Symbole oder Buchstaben handeln, die geschrieben werden können, ohne dabei den Stift abzusetzen.

^[2] Practitioners ofpattern recognition will recognize this classifier [eq. 2.1] as the classical linear discrimina­tor. [Rub91b, S. 53]

^[3]» For convenience in the next step [eq. 2.4], the usual 1 / (E [Abbildung in dieser Leseprobe nicht enthalten]) − 1 factor has not been included in Σ [Abbildung in dieser Leseprobe nicht enthalten]ij « [Rub91a, S. 334]

^[4]» [.. .] it is assumed that all gesture classes are equally likely to occur. The constant term [Abbildung in dieser Leseprobe nicht enthalten]may be adjusted if the a priori probabilities of each gesture class are known in advance. [Rub91b, S. 59]

^[5] Vereinzelt werden unter dem Begriff E-Book bzw. E-Buch die einzelnen Buchdateien anstatt der zu deren Anzeige verwendeten Geräte verstanden.