DE2909153A1

DE2909153A1 - Einrichtung zur elektronischen verarbeitung von bild- und/oder zeichenmustern

Info

Publication number: DE2909153A1
Application number: DE19792909153
Authority: DE
Inventors: Stanley R Sternberg
Original assignee: ENVIRONMENTAL RES INST; Environmental Research Institute of Michigan
Current assignee: ENVIRONMENTAL RES INST; Environmental Research Institute of Michigan
Priority date: 1976-11-15
Filing date: 1979-03-08
Publication date: 1980-09-11
Also published as: BE875163A; FR2451602A1; CA1116301A; DE2909153C2; SE445684B; US4167728A; GB2046487A; SE7902921L; CH637231A5; GB2046487B; FR2451602B1; NL7902709A

Description

PATENTANWÄLTE

SCHAUMBURG, SCHULZ-DÖRIAM & THOENES

ZUGELASSENE VERTRETER VOR DEM EUROPÄISCHEN PATENTAMT

KARL-HEINZ SOHAUMBURa, D1PL.-1NQ. WOUFQANa SCHULZ-OÖRLAM, INS. OiPL. DR. DIETER THOENES, OIPL.-PHYS.

7005 SBrt

Environmental Research Institute of Michigan
P.O. Box 8618
Ann Arbor, Michigan 48107 / USA

Einrichtung zur elektronischen Verarbeitung von Bild- und/oder

Zeichenmustern

0 30037/0421

MAUERK1RCHERSTRASSE 31 ■ D-SOOO MÜNCHEN 80 . TELEFON (O89) 981979 und Θ87Β31 TELEX 522Ο1Θ ESPAT D

Die Erfindung betrifft eine Einrichtung nach dem Oberbegriff des Patentanspruchs 1. Es handelt sich dabei um die Erkennung und Analyse von Bild- und/oder Zeichenmustern sowie insbesondere um eine automatische Bildverarbeitung unter Anwendung der Integralgeometrie und anderer mathematischer Verfahren, mit Hilfe derer Muster eines Silhouettenbildes klassiert werden können.

Es gibt eine Vielzahl von Anwendungsfällen für eine Maschine zur automatischen Erkennung, Analyse und/oder Klassierung von Mustern in Silhouettenbildern (durchgehend schwarze Formen auf weißem Hintergrund). Einige der einfacheren Probleme, die mit zumindest begrenztem Erfolg durch solche Maschinen gelöst wurden, sind die Erkennung alphanumerischer Schriftzeichen und die Erkennung oder Zählung von Teilchen wie beispielsweise Blutkörperchen. Schwierigere Anwendungen dieser Art, die die Möglichkeiten der gegenwärtigen Verfahren überschreiten, können beispielsweise in der automatischen Erkennung militärischer Ziele mit Infrarot-Bildsensoren oder in der Umsetzung von Handschrift in eine maschinenlesbare Codierung bestehen.

Es wurden bereits komplizierte Programme für Datenverarbeitungsmaschinen erstellt, mit denen die Musteranalyse und Klassierung durchgeführt werden können. Der begrenzte Erfolg, den man mit normalen Datenverarbeitungsmaschinen dabei hatte, liegt an extrem langen Verarbeitungszeiten für Bilder, die sehr viele Datenpunkte enthalten. Eine gewisse Verbesserung kann sich durch Anwendung eines Spezialgeräts ergeb en, das nach einem mathematischen Verfahren arbeitet, welches auf Daten in Form von Bildern angewendet werden kann. Die Integralgeometrie ist ein solches Verfahren. Hierbei werden Eingabedaten in Form einer M χ N-Anordnung der Werte 0 und 1 verwendet, die schwarze bzw. weiße Bildelemente darstellen. Aus dieser Eingabeanordnung wird eine weitere MxN-Anordnung abgeleitet,

030037/0421

