DE2303485A1

DE2303485A1 - Verfahren und anordnung zum skelettieren von zeichen

Info

Publication number: DE2303485A1
Application number: DE2303485A
Authority: DE
Inventors: Matthijs Beun
Original assignee: Philips Gloeilampenfabrieken NV
Current assignee: Koninklijke Philips NV
Priority date: 1972-01-28
Filing date: 1973-01-25
Publication date: 1973-08-02
Also published as: FR2169644A5; NL7201225A; JPS4885046A; GB1424551A; US3940737A

Description

PEIN.6096. JW/EVH.

Günter W A G E N E R
P a"t ent as s β s sor

Anmelderi H.Y.PHILIPS' GLOEILAMPEHPABRIEKEH 2303485

Aktes PHH-6096 .... . ... ....

Anm..vom: 24. Jan. 1973

Verfahren und Anordnung zum Skelettieren von Zeichen.

Die Erfindung bezieht sich auf ein Verfahren zum Skelettieren von Zeichen, die auf einem zweidimensionalen regelmässigen Muster von Positionen präsentiert werden, wobei eine Zeichenposition durch vorhandene digitale Information von einer Umgebungsposition unterschieden wird und die Zeichen von überflüssigen Informationen dadurch befreit werden, dass die Information einer Zeichenposition in die einer Umgebungsposition so geändert wird _s bis ein Skelettzeiclien erhalten wird, dessen Zeichsnelemente aus einfachen Reinen entsprechend einem Nachbarschaftskriterium aufeinanderfolgender Zeichenpositionen bestehen, und die Skelletierung in Zyklen erfolgt, wobei während eines Zyklus die Positionen <Ies "/.<- iuhenf eldeti in re ^e 1 ».lässiger und fester Reihenfolge

:09ß31 /0985

- 2 - PHN.6096.

behandelt werden, wobei während eines Zyklus jene Zeichen-Positionen, die sich, entsprechend einem Randkriterium an einem Rand des Zeichens befinden, in einem ersten Subzyklus dadurch markiert werden, dass der Information dieser.Zeichenpositionen eine zusätzliche Information zugefügt wird. Ein derartiges Verfahren ist aus der U.S.-Patentschrift 3.339.179 (g.L. Shelton) bekannt. In einer Anzahl Zyklen werden die Zeichenpositionen dadurch markiert, dass ihnen ein ZMhlsaldo zugefügt wird« Dieser Saldo wird nach einem der Autokorrelation ähnelnden Verfahren gebildet, er nimmt in jedem Zyklus zu. In einer Anzahl nachfolgender Zyklen werden die Zeichenpositionen, deren ZMhlsaldi zwischen bestimmten Grenzen liegen, mit einem Ufaeitbehrlichkeitskriterium verglichen. Es stellt sich heraus, dass auf diese Weise oft weniger gute Resultate erzielt n und die Erfindung betrifft dalier ein System, bei dem

eines ersten Subssyklusses in jedem Zyklus die Markierung versorgt wird. Weiter wird nach der genannten Patentschrift derart rigoros skelettiert, dass leicht charakteristische Element© der Zeichen verschwinden! Fig. 3 gibt ein Beispiel eines slsslettierten Majuskels "F". Einerseits hat der Querbalken auf* halber HShe die charakteristische Verdickung (seriph) am Ende.fast verloren» Andererseits bleiben noch überflüssige 2eiclieiip.ositionen übrig«

Es stellt sich also heraus, dass man einerseits weniger rigoros skelettieren möchte. Es stellt sich heraus, dass dann gleich kurze herausragende Zeicherielemente entstehen können. Diese können der Rest einer Verdickung im ursprünglichen Zeichen sein. Aber selbst trenn keine Verdici--im.--; vorh'iiidnn ν·:-·χ'

- 3 - PHN.6096.

können sie gleichsam "zufällig" entstehen. Wenn sie nicht übereinstimmen mit Kennzeichen (beispielsweise mit einer "Ausbäulung" des ursprünglichen Zeichens müssten sie fortgelassen werden. Es wurde vorgeschlagen, sie nach dem Skelettieren zu entfernen, dies aber birgt die Gefahr in sich, dass die falschen kurzen herausragenden Zeichenelemente entfernt werden können. Besser ist es, das Entstehen dieser Zeichenelemente überhaupt zu vermeiden. Die Erfindung schafft dies dadurch, dass die auf diese Weise markierten Zeichenpositionen während dieses Zyklusses nacheinander zunächst in einem zweiten Subzyklus mit einem ersten Unentbehrlichkeitskriterium verglichen werden, auf Grund dessen sie fortgelassen bzw. beibehalten werden und danach die auf diese Weise noch beibehaltenen markierten Zeichenpositionen in einem dritten Subzyklus mit einem zweiten Unentbehrlichkeitskriterium verglichen werden, auf Grund dessen sie fortgelassen bzw. beibehalten werden, wobei die im zweiten Subzyklus fortgelassenen Zeichenpositionen im dritten Subzyklus als Umgebungspositionen auftreten. Man kann das erste und das zweite Unentbehrlichkeitskriterium einander anpassen und auf diese Weise das Entstehen dieser kurzen herausragenden Zeichenelemente vermeiden, ohne dass ε 11 zu rigoros skelectiert werden muss.

Das in der genannten U.S.-Patentschrift 3.339.179

angewandte Unentbehrlichkeitskriterium behält Zeichenpositionen, durch deren Fortlassung eine Unterbrechung oder eine Schleife xsii Zeichen entstehen würde. Ein zusammenfassendes Kriterium könnte die "Rangordnung" einer Zeichenposition sein. Diese wird als die Komplexität (multiplicity) definiert, nach der

309831/0985

- h - PHN.6096.

eine Zeichenposition an eine Anzahl untereinander ein geschlossenes Muster bildender Gruppen von Zeichenpositionen grenzt. Das kann einfach, zweifach, usw. sein. Man geht nacheinander an den einer Zeichenposition benachbarten Positionen entlang und zählt wie viele Male der Zusammenhang unterbrochen ist. Dies ist die Rangordnung der zentralen Zeichenposition. Nur wenn die Rangordnung eins ist, entsteht bei Fortlassung keine Schleife bzw. Unterbrechung. Beispiele davon werden noch gegeben.

Die herausragenden Zeichenelemente fangen ihre Entwicklung bei einem Endpunkt an. Deswegen muss das Entstehen der Endpunkte gut unter Kontrolle bleiben. Sie entstehen auf dreierlei Weise»

a) Bei einem Zyklus entspricht eine Zeichenposition nicht dem Randkriterium und wird beim ersten Subzyklus (Markierabtastung) also nicht markiert. Beim zweiten und dritten Subzyklus (Skelettierabtastungen) verliert sie soviele markierte Nachbarn ( diese entsprachen in diesen Subzyklen den Unentbehrlichkeitskriterien nicht), dass sie ein Endpunkt wird. Es kann sein, dass sie nur noch eine benachbarte Zeichenposition übrig hat oder auch zwei, die einander wieder benachbart sind.

