Schrifterkennung theoretisch
Mein Professor für theoretische Informatik glaubte, zum Thema der Schrifterkennung folgenden Satz verlautbaren zu müssen: “Schriftmustererkennung hat nur deshalb wahnsinnige Ähnlichkeit mit ‘Desktop Publishing’, weil sie genau umgekehrt und doch ganz anders funktioniert.” Ganz ehrlich - ich habe den Sinn dieses Satzes nie so recht verstanden, obwohl mir die Bedeutung all dieser Worte geläufig ist, und vielleicht deshalb steht der Satz noch heute in meinem Vorlesungsskriptum.
Erst als dann verschiedene Wissenschaftssendungen von revolutionären Neuerungen in der Computertechnik zu berichten wußten und Worte wie ‘Künstliche Intelligenz’ und ‘Neuro-Computer’ die Runde machten, erst dann fiel mir dieser Satz wieder ein. Da gibt es Computer, die ‘sehen’ können, und bald kann ich mich mit dem Computer richtig unterhalten!
Ganz unbestritten gehört die Schrifterkennung in den Zweig der ‘Artifiziellen Intelligenz’ (Abk.: “AI”) - übrigens: von ‘künstlicher Intelligenz’ spricht man in deutschsprachigen Insiderkreisen längst nicht mehr (wegen der vielen Verwirrungen).
In der Computerbibel “Gödel, Escher, Bach” von Douglas R. Hofstadter ist auf Seite 641 eine übersichtliche Liste aller Disziplinen der AI aufgeführt. Hofstadter vermeidet zwar Hinweise auf sogenannte ‘Expertensysteme’ (auch wieder eine deutsche Wortschöpfung), räumt aber der visuellen AI viel Platz ein. Demnach gehört das “Erkennen individueller handgeschriebener Zeichen” und das “Lesen von Texten in verschiedenen Schriftarten” in diesen Wissenschaftszweig und wird der Überschrift ‘Mustererkennung’ zugeordnet.
Was ist eine (Muster)erkennung ?
Es geht im Grunde nur darum, irgendwelche Grafik in computerverständliche Zeichen umzuwandeln. Daß es sich bei dieser ‘Grafik’ um Buchstaben und Texte handelt, kann der Computer noch nicht wissen. Durch ein spezielles Lesegerät (Scanner) oder per Videokamera werden Hell-/Dunkel-Impulse analog abgetastet, digital in den Rechner transportiert und dort in ASCII-Zeichen umgewandelt. Gerade dieser Umwandlungsprozeß aber hat es in sich!
Problem 1: Solange bei der Analog/Digital-Wandlung im Scanner nur zwischen Ganzhell (Weiß) und Ganzdunkel (Schwarz) unterschieden werden muß, ist das Ganze kaum der Rede wert. Aber wenn mit mehreren Graustufen gearbeitet wird, oder sogar zwischen Farben unterschieden werden soll, muß der Scanner schon einiges leisten. Deswegen wird ein sogenannter Pendelwert vom Scanner berücksichtigt, der helleren Werten Weiß zuordnet und eher dunkleren Werten Schwarz.
Problem 2 - Die Auflösung: Die Anzahl der Lesepunkte einer Scannermatrix bestimmt die Genauigkeit des Lesevorganges. So waren bislang 200 dpi und 300 dpi recht grob, “dpi” = “dots per inch”, zu deutsch: Bildpunkte pro Zoll. Gerade an den Grenzen zweier Buchstaben können dabei Verwaschungen oder Auslassungen auftreten. Das ist insbesondere dann der Fall, wenn diese Buchstaben zwischen zwei Lesepunkten lagen. Bei einem DIN-A4-Blatt lesen etwa 3500 solcher Matrixpunkte eine Scannerzeile ein (nicht verwechseln mit einer Textzeile). Geräte mit 400 dpi und 600 dpi erreichen gerade preislich interessante Tiefen.
Problem 3 - Die Vorlage: Wenn der Kontrast zwischen Papier und Schrift nicht sehr hoch ist, kann es beim Pendelwert oft zu ‘entweder-oder-Entscheidungen’ kommen und das für jeden Lesepunkt einzeln. Eine Verbesserung erreicht man, wenn die Scannerhelligkeit größer gewählt wird.
Gehen wir davon aus, der Scanner hat uns eine schöne ‘Schwarzweißgrafik’ geliefert. Bevor nun ein recht komplizierter Programmteil an die Arbeit geht, werden markante Grafikteile herausgesucht. Ganz wichtig sind durchgehende Linien. Weiße Linien, die ‘unbeschadet’ horizontal den Text durchlaufen, werden automatisch als Zeilenzwischenräume erkannt. Einige Programme prüfen auch in vertikaler Richtung und schließen dabei auf Block- bzw. Spaltengrenzen. Dann werden schwarze Linien in beiderlei Richtung aufgespürt und ‘unsichtbar’ gemacht. Dabei muß das Programm gewisse Toleranzen berücksichtigen. Vertikale Linien beispielsweise, die so groß sind wie der Abstand der Zeilenzwischenräume oder weniger, dürfen nicht unterdrückt werden, es könnten ja Buchstaben sein. Horizontale schwarze Linien dürfen in aller Regel unbedenklich getilgt werden.
Verschiedene Programme prüfen besonders bei schwarzen Linien die unmittelbare Nachbarschaft ab, um sicher zu gehen, daß es sich wirklich um grafische Teile handelt. Durch diese Linienauslese werden insbesondere Bilder und Fotos ausgeschaltet. Einige Prüfroutinen stellen dabei sicher, daß nicht zufällig doch einige Buchstaben unter den Tisch fallen.
Erkennungsverfahren
Nun aber zum Erkennen selber. Allen Verfahren liegt ein Gedanke zugrunde: Beim Einlesen über die Leuchtdiodenmatrix des Scanners wird auf das Bild regelrecht ein Netz gelegt. Dieses Netz legt sich in Teilen auch über jeden einzelnen Buchstaben, und innerhalb dieser Maschen kann ‘erkannt’ werden. Man kennt mindestens fünf verschiedene Verfahren, dem Zeichen auf den Buchstaben zu kommen.
Allereinfachst ist das Vergleichsprinzip bzw. der ‘ASCII-Vergleich’ (Bild 1). Da muß vorher schon festgelegt sein, in welcher Schriftart und oftmals auch in welcher Größe der Text eingelesen wurde. In einer gewaltigen Bibliothek prüft das Programm eine streng näherungsweise Ähnlichkeit und nimmt bei Eindeutigkeit der Suche einen Treffer an. So haben früher die allerersten Programme gearbeitet. Das Verfahren ist sehr unflexibel und nimmt keine Abweichungen hin.
Etwas komplizierter (Bild 2) wird die Suche nach den ‘markanten Punkten’. So werden für einen bestimmten Buchstaben Punkte festgelegt, in denen er in höherem Maße ‘ausgeprägt’ ist. Ausprägung heißt nichts anderes, als daß genau dort ein Kontrastunterschied, also eine gegenteilige Farbe gegenüber den direkten Nachbarpunkten vorliegen muß. Das Maß der Ausprägung bedeutet, daß in dem markanten Punkt ein Kontrastunterschied zu mehr als der Hälfte der Nachbarpunkte vorliegt. Je weniger unmittelbare Nachbarpunkte dieselbe Farbe haben, desto höher das Maß der Ausprägung und desto markanter der Punkt. Nachbarpunkte sind auch jene Maschenquadrate, die nur mit einer Eckspitze an den fraglichen markanten Punkt stoßen.
Typisches Beispiel hierzu: Das kleine “i”. Es hat mindestens drei markante Punkte, von denen der i-Punkt (im wahrsten Sinne des Wortes) der markanteste ist. Vom i-Punkt aus gesehen haben alle acht direkten Nachbarpunkte eine gegensätzliche Farbe, also hat dieser markante Punkt das höchstmögliche Maß der Ausprägung. Die Wahl der markanten Punkte unterliegt wichtigen Gesetzmäßigkeiten. So nimmt die Treffergenauigkeit ab, wenn zu wenige markante Punkte definiert wurden (logisch), kurioserweise ebenso, wenn es zu viele sind. Auch ist die Lage, Entfernung und das Verhältnis der markanten Punkte zueinander zu beachten. Typische Punkte hoher Ausprägung sind Eckpunkte. Punkte innerhalb von Linien eignen sich nicht als markante Punkte.
Ziemlich schnell hat man aus dem Prinzip der markanten Punkte das ‘Drahtmodell’ entwickelt (Bild 3), aber nicht notwendigerweise, um dieses dadurch ablösen zu lassen. Dort wurde ganz einfach die Verbindung zwischen den Punkten sichtbar gemacht. Es genügt demgegenüber auch völlig, im markanten Punkt die Richtung des Linienverlaufes zu vermerken (Vektormodell), also die Linie selbst nicht zu ziehen. Vorteil dieser Verfeinerung: Es werden immer weniger markante Punkte zur Eindeutigkeit nötig.
Als Fortentwicklung dieses Modells zeigt sich das Einbeziehen typischer Muster wie Öffnungen auf bestimmten Seiten, bestimmte Winkelverhältnisse, Parallelitäten, Kreuzungen, Überlagerungen und ähnliches mehr.
Verfahren Nummer vier nennt man ‘Eingrenzung’ und sagt nichts anderes, als daß man für ein bestimmtes Maschennetz eindeutig festgelegt hat, wo eine gegenteilige Farbe sein darf und wo nicht. Man nennt diese Eingrenzung auch noch ‘Prinzip der verbotenen Zone’ (Bild 4). So kann man dreierlei ‘Zustände’ festschreiben und zwar: 1., wo ein gegenteiliger Maschenfarbpunkt auf jeden Fall sein muß, 2., wo er möglicherweise sein kann und 3., wo er auf jeden Fall nicht sein darf. Je strenger man diese Bedingungen für die 3 Zustände nimmt, desto genauer wird die Trefferquote.
Eine Abwandlung ist das stark vereinfachte ‘Maskenvergleichsverfahren’ (Bild 5). Da verfährt man mit den 3 obigen Zuständen folgendermaßen: 1. Man nimmt einen Treffer an, wenn das Zeichen die Maske überdeckt, und beachtet die Grenzbereiche nicht. 2. Man nimmt einen Treffer an, wenn die Maske überdeckt und keine Farbgegensätze außerhalb der Maske sind. Hauptnachteil: Es müssen auch hier die Zeichensätze annähernd bekannt sein. Hauptvorteil: extrem schnell.
Zusätzlich können noch Programmteile in Aktion treten, die gewisse grammatikalische und orthografische Eigenheiten berücksichtigen.
Dieter Kühner