wobei jeder Punkt dieser zweiten Anordnung eine Funktion des Zustandes des ihm äquivalenten Punktes in der ersten Anordnung sowie verschiedener seiner Nachbarpunkte ist. Eine Reihe dieser Umsetzungen kann durchgeführt werden, um einige der Eigenschaften von Mustern zu bestimmen, die in der ersten Anordnung dargestellt werden. In der US-PS 3 241 547 ist beispielsweise ein hierzu geeignetes Bildverarbeitungsgerät beschrieben, das zur Zählung von Lymphocyten des Blutes dient. Einrichtungen, die nach Verfahren arbeiten, welche gleichfalls derartige ¹¹ Nachbar schaf ttransformationen" anwenden, sind in dem. Auf satz "Pattern Detection and Recognition" von Unger in Proceedings of the IRE, 1959, Seite 737, sowie in den Aufsätzen "Feature Extraction" von Goley und "Hexagonal Pattern Transformers" von Preston, Jr. in IEEE Transactions on Computers, Vol. C-20, Nr. 9, September 1971, beschrieben.

Eine weitere Klasse von Spezialgeräten, die mit einer Inte— gralgeometrie-Analyse unter Anwendung sogenannter "Ja-Nein-Transformationen" arbeitet, ist in "The Texture Analyzer" in Journal of Microscopy, Vol. 95, Teil II, April 1972, auf den Seiten 349-356 beschrieben.

Diese bisher bekannten Bildverarbeitungsgeräte verwenden insgesamt Bilder, deren Datenpunkte auf binäre Form reduziert sind, also mit den Werten O oder 1 darstellbar sind. Dies entspricht den üblichen Anforderungen der Integralgeometrie. Anwendungen der Integralgeometrie für die Mustererkennung sind an folgenden Stellen veröffentlicht:

1. G. Matheron, "Random Sets and Integral Geometry" Wiley, 1975.

2. Albert B.J. Novikoff, "Integral Geometry as a Tool

in Pattern Perception", in Principles of Self-Organization,

030037/04 21

herausgegeben von Von Foerstn und Zopf, Pergamon Press, 1962.

3. J. Serra, "Stereology and Structuring Elements", Journal of Microscopy, Vol. 95, Teil 1, Februar 1972, Seiten 93-103.

Die Aufgabe der Erfindung besteht nun darin, eine Einrichtung anzugeben, bei der zur Bild- und/oder Zeichenverarbeitung das Konzept der Integralgeometrie erweitert ist und bei den Umsetzungen Matrizen verwendet werden, in denen jeder Bildpunkt einer größeren Anzahl von Zuständen zugeordnet werden kann als dies für einen Bildpunkt des Originalbildes angenommen werden kann.

Eine Einrichtung eingangs genannter Art ist zur Lösung dieser Aufgabe gemäß den Merkmalen des Patentanspruchs 1 ausgebildet. Vorteilhafte Weiterbildungen sind Gegenstand der Unteransprüche .

Wird mit einer Einrichtung nach der Erfindung beispielsweise ein digitalisiertes Originalbild in Form einer Silhouette verarbeitet, dessen Bildpunkte als Binärwerte angegeben sind, so können die aus den Transformationen dieses Bildes resultierenden Matrizen drei oder mehr mögliche Bildpunktzustände oder Werte haben. Die Ausdehnung der Integralgeometrie auf derartige Mehrfachzustände und die im folgenden zu beschreibenden Schaltungen zur Anwendung der mathematischen Verfahren sind wesentlich einfacher und/oder leistungsfähiger als die bisher bekannten Verfahren und Maschinen. Hieraus ergibt sich ein wesentlicher Fortschritt bei der Erkennung, Analyse und Klassierung von Silhouettenmustern.

0 3 0037/042 1