b) Während eines Subzyklusses (Skelettierabtastung) verliert eine markierte Zeichenposition eine Anzahl benachbarter Zeichenpositionen. Wenn sie dann selbst an der Reihe ist, um mit einem Unentbehrlichkeitskriterium verglichen zu werden, stellt es sich heraus, dass sie einen Endpunkt bildet,

3098 31/0985

- 5 - PHN.6096.

2103485

c) Eine markierte Zeichenposition wird zunächst mit

einem Unentbehrlichkeitskriterium während eines Subzyklus verglichen. Dabei stellt es sich heraus, dass sie unentbehrlich ist (beispielsweise weil ihre Rangordnung nicht eins entspricht). Danach werden noch benachbarte markierte Zeichenpositionen mit dem Unentbehrlichkeit skriterium verglichen und fortgelassen. Am Ende dieses Subzyklus stellt es sich heraus, dass die beibehaltene Zeichenposition einen Endpunkt bildet. Es hängt davon ab, ob die Fälle b) und c) Endpunkte Von charakteristischen Zeichenelementen ergeben, die zur Wiedererkennung notwendig sind. Oft wird dies nicht der Fall sein. Es wird nun vorausgesetzt, dass markierte Endpunkte nicht als unentbehrlich betrachtet werden. Wenn die im Fall c) beibehaltene Zeichenposition abermals mit diesem letzten Unentbehrlichkeitskriterium verglichen wird, wird sie nachträglich fortgelassen werden. Weiter hängt es oft von der Reihenfolge, in der die Zeichenpositionen geprüft werden ab, welche Zeichenpositionen fortgelassen werden. Durch das erfindungsgemässe Verfahren ist dies weniger wahrscheinlich.

Eine weitere Ausarbeitung der Erfindung weist das Kennzeichen auf, dass auf Grund des ersten Unentbehrlichkeitskriteriums nur diejenigen markierten Zeichenpositionen beibehalten werden» deren Fortlassung eine Unterbrechung oder eine Schleife im Zeichen entstehen lassen würde und auf Grund des zweiten Unentbehrlichkeitskriteriums nur diejenigen Zeichenpositionen fortgelassen werden, die auf die Art und Weise eines Endpunktes (Schweifpunkt) aus dem Zeichen herausragen,

309831/0985

- $ - PHN.6P96

Erfahrungsgemäss hat sich herausgestellt, dass ein derartiges Verfahren gute Resultate ergibt. Im zweiten Subzyklus werden viele Zeichenpositionen geprüft und von diesen wird ein beträchtlicher Prozentsatz fortgelassen. Im dritten Zyklus werden die gegebenenfalls auftretenden Endpunkte von sich entwickelnden herausragenden Zeichenelementen entfernt.

Eine Weiterbildung der Erfindung besteht darin, dass den Zyklen ein Glättungszyklus vorhergeht, in dem Zeichenpositionen, die entsprechend einem Glättungskriterium aus dem Zeichen herausragen, fortgelassen und Umgebungspositionen, die in das Zeichen einbäulen, zu Zeichenpositionen gemacht werden und dass bei den nachfolgenden Zyklen Zeichenpositionen, die nach einem Herausragungskriterium aus dem Zeichen herausragen, von Markierung ausgeschlossen werden. Es hat sich gezeigt, dass diese Kombination ein gutes Resultat ergibt. Namentlich bleiben die Zeichenpositionen nach dem obenstehenden Fall a) beibehalten. Diese bilden fast immer Endpunkte von charakteristischen Zeichenelementen des Skelettcharakters.

Die Erfindung bezieht sich auch Auf eine Anordnung zum Gebrauch beim Skelettieren von Zeichen, welche auf einem Träger präsentiert werden. Sie enthält einen Aufnehmer, der die Information der Zeichen auf einer vorhandenen Speicheranordnung abbildet, wodurch die genannten Zeichen als digitale Information von Zeichenpositionen bzw, Umgebungspositionen gespeichert werden. Diese Positionen sind nach einem zweidimensional en regelmässigen Muster von Positionen auf dem Träger gegliedert. Die Anordnung enthält weiter eine Skelettieranox-dnung, der mindestens die Information der Zeichenpostionen

309831/0985

- 7 - PHN.6096.

zuführbar ist und wodurch die Information von Zeichenpositionen in die von Umgebungspositionen änderbar ist, bis die in der genannten Speicheranordnung gespeicherte Information von Zeichenpositionen auf die Information von Zeichenpositionen von Skelettzeichen verringert ist, deren Zeichenelemente aus einfachen Reihen einander nach einem Benachbarkeitskriterium

