DE2017246C3

DE2017246C3 - Verfahren und Einrichtung zum Ermitteln des Konturverlaufes eines spaltenweise abgetasteten Schrittzeichens

Info

Publication number: DE2017246C3
Application number: DE2017246A
Authority: DE
Inventors: Meinolf Dipl.-Ing. 8035 Gauting Muenchhausen; Ekke 8000 Muenchen Weber
Original assignee: Siemens AG
Current assignee: Siemens AG
Priority date: 1970-04-10
Filing date: 1970-04-10
Publication date: 1975-11-06
Also published as: AT310265B; LU62959A1; NL7104783A; SE378691B; DE2017246B2; BE765562A; GB1306798A; DE2017246A1; FR2089374A5; US3713098A

Description

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 aufeinander· folgender Abtastspalten.

Das Problem der Zeichenerkennung gliedert siel eigentlich in zwei Teilaufgaben, einmal ein zu erken

nendes Schriftzeichen abzutasten, das Abtastergebnis in entsprechender Form festzuhalten und zum anderen dieses Abtastergebnis in einem Klassifizierungsprozeß einer bestimmten Bedeutungskkase zuzuordnen. Nun hat man seit längerem erkannt, daß der wesentliche Informationsgehalt eines Schriftzeich en s in der Gesamtheit seiner Konturen liegt, wobei unter einer Kontur der geometrische Ort gleicher Änderungen der Informationsparameter, d. h. Schwarz-Weiß- bzw. Weiß-Schwarz-Übergänge, 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 Konturen des Zeichens zu beeinflussen. Ein Abtastverfahren, das nach diesem Prinzip zufriedenstellend arbeitet, hat den gro3en Vorteil, daß für die eigentliche Klassifizierung des abgetasteten Schriftzeichens ein Abtastergebnis erhalten wird, das praktisch noch den gesamten Informationsgehalt des Schriftzeichens besitzt. Das wirkt sich auf den Klassifizierungsprozeß insbesondere dann sehr günstig aus, wenn mit einem Zeichenerkennungsverfahren 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 sem 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 Konturenverlauf 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 Lichtstrahl¹ 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 Abtastprinzips deutlich. Einmal ist die Abtastgeschwindigkeit begrenzt wegen der notwendigen Suchvorgänge des Abtastsystems bei gestörten Zeichen, aber auch bei Zeichen, deren Konturverlauf nicht aus vollständig zusammenhängenden Konturen besteht, zum anderen ist das Abtastergebnis auch nicht in allen Fällen genau genug, daß daraus exakt der ursprüngliche Konturverlauf 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 ;harakteristisch sein sollen. Das bedeutet aber, da3 beim Abtastvorgang selbst schon eine wesentliche Reduktion des Informationsgehaltes des zu erkennenden Schriftzeichens vorgenommen wird und man dann auch nicht mehr die ursprünglichen Konturen des Schriftzeichens 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ß.

Ein Beispiel für ein derartiges Verfahren zum Erkennen von Linienzügen bei spaltenweiser Abtastung ist in IEEE International Convention Record, Part 4, 1963, S. 64 ff., in dem Aufsatz »A Stream-Following Technique for Use in Character-Recognition« beschrieben. Dort ist ein Verfahren zum Verfolgen von Linienzügen mit Hilfe spaltenweiser Abtastung eines Zeichens bzw. eines Vergleichs der Abtastergebnisse zweier aufeinanderfolgenden Spalten eines Abiastfeldes erläutert. Bei diesem Verfahren werden wie in vielen anderen eine Formelementanalyse anwendenden Verfahren zur Zeichenerkennung aus dem sukzessiven Vergleich der Abtastergebnisse in jeweils zwei aufeinanderfolgenden Abtastspalten einfache Kriterien zur Beschreibung dabei erkennbarer Linienzüge des abgetasteten Zeichens gewonnen. Diese Kriterien sind Linienzuganfang bzw. -ende, Linienzugfortsetzung, Divergenz beim Auftreten einer Verzweigung eines Linienzuges und Konvergenz bei miteinander verschmelzenden Linienzügen. Am Ende der Abtastung liegt bei diesem Verfahren zunächst also eine Kurzbeschreibung der aufgetretenen Linienzüge anhand der genannten Formelemente vor.

