DE2064602A1 - Verfahren und Anordnung zur Zeichentrennung bei der maschinellen Zeichen erkennung - Google Patents

Description

Böblingen, 29. Dezember 1970 bt-rz

Anmelderin: International Business Machines

Corporation, Armonk, N.Y. 10504

Amtliches Aktenzeichen: Neuanmeldung Aktenzeichen der Anmelderin: Docket RO 969 005

Verfahren und Anordnung zur Zeichentrennung bei der maschinellen Zeichenerkennung ^

Die Erfindung betrifft ein Verfahren bei der maschinellen Zeichenerkennung zur Trennung aneinandergrenzender oder sich überdeckender Zeichen, die mittels mindestens eines Abtasters und eines Wandlers in eine zeitabhängige und/oder räumlich verteilte Reproduktion umgewandelt werden, die in einem Zwischenspeicher gespeichert wird.

Die meisten Anordnungen zur Zeichenerkennung sind so aufgebaut, daß jeweils nur einzelne, isolierte Zeichen erkannt werden können. Demzufolge ist es notwendig, eine sichere Anzeige für Anfang und Ende eines Zeichens zu haben. Abgesehen von der maschinellen Erkennung von zusammenhängend geschriebener Handschrift - dabei tritt das Problem wohl im größten Umfang auf -, ergeben sich auch bei der Abtastung und Erkennung maschinell erstellter Zeichen Schwierigkeiten beispielsweise durch fehlerhaften Druck oder unkorrekten Transport des Aufzeichnungsträgers. Sobald sich zwei zu erkennende Zeichen berühren, ist mit dem größten Teil der derzeitig handelsüblichen Zeichenerkennungsmaschinen eine Erkennung nicht mehr möglich.

Er> wurde bereits vorgeschlagen, bei gedruckten Zeichen, die üb-Licherwelse eLne bestimmto Zeichenbreite nicht überschreiten, die Ι.ΪΛ cxv, ι iinq bel.'ipielHwel t!f.i nach Durch Lauien einnr Anzahl von Bali-

ι (ι a ti /9 / μ a 5 "" ^0RK3INAL

nen, bzw. nach einer bestimmten Abtastzeit abzubrechen, um damit eine hintere Zeichengrenze zu definieren. Dieses Verfahren führt möglicherweise zu einer Erkennung des ersten von zwei ineinander gedruckten Zeichen, macht jedoch die Erkennung des zweiten sehr schwierig, wenn nicht gar unmöglich, da der vordere Teil des zweiten Zeichens nicht mehr berücksichtigt wird. Eine andere bereits vorgeschlagene Möglichkeit zur Zeichentrennung besteht in der Ausnutzung bestimmter, durch einen Grenzwert definierter Dichteschwankungen zwischen zwei sich berührenden Zeichen. Zweifel los ist hierdurch eine gewisse Verbesserung möglich, wird der Grenzwert jedoch relativ hoch angesetzt, um auch stark miteinander verbundene Zeichen noch trennen zu können, so tritt möglicherweise auch eine Trennung einzelner relativ schwach gedruckter Zeichen auf, die eine Erkennung solcher Zeichen unmöglich macht.

Aufgabe der Erfindung ist es, die genannten Nachteile der bereits vorgeschlagenen Verfahren und bekannten Anordnungen zu vermeiden und ein bei geringstmöglichem Aufwand sicheres Verfahren zur Trennung zusammenhängender oder sich überdeckender Zeichen anzugeben.

Diese Aufgabe wird bei einem Verfahren der eingangs genannten Art dadurch gelöst, daß durch Abtastung des Zwischenspeichers und gegebenenfalls des Wandlers räumlich benachbarte Teilflächen spalten- oder zeilenweise verglichen werden, daß eine spalten- bzw. zeilenweise oder zeichenweise Summierung der Vergleichsergebnisse erfolgt, daß diese Teilsummen mit Gewichtungskoeffizienten bewertet, und nach Abtastung jeweils einer Spalte oder Zeile die Gesamtsumme gebildet wird, abhängig von deren Größe eine Zeichentrennung durchgeführt wird.

Verfahren der vorgeschlagenen Art ist uncibhängig von der Zeichenform, da es von der prinzipiellen Voraussetzuncj ausgeht, daß das IiLnlenlntef/ral um eLn Isoliert: ütehencles Kelchen Muli i;t FUr jedes von zwei α Loh berührenden "eichen Uj t dLe»r»r?.-j Inteqt al jedoch ungleich NaLL, i.eine (Jrö/Je bemLiSt :>lch lUmn n.irh dar tin

Docket; Fid < >οί) 005

1 0 «j B 2 Ü / 1 I 9 S

BAD

der Berührungsstelle herrschenden Zeichendichte. Durch entsprechende Gewichtung der Einflußgrößen läßt sich ein Schwellwert bestimmen, der für eine exakte Zeichentrennung in einer Großzahl der Fälle sich berührender Zeichen sorgt.

Eine vorteilhafte Anordnung zur Durchführung des Verfahrens in einer Vorrichtung zur maschinellen Zeichenerkennung mit einer die zu erkennenden Zeichen abtastenden Abtastvorrichtung und einem an diese angeschlossenen Wandler, einem Zwischenspeicher zur Aufnahme einer Reproduktion der abgetasteten Zeichen und einer Zeichenerkennungsschaltung zeichnet sich dadurch aus, daß zumindestens einzelne Elemente des die elektrische Zeichenreproduktion aufnehmenden Zwischenspeichers mit Vergleichsschaltungen und deren Aus gangs leitungen wiederum mit einer ein Zeichentrennsignal nach Maßgabe vorgebbarer Bedingungen erzeugenden Schaltungsanordnung verbunden sind, und daß die das Zeichentrennsignal führende Ausgangsleitung der Schaltungsanordnung an die Zeichenerkennungsschaltung angeschlossen ist.

Weitere Merkmale der Erfindung können den Patentansprüchen, Einzelheiten den nachfolgend beschriebenen Ausführungsbeispielen der Erfindung mit den zugehörigen Zeichnungen entnommen werden. Auf den Zeichnungen zeigen:

Fig. l ein Blockschaltbild eines Zeichenerkennungssystemes, das eine Einrichtung zur Zeichentrennung gemäß der Erfindung enthält,