Wie sich aus der folgenden Beschreibung eines vorzugsweisen Äusführungsbeispiels der Erfindung ergibt, hat das Bildverarbeitungsgerät die Form einer Kette identischer Verarbeitungsstufen, wobei jede Stufe teilweise aus mehrstufigen Schieberegistern und Speichern mit direktem Zugriff besteht, welche in beliebiger Technik wie beispielsweise als Kernspeicher, Halbleiterspeicher oder Magnetbläschenspeicher aufgebaut sein können. Bei dem vorzugsweisen Ausführungsbeispiel wird jeder Bildpunkt mit zwei Binärwerten ausgedrückt, so daß er einen von vier möglichen Zuständen annehmen kann. Bei anderen Ausführungsbeispielen können auch noch mehr Bildpunktzustände vorgesehen sein. Die Funktion des Schieberegisters in jeder Verarbeitungsstufe besteht darin, nacheinander Zugriff zu allen möglichen Nachbarpunkten des in die Stufe eingegebenen Bildes zu erhalten. Zu diesem Zweck wird vorausgesetzt, daß die Bildpunkte der Stufe sequentiell zugeführt werden, was sich aus einer zeilenweisen Abtastung ergibt. Das Schieberegister enthält an geeigneten Stellen Ausgangskanäle, so daß der Wert eines jeden Bildpunktes sowie seiner unmittelbaren Nachbarpunkte gleichzeitig geprüft werden kann. Diese gleichzeitig verfügbaren Werte bilden das Argument einer logischen Funktion, die in Form eines Speichers mit direktem Zugriff, einer programmierbaren logischen Anordnung oder eines Netzwerks aus logischen Elementen vorliegt.

Während die in der Matrix repräsentierten Werte der Bildpunkte durch das Register geschoben werden,werden jeder Datenpunkt sowie seine Nachbarpunkte sequentiell geprüft, und die Logik erzeugt einen transformierten Datenpunkt, der eine Funktion des Wertes des äquivalenten Datenpunkts im eingegebenen Bild und der Werte der Nachbarpunkte im eingegebenen Bild ist. Die logische Funktion entsprechend diesen Nachbarwerten erzeugt das Ausgangssignal einer einzelnen Verarbeitungsstufe. Diese Werte werden dann der nächstfolgenden Verarbeitungsstufe

030037/0421

in der Kette zugeführt, in der eine weitere Transformation erfolgt.

Die Art der in jeder Verarbeitungsstufe durchgeführten Transformation kann mit einer zentralen Programmiereinheit geändert werden, die mit jeder Verarbeitungsstufe in Verbindung steht.

Das Konzept der Durchführung mehrstufiger Integralgeometrietransformationen in einer Reihenanordnung identischer Verarbeitungsstufen vermeidet eine Vielzahl peripherer Bildspeichervorrichtungen und arithmetischer sowie logischer Elemente, die normalerweise den Spezialgeräten zur Bildverarbeitung zugeordnet sind. Ferner tritt das Ausgangssignal einer jeden Verarbeitungsstufe mit derselben Geschwindigkeit wie das Eingangssignal auf. Die Betriebsgeschwindigkeit ist nur durch das Schieberegister und die Technologie der verwendeten Logikschaltungen begrenzt. Daher werden die mit Zeilenabtastung gelieferten Daten zeitgetreu verarbeitet, und das analysierte Bild ist laufend am Ausgang der letzten Verarbeitungsstufe mit nur einer fest vorgegebenen Verzögerung verfügbar, die proportional der Anzahl der Verarbeitungsstufen, in der Kette ist.

Das bei der Erfindung angewendete Datenverarbeitungsverfahren verwendet die Darstellung von Nachbarschaftstransformationen in einer zweidimensionalen Matrix aus Bildpunkten mit N möglichen Zuständen zur Schaffung transformierter Matrizen, in denen jeder Bilddatenpunkt mit N-M möglichen Zuständen ausgedrückt wird. Hat beispielsweise jeder Bilddatenpunkt zwei mögliche Werte im Eingangssignal, so kann die erste Verarbeitungsstufe eine transformierte Matrix erzeugen, in

030037/0 421

