DE1209339B - Anordnung zur Zeichenerkennung - Google Patents

Description

BUNDESREPUBLIK DEUTSCHLAND

DEUTSCHES

PATENTAMT

AUSLEGESCHRIFT

Int. Cl.:

Nummer:
Aktenzeichen:
Anmeldetag:
Auslegetag:

G06k

Deutsche KL: 43 a-41/03

1 209 339
J20889IXc/43a 25. November 1961 20. Januar 1966

Die Erfindung bezieht sich auf eine Anordnung zur Zeichenerkennung durch Vergleich von aus der Abtastung abgeleiteten Funktionen der zu erkennenden Zeichen mit Funktionen von Vergleichszeichen; sie beseitigt die dabei unter gewissen Urnständen mögliche Mehrdeutigkeit.

Die Wirksamkeit vieler Techniken zur Auswertung von Daten wird vergrößert, wenn Funktionen, Ableitungen der Daten benutzt werden, statt diese Daten unmittelbar zu analysieren. Dabei tritt jedoch die Schwierigkeit auf, daß diese Funktionen für manche Gruppen von Daten mehrdeutig sind. Ein Beispiel dafür sind Ableitungen von Funktionen, welche sich nur durch eine Konstante unterscheiden und damit identisch sind. Mit dem Verfahren nach der Erfindung sollen die Vorteile gewahrt bleiben, die durch die Auswertung von Funktionen gegeben sind; die einer solchen Auswertung anhaftende Mehrdeutigkeit soll jedoch vermieden werden.

Ein Anwendungsgebiet der Funktionserzeugung ist die Erkennung von Mustern (z. B. von gedruckten Zeichen), die erleichtert wird, wenn man gewisse Funktionen des Musters mit gleichen Funktionen von vorgegebenen Mustern vergleicht, statt das Muster unmittelbar mit dem vorgegebenen Muster zu vergleichen. Ein Beispiel für eine zu bildende Funktion ist die Autokorrelationsfunktion, die bei der Zeichenerkennung deshalb besonders wertvoll ist. weil sie von der Lage des Zeichens unabhängig macht. Zeichenerkennungsverfahren, welche Autokorrelationswerte vergleichen, sind zudem gegen Störwerte sehr unempfindlich. Aus dem erwähnten Gebiet der Zeichenerkennung wird z. B. auf die Zeichen »6« und »9«, »M« und »W«, »b« und »q«, »d« und »p« usw. hingewiesen. Wenn nun ein Muster durch Drehung um 180° in ein anderes übergeführt werden kann, ist die entstehende Autokorrelationsfunktion für jeweils ein solches Paar von Mustern mehrdeutig und die Identifizierung erschwert. Die Verwendung von Autokorrelationsfunktionen zur Zeichenerkennung wurde bereits vorgeschlagen und ist nicht Gegenstand der vorliegenden Erfindung.

Es ist schon vorgeschlagen worden, bei Verfahren zur Zeichenerkennung mit rasterhaftem Abtasten der Schwarz-Weiß-Werte die zu einem bestimmten Zeichen gehörenden Schwarz- bzw. Weißwerte über Koinzidenzschaltungen zusammenzufassen. Falls, bei gestörtem Zeichen, keine volle Übereinstimmung erzielbar ist, wird die Prüfung darauf beschränkt, ob die Anzeige, z. B. der Schwarz-Werte, Übereinstimmung ergibt. Bei Verfahren zur Zeichen-Anordnung zur Zeichenerkennung

Anmelder:

International Business Machines Corporation, Armonk, N. Y. (V. St. A.)

Vertreter:

Dipl.-Ing. H.E.Böhmer, Patentanwalt, Böblingen (Württ.), Sindelfinger Str. 49

Als Erfinder benannt:

William Lawrence McDermid, Rochester, N. Y.; '⁵ Harold Emanuel Petersen, Chappaqua, N. Y.; Glenmore Lorraine Shelton jun., Carmel, N. Y. (V. St. A.)

Beanspruchte Priorität:

V. St. v. Amerika vom 19. Dezember 1960 (76909)

erkennung mittels Erzeugung von Funktionen des zu erkennenden Musters ist ein solches Verfahren nicht anwendbar.