auffolgender Zeichenpositionen bestehen, wobei das Skelettieren durch eine Steueranordnung in Zyklen gesteuert wird, wobei während eines Zyklus Information de? Positionen des Zeichenfeldes in einer regelmassigen und festen Reihenfolge der Skelettieranordnung zuführbar ist und wobei während eines Zyklus in einem ersten Subzyklus mindestens die Information der Zeichenpositionen zusammen mit der Information der diesen Zeichenpositionen benachbarten Positionen einer ersten Entscheidungsanordnung zuführbar sind, in der ein Randkriterium eingebaut ist, welche erste Entscheidungsanordnung der Information jener Zeichenpositionen, für die das genannte Randkriterium erfüllt ist, zusätzliche Information zufügt. Der Aufnehmer kann aus einem Lichtpunktabtaster (flying spot scanner) bestehen und die Speicheranordnung aus einer Matrix bistabiler Elemente. Durch das Skelettieren wird die Redundanz kleiner und kann leichter wiedererkannt werden. Die Skelettierung erfolgt dadurch günstig, wenn in Weiterbildung der Erfindung danach in einem zweiten Subzyklus die Information der Zeichenpositionen zusammen mit der genannten zusätzlichen Information einer zweiten Entscheidungsanordnung zuführbar ist, in der ein erstes Unentbehrlichkeit skrit erium eingebaut ist und wodurch, wenn zwar das Randkriterium, nicht aber das

309831/0985

- 8 - PHN.6096.

erste Unentbehrlichkeitskriterium erfüllt ist, die Information der betreffenden Zeichenposition in die der Umgebungsposition änderbar ist, und wenn danach in einem dritten Subzyklus die Information der restlichen Zeichenpositionen zusammen mit der genannten zusätzlichen Information einer dritten Entscheidungsanordnung zuführbar ist, in der ein zweites Unentbehrlichkeitskriterium eingebaut ist und wodurch, wenn zwar das Randkriterium erfüllt war, nicht aber das zweite Unentbehrlichkeitskriterium, die Information der betreffenden Zeichenposition in die einer Umgebungsposition änderbar ist, wonach diese gegebenenfalls geänderte Information an einem Ausgang erscheint.

Die zweiten und dritten Entscheidungsanordnungen können unterschiedlich oder einander entsprechend aufgebaut sein. Wenn sie identisch sind, ist es sogar möglich, dass die zweite und dritte Entscheidungsanordnung dieselbe Anordnung sind, die zweimal durchlaufen wird.

Ein Ausführungsbeispiel der Erfindung ist in den

Zeichnungen dargestellt und wird im folgenden näher beschrieben. Es zeigern

Pig. 1 einige übliche Muster von Positionen, Fig. 2-16 einige Beispiele der "Rangordnung",

Fig. 17-21 ein Beispiel des Skelettierens nach einer älteren Technik,

Fig. 22 ein Beispiel eines Skelettierresultates nach der vorliegenden Erfindung,

Fig, 23-24 eine Darstellung zur Demonstration des Nutzens eines Glättungszyklus,

3098 31/0985

- 9 - PHN.6096.

Fig. 25 ein Blockschema einer erfindungsgemässen Anordnung,

Fig. 26 eine Darstellung eines Skelettierspeichers und eines .Merkspeichers,

Fig. 27 eine Darstellung einer Anordnung die ein Randkriterium erzeugt,

Fig. 28 eine Darstellung einer Anordnung, die markierte Zeichenpositionen mit einem Unentbehrlichkeitskriterium vergleicht ,

Fig. 1 zeigt drei übliche Muster von Positionen. Die Positionen sind durch Punkte angegeben. Durch eine Linie ist angegeben, in welcher Richtung eine benachbarte Position liegt. Die Positionen haben also k, 6 bzw. 8 Nachbarn.

