DE69230940T2

DE69230940T2 - Verfahren zum Ableiten der Merkmale von Zeichen in einem Zeichenerkennungssystem

Info

Publication number: DE69230940T2
Application number: DE69230940T
Authority: DE
Inventors: Robert Wilcke
Original assignee: Koninklijke KPN NV
Current assignee: PTT Post Holdings BV
Priority date: 1992-12-30
Filing date: 1992-12-30
Publication date: 2000-10-19
Anticipated expiration: 2012-12-31
Also published as: PT604687E; EP0604687A1; DK0604687T3; ES2146205T3; ATE191980T1; US6240209B1; EP0604687B1; JPH076209A; DE69230940D1; GR3033926T3

Description

A. Technischer Hintergrund der Erfindung

1. Technisches Gebiet der Erfindung

Die vorliegende Erfindung liegt auf dem Feld der Zeichenerkennung. Sie betrifft ein System zur Erkennung von Zeichen wie Zahlen und Buchstaben, sowohl in handgeschriebener als auch in gedruckter Form und insbesondere ein Verfahren zum Ableiten der Merkmale eines Zeichens, welches in einem Zeichenerkennungssystem dieses Typs zu erkennen ist.

2. Stand der Technik

Zeichenerkennungssysteme wie die oben beschriebenen umfassen im allgemeinen eine Anzahl von Verfahrensschritten, die unten unter Bezugnahme auf ein in Fig. 1 dargestelltes Flussdiagramm beschrieben werden. Diese Verfahrensschritte sind:
(1) optisches Abtasten eines Zeichens auf der Oberfläche eines Trägers; solch ein Abtasten, zum Beispiel mit einer Videokamera, resultiert in einem zweidimensionalen Punktmuster, zum Beispiel 64 mal 64 Punkte, denen ein Grauwert angehängt wird, der in 5 Bits kodiert ist;
(2) binäre Quantisierung des Punktmusters durch Unterwerfen der Grauwerte aller Punkte einer Schwellwertbildung, wobei das Ergebnis, welches ein schwarz-weiss-Muster oder ein Muster aus "Nullen" und "Einsen" bildet, in einem Speicher gespeichert wird;
(3) Ableiten, von diesen quantisierten Punktmustern ausgehend, von einer Bildbeschreibung des zu erkennenden Zeichens;
(4) Ableiten, von der Bildbeschreibung ausgehend, eines Satzes von Zeichenmerkmalen des zu erkennenden Zeichens;
(5) Prüfen des Satzes von erkannten Zeichenmerkmalen gegen die früher erhaltenen Ergebnisse mit der Hilfe eines Lernprozesses von bekannten Zeichen;
(6) Entscheiden auf der Basis dieser Prüfung, welches bekannte Zeichen als das zu erkennende Zeichen angesehen wird.
(7)
Eine Erkennungstechnik des oben genannten Typs ist beispielsweise aus der Druckschrift [1] in (siehe unter C.) bekannt. Bei dieser Technik wird das quantisierte Punktmuster eingesetzt, um eine Umrissbeschreibung abzuleiten. Wenn einer Umrissbeschreibung eines digitalisierten Musters eines Merkmals gefolgt wird, werden die Koordinaten von gewissen Punkten ausgewählt. Diejenigen Punkte werden ausgewählt, deren inneres Produkt des Punktvektors, der jedem Punkt entspricht, mit einem Richtungsvektor in einer Anzahl von vorbestimmten Richtungen den höchsten Wert ergibt. Ein gewählter Punkt wird als ein "extremaler Punkt" oder Extremalpunkt gekennzeichnet, falls der Unterschied zwischen dem besagten inneren Produkt dieses Punktes und dem inneren Produkt an dem folgenden ausgewählten Punkt einen vorher gewählten Grenzwert überschreitet. Diese Extremalpunkte bilden eine polygonale Annäherung des Umkreises des Musters. Solche Polygone zeigen ein Muster von konvexen und konkaven Strukturen. Diese Muster werden zum Vergleich mit ähnlichen Mustern eingesetzt, die Charakteristiken von bekannten Zeichen aufweisen und in einem vorher zusammengestellten "Lexikon" gespeichert sind. Das zu erkennende Zeichen wird als das bekannte Zeichen ausgelesen, dessen Muster die beste Übereinstimmung aufzeigt.
Eine funktionelle Begrenzung der Mustermerkmale, welche in diesem bekannten Erkennungsverfahren abgeleitet werden, liegen in der strukturellen Beschreibung des zu erkennenden Zeichens. Dies erzeugt eine akzeptable Zeichenerkennung nur, wenn das zu erkennende Muster eine klare Struktur aufweist. Dies bedeutet, dass diese bekannte Technik nur für die Erkennung von Zeichen einer klaren Handschrift oder Druckschrift angewandt werden kann. Eine andere Begrenzung ist die Veränderlichkeit der Anzahl der Merkmale, auf denen die Erkennung basiert, dass heisst die Anzahl der konvexen und konkaven Strukturen in dem Muster. Dies macht es schwierig, Entscheider in der Erkennung einzusetzen, die mit einer bestimmten festen Anzahl von Merkmalen arbeiten, wie zum Beispiel diejenigen, die neurale Netzwerke mit einer standardisierten "Vorwärtsleitung" einsetzen.
Die Druckschrift in [2] beschreibt ein weiteres Zeichenerkennungssystem des oben genannten Typs. Die Zeichenerkennung, auf der dieses System basiert, leitet Zeichenmerkmale aus einer Anzahl von sogenannten Ansichten eines Bildes, entweder des vollständigen Bildes oder eines Teiles von diesem, von einem binären quantisierten Punktmuster des zu erkennenden Zeichens ab. In dieser sogenannten Sichtmethode wird eine Anzahl von verschiedenen Merkmalen eines Punktmusters für jede Sicht abgeleitet, von oben, von unten und von der Seite und für jedes Bild oder Teil eines Bildes. Für diese Merkmale wie Sprünge, Neigungen, Endpunkte und Inseln, werden für jedes bestimmte in den Ansichten gefundene Muster Merkmalswerte bestimmt. Während der Überprüfungsphase werden die Merkmalswerte unter Einsatz von einstellbaren Gewichtsfaktoren für jede zu erkennende Klasse von Zeichen gewichtet. Diese Gewichtsfaktoren sind früher aus einem Lernprozess von bekannten Zeichen erhalten worden. Die gewichteten Merkmalswerte werden eingesetzt, um einen Wert für jede Klasse festzustellen. Das zu erkennende Zeichen wird als das Zeichen erkannt, welches zu der Klasse gehört, bei der der höchste Wert festgestellt worden ist.
Diese bekannte Technik, die die Sichtmethode zum Ableiten von Zeichenmerkmalen einsetzt, ist zuerst einmal zur Erkennung von Zahlen entwickelt worden. Das Zeichenmerkmal, welches in diesem Verfahren abgeleitet wird, ist zu allgemein, um für eine spätere Erkennung einsetzbar zu sein. Darüber hinaus weist das Verfahren, aufgrund der Vielfalt der verschiedenen Merkmale, für welche ein zu erkennendes Zeichen geprüft werden muss, eine zu komplexe Struktur auf. Aufgrund der Art der Merkmale, die tatsächlich strukturelle Merkmale sind, wird eine Zeichenerkennung, die auf diesen Merkmalen basiert, weiterhin für Brüche im Bildmuster eines zu erkennenden Zeichens empfindlich sein, und dieses Erkennungsverfahren ist daher zum Beispiel für Matrixzeichen ungeeignet, sowie insbesondere für Buchstaben, die von einem Punktmatrixdrucker stammen.
Aus der Bearbeitung von digitalen Bildern ist es auch bekannt, Distanzfunktionen einzusetzen. Verfahren, die hierauf basieren, werden teilweise als "Distanztransformation" oder "Distanzabbildung" bezeichnet. Ein bekanntes "Distanzabbildungsverfahren" dieses Typs ist beispielsweise in der Druckschrift [13] beschrieben. Dieses beinhaltet, an jeden Bildpunkt, der ein Teil eines Untersatzes von Punkten sein könnte, im Objekt (oder im Hintergrund) des originalen binären Bildes den kürzesten Abstand zum nächsten Bildpunkt im Hintergrund (oder dem Objekt) anzuhängen. Zu jedem Punkt besteht somit ein Distanzwert. Die weitere Bearbeitung wird dann auf der Basis dieser Zwei-Komponenten- Beschreibung ausgeführt, bei der die Verarbeitung unter anderem Skelettstrukturen des zu erkennenden Zeichens verfolgt. Ein Distanzwert dieses Typs ist an sich als ein Zeichenmerkmal ungeeignet, um insbesondere handgeschriebene Zeichen zu erkennen.

