DE2017246A1

DE2017246A1 - Verfahren und Einrichtung zum Er mitteln des Konturverlaufes eines spal tenweise abgetasteten Schriftzeichens

Info

Publication number: DE2017246A1
Application number: DE19702017246
Authority: DE
Inventors: Meinolf Dipl Ing 8035 Gauting Weber Ekke 8000 München Munchhausen
Original assignee: Siemens Corp
Current assignee: Siemens Corp
Priority date: 1970-04-10
Filing date: 1970-04-10
Publication date: 1971-10-21
Also published as: AT310265B; LU62959A1; NL7104783A; SE378691B; DE2017246B2; BE765562A; GB1306798A; DE2017246C3; FR2089374A5; US3713098A

Description

SIEMENSAKTIENGESELLSGHAPT München 2, den

Berlin und München Wittelsbacherplatz 2

70/2037

Verfahren und Einrichtung zum Ermitteln des Konturverlaufe & eines spaltenweise abgetasteten Schriftzeichens

Die Erfindung bezieht sich auf ein Verfahren zum Ermitteln und Zwischenspeichern eines aus mehreren Konturen zusammengesetzten Konturverlaufes eines spaltenweise abgetasteten Schriftzeichens mit Hilfe der Abtastergebnisse zweier jeweils aufeinanderfolgender Abtastspalten.

Das Problem der Zeichenerkennung gliedert sich eigentlich in .zwei Teilaufgaben, einmal ein zu erkennendes Schriftzeichen abzutasten, das Abtastergebnis in entsprechender Form festzuhalten und zum anderen dieses Abtaetergebnis in einem Klassifizierüngsprozeß einer bestimmten Bedeutungsklasse zuzuordnen. Nun hat man seit längerem erkannt, daß der wesentliche Informationsgehalt eines Schriftzeichens in seiner Kontur liegt, wobei unter einer Kontur der geometrische Ort gleicher Änderungen der Informationsparameter verstanden werden soll. Es hat deshalb bereits zahlreiche Versuche gegeben, ein zu erkennendes Schriftzeichen anhand seines Konturverlaufes abzutasten, d.h. den Abtastvorgang selbst durch die Kontur des Zeichens zu beeinflussen. Ein Abtastverfahren, das nach diesem Prinzip zufriedenstellend arbeitet, hat den großen Vorteil, daß für die eigentliche Klassifizierung des abgetasteten Schriftz.eichens ein Abtastergebnis erhalten wird, das praktisch noch den gesamten Informationsgehalt des Schriftzeichens

VPA 9/210/0020

Go/Ne . - 2 -

109843/0949

besitzt. Das wirkt sich.auf den Klassifizierungsprozeß insbesondere dann sehr günstig aus, wenn mit einem Zeiehenerkennungsverfahren auch alphanumerische Schriftzeichen erkannt werden sollen. Jedem Schriftzeichen muß dann aus einer größeren Anzahl von Bedeutungsklassen eine bestimmte Bedeutungsklasse zugeordnet werden. Wenn·das Zeichenerkennungsverfahren allgemein anwendbar sein soll, müssen aber auch innerhalb einer Bedeutungsklasse eine Vielzahl von Variationen zugelassen.werden, die zum Teil auch auf Störungen der Schriftzeichen zurückzuführen sind.

Diesen Vorteilen stehen aber ebenso starke Nachteile gegenüber, die sich aus dem angedeuteten Abtastprinzip ergeben. Da bei einer optischen Abtastung der Lichtstrahl dem Konturverlauf des abzutastenden Zeichens entsprechend ausgelenkt werden muß, dieser Konturverlauf aber zunächst als unbekannt anzusehen ist, wird die Steuerung der Auslenkung des Lichtstrahles einer Kathodenstrahlröhre zum Beispiel bei Linienzugunterbrechungen erschwert und aufwendig. Man kann bei einer unbekannten Zeichenstruktur nur davon ausgehen, daß ein eine Kontur verfolgender Licltstrahl weiterhin in der bisherigen Richtung ausgelenkt werden soll, ^ weil eine bestimmte Wahrscheinlichkeit dafür besteht, daß die Kontur ihre Richtung beibehält.

Damit werden nun die Schwierigkeiten dieses Abtastprinzipa deutlich. Einmal ist die Abtastgeschwindigkeit begrenzt wegen der notwendigen Suchvorgänge des Abtastsystemes bei gestörten Zeichen, aber auch bei Zeichen, deren Konturverlauf nicht aus zusammenhängenden Konturen besteht, zum anderen ist das Abtastergebnis auch nicht in allen Fallen genau genug, daß daraus die ursprüngliche

VPA 9/210/0020 - 3 -

109843/0949

Kontur wieder herzustellen wäre. Das ist außerdem noch darauf zurückzuführen, daß es auch erhebliche Schwierigkeiten bereitet, die Koordinaten der Konturen geometrisch exakt festzulegen. . . .