Für den vorliegenden Fall kann es dahingestellt bleiben, wie daraus im einzelnen Kriterien zum Erkennen des Zeichens abgeleitet werden, wesentlich ist nur, daß als Ergebnis des Abtastvorganges Linienzüge erkannt werden und ihre Form in einer Kurzbeschreibung anhand der sogenannten Formelemente zwischengespeichert wird. Diese vorteilhaft nur geringen Speicherplatz erfordernden Kurzbeschreibung reduziert aber den Informationsgehalt des abgetasteten Zeichens — wie oben ausgeführt -— in einer Weise, daß damit zugleich auch bereits der Erkennungs-Vorgang festgelegt ist. Dieser kann nur von den ermittelten Kriterien, also den Formelementen ausgehen, d. h., diese Elemente der Linienzugbeschreibung bilden zugleich auch die wesentlichen Erkennungskriterien. Das hat nicht nur den Nachteil, daß man sich damit also auch bereits auf ein bestimmtes Erkennungsverfahren beschränkt, sondern bedeutet auch eine gewisse Störanfälligkeit des gesamten Systems, denn verschmierte oder aufgerissene Zeichenteile führen zu anderen Formelementen und damit zu einer fehlerhaften Beschreibung des Zeichens, die als solche nicht nachprüfbar ist.

Die Erfindung geht daher von der Überlegung aus, daß es methodisch besser ist, einmal durch die Art der Zeichenbeschreibung als Ergebnis der Abtastung nicht bereits das Erkennungsverfahren festzulegen und zum anderen die Zeichenbeschreibung so auszubilden, daß sie möglichst exakt das abgetastete Zeichen widergibt. Das bedeutet, eine vom «wählten Pr.

kennungsverfahren unabhängige Zeichenbeschreibung bei einem Weiß-Schwairz-Ubergang, also einem Bild

sollte das Abtastergebnis ohne Unterdrückung von signalwechsel aus dem 2'ustand »0« in den Zustand »L

Zeichendetails im Vorgriff auf etwa für das gewählte in der «-ten Abtastspalte, den Wert»+1« besitzt, mi

Erkennungsverfahren irrelevante Informationen exakt den Ungleichungen der Anfang einer neuen Außen

widerspiegeln. Wollte man aber deswegen den ge- 5 kontur bzw. das Ende einer Innenkontur ermittel

samten Linienzugverlauf einschließlich der jeweils wird.

aufgetretenen Linienzugbreite zwischenspeichern, so Damit lassen sich die Vorteile eines spaltenweiser wäre das nicht nur aufwendig, sondern auch unzweck- Abtastprinzips auf einfache Weise verbinden mit der mäßig, da dann mit Sicherheit sehr viele redundante Vorteilen, die sich aus einer reversiblen Zwischeninformationen in der Zeichenbeschreibung enthalten io speicherung des Konturverlaufes eines abgetasteter wären. Diese Redundanz läßt sich aber, wie die Zeichens ergeben. Bei dem spaltenweisen Abtasterläuterten Konturverfolgungsverfahren zeigen, ver- prinzip wird einmal die Steuerung für die Auslenkung meiden, wenn man die Zeichenbeschreibung auf eine des das Schriftzeichen abtastenden Lichtstrahles beBeschreibung der Konturen des abgetasteten Zeichens sonders einfach und die genaue Zuordnung dei zurückführt, wobei diese bekannten Verfahren aller- 15 geometrischen Koordinaten des gerade abgetasteten dings den Nachteil komplizierter Abtaster zur Fest- Bildpunktes zu dem gesamten Abtastfeld möglich, stellung der Konturen haben. Außerdem geht bei dieser Abtastung und dem an-Der Erfindung liegt daher die Aufgabe zugrunde, schließenden Zwischenspeichern des Abtastergebnisses ein Verfahren zum Ermitteln und Zwischenspeichern so wenig Information verloren, daß man diesen Voreines aus mehreren einzelnen Konturen zusammen- 20 gang in bezug auf das digitalisierte Bildsignal als gesetzten Konlurverlaufes eines Schriftzeichens zu reversibel bezeichnen kann. Das bedeutet eine Erschaffen, bei dem aber das Zeichen spaltenweise ab- leichteruug der späteren Klassifizierung, für die es getastet werden kann, um den Aufwand für die auch bei strengeren Anforderungen an das Zeichen-Steuerung des Abtastsystems bei den Suchvorgängen erkennungssystem wesentlich ist, daß das gesamte und die dafür benötigte Zeit zu vermeiden. Außerdem 25 Abtastergebnis zur Verfügung steht. So wird es dann soll dieser Konturenverlauf allein aus dem digitali- z. B. möglich, wie bereits vorgeschlagen wurde, den sierten Abtastergebnis jeweils zweier aufeinander- eigentlichen Klassifizierungsvorgang in mehreren folgender Abtastspalten derart gewonnen werden Schritten durchzuführen und damit die Rückweisungskönnen, daß die Gesamtheit der Konturen eines rate zu senken.