B. Zusammenfassung der Erfindung

Es ist die Aufgabe der Erfindung, ein Verfahren zum Ableiten von Zeichenmerkmalen in einem Zeichenerkennungssystem anzugeben und ein Zeichenerkennungssystem anzugeben, bei dem das Verfahren angewendet werden kann, wobei das Verfahren und das System nicht die oben genannten Nachteile und Begrenzungen der Funktionalität aufweist. Gemäss der vorliegenden Erfindung verfügt ein Verfahren zur Ableitung von Zeichenmerkmalen in einem Zeichenerkennungssystem zum Erkennen von Zeichen, wie Buchstaben und Zahlen, über einen Schritt, mit dem für jeden Punkt einer Vielzahl von Punkten in einer Bildebene von Bildpunkten eines Muster eines zu erkennenden Zeichens Merkmalsdaten abgeleitet werden, die für den Abstand zum nächsten Bildumrisspunkt des Musters kennzeichnend sind, der aus der Druckschrift [3] bekannt ist, und ist zu diesem Zweck durch die Merkmale des Anspruchs 1 gekennzeichnet. Eine in diesem Zusammenhang bestehende Idee liegt darin, dass für einen solchen Referenzpunkt Ri ein nächster Grenzumrisspunkt einen einzigartigen Punkt der Bildbeschreibung des zu erkennenden Zeichens darstellt, inkl. der Umgebung. Durch eine Betrachtung der Umgebung von solch einem einzigartigen Punkt aus, der einem Referenzpunkt Ri entspricht, ist es möglich, zusätzlich zu den Distanzdaten D(Ri) eines oder mehrere Merkmale auszuwählen, die die Umrisse der Bildbeschreibung des Zeichens in der Umgebung von solch einem Referenzpunkt charakterisieren. Es ist herausgefunden worden, dass ein starkes Merkmal zu diesem Zweck das Merkmal ist, welches eine Schätzung der Richtung H(Ri) liefert, welches, falls die Beschreibung des Zeichens eine Umrissbeschreibung enthält, eine Umrissbegrenzung in einem einzigen Umrissbegrenzungspunkt aufweist, der dem Referenzpunkt Ri entspricht. In einem bevorzugten Ausführungsbeispiel ist das Verfahren gemäss der Erfindung durch den Anspruch 2 gekennzeichnet.
Im Vergleich zu dem Ansichtsverfahren, welches oben beschrieben worden ist, basiert das Verfahren gemäss der Erfindung auf der Erkennung einer Anzahl von Merkmalen, die von lokalen Ansichten eines Bildmusters erhalten worden sind, wie dies von jedem der Referenzpunkte gesehen werden kann.
Die Druckschrift [5] beschreibt ein Verfahren zum Ableiten von Merkmalen zum Zwecke einer Graubilderkennung, bei dem Merkmale in einer sogenannten Merkmalszelle festgestellt werden, von der Orte aus Übereinstimmungszwecken durch Polarkoordinaten relativ zu einem Ursprung beschrieben werden, der als Referenzzelle beschrieben wird. Die abgeleiteten Merkmale sind sehr viel komplizierter als die von dem Verfahren der vorliegenden Erfindung abgeleiteten Merkmale.
Gemäss der Erfindung wird ein Zeichenerkennungssystem der eingangs genannten Art entsprechend dem Oberbegriff des Anspruchs 7 und welches aus den Druckschriften [1] oder [2] bekannt ist, durch den Anspruch 7 gekennzeichnet.

C. Druckschriften

[1] US 4,566,124 mit dem Titel "Pattern reading system";
[2] US 3,999,161 mit dem Titel "Method and device for the recognition of characters preferably of figures";
[3] P.-E. Danielsson, "Euclidean distance mapping, Computer Graphics and Image Processing 14", Seiten 227-248 (1980);
[4] R. P. Lippmann, "An introduction to computing with neural nets", IEEE ASSP Magazine, April 1987, Seiten 4-22; und
[5] M. Sano et al., "Gray-level image recognition based on multiple cell-features", Systems and Computers in Japan, Band 22 (1991) Nr. 5, New York, USA, Seiten 81-93.

D. Kurze Beschreibung der Zeichnungen