Die Fig. 2-16 zeigen Beispiele zur Bestimmung der "Rangordnung" der zentralen Zeichenposition. Zeichenpositionen sind durch einen von einem Kreis umgebenen Punkt angegeben. Es sind eine Anzahl Verbindungen dargestellt um die Komplexität anzugeben, mit der die zentrale Zeichenposition an eine Anzahl untereinander ein geschlossenes Muster bildender Gruppen von Zeichenpositionen grenzt. Gestrichelte Linien bedeuten Verbindungen im Falle, dass eine Position acht Nachbarn hat{ die gezogenen Linien gelten in den Fällen mit vier bzw. sechs Nachbarn. Die Rangordnung ist nun wie folgt j

309831 /0985

PHN.6096.

Figur	Nachbarn	Rang ordnung	Nachbarn	Rang ordnung	Nachbarn	Rang ordnung
2	4	0			8	0
3			6	0
4			6	#
5	^	1			8	0
6			6	1
7	4	#			8	1
8	4	1			8	1
9	4	1			8	1
10			6	2
11	4	1			8	3
12	4	2			8	3
13	4	*			8	4
14.			6	3
15	4	1			8	2
16	4	4			8	4

Die durch, einen Stern bezeichneten Fälle betreffen isolierte Zeichenpositionen.» Diese FSlIe lassen sich leicht einzeln detektieren. Fig_# 3 zeigt die Hangordnimg UuIl und Tbei Portiassung dieser Zeichesposition würde eine Schleife entstellen« Es stellt sich heraus, dass die Rangordnung von der Anzahl Hachbarn, die in. Betracht gesogen werden, abhängig ist» Die der zentralen Zeichenposition benachbarten Positionen bilden einen sogenannten Kranz um! die Rangordnung kann auch als die Anzahl Male, dass dieser Kranz anterbrochen, ist, angegeben werden*

309831/0985

- 11 - PHN.6096.

Die Fig. 17-21 geben ein Beispiel des Skelettierens entsprechend der deutschen Patentanmeldung P 21 5^ 411,6. Pig. 17 zeigt ein nach rechts herausragendes Zeichenelement, beispielsweise einen horizontalen Balken eines Majuskels "F", Zeichenpositionen sind durch einen von einem Kreis umgebenen Punkt angedeutet und Umgebungspositionen nur durch einen Punkt. Der Teil des Zeichens zur linken Seite der vertikalen Linie wird nicht betrachtet. Das .Randkriterium lautet wie folgt: es wird eine Matrix von 3*3 betrachtet. Wenn davon die erste Spalte höchstens eine Zeichenposition zählt und die restlichen Spalten (einschliesslich der zentralen Zeichenposition) mindestens drei, wird die zentrale Zeichenposition markiert. Ein entsprechendes Kriterium gilt in den drei anderen Orientierungen. Eine markierte Zeichenposition hat dann mindestens zwei Nachbarn. Es stellt sich heraus, dass dies zu einem rigorosen Skelettieren führt.

Danach werden die markierten Zeichenpositionen zeilenweise von links nach rechts mit einem Unentbehrlichkeitskriterium verglichen, das hier lautet: wenn durch Fortlassung eine Unterbrechung entstehen würde (oder auch eine Schleife, was aber hier durch die Wahl des Randkriteriums nicht gilt), wird die Zeichenposition beibehalten. Dazu werden alle acht äusseren Positionen der 3x3-Matrix als Nachbar der zentralen Zeichenposition betrachtet.

In Fig. 18 ist angegeben, welche Zeichenpositionen mit einem Unentbehrlichkeit skrit erium verglichen werden: durch ein Kreuz ist angegeben, welche Positionen fortgelassen werden durften. Durch ein A ist angegeben, dass die betreffende

309831/0985

- 12 - PHN.6096.

Zeichenposition beibehalten wurde j in dem Augenblick, wo-der Vergleich mit dem Kriterium stattfand, war die Zeichenposition rechts unten noch vorhanden» es würde also durch Fortlassung eine Unterbrechung entstanden sein. Die in Fig. 18 durch ein A angegebene Zeichenposition wird in den nachfolgenden Zyklen nicht mehr bewertet, denn sie hat nur einen Nachbarn. Auf diese Weise bietet diese Position einen bleibenden Endpunkt. Auch in Fig» 19» 20, 21 wird immer die durch ein A angegebene Zeichenposition beibehalten, weil Fortlassung eine Unterbrechung grgeben würde.

Fig. 21 zeigt das Endresultatϊ die Symmetire ist völlig geändert. In Fig. 17 gibt es eine Neigung nach -rechts oben. In Fig. 21 eine stärkere nach rechts unten.

Eine bessere Skelettierung erhält man. dadurch, dass nach der Erfindung die in Fig. 18 durch ein A angegebene Zeichenposition abermals auf ihre Unentbehrlichkeit geprüft wird. Eine Fortlassung ergibt keine Unterbrechung und wenn das zweite Unentbehrlichkeitskriterium dasselbe ist wie das erste, darf die ,Zeichenposition fortgelassen werden. In den nachfolgenden Zyklen entsprechen dann die in Fig. 19-21 durch ein A angegebenen Zeichenpositionen nicht dem Unentbehrlichkeit skriterium und werden folglich fortgelassen. So entsteht das Resultat nach Fig. 22. Indem also mindestens in einem ersten Zyklus zweimal ein Unentbehrlichkeitskriterium angelegt wurde, ist eine bessere Skelettierung erreicht worden. Es kann auch sein, dass die Verbesserung dadurch entsteht, dass in einem zweiten.und weiteren Zyklus zweimal ein Unentbehrlichkeitskriterium angelegt wird»* Dadurch, dass das

309831/.0 985

- 1? - PHN.6096.

Unentbehrlichkeitskriterium zweimal angelegt wird, werden von vielen herausragenden Zeichenelementen die kein Kennzeichen des Zeichens bilden, die Endpunkte bei ihrem Entstehen entfernt. Auf diese Weise können die Zeichenelemente sich nicht entwickeln. Im Beispiel waren die beiden Unentbehrlichkeit skriterien identisch formuliert, aber dies ist nicht notwendig. Sie können sogar von Zyklus zu Zyklus voneinander abweichen. Ein zusätzlicher Vorteil der Methode mit der doppelten Anwendung der Unentbehrlichkeitskriterien ist, dass diese weniger hoch sein dürfen. Venn die Zeichenpositionen das erste Mal beibehalten werden, werden sie ja abermals geprüft. Auf dieselbe Art und Weise darf das Kriterium zum Markieren weniger hoch sein.

Fig. 23 zeigt für den Fall von acht Nachbarn ein Beispiel, aus dem der Nutzen eines Glättungszyklus hervorgeht. Diese Figur ist gegen Skelettieren immun. Eine Fortlassung einer Zeichenposition lässt immer eine Schleife bzw. eine Unterbrechung entstehen. Es ist vorausgesetzt worden, dass die vier Enden nicht markiert werden. Ein Glättungskriterium seit eine Umgebungsposition mit mehr als vier angrenzenden Zeichenpositionen wird aufgefüllt. Das Resultat ergibt Fig. 24, die eine einfache Konfiguration gibt. Das Auffüllen von Umgebungspositionen kann auf Fälle beschränkt werden, bei denen keiner der vertikalen . oder horizontalen Nachbarn eine Umgebungsposition ist. Im allgemeinen kann man dem letztgenannten Nachbarn eine grössere Bedeutung anerkennen als anderen, beispielsweise dadurch, dass in die Kriterien Wftgnncsfaktoren aufgenommen werden. Ein derartiges Glätten

309831/0985

PHN.6096.

ergibt insbesondere in Kombination mit einer doppelten Anwendung eines Unentbehrlichkeitskriteriums von markierten Zeichenpositionen ein gutes Resultat. Dies stellt sich, heraus, wenn von einer Vielzahl angebotener Zeichen, beispielsweise 10 , eine grössere Anzahl als richtig wiedererkannt wird. Das Beispiel ist für acht Nachbarn pro Position ausgearbeitet worden. Für vier oder sechs Nachbarn gelten analoge Behandlungen.

In der deutschen Patentanmeldung ist auch eine Anordnung zum Vergleichen mit einem Unentbehrlichkeitskriterium beschrieben worden. Die Fig. 7-12 dieser Anmeldung zeigen eine Schaltungsanordnung hierfür. Mit der Anordnung entsprechend der genannten Patentanmeldung lassen sich Zeichenpositionen zweimal mit einem Unentbehrlichkeitskriterium vergleichen. Dies erfolgt beispielsweise wenn in einem ersten Zyklus eine Zeichenposition einem Randkriterium entspricht und es sich herausstellt, dass sie unentbehrlich ist und wenn* sie in einem zweiten Zyklus aufs neue einem Randkriterium entspricht. Man kann die in dieser Patentanmeldung beschriebene Anordnung derart ausbauen, dass die Information aller Positionen pro Zyklus zweimal rundläuft, während der Markierungsspeicher (Fig. 11 der genannten Patentanmeldung) derart ausgebaut wird, dass er etwaige zusätzliche Information sämtlicher markierten Zeichenpositionen enthalten kann. Dadurch würde er stark vergrössert werden und zwar bis etwa ebenso gross wie der Hauptspeicher, beispielsweise bis 32 χ 32 = 2 Bits. Ausserdem würde der Durchgang eines Zyklus etwa doppelt soviel Zeit beanspruchen.

309831/09 8 5

- 15 - PHN.6096.

Pig. 25 zeigt ein Blockschaltbild zum Durchführen des Verfahrens nach der Erfindung und enthält einen Träger A mit Zeichen» einen Aufnehmer B, einen Pufferspeicher C, eine Schaltungsanordnung D₁ einen Hauptspeicher E, eine Steueranordnung F, einen Taktimpulsgenerator G, eine Verbindung H, einen Marki*erungsspeicher Σ, einen Skelet tier speicher J, eine logische Einheit K, eine zweite logische Einheit L, einen Merkspeicher M, eine bistabile Anordnung N und eine Ausgangsanordnung 0. Durch gestrichelte Linien ist angegeben, welche dieser Teile eine Hauptsteueranordnung PA, eine Markierungsanordnung MI und eine Entscheidungsanordnung BSI bilden. Die Zeichen sind mit kontrastierender Tinte auf dem Träger A gedruckt. Der Aufnehmer B ist ein Lichtpunktabtaster, der das Zeichen zeilenweise abtastet. Der Pufferspeicher C ist ein Schieberegister von beispielsweise 32 Bits, Darin wird die Information einer Zeile des Zeichens gespeichert: die einfachste Form ist die von einem Bit pro Position, die also die Information "belegt" oder "leer" gibt. Der Hauptspeicher E kann ebenfalls als Schieberegister aufgebaut sein. Der Taktimpulsgenerator G gibt zu regelmässigen Zeitpunkten Taktimpulse zur Steueranordnung F, die den weiteren Ablauf steuert. Der Pufferspeicher C wird dazu verwendet, die Eigenschaften des Aufnehmers B und des Hauptspeichers E aneinander anzupassen. Nach dem Abtasten einer Zeile des Zeichens wird die Information dieser Zeile über die Schaltungsanordnung D unter Ansteuerung der Steueranordnung P weitergeleitet. Das Zeichen besteht beispielsweise aus 32 Zeilen und zu 32 Bits. Wenn alle Informationen des Zeichens dann im Hauptspeicher E gespeichert

309831 /0985

- j6 - pun.6096.

sind, beginnt das Skelettieren. Dazu wird eine Ringschaltung gebildet aus dem Hauptspeicher E, dem Markierungsspeicher I, dem Skelettierspeicher J, der logischen Einheit L und der Ausgangsanordnung O, Die Speicher können alle als Schieberegister ausgebildet sein. Unter Ansteuerung der Taktimpulse und der Steueranordnung F läuft die Information des Zeichens bis sie wieder in den Hauptspeicher E zurückgekehrt ist. Dabei werden im Markierungsspeicher I die Zeichenpositionen gegebenenfalls entsprechend einem Randkriterium markiert, welches die Information einer Zeichenposition mit dem gegebenenfalls belegten Zustand der benachbarten Positionen vergleicht. Dies erfolgt durch die logische Einheit K, während die Information, ob die betreffende Zeichenposition markiert ist, dem Merkspeicher M zugeführt wird. Der Ausgang des Markierungsspeichers I ist über die Verbindung H mit dem Eingang des Skelettierspeichers J verbunden. Darin wird die Information der markierten Zeichenpositionen mit der der benachbarten Positionen verglichen. So wird ein Unentbehrlichkeitskriterium implementiert: die Marke der betrachteten Zeichenposition und gegebenenfalls die anderer Zeichenpositionen wird durch den Merkspeicher M der zweiten logischen Einheit L zugeführt. Diese vergleicht mit einem ersten Unentbehrlichkeitskriterium und entscheidet, ob die markierte Zeichenposition entfernt werden darf oder nicht. Wenn dies erlaubt ist, wird die Information geändert in die einer Umgebungsposition. Nach der vorliegenden Erfindung vergleicht danach diese zweite logische Einheit L mit einem zweiten Unentbehrlichkeitskriterium, aber erst nachdem der erste Vergleich soweit fortgeschritten ist,

309831/0985

-17- PIIN. 6096.

dass die Resultate dieses Vergleichs den zweiten Vergleich nicht mehr beeinflussen können. Die Information der gegebenenfalls entfernten Zeichenposition geht über die Ausgangsanordnung 0 zum Hauptspeicher E zurück und ist gegebenenfalls an einer¹ Ausgangsklemme der Ausgangsanordnung 0 verfügbar. Wenn in einem Zyklus keine Zeichenposition entfernt wird, wird die Skelettierung beendet. Dies wird durch die bistabile Anordnung N detektiert, welche die Entfernungssignale empfängt. Gegebenenfalls können dann noch ein oder mehrere Zyklen anderer Typen folgen. Die Subzyklen sind also in der Zeit nicht getrennt; wohl durchlaufen die Zeichenpositionen zunächst den ersten, dann den zweiten und zum Schluss den dritten Subzyklus·

Fig. 26 zeigt einen Skelettierapeicher und einen Merkspeicher. Das Zeichenfeld besteht beispielsweise aus 32 χ 32 Positionen, deren Information als jeweils ein Bit pro Position gespeichert wird.

Der Skelettierspeicher enthält fünf Schieberegister IJ, J2, J3» J^ und J5 zu je 30 Bits mit Anpassungswiderständen IRJ, JR2, JR3, JR4 und JR5 und Regenerationsverstärkern IJV, JV2, JV3, JVk und JV5. Weiter enthält der Skelettierspeicher zehn Plip-Flopschaltungen IJ1, IJ2, J21, J22, J31, J32, Jki, J42, J51 und J52. Die Information des letzten Bits der Schieberegister und der Flip-Flopschaltungen ist an den Signalklemmen 1 ..... 9 und 18 ..... 23 vorhanden. Die Klemme ist als Signalausgangsklemme wirksam. Die Flip-Flopschaltungen J21 und J41 haben nicht dargestellte Rückstelleingänge. Weiter enthält Fig. 26 einen Merkspeicher. Dieser ist auf

309831 /0 985

- 18 - Pin.6096.

analoge Weise mit einer Signaleingangsklemme MOO, vier Schieberegistern zu 30 Bits M2, M3, M4, M5 mit Regenerationsverstärkern

und Abschlusswiderständen MV2 .....5 und MR2 5» neun

Flip-Flopschaltungen M1 1, 12, 21,22, 31, 32, 4i , 42 und 51

und den Signalklemmen 10 17 aufgebaut. Im Skelettier-

speicher wird also die Information gespeichert, ob eine Position eine Zeichenposition ist oder nicht, im Merkspeicher ob die Position markiert ist oder nicht.

In Fig. 27 ist eine Anordnung dargestellt, durch die ein Randkriterium erzeugt wird. Es sei wieder vorausgesetzt, dass jede Position acht benachbarte Positionen hat. Man folgt dem Kranz dieser benachbarten Positionen und zählt, wie viele Male eine Umgebungsposition einer Zeichenposition unmittelbar folgt.

Die Anordnung nach Fig. 27 enthält drei Schieberegister 11 , 12 und IJ zu je 30 Bits mit Anpassungswider stand en IR1 , IR2 und IRJ und Regenerationsverstärkern IV1 , IV2 und IVJ. Weiter enthält die Anordnung die Flip-Flopschaltungen 111,112,

121, 122, IJ1, IJ2, die logischen UND-Tore DE 1 9, das

logische ODER-Tor D01 , elf Widerstände DR1 11, einen

Transistor DT und eine Spannunftsklemme U. Die Anordnung bildet einen Markierungsspeicher. Bei einer Zeile von 32 Positionen ist die Information einer 3x3-Matrix von Positionen also an den Ausgängen der Anpassungswiderstände und der sechs Flip-Flopschaltungen verfügbar. Die UND-Tore DEI.....8 empfangen die Information von einer Position des Kranzes nicht invertiert und von der nächsten Position des Kranzes um die zentrale Zeichenposition invertiert. Wenn einer Zeichenposition bei

309831/0985

- 19 - PUN.6096.

einem Umlauf an diesem Kranz entlang unmittelbar eine Umgebungsposition folgt, wird der Ausgang eines der UND-Tore

DE1 8 hoch. Die dadurch in die Widerstände DR1.....8

fliessenden Ströme werden addiert, so dass die Spannung am Widerstand DR1O der Anzahl der Merkmale, dass einer Zeichenposition eine Umgebungsposition unmittelbar folgt, proportional ist. Ist diese Anzahl mindestens gleich eins, so wird auch der Ausgang des ODER-Tores D01 hoch. Wenn diese Anzahl mindestens zwei ist, wird der Transistor DT leitend (die Klemme U erhält eine Speisespannung). Wenn der Transistor DT leitend ist, wird der damit verbundene Eingang des UND-Tores DE9 durch den Spannungsfall am Widerstand DRI1 niedrig und das UND-Tor DE9 gibt also nur ein hohes Signal ab, wenn bei einem Umlauf an einem Kranz entlang um eine Position:

a) die zentrale Position einer Zeichenposition ist;

