Entwicklung eines Benchmarking-Programmes für ein Dokumentenanalysesystem

Jochen Schäfer

Zusammenfassung:

Mit einem Dokumentenanalysesystem können verschieden komplexe Dokumente, die eingescannt wurden, analysiert und erfasst werden. Die fortschreitende Digitalisierung der Geschäftsvorgänge verlangt, dass Dokumente in solcher Form vorliegen, dass Businesssoftware damit umgehen kann. Zur Optimierung des Systems ist es notwendig, objektiv nachvollziehbare Aussagen über die Erkennungsqualität zu treffen. Diese Verfahren werden in dieser Arbeit beschrieben.

Inhalt

1. Einleitung

Ein Dokumentenanalysesystem hat das Ziel, auf Papier vorhandene Informationen elektronisch verfügbar zu machen. Dazu werden Dokumente, die zuvor eingescannt wurden, vom System klassifiziert und relevante Informationen extrahiert. Das Werkzeug, das in dieser Projektarbeit beschrieben werden soll, dient dazu, die korrekte Funktion der Systemkomponenten bei der Entwicklung zu prüfen, sowie Verbesserungen bzw. Verschlechterungen einzelner Komponenten detailiert zu untersuchen. Das Werkzeug soll es weiterhin ermöglichen, innerhalb des Systems objektive Daten über die Qualität der extrahierten Texte zu sammeln. Dabei wird darauf geachtet, dass das System erweiterbar und flexibel bleibt. Das in dieser Arbeit beschriebene Verfahren zur Einschätzung der Erkennungsqualität des Dokumentenanalysesystems soll es zum Beispiel für den Vertrieb einfacher machen, gegenüber Kunden objektive Aussagen über die Erkennungsraten des Systems zu treffen. Dieses ist insbesondere in vertragsrechtlicher Hinsicht wichtig, da bei Nichteinhaltung bestimmter zugesicherter Mindestraten Vertragsstrafen drohen. Ebenso ist es für den Vertrieb wichtig, zukünftige Kunden zu überzeugen. Auch für die Entwicklungsabteilung ist die Kenntnis der Erkennungsraten wichtig, da damit die Schwachstellen des System identifizert und verbessert werden können. Außerdem kann anhand der ermittelten Daten überprüft werden, ob sich das System oder Teile davon verbessert oder verschlechtert haben. Dies erlaubt dem Entwickler des Systems, dieses zu optimieren.

2. Begriffe

In diesem Abschnitt werden einige wichtige Begriffe erklärt, die für das Verständnis der Projektarbeit grundlegend sind.

3. Systembeschreibung

3.1 Das Dokumentenanalysesystem

In diesem Kapitel werden die einzelnen Kompontent der Dokumentenanalysesystems beschrieben. Die Abbildung 1 gibt eine Übersicht des Systems.
Abbildung 1: Systemübersicht
Systemübersicht
Das System besteht aus folgenden Teilen:

3.2 Dokumentendefinitionen

Dokumentendefintionen sind das Ergebnis des Trainings mit dem FormManager (s. Abschnitt 3.1). Jede Dokumentendefinition repräsentiert dabei eine Dokumentenklasse, die alle für die Erkennung notwendigen Informationen über die Klassifikation, die enthaltenen Felder und Feldprüfungen zusammenfasst.

3.2.1 Klassifikation

Für die Klassifikation eines Dokumentes ist es nötig, die Merkmale festzulegen, die für die jeweilige Dokumentenklasse auszeichnend ist. Die in Abschnitt 3.2.4.3 beschriebenen Klassifikationskomponenten FormClass, TableClass und PatternClass können diese Merkmale zur Klassifikation der Dokumente verwenden. Beispielsweise erkennt FormClass Dokumente anhand des Layout. Anhand des spezifischen Layouts eines Steuerformular kann dieses dann als solches erkannt werden.

3.2.2 Felder

Die Felderdefinition legt fest, wo die Felder des Dokumentes zu finden sind. Am einfachsten ist dies für Formulare, da dort die Position der Felder fest ist. Beispielsweise findet man das Adressfeld eines Steuerformular immer (zumindest für ein Jahr) an der gleichen Stelle. Bei Dokumenten mit freier Struktur ist das Positionieren der Felder etwas schwieriger, jedoch bietet das Dokumentenanalysesystem die Möglichkeit, nach Bereichen auf dem Dokument zu suchen, die bestimmten, vom Benutzer festzulegenden Regeln genügen. Möchte man etwa das Datum auf einem Dokument finden, das eine freie Form hat, also kein Formular ist, dann könnte man als Suchmuster ``Datum:'' suchen und das Feld rechts von diesem Text positionieren.

3.2.3 Verbünde

Verbünde schränken die Wertemenge zusammenhängender Felder ein. Dazu werden sogenannte Constraints angegeben (s. Abschnitt 3.2.4.7). Bei einer Adresse z.B. können die Inhalte der Felder durch eine Adressdatenbank abgeglichen werden, um möglichst plausible Werte zu erhalten. Enthält die Datenbank etwa einen Eintrag ``Petra Mustermann'', die Buchstabenerkennung liefert aber ``Peter Mustermann'', wird angenommen, dass der Datenbankeintrag wahrscheinlich der richtige Wert ist (s. Abschnitt 3.2.4.7).

3.2.4 Komponenten des Analysers

3.2.4.1 Vorverarbeitung

3.2.4.2 OCR

Die OCR (engl. Optical Character Recognition) erkennt die einzelnen Buchstaben der Wortsegmente, die bei der Segmentierung erzeugt wurden. Dabei wird ein Graph mit möglichen Alternativen erzeugt. Jeder Knoten repräsentiert hierbei ein Segment. Ein Knoten beinhaltet die einzelnen Alternativen für dieses Segment mit einer Wahrscheinlichkeit, dass die jeweiligen Alternative die Richtige ist. Beispielsweise werden die Zeichen für Eins (``1'') und für ein kleines L (``l'') oft sehr ähnlich (manchmal sogar gleich) dargestellt. Im OCR-Graph würde in einem Knoten beide Alternativen dargestellt. Außerdem enthält der OCR-Graph Segmentierungsalternativen. Bei dem Wort ``Otto'' beispielsweise könnte die OCR einen Knoten für das Segemnt ``tt'' und einen Knoten für das Segment ``H'' erzeugen. Die Kanten an diesen Knoten haben ihrerseits Gewichte.
Abbildung 2: Beispiel für einen OCR-Graph
OCR-Graph

3.2.4.3 Dokumentenklassifikation

Die Dokumentenklassifikation versucht den Typ des Dokuments und die Anzahl der Seiten zu erkennen. Dabei gibt es drei Komponenten:

3.2.4.4 Adresslocalizer/Adressplitter

Der Adresslocalizer/Adressplitter sucht auf dem Dokument Adressen und zerteilt sie in Vorname, Name etc.

3.2.4.5 Pattern Matcher

Der PatternMatcher extrahiert anhand von reguläre Ausdrücken Informationen aus dem Dokument.

3.2.4.6 Table Analyzer

Der Table Analyser extrahiert in einer Tabelle die enthaltenen Tabellenzellenfelder.

3.2.4.7 Improver