Fig. 2 zwei sich überschneidende Zeichen,

Fig. 3 die die Zeichenmatrix bildenden Schieberegister,

Fig. 4 ein Blockschaltbild der logischen Schaltung zur Bestimmung dreier Mustermerkmale,

Fig. 5 drei Beispiele von sich berührenden Zeichen,

Docket KO 969 005 -,O₉₈₂₉/ 1195

Fig. 6 ein Blockdiagramm der logischen Schaltung zur Bestimmung dreier weiterer Mustermerkmale des abgetasteten Zeichens,

Fig. 7 ein Ablaufdiagramm für die Ausführung des Trennalgorithmus ,

Fig. 8 ein Blockdiagramm der speziell zur Durchführung des Trennalgorithmus geschaffenen Bauteile,

Fig. 9 zwei sich überschneidende Zeichen,

Fig. 10 sich stark berührende Zeichen mit einer hohen Druckdichte und

Fig. 11 ein Blockdiagramm einer Analogschaltung zur Ableitung der Trennparameter.

Fig. 1 zeigt in einem grundlegenden Diagramm ein System zur Zeichenerkennung, welches eine Einrichtung zur Zeichentrennung enthält. Es wird angenommen, daß die Video-Eingangssignale von einem bekannten Raster-Abtastsystem kommen, welches vertikal von unten nach oben und von rechts nach links abtastet, und daß diese Signale auf einen Videodetektor 10 gegeben werden, W dessen Ausgangssignale auf einen Bildspeicher 14 geleitet werden. Der Bildspeicher 14 speichert die das abgetastete Zeichen darstellenden Videobits in Matrixform. Eine Trenneinheit beeinflußt das gespeicherte Bild so, daß sich berührende Zeichen getrennt werden. Die Zeichenerkennungseinheit 16 stellt entsprechend den Erkennungsalgorithmen die Identität von in der Matrix des Bildspeichers 14 gespeicherten Zeichen fest. Die Trennschaltung 12 bestimmt mit Hilfe eines nachfolgend noch zu beschreibenden Algorithmus den geeigneten Zeitpunkt, an welchem die Trenneinheit eingeschaltet wird. Auf diese Weise wird die Trenneinheit, die sich stark berührende Zeichen trennen kann, im Mittelteil eines einzelnen Zeichens nicht eingeschaltet und kann somit ein Zeichen nicht in zwei Hälften trennen.

Docket RO 969 005 _10ä829/1196

^ϊ1: " "■ ·' ¹I"-¹¹" "■■■■■"■'"■: '^:·-' ■' ^:'··-:· ■■■.■■■■ ·' : ' ■■:■■■ ■ ■■ ■ ■■ .■■ r , ;i,_0!-

Ein einfaches Beispiel für zwei sich berührende Zeichen ist in Fig. 2 gegeben. Die Zahlen an der Unterkante des Zeichens "O" geben die Anzahl der vertikalen Abtastungen an. Hinter der 30. Abtastung, der letzten des Zeichens O, folgt in einem System mit vollständig getrenntem Zeichen eine leere Abtastung. Die beiden Zeichen 0 und N sind jedoch nicht durch eine Leer-Abtastung voneinander getrennt, da sie sich überschneiden. Die das Zeichen darstellende digitalisierte Videoinformation wird auf ein serielles Schieberegister der in Fig. 3 gezeigten Art geleitet und dort gespeichert. Die seriell angeordneten Schieberegister sind genauso lang wie eine vertikale Abtastbahn. Das äußerste ^ linke Schieberegister stellt die laufende Abtastung η dar, das ™ nächste Schieberegister die Videosignale von der Abtastung n-l usw. Die obersten drei Registerpositionen sind vertikal durch die Buchstaben A, B und C gekennzeichnet. Die Horizontalpositionen sind durch die Abtastnuramern n, n-l, n-2 bezeichnet. Die Bitinformation im Speicherschieberegister der Fig. 3 wird dazu benutzt, drei Mustermerkmale zu erzeugen, die die Grundlage für den Trennalgorithmus bilden. Bevor der Trennalgorithmus genauer beschrieben wird, wird die Merkmalbestimmung im Zusammenhang mit den Fign. 2, 3 und 4 beschrieben.

In dieser Beschreibung werden Ausdrücke und Zeichen mit folgender Bedeutung benutzt: ^

P = die Anzahl der Zeichenkantenbits, d.h. der Ober- bzw. Untergrenze einer Abtastspur. Anders ausgedrückt stellt die Zahl P denjenigen vertikalen Teil der Abtastspur dar, der außerdem in Abtastrichtung betrachtet die Vorderkante eines Zeichens sein kann. In der Spur 12 der Fig. 2 erreicht die Anzahl der Zeichenbits, d.h. die vertikale Dichte L den Wert 5. Da die ganze vertikale Linie des in der Spur 12 aufgenommenen Zeichens außerdem eine Ober- und Untergrenze eines Zeichens ist, ist der Wert P tür die Abtastspur 12 ebenfaLls gleich 5.

/lit dem Buchstaben N wird die Anzahl der F'eblbits bezeichnet, uie liürteutunfj der Werte P iür dJU· ZeLchenkantenbits eLner

Docket IiO Of.') (X)¹,

1 ü il 8 Ί ^f) / 1 1 B 5 ^ÖAO

206A602

Abtastspur, N für die Fehlbits und L für die Zeichenbits gehen aus einer Betrachtung der Abtastspur 14 in Fig. 2 hervor. Der Wert L₁₄ ist 14, da bei dieser Abtastung 14 schwarze Bits abgetastet werden. Zwei dieser schwarzen Bits bilden einen Teil der Begrenzung eines Zeichens, und zwar das oberste und das unterste schwarze Bit. Demzufolge ist P.. « 2. In der Spur 14 treten keine Fehlbits auf und somit ist N₄ » O. In der Abtastspur 15 ist jedoch N₅ = 11, da 11 Bitstellen, die in der vorigen Abtastspur von schwarzen Bits belegt waren, jetzt nicht durch schwarze Bits belegt sind.

