Diplomarbeit - Kapitel 2

Dieses Kapitel vermittelt einen groben Überblick über dieses System zur Erfassung von Online-Daten mit einer Videokamera. Hierbei wird der Datenfluss durch die einzelnen Komponenten vorgestellt und die Aufgaben und Funktionsweise der Komponenten kurz angerissen. Die Informationen aus diesem Kapitel dienen in den späteren Kapiteln als Grundlage und bilden den Rahmen für das Verständnis des Systems. Details zu den Komponenten und Algorithmen folgen im Kapitel 3. Auf das objektorientierte Design und die Implementation in C++ wird im Kapitel 4 eingegangen.

Die Erfassung der Online-Daten kann, wie in Bild 4 dargestellt, als Datenfluss durch mehrere Komponenten betrachtet werden. Zuerst wird die Person beim Schreiben einer Textzeile mit einer Videokamera gefilmt. Diese Bildsequenz wird auf dem Computer eingelesen und an die Vorverarbeitung weitergereicht. Nach der Vorverarbeitung werden die Differenzbilder zwischen den Einzelbildern der Bildsequenz berechnet. Diese Differenzbilder gelangen via Nachverarbeitung an die Erkennungsroutine. In der Erkennungsroutine wird die Position des Schreibstifts bestimmt und ausgegeben. Diese Liste von Positionen wird schliesslich qualitativ verbessert und im Format des Online-Erkennungssystems ausgegeben. Nachfolgend werden die einzelnen Schritte des Datenflusses näher vorgestellt.

Während des Schreibens einer Textzeile wird der Benutzer von einer Videokamera gefilmt. Wie dem Bild 5 entnommen werden kann, sitzt der Benutzer an einem Tisch, auf dem ein weisses Blatt Papier befestigt ist. Gegenüber dem Benutzer ist die Videokamera auf einem Stativ befestigt und erfasst das obere Drittel des Papiers.

Der Benutzer schreibt mit einem Filzstift. Dieser Filzstift färbt blau und die Stiftspitze hat einen Durchmesser von 0.7 mm. Das Äussere des Stifts, ausser der Stiftspitze, ist weiss eingefärbt. Die Buchstaben haben eine Höhe von 1 bis 1.5 cm und werden vom Benutzer langsam geschrieben.

Es ist wichtig, dass die ganze Szene gut und homogen beleuchtet ist. Deshalb dürfen nicht Spotlampen zum Einsatz kommen, da die von ihnen erzeugten scharfen Schatten um die Stiftspitze stören würden. Eine starke indirekte Beleuchtung mit vier Fotolampen über die weisse Zimmerdecke hat sich bewährt.

Die Aufnahme des Schreibers geschieht unabhängig von der späteren Erfassung der Stiftpositionen. Dies war technisch unumgänglich, denn eine Verarbeitung der anfallenden Videodaten wäre nur mit grossem technischen Aufwand online zu realisieren. Die Signale der Videokamera werden auf einer Workstation (1) digitalisiert und abgespeichert. Die Einzelbilder haben eine Grösse von 384 auf 288 Pixel wobei jedes Pixel im TrueColor-Format (2) abgespeichert wird. Pro Sekunde werden ca. 19 Bilder erfasst. Um die riesige Datenmenge (6 MB/s) zu bewältigen wird die Bildinformation verlustbehaftet nach dem MPEG-Verfahren komprimiert. Eine durchschnittliche Textzeile (1.5 cm hoch, 12 cm lang, 3 bis 6 Worte) belegt 30 MB Speicherplatz. Weitergehende Details über die Hard- und Softwarekomponeten zur Erfassung von Videodaten können im Anhang A gefunden werden.

In der Vorverarbeitung werden die einzelnen Bilder eingelesen und in Graustufenbilder konvertiert. Die zu verarbeitende Datenmenge wird dabei auf einen Drittel reduziert. Weil die Videokamera gegenüber dem Schreiber plaziert ist, werden die Bilder noch um 180° rotiert um den Blickwinkel des Benutzers zu erhalten.

Um eine gute Geschwindigkeit des Systems zu erreichen werden die Bilder auf ein kleines Rechteck (Bounding-Box) beschnitten, welches alle wesentlichen Teile der Textzeile bzw. des Worts umfasst. Die Festlegung dieser Bounding-Box geschieht manuell, basierend auf dem letzten Bild der Sequenz. Hierdurch kann die Fläche des Bildausschnittes ca. um den Faktor 10 verkleinert und dementsprechend die Verarbeitung um den gleichen Faktor beschleunigt werden. Ausserdem beschränken sich alle weiteren Routinen auf diesen Bereich und werden von anderen Daten weniger störend beeinflusst.