Bei der Extraktion von Informationen aus Dokumenten hat man das Problem, ob und wieweit man den Ergebnissen einer OCR vertrauen kann. Insbesondere sind die Ergebnisse verschiedener OCR-Engines auf dem gleichem Dokument oft sehr unterschiedlich. Daher wird in der Improver-Komponente, die die Ergebnisse der verwendeten OCR entgegennimmt, das Konzept des Constraint3.1 Programming (CP) zur Kontrolle und Verbesserung der OCR-Ergebnisse eines Verbundes benutzt. Die OCR liefert wie oben beschrieben (Abschnitt 3.2.4.2) einen OCR-Graphen mit den möglichen Ergebnissen. Für eine Aussage über die Erkennungsqualität kann man sich jedoch nicht auf diese Ergebnisse verlassen. Eine bessere Aussage lässt sich treffen, wenn man Wissen über den Kontext eines Dokumentes ausnutzt. Eine Arztrechnung etwa enthält mit sehr grosser Wahrscheinlichkeit die Patientendaten, eine oder mehrere Diagnosen und eine Tabelle mit den abzurechnenden Arzttätigkeiten sowie die Summe aller Kosten. Hier kennt man die GOÄ (Gebührenordnung Ärzte), die die Kostenschlüssel und die erlaubten Kombination u.ä. festlegt. Man kann über ein mathematisches Constraint die Einzelbeträge und dann die Summe geprüft und gegebenenfalls korrigiert werden. Eine andere Möglichkeit, CP zu nutzen, ist die Benutzung von Datenbanken. Hier werden Datenbankeinträge als Relationen zwischen den entsprechenden Feldern angesehen. Bei einer Adresse beispielsweise kann das OCR-Ergebnis mit einer Kundendatenbank abgeglichen werden, oder der Ort mit der Postleitzahl. Es lässt sich zwar nicht immer ein eindeutiges Ergebnis finden, doch mit einer Heuristik wird das wahrscheinlichste Ergebnis ausgewählt. Hier zeigt sich wieder ein Problem bei der Festlegung der Ground-Truth: Bei dem obigen Beispiel mit einer Arztrechnung könnte ein Fehler in dem Originaldokument vorhanden sein, etwa ein Rechenfehler. Hier ist die Frage zu stellen, welche Werte für die Ground-Truth zu wählen sind, denn man hat in diesem Beispiel zwei Möglichkeiten. Erstens kann man einen Ansatz verfolgen, der die buchstäbliche Genauigkeit der Erkennung voraussetzt, also ist der Fehler ``korrekt'' und wird als Ground-Truth angesehen. Andererseits kann man festlegen, dass das was gemeint war, also die korrekte Tabelle, die Ground-Truth sein soll. Da der Improver erheblich bessere Erkennungsraten liefert als eine reine OCR-Erkennung, und da es das Ziel ist, das gesamte System zu optimieren, wird im folgenden von letzteren Ansatz ausgegangen.

3.3 Verifier

Der Verifier dient im Rahmen dieser Projektarbeit zur Erfassung der Ground-Truth. Jedoch ist es nicht immer sinnvoll, alle möglichen Verfahren und Komponenten zu testen. Beispielsweise ist die Verdrehung des Bildes nur schwer als Ground-Truth festzulegen, da die Auswirkung einer kleinen Abweichung von der Ground-Truth nicht unbedingt grössere Auswirkungen auf die Qualtität haben muss. Dies kann jedoch nur im Rahmen der Fähigkeiten des Verifier geschehen. Da der Verifier z.Zt. beispielsweise keine Änderung der Skalierung oder Verdrehung (Skew) des Seitenbildes eines Dokument erlaubt, können diese Daten nur manuell geändert werden bzw. müssten durch ein spezielles Programm erstellt werden. Für diese Arbeit wurde deshalb festgelegt, dass nur solche Daten getestet werden sollen, die auch im Verifier korrigierbar sind.

4. Konzepte

4.1 Ziel

Das Ziel dieser Projektarbeit ist es, ein System zum Benchmarking zu entwickeln und zu implementieren. Dabei sollen folgende Bedingungen gelten: In dieser Arbeit werden nur die drei folgenden Datengruppen erhoben:

4.2 Geeignete Daten

Der Ansatz für das Statistikprogramm läßt die Erhebung aller während der Analyse erhobenen Daten zwar grundsätzlich zu, es sprechen jedoch verschiedene Gründe dagegen:
  1. Der Speicheraufwand für jedes Feld scheint zwar gering zu sein, aber durch die große Anzahl der Felder eines Bildstapels kann der gebrauchte Speicherplatz schnell größere Mengen annehmen.
  2. Jedes Datum, das zu Daten hinzugefügt wird, vergrößert den Wartungsaufwand. Ein wichtiger Aspekt bei der Auswahl ist, dass die Wartbarkeit stark von der Anzahl der zu bearbeitenden Daten abhängt. Die Abhängigkeiten zwischen den einzelnen Daten werden komplexer, je mehr Daten vorhanden sind. Dies führt bei Änderung der Semantik eines Datums zu erheblichen Problemen. Diese Problematik lässt sich nicht immer vermeiden, denn notwendige Verhaltensänderungen kommen immer wieder vor, um das eigentliche Produkt zu verbessern. Komplexe Abhängigkeiten verschlimmern jedoch die Situation.
  3. Zu den einzelnen Daten muss jeweils Ground-Truth erhoben werden. Dies soll einerseits wie schon erwähnt möglichst mit dem Verifier geschehen. Andererseits sind für manche Daten, wie z.B. der Verdrehung des gescannten Dokuments, keine eindeutige oder vernünftige Ground-Truth festzulegen. Bei der Verdrehung kommt es zum Beispiel auf geringe Abweichung nicht an, jedoch ist es schwer für alle Dokumente ein generelles Intervall für die Ground-Truth anzugeben.
Diese Aspekte erfordern eine sorgfältige Auswahl der benötigten Daten. Die Beschränkung auf die Erfassung der Ground-Truth mit dem Verifier schränkt die zu verwendenden Daten stark ein, denn mit dem Verifier kann nur die Klassifikation, der Inhalt von Feldern und Tabellen verändert werden. Daher werden nur Klassifikations-, Feld- und Tabellenvergleiche durchgeführt und in dieser Arbeit beschrieben4.2. Andere Analyseschritte, wie die Segmentierung werden hierbei implizit getestet, da die Korrektheit der Analyse die korrekte Ausführung der entsprechenden Analyseschritte voraussetzt. Es hat sich jedoch gezeigt, dass die mit dem Verifier erfassbaren Daten durchaus reichen, um brauchbare Ergebnisse zu erhalten.

4.3 Vorgehen bei der Erfassung von Ground-Truth und Vergleichsdaten

4.3.1 Erzeugung der Statistikdaten

Sowohl die Ground-Truth-Objekte als auch die damit zu vergleichenden Objekte (im folgenden Vergleichsobjekte genannt), werden von der Extraktion erzeugt. Die Extraktion erhält vom Programm die verfügbaren Bildstapel, durchläuft die Dokumente dieser Bildstapel und erzeugt die entsprechenden Dokumentenobjekte. Für jedes Dokument werden dann die Felder und die Seiten durchlaufen und wiederum die entsprechenden Statistikobjekte erzeugt. Eine solche Liste von Dokumentenobjekten wird für jeden Bildstapel erzeugt. Das Programm speichert dann die Statistikdaten stapelweise in Textdateien. Der Name der Textdatei setzt sich dabei aus dem Präfix ''GT'' für Ground-Truth-Daten bzw. ''Cmp'' für Vergleichsdaten, der Id der Bildstapel und der Dateiendung ''.txt'' zusammen. Beispielsweise würden die Ground-Truth-Daten eines Bildstapel mit der Id ''TestDocs'' in der Datei ''GTTestDocs.txt'' abgespeichert. Der Präfix ist für das Wiedereinlesen der Statistikdaten insofern wichtig, als dass das Programm mit dem Muster ''GT*.txt'' bzw. ''Cmp*.txt'' nach Daten für die Bildstapel sucht.

4.3.2 Erstellung der Ground-Truth