der jeder Bilddatenpunkt einen von drei Werten annehmen kann. Nachfolgende Transformationen mit weiteren Verarbeitungsstufen der Kette können die Zahl von Zuständen, die einem Bilddatenpunkt zuzuordnen sind, erhöhen oder verringern. Die meisten Transformationen erhöhen oder verringern die Zahl zulässiger Zustände für einen Bilddatenpunkt um den Wert 1, jedoch ist das Verfahren so allgemein anwendbar, daß auch Transformationen in Betracht kommen können, die die Zahl zulässiger Zustände um einen höheren Wert ändern.

Als einfaches Beispiel eines mit der Erfindung anwendbaren analytischen Verfahrens sei die zweidimensiönale Anordnung der Werte 1 und O betrachtet, die in Fig. 1 dargestellt ist. Die Werte 1 bilden eine Anzahl offener und sich gegenseitig nicht schneidender Kurven unterschiedlicher Länge. Bei der Auswahl der Kurven mit einer Länge größer als L ergibt eine gerade Zahl der Einheiten des minimalen Abstandes zwischen zwei Punkten der Anordnung deren Auflösungsgrenze. Die erste Verarbeitungsstufe einer Kette von Stufen führt eine Nachbarschaftstransformation der in sie eingegebenen Anordnung durch, bei der alle Werte 1 mit einem einzigen unmittelbaren Nachbarwert 1 in Werte 2 umgesetzt werden, während alle anderen Bildpunkte ihre Anfangszustände beibehalten {Fig. 2}. Diese Transformation markiert die Endpunkte einer jeden Kurve. Dann werden mehrere identische Transformationen nacheinander durchgeführt, bei denen jeder Bildpunkt des Wertes 1 mit einem unmittelbaren Nachbarwert 2 zum Wert 2 umgesetzt wird. Diese Transformation wird L/2-1mal in L/2-1 Verarbeitungsstufen nach der Anfangsstufe der Kette durchgeführt. Dann bestehen alle Kurven mit einer Länge kleiner oder gleich L nur aus Werten 2, und '.die längeren Kurven haben einen mittleren Teil mit Werten 1 {Fig. 3). Danach werden L/2 Transformationen

030037/0421

in den nächstfolgenden L/2 Verarbeitungsstufen durchgeführt, wobei jeder Punkt mit dem Wert 2 und einem unmittelbaren Nachbarwert 1 zum Wert 1 umgesetzt wird. Nach dieser Reihe von Transformationen werden die Kurven mit einer Länge größer als L durch Werte 1 und die Kurven mit einer Länge kleiner oder gleich L durch Werte 2 angegeben (Fig. 4). Somit sind die Kurven in zwei Gruppen entsprechend ihren Längen klassiert und durch zwei unterschiedliche Bilddatenpunktwerte gekennzeichnet. Die Analyse erfolgte in einer Kette von L-Verarbeitungsstufen.

Bei der Betrachtung dieser Transformationsreihe ist zu berücksichtigen, daß das transformierte Bild einer jeden Stufe innerhalb der Reihe einen ausreichenden Informationgehalt hat, um das Originalbild wieder herzustellen. Deshalb ist keine Speicherung des Originalbildes oder eines Zwischenbildes wie bei den bisherigen Analysiersystemen erforderlich. Auch müssen keine Bilder addiert oder voneinander subtrahiert werden, wie es bei den bisher bekannten Verfahren nötig ist, da mit den bei der Erfindung angewendeten Transformationen dieselben äquivalenten Ergebnisse erzielt werden.

Zur Durchführung der vorstehenden Analyse mit einer Einrichtung nach der Erfindung ist es lediglich erforderlich, eine Kette von Verarbeitungsstufen mit einer Länge gleich der Anzahl von Nachbarschaftstransformationen in dem Algorithmus zur Längendiskriminierung zu programmieren. Die Einzelstufen der Kette können mit einem zentralen Steuergerät so programmiert werden, daß sich eine bestimmte Nachbarschaftstransformation ergibt, wobei die Steuerdaten von einer Tastatur oder einer anderen Informationsquelle geliefert werden. Alternativ kann auch eine höhergradige Programmiersprache zur Programmierung der Einzelstufen verwendet werden. Beispielsweise kann bei