Die Erfindung wird nun im grösseren Detail unter Bezugnahme auf ein beispielhaftes Ausführungsbeispiel erläutert, dass in den Figur dargestellt ist. Es zeigen:
Fig. 1 ein Flussdiagramm der Verfahrensschritte eines Zeichenerkennungssystems,
Fig. 2 ein Schwarz-Weisses-Punktbild eines zu erkennenden Zeichens mit einem Innenumriss und mit einem Aussenumriss,
Fig. 3 eine Darstellung eines Verfahrens zur Festlegung eines Umrisses, wobei Fig. 3a die Situation für einen einzigen schwarzen Bildpunkt zeigt und Fig. 3b die Situation nach Auffinden eines k-ten Umrisspunktes zeigt,
Fig. 4 eine Umrisslinie nach Filterung der Ränder des Punktbildes nach Fig. 2,
Fig. 5 eine Darstellung von drei verschiedenen Situationen der Position eines Bezugspunktes in Bezug auf eine Umrisslinie in den Fig. 5a, 5b, und 5c,
Fig. 6 einen Überblick in Gestalt eines Blockschaltbildes eines Prozessors und eines Speichermittels für den spezifischen Zweck des Ausführens der Verfahrensschritte (3) und (4) aus Fig. 1 gemäss der Erfindung, und
Fig. 7 ein Diagramm eines Entscheiders zum Ausführen der Verfahrensschritte (5) und (6) gemäss Fig. 1, wie er in Kombination mit dem Verfahren gemäss der Erfindung angewandt wird.

E. Beispielhaftes Ausführungsbeispiel