Um die Vorteile der Zeichenerkennung mittels Funktionserzeugung zu bewahren und trotzdem die mögliche Mehrdeutigkeit zu vermeiden, werden erfindungsgemäß aus einem eindeutigen Merkmal des Musters oder aus einer eindeutigen Teilfunktion des Musters eindeutige Hilfsfunktionen gebildet und diese zusammen mit der mehrdeutigen Autokorrelationsfunktion zur Identifizierung herangezogen. Gegenstand der Erfindung ist demnach eine Anordnung zur Zeichenerkennung durch Vergleich von durch Abtastung abgeleiteten Funktionen von Vergleichszeichen, wobei einige Funktionen der Zeichen mehrdeutig sein können, mit dem Merkmal, daß ein Funktionsgenerator vorgesehen ist, der zum Erkennen von Zeichen, die bei der Abtastung mehrdeutige Funktionen liefern, aus weiteren Merkmalen der betreffenden Zeichen Hilfsfunktionen bildet, und daß Vergleicher vorgesehen sind, die diese Hilfsfunktionen mit entsprechenden Vergleichshilfsfunktionen vergleichen.

Eine Autokorrelationsfunktion ist ein Maß für die Beziehung einer Funktion zu sich selber und ist damit ihrem Wesen nach lageunabhängig. Es

509 779/186

werde als identifizierendes Muster eine Matrix mit einzelnen, vorwiegend schwarzen oder weißen Feldern und den Koordinaten (x, y) angenommen; die Schwarz-Weiß-Verteilung hänge von der Lage des Musters ab. Dann gibt es eine Funktion/(x, y), die den Wert 1 hat für alle Fälle, in denen das Gebiet mit den Koordinaten (x, y) schwarz ist, und den Wert 0, wenn dieses Feld weiß ist. Die Autokorrelationsfunktion gibt die Zahl von Paaren schwarzer Felder an, die sich in gegebenem Abstand und gegebener Richtung voneinander vorfinden, und zwar für alle Abstände und Richtungen. Wenn (x. v) ein Punkt des Musters ist und χ + x\ y + y' ein anderer Punkt des Musters ist, der von dem erstgenannten und dem Betrag (x', y') entfernt ist, dann ist das Produkt (x, y) (x + x', y + /) = 1 nur dann, wenn beide Punkte schwarz sind. Da dieses Verfahren für alle Punktpaare des Musters durchgeführt wird, ist die Autokorrelationsfunktion D (x\ /) definiert als

D (x\ /) = Σ f{x, y)f(x + x\ y + /).

Weitere Merkmale der Erfindung gehen aus den Unteransprüchen hervor. Das nachfolgend beschriebene Ausführungsbeispiel wird durch Zeichnungen erläutert.

F i g. 1 ist das Blockschema eines eindeutigen Identifizierungssystems, und

F i g. 2 zeigt schematisch ein Ausführungsbeispiel.

Bei dem Identifizierungssystem der F i g. 1 ist das zugeführte Eingangssignal notwendigerweise in gewisser Hinsicht eindeutig. Das Eingangssignal gelangt zu einem Funktionsgenerator 101, der eine eindeutige Funktion / (Eingang) daraus bildet. Dieser Funktionsgenerator arbeitet analog einem Digital-Umsetzer, einem logarithmischen Generator od. dgl., die in Abhängigkeit von einem bestimmten Eingangssignal ein eindeutiges Ausgangssignal liefern. Dieser Generator dient dazu, das Eingangssignal mit der übrigen Schaltung verträglich zu machen. Wenn dieses bereits der Fall ist, kann der Funktionsgenerator 101 als Ganzes wegfallen. Die eindeutige Funktion/(Eingang) gelangt dann zu einem zweiten Funktionsgenerator 103, der für zwei oder mehr mögliche Eingangssignale mehrdeutige Ausgangssignale erzeugt. Es können dies z. B. Autokorrelations-Funktions-Generatoren, Integratoren oder Differentiatoren sein, die für zwei oder mehr bestimmte Eingangsfunktionen dieselbe Ausgangsfunktion erzeugen.

In einem Vergleicher 107 wird die Art der Ableitung der mehrdeutigen Eingangsfunktion / (Eingang), mit der ersten mehrdeutigen Ableitung des Vergleichswertes, / (Vl oder V2), die in einem Vergleichswertspeicher 105 enthalten ist, in Beziehung gesetzt. Wenn der Vergleich eine Ähnlichkeit ergibt, so wird den beiden UND-Schaltungen 109 und 111 eine mehrdeutige Ausgangsfunktion zugeführt. Die endgültige Feststellung der Identität des Eingangssignals wird von einem zweiten Vergleichsvorgang abhängig gemacht; dabei wird eine eindeutige Funktion des Einganges mit einer eindeutigen Funktion jedes Vergleichswertes verglichen. Der Funktionsgenerator 113 dient dazu, eine eindeutige Funktion /' (Eingang) zu den Vergleichern 115 und 117 zu liefern. Diese Funktion/' (Eingang) kann etwa eine einfache Auswahlschaltung sein, die einen eindeutigen Teil des Eingangssignals an ihren Ausgang abgibt. Den beiden Vergleichern 115 und 117 werden außerdem eindeutige Vergleichsfunktionen/' (Fl) und/' (F2) zugeführt. Einer der Vergleicher liefert daraus ein Signal zu den UND-Schaltungen 109 oder 111, wodurch das Eingangssignal eindeutig identifiziert ist.