Der Trennalgorithmus der vorliegenden Erfindung basiert auf den folgenden Forraeessungen des Zeichens. Wenn «!genommen wird, daß die Zeichen vertikal von unten nach oben und horizontal von rechts nach links abgetastet werden, so wird das digitalisierte Videosignal in das Abtastspeicher-Schieberegister der Fig. 3 verschoben und die Messungen P, N und L entsprechend der in Fig. 4 gezeigten Schaltung vorgenommen. Die grundlegenden Formbeziehungen, die durch ein binäres Muster erfüllt werden, sind in den folgenden Gleichungen 1 und 2 gegeben. Für jede Abtastung η des Musters gilt

£ ³ j=0 ^{3 n}

an der durch Leer-Abtastungen definierten natürlichen Trennstelle ist

η η

N ^J

(2) I P. ~ I N = O

j=0 ^J

j=0
erfüllt.

Die Gleichungen 1 und 2 bedeuten, daß am Ende einer jeden Abtastung des Musters die Summe der Zeichenkantenbitwerte P. abzüglich der Summe der Fehlbitwerte N.. gleich der Anzahl von Zeichenbits in der Abtastung η ist. Die Gleichung 2 ist erfüllt, sobald die Abtastung η Leer ist und als solche einen Trennungs-

Docke t RO 960 ΟΟΰ

10 9 8 2 9/ I T95

BAD ORIGINAL

■Η ■'(, !!^»lllllliliPIIIIFill ¹¹V

206A602

ρunkt definiert. Das bedeutet, daß die Hinterkante aller Huster-Abtastspuren, die vorher in diesem Zeichen gefunden wurden, überschritten wurde. Die unten stehende Tabelle 1 zeigt die aus den Abtastungen 12 bis 31 des in Fig. 2 gezeigten Zeichens 0 resultierenden Parameter.

	Σ»,	Tabelle	1	Ln	N η	*
an (n)	0	ΣΡ3	5	0	5
12	0	5	12	0	7
13	0	12	14	0	2
14	11	14	6	11	3
15	14	17	5	3	2
16	16	19	4	2	1
17	17	20	5	1	2
18	18	22	4	1	0
19	18	24	4	0	0
20	18	24	4	0	0
21	18	24	4	0	0
22	18	24	4	0	0
23	18	24	6	0	0
24	20	24	4	2	0
25	22	24	4	2	2
26	22	26	6	0	12
27	24	28	16	2	12
28	28	40	12	4	0
29	32	40	9	4	1
30	40	41	2	8	1
31	42

Gleichung 1 ist immer erfüllt, am Ende der Abtastung ist jedoch Gleichung 2 nicht erfüllt, weil die Zeichen sich überschneiden. Wenn die Abtastung 31 leer wäre, wäre die Gleichung 2 erfüllt und würde eine natürliche Trenneteile definieren.

Da die Abtrennung bei Berührung oder Überschneidung von Zeichen nicht auf der Erfüllung der Gleichung 2 basieren kann, basiert der Zeichen-Trennalgorithmus auf einer Schwellenwertfunktion T, die aus den Gleichungen 1 und 2 abgeleitet und allgemein durch die Gleichung 3 beschrieben ist.

(3) T - f(I₀U[P]) - f (J₀V[N]) - f(I_-W[L]) - X worin

Docket RO 969 005

109829/11SS

C = Summe über dem Zeichen
S = Summe über der Abtastung
U, V, W, X = positive Gewichtungskoeffizienten und P, N, L = Meßwerte der allgemeinen Form ähnlich den unten und in Fig. 4 gezeigten sind.

Die Gleichung 3 besagt, daß der Schwellenwert T eine Funktion ist der Summe der Zeichenkantenbitwerte über das ganze Zeichen, gewichtet durch den Faktor U, abzüglich der Summe der Fehlbitwerte über das ganze Zeichen, gewichtet durch den Faktor V, abzüglich der durch den Faktor W gewichteten Bitdichte der gegenwärtig abgetasteten Spalte und einer zusätzlichen Gewichtung durch den Koeffizienten X. Bei der Benutzung der Gleichung 3 zur Trennung in einem speziellen Anwendungsbeispiel wird durch Wahl der Meßwerte P, N und L und durch eine veränderliche Steuerung der Gewichtungskoeffizienten über das Zeichen der Schnittbereich mit seinem Anfang in die erste Abtastung gelegt, in welcher T kleiner gleich 0 ist.

Bevor spezielle Beispiele für den Trennalgorithmus und das Gerät zur Ausführung dieses Algorithmus gegeben werden, werden einige allgemeine Betrachtungen über die Zeichengeometrie und Form in Bereichen angestellt, in denen Schnitte auftreten können. Einige Beispiele für sich berührende Zeichen sowie die erste Abtastung, bei der eine Trennung zulässig ist, sind in Fig. 5 gezeigt. Für Zeichen, die mit Vertikallinien auf der linken Seite enden, wie z.B. das E in der obersten Zeile der Fig. 5, kann die Schnittstellen-Schwellenfunktion in einem bestimmten Abstand von der linken vertikalen Linie erfüllt werden, wenn der Koeffizient V der N-Messung in diesem Bereich erhöht wird. Diese Erhöhung ist erforderlich, da die Summe der N-Werte allein sehr klein ist, wenn das berührende Zeichen in einer linken vertikalen Linie endet.

Bei Betrachtung des letzten Zeichens N in der mittleren Zeile in Fig. 5 stellt man fest, daß das beendende Merkmal imSchnittbe-

Docket RO 969 005

10 9 8 2 9/1195 _t