Dazu wird für die gewünschten Dokumente ein Analysevorgang durchgeführt. Dabei ist zu beachten, dass die Dokumente zu den gleichen Bildstapeln zusammengefasst werden, wie sie später analysiert werden, da das Statistiktool nur Dokumente im gleichen Bildstapel vergleicht. Desweiteren müssen die Bild-IDs der Dokumente gleich sein, da das Statistiktool diese zur Zuordnung der einzelnen Seiten zueinander benützt. Ist die Analyse erfolgt, müssen die Daten mit dem Verifier überprüft werden. Hier ist besondere Sorgfalt nötig, da die hier erzeugten Daten bei späteren Vergleichen als die wahren Feldwerte angesehen werden. Falsche Werte in der Ground-Truth führen also bei späteren Vergleichen zu falschen Ergebnissen (s. Abschnitt 4.4). Hier hat sich das Vier-Augen-Prinzip bewährt: Die Verifikation wird von zwei Personen durchgeführt und die Ergebnisse miteinander verglichen. Die Unterschiede werden dann aufgelöst und diese Daten als Ground-Truth übernommen. Die vom Verifier in der Systemdatenbank abgelegten Daten werden jetzt vom Statistiktool eingelesen und wie oben beschrieben (s. Abschnitt 4.3.1) in das eigene Datenformat umgewandelt. Werte, die der Verifier nicht ändern kann, die aber durch den Analyser nicht korrekt erzeugt wurden, müssen hier von Hand nachkorrigiert werden.
Abbildung 3: Ablauf der Datenerzeugung
Ablauf

4.3.3 Erzeugung der Vergleichsdaten

Zum Vergleich der Ground-Truth mit Analyseergebnissen werden die Analyseergebnisse direkt aus dem Analyser vom Statistiktool eingelesen und in das eigene Format umgewandelt. Jetzt können Ground-Truth und Analyseergebnisse miteinander verglichen werden (s. Abschnitt 5.3.1). Das Statistiktool erzeugt nun die Dateien mit den Ergebnissen und stellt sie dar (s. Abbildung 11).

4.4 Zu vergleichende Daten

daten Im folgenden Abschnitt wird häufig von ``Dokumentenvergleich'' die Rede sein. Gemeint ist nicht der Vergleich zwischen verschiedenen Dokumenten, sondern immer ein Vergleich zwischen Ground-Truth und Analyseergebnis eines Dokumentes. Um falsche Vergleichsergebnisse zu vermeiden, wurde eine ``defensive'' Strategie gewählt. Dies bedeutet, dass es vorgezogen wurde, einen Vergleich abzubrechen, wenn eine unsichere Situation entsteht. Beispielsweise würde eine Weiterführung des Vergleichs bei falscher Klassifikation zu viele falsch erkannte Felder ergeben. Dies würde die Fehlerstatistik unnötig verschlechtern und den Fehlergrund verschleieren.

4.4.1 Klassifikation

Damit die Klassifikation eines Dokumentes mit seiner Ground-Truth übereinstimmt, müssen die folgenden Bedingungen gelten:

4.4.2 Felder

Der Vergleich von Feldern besteht aus zwei Teilen, dem OCR-Vergleich und dem Vergleich des Analyseergebnisses. Der OCR-Vergleich vergleicht das Ergebnis der OCR mit der Ground-Truth. Da die Ground-Truth jedoch auf einen Vergleich mit dem Analyseergebnis, also dem Ergebnis des Improver, abgestimmt ist, ist die Aussage dieses Vergleichs eingeschränkt. Betrachten wir im folgenden den Vergleich eines Betragsfeld und nehmen an, dass auf dem Original ``120,00'' steht. Um das gesetzte Ziel, das System zu optimieren, erreichen zu können, muss als Ground-Truth für dieses Feld ``120.00'' angenommen werden. Dies ist wegen des Improvers nötig, der automatisch Betragswerte in die anglikanische Notation, also ein Dezimalpunkt statt eines Dezimalkommas, konvertiert. Der wichtigere Vergleich für die Optimierung ist der zwischen Ground-Truth und Analyseergebnis. Beide Vergleich werden durch den gleichen Algorithmus durchgeführt. Dabei kommt das zu definierende Ähnlichkeitsmaß (s. Abschnitt 5.2) zum Einsatz. Untersucht werden hierbei normale Felder und Felder aus Tabellen (s. nächsten Abschnitt).

4.4.3 Tabellen

Zuerst wird die Dimension der Tabelle, d.h. die Anzahl der Zeilen und Spalten, verglichen. Sind die Dimensionen bei Analyseergebnis und Ground-Truth gleich, so wird davon ausgegangen, dass die Analyse des Dokumentes die Tabelle korrekt erkannt hat. In diesem Fall werden die einzelnen Tabellenzellen direkt verglichen, also die Zelle an der Position (i,j) aus dem Analyseergebnis wird mit der Zelle an der gleichen Position in der Ground-Truth verglichen. Dabei wird wie im vorherigen Abschnitt beschrieben vorgegangen. Sind die Dimensionen nicht gleich, wird versucht mit Hilfe des noch folgenden Ähnlichkeitsmasses für Tabellen (s. Abschnitt 5.2.3) ähnliche Tabellenzeilen zu identifizieren und dann die enthaltenen Zellen zu vergleichen. Dies wird jedoch nur durchgeführt, wenn die Anzahl der Spalten gleich ist. Ansonsten wird der Vergleich für diese Tabelle abgebrochen.

4.4.4 Tabellendimension

Dieser Vergleich dient nur der Information, ob die Dimension der untersuchten Tabelle von der Ground-Truth abweicht. Dies ist wichtig, da diese Information über die Auswahl des Vergleichs der Tabelle entscheidet, wie im vorherigen Abschnitt beschrieben.

5. Realisierung

5.1 Ein- und Ausgabe der Programmdaten

5.1.1 Erzeugung der Statistikdaten

statdate Sowohl die Ground-Truth-Objekte als auch die damit zu vergleichenden Objekte (im folgenden Vergleichsobjekte genannt), werden von der Klasse statExtraction, wie in Abschnitt 4.3.1 beschrieben, erzeugt.

5.1.2 Dateiformat der Statistikdaten

Die Daten werden in der Textdatei wie folgt gespeichert: In einer solchen Zeilen sind ''.'' und ''='' Sonderzeichen, deren Vorkommen im Dokumentname, Seitenname, Attributname oder Wert durch ''\.'' und ''\='' ersetzt werden.

5.1.2.1 Einlesen der Daten

Beim Einlesen wird die gesamte Datei zeilenweise eingelesen und analysiert. Dabei wird ein temporärer Baum erzeugt (s. Abbildung 4).
Abbildung 4: Baumstruktur zum Einlesen von Statistikobjekten
Baumstruktur
Dieser ermöglicht es die Objekte so zu erzeugen, dass fehlende Attribute in der Datei trotzdem eingelesen werden können, da die Blätter des Baumes als Attribute der übergeordneten Knoten angesehen werden. Beim Einlesen eines Attributs werden dessen Name sowie der Name der dazugehörigen Objekts als Suchkriterien angegeben. Ist das Attribut im Baum nicht vorhanden, wird ein Standardwert für den Datentyp des Attributs zurückgegeben. Überflüssige Attribute werden so einfach ignoriert. Somit ist das Programm nur beim Einlesen der Daten aus den Datenbanken auf deren Versionsstand des Binärformats angewiesen. Dies vereinfacht die Weiterentwicklung des Statistiktools sehr, da nicht bei jeder Änderung der Datenstrukturen die Ground-Truth von neuem erzeugt werden muss. Hierbei ist jedoch zu beachten, dass die Attributte ''ClassId'', ''Name'' und ''isGT'' vorhanden sein müssen, um die korrekte Erzeugung der Objekte zu gewährleisten. Das folgende Beispiel zeigt ein minimales Dokument:
Dokument.ClassID=Document
Dokument.Name=Dokument
Dokument.isGT=1
Mehrfachnennungen eines Attributs sind erlaubt und können als Liste gelesen werden. Wird das Attribut jedoch als einzelner Wert eingelesen, wird als Wert das letzte Vorkommen des Attributs zurückgegeben. Das Format ist zwar unabhängig vom Vorhandensein bestimmter Attribute oder Werte eines Objektes, jedoch können Änderungen der Semantik von Attributen nicht durch das Programm abgefangen werden. Dazu muss jeweils ein Konvertierungsprogramm erstellt werden, dass ältere Daten in die gewünschte Form bringt. Eine andere Möglichkeit wäre es das Analyseprogramm so zu ändern, dass es die Formate erkennt und entsprechend reagiert.