b) nur einmal einer Zeichenposition eine Umgebungsposition folgt,

Zur Fig. 27 sei bemerkt, dass durch eine geringfügige Aenderung der Rangordnung der zentralen Zeichenposition bestimmt werden kann« Dazu sind vier logische ODER-Tore DOR1.... h notwendig. Sie empfangen die Eingangssignale der Ausgänge von: IR2 und IRJ; IJ1 und IJ2; 122 und 112 bzw. 111 und IRI.

Die Ausgänge der logischen ODER-Tore DOR1..... k sind

dann mit Eingängen von vier logischen UND-Toren DAND1 k

verbunden. An ihren anderen Eingängen empfangen sie invertiert die Signale der Ausgänge von IJ1; 1225 111 bzw. IR2. Die Anzahl dieser UND-Tore, die ein hohes Signal abgeben, entspricht der Rangordnung. Diese Anzahl kann auf dieselbe Art und Weise bestimmt werden wie in Fig. 27 die Anzahl hoher Signale an

309831/0985

-20- PIIN. 6096.

den Toren DE1 8 gezählt wird: nur wenn die Rangordnung

eins ist, werden alle drei Eingänge des Tores DE9 hoch über ODER-Tor D01 und Transistor DT. Die Basis von DT ist dann über vier Widerstände mit den Ausgängen der Tore DAND1....4 verbunden wie dies mit dem Eingang des ODER-Tores D01 unmittelbar der Pail ist. Die Tore DE1 8 können fortfallen, ebenso