Die Erfindung betrifft ein Verfahren zum Ableiten von Zeichenmerkmalen zum Zwecke eines Erkennungssystems zur Zeichenerkennung wie beispielsweise von gedruckten oder handgeschriebenen Zeichen und Buchstaben. Ausgehend von der Beschreibung eines zu erkennenden Zeichens geht die Zeichenerkennung von einer Basis einer Anzahl von Merkmalen, die innerhalb vorgegebener Grenz punkte abgeleitet werden, von einem beschriebenen Zeichen aus. Die Erfindung betrifft daher zuerst einen Verfahrensschritt (4) in dem Zeichenerkennungssystem, welches unter Bezugnahme auf Fig. 1 beschrieben ist. Die Erfindung kann sowohl auf eine Punktbeschreibung als auch auf eine Umrissbeschreibung eines zu erkennenden Zeichens abgestellt sein. Dies betrifft den Verfahrensschritt (3). Da eine Umrisserkennung bevorzugt ist, wird diese im Detail nachgehend beschrieben, wobei die Punkterkennung nur angedeutet werden wird. Die Verfahrensschritte (1) und (2) werden gemäss den bekannten Techniken durch Aufzeichnungsmittel ausgeführt, die an sich bekannt sind und die daher nicht in grösserem Detail beschrieben werden. In der weiteren Beschreibung eines beispielhaften Ausführungsbeispiels wird angenommen, dass diese Schritte stattgefunden haben und dass ein Schwarz-Weisses- Punktmuster eines zu erkennenden Zeichens in einem zweidimensionalen Bildspeicher gespeichert ist und für weitere Bearbeitungen zugänglich. Solch ein Schwarz-Weisses-Punktmuster in einer Bildebene mit L mal M Bildpunkten hat eine elementare Beschreibung, eine sogenannte Bildbeschreibung, durch eine Funktion B(i, j) vorgegeben, wobei Bildwerte für jeden Punkt (i, j) in der Bildebene vorhanden sind, wobei i = 1, ..., L und j = 1, ..., M, sind, wobei die Funktion durch B(i, j) = 1 für jeden schwarzen Bildpunkt (i, j) und B (i, j) = 0 für jeden weissen Bildpunkt (i, j) in der Bildebene definiert ist.
Es wird weiter angenommen, dass das zu erkennende Zeichen Teil einer Reihe von gleichzeitig aufgenommenen Zeichen ist, wobei bereits ein Trennungsvorgang auf dieser Reihe stattgefunden hat, bei dem die an sich bekannten Techniken eingesetzt worden sind, um Zeichen zu trennen und sie für eine getrennte Behandlung vorzusehen. Die Verfahrensschritte (5) und (6) werden auch mit bekannten Techniken ausgeführt. Da jedoch die Überprüfungs- und Entscheidungsmittel vorher gelernt haben müssen, dass gewisse Zeichen auf der Basis von Zeichenmerkmalen zu erkennen sind, die gemäss dem Verfahren gemäss der Erfindung abgeleitet worden sind, werden diese Mittel kurz in grösserem Detail in der folgenden vollständigen Beschreibung des Verfahrens erläutert.
Im technischen Gebiet der Bildverarbeitung und Zeichenerkennung ist die sogenannte Distanztransformation bekannt. Diese Transformation hängt eine Zahl D(P) dem Punkt P in einer Bildebene eines Schwarzen-und-Weissen Musters von Bildpunkten an, wobei wie folgt vorgegangen wird:
- falls der Punkt P in einem weissen Bereich der Bildebene angeordnet ist, dann ist D(P) gleich dem Abstand zum nächsten schwarzen Bildpunkt; und
- falls der Punkt P in einem schwarzen Bereich angeordnet ist, der zum Beispiel eine Zahl oder ein Zeichen repräsentiert, dann ist D(P) gleich zum Abstand zum nächsten weissen Bildpunkt, jeweils mit einem Minuszeichen versehen.
Diese Distanztransformation wird häufig in sogenannten Skelett- Algorithmen eingesetzt, um Skelettsstrukturen zu verfolgen, wobei die Zeichenerkennung auf der Basis der aufgefundenen Skelettstrukturen durchgeführt wird. Ein Bildsignal, das so transformiert worden ist, wird teilweise direkt zum Zwecke der Zeichenerkennung eingesetzt. Eine Distanzmarkierung wird dann als Zeichenmerkmal benutzt. Falls eine begrenzte Anzahl von Bildpunkten in diesem Prozess eingeschlossen ist, zum Beispiel um die mathematische Operation zu beschleunigen, ist die Distanzmarkierung unzureichend, um ein zu erkennendes Zeichen zu beschreiben. Um eine ausreichende Erkennungswahrscheinlichkeit zu erreichen, ist eine sehr grosse Anzahl von Bildpunkten, wenn nicht alle Bildpunkte, in der Transformation einzuschliessen. Dennoch ist die Erkennung insbesondere von Handschrift unzureichend. Das Ziel der Erfindung ist es, eine erheblich höhere Er kennungswahrscheinlichkeit zu erreichen, indem ein Zeichenmerkmal oder mehrere Zeichenmerkmale zu jeder erhaltenen Distanzmarkierung auf der Basis einer Distanztransformation für eine begrenzte Anzahl N von Punkten Ri hinzugefügt werden, die in einer geeigneten Weise ausgewählt worden sind (wobei i = 1, 2 ..., N), die als Referenzpunkte bezeichnet werden und die in der Bildebene liegen. Dies basiert auf der Idee, dass, falls ein solcher Referenzpunkt Ri eine Distanzmarkierung D(Ri) aufweist, die angehängt ist, im Allgemeinen ein einzigartiger Grenzpunkt Pi eines zu erkennenden Zeichens diesem entsprechend und zusammen mit der Umgebung zugehörig sein wird. Grenzpunkte werden als solche Bildpunkte verstanden, die sowohl weisse als auch schwarze Bildpunkte in ihrer direkten Umgebung aufweisen. Im Falle einer Umrissbeschreibung ist ein Grenzpunkt ein Punkt auf dem Umriss, ein Umrisspunkt. Ohne einen direkten anderslautenden Hinweis werden von nun an eine Umrissbeschreibung und Umrisspunkte angenommen werden. Durch das Betrachten der Umgebung eines einzigen Umrisspunktes Pi dieses Typs und der sich auf einen Referenzpunkt Ri bezieht, ist es möglich, zu einer Distanzmarkierung D (Ri) ein oder mehrere Merkmale hinzuzufügen, die, von solch einem Referenzpunkt Ri aus gesehen, den Umriss des nächsten Umrisssegmentes C(Ri) beschreiben. Es ist herausgefunden worden, dass ein sehr starkes Merkmal das Merkmal ist, welches einen Hinweis auf die Richtung H(Ri) des Umrisses im Umrisspunkt Pi angibt. Andere zusätzliche Merkmale, die zu nennen wären, bilden eine Schätzung der zweiten und dritten Ableitung des Umrisses im Umrisspunkt Pi. Diese zusätzlichen Merkmale liefern jedoch keinen zusätzlichen Anteil zur erhöhten Erkennungswahrscheinlichkeit eines Zeichens. Alle diese Beschreibungen auf der Basis der besagten zusätzlichen Merkmale zu den benachbarten Umrissabschnitten C(Ri) für alle N Referenzpunkte Ri bilden zusammen eine sehr wirksame Erkennung, falls N ausreichend gross ist. Es werden vorzugsweise 70 bis 120 Referenzpunkte für jedes Zeichen eingesetzt, die in gleichförmiger Weise oder zufällig über die Bildebene verteilt sein können. Im unten gegebenen Beispiel wird das Verfahren zur Bestimmung der Merkmale D (Ri) und H (Ri) für einen Referenzpunkt Ri in der Bildebene eines zu erkennenden Musters im grösseren Detail erklärt.
Zu diesem Zweck zeigt die Fig. 2 ein Schwarzes-und-Weisses Muster eines getrennten Zeichens in einem Rechteck von 12 · 16 Feldern, wobei jedes Feld einem Bildpunkt entspricht. Zur Klarheit ist die Anzahl von Bildpunkten in diesem Beispiel kleingehalten. Jedes Feld ist einzigartig identifizierbar durch seine Mittelkoordinaten (i, j) wobei i = 1, ..., 12 und j = 1, ..., 16. Die schwarzen Felder sind schraffiert. Jedes Feld ist schwarz oder weiss. 5o ist das Feld (2, 3) weiss und das Feld (4,3) ist schwarz. Falls ein Feld (i, j) schwarz ist, dann hat es einen Bildwert B(i, j) = 1 und, falls das Feld weiss ist, dann hat es einen Bildwert B(i, j) = 0. Wenn ein schwarzes Feld neben einem weissen Feld liegt, sind die Grenzlinien als fette Linien ausgezeichnet. Die besagte zweidimensionale Beschreibung wird dann durch ein Verfahren, welches als Umrissverfolger bekannt ist, in eine eindimensionale Umrissbeschreibung des Musters des zu erkennenden Zeichens gewandelt. Dieser Umrissverfolger läuft nacheinander durch alle 12 · 16 Felder des Bildpunktes, während er nach Umrisspunkten Ausschau hält. Jedesmal, wenn ein Startpunkt gefunden ist, wird ein Umriss erzeugt. In diesem Verfahren werden den Rändern Nummern gegeben und ihre relative Position wird dadurch festgehalten, indem daran erinnert wird, ob ein Startpunkt innerhalb eines vorher bestimmten Umrisses liegt. Das Verfahren des Verfolgens eines Umrisses wird nun im grösseren Detail unter Bezugnahme auf die Fig. 3 mit den Unterabschnitten Fig. 3a und 3b beschrieben. In diesem Verfahren wird jeder Bildpunkt als ein kleines schwarzes oder weisses Quadrat von begrenzten Dimensionen angesehen. Die Ecken eines solchen Quadra tes werden Gitterpunkte genannt. In der Fig. 3a ist ein einzelner schwarzer Bildpunkt mit den Mittelkoordinaten (i, j) als ein schraffiertes kleines Quadrat dargestellt, wobei die Gitterpunkte 1 bis 4 durchnumeriert sind. Ein getrennter schwarzer Bildpunkt hat einen wohlbegrenzten Umriss, der durch die fett gezeichneten Umrisssegmente 1 nach 2, 2 nach 3 usw. ausgebildet ist, der einen schwarzen Bereich in einer in Uhrzeigerrichtung verlaufenden Sichtweise umschliesst (entsprechend der Pfeilrichtung). Die x,y-Koordinaten der besagten vier Gitterumrisspunkte 1 bis 4 werden gewählt als:
(x(1), y(1)) = (i - 0.5, j + 0.5)
(x(2), y(2)) = (i + 0.5, j + 0.5)
(x(3), y(3)) = (i + 0.5, j - 0.5)
(x(4), y(4)) = (i - 0.5, j - 0.5)
In der Fig. 3b ist die Situation dargestellt, dass bei der Verfolgung eines Umrisses C nach dem (k-2)-ten und dem (k-1)-ten Umrissgitterpunkt, wenn von einer Ankunftsrichtung v gekommen wird, ein Gitterpunkt (x(k), y(k)) als k-ter Umrisspunkt aufgefunden worden ist. Die Ankunftsrichtung v = (vx, vy) hat vier mögliche Werte, die wie folgt ausgedrückt werden können (1,0), (- 1, 0), (0, 1) und (0, -1). Im dargestellten Beispiel ist es (1,0). Zur Linken und zur Rechten der Fortführung der Ankunftsrichtung v über den k-ten Umrisspunkt hinaus sind zwei Bildpunkte L und R als gestrichelte Linien dargestellt. Drei Richtungen sind möglich, bei denen der folgende (k + 1)-te Umrisspunkt gefunden werden kann, was in der Figur als v&sub1;, v&sub2; und v&sub3; dargestellt ist. Die Richtung, in der der folgende Umrisspunkt gefunden werden kann, hängt von dem Bildwert B jeder der beiden Bildpunkte L und R ab. Die zentralen Koordinaten der Bildpunkte L und R angesichts der Ankunftsrichtung (vx, vy) und der Koordinaten des k-ten Umrissgitterpunktes sind:
iL = x (k) + (vx - vy)/2 und jL = y(k) + (vx + vy)/2
iR = x(k) + (vx - vy)/2 und jR = y(k) + (vx - vy)/2
Der (k + 1)-te Umrissgitterpunkt und die zugehörige Ankunftsrichtung werden durch das Mittel eines Umrissverfolgungsalgorithmus bestimmt, der das folgende Aussehen haben kann:
Falls B(iL, jL) = 1 dann Beginne vx: = vy; vy: = vx Ende, ansonsten
Falls B(iR, jR) = 0 dann Beginne vx: = vy; vy: = vx Ende; x(k + 1): = x(k) + vx; y(k + 1): = y(k) + vy; k: = k + 1;
gehe zum nächsten Punkt über.
Um die Ränder eines Punktbildes, wie das in der Fig. 2 dargestellte, aufzufinden, wird die Bildebene von links nach rechts und von oben nach unten abgetastet. Ein erster Startpunkt für einen Umriss wird aufgefunden, falls bei dieser Abtastung der erste schwarze Bildpunkt, im Beispiel der Bildpunkt (6,14), aufgefunden wird. Die ersten zwei ausgewählten Umrisspunkte sind in diesem Fall die Umrissgitterpunkte 1 und 2 in der Fig. 3a; wobei v = (1, 0) die Ankunftsrichtung im zweiten Umrissgitterpunkt ist. Der Umrissverfolgungsalgorithmus startet dann, bis eine Rückkehr zum ersten Umrissgitterpunkt erfolgt ist. Bei jedem neuen Start des Umrissverfolgungsalgorithmus wird die Umrissnummer CN um 1 erhöht. Während jeder Ausführung des Umrissverfolgungsalgorithmus werden die Bildpunkte, die zum selben Umriss gehören, mit derselben Umrissnummer CN markiert. Diese Markierung wird in einem getrennten zweiten Bildspeicher festgehalten. Vor dem Beginn des Abtastens der Bildebene sind alle Bildpunkte im zweiten Bildspeicher mit derselben anfänglichen Markierung versehen, zum Beispiel mit der Zahl 0. Nach der Vervollständigung eines Umrisses wird das Punktbild erneut in der Suche nach einem neuen Startpunkt für den nächsten Umriss abgetastet. Der nächste Startpunkt wird gefunden, falls während des weiteren Abtastens ein schwarzer Bildpunkt gefunden wird, der noch nicht markiert worden ist, oder falls ein unmarkierter weisser Bildpunkt inner halb eines vorherig aufgefundenen Umrisses aufgefunden wird. In solch einem Fall wird der Verfolgungsalgorithmus erneut durchlaufen. Während des Durchlaufes werden alle Umrissgitterpunkte, die aufgefunden worden sind, in der aufgefundenen Reihenfolge in einer Umrisstabelle aufgezeichnet, die einen zugehörigen Umrisszähler umfasst. Dieser Zähler umfasst für jeden Umriss die Umrisszahl C des Umrisses mit den Zeigern nrept und nrlpt für den ersten und den letzten Umrissgitterpunkt des betreffenden Umrisses und einen Code cdoc, der die Nummer des unmittelbar angrenzenden Randes angibt. Der Umriss des gesamten Punktbildes wird in diesem Zusammenhang als mit einem virtuellen Umriss der Nummer 0 betrachtet. Das Punktbild der Fig. 2 weist einen ersten Umriss C1 auf, dessen Umrissgitterpunkte nacheinander mit 1, 2, 3, ..., 61 und 62 durchnumeriert sind. Es verfügt über einen zweiten Umriss C2, dessen Umrissgitterpunkte mit den Zahlen 63, 64, ..., 77 und 78 bezeichnet sind, und welcher vollständig innerhalb des ersten Umrisses C1 liegt. Die zugehörige Umrisstabelle ist in der Tabelle 1 dargestellt, wobei Unterabschnitte 1a und 1b dargestellt sind und der Umrisszähler in den Unterabschnitten 1a angegeben und in der Tabelle 1b die Liste der Umrissgitterpunkte angegeben sind.
Beispielhaft sei ein Satz RP von Referenzpunkten RP(m, n) angenommen, die eine Anzahl von Bildpunktmittelpunkten aufweist: RP = {RP(m, n) = (4m - 2,5n - 2) m, n = 1, 2, 3}
Einer der besagten Referenzpunkte RP (3,2) ist in der Fig. 2 dargestellt. Falls von solch einem Punkt die lokale Form des benachbartesten Umrisssegmentes, in diesem Fall der Umriss C1, untersucht wird, werden Merkmale eines ziemlich winkligen und komplexen Musters erhalten. Daher wird vor dem Beginn der eigentlichen Merkmalsableitung die durch den oben genannten Verfolgungsalgorithmus erhaltene Umrissbeschreibung zuerst einem Umriss filterprozess zugeführt, der einen Umriss mit einer ruhigeren Linienführung erzeugt. Dies wird beispielsweise durch einen einfachen linearen Filter gemacht, der entlang des Umrisses verläuft und jeweils ein gewichtetes Mittel der jeweiligen benachbarten Umrissgitterpunkte bestimmt. In diesem Verfahren wird der Filterschritt immer mit einem Versatz von einer Gitterweite durchgeführt. Das Ergebnis dieser Filterung ist eine neue gleich lange Liste von Umrisspunkten, die üblicherweise nicht länger Gitterpunkte sind und die die Ecken eines Polygons mit einer ruhigeren Umkreislinie bilden. Falls die Länge eines solchen linearen Filters vier Gitterpunkte beträgt, umfasst jeder Filterschritt fünf aufeinanderfolgende Umrissgitterpunkte aus der Umrisstabelle. Eine neue Umrisstabelle wird dann unter Hinzufügung von neuen Koordinaten zu den Koordinaten des jeweiligen k-ten Umrissgitterpunktes in der nun alten Umrisstabelle zusammengefasst durch:
X(k) = x(k - 2)/8 + x(k - 1)/4 + x(k)/4 + x(k + 1)/4 + x(k + 2)/8
Y(k) = y(k - 2) /8 + y(k - 1) /4 + y(k) /4 + y(k + 1) /4 + y(k + 2)/8
Wenn dies auf das Bildmuster aus der Fig. 2 mit der Umrisstabelle nach Fig. 1b angewandt wird, erzeugt es eine neue Umrisslinie, die in der Fig. 4 dargestellt ist und deren zugehörige Umrisstabelle in Tabelle 2 dargestellt ist, wobei diese die Liste von neuen Koordinaten der Umrisspunkte umfasst. Der Umrisszähler bleibt in diesem Falle unverändert. Es ist dann der Fall, dass die Umrissbeschreibung für die Ableitung der lokalen Umrissmerkmale D und H für jeden der Referenzpunkte des Satzes RP geeigneter ist. In diesem Verfahren wird jeder Umriss betrachtet, als dass er aus Sehnen besteht. Eine Sehne der Nummer k ist die gerade Verbindungslinie zwischen zwei aufeinanderfolgenden Umrisspunkten k-1 und k und enthalten den Umrisspunkt k als Endpunkt und nehmen den Umrisspunkt k-1 als Startpunkt aus. Die Liste der Umrisspunkte in der Umrisstabelle wird somit eine Liste von End punkten von aufeinanderfolgenden Sehnen, die die Ränder in der Umrissliste spezifizieren. Es wird dann für jeden Referenzpunkt aus dem Satz RP festgestellt, welche der Sehnen von allen Rändern in der Umrisstabelle den kürzesten Abstand zum Referenzpunkt Dmin(RQ) als auch den kürzesten Abstand selbst aufweist. Dies wird erreicht, indem aufeinanderfolgend durch die Liste der Endpunkte der Sehnen hindurchgegangen wird. In Abhängigkeit von der Position eines Referenzpunktes RQ im Hinblick auf eine Sehne k können drei verschiedene Situationen auftreten. Diese sind schematisch in der Fig. 5 mit den Unterfiguren 5a, 5b und 5c dargestellt. In der Situation nach Fig. 5a ist der am nächsten aufzufindende Punkt tatsächlich der Startpunkt der Sehne k. Der bisher aufgefundene minimale Abstand Dmin(RQ) ist somit immer im Falle einer vorherigen Sehne aufzufinden. In den Situationen nach Fig. 5b und 5c sind ein Punkt P der Sehne k und der Endpunkt der Sehne k die nächsten Punkte, die in einem Abstand d vom Referenzpunkt RQ liegen. In beiden Fällen wird ein Test ausgeführt, um festzustellen, ob diese aufgefundene Distanz d kürzer als die minimale Distanz Dmin(RQ) ist, die bis jetzt aufgezeichnet worden ist. Falls dem so ist, wird der aufgefundene Abstand d als neuer Wert für Dmin(RQ) zusammen mit der zugehörigen Sehne und dessen Nummer aufgezeichnet. Die folgende Formel wird für die Berechnung des Abstandes eingesetzt:
- in der Situation gemäss Fig. 5b:
d² = (ax · cy - ay · cx)²/(cx² + cy²)
- und in der Situation nach Fig. 5c:
d² = ax² + ay²
wobei:
ax = x(RQ) - X(k) und ay = y(RQ) - Y(k)
cx = X(k) - X (k-1) und cy = Y(k) - Y(k - 1)
Tatsächlich wird das Minimum d² zuerst festgestellt und nur, falls dieses aufgefunden wird, wird die Wurzel berechnet. Zur selben Zeit überprüft das Verfahren, ob der Referenzpunkt RQ zur betreffenden Linken oder zur Rechten des Umrisses angeordnet ist, von dem die Sehne mit dem minimalen Abstand Dmin(RQ) Teil ist. Dies wird durch Bestimmung des inneren Produktes (ax* cyay*cx) des Vektors (cy, cx), der senkrecht zur Sehne steht, der nun als Vektor (cx, cy) betrachtet wird, mit dem Vektor (ax, ay) bestimmt, der durch den Endpunkt der Sehne begrenzt wird durch und den Referenzpunkt RQ vorgegeben ist. Falls der Wert des inneren Produktes positiv ist, ist der Referenzpunkt RQ auf der Rechten angeordnet, und falls es negativ ist, ist er auf der linken Seite des Umrisses angeordnet. Da ein Umriss immer in Uhrzeigerrichtung um das Schwarze ausgewählt wird, ist dann bekannt, ob der betreffende Referenzpunkt RQ in einem "schwarzen" oder in einem "weissen" Bereich des gefilterten Bildmusters angeordnet ist.
Die gewünschten Merkmale des Referenzpunktes RQ werden nun wie folgt bestimmt:
(i) D(RQ) = Dmin(RQ), falls RQ in einem "weissen" Bereich liegt; D(RQ) = - Dmin(RQ), falls RQ in einem "schwarzen" Bereich liegt;
(ii) H(RQ) = Richtung der nächsten aufgefundenen Sehne, die als Richtung des Vektors [X(k)-X(k-1), Y(k)-Y(k-1)] in Richtung der Fig. 5 berechnet wird;
H(RQ) = Richtung des Vektors rechtwinklig zur Verbindungslinie zwischen dem Endpunkt der nächsten Sehne und dem Referenzpunkt RQ, der in Richtung des Vektors ±[Y(k) - Y(RQ), - X(k) + X(RQ1)]in der Situation nach Fig. 5c berechnet wird, wobei das Plus- bzw. das Minus-Zeichen jeweils angewandt wird, wenn der Referenzpunkt RQ in einem "schwarzen" oder in einem "weissen" Bereich angeordnet ist.
Das Richtungsmerkmal wird vorzugsweise in einem Winkel ausgedrückt und es kann beispielsweise durch eine Umkehrfunktion des Kosinus, Sinus oder Tangens berechnet werden. Wenn es auf eine gefilterte Umrissbeschreibung wie in Fig. 4 angewandt wird, ist für den Referenzpunkt RP(3,2) festgestellt worden, dass die Sehne mit der Nummer 14 den kürzesten Abstand aufweist. Da der Referenzpunkt im "Weissen" angeordnet ist, wird der minimale Abstand als positiv betrachtet und das Richtungsmerkmal H(RP(3, 2)) = Richtung des Vektors [X(14)-X(13), Y(14)-Y(13)]. Wie bereits oben erwähnt, kann das Verfahren gemäss der Erfindung nicht nur mit einer Umrissbeschreibung eines Bildmusters ausgeführt worden werden. Eine Beschreibung auf Bildpunktbasis, die Bildpunktbeschreibung B(i, j), ist in ähnlicher Weise zur Bestimmung der Merkmale D(RQ) und H(RQ) direkt geeignet. Im Falle dieser Beschreibung ist es darüber hinaus möglich, einen oder mehrere der vielen bekannten Algorithmen zur Bestimmung der Distanztransformation einzusetzen. Wenn die Bildzentren wiederum als Referenzpunkte gewählt werden, kann ein einfacher Algorithmus wie folgt vorgehen: Falls ein Referenzpunkt RQ im "Weissen" angeordnet ist, werden die Bildumgebungen um den Referenzpunkt RQ in stetiger Weise mit sich vergrössernden "Kreisen" abgetastet, bis der nächste schwarze Bildpunkt Z gefunden worden ist. Dann wird das Merkmal wie folgt gewählt:
D (RQ) = {(i (Z) - i (RQ))² + (J (z) - J (RQ))²}1/2, und H(RQ) = Richtung des Vektors [-j(Z) + j(RQ), i(Z)- i(RQ)].
Falls RQ in einem "schwarzen" Bereich liegt, wird natürlich der nächste "weisse" Bildpunkt W gesucht und die analogen Ausdrücke werden dann für diese Merkmale angewandt. Die oben erwähnte Auswahl für das Richtungsmerkmal H(RQ) ist sehr einfach, aber eher grob. Verfeinerungen können erhalten werden, indem die umgebenden Punkte von Z oder W eingeschlossen werden, deren Bildpunktwerte mit Z oder W korreliert sind. Die Merkmale, die in der oben genannten Weise erhalten worden sind, bilden auf der Basis entweder einer Bildpunktbeschreibung oder einer Umrissbeschreibung eines zu erkennenden Zeichens die Elemente eines Vektors, den Merkmalsvektor V = {vn} mit n = 1, ..., 2 N, wobei die Reihe der Vektorkoeffizienten gewählt wird als:
{Vn} = {D(R&sub1;), H(R&sub1;), D(R&sub2;) rH(R&sub2;),- -, D(RN)rH(RN)}
Die Fig. 6 zeigt als Blockschaltbild einen Überblick über ein Prozessormittel PM und ein Speichermittel mm, die speziell geeignet sind, um die Verfahrensschritte (3) und (4) aus der Fig. 1 gemäss dem oben beschriebenen Verfahren zur Ableitung von Zeichenmerkmalen auszuführen. Unter einer gestrichelten Linie sind die Speichermittel dargestellt, die mit M1, M2, M3 und M4 bezeichnet sind, und oberhalb der gestrichelten Linie sind die Prozessormittel PM dargestellt, um die drei Prozesse CD, CF und FD auszuführen. Die Beziehung ist wie folgt: Das Verfahren CD beschreibt den Umriss eines Zeichens. Es führt einen den Umriss verfolgenden Algorithmus auf dem Bildmuster des Zeichens aus, welcher nach den Verfahrensschritten (1) und (2) von Fig. 1 ausgeführt worden ist und nachfolgend in einem ersten Speicher M1 als Bildspeicher verfügbar ist. Und es übernimmt die erhaltene Umrissbeschreibung in einem zweiten Speicher M2. Dann führt das Verfahren CF den Umrissfilterprozess auf der Umrissbeschreibung aus, der im zweiten Speicher M2 abgelegt ist, und legt die gefilterte Umrissbeschreibung in einem dritten Speicher M3 ab. In einem vierten Speicher M4 ist eine Liste mit allen Koordinatendaten der Referenzpunkte R1 des Satzes RP abgelegt. Das Verfahren FD führt die Merkmalsableitung für alle Referenzpunkte aus der Liste des vierten Speichers M4 auf der gefilterten Umrissbeschreibung aus dem dritten Speicher aus und liefert den Merkmalsvektor V, der in dieser Weise erhalten worden ist.
Der Merkmalsvektor V wird anschliessend den kombinierten Überprüfungs- und Entscheidungsmitteln vorgelegt, dem Entscheider 100, von dem ein Schaubild in der Fig. 7 zu erkennen ist, um die Verfahrensschritte (5) und (6) der Fig. 1 auszuführen. Der Entscheider 100 umfasst einen Merkmalsüberprüfer 101 und eine Auswahlvorrichtung für das Maximum 102. Der Merkmalsüberprüfer hat so viele Eingänge In wie der Merkmalsvektor V Koeffizienten hat, im vorliegenden Beispiel daher 2 N, um alle Koeffizienten Vn aufzunehmen, die abgeleiteten Merkmalswerte. Und er weist so viele Ausgänge Um wie die Gesamtzahl M der zu erkennenden Zeichen auf. Die besagte Zahl M ist beispielsweise 34, falls der zu erkennende Zeichensatz aus den Zahlen, 0, 1, ..., 9 und den Grossbuchstaben A, B, ..., Z besteht. Für jeden Merkmalsvektor V, der am Eingang des Merkmalsüberprüfers 101 ansteht, bestimmt dieser letztere einen Wertvektor S = {S m m = 1, ..., M}, wobei jeder Koeffizient sm von diesen dann das Mass ausdrückt, gemäss dem der vorgelegte Merkmalsvektor V dem m-ten Zeichen des Satzes an zu erkennenden Zeichen entspricht. Die Koeffizienten des Wertvektors S werden über die Ausgänge Um zu dem Maximumwähler 102 übermittelt. Dieser Maximumwähler 102 bestimmt den grössten der Koeffizienten sm, und liefert ein Signal CH an seinem Ausgang 103, gemäss dem Zeichen aus dem zu erkennenden Zeichensatz, welches dem grössten Koeffizienten entspricht. Der Merkmalsprüfer ist vorzugsweise ein vielschichtiges neurales Netzwerk, zum Beispiel bestehend aus drei Schichten, aus Perzeptronen, wie diese beispielsweise in der Druckschrift [4] beschrieben worden sind. In der Fig. 7 ist der Merkmalsprüfer 101 nur als ein einschichtiges neurales Netzwerk mit einer Anzahl M an Perzeptronen dargestellt. Die drei Schritte, die in dem Merkmalsprüfer 101 zu unterscheiden sind, sind nämlich:
- ein Verteilungsschritt, mit dem Buchstaben T bezeichnet,
- ein Gewichtungsschritt, mit dem Buchstabe W bezeichnet, und
- ein Summationsschritt, mit dem Buchstaben Σ bezeichnet.
Die Merkmalswerte, die mit dem Merkmalsvektor V dem Merkmalsüberprüfer 101 vorgelegt werden, sind - wie abgeleitet - kontinuierliche Werte. Im Verteilungsschritt T wird jeder vorgelegte Wert vn als solcher mit Verteilungseinheiten tn (n = 1, 2 N) verteilt, indem derselbe Wert in einer vielfachen Weise vorgelegt wird, nämlich in M Richtungen, das heisst in so vielen Richtungen, wie es Perzeptronen gibt. Während des Gewichtungsschritt W wird jeder Merkmalswert vn in jeder Richtung m durch das Mittel eines Gewichtungsfaktors Wnm, aus einem Satz von Gewichtungsfaktoren {Wnm} ausgewählt. Dieser Satz von Gewichtsfaktoren bildet eine Dimensionsmatrix, die Gewichtsfaktormatrix, wobei n = 1, ..., 2 N die Anzahl von vorgelegten Merkmalswerten vn und m = 1, ..., M die Anzahl von zu erkennenden Zeichen aus dem Satz von zu erkennenden Zeichen ist. Mit der Hilfe der Gewichtsfaktoren wird ein Wert im Summationsschritt Σ für jeden von einer Anzahl M von Summatoren Cm bestimmt, welcher Wert die vorausgegangen erwähnten Koeffizienten sm des Summenvektors S bildet. Für den Summator am ist dieser Wert: sm - f (ΣWnm * vn), wobei die Summation über alle n = 1, ..., 2 N geht und f eine nicht lineare Funktion, wie zum Beispiel eine sigmoide Funktion darstellt. Dies wird in der Fig. 7 durch Pfeile für jede Verteilungseinheit tn für jeden der Summatoren σm angezeigt. Die Pfeile sind hier mit den zugehörigen Gewichtsfaktoren aus der Gewichtsfaktormatrix versehen.
Die Koeffizienten sm des Wertvektors S werden dem Maximumsselektor 102 zugeführt. Die Gewichtsfaktormatrix {wmn} ist in einem Speicher angeordnet, der dem Entscheider zugänglich ist. Die Koeffizienten dieser Matrix sind durch einen Trainingsalgorithmus vorbestimmt, welcher als "Zurückausbreitung enthaltener Algorithmus" bekannt ist (siehe zum Beispiel Druckschrift [4] insbesondere Kasten 6). In diesem Falle sind Zeichenmerkmale dem Entscheider von bekannten Zeichen aus einem Trainingssatz von bekannten Zeichen vorgelegt worden, welche mit der Hilfe des oben beschriebenen neuen Verfahrens abgeleitet worden sind. Wenn das Verfahren an einem grossen Testsatz an Material aus der Praxis (zum Beispiel 200'000) von leicht trennbaren handgeschriebenen Zeichen angewandt wird, kann ein Zeichenerkennungssystem, welches mit dem neuen Verfahren zur Ableitung der Zeichenmerkmalen "Distanz" und "Richtung" arbeitet, 99,3% der vorgelegten Zeichen erkennen. Falls nur das Zeichenmerkmal "Distanz" eingesetzt wurde, war die maximale Trefferquote 98,6%. Tabelle 1a Tabelle 1b Tabelle 2

Claims

1. Verfahren zur Ableitung von Zeichenmerkmalen in einem Zeichenerkennungssystem zum Erkennen von Zeichen, wie Buchstaben und Zahlen, mit einem Schritt, mit dem für jeden Punkt einer Vielzahl von Punkten in einer Bildebene von Bildpunkten, die ein Muster eines zu erkennenden Zeichens umfassen, Merkmalsdaten abgeleitet werden, die für den Abstand zum nächsten Grenzpunkt des Musters kennzeichnend sind, dadurch gekennzeichnet, dass die Vielzahl von Punkten einen Satz (R {Ri i = 1, ..., N}) von vorausgewählten Punkten (Ri), sogenannte Referenzpunkte, beinhalten und dass das Verfahren einen weiteren Schritt umfasst, in dem für jeden Referenzpunkt weitere Merkmalsdaten (H(Ri)) abgeleitet werden, die für die Richtung der Grenze zu dem unmittelbar benachbarten nächsten Grenzpunkt kennzeichnend sind.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Grenzpunkte Umrisspunkte eines gefilterten Umrisses (C1, C2) sind, wobei der gefilterte Umriss durch Schritte der Umrissverfolgung und des Fihterns erhalten wird, die dem besagten ersten Ableitungsschritt vorausgehen.

3. Verfahren nach Anspruch 1 oder Anspruch 2, dadurch gekennzeichnet, dass das Verfahren den Schritt umfasst, einen Merkmalsvektor (V = {vn} n = 1, ..., 2 N) aus den besagten Merkmalsdaten und den weiteren besagten Merkmalsdaten festzustellen, und wobei der Merkmalsvektor die Distanzdaten (D(Ri)) und die Richtungsdaten (H(Ri)) für jeden Referenzpunkt (Ri) als Vektorkoeffizienten beinhaltet.

4. Verfahren nach einem der Ansprüche 1, 2 oder 3, dadurch gekennzeichnet, dass die Anzahl der Referenzpunkte grösser als 70 und kleiner als 120 ist.

5. Verfahren nach einem der Ansprüche 1, 2, 3 oder 4, dadurch gekennzeichnet, dass der Satz an Referenzpunkten in der Bildebene zufällig verteilte Punkte umfasst.

6. Verfahren nach einem der Ansprüche 1, 2, 3 oder 4, dadurch gekennzeichnet, dass der Satz an Referenzpunkten in der Bildebene regelmässig verteilte Punkte umfasst.

7. Zeichenerkennungssystem zum Erkennen von Zeichen wie Buchstaben und Zahlen, wobei das System umfasst:

- Mittel zum Aufnehmen eines Bildmusters eines zu erkennenden Zeichens auf der Oberfläche eines Trägers,

- Merkmalsableitungsmittel zum Ableiten von Merkmalsdaten für eine Anzahl von Zeichenmerkmalen des zu erkennenden Zeichens aus dem besagten aufgenommenen Bildmuster,

- Überprüfungsmittel (101) zum Überprüfen der abgeleiteten Merkmalsdaten gegen zuvor erhaltene Ergebnisse auf einem Satz von bekannten Zeichen und zur Ausgabe überprüfter Ergebnisse,

- Entscheidermittel (102) zum Entscheiden auf der Basis der überprüften Ergebnisse, als welches bekannte Zeichen das zu erkennende Zeichen erkannt wird,

dadurch gekennzeichnet, dass die Merkmalsableitungsmittel (FD) Ableitungsmittel umfassen, um für jeden Punkt eines Satzes von vorab gewählten Punkten, sogenannten Referenzpunkten, in einer Bildebene des besagten aufgenommenen Bildmusters Merkmalsdaten, die für den Abstand zu einem nächsten Grenzpunkt des Musters kennzeichnend sind, und Merkmalsdaten abzuleiten, die für die Richtung der Grenze zu seinem nächsten Grenzpunkt kennzeichnend sind.

8. Zeichenerkennungssystem nach Anspruch 7, dadurch gekennzeichnet, dass das System weiterhin einen Umrissverfolger (CD, CF) beinhaltet, um einen Umriss eines zu erkennenden Zeichens aufzufinden und um eine Umrissbeschreibung des aufgefundenen Umrisses festzustellen, wobei die Ableitungsmittel so angeordnet sind, um für jeden Referenzpunkt (Ri) den Abstand (D(RQ) = d) zu einem nächsten Umrisssegment (k) und die Richtung (H(Ri)), zumindest als Annäherung, des nächsten Umrisssegmentes zu bestimmen.