Wegen dieser Schwierigkeiten und des großen Aufwandes, ein derartiges Abtastverfahren praktisch durchzuführen, ist man auch schon einen anderen Weg gegangen und hat das zu erkennende Schriftzeichen spaltenweise abgetastet. Dabei werden dann die Abtastergebnisse jeweils zweier aufeinanderfolgender Abtastspalten miteinander verglichen und dabei sogenannte Formelemente ermittelt, die für Schriftzeichen einer bestimmten Bedeutungsklasse charakteristisch sein sollen. Das bedeutet aber, daß beim Abtastvorgang selbst schon eine wesentliche Reduktion des Informationsgehaltes des zu erkennenden Schriftzeichens vorgenommen wird und man dann auch nicht mehr die ursprüngliche Kontur des Schriftseichens aus dem Abtastergebnis wieder herstellen kann. Daraus folgt aber wiederum, daß man im eigentlichen Klassifizierungsprozeß mit wesentlich weniger Informationen auskommen muß, um das abgetastete Schriftzeichen zu erkennen. Derartige Verfahren sind also in ihren Anwendungsmöglichkeiten beschränkt auf Schriftzeichen mit nur wenigen Variationen in einer Bedeutungsklasse und außerdem sehr störempfindlich, da bei größeren Zeichenstörungen mit einer hohen Rückweisungsrate bzw. Falscherkennungsrate gerechnet werden muß.

- Der Erfindung liegt daher die Aufgabe zugrunde, ein Verfahren zum Ermitteln und. Zwischenspeichern eines aus mehreren einzelnen Konturen zusammengesetzten Konturverlaufes eines Schriftzeichens zu schaffen, bei dem aber

VPA 9/210/0020 - 4-

109843/094 9

BAD ORIGINAL

das Zeichen spaltenweise abgetastet werden kann, um den Aufwand für die Steuerung des Abtastsystemes bei den Suchvorgängen und die dafür benötigte Zeit zu vermeiden. Außerdem soll dieser Konturverlauf allein aus dem digitalisierten Abtastergebnis jeweils zweier aufeinanderfolgender Abtastspalten gewonnen werden können, so daß die gesamte Kpntur eines Zeichens reversibel in einem verhältnismäßig einfach aufgebauten Speicher auch schon bei kleiner Spei- ^ · cherkapazität zwischengespeichert werden kann.

Diese Aufgabe wird erfindungsgemäß dadurch gelöst, daß in jeder Abtast-spalte bei einem Wechsel eines digitalisierten Bildsignales von einer Stufe in eine andere eine Kontur festgestellt wird, daß jeder dieser Übergänge fortlaufend gezählt und damit jeder Kontur eine bestimmte Adresse zugeordnet wird, daß die in zwei aufeinanderfolgenden Abtastspalten auftretenden Differenzwerte der Ordinaten einer Kontur quantitativ ermittelt und in einem Konturspeicher gespeichert werden, daß durch einen Bildsignalwechsel nur dann der Anfang zweier neuer Konturen festgelegt wird, wenn für die Grdinaten zweier Konturen in zwei W aufeinanderfolgenden Abtastspalten n, m eine erste Ungleichung . ■

Yn (k) £ Ym (k - 1) + G

erfüllt ist, bzw. durch den Bildsignalwechsel nur dann das Ende zweier Konturen festgelegt wird, wenn eine andere Ungleichung