5.2 Levenshtein-Maß für Felder

5.2.1 Einleitung

Dieses Maß wurde nach dem dem russischen Wissenschaftler Wladimir Levenshtein benannt, der den Algorithmus 1965 entwickelt hatte [5]. Das Levenshtein-Maß, auch Editierabstand genannt, wird überall dort gebraucht, wo es nicht ausreicht zu wissen, ob zwei Worte5.1 gleich ist. Beispiele für Anwendungen sind Spracherkennung, DNA-Analyse und Rechtschreibprüfung [5] ( Literatur: [2], [3], [4], [5], [6]).

5.2.2 Implementierung

Der Levenshtein-Algorithmus liefert einen Wert zurück, der ein Maß der Ähnlichkeit zweier Zeichenketten angibt. Die Definition eines Maßes verlangt eine Normierung, so dass hier zunächst der absolute Abstand der beiden Zeichenketten bestimmt und durch den größeren Wert der beiden Zeichenkettenlängen geteilt wird. Dies ergibt den relativen Abstand d der Zeichenketten. Die Ähnlichkeit s ist dann s = 1 - d. Der absolute Abstand zweier Zeichenketten ist hier der kleinste Weg, der benötigt wird, um durch die Operationen Einfügen, Löschen und Vertauschen mit den geringsten Kosten von der ersten Zeichenkette zur zweiten Zeichenkette zu gelangen. Die Operationen werden dabei gewichtet, d.h. die Kosten für eine Operation werden berücksichtigt. Beispielswiese könnte das Einfügen günstiger als Löschen sein, also könnten die Kosten für Einfügen sein und für Löschen . Dies soll an folgendem Beispiel verdeutlicht werden: Enthalte s1 die Zeichenkette JOCHEN und s2 JOACHIM. Wir nehmen bei diesem Beispiel der Einfachheit an, dass die Kosten für alle Operation gleich ist. Der absolute Abstand kann dann aus der Tabelle 1 an der rechten, unteren Ecke abgelesen werden abgelesen werden und ist.
Tabelle 1: Beispiel 1 Levenshtein-Abstand
  ε J O A C H I M
ε 0 ¬ 1 2 3 4 5 6 7
J 1 0 ¬ 1 2 3 4 5 6
O 2 1 0 ¬ 1 2 3 4 5
C 3 2 1 1 → 1 ¬ 2 3 4
H 4 3 2 2 2 1 ¬ 2 3
E 5 4 3 3 3 2 2 ¬ 3
N 6 5 4 4 4 3 3
3
Dieses Ergebnis wird durch geteilt und ergibt eine Ähnlichkeit von s = 1 - (3/7) = 1 - 0,43 = 0,57. Man erkennt anhand der Tabelle 2, dass es durchaus mehrere Möglichkeiten gibt, einen kürzesten Weg mit den geringsten Kosten zu finden.
Tabelle 2: Beispiel 2 Levenshtein-Abstand
  ε J O A C H I M
ε 0 ¬ 1 2 3 4 5 6 7
J 1 0 ¬ 1 2 3 4 5 6
O 2 1 0 → 1 ¬ 2 3 4 5
C 3 2 1 1 1 ¬ 2 3 4
H 4 3 2 2 2 1 ¬ 2 3
E 5 4 3 3 3 2 2 ¬ 3
N 6 5 4 4 4 3 3
3
Das Ergebnis des Levenshtein-Maß selbst ist trotz der Möglichkeit von mehreren kürzesten Pfaden eindeutig, so dass die Auswahl des Pfades keine Auswirkung auf das Ergebnis des Algorithmus hat.

5.2.3 Erweitertes Levenshtein-Maß für Tabellen

Oben wurde ein Levenshtein-Maß auf Zeichenketten angegeben. Man kann nun analog einen Levenshtein auf Listen von Zeichenketten und auf Listen davon (also Tabellen) definieren, denn eine Zeichenkette ist ja eine Liste von Zeichen. Dies führte zu einer Implementierung des Levenshtein-Algorithmus in einer Template-Klasse, die dann entsprechend für Zeichenketten, Listen und Tabellen instantiiert wurde. Zum Berechnung der Distanz zwischen zwei Elementen wird wiederum das Levenshtein-Maß für den entsprechenden Elementtyp aufgerufen. Um die Klasse flexibel zu halten, werden auf einem Stack die Parameter für jedes Levenshtein-Maß plaziert. Neben den Kosten der Editieroperationen kann noch angegeben werden, ob bei der Distanz zweier Elemente auf Gleichheit geprüft werden soll oder das Levenshtein-Maß des Elementtyps herangezogen werden soll. Desweiteren ist es möglich, für Zeichenketten eine Vertauschungsmatrix anzugeben. In dieser Vertauschungsmatrix stehen die Ähnlichkeiten von Zeichen untereinander. Ein Zeichen hat zu sich selbst grundsätzlich die Ähnlichkeit . Soll z.B. festgelegt werden, dass ein Komma und ein Punkt gleich sein sollen, dann gibt man ihnen in der Vertauschungsmatrix einen Wert von .

5.2.3.1 Zeilenzuordnung

Bei der Erkennung von Tabellen kommt es vor, dass Zeilen falsch getrennt oder nicht erkannt werden. D.h. Zeilen sind im Analyseergebnis gegenüber der Ground-Truth zu viel oder fehlen. Um dennoch möglichst viele Zeilen des Analyseergebnisses mit der Ground-Truth vergleichen zu können, wird das oben beschriebene Levenshtein-Maß auf Tabellen angewandt. Wichtig bei der Anwendung in diesem Kontext ist es, dass das Gewicht für Vertauschung größer oder gleich der Summe von Einfügen und Löschen eingestellt wird. Wird dies nicht beachtet wird, können die zusammen passenden Tabellenzeilen nicht gefunden werden. Dies lässt sich durch die Tatsache erklären, dass der Algorithmus stets einen kürzesten gewichteten Weg sucht. Eine Vertauschungsoperation, die äquivalent einer gleichzeitigen Löschung und Einfügung ist, würde bei gleicher Gewichtung wie die anderen Operationen immer einen kürzeren Weg angeben. Dies führt jedoch bei dem beschriebenen Tabellenlevenshtein dazu, dass unähnliche Zeilen einander zugeordnet werden. Um die passenden Zeilen zu finden, wird ein kürzester Pfad ermittelt. Dieser führt rückwärts von der Zelle rechts unten in der Distanzmatrix nach links oben. Es gibt nun in diesem Pfad drei Schritte, die auftreten können:
Abbildung 5: Zeilenzuordnung
Zeilenzuordnung
Zur Verdeutlichung betrachten wir nochmal die Tabelle 1. Für dieses Beispiel sollen die einzelnen Buchstaben Tabellenzeilenzeilen, wobei gleiche Buchstaben gleiche Zeilen bedeuten. Weiter sei ''JOCHEN'' die Ground-Truth und ''JOACHIM'' das Analyseergebnis. In Abbildung 5 kann das Zuordnungsergebnis abgelesen werden. Man sieht, dass der Algorithmus die Zeilen 'J', 'O', 'C', 'H' einander zuordnen konnte. Die Zeilen 'E' und 'N' der Ground-Truth finden sich jedoch nicht im Analyseergebnis. Die Analyse hat ausserdem die Zeilen 'I' und 'M' im Analyseergebnis erzeugt, die jedoch in der Ground-Truth nicht zu finden sind.