Um den Bildausschnitt nochmals zu verkleinern wird jedes Bild wie in Bild 6 maskiert. Diese Maske ist dem Schriftzug angepasst und umfasst diesen möglichst eng.

1. Originalbild von der Kamera nach der Wandlung in Graustufen
2. Rotation um 180°
3. Beschneidung des ganzen Bilds auf Bounding-Box der Textzeile
4. Maskierung der Textzeile

Als Differenzbild wird im folgenden ein Bild verstanden, das genau die Unterschiede zweier Bilder enthält. Im Idealfall besteht ein Differenzbild zweier aufeinanderfolgender Bilder einer Sequenz genau aus den im betrachteten Zeitabschnitt zusätzlichen Schriftzug (vgl. Bild 7). Leider entspricht dieser Idealfall nicht der Wirklichkeit. Beim Schreiben mit einem Stift verändert sich die Position des Stifts, der Stift wirft Schatten auf das Papier und verdeckt Teile des bereits geschriebenen Schriftzuges.

Bild 7: Idealfall der Erstellung der Differenzbilder. In diesem Beispiel wird
vorausgesetzt, dass Binärbilder verarbeitet werden und die exakte
Position der Tinte auf dem Blatt Papier betrachtet wird.

Diesem Problem wird auf zwei Arten Rechnung getragen. Einerseits ist der Stift bis auf die Spitze weiss eingefärbt um dem Hintergrund, dem weissen Papier, möglichst ähnlich zu sein. Andererseits werden nicht nur die zwei aufeinanderfolgenden Bilder betrachtet, sondern auch die nachfolgenden Bilder. Wenn ein neuer Teil des Schriftzugs zu einer Differenz der Bilder führt, so ist diese Differenz auch in den nächsten Bildern noch vorhanden, denn die Farbe wurde unwiederbringlich auf das Blatt Papier aufgetragen.

Wenn aber im Gegensatz dazu der Stift durch Verdeckung zu einer Differenz zwischen den zwei Bildern führt, so wird er sich in den nachfolgenden Bildern an einer anderen Stelle befinden und somit die Ursache für die Differenz nicht mehr existent sein. Wird diese Problematik nicht berücksichtigt, so führt wie in Bild 8 das Verschieben des Stift unweigerlich zu falschen Pixel im Differenzbild.

Bild 8: In einem dreiwertigen Bild (weiss, grau, schwarz) wird die Stiftspitze (graues Dreieck) fälschlicherweise in die Generierung des Differenzbilds mit einbezogen.

Dank der Betrachtung der in der Sequenz nachfolgenden Bilder (Lookahead-Technik) können Fehler wie in Bild 8 vermieden werden und die Differenzbilder bestehen zu grossen Teilen nur noch aus Veränderungen der auf das Blatt aufgetragenen Farbe. Diese Lookahead-Technik wird in Kapitel 3 näher vorgestellt.

Während dem Schreiben kommt es vor, dass der Stift bereits geschriebene Teile des Schriftzugs verdeckt. Wenn der Stift nun weiter bewegt wird kann es geschehen, dass die Differenz zweier Bilder aus früher erfassten Teilen des Schriftzuges besteht (vgl. Bild 9). Dies würde zu einer falschen Erfassung der Stiftposition führen.

Bild 9: Entstehung des Buchstabens "H". Im linken Bild ist die untere Hälfte des
senkrechten Strichs noch sichtbar. Im mittleren Bild ist sie vom Stift
verdeckt und erscheint schliesslich im rechten Bild wieder.

Zur Vermeidung der wiederholten Erfassung bereits erkannter Teile des Schriftzugs werden alle bereits erstellten Differenzbilder in einem Summenbild kummuliert. In diesem Summenbild sind alle Teile des Schriftzuges enthalten welche bisher je in einem Differenzbild erschienen sind. Dieses Summenbild wird in der Nachverarbeitung aus dem Differenzbild entfernt, wodurch schon früher Erfasstes wieder entfernt und der Fehler vermieden wird (vgl. Bild 10).