Yn (k) > Ym (k +' 1.) + C

erfüllt ist. ,

Durch diese erfindungsgemäße Lösung: lassen sich die Vor- ■

VPA 9/210/0020 _ 5 - · ■ ■ -

■'■■'■ ■ BAD ORiGINAL

109843/0949

teile eines spaltenweisen Abtastprinzipes auf einfache Weise verbinden mit den Vorteilen, die sich aus einer reversiblen Zwischenspeicherung des Konturverlaufes eines abgetasteten Zeichens ergeben. Bei dem .spaltenweisen Abtastprinzip wird einmal die Steuerung für die Auslenkung des das Schriftzeichen abtastenden Lichtstrahles besonders einfach und die genaue Zuordnung der geometrischen Koordinaten des gerade abgetasteten Bildpunktes zu dem gesamten Abtastfeld möglich. Außerdem geht bei dieser Abtastung und dem anschließenden Zwischenspeichern des Abtastergebnisses so wenig Information verloren, daß man diesen Vorgang in bezug auf das digitalisierte Bildsignal als reversibel bezeichnen kann. Das bedeutet eine Erleichterung der späteren Klassifizierung, für die es auch bei strengeren Anforderungen an das Zeichenerkennungssystem wesentlich ist, daß das gesamte Abtastergebnis zur Verfügung steht. So wird es dann z.B. möglich, wie bereits vorgeschlagen wurde, den eigentlichen Klassifizierungsvorgang in mehreren Schritten durchzuführen und damit die Rückweisungsrate zu senken.

Diese Vorverarbeitung der bei der Abtastung gewonnenen Bildsignale ermöglicht eine besondere vorteilhafte Weiterbildung mit einem Konturspeicher, der dadurch direkt adressierbar ist, daß mit der Adresse k einer Kontur die k-te Zeile des Konturspeichers ausgewählt wird, daß bei einem festgestellten Anfang zweier neuer Konturen mit den Adressen (k - 1) und k sämtliche Zeilen des Konturspeichers deren Adresse größer als (k - 2) ist, in jeweils eine Zeile mit um zwei größerer Adresse umgespeichert werden und daß bei einem festgestellten Ende eines Konturpaares der Inhalt sämtlicher Speicherzeilen, deren Adressen höher

VPA 9/210/0020 .- ⁶ - BAD ORIQ₁NAL

109843/0949

sind als die Adressen des abgeschlossenen Konturpaares, ,ieweils in Speicherzeilen mit um zwei kleinerer Adresse umgespeichert wird, sobald die Werte des abgeschlossenen Konturpaares in einen weiteren kleineren Konturspeicher übertragen sind. Damit wird erreicht, daß zu jedem Zeitpunkt die Anzahl der im Konturspeicher belegten Zeilen gleich der Anzahl der Konturen in der abgetasteten Spalte ist. Neben dem geringen Speicherplatzbedarf bei der Kon-F turspeicherung bedeutet es aber auch eine besonders einfache Auswahl der Speicherplätze.

Andere Weiterbildungen der Erfindung sind-in Unteransprüchen gekennzeichnet. ' '

Zum besseren Verständnis werden im folgenden Einzelheiten und ein Ausführungsbeispiel der Erfindung im Zusammenhang mit eine.r Einrichtung zur Durchführung eines erfindungsgemäßen Verfahrens anhand der Zeichnungen näher beschrieben. Es zeigen:

k Fig.1 die schematisierte Darstellung einer Ziffer "2"

mit den entsprechenden Konturen k,

Fig.2 das Schema einer Zeichenstruktur, bei der eine

neue Außenkontur in der Abtastspalte η auftritt,

Fig.3 ein entsprechendes Schema mit dem Ende einer Innenkontur,

Fig.4-7 ' schematische Grenzfälle von Zeichenstrukturen mit dem Anfang oder dem Ende von Außen- bzw. Innenkontüren, anhand deren verschiedene Werte für die Funktionsvariable C festgelegt werden und

VPA 9/210/0020 .- : - 7 -

f 09-8-43/0949'

Pig.a das Blockschaltbild einer Einrichtung zur Durchführung eines erfindungsgemäßen Verfahrens.

Bei der spaltenweisen Abtastung eines in einem Abtastfeld liegenden Schriftzeichens, zum Beispiel mit Hilfe eines ausgelenkten Elektronenstrahles, trifft der Lichtstrahl nacheinander auf mehrere Konturen auf, wobei unter den Konturen eines digitalen Schriftzeichens.die durch Schwarz-Weiß-Übergänge oder Weiß-Schwarz-Übergänge erzeugten Ränder der Linienzüge verstanden werden sollen. Diese Konturen sind in Pig.1 durch eine Ordnungszahl k bezeichnet, so treten bei der dargestellten Ziffer "2" sechs Konturen auf, deren Anfänge und Enden durch Kreise bezeichnet sind. In dem hier sieben Abtastspalten überdeckenden Mittelteil der Ziffer "2" läßt sich jede Kontur eindeutig mit den von Spalte zu Spalte auftretenden Differenzwerten der Konturordinaten beschreiben, wie die Tabelle 1 zeigt.

Tabelle 1:

k	Ordinatendifferenz	1	-1	Q-	O	-2	O
6	1	O	O	O	-1	O	-2
5	2	1	1	1	0	1	2
4	O	O	1	1	1	O	1
3	1	O	O	O	O	1	-1
2	O	O	O	O	O	0	O
1	O

Nun ist eine,derartige Konturbeschreibung für die spätere Klassifizierung noch wenig geeignet, es ist vielmehr erwünscht, jede Kontur in ihre einzelnen Elementarmerkmale zu zerlegen. Dabei hat es sich als zweckmäßig und günstig

VPA 9/21O/OO2O _ 8 -

109843/0949 ; BAD ORIGINAL

erwiesen, eine Kontur anhand von vier Elementarmerkiaalen zu beschreiben, die als "Steigung positiv" (SP) bei ansteigendem Konturverlauf, "Steigung negativ"(SfTX'bei abfallendem Konturverlauf, "vertikal" (VE) bei vertikalem und "horizontal" (HO) bei horizontalem Konturverlauf bezeichnet werden. Diese Bezeichnung wurde aus anschaulichen Gründen gewählt. Für die digitale maschinelle Verarbeitung muß ihnen aber ein Code zugeordnet werden, diese Zuordnung • ist in der Tabelle 2 dargestellt. ,

Tabelle 2: Elementarmerkmale - Code

Steigung positiv (SP) * 10

Steigung negativ (SN) , 01

Vertikal (VE) 11

Horizontal (HO) 00

Als Beispiel für die Beschreibung einer Kontur anhand der Elementarmerkmale sei der Mittelteil der sechsten Kontur der in der Pig.1 dargestellten Ziffer "2" in Tabelle 3 erläutert.

Tabelle	3:	1	1	-1	0	0	-2	SN	0
Ym - Yn		SP	SP	SN	HO	HO	VE	01	HO
Merkmal		10	10	01	00	00	11		00

Dort sind in der ersten Zeile die Differenzwerte derKonturordinaten (Ym- Yn) nochmals dargestellt, die aus der Zeile k =6 der Tabelle 1 übernommen wurden. In der «weiten Zeile der Tabelle 3 stehen die aus diesen

VPA 9/210/0020 -9- BAD ORIGINAL

109843/0949

Differenzwerten gebildeten Elementarmerkmale SP, SN, HO und VE, Aus der vorletzten Spalte dieser Tabelle ist zu ersehen, daß aus einem Differenzwert, im Beispiel dem Wert "-.2", auch mehrere Elementarmerkmale gebildet werden können und dann auch müssen, um die Kontur an solchen Stellen eindeutig zu beschreiben. Das ist immer dann der Pail, wenn in zwei aufeinanderfolgenden Abtastspalten ein größerer Differenzwert als eins auftritt, so entspricht dann zum Beispiel einem Differenzwert."+5" die Folge von Elementarmerkmalen 10, 11, 11, 11, 11.

Um die Differenzwerte der Konturordinaten bilden zu können, muß jeder festgestellte Bildsignalwechsel eindeutig einer bestimmten Kontur zuzuordnen sein, d.h. es muß eine Adresse dieser Kontur festgelegt werden. In Bereichen, wie in dem Mittelteil der Ziffer "2" in Pig. \ ist eine einfache Markierungsvorschrift für jede Kontur durch laufendes Mitzählen der Bildsignalwechsel in jeder Spalte möglich. Das ist aber dann nicht mehr der Fall, wenn sich die Anzahl der Konturen von einer Abtastspalte zur anderen ändert, oder anders ausgedrückt, wenn in der benachbarten Abtastspälte ein neues Konturenpaar auftritt, wie dies, zum Beispiel schematisch in der Fig.2. in der η-ten Abtastspalte mit zwei neuen Außenkonturen der Fall ist.

Um nun die Zuordnung der Bildsignalwechsel zu bestimmten Konturen aufrecht zu erhalten, müssen derartige Konturanfänge bzw. Konturenden erkannt werden, dazu reichen ab&r die Ordinaten der den Konturen zugeordneten Schwarz-Weiß-Übergänge und Weiß-Schwarz-Übergänge zweier benachbarter Spalten aus. Bezeichnet man mit Yn (k) die k-te Konturordinate der eben abgetasteten Spalte η und mit Ym (k) die k-te Konturordinate der" vorher abgetasteten benachbarten

VPA 9/210/002Ö . ' - 10

IQ 98 £3/OiUfK

- ίο -

Spalte m und zählt man die Konturadresse k in Y-Richtung von unten nach oben, so ist normalerweise der Wert einer höher adressierten Konturordinate größer als der einer -niedrig adressierten benachbarten Konturordinate. Diese Regel wird nur bei Konturanfängen und Kontur end en', durchbrochen, wie dies auch aus den Darstellungen in Pig.2 und Fig.3 hervorgeht. Allgemeiner ausgedrückt bedeutet das, daß bei einem Konturanfang die Ungleichung

(1) Yn (k) ^ Ym (k - T) +0

und bei einem Konturende die Ungleichung

(2) Yn"(k) 7 Ym (k + 1) + C

erfüllt sein muß, sonst setzt sich die schon bisher markierte Kontur fort. .

Das Unterscheidungskriterium zwischen einer Außenkontur, die in Pig.2 dargestellt ist und einer Innenkontur, wie \ sie Pig.3 zeigt, ist die Übergangsrichtung des Bildsignal wechseis in der gerade abgetasteten Abtastspalte η zu einem Zeitpunkt, da die Ungleichung erfüllt ist. Sie verläuft für den Anfang oder das Ende einer Innenkontur " gerade umgekehrt wie bei einer Außenkontur, wie aus dem Vergleich der Fig.4 mit der Pig.5, bzw. der Fig.6 mit der Pig.7 hervorgeht. -Dort sind schematisch Grenzfälle von Strukturkonstellationen dargestellt, mit denen der Wert der Funktionsvariablen C im einzelnen festgelegt werden soll. Die Fig.4 zeigt in der η-ten Abtastspalte den Beginn eines neuen Paares von Außenkonturen, bei dem in jedem Fall die k-te KonturOrdinate durch einen Schwärz-'.Yeiß-Übergang des Bildsignales angezeigt wird. Für den Zusammenhang zwischen beiden Kontürordinaten in den benachbarten Spalten gilt dann die Gleichung

(3) Yn (k) = Ym (k - 1) -2 ■

- 11 -

Das bedeutet,bei einem Anfang von neuen Außenkonturen ist die Punktionsvariable C = -2.

In der Pig.5 ist der entsprechende Grenzfall für den Beginn eines neuen Paares von Innenkonturen dargestellt, dem in der Abtastspalte η der k-ten Kontur auf jeden Fall ein Weiß-Schwarz-rÜbergang des Bildsignales zugeordnet ist. Pur die beiden interessierenden Konturordinaten ergibt sich dann die Gleichung

(4) Yn (k) = Ym (k - 1) + 1

und um die Ungleichung (1) zu erfüllen, folgt daraus die Punktionsvariable C = 1. ,

In der Pig.6 ist das Ende eines Paares von Außenkonturen dargestellt, bei dem in der k-ten KonturOrdinate der Abtastspalte η ein Weiß-Schwarz-Ubergang des Bidlsignales stattfindet. Diese Strukturkonstellation läßt sich durch die Gleichung

(5) Yn (k) = Ym (k + 1) + 2

beschreiben. In der Ungleichung (2) ist dann die Punktionsvariable C = 1.

Die Pig.7 zeigt schließlich die vierte Möglichkeit, nämlich den Grenzfall für das Ende eines Innenkonturpaares in der Abtastspalte n, wobei in dieser Abtastspalte bei der k-ten Konturordinate ein Schwarz-Weiß-Übergang des Bildsignales auftritt. Die Beziehung zwischen den beiden zu vergleichenden Konturordinaten

Yn (k + 1) und Yn (k)
ist hier durch die Gleichung

(6) Yn (k) -Ym (k + 1) -1

gegeben, um die Ungleichung (2) zu erfüllen, muß die

VPA 9/210/0020 - 1.2 -

109843/0949

Punkt ions; variable C in diesem Pall wiederum de** Wert "-2" annehmen.

Daraus ergibt sich allgemein, daß^die Funktionsvariable G in den Ungleichungen (1} bzw, (2) bei einem Schwarz-Weiß-Übergang in der η-ten Abtastspalte jeweils den Wert "—2" bzw. bei einem Weiß-Sc.hwarz-4ibergang den Wert "1" annimmt. Das bedeutet_K daß immer dann, wenn eine der beiden Ungleichungen (T) oder (2) erfüllt ist, aus der | Richtung des Zustandswechsels eines Bildsignales ermittelt werden kann, ob nunmehr ein Paar von Innen-bzw, Außenkonturen anfängt oder endet. Um mit diesem Ungleichungssystem in jedem Fall arbeiten zu können, muß man lediglich voraussetzen, daß zu jedem Zeitpunkt oberhalb und unterhalb der laufenden Kontur Vergleichskonturen existieren. Das erreicht man zum Beispiel leicht durch Simulation von zwei Konturen am oberen bzw. unteren Bildrand,

Aus dem Vorstehenden wurde deutlich, daß man eine laufende Kontur mit Hilfe von vier Elementarmerkmalen reversibel beschreiben kann, die aus der Differenz der Konturordinaten benachbarte Abtastspalten gewonnen werden und daß W man die Beschreibung dieser Kontur vervollständigt, wenn man die Beschreibung derOrdinaten ihres Anfanges und Endes erfaßt.

Ein-sogenannter Konturspeieher KSP, in dem der Konturyerlauf eines abgetasteten Schriftzeichens* direkt adressierbar zwischengespeichert werden kann, kann gemäß einer Weiterbildung der Erfindung so aufgebaut sein, daß jeweils die gesamte Besehreibung einer Kontur in einer entsprechenden Speicherzeile gespeichert wird. Man kann nun

VPA 9/210/0020 -13-

schematisch den Konturspeicher KSP1 spaltenweise in drei Speichereinheiten aufteilen. Die erste Speichereinheit SKA "besitzt zwei Spalten für die Koordinaten des Konturanfanges, die durch eine -bestimmte der χ Abtastspalten als Abszissenwert und die Y-Ordinate gegeben sind. Die zweite Speichereinheit SKE des Konturspeichers KSP1 ist dementsprechend ebenfalls aus zwei Spalten aufgebaut, die in analoger Weise die Koordinaten für ein Konturende aufnehmen. Die dritte Speichereinheit des Konturspeichers, der Merkmalspeieher SM, enthält schließlich in jeder ihrer Speicherzeilen sämtliche Elementarmerkmale, die jene Kontur beschreiben, die dieser Zeile zugeordnet ist. ^;

Um nun die direkte Adressierung des Konturspeichers und damit die einfache Speicherplatzauswahl aufrecht erhalten zu können, müssen bei jedem Konturanfang eines neuen Kon.turenpaar.es _zwei Speicherzeilen dieses Konturspeichers KSPT zur Aufnahme der Konturbeschreibung bereitgestellt werden. Sind...in dem Konturspeicher bereits, die Beschreibungen laufender Konturen enthalten, deren Ordnungszahl sich jetzt durch das Auftreten eines neuen Konturenpaares ändert, so müssen die Speicherzeilen des Konturspeichers KSP1, deren Adressen höher als (k - 1) sind, jeweils um zwei Zeilen nach oben umgespeichert werden, dann können die Anfangskoordinaten der neuen Konturen Yn (k) und Ym (k -1) in die freigewordenen Speicherzeilen aufgenommen werden. Dasselbe gilt umgekehrt auch für das Ende' einer Kontur, zunächst werden die Merkmalsätze der abgeschlossenen Kontur in einen weiteren Speicher Übertragen, wenn dabei gleichzeitig eine Merkmalreduktioh vorgenommen wird, kann dieser zweite Konturspeicher KPS2, der an-

VPA 9/210/0020 -H-

109843/0949

sonsten im wesentlichen ähnlich aufgebaut ist, noch kleiner dimensioniert werden, Fun können alle Speicherzeilen des Konturspeichers KSP1, deren Adressen größer als (k + 2) sind, um zwei Zeilen nach unten verschoben -werden. Damit wird erreicht, daß zu jedem Zeitpunkt die Anzahl der im Konturspeicher KSP1 belegten Zeilen gleich der Anzahl der Konturen in einer gerade abgetasteten Spalte ist. Nach dem Umspeiehern der Merkmalsätze noch laufender Konturen muß die Bedingung für ein Kontur-" ende aufgrund der Ungleichung (2) erneut abgefragt werden, um eventuell mehrere direkt übereinander liegende Konturenpaare einer Spalte erkennen zu können. Zeigt sich dann, daß keine der beiden Ungleichungen (T) oder (2) für einen gerade abgetasteten Bildsignalwechsel erfüllt ist, so stellt das das Kriterium für die Portsetzung einer markierten Kontur dar. Die aus dem Differenzwert, der Konturordinaten ermittelten Elementarmerkmale werden dann codiert und in den Merkmalspeicher SM eingeschrieben.

Anhand der Blockdarstellung einer Einrichtung zur Durchführung eines erfindungsgemäßen Verfahrens, die in Fig.8 Il dargestellt ist, seien im folgenden die bisher einzeln behandelten Merkmale der Erfindung nochmals zusammen^ fassend dargestellt. .

Die Fig.8 zeigt vier Speicherelemente, als Arbeitsspeicher den ersten Konturspeicher KSP1 mit der Speiehereinheit SKA zur Speicherung der Konturanfänge, der Speichereinheit SKE zur Speicherung der Konturenden und dem Merkmalspeicher SM zur Speicherung der Elementarmerkmale einer Kontur. Dazu kömmt als Ergebnisspeicher der zweite Konturspeicher KSP2, der wie der erste 16 Zeilen besitzen möge, wobei aber das in einer Speicherzelle zu speichernde Wort nur noch halb so groß sein möge.

VPA 9/210/0020 ; - 15 -

100843/0949

Außerdem ist eine Spei eher spalte SYiji für die Konturordinaten der zuletzt bearbeiteten Abtastspalte m mit 16.6 Bit vorgesehen, die mit dem Konturspeieher KSP1 zeilengekoppelt ist. Dieser ersten Speicherspalte SYm entspricht schließlich als viertes Speicherelement eine weitere Speicherspalte SYn für die Konturordinaten· der laufenden Abtastspalte η mit ebenfalls 16.6 Bit. Je zwei zeitlich aufeinanderfolgende Bildsignale des Abtasters AB entscheiden, ob ein Schwarz-Weiß-Übergang oder ein Weiß-Schwarz-Übergang vorliegt. Dieses Kriterium wird in der Schwarz-Weiß-Logik SWL ermittelt. Jeder solche Bildsignalwechsel wird in dem Konturmarkierer KZ gezählt, damit die Ordnungszahl der Konturadresse k festgelegt und die einzelnen Vielfaehschalter S1 bis S6 entsprechend gesteuert. Bei einem Bildsignalwechsel wird die Konturordinate von der Abtaststeuerung AST über einen ersten Vielfachschalter S1 auf eine der 16 Speicherstellen der zweiten Speicherspalte SYn übertragen. Bei einem Spaltenende, das von der Abtaststeuerung AST durch den Befehl SPE angegeben wird, werden die Kontakte des Trennschalters SK1 durchgeschaltet und die erste Speicherspalte SYm übernimmt den gesamten Speicherinhalt der Speicherspalte SYn, gleichzeitig wird der Konturmarkierer KZ auf k = 0 zurückgesetzt.

Bei jedem Bildsignalwechsel, der einem Schwarz^Weiß^Übergang oder einem Weiß-Schwarz-Übergang entspricht, werden durch die Vielfachschalter. S2 und S3 zwei bzw. drei der Ausgänge der beiden Speieherspalten SYn und SYm auf die Ausgänge der beiden Vielfachschalter S2 bzw. S3 durchgeh schaltet und damit die Werte Yn (k), Yn (k + 1) bzw. Ym (k), Ym (k - 1), Ym (k + 1) zu den beiden Vergleichsschaltungen

VPA 9/210/002O₁ - 16 -

109843/0949

KAV und KEV übertragen, in denen die beiden Ungleichungen (1) und (2) logisch realisiert sind und mit denen damit _: Bedingungen für.den Konturanfang bzw. das Konturende, _ festgestellt werden. Zeigt die erste Vergleichsschal- . ■■ -_; tung KAV die Erfüllung der Ungleichung (1) an, so werden die Werte Yn (k - 1) und Ym (k) und die Spaltenposition χ als Koordinaten der beiden Kont.uranfänge in den ersten, , Konturspeicher.KSP1 übertragen, nachdem vorher.eine Verschiebung der Merkmalsätze größerer Adresse um jeweils. zwei KonturSpeicherzeilen nach oben in Abhängigkeit vom Konturmarkierer KZ erfolgte. Eine Steuereinheit ADR enthält dazu eine Verschiebeeinheit, einen Merkmalzähler und einen Adressenwähler zur Ansteuerung des Konturspeichers KSPI.

Bei einem Konturendesignal werden analog Ym (k + 1 ) und Ym (k) und X als die Ordinaten des Konturendes in den Konturspeicher KSPT übertragen. Der Inhalt der , zugehörigen Konturspeicherzeilen kann nach einer Merkmalreduktion in dem Merkmalreduktor (RED) in.4^^ zweiten Konturspeicher KSP2 übertragen werden. Für die Auswahl der entsprechenden Speicherzeilen der Konturspeicher KSP1 und KSP2 dienen die durch den Konturmarkierer.KZ gesteuerten "Vielfachschalter S5 bzw* S6. Die Merkmalsätze größerer Adresse können nun um zwei Zeilen abwärts verschoben werden. Dies wird wiederum durch die Adressensteuerung ADR des Konturspeichers KSPI vorgenommen. Wird dagegen durch die Vergleichsschaltungen KAV bzw. KEV weder ein Konturanfang noch ein Konturende festgestellt, so gilt die markierte Kontur als fortgesetzt und die Ordinatendifferenz Yn (k) - Ym (k) wird in dem Differenzglied DIF festgestellt. Daß weder die Ungleichung (T) noch die Ungleichung (2) erfüllt ist, wird durch den

VPA 9/210/0020 " ' - 17 -

109843/0949

logischen Schaltkreis KPL festgestellt, der an die Ausgänge der beiden Vergleichsschaltungen KAV und KEV angeschlossen ist. Der Trennschalter SK4 wird geschlossen und damit ist das -Differenzglied DIP an den Eingang eines Codewandlers COW angeschlossen. Dort werden aus dem festgestellten Differenzwert der Konturordinäten die Elementarmerkmale ermittelt, die dann entsprechend der Einstellung des Vielfachschalters S4 in die k-te Zeile des MerkmalSpeichers SM übernommen werden.

Vorstehend wurden die Merkmale der Erfindung und ein Ausführungsbeispiel näher erläutert. Es sind aber im Rahmen der Erfindung durchaus noch andere Lösungswege erdenkbar. Wenn z.B. mehrere Konturanfänge oder Konturenden zeitlich dicht aufeinanderfolgen, kann unter Umständen die vom Abtastprogramm zur Verfügung gestellte Zeit zur Aus-? führung der Rechenoperationen nicht mehr ausreichen. Hier brächte dann eine zeitliche Entkopplung mit Hilfe einer gepufferten Speicherspalte SYn den Vorteil, die Rechenoperationen auf die Spaltenahtastzeit beliebig verteilen zu können. Außerdem ist es ohne weiteres denkbar, ein erfindungsgemäßes Verfahren nur mit einem Konturspeipher zu realisieren^ wenn abgeschlossene Konturen im Konturspeicher verbleiben. Dann ist allerdings die Adrgsse einer Vergleichskontur nun im allgemeinen nicht mehr der laufenden Konturadresse benachbart, sondern muß unter der Berücksichtigung einer Kennzeichnung bestimmt werden,, die sum Beispiel aufgrund der Konturenden erfolgen könnte»

7 Patentansprüche

8 Figuren.

VPA 9/210/0020 - 18 -

109843/0849

Claims

--■■ 18 -a t e η t a η s ρ r ü c h e

'!.,Verfahren zum Ermitteln und Zwischenspeichern eines aus mehreren einzelnen Konturen zusammengesetzten Konturverlaufes eines spaltenweise abgetasteten Schriftzeiohens mit Hilfe der Abtastergebnisse zweier jeweils aufeinanderfolgender Abtastspalten, dadurch g e -

fc- k e η η ze i c h η e t, daß in jeder Abtastspalte (x) bei einem Wechsel des digitalisierten Bildsignales von einer Stufe in eine andere eine Kontur (k) festgestellt wird, daß jeder dieser Übergänge fortlaufend gezählt und damit jeder Kontur,eine bestimmte Adresse zugeordnet wird, daß die in zwei aufeinanderfolgenden Abtastspalten (m, n) auftretenden Bifferenzwerte der Ordinaten (Ym, Ck.),.' Yn (k)) einer Kontur quantitativ ermittelt und in einem Konturspeicher (KSP1) gespeichert werden, daß aber durch einen Bildsignalwechsel dann und nur dann der Anfang zweier neuer Konturen festgelegt wird, wenn für die Ordinaten (Y) zweier Konturen (k - 1 _r k) in zwei aufeinanderfolgenden Abtastspalten (nt,, n) eine erste Ungleichung

Yn (k) i£ Ym (k - 1) - C erfüllt ist, bzw. durch den Bildsignalwechsel dann und nur dann das Ende zweier Konturen festgelegt wird, wenn eine andere Ungleichung Yn (k)* Ym (k +1)+0 erfüllt igt. -

2. Verfahren nach Anspruch 1, da du r c h g e k e η n-ζ e i c h η e; t, daß dieFunktionsvariable (G) bei einem Schwarz-Weiß-Übergang, also einem Bildsignalwechsel aus dem Zustand "1" in den Zustand "0" in der η-ten Abtastspalte, den Wert "-2" besit2?t und dann mit den beiden -

VSA 9/210/0020 "

1098^^/0949

-19 ■■-■-. ■'■,■ - - : ^: ■■" : ^::

- Ungleichungen der Anfang einer neuen Innenkontur bzw.
das Ende einer Außenkontür ermittelt wird und daß
die Funktionsvariable (G) bei einem Weiß-Schwarz-Übergangy also einem Bildsignalwechsel aus dem Zustand "O" in den Zustand "L·" in der η-ten Abtastspalte, den Wert ••+l" besitzt und dann mit den Ungleichungen der Anfang einer neuen Außenkontur bzw. das Ende,einer Innenkontur ermittelt wird*

■3» Verfahren nach einem der Ansprüche 1 oder 2, d ä d u rc h g e kenn ζ ei oh η et, daß am oberen und unteren Rand des Abtastfeldes ständig Je eine Kontur als Vergleichskontur simuliert wird.

4. Verfahren nach einem der Ansprüche 1 bis 3» d a d u r c h g ek e η η ζ e i c h η e t, daß der Verlauf einer Kontur durch Elementarmerkmale "Steigung positiv" (SP) bei '
ahsteigendem, "Steigung negativ" (SN) bei abfallendem, "horizontal" (HO)bei horizontalem und "vertikal" (VE)
bei vertikalem Konturverlauf beschrieben wird.

5. Verfahren nach Anspruch 4, da d ure h g e k e η nz el c h η et, daß die Elementarmerkmale (SP, SN, HO und VE) aus den Differenzeh der Konturordinatenbenachbarter Abtastspalten derart ermittelt werden, daß eine positive Ordinatendifferenz vom Betrag d einem Elementarmerkmal "Steigung positiv" (SP) und einer Folge von (d-1) Elementarmerkmalen "vertikal" (VE),eine negative Ordinatenäifferenz vom Betrage d dagegen einer Folge von (d-1) Elementarmerkmalen "vertikal"(VE) und einem*
Elementarmerkmal "Steigung negativ" (SN) entspricht und daß das Elementarmerkmal "horizontal" (HO) vorliegt,
wenn die Ordinatendifferenz ¹¹O" let.

VPA 9/210/0020 _ 2Ö - *

109843/0949

... 20.- ■

6. Verfahren nach einem der Ansprüche 1 bis 5, da d,, u r c h gekennzeichnet, daß der Konturspeicher (KSP1) dadurch direkt adressierbar ist, daß mit der Adresse k einer Kontur die k-te Zeile des KonturSpeichers ausge-. wählt wird, daß bei einem festgestellten Anfang zweier neuer Konturen mit,, den Adressen Ck - 1) und k sämtliche Zeilen des Konturspeichers,.deren^Adresse größer als

(k - 2) ist, in jeweils eine Zei.le *mit um zwei größerer _k Adresse umgespeichert werden und daß bei einem ,festgestellten Ende des Konturenpaar.es der Inhalt sämtlicher Speicherzeilen, deren Adressen höher sind als die Adressen des abgeschlossenen Konturenpaares, 4ewells in Speicherzeilen mit um zwei kleinerer Adresse umgespeichert wird, sobald die Werte des abgeschlossenen Konturenpaares in einen weiteren kleinen Konturspeicher (K.SF2) übertragen sind. . -

7. Einrichtung zur Durchführung eines Verfahrens nach einem der Ansprüche 1 bis 6, d a d u r c h g e k e η η ζ e i ohne t, daß zwei Speichereinheiten (SYn;und SYm) vorgesehen sind, in die für zwei aufeinanderfolgende Abtastspalten (m, n) die aus den Bildsignalen (BS) ermittelten Bildsignalwechsel in ihrer Reihenfolge und mit ihren Ordinaten gespeichert werden, daß den beiden Speichereinheiten (SYm, SYn) je ein durch die Bildsignalwechser steuerbarer Vielfachschalter (S2 bzw. S3) zugeordnet ist und die entsprechenden Ausgänge (A, B bzw. C, D und E) dieser Vielfachschalter Über steuerbare Trennschalter (SK2 bzw. SK3) mit den Eingängen «weter eum Speichern der Anfänge bzw. der Enden von Konturen vorgesehenen Speichereinheiten (SKA, SKE) des Konturspeichers (KSP1) verbunden sind, daß Ausgänge der Vielfachschalter

VPA 9/210/0020 - 214-

109843/0949 ...

(S2 und S3), außerdem mit zwei Vergleichsschaltungen (KAV bzw. KEV) zum Peststellen von Konturanfängen- bzw. Konturenden durch die jeweils einer der .."beiden Trennschalter (SK2 bzw. SK3) gesteuert wird und weiterhin mit einem Differenzglied (DIF) zum Bilden der Differenzwerte der Konturordinaten zweier benachbarer Abtastspalten verbunden sind und daß dieses Differehzglied über einen weiteren Trennschalter (SK4)_f einen Codewandler (COW), in dem aus den Differenzwerten der Konturordinatönndie Elementarmerkmale (SP, SN, VE, HO) in codierter Form ermittelt werden, an den Eingang eines weiteren steuerbaren Vieifachschalters (S4) angeschlossen ist, dessen Ausgänge je einer Zeile eines sogenannten Merkmalspeichers (SM) des Konturspeichers (KSP1) zugeordnet sind.

VPA^9/210/0020"

109843/094»