030037/0421

Anwendung der vorstehend beschriebenen Transformationsreihe die Zahl L in das zentrale Steuergerät mit einer Tastatur eingegeben werden. Dieses Gerät programmiert dann die jeweilige Stufe in der Kette an geeigneten Punkten, so daß die Bedienungsperson die erforderliche Umsetzung nicht L+1mal kennzeichnen muß.

Jede Einzelstufe führt mit den in sie eingegebenen Daten im wesentlichen dieselbe Transformation durch. Zunächst wird die zentrale Zelle eines Nachbarschaftsbereichs von 9 Zellen geprüft, um zu bestimmen, ob sie den Wert KI hat. Danach wird eine Untergruppe N der 8 Nachbarzellen geprüft um zu bestimmen, ob mindestens eine Zelle mit dem Wert K2 vorliegt. Werden diese beiden Bedingungen erfüllt, so wird der Wert der mittleren Zelle zu K3 geändert. Die Programmierung eines derartigen Moduls besteht in der Eingabe der Werte N, K1, K2 und K3 in die entsprechenden Register des Moduls.

Ein vorzugsweises Äusführungsbeispiel einer Einrichtung nach der Erfindung sowie typische mit ihr durchführbare Verfahren werden im folgenden anhand der Figuren beschrieben. Es zeigen:

Fig. 1 bis 4 schematische Darstellungen einer Transformationsfolge in einer Einrichtung nach der Erfindung,

Fig. 5 das Blockdiagramm eines Geräts zur Durchführung der Umsetzungen als vorzugsweises Ausführungsbeispiel der Erfindung,

Fig. 6 das Blockdiagramm eines Teils eines typischen Moduls innerhalb eines Systems nach Fig. 5,

030037/0421

Pig. 7 das Blockdiagramm eines Adressendecodierers

und einer Registeranordnung in einem der Module nach Fig. 5,

Fig. 8 das Blockdiagramm der in einem Modul nach Fig. verwendeten Schaltung zur Bestimmung der Identität zwischen Nachbarzellwerten und dem Inhalt des K2-Registers,

Fig. 9 das Blockdiagramm der Schaltung eines Moduls nach Fig. 5 zur Bestimmung der Identität zwischen einer zentralen Zelle und dem Inhalt des K1-Registers,

Fig. 10 das Blockdiagramm einer Schaltung in jedem der Module nach Fig. 5 zur Bestimmung einer positionsabhängigen Nachbarschaftsuntergruppe,

Fig. 11 eine Darstellung typischer ünterfeider, die die Gruppe von Positionen in der Eingabeanordnung angeben, welche mit den Modulen nach Fig. 5 mit identischen Nachbarschaftskonfigurationen verarbeitet werden, und

Fig. 12 das Blockdiagramm einer anderen möglichen Ausführung der Schaltung zum Vergleich der Werte einer jeden Nachbarzelle mit dem Inhalt des K2-Registers.

Die nach der Erfindung durchzuführenden Verfahren können mit in geeigneter Weise programmierten Datenverarbeitungsgeräten durchgeführt werden, sind jedoch so aufgebaut, daß sich eine

030037/0421

Klasse relativ einfacher, jedoch extrem leistungsfähiger Spezialgeräte ergibt. Wie aus Fig. 5 hervorgeht, besteht das vorzugsweise Ausführungsbeispiel einer Einrichtung nach der Erfindung aus mehreren Modulen 10, die praktisch identisch ausgeführt und in Reihe geschaltet sind, so daß das Ausgangssignal jeweils eines Moduls das Eingangssignal für den nächstfolgenden Modul in der Kette ist. Die Zahl verfügbarer Module begrenzt die Zahl der Transformationen, die die Einrichtung mit eingegebenen Daten in einem einzigen Arbeitsgang durchführen kann. Da jeder Modul relativ einfach und billig aufgebaut ist, können Einrichtungen mit mehreren hundert oder tausend Modulen realisiert werden, wobei ein Kostenvorteil gegenüber einem normalen Datenverarbeitungsgerät erhalten bleibt.

