Schrifterkennung theoretisch - Fortsetzung folgt
Während wir im Mai-Heft die grundlegenden Verfahrensweisen der Schrifterkennung betrachtet haben, soll heute etwas mehr auf neuere Entwicklungen eingegangen werden. Rekapitulieren wir noch einmal.
Die Schrift(muster)erkennung ist in zwei Hauptrichtungen gespalten: Einerseits stehen die vergleichenden Systeme mit a) reinem ASCII-Vergleich. b) dem Eingrenzungsverfahren und c) dem Maskenvergleichsverfahren. Allen gemeinsam ist eine mehr oder weniger große Bibliothek mit sogenannten Prototypen, über die dann der Vergleich stattfindet. Diese Programme zeichnen sich positiv durch hohe Treffsicherheit und zunächst auch hohe Geschwindigkeit aus, aber negativ durch hohen Arbeitsspeicherbedarf. Je größer dann eine Bibliothek wird, desto langsamer ist der Erkennungsvorgang. Grenzen für einen tolerierbaren Zeitrahmen werden bald spürbar.
Andererseits gibt es typisierende Systeme. die a) nach markanten Punkten, b) dem Draht- und c) dem Vektormodell arbeiten. Bei ihnen sind positiv der geringe Speicherplatz und eine fast immer hohe Geschwindigkeit zu werten. Negativ fällt die schwächere Treffsicherheit ins Gewicht. Hierbei liegt es hauptsächlich an der Kompliziertheit des benutzten Algorithmus’.
Buchstabentypisches
Zur Zeit sieht der Trend in der Schriftmustererkennung danach aus, als würden die vergleichenden Programme an Bedeutung verlieren und die typisierenden schneller weiterentwickelt werden. Eine „Disziplin“, welche derzeit im Kommen ist, nennt man Prinzip der typischen Muster’.
Bei den ‚typischen Mustern’ wird weniger ein bestimmter Linienverlauf oder ein Netz markanter Punkte benutzt (könnte natürlich zusätzlich der Fall sein), sondern vielmehr eine Merkmalsliste bestimmter Eigenschaften. Je typischer solche Merkmale für einen bestimmten Buchstaben sind, desto höher ist die Trefferquote. Es gibt sogar eine ausreichende Anzahl sogenannter ‚ausschließlicher typischer Muster’, die nur bei einem einzigen und keinem anderen Buchstaben sonst Vorkommen. Auch ein Aufaddieren mehrerer solcher ausschließlicher Muster für einen Buchstaben ist denkbar, was die Trefferquote noch weiter erhöht.
Beispiele für typische Muster wären:
- Öffnungen auf bestimmten Seiten.
- Winkelverhältnisse,
- parallele Linien,
- Kreuzung von Linien,
- Überlagerungen von Merkmalen,
- geschlossene Kreise,
- Quadrate,
Punkte und Zeichen und ähnliches mehr.
Hauptvorteil: Da die typischen Merkmale unabhängig von Schriftart und -große immer gleich sind, führt dies auch bei technischen Unsicherheiten (z.B. schlechte Druckqualität, schräge Vorlage, schwankende Helligkeit usw.) fast immer zu einem Treffer. Wenn zudem mehr und mehr ausschließliche Muster definiert und erkannt werden können, steigt die Trefferquote fast proportional an. Dieses Verfahren ist extrem schnell, ihm liegt aber ein verhältnismäßig komplizierter Algorithmus zugrunde.
Der Duden liest mit
Aus den vergleichenden Programmen wird eine Weiterentwicklung in Verbindung mit einem eingebauten Wörterbuch versucht. Das Programm prüft nach Definition der Buchstaben ab, ob die gefundene Kombination mit der in einem Wörterbuch übereinstimmt. Ähnlich wie bei der Bibliothek der Prototypen, muß dann natürlich auch Arbeitsspeicher für dieses Wörterbuch vorhanden sein. Ein Einsatz von Festplatten als virtuelle Speicher oder „hashing“ wäre zusätzlich recht nützlich.
Solange die erkannten Wörter mit jenen im Lexikon übereinstimmen, läuft dieses Verfahren recht klaglos. Aber wenn unbekannte Wörter abgeprüft werden sollen, dann wird’s kritisch.
Da kann es bei mehreren ähnlichen, aber im Wörterbuch nicht vorhandenen Wörter zum „Gleiche-Wörter-Konflikt“ kommen. Wenn die „gleichen Wörter“ dann nur in einem Buchstaben variieren, muß der Mensch manuell die Entscheidung treffen, welches Wort richtig ist. Diese „LexikonProgramme“ arbeiten allermeistens so, daß zunächst alle Wörterbuchwörter erkannt werden und anschließend per Bildschirm oder Drucker eine Liste unbekannter Wörter ausgegeben wird. Ein Grundwortschatz von 30.000 bis 50.000 Wörtern ist akzeptabel, und daß sich das Wörterbuch automatisch erweitert, dürfte selbstverständlich sein.
Auch gibt es ein Problem mit Wörtern, die sich selbst im Lexikon nur durch einen einzigen Buchstaben unterscheiden. Was passiert, wenn just dieser eine Buchstabe falsch erkannt wurde? Dies hat schnell dazu geführt, daß außer dem Lexikon mit Wörtern auch noch eins mit grammatikalischen und orthografischen Merkmalen mitgeführt wird. Auch wäre eine Liste undenkbarer Zeichenfolgen möglich. Z.B. drei Buchstaben hintereinander oder irre Folgen wie „grglhupf“, „sftware“ oder „ST-Cmptr“. (Sie erkennen die Ähnlichkeit in der Denkweise mit den oben besprochenen typischen Mustern? Um es nun ganz auf die Spitze zu treiben, wäre sogar ein Lexikon mit dem typischen Satzbau denkbar (ist aber noch nicht realisiert worden).
Vorteil der Lexikonprogramme: Unsicherheiten im Erkennungsprozeß können hiermit zusätzlich überwunden werden. Die Trefferrate im Erkennen ist sehr hoch. Es gibt aber (derzeit noch) einen Riesennachteil: der unermeßlich große Speicherbedarf und die hohe Rechenzeit. Deshalb sollten Lexikonprogramme vorerst noch immer nur zusätzlich angewandt werden.
Mit Mathematik erkennen
Als jüngstes Kind in der Familie darf man ‚rein mathematische Verfahren’ zur Schrifterkennung begrüßen. Wohlgemerkt werden selbstverständlich in den vorher besprochenen Erkennverfahren auch mathematische Prinzipien angewandt, beispielsweise, wenn es um Pendelwerte, Toleranzen oder Näherungen geht. Bei den „mathematisierten“ Verfahren vielmehr ist an Statistik. Wahrscheinlichkeitsrechnung und Analysis gedacht.
Gleich das Hauptproblem vorweg: Diese mathematischen Prozesse können nicht für sich alleine arbeiten. Irgend ein vorgeschaltetes Verfahren muß, in welcher Form auch immer, Anhaltspunkte zum Erkennvorgang geliefert haben. Meist ist dies ein einfaches Raster wie b ei dem Maskenvergleichsverfahren. Erst dann können komplizierte Algorithmen an die Arbeit gehen.
Ein Bild läßt sich also grundsätzlich immer als eine Funktion (beispielsweise)
f(x,y) = fschwarz(x,y) und
f(x,y) = fweiß(x,y)
beschreiben. So bestimmt f(x,y) die Intensität der Werte „schwarz“ und „weiß“ an der Stelle der Koordinaten (x,y).
Eine andere Schreibweise ergibt sich für mehrfarbige Bildpunkte. wobei dann das RGB-Spektrum benutzt wird:
f(x,y) = frot(x,y)
f(x,y) = fgrün(x,y) und
f(x,y) = fblau(x,y)
(Sie sehen, daß der Schritt zu Erkennungsprogrammen, die mit Farb-Scannern arbeiten, gar nicht mehr so weit hergeholt scheint.)
Gerade bei der Schrifterkennung bietet sich in Erweiterung des Funktionsbegriffes eine dritte Dimension an: die Zeit. Das sähe dann so aus:
f(x,y,t) = fschwarz(x,y,t)
und
f(x,y,t) = fweiß(x,y,t)
In der Funktionsanalysis ist nichts durch irgendwelche Dimensionen begrenzt - in der Mathematik gibt es die beschreibbare Unendlichkeit. Nicht so im Arbeitsspeicher des Computers. Also muß der ‚unendlichkeitsfähige’ Funktionsbegriff durch Grenzen festgestellt werden. Dies geschieht durch die Menge der möglichen Punkte (x,y,t) und auch die Menge der möglichen Funktionswerte f(x,y,t) in endlich festgelegten Schritten (Intervalle). Daraus entsteht dann eine Matrix. (Ähnlichkeit mit grafischem Raster ist nicht rein zufällig und nicht ungewollt!)
Es folgen zwei unterschiedliche Verfahren, die man als Scanning (Digitalisierung) und als Sampling (Quantisierung) bezeichnet. Sie sind so allgemein gültig, daß uns dies von der Spezialanwendung „Schrifterkennung“ hin zur Globalanwendung „Bilderkennung“ führt. Es würde den Rahmen des heutigen Berichtes sprengen, näher auf diese komplizierten Vorgänge einzugehen, außerdem werden sie für uns an dieser Stelle einfach viel zu theoretisch.
Ein kleines (vorläufiges) Schlußwort sei mir erlaubt. Die Schriftmustererkennung beginnt gerade erst, ihre potentiellen Anwender zu begeistern. Dieser Bericht (und der im Mai-Heft) wollte nur kurz die Oberfläche anreißen und aufzeigen, was sich in Zukunft alles tun könnte. Software-Entwickler mag dieser kleine Streifzug (hoffentlich) angeregt und dem anderen Leser etwas Appetit gemacht haben. Ich bin sicher, daß wir bald mit interessanten Neuigkeiten zu diesem Thema zurückkehren werden.
Dieter Kühner