Bild 10: Das Wiederauftauchen von durch den Stift (weises Dreieck) verdeckten Pixel kann durch das Eliminieren aller schon früher erfassten Pixel umgangen werden

Die Veränderung des Schriftzuges von Bild zu Bild der Bildsequenz ist sehr klein. Meistens besteht die Differenz nur aus wenigen Punkten. Die Position des Stifts entspricht ungefähr dem Mittelpunkt dieser wenigen Differenzpunkte.

In Wirklichkeit besteht das Differenzbild nicht aus einer kleinen Häufung von schwarzen Punkten, sondern aus einem Grauwertbild welches durchaus mehrere dunklere Stellen aufweisen kann. Dieses Grauwertbild wird zuerst in ein binäres Bild umgewandelt. Der hierzu notwendige Schwellwert wird aus der Grauwertverteilung (Histogramm) des Differenzbilds abgeleitet. Von diesen schwarzen Punkten wird dann ein Zentrum bestimmt. Befinden sich keine schwarzen Punkte im Bildausschnitt, hat keine Veränderung zwischen den zwei aufeinanderfolgenden Bildern stattgefunden; der Stift war also nicht auf dem Papier abgesetzt. Eine entsprechende Mitteilung ("leerer Punkt") wird an den nächsten Verarbeitungsschritt weitergegeben.

Zur Bestimmung des Mittelpunkts können die vier verschiedenen Verfahren von Bild 11 angewandt werden. Das einfachste Verfahren, bei dem der Schwerpunkt (arithmetisches Mittel) der einzelnen Punkte bestimmt wird eignet sich nur bedingt, da einzelne verstreute Punkte das Resultat verfälschen. Eine iterative Bestimmung des Schwerpunkts führt zu besseren Resultaten. Beim iterativen Verfahren werden die Punkte bei der Berechnung des Mittelpunkts in mehreren Schritten umgekehrt proportional zum Abstand vom Mittelpunkt des vorherigen Schrittes gewichtet.

Gute Ergebnisse werden durch die Bestimmung des Medians der Punkte erzielt. Der resultierenden Mittelpunkt der schwarzen Bildpunkte liegt meistens in oder nahe der grössten Ansammlung von Punkten. Die besten Resultate liefert die Bestimmung desjenigen schwarzen Bildpunkts, der zentral im Vergleich zu allen anderen Punkten liegt. Es wird also ein bestehender Punkt als Mittelpunkt gewählt und nicht ein neuer Punkt erzeugt. Die Bestimmung der Mittelpunkte wird im Abschnitt "3.6 Stiftpositionen erfassen" detailliert erklärt.

Die im vorherigen Schritt erkannten Stiftpositionen können oft mit einfachen Mitteln verbessert werden. Wenn zwischen zwei erkannten Punkten wenige "leere Punkte" liegen und die Distanz zwischen den erkannten Punkten klein ist, macht eine Verbindung Sinn und die zwischenliegenden "leeren Punkte" werden linear interpoliert (vgl. Bild 12).

Bild 12: Der leere Punkt vom linken Bild, symbolisiert durch einen kleinen Kreis,
wurde durch lineare Interpolation zu einem neuen Punkt im rechten Bild

Wenn der Abstand zwischen zwei aufeinanderfolgenden erkannten Punkten zu gross ist, macht die bestehende Verbindung keinen Sinn und die Verbindung der beiden Punkte wird getrennt. Durch diese zwei einfachen Änderungen an den Punkten wird in vielen Fällen eine wesentliche Verbesserung der Resultate erzeugt.

Die erkannten und verbesserten Punkte müssen schliesslich noch in einem spezifischen Format ausgegeben werden, um später als Eingabe für einen Online-Erkenner oder ein Programm zur Darstellung von Online-Daten zu dienen. Die Ausgabe erfolgt in eine Textdatei, welche pro Zeile eine Zeitmarke und die Stiftposition als x- und y-Koordinate enthält. Details können dem Abschnitt "3.7 Verbesserung und Ausgabe der Positionen" entnommen werden.

1) SUN UltraSparc 143MHz mit speziellem SunVideo-Board, welches die Videosignale in Echtzeit abtastet und als komprimierte Videodatei abspeichert.

2) TrueColor-Bilder verwenden pro Bildpunkt 24bit Information. Aufgeteilt auf die drei Farbkanäle Rot, Grün und Blau ergibt das je 256 Abstufungen. Maximal können 16.7 Millionen unterschiedliche Farben adressiert werden.