Die Eingabematrix für den ersten Modul 10 der Kette wird von einer Datenquelle 12 geliefert, die mit einem Speicher, beispielsweise einem Magnetbandspeicher, verbunden sein oder auch ein Digitalisierungsgerät sein kann, das mit einem Datenstrom von einer zeitgerecht arbeitenden Einrichtung, beispielsweise von einem Radarempfänger 16, gespeist wird.

Das Ausgangssignal des letzten Moduls 10 der Kette wird einer Anzeige- oder Aufzeichnungsvorrichtung 18 zugeführt, die eine Kathodenstrahlröhre oder ein Magnetbandgerät o.a. sein kann, wobei das letztere zu einem späteren Zeitpunkt eine Anzeigevorrichtung steuern kann.

Die in jedem Modul 10 durchgeführte Transformation wird durch eine Transformationssteuerung 20 bestimmt. Die Arbeitsweise dieser Steuerung kann durch eine Tastatur 22 oder eine andere geeignete Programmiervorrichtung, beispielsweise mit Lochkarten,

030037/0421

Bandspeicher usw., bestimmt werden. Die Steuerung 20 ist mit jedem Modul 10 über eine Adressensammelleitung 24 und eine Transformationssammelleitung 26 verbunden. Zur Modifikation der mit einem einzelnen Modul 10 durchgeführten Transformation erzeugt die Steuerung 20 zunächst die Adresse dieses Moduls 10 auf der Adressensammelleitung 24 und danach einen geeigneten Transformationscode auf der Transformationssammelleitung 26. Jeder Modul 10 enthält eine ihm zugeordnete gespeicherte Adresse zum Vergleich mit einer Adresse auf der Adressensammelleitung 24. Ist der Vergleich erfolgreich, so wird der auf der TransformationsSammelleitung 26 folgende Transformationscode in dem Modul 10 gespeichert und steuert dessen Arbeitsweise.

Alle Schaltungen innerhalb dieser Einrichtung arbeiten synchron unter Steuerung mit ZeitSignalen, die ein Taktgenerator 28 liefert.

Die wichtigsten logischen Einheiten eines Moduls 10 sind in den Fig. 6 bis 10 dargestellt. Fig. 6 zeigt die Schieberegisteranordnung zur sequentiellen Aussonderung der 9 Nachbarschaftszellen aus dem eingegebenen Datenstrom. In dieser Darstellung kann jede Zelle jeden von vier möglichen Zuständen annehmen, so daß zwei Bits pro Zelle für alle Schieberegisterstufen erforderlich sind. Wenn die eingebene Datenmatrix eine Breite von W Elementen hat, so muß das Schieberegister eine Länge von W-3 Stufen haben.

Jeder Modul 10 hat eine Adresse, die durch seine Position in der Kette festgelegt ist. Zur Programmierung eines Moduls 10 überträgt die Steuerung 20 gleichzeitig die Adresse dieses Moduls 10 auf der Adressensammelleitung 24 und die Werte N,

030037/0421

K1, Κ2 und Κ3 auf der Datensammelleitung. Der Wert N ist eine achtstellige Binärzahl, bei der eine T an der i-ten Bitstelle anzeigt, daß die Grenznachbarschaftszelle i in die Nachbarschaftsuntergruppe N der zentralen Zelle einzuschließen ist (die Numerierung für die Grenznachbarschaftszellen ergibt sich aus Fig. 6). Fig. 7 zeigt die Anordnung des Adressendecodierers sowie der Register.