5.3 statCompare

Die Klasse statCompare ist die zentrale Klasse der Vergleiche und ruft die definierten statCompare-Objekte dokumentenweise auf.

5.3.1 statCompare

statCompare ruft die zu den Objektklassen korrespondierenden Vergleichsklassen dokumentenweise auf. Die Ergebnisse der Vergleiche werden von statCompare gesammelt und an das Programm weitergegeben. Bei Nichterfolg eines Vergleichs werden abhängige Vergleiche nicht ausgeführt. So macht es z.B. keinen Sinn einen Vergleich der OCR-Ergebnisse durchzuführen, wenn die Klassifikation des Dokuments nicht stimmt, da der Analyser häufig aufgrund der Dokumentenklassifikation die Bereiche der Seite auswählt, in denen die OCR Zeichen suchen soll.

5.3.2 Ablauf

Abbildung 6: Sequenzdiagramm des Vergleichs
Sequenzdiagramm
Das Programm übergibt die Dokumente für Ground-Truth und Analyseergebnis in einem Bildstapel an statCompare. Diese versucht anhand der Bildidentifikationen die einzelnen Seiten in Ground-Truth und Analyseergebnis einander zu zuordnen. Dies ist nötig, um Seitenzuordnungsfehler zu erkennen. Nur Dokumenten, deren Seiten zueinander passen, werden weiter verglichen. Jetzt ruft statCompare für jedes Dokument statCompareDocument auf (s. Abbildung 6). statCompareDocument ruft seinerseits statCompareTable für eine vorhandene Tabelle auf. Danach wird für jede Seite statComparePage aufgerufen. Hier werden einige Informationen über Seiten gesammelt. Als Nächstes wird für jedes Feld entsprechend des Feldtyps entweder statCompareMetaRoi oder statCompareSimpleRoi aufgerufen. Nach Ermittlung allgemeiner Daten wird die entsprechende Vergleichsklasse aufgerufen, z.B. für ein Textfeld statCompareTextRoi. Alle von einer Vergleichsklasse erzeugten Ergebnisse werden von der aufrufenden Klasse gesammelt und ebenfalls an den Aufrufer weitergereicht, bis alle Vergleichsergebnisse zu statCompare gelangen. Zwar werden alle Vergleichsklassen aufgerufen, aber nur wenige erzeugen z.Zt. tatsächlich Vergleichsergebnisse:

5.3.3 Die Vergleiche im Einzelnen

In diesem Abschnitt werden die einzelnen Vergleiche detailierter beschrieben. Die Begriffe ''Ground-Truth'' und ''Analyseergebnis'' beziehen sich in diesem Abschnitt nur auf das jeweils untersuchte Dokument.

5.3.3.1 statCompareDocument

statCompareDocument überprüft die korrrekte Klassifikation des analysierten Dokumentes und führt nur weitere Vergleiche auf diesem Dokument durch, wenn die Klassifikation korrekt ist. Die Klassifikation ist genau dann korrekt, wenn folgende Bedingungen gelten:

5.3.3.2 statCompareTableRoi

statCompareTableRoi überprüft nur die korrekten Dimensionen der Tabelle des Analyseergebnisses, d.h. ob sowohl die Anzahl der Spalten als auch die Anzahl der Zeilen mit denen der Ground-Truth überein stimmen.

5.3.3.3 statComparePage

Im ersten Schritt wird die auf dieser Seite befindliche Tabelle überprüft. Die hier gesammelten Vergleichsergebnisse werden dann an die Klasse statCompareDocument weitergereicht.

5.3.3.4 statCompareRoi

statCompareRoi zeichnet den Namen und den Feldtyp von Ground-Truth und Analyseergebnis des gerade bearbeiteten Feldes auf. Danach wird je nach Feldtyp statCompareMetaRoi oder statComapreSimpleRoi aufgerufen. statCompareMetaRoi wiederum ruft nur die dem Feldtyp entsprechende Vergleichsoperation auf (ausgenommen statCompareTableRoi). Diese Feldtypen erzeugen zur Zeit jedoch keine Vergleichsergebnisse.

5.3.3.5 statCompareSimpleRoi

statCompareSimpleRoi macht zwei Levenshtein-Vergleiche, wobei nur beim zweiten eine Vertauschungsmatrix benutzt wird. Eine Vertauschungsmatrix definiert eine Matrix, mit der man festgelegen kann, welche Zeichen untereinander mit welcher Wahrscheinlichkeit durch die OCR vertauscht werden. Beispielsweise werden '.' und ',' oft verwechselt, so dass hier eine 1.0 eingetragen ist, also eine Vertauschungswahrscheinlichkeit von 100%.

5.4 Benutzeroberfläche

In diesem Abschnitt wird die Benutzeroberfläche des beschriebenen Programms erläutert. Das Programm wurde mit GUI-Toolkit Qt der norwegischen Firma Trolltech für Windows erstellt.

5.4.1 Hauptfenster

Die Abbildung 7 zeigt die Benutzeroberfläche im Initialzustand. Sie hat verschiedene Menüs, eine Statuszeile und einen Bereich in der Mitte des Hauptfenster, der Unterfenster enthält. Das Verhalten der Unterfenster ist ähnlich dem des MDI-Paradigmas (Multiple Document Interface).
Abbildung 7: Das Hauptfenster
Hauptfenster

5.4.2 Einstellungen

Nach dem Start zeigt das Programm den Einstellungsdialog, damit der Benutzer die eingestellten Pfade überprüfen kann. Der Einstellungsdialog besteht aus vier Seiten, die über je eine Auswahllasche ausgewählt werden können. Die erste Seite enthält einige Informationen über den Zweck des Dialogs. Die nächste Seite (s. Abbildung 8) enthält die Einstellungen für die Ground-Truth. Dabei handelt es sich um die Pfade zu den Quellpaketen und zu den Ground-Truth-Daten.
Abbildung 8: Die Ground-Truth-Einstellungen
GT-Einstellungen
Die dritte Seite (s. Abbildung 9) enthält die Einstellungen für die Vergleichsdaten. Die einzustellenden Daten sind die Pfade zu den Quellpaketen und zu den Vergleichsdaten.
Abbildung 9: Die Einstellungen für die Vergleichsdaten
Einstellungen Vergleichsdaten

5.4.3 Fortschrittsdialog

Wenn das Programm eine Aktion durchführt, wird dem Benutzer der Fortschritt (s. Abbildung 10) angezeigt, um ihm auch bei längeren Warten auf dem Laufenden zu halten.
Abbildung 10: Fortschrittsdialog
Fortschrittsdialog

5.4.4 Ergebnisanzeige

Die Ergebnisanzeige (s. Abbildung 11) enthält die Ergebnisse eines Vergleichs (s. Abschnitte 4.4 und 5.3). Dabei werden die einzelnen Ergebnisse in jeweils einer eigenen Seite angezeigt und in einer Tabelle organisiert.
Abbildung 11: Ergebnisse
Ergebnisse

6. Ergebnisse und Ausblick

Das in dieser Arbeit beschriebene Verfahren zur Einschätzung der Erkennungsqualität des Dokumentenanalysesystems hat sich schon während der Entwicklung bewährt. So war es zum Beispiel für den Vertrieb einfacher, gegenüber Kunden Aussagen über Erkennungsraten des Systems zu machen. Bei allen möglichen Anwendungen ist es wichtig, verlässliche und objektiv nachprüfbare Daten zu erhalten. Dies alles leistet das vorgestellte Verfahren. Gleichzeitig zeigte sich, dass der Ansatz, von vorne herein alle denkbaren Daten zu erheben, aber diese nicht zu nutzen, nicht trägt. Dieses zeigte sich insbesondere bei der Verarbeitungsgeschwindigkeit, die aufgrund der Menge der Objekte, die jedoch letztlich nicht gebraucht werden, sehr gesenkt wurde. Durch die Nachbildung der Systemobjekte wurde die Pflege des Programms erschwert, da jede Änderung des Objektsystems eine Änderung in den Algorithmen nach sich zog. Insgesamt zeigte sich, dass eine Vereinfachung des Objektssystem und der Eingabedaten nötig ist, um die Weiterentwicklung und Benutzbarkeit des Programms zu vereinfachen. Jedoch kann dabei der Kern der Vergleichsalgorithmus erhalten bleiben.