wie die Widerstände DR1.....8.

Der Ausgang des UND-Tores DE9 ist mit der Eingangsklemme MOO aus Fig. 26 verbunden. In Fig. 12 der deutschen Patentanmeldung P 21 $k 411.6 wird die Bildung eines Unentbehrlichkeitskriteriums gegeben: durch die NICHT-UND-Tore Y4-Y15 wird das Fortlassen einer markierten Zeichenposition vermieden wenn dadurch eine Unterbrechung entstehen würde. Das kann auch bei dem vorliegenden Beispiel auf dieselbe Art und Weise erfolgen. Wenn der Ausgang des logischen NICHT-UND-Tors Y15 hoch wird, darf die Zeichenposition nicht in eine Umgebungsposition geändert werden. Dann kommen in Fig. 26 die Klemmen 7, 8, 9, 18, 19, 20, 21, 22, 23 an die Stelle der Klemmen 1...9, in bezug auf die Eingangssignalklemmen der NICHT-UND-Tore Y4.....15 in Fig. 12 der deutschen Patentanmeldung. Die übrigen Elemente dieser Figur, namentlich die NICHT-UND-Tore Yi6o....18, der Transistor T5 und die damit verbundenen Teile werden hier nicht näher betrachtet.

Eine andere Möglichkeit ist, dass beim zweiten Vergleich Zeichenpositionen, die aus dem Zeichen herausragen, entfernt werden. Eine Anordnung dazu ist in Fig. 28 dargestellt. Markierte Zeiphenpositionen werden entfernt, wenn sie nur einen Nachbarn haben oder zwei aneinander grenzende Nachbarn (nach der

309831/0985

PHN.6096.

Entfernung beim ersten Vergleich der nicht unentbehrlichen Zeichenpositionen).