Für jeden ausgesonderten Nachbarschaftspunkt wird der mit zwei Bits angegebene Wert eines jeden Nachbars mit dem Inhalt des K2-Registers innerhalb einer Gruppe von acht Vergleichern (Fig. 8) verglichen. Das Ausgangssignal eines Vergleichers hat den Wert 1 dann und nur dann, wenn der Inhalt der Nachbarzellen dem Inhalt des K2-Registers entspricht. Das Ausgangssignal eines jeden Vergleichers wird dann durch das entsprechende Bit im Nachbarschafts-Untergruppenregister oder N-Register weitergeleitet. Das Ausgangssignal eines jeden hierzu vorgesehenen logischen Schaltgliedes ist 1 dann und nur dann, wenn die entsprechende Nachbarschaftsposition in der Nachbarschaftsuntergruppe N eingeschlossen ist und der Inhalt der Nachbarschaftszelle den Wert K2 hat. Ein ODER-Glied prüft das Ausgangssignal eines jeden UND-Gliedes und liefert ein Äusgangssignal mit dem Wert 1 dann und nur dann, wenn mindestens eine Nachbarschaftszelle in der Untergruppe N den Wert K2 hat.

Der Inhalt der Zentralzellen wird mit dem Inhalt des K1-Registers in dem in Fig. 9· gezeigten Vergleicher verglichen. Das Ausgangssignal des Vergleichers hat dann und nur dann den Wert 1, wenn die Zentralzelle den Wert K1 hat. Tritt dieser Zustand in Verbindung mit dem zuvor abgeleiteten Zustand der Nachbarzellen ein, so wird das Äusgangssignal des Multiplexers auf

0 30 03 7/0421

den Wert K3 gebracht. Im anderen Fall ist das Ausgangssignal des Multiplexers gleich dem Inhalt der Zentralzelle. Das Ausgangssignal des Multiplexers bildet den Ausgangsdatenstrom eines Moduls.

Es ist ggf.. nicht immer erwünscht, jede Zelle einer Anordnung in genau derselben Weise unabhängig von ihrer Position in der Anordnung zu verarbeiten. Allgemein kann die Untergruppe N von Nachbarn einer zentralen Zelle mit der Position i, j in der Anordnung eine Funktion dieser Position sein. Die Art der Bestimmung der positionsabhängigen Nachbarschaftsuntergruppe N. . ist in Fig. 10 gezeigt. Die Gruppe aller Zellpositionen in der Eingabeanordnung, die mit identischen Nachbarschaftskonfigurationen verarbeitet werden, bildet ein Unterfeld. Eine Anordnung kann in M Unterfelder geteilt werden, wobei M den Wert 2, 3, 4 oder höher haben kann. Zwei günstige Unterfelder sind in Fig. 11 gezeigt.

Zur Unterfeldverarbeitung ist es vorteilhaft, das N-Register durch ein größeres Speicherelement zu ersetzen, das M Worte mit 8 Bitstellen entsprechend den M Nachbarschaftsuntergruppen enthält, und zwar eine für jedes von M möglichen Unterfeldern. Das Ausgangssignal dieses Speichers wird durch das Eingangssignal der Anordnung ausgewählt, welches das Unterfeldzeichen R ist, wobei R den Wert 1,2, ..., M haben kann. Das Nachbarschaftsspeicherelement kann durch die Steuerung über die Adressensammelleitung und die DatenSammelleitung ähnlich programmiert werden, wie es für das N-Register der Fall ist.

Das Unterfeldzeichen R wird aus der Zentralzellenposition i, j in der logischen Unterfeldanordnung abgeleitet. Die genaue Ausführung dieses Netzwerks hängt von der Zahl der Unterfelder

030 037/0Λ2 1

und ihrer jeweiligen Konfiguration in der Datenanordnung ab. Da Zentralzellen sequentiell geprüft werden, können ihre Koordinaten durch einen Zähler laufend registriert werden, wenn dieser durch die Steuerung entsprechend der Position des Moduls in der Kette auf eine Anfangsstellung gesetzt wird.