A. Implementationsdetails

A.1 Einleitung

Bei den Implementationsdetails wird folgendes Schema angewandt:

A.2 Typen

Die folgenden Typen werden durch typedef erzeugt der Abkürzung und Übersichtlichkeit.
Tabelle 3: Typen
Name Typ
statDocumentPtr daPointer<statDocument>
statPagePtr daPointer<statPage>
statRoiPtr daPointer<statRoi>
statTableRoiPtr daPointer<statTableRoi>
statPageList list<daPointer<statPage> >
statRoiList list<daPointer<statRoi> >
ideeStringList list<ideeString>
ideeStringVec vector<ideeString>
ideeStringField vector<vector<ideeString> >
statStreamFunc statAsciiDb& (*func)(statAsciiDb&)
statManipFunc statAsciiDb& (*func)(statAsciiDb&, const ideeString&)
ideeStringPairList list<pair<ideeString, ideeString> >
statNode ideeTreeNode<statNodeObj>

A.3 Statistikobjekte

Abbildung 12: Klassenhierarchie der Statistikobjekte
Klassendiagramme
Die Statistikobjekte enthalten die notwendigen Statistikinformationen aus den Objekten der Klassenhierachie von modIdeeInterface (s. Abbildung 12).

A.3.1 statIfcObject