Die Anordnung nach Fig. 28 enthält ausser einer Anzahl bereits in Fig. 26 dargestellter Elemente die logischen

UND-Tore DE10 19, die logischen ODER-Tore D02 und D03,

die Transistoren DT2 und DT3, die Widerstände DR12 und eine Spannungsklemme U. Sind zwei benachbarte Positionen eines Ringes um die zentrale Position Zeichenpositionen,

so gibt das zugehörige UND-Tor der Reihe DE10 17 ein

hohes Signal ab. Ist dabei mehr als eine der zentralen Positionen benachbarten Positionen eine Zeichenposition, so wird der Transistor DT2 leitend, wodurch der zugehörende Eingang des ODER-Tores D03 niedrig wird. Wenn es aber nur eine benachbarte Zeichenposition gibt und die zentrale Position ist eine gemerkte (Klemme 17 aus Fig, 27) Zeichenposition (Ausgang der Flip-Flopschaltung J41), gibt das UND-Tor DE19 ein hohes Signal ab.

Wenn nun mehr als zwei der der zentralen Position benachbarten Positionen Zeichenpositionen sind, so wird auch der Transistor DT3 leitend, wodurch der zugehörende Eingang des UND-Tores DE18 niedrig wird. Wenn also zwei Zeichenpositionen der zentralen Zeichenposition benachbart sind, diese zwei Nachbarn unterschieden sind und die zentrale Position eine gemerkte Zeichenposition ist, wird der Ausgang des UND-Tores DEI9 hoch.

In allen anderen als in den zwei genannten Fällen ist der Ausgang des UND-Tores DEI9 niedrig und die (etwaige) zentrale Zeichenposition entspricht dem Unentbehrlichkeitskriteriun

309831/0985

. ΡΗ.\^Τ.6Ο96.

Unter Ansteuerung des hohen Signals von DE sind die zentralen Zeichenpositionen in eine Umgebungsposition umgewandelt, beispielsweise durch einen Impuls zum Rückstelleingang der Flip-Flopschaltung J'H . Die Widerstände DR24, 25, 26 und 27 dienen zum Einstellen der Transistoren DT2 und DTR3

Eine derartige Anordnung lässt sich auch bei einem Glättungszyklus verwenden. Dann wird beispielsweise die Klemme 17 bei einem hohen Signal gesperrt.

Die Erfindung kann eine Reihe von Kriterien anwenden. Für acht benachbarte Positionen werden eine Anzahl Beispiele gegeben:

a) Glättungskriterium zum Auffüllen;

- eine Umgebungsposition grenzt an mindestens fünf Zeichenpositionen;

- dasselbe, insofern sie danach die Rangordnung 1 hat; eine Umgebungsposition würde nach Auffüllen, die Rangordnung 2 haben.

Glättungskriterium zum Entfernen;

- eine Zeichenposition hat die Rangordnung 1 und höchstens drei benachbarte Zeichenpositionen; dasselbe mit der zusätzlichen Bedingung, dass diese höchstens drei Zeichenpositionen in derselben Reihe bzw. Spalte liegen.

b) Randkrit erium t

- in der 3x3-Matrix enthält eine Reihe/Spalte höchstens eine Zeichenposition und der Rest mindestens drei (oder vier);

- die "Rangordnung" der Zeichenposition . ist 1; -

- die Zeichenposition grenzt in horizontaler oder vertikaler Richtung an eine Umgebungsposition;

309831 / 098 S

- at. - pun.6096.

-dasselbe und dabei hat diese Zeicherposition mindestens

drei benachbarte Zeichenpositionen, c) Unentbehrlichkeitskriterium;

- eine Fortlassung darf keine Unterbrechung verursachen;

- die gemerkte Zeichenposition darf keinen Teil eines Blocks von vier gemerkten Zeichenpositionen bilden, während der Rest der Matrix von 3x3 fünf Umgebungspositionen enthält!

- die Rangordnung entspricht nicht eins;

- die Zeichenposition hat nur einen Nachbarn (Endpunkt): unentbehrlich.

Für andere Muster kann man entsprechende Kriterien aufstellen. Die gegebene Liste ist sogar für acht Nachbarn nicht erschöpfend, Man kann mehrere Kombinationen der Kriterien bilden: so können das Randkriterium, das erste und zweite Unentbehrlichkeitskriterium aneinander angepasst werden. Man kann die Behandlung auch parallel verlaufen lassen: man kann das Zeichenfeld beispielsweise in zwei Teile aufteilen und zwei Anordnungen nach der Erfindung verwenden. Die Wahl der Kriterien kann beispielsweise von der Art der Zeichen abhängen« Auch können in verschiedenen Zyklen verschiedene Rand- und/oder Unentbehrlichkeitskriterien verwendet werden.