Hjllliijlügijllj !'''[i; ■■» ■■■■ =■■!: 'Sii¹ "Ί¹;¹¹"¹ ■■ f

reich stark verschleiert ist. Der Teil der Verbindung rauB daher durch den Ausdruck W(L) und den Ausdruck X subtrahiert werden, wenn man auf den Schnittbereich stößt. Das Zeichen A in der untersten Zeile der Fig. 5 zeigt im Schnittbereich eine abnehmende Dichte des Bitmusters. Die durchgezogenen senkrechten Linien mit den Pfeilen an den Enden bezeichnen die Bereiche, in denen ein Schnitt zuerst erzeugt werden könnte. Der tatsächliche Schnitt erfolgt aber einig« Abtastspuren weiter links von jeder senkrechten Linie.

Allgemeine Merkmale des Sahnittberelches von Zeichen können wie folgt zusammengefaßt werden: f

1. N-Werte treten häufiger auf, da die Zeichen-Hinterkanten eine Erhöhung ihres Koeffizienten in der Mähe des Schnittbereiches herbeiführen;

2. P-Werte sind in einem Schnittbereich unwahrscheinlich, da sie Vorderkanten eines Zeichens bezeichnen. Diese Tatsache legt den Einschluß eines Sperrausdruckes nahe, der auch P-Summen über eine Abtastung enthält;

3. Die Bitdichte L nimmt ab, da das Zeichen zu Ende geht;

4. Die Bitdichte in der ersten Abtastung des Abschnittes ist Λ wahrscheinlich relativ zur Zeichenhöhe groß, z.B. bei sich berührenden O¹S.

Anschließend wird ein Beispiel für eine besondere Formulierung des Trennalgorithmus betrachtet. Die Grundmessungen P, N und L erfolgen gemäß der Definition durch die in Fig. 6 gezeigte Schaltung. Diese unterscheidet sich von der in Fig. 4 gezeigten Schaltung zur Erzeugung derselben Parameter dadurch, daß zusätzlich die horizontale UND-Verknüpfung der schwarzen Bits in der P- und L-Messung eingeführt wurde, um die Auswirkungen einzelner ein Bit breiter Störungen auf die Meßergebnisse zu reduzieren. Bei Verwendung der UND-Form der P- und N-Messungen ist die Differenz einheitlich gewichteter P-N-Werte nach jeder Abtastung im

Docket RO 969 0O5 - η _Λ ο -> η / 1 1 α G

109829/1195

Zeichen gleich der Anzahl von UND-Blts zwischen den Abtastungen η und n-1. 01· L-Meseung hat aus zwei Gründen die dargestellte Form. Erstens treten L-Werte In solchen Bereichen des Musters häufiger auf, die durch eine abnehmende Dichte an schwarzen Bits gekennzeichnet sind und zweitens wird ihr Auftreten reduziert proportional zur Anzahl der horizontalen Linienelementen, die in der vertikalen Abtastung auftreten. Basierend auf den Parametermessungen durch die in Fig. 6 gezeigte Schaltung kann ein speziell·* Beispiel der Trenn-Schwellenwertfunktion, die in der unten stehenden Gleichung 4 gegebene Form annehmen.

(41 T_n -

worin η » Zahl der Abtastungen seit Zeichenanfang

U. » 1 V=I+ 0,05(F) + O,O3(F) Y_n - 0,5

W_n - 0,8 + 0,03(F)

X_n = F

Die für die Gewichtungsfunktionen gewählten Werte sind Erfahrungswerte. Die Gewichtungsfunktionen V, W und X sind abhängig von den Veränderlichen F und F veränderlich. Die Veränderlichen F und F sind selbst wieder von einer Rückkopplungsbedingung abhängig, die mit CFR bezeichnet ist. Die unten zu definierenden Werte CFR und somit die Werte F und F sind günstige Gewichtungsfunktionen, die sich auf die Formparameter beziehen. Sie sollen eine Trennung an der Hinterkante des Zeichens wahrschein licher machen. Die Rückkopplungsbedingung CFR ist durch die Gleichung 5 definiert.

Docket RO 969 005 _{Λ Λ} _. _{ÖAn nolfMM}..

109829/119S ^BAD ORIGINAL

¹¹ =:: .-■■. - :■:■■! -ι: ■■:!!! fi::: ;■■■ .

206Α602 - li -

(5) CFR = CPR , + 1, wenn Y (U. [Ρ.Ί-V. [N.1-3F) >1,5

η η-1 .^₁ DD JJ

η
_n = CFR_n-1, wenn J (U^ [P.]-V. [ϊ^]-3F) £1,5

η CFR_n =

worin ^CFRo ~ °

Aus Gleichung 5 ist zu ersehen, daß diese Funktion ansteigt, wenn die gesamte Vorderkantenlänge um einen bestimmten Betrag größer ist als die gesamte Hinterkantenlänge (beide gewichtet). Die Gewichtungsfunktionen F und F sind durch die nachfolgenden Λ Gleichungen 6 und 7 definiert.

(6) F=O wenn CFR <10

η η

F = CFR -10 wenn CFR >10
η η η—

worin F=O

(7) F = F + 1 wenn CFR >1 und wenn CFR . = CFR

η η~1 η— η-1 η

F=F, wenn CFR = CFR , + l η η-1 η n-1

worin F=O %

Die Rückkopplungsbedingung wird am Ende einer jeden Abtastung yemessen, während der Abtaster über das Zeichen läuft. Für jede Abtastspur, nach der die Beziehung in Gleichung 5 erfüllt ist, wird die CFR-Zahl um Eins erhöht. Nach den ersten zehn Rückkopplungsanforderungen wird F jedesmal um Eins erhöht, wenn CFR erhöht wird. Die Funktion F wird nach jeder Abtastung erhöht, wenn CFR nicht erhöht wird, vorausgesetzt, daß CFR mindestens einmal für dieses Zeichen erfüllt wurde.

Die gewichtete Summe von P-N (Gleichung 5) über das Zeichen bleibt groß, wenn entweder das digitalisierte Videomuster stark ist oder

Docket RO 969 005

109829/1196

sich aus starken horizontal verlaufenden Linien zusammensetzt, wie z.B. beim Zeichen S. Große P-N-gewichtete Summen zeigen einen hohen Grad von Verbundenheit an und eine größere Wahrscheinlichkeit einer schwierigeren Trennung. In diesem Fall wird der "starke" Rückkopplungsausdruck S schneller vorgeschaltet. Auf der anderen Seite führt eine weniger starke Verbundenheit dazu, daß der "leichte" Rückkopplungsausdruck P schneller vorgeschaltet wird. Aus Gleichung 4 ist zu ersehen, daß die Rückkopplungsparameter F und F in den negativen Mengen der Schwellenwertgleichung enthalten sind. Der "starke" Rückkopplungsparameter F senkt den Schwellenwert in einem größeren Ausmaß als der "leichte" Rückkopplungsparameter F. Zu Beginn der Abtastung eines Zeichens ist der Wert T im wesentlichen gleich der Summe der P-Werte, d.h. der Zeichenkantenbits über das Zeichen, abzüglich der Summe der Fehlbitwerte N über das Zeichen zuzüglich eines Faktors, der auf die Differenz zwischen den Zeichenkantenbits und der Dichte in der letzten Abtastung bezogen ist. Wenn die Verbindung groß ist (Zeichen mit großer Dichte), ist zwar die Differenz zwischen dem P- und dem N-Wert hoch, der Wert T wird jedoch durch den Rückkopplungsparameter F erniedrigt.

Die eigentliche Berechnung des Wertes T kann entweder durch einen extra hierfür programmierten Digitalrechner oder durch einen Analogrechner vorgenommen werden. In Fig. 7 ist ein zur Durchführung einer solchen Berechnung mit einem allgemeinen Digitalrechner geeignetes Programm-Ablaufschema gezeigt. Fig. 7 zeigt die Berechnungsfolge für die Trenn-Schwellenwertfunktion während des Abtastung eines Zeichens in Echtzeit. Das Ablaufdiagramm ist im wesentlichen selbsterklärend/ da jeder Block die durchgeführte Rechenfunktion anzeigt, wobei die ursprünglichen Blocks die Anfangswerte der Gewichtungsfunktionen wiedergeben. Der grundlegende Rechenzyklus pro Abtastung kann in drei aufeinanderfolgende Operationen unterteilt werden. Beginnend zur Startzeit wird die Berechnung eingeleitet durch Setzen der Messungskoeffizienten auf ihre ersten Bedingungswerte. Zuerst wird das Zeichen während der Verschiebungszeit abgetastet. Das digitalisierte Video-Abtast-Signal wird durch den Mess-Matrixbereich in das

Docket RO 969 005

10 9 8 2 9/1195

BAD ORIGINAL

^Abtastspeicher-Schieberegister eingegeben. Das gestattet die Berechnung der Parameter P, N und L sowie die gewichtete Summe von P-N über dem Zeichen für diese Abtastung. Im zweiten Schritt werden während einer letzten Bitzeit des Abtastzyklus die Rückkopplungsbedingungen CFR fortgeschrieben. Wie z.B. aus Fig. zu ersehen ist, wird CFR um Eins erhöht, wenn die P-N-Suinme über dem Zeichen größer als 1,5 + 3F ist. Sobald CFR größer als 10 ist, wird der Rückkopplungsparameter F dann um Eins erhöht, wenn CFR um Eins zunimmt. Entsprechend dem neuen Wert von F wird dann auch gemäß dem Bedarf für die Gleichung der Wert für X und V fortgeschrieben. Wenn die Summe P-N nicht größer als 1,5 + 3F, CFR jedoch größer als Null ist, wird F um Eins erhöht. Demzu- ä folge werden auch die Werte für V und W entsprechend erhöht. Schließlich wird in der ersten Bitzelt der Abtasterrückführung, nachfolgend Entscheidungszeit genannt, die Schwellenwertfunktion P berechnet, um zu ermitteln, ob diese Trennungsanforderung erfüllt ist. Die Trennungsanforderung ist erfüllt, wenn der Wert P kleiner oder gleich Null ist. Wenn die Trennungsanforderung nicht erfüllt ist, wird der Wert n, der die Abtastungszahl darstellt, um Eins erhöht und die Berechnung bei der folgenden Abtastung fortgesetzt. Wenn die Trennungs-Schwellenwertanforderung erfüllt ist, beginnt die Berechnung für das neue Muster bei der ersten der Trennung folgenden Abtastung. Der Rest der Taster-Rücklaufzeit wird für die Rückstellung benötigt.

Fig. 8 zeigt ein Blockdiagramm der Bauteile zur Durchführung des Trennalgorithmus und zur Durchführung der Trennung. Das gezeigte Gerät arbeitet mit Leistungsverstärkern, Vergleichern, Analogschaltern und zugehörigen Verknüpfungsschaltungen. Die an den Eingängen der Leistungsverstärker 101, 103, 104, 107, 108, 115, 116 und 119 erscheinenden Zahlen stellen die entsprechenden Gewichte dar, die den Spannungen auf der zugehörigen Leitung beigemessen werden. Die Leistungsverstärker 103, 107, 115 und 118 fungieren als Integratoren, die Leistungsverstärker 111 und 116 als Summierungsschaltungen, der Leistungsverstärker

Docket RO 969 005

109829/1195 BAD ORIGINAL

108 als Null-Grenzsumraierer durch die in die Rückkopplungsschleife gelegte Diode mlO9 und die Verstärker 104 und 119 als Spannungsvergleicher. Die Analogschaltung 102, 106, 110, 114 und 117 werden nur benötigt, wenn die Verknüpfungsebenen nicht hinreichend konstant gehalten werden können, um als Analog-Bezugssignale verwendet zu werden. Der Ausdruck "Analogschalter" oder "analoges Tor" wird ebenfalls für diese Einheit verwendet.

Das Ausgangssignal des Vergleichers 104 wird als richtig (echt) angesehen, wenn die Summe der analogen Eingänge negativ ist. Das Ausgangssignal des Vergleichers 119 wird als echt angesehen, wenn die Summe der analogen Eingänge positiv ist. Die Analogschalter 102, 110 und 117 haben analoge Ausgänge, die dem analogen Eingang gleich sind, wenn die Verknüpfungssteuerung eingeschaltet ist. Ganz allgemein sind die durch ausgezogene Linien dargestellten Verbindungen analoge Signale und die durch gestrichelte Linien dargestellten Verbindungen digitale Signale. Am Ende einer Abtastung vor Beginn eines neuen Zeichens wird das System dadurch eingeschaltet, daß die Integratoren 102, 107, 115 und 118 durch Steuerung ihrer Rückstelleingänge R auf 0-Ausgangswerte zurückgestellt werden. Die relativen Verstärkungen aller Eingänge zu den Analogkomponenten sind in normalisierten Einheiten dargestellt. Vor Abtastung der ersten Abtastspur eines Zeichens sind die Anfangsbedingungen des Systems folgende: Der Ausgang des Summenverstärkers 116, -W, ist gleich -0,8 Einheiten, da der Eingang F Null ist. Der Ausgang des Integrators 103, der die Summe über dem Zeichen der gewichteten P-N-Messungen erzeugt, ist Null. Der Ausgang des Integrators 118, der die gewichtete Summe durch die Abtastung der P-Messung mißt, ist Null. Der Ausgang des Integrators 107, der die Summe der verbindenden Rückkopplungsanforderungen CFR über dem Zeichen erzeugt, ist Null. Der Ausgang des Integrators 115, der die Summe von F über dem Zeichen erzeugt, ist Null. Der Ausgang des Grenzsummierers 108 ist Null, da sein einziger Eingang +10 Einheiten hat. Die Diode

109 begrenzt den invertierten Ausgang des Grenzsummierers 108 nur auf positive Werte. Da die Summe der Eingänge positiv ist, ist somit der Ausgang Null.

Docket RO 969 005

109829/1195

206A602

Die gewichtete Summe der in der laufenden Abtastung auftretenden Messungen wird über die Analogschalter 102, 110 und 117 an den Ausgängen der Integratoren 103 und 118 summiert. Während der Zeit des letzten Bits D-I der laufenden Abtastung wird das UND-Glied 105 eingeschaltet. Wenn der Ausgang des Vergleichers 104 echt ist, ist die Einschaltbedingung des UND-Gliedes 105 erfüllt und das Signal CFR wird erzeugt. Dieses Signal schaltet den Analogschalter 106 ein und verursacht die Summierung einer Rückkopplungsbedingung am Ausgang des Integrators 107. Das Flipflop 112 wird ebenfalls gesetzt und damit angezeigt, daß das erste CFR-Signal für dieses Zeichen empfangen wurde. Nach der Zeit D-I folgt die Entscheidungszeit D, die das UND-Glied *

120 anschaltet. Der Vergleicher 119 mißt die vollständige Trenn-Schwellenwertfunktion und liefert ein breites Eingangssignal an das UND-Glied 120. Nach der Entscheidungszeit wird das UND-Glied 120 abgeschaltet und der Integrator 118 zurückgestellt. Er verbleibt in dieser Stellung bis zum Ende der Abtaster-Rückführzeit. Am Ende dieser Rückführzeit beginnt die Verschiebezeit und die Berechnung der Schwellenwertfunktion für den folgenden Abtastlauf.

Wenn am Ende der Verschiebungszeit während der CFR-Fortschreibung oder während der Zeit D-I das Ausgangssignal des UND-Gliedes 105 falsch ist (und damit keine Rückkopplungsbedingung anzeigt), ist der Ausgang des Inverters 11 richtig. Wenn das %

Flipflop 112 bei einer vorhergehenden Abtastung gesetzt wurde, wird das Tor 113 und dadurch der Analogschalter 114 während der Zeit D-I eingeschaltet, wodurch der Ausgangswert des Integrators 115, F, um Eins erhöht wird. Nach dem zehnten CFR-Signal ist die Summe der CFR am Ausgang des Integrators 107 gleich -10 Einheiten. Für jedes folgende CFR überschreitet dieser Ausgang den Wert von 10 Einheiten und der Ausgang vom Summierer 108 ist gleich F. Während F und F erhöht werden, werden diese Ausgänge auf die Summierungsverstärker 101 und 116 zurückgekoppelt und erhöhen die Gewichtungskoeffizienten V bzw. W. Wenn schließlich die Trennabtastung eines Zeichens erreicht wird, wird die vom Vergleicher

Docket RO 969 OO5

109829/1195

BAD ORIGINAL

119 gemessene Trenn-Schwellenwertfunktion erfüllt. Zur Entscheidungszeit wird das Tor 120 eingeschaltet, das Flipflop 121 gesetzt und dadurch eine Trennbedingung angezeigt. Die Trennbedingung wirkt als Einschaltfunktion für die Trennung selbst. Wenn die Trennbedingung erfüllt ist, werden während der Abtasterrückführzeit nach der Entscheidungszeit die Rückstelleingänge der Integratoren 103, 107, 115 und 118 eingeschaltet und das System auf die Anfangsstellung zurückgesetzt. Zur Verschiebezeit wird das System so vorbereitet, daß es die Trenn-Schwellenwertfunktion für das folgende Zeichen berechnet.

Fig. 9 und die nachfolgende Tabelle 2 zeigen die Werte der verschiedenen Parameter für die Abtastungen 1 bis 19 einer sehr dünn über zehn Schritte geschriebenen Null. Fig. 10 und die Werte der in Tabelle 3 gegebenen Parameter zeigen eine sehr dick mit Störungen über zwölf Schritte geschriebene Null. Die Werte in den Tabellen 2 und 3 gelten gemäß den oben angegebenen Gleichungen und werden durch das in Fig. 8 gezeigte Gerät oder einen Digitalrechner errechnet, der nach dem in Fig. 7 gezeigten Algorithmus programmiert ist. Diese Berechnungen zeigen die Operation des Schwellenwert-Trennungssystemes während die Abtastung der Zeichen von rechts nach links weiterläuft. Diese beiden Beispiele zeigen die Fähigkeit der verbindenden Rückkopplungsfunktionen F und F, den Messungs-Gewichtungskoeffizienten so zu steuern, daß die Trenn-Schwellenwertbedingung im richtigen Abtastspur-Bereich des Musters erfüllt ist. Da diese Rückkopplungsfunktionen durch die Stärke des Musters sowie dessen Form gesteuert werden, können sie die Gewichtungskoeffizienten für alle Zeichenformen richtig s teuern.

Docket RO 969 005

109829/1195

Tabelle 2

8-

UJ tn

	Abtast	n	0	Tv	N	η	0	*£V.N	j	T1	P-N	3	V	η	τ	05	X	η	0	η	CFR	0 ·	c;
	spur (n)	5	~ j	0					6	ι	03	0	♦ O	η	1
	1	7	0	0	0		0	·. 0	S	1	11	0	.3	ι	0
		12	5	11	0		0	3	2	1	14	0	. 8	τ_	0
	3	3	12	3.	0		5	12	3	1	19	0	.3	1	0
	4	2	14	2	11		0	3	2	1	22	0	,8	1	0
	5	I'	17	1	14		0	3	1	27	■ ο	. S	1	0
	δ	2	19	"I	16		0	3	ν	Q	,5	α.	0
	- 7	0	20	0	17		1	3	ΐ	0	.8	ι	0
	ε	0	22	0	13		0	4·	1	. 0	.3	1	0
O	9	0	22	. 0	13		0	4	1	0	.3	1	0
ca	10 ·	0	22'	C	IS		0	4	1	0	.3	1	0
ao>	11	0	22	0	13		0	4	ι.	1	π . U	0	0
to	12		22	2	18		0	4	J- ·	τ_	.3	0	0
co		0	22	2	13	2	0	4	JL *	1	.53	0	1
k	14	2	24	0	20.	4	2	3.	1.	2	.35	1	1
_k	15	2	24	2	22.	.4	0	' τ J. .	1.	2	.89	0	1
CD	16	12	26	4	22.	S	0	4.	1.	3	.89	1	0
cn	17	0	•28	4	24.	7	2	3.	i.	3	.92	0
	IS	40	29.	,8	0	IC.			.92	0
	19	40	34,	S	'5.		1

F	η	0	F	T
0		ι η
0	0	0
0	0	7. 5
0	C	11.5·
0	0	4.0"
0	0	4.5
0	0	4.0
0	■ 0	2.7
0	0	5.0
0	0	4.0
1	0	4.0
Ί	0	4.0
ι	0	3.0
Ϊ	τ_	■ 3.0
2	2
2	3	0.6
3	3	2.6
3	4	0.4
	4	13.3
		-5.2,
	Trennung
	(Sektion)

O CD -P--CD CD NJ

	Abtast- spur(n)	0	P L. η	Νη	0	"j	Tabelle 3	P-N	Vn	Χη	W η	CFRn	CFR^	■ F η	Fn	T η
Doc	1	7	0	0	0		L η	0.0	1	0	.8	0	0	0	0
ro	2	5	7	0	0		0	7.0		0	.8	1	0	0	0	10.5
Γ+	3	1	12	0	•0		0	' 12.0	ι ·	0	.8	2	0	0	0	3.9
§	4	4	13	0	0		7	13.0	1	0	.8	3	0	0	0	5.5
	5	3	17	0	7		10	17.0	2	0	.8	4	0	0	0 '	8.6
	6	2	20	7	11		13	13.0		0	.8	5	0	0	0	6.5
	7	0	22	"4	15		10	11.0	JL	0	.8	6	0	0	■ 0	5.6
O	8	2	22	4	15		8	.7.0	1	0	.8	7	' 0	•ο	0	3.8
	9	5	24	1	16		4	3.0	ι	0	.8	8	0	0	0	5.8
	10	1	29	0	21		4	13.0	T JL	0	.3	9	0	0	0	11.5
—*	11	1	30	5	23		5	9.0	T	0	.8	10	0	0	0
O	12	6	31	2	25		5	8.0	1	1	.8	11	0	1	0	1.5
CO	13	4	37	' 2 .	26	.1	6.	11.9	1.05	2	.8	12	0 ""	2	0	8.9
to	14	4	41	1	29	.2	5	14.8	1.1	3	.8	■ 13	0	3	0	5.8
co	15	0	45	3	32	.6	10	15.4	1.15	4	.3	14	0	4	0	3.8
**·	16		45	2 .			12	■ 13.0	1.20	5	.8	15'	0	5	0	-4.0
—*							14									Trennung
															(Sektion)
en

Die obigen Beispiele basieren auf der spezifischen Gleichung und der Erzeugung der Werte P_r N und L gemäß der in Fig. 6 gezeigten Verknüpfung. Die Gewichtung in der Gleichung kann jedoch auch andere Werte annehmen und die Parameter P, N und L können auf Daten basieren, die man von weniger als drei Abtastungen (wie sie in Fig. 6 gezeigt sind) erhält, ohne daß die Grundnatur der Erfindung dadurch verändert wird.

Die Erfindung braucht weiterhin nicht nur mit digitalisierten Videodaten zu arbeiten, sondern läßt sich ebenso auf analoge Videoinformationen anwenden. Ein Beispiel dafür ist in Fig. gezeigt. Wie daraus zu ersehen ist, werden die analogen Video- * daten auf eine Abtast-Verzögerungsleitung 201 gegeben, deren Verzögerung genauso groß ist wie eine Abtastperiode. Die Ausgangssignale der Verzögerungsleitung werden auf eine Summierungsschaltung 203 über einen Verstärker 202 zusammen mit den momentan abgetasteten analogen Videodaten gegeben. Der Ausgang des Summierers 203 ist der analoge Wert, der die momentane Differenz zwischen dem Videopegel von η-Abtastungen und n-1-Abtastungen darstellt, die durch die Verzögerungsleitung 201 erzeugt wurde. Dieser Ausgang wird auf zwei Null-Begrenzungssummierer 205 und 206 gegeben. Das Ausgangssignal des Summierers 205 kann nur positiv sein und stellt ein Maß des momentanen P-Wertes dar. Der Ausgang des Summierers 206 kann nur negativ sein und mißt den momentanen Wert -N. Der Ausgang des Verstärkers 204 ist der momentane Wert für das analoge Videosignal L. Diese Ausgänge können im wesentlichen genauso benutzt werden wie die Ausgänge der Digital-Analog-Schalter der oben in Verbindung mit Fig. 8 beschriebenen Ausführung.

Der in obiger Beschreibung gegebene Algorithmus kann abhängig von der Datenquelle, auf die er angewendet wird, verändert werden. Wenn die Daten z.B. eine besonders niedrige Qualität und eine hohe Anzahl von Störbit» aufweisen, können die P- und die N-Meesungen durch eine ODER-Verknüpfung zweier aufeinanderfolgender Abtastungen gebildet werden, wodurch sich effektiv ihr durch-

Docket RO 969 005

10982-9/1195

schnittliches Auftreten über einem örtlich begrenzten Bereich ergibt. Die Form der L-Messung kann über einen größeren vertikalen oder horizontalen Bereich ausgedehnt werden, um extreme Veränderungen in der Linienbreite oder spezielle Zeichenformen zu erfassen. Durch Ausnutzung der Konvolutionseigenschaft der Form vieler Zeichen kann eine andere Form der Meßkoeffizientensteuerung eingeführt werden. Zeichen wie M und O sind z.B. durch viele Linienelemente in der horizontalen Ebene gekennzeichnet. Die Koeffizienten der resultierenden N- und P-Messungen für die der ersten Linienkante nachfolgende Linienkanten können entsprechend erhöht oder erniedrigt werden, um die Trenn-Schwellenwertfunktion unabhängig von der Zeichenbreite für in einer räumlichen Proportion stehende Daten zu unterstützen. Außerdem kann bei dieser Anwendung die Rückkopplungsfunktion für bestimmte Formänderungen und nicht durch die Abtastung fortgeschrieben werden, um die Abhängigkeit von der Zeichenbreite weiter zu reduzieren. Außerdem können für die Anwendung bei vorgegebenen Schrittbreiten stärkere Beschränkungen durch die Abtastzählung eingeführt werden, als sie in dem beschriebenen Ausführungsbeispiel gegeben sind.

Docket RO 969 005

109829/1195

Claims (9)

1. PATENTANSPRÜCHE

   (j.. Verfahren bei der maschinellen Zeichenerkennung zur Trennung aneinandergrenzender oder sich überdeckender Zeichen, die mittels mindestens eines Abtasters und eines Wandlers in eine zeitabhängige und/oder räumlich verteilte Reproduktion umgewandelt werden, die in einem Zwischenspeicher gespeichert wird, dadurch gekennzeichnet, daß durch Abtastung des Zwischenspeichers und gegebenenfalls des Wandlers räumlich benachbarte Teilflächen spalten- oder zeilenweise verglichen werden, daß eine spalten- bzw. zeilenweise oder zeichenweise Summierung der Vergleichsergebnisse erfolgt, daß diese Teilsummen mit Gewichtungskoeffizienten bewertet werden, und ™ nach Abtastung jeweils einer Spalte oder Zeile die Gesamtsumme gebildet wird, abhängig von deren Größe eine Zeichentrennung durchgeführt wird.
2. 2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Abtastung seriell länge parallel in geringem Abstand voneinander verlaufender Abtastspuren erfolgt.
3. 3. Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß jede Abtastspur in Spurabschnitte unterteilt ist, daß das für jeden Abschnitt der η-ten Spur ermittelte digitalisierte Videosignal mit dem für den entsprechenden Abschnitt der (n-l)-ten Spur ä gespeicherten Videosignal verglichen wird, und daß die Vergleichsergebnisse spuren- bzw. zeichenweise summiert die Teilsummen ergeben.
4. 4. Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß das für eine n-te Spur ermittelte zeitabhängige analoge Videosignal mit dem für die (n-l)-te Spur ermittelten und gespeicherten Videosignal verglichen wird, und daß die zeitabhängige Vergleichsfunktion, insbesondere die Differenzfunktion beider zeitabhängiger Videosignale, über die Zeit integriert wird.
5. 5. Verfahren nach Anspruch 1, gekennzeichnet durch von den Ergeb-

   Docket RO 969 005

   1 09829/1196

   nissen vorangegangener Vergleiche benachbarter Teilflächen abhängige Gewichtungskoeffizienten.
6. 6. Anordnung zur Durchführung des Verfahrens nach Anspruch 1 in einer Vorrichtung zur maschinellen Zeichenerkennung mit einer die zu erkennenden Zeichen abtastenden Abtastvorrichtung und einem an diese angeschlossenen Wandler, einem Zwischenspeicher zur Aufnahme einer Reproduktion der abgetasteten Zeichen und einer Zeichenerkennungsschaltung/ dadurch gekennzeichnet, daß zumindest einzelne Elemente des die Zeichenreproduktion aufnehmenden Zwischenspeichers (14 in Fig. l_r Fig. 3) mit Vergleichsschaltungen (12 in Fig. 1, Fig. 4, Fig. 6) und deren Ausgangsleitungen (P, N, L in Fig. 4; P_n, N-, L_n in Fig. 6) wiederum mit einer ein Zeichentrennsignal nach Maßgabe vorgebbarer Bedingungen erzeugenden Schaltungsanordnung (12 in Fig. 1, Fig. 8) verbunden sind, und daß die das Zeichentrennsignal führende Ausgangsleitung der Schaltungsanordnung (12 in Fig. 1, Fig. 8) an die Zeichenerkennungsschaltung (16 in Fig. 1) angeschlossen ist.
7. 7. Anordnung nach Anspruch 6 mit serielle}; Abtastung, dadurch gekennzeichnet, daß der ZwXschen&peicjxer (14 in- Fig. 1) als Schieberegister (Fig. 3) ausgebildet ist, das synchron zur seriellen Abtastung weitergeschaltet wird und digitalisierte Videosignale seriell aufnimmt, und daß zumindest ein Teil der Ausgangsleitungen der Schieberegisterstufen mit Verknüpfungsschaltungen (Fig. 4, Flg. 6) verbunden sind.
8. 8. Anordnung nach Anspruch 6 mit serieller Abtastung, gekennzeichnet durch einen als Verzögerungsspeicher (201 in Fig. 11) ausgebildeten Zwischenspeicher (14 in Fig. 1) zur Aufnahme analoger Videosignale.
9. 9. Anordnung nach Anspruch 6, dadurch gekennzeichnet, daß die Schaltungsanordnung (Fig. 8) zur Erzeugung des Zeichentrennsignals ("Sektion" in Fig. 8) die Gleichung

   Docket RO 969 005

   109829/ 1 1 96

   " "^:l" *■" ^: "■■ " " '■-■■'- ■■■ ■ ■ ■" ' ■ "■ ■ ' ■ *■*'■■■-■> ■ ■- ' " · -■■■: .·■. : -, , , ,:,.

   - 23 -

   ^Tn ■ X »j CPj]-Vj ["j])-<V + (V_n [P_n] -W_n

   verwirklicht_f worin

   η = Zahl der Abtastungen seit Zeichenanfang

   U. = 1

   V. = 1 + O,O5(F) + O_fO3(F)

   Y_n = 0,5

   W = 0,8 + 0,03(F)
   η

   ^Xn = ^F

   und F und F durch Rückkopplungsschaltungen (106 bis 109 und 111 bis 115 in Fig. 8) erzeugte Rückkopplungsparaineter sind.

   Docket RO 969 005

   109829/1195

   Leerseite