Die Klasse statIfcObject ist die Basisklasse für alle Statistikobjekte.
Tabelle 4: Attribute - statIfcObject
Name Datentyp Beschreibung Zugriff
Name ideeString Enthält den Namen des Objekts. rw
IsGround bool Ist IsGround true, dann ist dieses Objekt Ground-Truth. Ansonsten ist das Objekt ein Vergleichsobjekt. rw
Tabelle 5: Public Members - statIfcObject
Name Beschreibung
statIfcObject() Der Standardkonstruktor
statIfcObject(const ifcObject &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.2 statDocument

Diese Klasse repräsentiert die Statistikinformationen eines Dokumentes.
Tabelle 6: Attribute - statDocument
Name Datentyp Beschreibung Zugriff
Pages statPageList Die Liste der Seiten, die in diesem Dokument enthalten sind. r
RoiList statRoiList Die Liste der Felder, die in diesem Dokument enthalten sind. r
DocClass ideeString Die Dokumentenklasse dieses Dokuments. rw
Tabelle 7: Public Members - statDocument
Name Beschreibung
statDocument() Der Standardkonstruktor
statDocument(const statDocument &obj) Der Copy-Konstruktor
void addPage(const statPagePtr &page) Fügt eine neue Seite zu diesem Dokument hinzu.
const statPagePtr& page(const ideeString &name) Sucht eine Seite mit dem Namen name und gibt die gefundene Seite zurück. Wurde kein entsprechendes Feld gefunden, so gibt die Methode einen NULL-Zeiger zurück.
void addRoi(const statRoiPtr &roi) Fügt ein neues Feld zu diesem Dokument hinzu.
const statRoiPtr& roi(const ideeString &name) Sucht ein Feld mit dem Namen name und gibt das gefundene Feld zurück. Wurde kein entsprechendes Feld gefunden, so gibt die Methode einen NULL-Zeiger zurück.
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.3 statPage

Diese Klasse repräsentiert die Statistikinformationen einer Seite.
Tabelle 8: Attribute - statPage
Name Datentyp Beschreibung Zugriff
SkewAngle float Der Winkel, mit dem das Originalbild gegenüber der aufrechten Position gedreht wurde. rw
Movement daPoint Die Attribute x und y von daPoint geben die Verschiebung des Originalbildes gegenüber der richtigen Position an. rw
Scale float Der Skalierungsfaktor, mit dem das Originalbild in das Analysebild verwandelt wurde. rw
ImageId ideeString Der eindeutiger Name des Seitenbildes, wie er durch das Bildarchivierungssystem erzeugt wurde. rw
RoiList ideeStringList Die Liste der Namen der Felder, die auf dieser Seite enthalten sind. r
TableCells ideeStringList Die Liste der Tabellenzellen, die auf dieser Seite enthalten sind. rw
Columns int Die Anzahl der Tabellenspalten auf dieser Seite. rw
Rows int Die Anzahl der Tabellenzeilen auf dieser Seite. rw
Tabelle 9: Public Members - statPage
Name Beschreibung
statPage() Der Standardkonstruktor
statPage(const statPage &obj) Der Copy-Konstruktor
void addRoiName(const ideeString &name) Fügt einen neuen Feldnamen zu dieser Seite hinzu.
void addTableCell(const ideeString &name) Fügt einen neuen Feldnamen einer Tabellenzellen zu dieser Seite hinzu.
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.4 statRoi

Diese Klasse repräsentiert die Statistikinformationen eines Feldes.
Tabelle 10: Attribute - statRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 11: Public Members - statRoi
Name Beschreibung
statRoi() Der Standardkonstruktor
statRoi(const statRoi &obj) Der Copy-Konstruktor
virtual const bool isMeta() const Gibt true zurück, wenn das Feldobjekt ein Meta-Feld repräsentiert.
static statRoiPtr createRoi(ideeString classTyp, ideeString name) Erzeugt ein Feld, das den Klassentyp classTyp, z.B. TextRoi, und den Namen name hat.
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette.

A.3.5 statSimpleRoi

Diese Klasse repräsentiert die Statistikinformationen einer SimpleRoi.
Tabelle 12: Attribute - statSimpleRoi
Name Datentyp Beschreibung Zugriff
OcrResult ideeString Resultat der OCR. rw
DbMatchResult ideeString Resultat des DB-Matches. rw
RegExpResult ideeString Resultat der regulären Ausdrücke. rw
ProveRestrictionResult ideeString Resultat der prüfenden Restriktionskontrolle. rw
CorrectRestrictionResult ideeString Resultat der korrigierenden Restriktionskontrolle. rw
AnalyserResult ideeString Resultat des Analyser. rw
VerifierResult ideeString Resultat der Verifikation. rw
Creator ideeString Wurde diese SimpleRoi aus einer MetaRoi erzeugt, so enthält dieses Attribut den Namen dieses Feldes. rw
ImproverRating (mImpRating) ifcSimpleRoi::ImproverRating Bewertung des Ergebnisses durch den Improver rw
VerifierAction (mVerAction) ifcSimpleRoi::VerifierAction Aktion, die bei der Verifaktion durchgeführt wurde. rw
Tabelle 13: Public Members - statSimpleRoi
Name Beschreibung
statSimpleRoi() Der Standardkonstruktor
statSimpleRoi(const statSimpleRoi &obj) Der Copy-Konstruktor
virtual const bool isMeta() const Gibt true zurück.
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.5.1 statBarcodeRoi

Diese Klasse repräsentiert die Statistikinformationen einer BarcodeRoi.
Tabelle 14: Attribute - statBarcodeRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 15: Public Members - statBarcodeRoi
Name Beschreibung
statBarcodeRoi() Der Standardkonstruktor
statBarcodeRoi(const statBarcodeRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.5.2 statCheckboxRoi

Diese Klasse repräsentiert die Statistikinformationen einer CheckboxRoi.
Tabelle 16: Attribute - statCheckboxRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 17: Public Members - statCheckboxRoi
Name Beschreibung
statCheckboxRoi() Der Standardkonstruktor
statCheckboxRoi(const statCheckboxRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.5.3 statDbRoi

Diese Klasse repräsentiert die Statistikinformationen einer DbRoi.
Tabelle 18: Attribute - statDbRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 19: Public Members - statDbRoi
Name Beschreibung
statDbRoi() Der Standardkonstruktor
statDbRoi(const statDbRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.5.4 statTextRoi

Diese Klasse repräsentiert die Statistikinformationen einer TextRoi.
Tabelle 20: Attribute - statTextRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 21: Public Members - statTextRoi
Name Beschreibung
statTextRoi() Der Standardkonstruktor
statTextRoi(const statTextRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.5.5 statPatternRoi

Diese Klasse repräsentiert die Statistikinformationen einer PatternRoi.
Tabelle 22: Attribute - statPatternRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 23: Public Members - statPatternRoi
Name Beschreibung
statPatternRoi() Der Standardkonstruktor
statPatternRoi(const statPatternRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.6 statMetaRoi

Diese Klasse repräsentiert die Statistikinformationen einer MetaRoi.
Tabelle 24: Attribute - statMetaRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 25: Public Members - statMetaRoi
Name Beschreibung
statMetaRoi() Der Standardkonstruktor
statMetaRoi(const statMetaRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.6.1 statAddressRoi

Diese Klasse repräsentiert die Statistikinformationen einer AddressRoi.
Tabelle 26: Attribute - statAddressRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 27: Public Members - statAddressRoi
Name Beschreibung
statAddressRoi() Der Standardkonstruktor
statAddressRoi(const statAddressRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.6.2 statCombiRoi

Diese Klasse repräsentiert die Statistikinformationen einer CombiRoi.
Tabelle 28: Attribute - statCombiRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 29: Public Members - statCombiRoi
Name Beschreibung
statCombiRoi() Der Standardkonstruktor
statCombiRoi(const statCombiRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.6.3 statTableRoi

Diese Klasse repräsentiert die Statistikinformationen einer TableRoi.
Tabelle 30: Attribute - statTableRoi
Name Datentyp Beschreibung Zugriff
TableType ideeString Der Typ dieser Tabelle. rw
Columns int Die Anzahl der Spalten. rw
Rows int Die Anzahl der Zeilen. rw
Header ideeStringList Die Liste der Spaltenüberschriften. rw
TableCells ideeStringList Die Liste der Namen der Tabellenzellen. rw
Tabelle 31: Public Members - statTableRoi
Name Beschreibung
statTableRoi() Der Standardkonstruktor
statTableRoi(const statSimpleRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.3.6.4 statTopDownRoi

Diese Klasse repräsentiert die Statistikinformationen einer TopDownRoi.
Tabelle 32: Attribute - statTopDownRoi
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 33: Public Members - statTopDownRoi
Name Beschreibung
statTopDownRoi() Der Standardkonstruktor
statTopDownRoi(const statTopDownRoi &obj) Der Copy-Konstruktor
virtual void write(statAsciiDb &db) const Schreiboperator
virtual void read(statAsciiDb &db) Leseoperator
virtual const ideeString classTyp() const Liefert den Klassentyp als Zeichenkette

A.4 Stream-Objekte

Die genaue Anleitung zum Einsatz von Manipulatoren bei Streams kann [1], Seiten 676-678 entnommen werden.

A.4.1 statAsciiDb

Tabelle 34: Attribute - statAsciiDb
Name Datentyp Beschreibung Zugriff
Path ideePath Der Pfad zur Datei, in die geschrieben oder aus der gelesen werden soll. r
Tree statObjTree* Der temporäre Baum, der beim Einlesen der Objekte erzeugt wird. rnc
ActDoc ideeString Der Name des aktuellen Dokuments. r
ActPage ideeString Der Name der aktuellen Seite. r
ActRoi ideeString Der Name der aktuellen Roi. r
ActAttr ideeString Der Name des aktuelen Attributs. r
Stream fstream Der Ein- und Ausgabestream auf die benutzte Datei.  
Writing bool (mWrite) Dieses Flag zeigt an, ob der Stream zum Schreiben oder Lesen geöffnet wurde. r
Aborted bool Dieses Flag zeigt an, ob die Schreib- oder Leseoperation abgebrochen wurde.  
Tabelle 35: Public Members - statAsciiDb
Name Beschreibung
statAsciiDb(const ideePath &path, const bool bWrite) Der Konstruktor
˜statAsciiDb() Der Destruktor
void open() throw(ideeFileOpenError) Öffnet den Stream.
void close() throw(ideeFileCloseError) Schliesst den Stream.
void writeChar(char &value) throw(ideeFileWriteError) Schreibt ein char.
void writeBool(bool &value) throw(ideeFileWriteError) Schreibt ein bool.
void writeInt(int &value) throw(ideeFileWriteError) Schreibt ein int.
void writeULong(ulong &value) throw(ideeFileWriteError) Schreibt ein ulong.
void writeFloat(float &value) throw(ideeFileWriteError) Schreibt ein float.
void writeDouble(double &value) throw(ideeFileWriteError) Schreibt ein double.
void writeString(const char *value) throw(ideeFileWriteError) Schreibt eine C-Zeichenfolge.
void readChar(char &value) throw(ideeFileReadError) Liest ein char.
void readBool(bool &value) throw(ideeFileReadError) Liest ein bool.
void readInt(int &value) throw(ideeFileReadError) Liest ein int.
void readULong(ulong &value) throw(ideeFileReadError) Liest ein ulong.
void readFloat(float &value) throw(ideeFileReadError) Liest ein float.
void readDouble(double &value) throw(ideeFileReadError) Liest ein double.
void readString(char *value) throw(ideeFileReadError) Liest eine C-Zeichenfolge.
statAsciiDb& operator>>(statStreamFunc func) throw(ideeFileWriteError) Dieser Operator erlaubt paramterlose Manipulatoren.
statAsciiDb& operator>>(statStreamFunc func) throw (ideeFileReadError) Dieser Operator erlaubt paramterlose Manipulatoren.
statAsciiDb& setAttribName(const ideeString &name) Wird über einen Manipulator aufgerufen, um den aktuellen Attributnamen zu setzen.
statAsciiDb& startDocument(const ideeString &name) Wird über einen Manipulator aufgerufen, um den aktuellen Dokumentennamen zu setzen.
statAsciiDb& endDocument(const ideeString &name) Wird über einen Manipulator aufgerufen, um den aktuellen Dokumentennamen zu löschen.
statAsciiDb& startPage(const ideeString &name) Wird über einen Manipulator aufgerufen, um den aktuellen Seitennamen zu setzen.
statAsciiDb& endPage(const ideeString &name) Wird über einen Manipulator aufgerufen, um den aktuellen Seitennamen zu löschen.
statAsciiDb& startRoi(const ideeString &name) Wird über einen Manipulator aufgerufen, um den aktuellen Roinamen zu setzen.
statAsciiDb& endRoi(const ideeString &name) Wird über einen Manipulator aufgerufen, um den aktuellen Roinamen zu löschen.
ideeString key() const Erzeugt den Schlüssel für ein Attribut.
statNode* getNode() const Sucht den zum aktuellen Objekt gehörigenden Knoten im Objektbaum.
Tabelle 36: Protected Members - statAsciiDb
Name Beschreibung
void readFile() Liest die gesamte Datei zeilenweise, übergibt parseLine den Inhalt der Zeile.
void parseLine(const ideeString &line) Interpretiert die Zeile und fügt die Informationen in den Objektbaum ein.
Tabelle 37: Protected Slots - statAsciiDb
Name Beschreibung
void cancel() Setzt das Attribut Aborted auf true und wird durch ein Qt-Signal (Knopfdruck) aufgerufen.

A.4.2 manip

Tabelle 38: Attribute - manip
Name Datentyp Beschreibung Zugriff
String ideeString Die vom Manipulator übergebene Zeichenkette.  
Func statManipFunc Zeiger auf Manipulator-Funktion.  
Tabelle 39: Public Members - manip
Name Beschreibung
manip(statManipFunc func, const ideeString& string) Der Konstruktor

A.4.3 statSpreadSheetExport

Diese Klasse erlaubt es die Resultate in eine Textdatei zu schreiben. Dabei werden die Spalten einer Zeilen durch Tabulator getrennt, so dass die Textdateien in eine Tabellenkalkulation wie Excel importiert werden können.
Tabelle 40: Attribute - statSpreadSheetExport
Name Datentyp Beschreibung Zugriff
Path ideePath Der Pfad zur Datei, in die geschrieben werden soll. r
Results ideeStringField Die Resultate, die geschrieben werden. Die Tabelle ist zeilenweise angeordnet.  
Captions ideeStringVec Die Spaltenüberschriften, die in die erste Zeile der Datei geschrieben werden.  
Stream ofstream Der Dateiausgabestream, der zum Schreiben benutzt wird.  
Tabelle 41: Public Members - statSpreadSheetExport
Name Beschreibung
statSpreadSheetExport(const ideePath &path, const ideeStringVec &captions, const ideeStringField &results) Der Konstruktor.
˜statSpreadSheetExport() Der Destruktor
Tabelle 42: Protected Members - statSpreadSheetExport
Name Beschreibung
void open() throw (ideeFileOpenError) Öffnet die Datei und schreibt die Daten in die Datei. Die Spalten werden durch Tabulatoren getrennt. Anschliessend wird die Datei wieder geschlossen.
void close() throw (ideeFileCloseError) Schliesst die Datei.

A.4.4 statNodeObj

Diese Klasse repäsentiert die Knoteninformationen in dem Baum, der zum Wiedereinlesen der Ground-Truth benötigt wird.
Tabelle 43: Attribute - statNodeObj
Name Datentyp Beschreibung Zugriff
Attribs ideeStringPairList Liste der Attribut-Werte-Paare r
Tabelle 44: Public Members - statNodeObj
Name Beschreibung
statNodeObj() Der Standardkonstruktor.
void addAttribute(const ideeString &name, const ideeString &value) Füge der Liste von Attributen ein neues hinzu.
const ideeString &getAttribute(const ideeString &name) const Sucht das erste Vorkommen eines Attributes mit den Namen name.
const ideeStringList &getAttributes(const ideeString &name) const Sucht die Vorkommen von Attributen mit den Namen name.

A.4.5 statObjTree

Instantiierung und Ableitung der Schablone ideeTree<T> mit statNodeObj als Parameter.
Tabelle 45: Attribute - statObjTree
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 46: Public Members - statObjTree
Name Beschreibung
statObjTree() Der Standardkonstruktor.
void addDocument(const ideeString &name) Füge eine neues Dokument in den Objektbaum ein.

A.5 Extraktion und Vergleich

A.5.1 statExtraction

Tabelle 47: Attribute - statExtraction
Name Datentyp Beschreibung Zugriff
TableRoi statTableRoiPtr Zeiger auf eine eventuell in dem Dokument enthaltene Tabelle  
GT bool Flag, ob es sich bei den extrahierten Daten, um Ground-Truth oder nicht handelt. Setzt das Attribut isGT in statIfcObject. r
LocalDir ideePath Der Pfad zu den lokal gespeicherten Pakete, die bearbeitet werden sollen.  
Tabelle 48: Public Members - statExtraction
Name Beschreibung
statExtraction(bool isGT, ideePath localPath= ideePath(''i:\packets'')) Der Konstruktor.
statDocumentList& extract(dbiControlDbInterface::ImageStackId &stackId) Extrahiert die Dokumente eines Bildstapels.
statDocumentListMap& extract(bool local = false) Extrahiert die Bildstapel, die vom Benutzer ausgewählt wurden.
Tabelle 49: Protected Members - statExtraction
Name Beschreibung
void extractDoc(const ifcDocument &doc, statDocumentList *dlist) Extrahiert die Daten eines Dokuments und fügt ein statDocument zu dlist hinzu.
void extractPages(const ifcDocument &doc, statDocumentPtr &sDoc) Extrahiert die Daten der Seiten und fügt sie zu sDoc hinzu.
void extractRois(const ifcDocument &doc, statDocumentPtr &sDoc) Extrahiert die Daten von Feldern und fügt die statRois zu sDoc hinzu.
void fillInSimpleRoi(ifcRoiShd &roi, statSimpleRoi *sRoi) Füllt die eine SimpleRoi betreffende Informationen aus roi in sRoi ein.
void fillInMetaRoi(ifcRoiShd &roi, statMetaRoi *sRoi) Füllt die eine MetaRoi betreffende Informationen aus roi in sRoi ein.
void extractTableCells(const ifcDocument &doc, statDocumentPtr &sDoc, ifcPageShd &page, statPagePtr &sPage) Extrahiert die Tabellenzellen einer Seite und füllt sie in sDoc bzw. sPage ein. Dabei ist zu beachten, dass derzeit pro Dokument nur eine Tabelle geben kann.
Tabelle 50: Signale - statExtraction
Name Beschreibung
void stacksParsed(unsigned int nrStacks, unsigned int totalStacks) Teilt mit, dass nrStacks Bildstapel von insgesamt totalStacks Bildstapel schon bearbeitet wurden.
void docsParsed(unsigned int nrDocs, unsigned int totalDocs) Teilt mit, dass nrDocs Dokumente von insgesamt totalDocss Dokumente eines Bildstapels schon bearbeitet wurden.

A.5.2 statCompare

Tabelle 51: Attribute - statCompare
Name Datentyp Beschreibung Zugriff
Keine Attribute
Tabelle 52: Public Members - statCompare
Name Beschreibung
statCompare(const statDocumentPtr &doc, const statDocumentPtr &gt) Der Konstruktor.

Literatur

1
Die C++-Programmiersprache, 3.Auflage.
2
Optimal Correspondence of String Subsequences, Ynjin P. Wang und Theo Pavlidis, IEEE 1990
3
The Noisy Substring Matching Problem, R. L. Kashyap und B. John Oommen, IEEE 1983
4
Dispatch. Ein System zur hierarchischen Dokumentklassifikation anhand automatisch generierter Pattern, Kai Kramer, August 1999
5
Levenshtein Distance, in Three Flavors, Michael Gilleland, http://www.meriampark.com/ld.htm
6
Learning String Edit Distance, Eric Sven Ristad und Peter N. Yianilos, 1997, http://www.cs.princeton.edu/ ristad/papers/pu-532-96.ps.gz

Abbildungsverzeichnis

Tabellenverzeichnis


Über dieses Dokument ...

Entwicklung eines Benchmarking-Programmes für ein Dokumentenanalysesystem

This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.43)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -no_subdir -split 0 -show_section_numbers benchmark.tex

The translation was initiated by Jochen Schäfer on 2002-05-02<


Fußnoten

... Constraint3.1
Engl. für Beschränkung oder Einschränkung
... importieren4.1
Dies wurde im Rahmen dieser Projektarbeit nicht implementiert, ist aber aufgrund der einfachen Textdarstellung der Statistikdaten grundsätzlich möglich.
... beschrieben4.2
Das resultierende Benchmarkprogramm kann aufgrund verschiedener Anforderungen mehr Daten verarbeiten als hier beschrieben. Diese sind jedoch meist statistischer Natur und somit für eine Qualitätsaussage nicht wesentlich.
... Worte5.1
Wort bedeutet hier ein Objekt, das aus Symbolen zusammengesetzt ist, also z.B. eine Zeichenkette, oder wie später noch gezeigt wird, eine Tabelle aus Tabellenzeilen

Jochen Schäfer 27.05.2002

Valid HTML 3.2! Valid CSS!