309831/0985

Claims

- 24 - pun.6096.

PATENTANSPRÜCHE:

1, Verfahren zum Skelettieren von Zeichen, die auf einem zweidimensionalen regelmässigen Muster von Positionen präsentiert werden, wobei eine Zeichenposition durch vorhandene digitale Information von einer Umgebungsposition unterschieden wird und die Zeichen von überflüssigen Informationen dadurch befreit werd en, dass die Information einer Zeichenposition in die einer ümgebungsposition so geändert wird, bis ein SkeIettzeionen erhalten wird, dessen Zeichenelemente aus einfachen Reihen entsprechend einem Nachbarschaftskriterium aufeinanderfolgender Zeichenpositionen bestehen und die Skelettierung in Zyklen erfolgt, wobei während eines Zyklusses die Positionen des Zeichenfeldes in regelmässiger und fester fieihenfolge behandelt werden, wobei während eines Zyklus Jene Zeichenpositionen, die sich nach einem üandkriterium an einem Rand des Zeichens befinden, in. einem ersten Snfozykius dadurch, markiert werden, dass der InföTmatitm dieser Zeichenpositionen eine zusätzliche Information zugefügt wird, dadurch gekennzeichnet, dass die auf diese Weise markierten Zeichenpositionen während dieses Zyklusses nacheinander zunächst in einem zweiten Subzyklus mit einem ersten Unentbehrlichkeitskriterium verglichen werden, auf Grund dessen sie fortgelassen, bzw» beibehalten, werden land danach die auf diese leise noch beibehaltenen markierten Zeichenpositionen in einem dritten Subzyklus mit einem zweiten Unentbehrliehkeitslcrlteriuin verglichen werden, auf Grund dessen sie fortgelassen bzw* beibehalten weräes, wobei die im zweiten Subzyklus fortgelassenen Zeichenpositionen im dritten Subzyklus als Umgebangspositionen auftreten«

308831/0985

PiiN, 6096.
2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass auf Grund des ersten Unentbehrlichkeitskriteriums nur diejenigen markierten Zeichenpositionen beibehalten werden, deren Fortlassung eine Unterbrechung oder eine Schleife im Zeichen entstehen lassen würde und auf Grund des zweiten Unentbehrlichkeitskriteriums nur diejenigen Zeichenpositionen fortgelassen werden, die auf die Art und Weise eines Endpunktes (Schweifpunkt) aus dem Zeichen herausragen.
3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass den Zyklen ein Glättungszyklus vorhergeht, in dem Zeichenpositionen, die entsprechend einem Glättungskriterium aus dem Zeichen herausragen, fortgelassen und Umgebungspositionen, die in das Zeichen einbäulen, zu Zeichenpositionen gemacht werden und dass bei den nachfolgenden Zyklen Zeichenpositionen, die nach einem Herausraguiigskriterium aus dem Zeichen herausragen, von Markierung ausgeschlossen werden,
4. Anordnung zum Gebracuh beim Skelettieren von Zeichen nach dem Verfahren nach Anspruch 1, weiche Zeichen auf einem Träger präsentiert sind, welche Anordnung einen Abtaster enthält, der die Information der Zeichen auf einer vorhandenen Speicheranordnung abbildet, wodurch die genannten Zeichen als digitale Information von Zeichenpositionen bzw. Umgebungspositionen gespeichert werden, welche Positionen auf dem Träger entsprechend einem zweidimensionalen regelmässigen Muster von Positionen gegliedert sind, welche Anordnung weiter eine Skelettieranordnung enthält, der mindestens die Information der Zeichenpositionen zuführbar ist und wodurch die Information von Zeichenpositionen in die von Umgebungspositionen änderbar

309831/0985

- 26 - PTM.6096.

ist, bis die in der genannten Speicheranordnung gespeicherte Information von Zeichenpositionen auf die Information von Zeichenpositionen von Skelettzeichen verringert ist, deren Zeichenelemente aus einfachen Reihen einander entsprechend einem Benachbarkeitskriterium auffolgender Zeichenpositionen bestehen, wobei das Skelettieren durch eine Steueranordnung in Zyklen gesteuert wird, wobei während eines Zyklus Information der Positionen des Zeichenfeldes in einer regelmässigen und festen Reihenfolge der Skelettieranordnung zuführbar i-st und wobei während eines Zyklus in einem ersten Subzyklus mindestens die Information der Zeichenpositionen zusammen mit der Information der diesen Zeichenpositionen benachbarten Positionen einer ersten Entscheidungsanordnung zuführbar sind, in der ein Randkriterium eingebaut ist, welche erste Entscheidungsanordnung der Information jener Zeichenpositionen, für die das genannte Randkriterium erfüllt ist, zusätzliche Information zufügt, dadurch gekennzeichnet, dass danach in einen zweiten Subzyklus die Information der Zeichenpositionen zuäammen mit der genannten zusätzlichen Information einer zweiten Entscheidungsanordnung zuführbar ist, in der ein erstes Unentbehrlichkeitskriterium eingebaut ist und wodurch, wenn zwar das Randkriterium, aber nicht das erste Unentbehrlichkeit skriterium erfüllt ist, die Information der betreffenden Zeichenposition in die der Umgebungsposition änderbar ist, und dass danach in einem dritten Subzyklus die Information der restlichen Zeichenpositionen zusammen mit der genannten zusätzlichen Information einer dritten Entscheidungsanordnung zuführbar ist, in der ein zweites Unentbehrlichkeitskriterium

309831 /0985

- 27 - PHN.6096.

eingebaut ist und wodurch, wenn zwar das Randkriterium erfüllt war, nicht aber das zweite Unentbehrlichkeitskriterium erfüllt ist, die Information der betreffenden Zeichenposition in die einer Umgebungsposition änderbar ist, wonach diese gegebenenfalls geänderte Information an einem Ausgang erscheint.

30 9831/0985

Le e rs e i te