Zeichens reversibel in einem verhältnismäßig einfach 30 Diese Vorverarbeitung der bei der Abtastung geaufgebauten Speicher auch schon bei kleiner Speicher- wonnenen Bildsignale ermöglicht eine besondere vorkapazität zwischengespeichert werden kann, wobei teilhafte Weiterbildung mit einem Konturspeicher, unter der reversiblen Zwischenspeicherung der Kon- der dadurch direkt adressierbar ist, daß mit der türen die Tatsache verstanden werden soll, daß die Adresse k einer Kontur die k-te Zeile des Kontur-Beschreibung den Konturverlauf exakt widergibt, so 35 Speichers ausgewählt wird, daß bei einem festgestellten daß daraus der Konturverlauf des abgetasteten Zei- Anfang zweier neuer Konturen mit den Adressen (it — 1) chens — abgesehen von der unvermeidlichen Digitali- und k sämtliche Zeilen des Konturspeichers, deren sierungsunschärfc — wider rekonstruierbar wäre. Adresse größer als (k—2) ist, in jeweils eine Zeile mit Diese Aufgabe wird erfindungsgemäß dadurch um zwei größerer Adresse umgespeichert werden und gelöst, daß in jeder Abtastspalte bei einem Zustande- 40 daß bei einem festgestellten Ende eines Konturpaares wechsel eines digitalisierten Bildsignals eine Kontur der Inhalt sämtlicher Speicherzeilen, deren Adressen festgestellt wird, daß jeder dieser Übergänge fort- höher sind als die Adressen des abgeschlossenen laufend gezählt und damit jeder Kontur eine be- Konturpaares, jeweils in Speicherzeilen mit um zwei stimmte Adresse zugeordnet wird, daß die in zwei kleinerer Adresse umgespeichert wird, sobald die aufeinanderfolgenden Abtastspalten auftretenden Dif- 45 Werte des abgeschlossenen Konturpaares in einen ferenzwerte der Ordinaten einer Kontur quantitativ weiteren kleineren Konturspeicher übertragen sind, ermittelt und in einem Konturspeicher gespeichert Damit wird erreicht, daß zu jedem Zeitpunkt die werden, daß aber durch einen Büdsignalwechsel nur Anzahl der im Konturspeicher belegten Zeilen gleich dann der Anfang zweier neuer Konturen festgelegt der Anzahl der Konturen in der abgetasteten Spalte wird, wenn für die Ordinaten zweier Konturen in zwei 50 ist. Neben dem geringen Speicherplatzbedarf bei der aufeinanderfolgenden Abtastspalten n, m eine erste Konturspeicherung bedeutet es aber auch eine beson-Ungleichung ders einfache Auswahl der Speicherplätze.

Andere Weiterbildungen der Erfindung sind in