Die Nachbarschaftsverarbeitungsstufe nach Fig. 6 bis 10 arbeitet so allgemein, daß alle nützlichen Nachbarschaftstransformationen mit einer oder mehr Verarbeitungsstufen in Reihenanordnung durchgeführt werden können. Die in Fig. gezeigte Schaltung ist jedoch für den Fall vorteilhaft, daß bestimmte Transformationsarten durch eine einzige Verarbeitungsstufe anstelle von mehreren durchgeführt werden können. Die in Fig. 12 gezeigte Schaltung stimmt mit der nach Fig. 8 überein mit dem Unterschied, daß das ODER-Glied durch eine allgemeinere logische Funktion von acht Variablen ersetzt ist, die in einem Speicher mit direktem bzw. wahlfreiem Zugriff gespeichert sind. Dieser Speicher kann selbstverständlich über die Ädressensammelleitung und die Datensammelleitung von der Steuerung programmiert werden.

030037/0421

-Μ-

Leerseite

Claims

-X-

Patentansprüche

(y Einrichtung zur elektronischen Verarbeitung von BiId-

und/oder Zeichenmustern, die von einer Datenquelle in Form serieller digitaler elektrischer Signale mit mehreren zulässigen Zuständen geliefert werden und eine Matrix von Musterpunkten darstellen, gekennzeichnet durch eine Kette gleichartiger» in Reihe geschalteter Transformationsmodule (10), durch mehrere in Reihe geschaltete Digitalspeichervorrichtungen zur vorübergehenden Speicherung eines Nachbarschaftsbereichs der Matrix, der aus den Zuständen eines zentralen Datenpunkts und der ihn umgebenden Punkte gebildet ist, durch eine Vorrichtung zum Schieben der Signale durch die Digitalspeichervorrichtungen zum sequentiellen Zugriff zu allen in der Matrix vorhandenen Nachbarschaftsbereichen, durch eine mit den Digitalspeichervorrichtungen verbundene Digitalsteuerung zur Analyse eines jeden Nachbarschaftsbereichs in der jeweiligen Digitalspeichervorrichtung und zur Erzeugung eines Ausgangssignals am Eingang des nächstfolgenden Moduls (10) abhängig von der Analyse, umfassend eine Vorrichtung zur Speicherung eines Nachbarschaftsmusters und einen Vergleicher zum Vergleich des gespeicherten Musters mit in den Digitalspeichervorrichtungen gespeicherten Nachbarschaftswerten, durch eine zentrale Programmiervorrichtung (20), die mit der Digitalsteuerung eines jeden Moduls (10) verbunden ist und die Analyse des Nachbarschaftsbereichs von Punkten in jedem Modul (10) durch Übergabe der Nachbarschaftsmuster an die jeweilige Digitalsteuerung ändert, und durch eine mit dem Ausgang des letzten Moduls (10) verbundene Vorrichtung (18) zur Nutzung der transformierten Ausgangsmatrix.

030037/0421
2. Einrichtung nach Anspruch 1, dadurch gekennzeichnet, daß das Äusgangssignal der jeweiligen Digitalsteuerung eine größere Anzahl zulässiger Zustände als die jeweils zu analysierenden Punkte hat.
3. Einrichtung nach Anspruch 2, dadurch gekennzeichnet, daß die Vorrichtung zur Nutzung (18) der transformierten Matrix eine Anzeigevorrichtung zur Anzeige einer Punktmatrix ist, die ein Muster darstellt, in dem jeder Punkt eine größere Anzahl zulässiger Zustände als sein äquivalenter Punkt in der ursprünglichen, dem ersten Modul (10) zugeführten Matrix hat.
4. Einrichtung nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß der Nachbarschaftsbereich aus einer N χ M-Anordnung von Punkten besteht und daß die Vorrichtung zur Aussonderung des Nachbarschaftsbereichs NxM Speichervorrichtungen enthält.
5. Einrichtung nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß die Digitalsteuerung einen Vergleicher zum Vergleich des Zustandes des Zentralpukts in dem Nachbarschaftsbereich mit einem durch die Programmiervorrichtung (20) gelieferten Wert enthält.
6. Einrichtung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß die Digitalsteuerung einen Vergleicher zum Vergleich der Zustände der Umgebungspunkte in dem Nachbarschaf tsber eich mit einem durch die Programmiervorrichtung (20) gelieferten Wert enthält.

030037/042 1