Die F i g. 2 zeigt ein Blockschema einer Ausführungsform der Erfindung für ein System zur

ίο Zeichenerkennung. Die Lichtpunktabtaströhre 121 und die Photoelektronenröhre 123 liefern eine Funktion fs (χ, y) des Musters 125 auf der Matrix 127. Der Autokorrelations-Funktions-Generator 129 erzeugt daraus die Funktion Ds (x', /)* welche bei gewissen Mustern mehrdeutig ist. Beim vorliegenden Beispiel sollen die arabischen Ziffern 0 bis 9 identifiziert werden, und es kann unterstellt werden, daß die Ziffern 6 und 9 mehrdeutige Autokorrelationsfunktionen ergeben.

Der Vergleichswertspeicher 131 liefert für jedes Muster (jede Ziffer) Autokorrelationsfunktionen Dr (x\ /). Für die Fälle 6 und 9 wird nur eine Funktion, Dr »6« oder »9« (x', y'), geliefert. Der Vergleicher 133 gibt eine Anzeige für die Identität der Muster aller eindeutigen Fälle und eine Anzeige »6« oder »9« für die mehrdeutigen Muster.

Bei einem ersten Ausführungsbeispiel liefert ein Funktionsgenerator 135 eine eindeutige Funktion / (Muster) aus der Funktion/· (x, y). Bei einem zweiten Ausführungsbeispiel bildet der Funktionsgenerator 137 aus einem eindeutigen Teil der Autokorrejationsfunktion des Musters eine eindeutige Funktion / (Muster).

Die eindeutige Funktion / (Muster) gelangt zu zwei Vergleichern 139 und 141. Diesen beiden Vergleichern werden außerdem mit/ (V6) bzw./ (F9) bezeichnete Funktionswerte zugeleitet. Diese letztgenannten Funktionswerte stammen aus dem Vergleichswertspeicher und werden aus eindeutigen Teilmerkmalen der insgesamt mehrdeutigen Funktionen (von »6« und »9«) abgeleitet. Solche Teilmerkmale könnten beispielsweise die Anzahl der vom Muster belegten Rasterelemente sein, die bei der Abtastung des Musters nach dem Auftreten des ersten belegten Rasterpunktes innerhalb einer bestimmten Anzahl folgender Rasterpunkte angetroffen werden. Dieses Teilmerkmal ist für die gewählten beiden Muster (»6« und »9«) mit insgesamt mehrdeutiger Anzeige unterschiedlich; diese Teilmerkmale sind jedoch nur im Zusammenhang mit der Betrachtung und Auswertung des gesamten Musters zur Identifizierung ausreichend. Einer der Vergleicher 139 und 141 liefert dann den angeschlossenen UND-Schaltungen 143 und 145 ein Signal, welches die endgültige, eindeutige Anzeige für das abgetastete Muster bildet.

Claims (2)

Patentansprüche:

1. Anordnung zur Zeichenerkennung durch Vergleich von aus der Abtastung abgeleiteten Funktionen der zu erkennenden Zeichen mit Funktionen von Vergleichszeichen, wobei einige Funktionen der Zeichen mehrdeutig sein können, dadurch gekennzeichnet, daß ein Funktionsgenerator (113) vorgesehen ist, der zum Erkennen von Zeichen, die bei der Abtastung mehrdeutige Funktionen liefern, aus weiteren

5 6

Merkmalen der betreifenden Zeichen Hilfsfunk- denden Funktionsgenerator (135 oder 137) als

tionen bildet, und daß Vergleicher (115, 117) Eingangssignal die Eingangsfunktion \f_s (x. v)]

vorgesehen sind, die diese Hilfsfunktionen mit oder eine daraus abgeleitete Funktion zugeführt

entsprechenden Vergleichshilfsfunktionen ver- wird.

gleichen. 5

2. Anordnung nach Anspruch ■ 1, dadurch In Betracht gezogene ältere Patente:

aekennzeichnet. daß dem die Hilfsfunktion bil- Deutsche Patente Nr. 1 114 349, 1 180 560.

Hierzu 1 Blatt Zeichnungen

509 779/186 1.66 © Bundesdruckerei Berlin