Yn(K) S /TH(A-IJ + C Unteransprüchen gekennzeichnet.

55 Zum besseren Verständnis werden im folgenden

erfüllt ist, bzw. durch den Bildsignalwechsel nur dann Einzelheiten und ein Ausführungsbeispiel der Erfin-

das Ende zweier Konturen festgelegt wird, wenn eine dung im Zusammenhang mit einer Einrichtung zur

andere Ungleichung Durchführung eines erfindungsgemäßen Verfahrens

„ „. „ „ ,. , _ anhand der Zeichnungen näher beschrieben.

Yn (k) > im (fc+1) + C 60 Es zeigt

F i g. 1 die schematisierte Darstellung einer Zif-

erfüllt ist, wobei, sofern die Funktionsvariable (C) bei fer »2« mit den entsprechenden Konturen k,

einem Schwarz-Weiß-Übergang, also einem Bild- F i g. 2 das Schema einer Zeichenstruktur, bei der

signalwechsel aus dem Zustand »L« in den Zustand »0« eine neue Außenkontur in der Abtastspalte η auftritt,

in der «-ten Abtastspalte, den Wert »—2« besitzt, mit 65 F i g. 3 ein entsprechendes Schema mit dem Ende

den beiden Ungleichungen der Anfang einer neuen einer Innenkontur,

Innenkontur bzw. das Ende einer Außenkontur F i g. 4 bis 7 schematische Grenzfälle von Zeichenermittelt wird und, sofern die Funktionsvariable (C) Strukturen mit dem Anfang oder dem Ende von

Außen- bzw. Innenkonturen, anhand deren verschiedene Werte für die Funktionsvariablc C festgelegt werden und

F i g. 8 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 Schriftzeichens die durch Schwarz-Weiß-Übergänge oder Weiß-Schwarz-Ubergänge erzeugten Ränder der Linienzüge verstanden werden sollen. Diese Konturen sind in F i g. 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, durch unterbrochene Linien eingegrenzten. Mittelteil der Ziffer »2« läßt sich jede Kontur eindeutig nut den von Spalte zu Spalte auftretenden Differenzwerten der Konturordinaten beschreiben, wie die Tabelle 1 zeigt.

Tabelle 1
k I Ordinatendifferenz Yn (k) — Ym (k)

Tabelle 3

*Yn-Ym*	1	1	-1	0	0	2	SN	0
Merkmal	SP	SP	SN	HO	HO	VE	01	HO
10	10	01	00	00	11	00

6	1	1	-1	O	O	-2	O
5	2	O	O	O	—1	O	-2
4	O	1	1	1	O	1	2
3	1	O	1	1	1	O	1
2	O	O	O	O	O	1	-1
1	O	O	O	O	O	O	O

Dort sind in der ersten Zeile die Differenzwerte der Konturordinaten (Yn- Ym) nochmals dargestellt, die aus der Zeile k — 6 der Tabelle 1 übernommen wurden. In der zweiten Zeile der Tabelle 3 stehen die aus diesen 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 Elemenlarmerkmale gebildet werden können und dann auch müssen, um die Kontur an solchen Stellen eindeutig zu beschreiben. Das ist immer dann der Fall, wenn in zwei aufeinanderfolgenden Abtastspalten ein größerer Differenzwert als eins auftrritt, 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<i in F i g. 1, 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 Abtastspalte ein neues Konturenpaar auftritt, wie dies zum Beispiel schematisch in der F i g. 2 in der η-ten Abtastspalte mit zwei neuen Außenkonturen der Fall ist.

Um nun die Zuordnung der Bildsignalwechsel zu bestimmten Konturen aufrechtzuerhalten, müssen derartige Konturanfänge bzw. Konturenden erkannt werden, dazu reichen aber die Ordinaten der den Konturen zugeordneten Schwarz-Weiß-Übergänge und Weiß-Schwarz-Übergänge zweier benachbartei Spalten aus. Bezeichnet man mit Yn (k) die fc-te Konturordinate der eben abgetasteten Spalte η und mil Ym (k) die /c-te Konturordinate der vorher abgetaste ten benachbarten Spalte m und zählt man die Kontur adresse Ic in F-Richtung von unten nach oben, so is normalerweise der Wert einer höher adressiertei Konturordinate größer als der einer niedrig adressier ten benachbarten Konturordinate. Diese Regel win nur bei Konturanfängen und Konturenden durch brochen, wie dies auch aus den Darstellungen ii F i g. 2 und F i g. 3 hervorgeht. Allgemeiner aus gedrückt bedeutet das, daß bei einem Konturanfan; die Ungleichung

Yn(k) < Ym(k-l)+ C (1)

und bei einem Konturende die Ungleichung

Als Beispiel für die Beschreibung einer Kontur 65 Yn (k) > Fm(fc-|-1) + C (2)

anhand der Elementarmerkmale sei der Mittelteil der

sechsten Kontur der in der F i g. 1 dargestellten erfüllt sein muß, sonst setzt sich die schon bisht Ziffer »2« in Tabelle 3 erläutert. markierte Kontur fort.

509645/12

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 erwiesen, eine Kontur anhand von vier Elementarmerkmalen zu beschreiben, die als »Steigung positiv« (SP) bei ansteigendem Konturverlauf, »Steigung negativ« (SN) 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) Steigung negativ (SN) Vertikal (VE) Horizontal (HO)	10 01 11 00

Das Unterscheidungskriterium zwischen einer Au- den kann, ob nunmehr ein Paar von Innen- bzw. Denkontur, die in F i g. 2 dargestellt ist und einer Außenkonturen anfängt oder endet. Um mit diesem Innenkontur, wie sie F i g. 3 zeigt, ist die Übergangs- Ungleichungssystem in jedem Fall arbeiten zu können, richtung des Bildsignalwechsels in der gerade abge- muß man lediglich voraussetzen, daß zu jedem Zeittasteten Abtastspalte η zu einem Zeitpunkt, da die 5 punkt oberhalb und unterhalb der laufenden Kontur Ungleichung erfüllt ist. Sie verläuft für den Anfang Vergleichskonturen existieren. Das erreicht man z. B. oder das Ende einer Innenkontur gerade umgekehrt leicht durch Simulation von zwei Konturen am oberen wie bei einer Außenkontur, wie aus dem Vergleich bzw. unteren Bildrand.

der F i g. 4 mit der F i g. 5 bzw. der F i g. 6 mit Aus dem Vorstehenden wurde deutlich, daß man

der F i g. 7 hervorgeht. Dort sind schematisch io eine laufende Kontur mit Hilfe von vier verschiedenen Grenzfäile von Strukturkonstellationen dargestellt, Elementarmerkmalen reversibel beschreiben kann, mit denen der Wert der Funktionsvariablen C im die aus der Differenz der Konturordinaten benachbarte einzelnen festgelegt werden soll. Die F i g. 4 zeigt Abtastspalten gewonnen werden und daß man die in der η-ten Abtastspalte den Beginn eines neuen Beschreibung dieser Kontur vervollständigt, wenn Paares von Außenkonturen, bei dem in jedem Fall 15 man die Ordinaten ihres Anfangs und Endes erfaßt, die fc-te Konturordinate durch einen Schwarz-Weiß- Ein sogenannter Konturspeicher KSP, in dem der

Übergang des Bildsignals angezeigt wird. Für den Konturverlauf eines abgetasteten Schriftzeichens di-Zusammenhang zwischen beiden Konturordinaten rekt adressierbar zwischengespeichert werden kann, in den benachbarten Spalten gilt dann die Gleichung kann so aufgebaut sein, daß jeweils die gesamte Be- Y (i.\ __ Ym(Ie-W-I (3) ²⁰ Schreibung einer Kontur in einer entsprechenden

⁽ Speicherzelle gespeichert wird. Man kann nun sche-

da in jedem Fall das Schwarzelement als Teil der matisch den Konturspeicher KSPl spaltenweise in Kontur gewertet wird und somit die Ordinatendiffe- drei Speichereinheiten aufteilen. Die erste Speicherrenz den Wert »2« besitzt. einheit SKA besitzt zwei Spalten für die Koordinaten

Das bedeutet, bei einem Anfang von neuen Außen- 25 des Konturanfangs, die durch eine bestimmte der konturen ist die Funktionsvariable C = — 2. χ Abtastspalten als Abszissenwert und die y-Ordinate

In der F i g. 5 ist der entsprechende Grenzfall gegeben sind. Die zweite Speichereinheit SKE des für den Beginn eines neuen Paares von Innenkonturen Konturspeichers KSPl ist dementsprechend ebenfalls dargestellt, dem in der Abtastspalte η der Ä-ten Kon- aus zwei Spalten aufgebaut, die in analoger Weise die tür auf jeden Fall ein Weiß-Schwarz-Übergang des 30 Koordinaten für ein Konturende aufnehmen. Die Bildsignals zugeordnet ist. Für die beiden interessieren- dritte Speichereinheit des Konturspeichers, der Merkden Konturordinaten ergibt sich dann die Gleichung malspeicher SM, enthält schließlich in jeder ihrer Y_n ι^\ — Y_m(k — \\4-\ (4) Speicherzellen sämtliche Elemenlarmerkmale, die jene

Kontur beschreiben, die dieser Zeile zugeordnet ist.

und um die Ungleichung (1) zu erfüllen, folgt daraus 35 Um nun die direkte Adressierung des Konturdie Funktionsvariable C = I. Speichers und damit die einfache Speicherplatzauswahl

In der F i g. 6 ist das Ende eines Paares von Außen- aufrechterhalten zu können, müssen bei jedem Konikonturen dargestellt, bei dem in der Α-ten Kontur- turanfang eines neuen Konturpaares zwei Speicherordinate der Abtastspalte η ein Weiß-Schwarz-Über- zeilen dieses Konturspeichers KSPl zur Aufnahme gang des Bildsignals stattfindet. Diese Struktur- 40 der Konturbeschreibung bereitgestellt werden. Sind konstellation läßt sich durch die Gleichung in dem Konturspeicher bereits die Beschreibungen

Yn (k) — Ym (k -t-1) -4- 2 (5) laufender Konturen enthalten, deren Ordnungszahl

sich jetzt durch das Auftreten eines neuen Konturen-

beschreiben. In der Ungleichung (2) ist dann die paares ändert, so müssen die Speicherzeilen des Funktionsvariable C- 1. 45 Konturspeichers KSPl, deren Adressen höher als

Die F i g. 7 zeigt schließlich die vierte Möglich- (A-- 1) sind, jeweils um zwei Zeilen nach oben umgekeit, nämlich den Grenzfall für das Ende eines Innen- speichert werden, dann können die Anfangskoordinakonturpaares ir der Abtastspalten, wobei in dieser ten der neuen Konturen Yn (A) und Fw(A-I) in Abtastspalte bei der A--ten Konturordinate ein Schwarz- die frei gewordenen Speicherzeilen aufgenommen Weiß-Übergang des Bildsignals auftritt. Die Bezie- 5° werden. Dasselbe gilt umgekehrt auch für das Ende hung zwischen den beiden zu vergleichenden Kontur- einer Kontur, zunächst werden die Merkmalsätze dei ordinaten abgeschlossenen Kontur in einen weiteren Speichel

Yn (k+l) und Yn (k) übertragen, wenn dabei gleichzeitig eine Merkmal

reduktion vorgenommen wird, kann d eser zweitf

ist hier durch die Gleichung 55 Konturspeicher KSPl, der ansonsten im wesentlichsi

Y_n (k) — Ym (k+l) — 1 (6) ähnlich aufgebaut ist, noch kleiner dimensionier

werden. Nun können alle Speicherzeilen des erstei

gegeben, um die Ungleichung (2) zu erfüllen, muß die Konturspeichers KSPl, deren Adressen größer al Funktionsvariable C in diesem Fall wiederum den (k + 2) sind, um zwei Zeilen nach unten verschöbe' Wert »—2« annehmen. 60 werden. Damit wird erreicht, daß zu jedem Zeitpunk

Daraus ergibt sich allgemein, daß die Funktions- die Anzahl der im ersten Kor.turspeicher KSPl be variable C in den Ungleichungen (1) bzw. (2) bei legten Zeilen gleich der Anzahl der Konturen in eine einem Schwarz-Weiß-Übergang in der η-ten Abtast- gerade abgetasteten Spalte ist. Nach dem Umspeicher spalte jeweils den Wert »—2« bzw. bei einem Weiß- der Merkmalsätze noch laufender Konturen muß di Sclnvarz-Übergang den Wert »1« annimmt. Das be- 65 Bedingung für ein Konturende auf Grund der Ui deutet, daß immer dann, wenn eine der beiden Un- gleichung (2) erneut abgefragt werden, um eventue gleichungen (1) oder (2) erfüllt ist, aus der Richtung mehrere direkt übereinanderliegende Konturenpaai des Zustandswechsels eines Bildsignals ermittelt wer- einer Spalte erkennen zu können. Zeigt sich dann, da

11 12

keine der beiden Ungleichungen (1) oder (2) für einen Erfüllung der Ungleichung (1) an, so werden die

gerade abgetasteten Bildsignalwechsel erfüllt ist, so Werte Yn (A — 1) und Yn (A) und die Spaltenposition χ

stellt das das Kriterium für die Fortsetzung einer mar- als Koordinaten der beiden Konturanfänge in den

kicrten Kontur dar. Die aus dem Differenzwert der ersten Konturspeicher KSPI übertragen, nachdem

Konturordinaten ermittelten Elementarmerkmale wer- 5 vorher eine Verschiebung der Merkmalsätze größerer

den dann codiert und in den Merkmalspeicher SM Adresse um jeweils zwei Konturspeicherzeilen nach

eingeschrieben. oben in Abhängigkeit vom Konturmarkierer KZ er-

An Hand der Glockdarstellung einer Einrichtung folgte. Eine Steuereinheit ADR enthält dazu eine

zur Durchführung des erläuterten Verfahrens, die in Verschiebeeinheit, einen Merkmalzähler und einen

F i g. 8 dargestellt ist, seien im folgenden seine bisher io Adressenwähler zur Ansteuerung des Konturspeichers

einzeln behandelten Merkmale nochmals zusammen- KSPl.

fassend dargestellt. Bei einem Konturendesignal werden analog

Die F i g. 8 zeigt vier verschiedene Speicher, als Tm(A-H) und Ym (k) und X als die Ordinaten des Arbeitsspeicher den ersten Konturspeicher KSPl mit Konturendes in den Konturspeicher KSPl überder Spe cheieinhcit SKA zur Speicherung der Kontur- 15 tragen. Der Inhalt der zugehörigen Konturspeicheranfänge, der Speichereinheit 5A'£ zur Speicherung zeilen kann nach einer Merkmalreduktion in dem der Konturenden und dem Merkmalspeicher SM zur Merkmalreduktor RED in den zweiten Konturspeicher Speicherung der Eicmentarmerkmale einer Kontur. KSPl übertragen werden. Für die Auswahl der ent-Dazu kommt als Ergebnisspeicher der zweite Kontur- sprechenden Speicherzeilen der Konturspeicher A'5P1 speicher KSPl, der wie der erste 16 Zeilen besitzen 20 und KSP2 dienen die durch den Konturmarkierer KZ möge, wobei aber das in einer Speicherzeile zu spei- gesteuerten Vielfachschalter 55 bzw. 56. Die Merkchernde Wort nur noch halb so groß sein möge. maisätze größerer Adresse können nun um zwei Zeilen

Außerdem ist eine Speicherspalte 5Ym für die abwärts verschoben werden. Dies wird wiederum Konturordinaten der zuletzt bearbeiteten Abtast- durch die Adressensteuerung ADR des Konturspeichers spalte m mit 16-6 Bit vorgesehen, die mit dem 25 KSPl vorgenommen. Wird dagegen durch die Ver-Konturspeicher KSPl zeilengekoppelt ist. Dieser er- gleichsschaltungen KA V bzw. KEV weder ein Konturstcn Speicherspalte 5Ym entspricht schließlich als anfing noch ein Konturende festgestellt, so gilt die vierter Speicher eine weitere Speicherspalte 5Yn für nächste, bereits markierte Kontur als fortgesetzt und die Konturordinaten der laufenden Abtastspalte/; die Ordisiatcndifferen? Tn(A)-Tm(A) wird in dem mit ebenfalls 16 -6 Bit. Je zwei zeitlich aufeinander- 30 Differenzglied DJF festgestellt. Daß weder die Unfolgende Bildsignale des Abtasters AB entscheiden, gleichung (1) noch die Ungleichung (2) erfüllt ist, ob ein Schwarz-Weiß-Übergang oder ein Weiß- wird durch den logischen Schaltkreis KFL festgestellt, Schwarz-Übergang vorliegt. Dieses Kriterium wird der an die Ausgänge der beiden Vergleichsschallungen in der Schwarz-Weiß-Logik SWL ermittelt. Jeder KA V und KFl angeschlossen ist. Der Trennschalter sdchc Bi'dsignalwechse! wird in dem Konlurmarkierer 35 5A'4 wird geschlossen, und damit ist das Differenz- KZ gezählt, mit dieser Ordnungszahl ist zugleich die glied DIF an den Eingang eines Codewandlers COW Konturadiesse A festgelegt. Entsprechend dieser Kon- angeschlossen. Dort werden aus dem festgestellten turadresse steuert er die ein/einen Vielfachschalter Differenzwert der Konturordinaten die Elemenlar-51 bis 56. Bei einem Bildsignalwechsel wird die merkmale ermittelt, die dann entsprechend der Ein-Konturordinate von der AHaststeucrung AST über 40 stellung des Vielfachschalters 54 in die A-te Zeile des einen ersten Vieifachschalter 51 auf eine der 16 Merkmaispeichers SM übernommen werden.
Speicl.erstdlen der zweiten Speicherspalte SYn über- Vorstehend wurden die Merkmale der Erfindung tragen. Bei einem Spaltenende, das \on der Abtast- und ein Ausführungsbeispiel näher erläutert. Es sind steuerung AST dirch den nefehl SPF angegeben aber im Rahmen der Erfindung durchaus noch andere wird, werden die Kontakte des Trer nschalters 5A1 45 Losungswege erdenkbar. Wenn z. B. mehrere Konturdurchgeschaltet, und die erste Speicherspalte 5Tn; anfange oder Konturenden zeitlich dicht aufeinanderübernimml den gesamten Speicherinhalt der Speicher- folgen, kann unter Umständen die vom Abtastspalte 5Tn, gleichzeitig wird der Konturmarkierer KZ programm zur Verfugung gestellte Zeit zur Ausfühauf k - 0 zurückgesetzt. rung der Rechenoperationen nicht mehr ausreichen.

Bei jedem Bildsignalwechsel, der einem Schwarz- 50 Hier brächte dann eine zeitliche Entkopplung mit Weiß-Übergang oder einem Weiß-Schwarz-Übergang Hilfe einer gepufferten Speicherspalte SYn den Vorentspricht, werden durch die Vielfachschalter 52 und teil, die Rechenoperationen auf die Spaltenabtastzeit S3 zwei bzw. drei der Ausgänge der beiden Speicher- beliebig verteilen zu können. Außerdem ist es ohne spalten 5Γ« und SYm auf die Ausgänge der beiden weiteres denkbar, ein erfindungsgemäßes Verfahren Vielfachschalter 52 bzw. 53 durchgeschaltet und 55 nur mit einem Konturspeicher zu realisieren, wenn damit die Werte Yn (A), Tn(A-H) bzw. Ym (A), abgeschlossene Konturen im Konturspcicher verblei-Fm(A-I), Tw (A-+1) zu den beiden Vergleichs- ben. Dann ist allerdings die Adresse einer Vergleichsschaltungen KAV und KFJ übertragen, in denen die kontur nun im allgemeinen nicht mehr der laufenden beiden Ungleichungen (1) und (2) logisch realisiert Konturadresse benachbart, sondern muß unter der sind und mit denen damit Bedingungen für einen 60 Berücksichtigung einer Kennzeichnung bestimmt wer-Konturanfang bzw. ein Konturende festgestellt wer- den. die 1. B. auf Grund der Konturenden erfolgen den. Zeigt die erste Vergleichsschaltung KA V die kernte.

Hierzu 2 Blatt Zeichnungen

Claims

Patentansprüche

1. Verfahren zum Ermitteln und Zwischenspeichern eines aus mehreren einzelnen Konturen zusammengesetzten Konturverlaufes eines spaltenweise abgetasteten Schriftzeichens mit Hilfe der Abtastergebnisse zweier jeweils aufeinanderfolgender Abtastspalten, dadurch gekennzeichnet, daß in. jeder Abtastspalte (x) bei einem Zustandswechsel des digitalisierten Bildsignals eine Kontur (fc) 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 Differenzwerte der Ordinaten Ym, (fc), Yn (fc) einer Kontur quantitativ ermittelt und in einem Konturspeicher (KSPl) gespeichert werden, daß aber durch einen Bildsignalwechsel dann und nur dann der Anfang zweier neuer Konturen festgelegt wird, wenn für die Ordinaten (F) zweier Konturen (fc — 1, fc) in zwei aufeinanderfolgenden Abtastspalten (w, ti) eine erste Ungleichung

Yn (fc) < Ym (fc-1) + C

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

Yn(Jc) > Ym{k+l) + C

erfüllt ist, wobei, sofern die Funktionsvariable (C) bei einem Schwarz-Weiß-Übergang, also einem Bildsignalwechsel aus dem Zustand »L« in den Zustand »0« in der η-ten Abtastspalte, den Wert »—2« besitzt, mit den beiden Ungleichungen der Anfang einer neuen Innenkontur bzw. das Ende einer Außenkontur ermittelt wird und, sofern die Funktionsvariable (C) bei einem Weiß-Schwarz-Übergang, also einem Bildsignalwechscl aus dem Zustand »0« in den Zustand »L« in der n-ten Abtastspalte, den Wert »+1« besitzt, mit den Ungleichungen der Anfang einer neuen Außenkontur bzw. das Ende einer Innenkontur ermittelt wird.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß am oberen und unteren Rand des Abtastfeldes ständig je eine Kontur als Vergleichskontur simuliert wird.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß der Verlauf einer Kontur durch Elementarmerkmale »Steigung positiv« (SP) bei ansteigendem, »Steigung negativ« (SN) bei abfallendem, »horizontal« (ZiO) bei horizontalem uud »vertikal« (VE) bei vertikalem Konturverlauf beschrieben wird.

4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, daß die Elementarmerkmale (SP, SN, HO und VE) aus den Differenzen der Konturordinaten benachbarter Abtastspalten derart ermittelt werden, daß eine positive Ordinatendifferenz vom Betrag d einem Elementarmerkmal »Steigung positiv« (SP) und einer Folge von (d—l) Elementarmerkmalen »vertikal« (VE), eine negative Ordinatendifferenz vom Betrag d dagegen einer Folge von (d—l) Elementarmerkmalen »vertikal« (VE) und einem Elementarmerkmal »Steigung negativ« (SN) entspricht und daß das Elementarmerkmal »horizontr-1« (HO) vorliegt, wenn die Ordinatendifferenz »0« ist.

5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß der Konturspeicher (KSPl) dadurch direkt adressierbar ist, daß mit der Adresse k einer Kontur die fc-te Zeile des Konturspeichers ausgewählt wird, daß bei einem festgestellten Anfang zweier neuer Konturen mit den Adressen (fc—1) und it sämtliche Zeilen des

ίο Konturspeichers, deren Adresse größer als (fc—2) ist, in jeweils eine Zeile mit um zwei größerer Adresse umgespeichert werden und daß bei einem festgestellten Ende des Konturenpaares der Inhalt sämtlicher Speicherzeilen, deren Adressen höher sind als die Adressen des abgeschlossenen Konturenpaares, jeweils in Speicherzeilen mit um zwei kleinerer Adresse umgespeichert wird, sobald die Werte des abgeschlossenen Konturenpaares in einen weiteren kleinen Konturspeicher (KSP2)

ao übertragen sind.

6. Einrichtung zur Durchführung eines Verfahrens nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, daß zwei Speichereinheiten (S Yn und 5Fw) 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 (SFw, SYn) je ein durch die Bildsignalwechsel steuerbarer Vielfachschalter (S2 bzw. S3) zugeordnet ist und die entsprechenden Ausgänge (A, B bzw. C, D und E) dieser Vielfachschalter über steuerbare Trennschalter (SKI bzw. SK3) mit den Eingängen zweier zum Speichern der Anfänge bzw. der Enden von Konturen vorgesehenen Speichereinheiten SKA, SKE) des Konturspeichers (KSPl) verbunden sind, daß Ausgänge der Vielfachschalter (S 2 und S3) außerdem mit zwei Vergleichsschaltungen (KA V bzw. KEV) zum Feststellen von Konturanfängen bzw. Konturenden durch die jeweils einer der beiden Trennschalter (SA'2 bzw. SK3) gesteuert wird und weiterhin mit einem Differenzglied (DIF) zum Bilden der Differenzwerte der Konturordinaten zweier beuach-

4f, barter Abtastspalten verbunden sind und daß dieses Differenzglied über einen weiteren Trennschalter (SK4), einen Codewandler (COW), in dem aus den Differenzwerten der Konturordinaten die Elementarmerkmale (Sf, SN, VE, HO) in codierter Form ermittelt werden, an den Eingang eines weiteren steuerbaren Vielfachschalters (S 4) angeschlossen ist, dessen Ausgänge je einer Zeile eines sogenannten Merkmalspeichers (SM) des Konturspeichers (KSPl) zugeordnet sind.