DE3804938C2

DE3804938C2 - Bildverarbeitungseinrichtung

Info

Publication number: DE3804938C2
Application number: DE3804938A
Authority: DE
Inventors: Yoshinobu Mita; Miyuki Enokida; Yoshihiro Ishida; Naoto Kawamura
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1987-02-18
Filing date: 1988-02-17
Publication date: 1994-07-28
Anticipated expiration: 2008-02-18
Also published as: US5692210A; US6477281B2; DE3804938A1; US20020067861A1

Description

Die Erfindung bezieht sich auf eine Bildverarbeitungseinrichtung gemäß dem Oberbegriff des Patentanspruchs 1.

Wenn ein Bild mit hoher Geschwindigkeit verarbeitet werden soll, besteht das übliche Vorgehen darin, sich auf die Computerverarbeitung unter Anwendung von Programmen zu stützen. Zur Behandlung größerer Bilddatenmengen sind jedoch höhere Verarbeitungsgeschwindigkeiten erforderlich. Zur Steigerung der Verarbeitungsgeschwindigkeit können zweierlei Verfahren angewandt werden: Das eine besteht darin, eine Schaltungsausstattung zur sequentiellen Verarbeitung oder ein sogenanntes "Pipeline"-System zu benutzen. Bei dem anderen Verfahren wird ein Parallelverarbeitungssystem benutzt, indem viele Prozessoren parallel angeordnet sind.

Bei dem ersten System besteht eine Einschränkung hinsichtlich der erzielbaren Verarbeitungsgeschwindigkeit, da die für die Verarbeitung erforderliche Taktfrequenz mit einem Anstieg der Geschwindigkeit ansteigt, mit der die Bilddaten verarbeitet werden. Andererseits kann bei dem letztgenannten System die Verarbeitungsgeschwindigkeit nach Wunsch dadurch gesteigert werden, daß die Anzahl der parallel betriebenen Prozessoren erhöht wird. Letztlich kann eine maximale Geschwindigkeit dadurch erreicht werden, daß Prozessoren in einer Anzahl vorgesehen werden, die gleich der Anzahl von Bildelementen ist. Aus diesem Grund ist das Verfahren mit dem letzteren System nun in den Mittelpunkt vieler Interessen gerückt.

Hierbei ist eine Verarbeitung für die Verbindung zwischen Bildelementen von Bedeutung, wobei es notwendig ist, daß die Verarbeitung während einer solchen Querverbindung fortschreitet. Bei dem genannten Parallelverarbeitungssystem ist es bei der Behandlung von Daten für hohe Auflösung unmöglich, Prozessoren in einer der Anzahl der Bildelemente äquivalenten Anzahl vorzusehen. Beispielsweise beträgt bei einem Bild, das von einem Blatt im Format A4 mit 16 Bildelementen je Millimeter gelesen wird, die Anzahl der Bildelemente ungefähr 16 M, so daß daher das gleichzeitige Ausstatten des Systems mit derart vielen Prozessoren undenkbar ist.

Infolgedessen ist es erforderlich, eine Bildverarbeitung unter Benutzung einer endlichen kleinen Anzahl von Prozessoren auszuführen. In der US 4 786 820 ist ein Verfahren für eine derartige Parallelverarbeitung vorgeschlagen, das die Unterteilung der Bilddaten in eine Vielzahl von Blöcken aus jeweils mehreren Bilddatenposten und das Verarbeiten der Bilddaten in einen jeden Block durch jeweils eine von einer Vielzahl von Zentraleinheiten vorsieht. Die Anordnung ist derart getroffen, daß jede Zentraleinheit die Bilddaten des entsprechenden Blocks sowie die Bilddaten der benachbarten Blöcke aufnimmt und daß die Zentraleinheit die Bilddaten des entsprechenden Blocks verarbeitet.

Das vorgeschlagene System läßt jedoch noch viel Spielraum zur Verbesserung hinsichtlich der Leistungsfähigkeit und des Aufbaus offen.

Aus DE-Z, "Image Processing on the Massively Parallel Processor" von J.L. Potter, in "Computer", Januar 1983, Seiten 62 bis 67, von dem im Oberbegriff des Patentanspruchs 1 ausgegangen wird, ist ein Bildverarbeitungsgerät mit einer aus 128×128 parallel arbeitenden Prozessorelementen bestehenden Prozessoreinheit beschrieben. Zur parallelen Verarbeitung der Bilddaten wird aus dem Bildspeicher jeweils ein aus 128×128 Bildelementen bestehender Bilddatenblock ausgelesen und zu den Prozessorelementen übertragen. Der Bildspeicher ist dabei in der Art organisiert, daß auf jede gewünschte Speicherzelle selektiv zugegriffen werden kann.

In der DE-Z, "Image Processing Machines in Japan" von Masatsugo Kidode, in "Computer", Januar 1983, Seiten 68 bis 80 ist ein Bildverarbeitungsgerät beschrieben, das 4×4 parallel arbeitende Prozessorelemente aufweist. Zur parallelen Verarbeitung der Bilddaten wird aus dem Bildspeicher jeweils ein aus 4×4 Bildelementen bestehender Bilddatenblock ausgelesen und zu den Prozessorelementen übertragen. Der Bildspeicher ist dabei derart organisiert, daß ein aus beliebigen 4×4 Bildelementen bestehender Bereich parallel auslesbar ist.

Die beiden vorstehend genannten Vorrichtungen weisen noch den Nachteil auf, daß das Auslesen der Bildelemente einen relativ hohen schaltungstechnischen und zeitlichen Aufwand erfordert.

Der Erfindung liegt die Aufgabe zugrunde, ein Bildverarbeitungsgerät der im Oberbegriff des Patentanspruchs 1 angegebenen Art derart weiterzubilden, daß auf einfache Art und Weise eine sehr rasche und effiziente Verarbeitung von in einem Bildspeicher gespeicherten Bildelementdaten ermöglicht wird.

Diese Aufgabe wird durch eine Bildverarbeitungseinrichtung mit den im Patentanspruch 1 angegebenen Merkmalen auf besonders vorteilhafte Art und Weise gelöst.

Vorteilhafte Weiterbildungen der Erfindung sind Gegenstand der Unteransprüche.

Demnach ist der Bildspeicher so aufgebaut, daß jeweils einem mehrere Speicherzellen umfassenden Speicherbereich dieselbe Adresse zugeordnet ist, wobei Bildelementdaten an übereinstimmenden Stellen innerhalb der Bildspeicherbereiche einem jeweils übereinstimmenden Speicherelement zugeordnet sind. Zum Auslesen der Daten eines gewünschten Bildfeldes werden die Adreßdaten, welche die Lage der Bildpunkte des Bildfeldes in einem jeweiligen Bildspeicherbereich angeben, ausgelesen und zur Adressierung des Bildspeichers zusammengefaßt.

Auf diese Weise ist es möglich, daß zum Auslesen von Daten aus dem Bildspeicher nicht jede Speicherzelle einzeln adressiert werden muß, sondern statt dessen durch Anlegen einer einzigen Adresse gleich alle der im gewünschten Bildfeld liegenden Bildelementdaten erhalten werden können.

Das erfindungsgemäße Gerät ermöglicht somit eine rasche und effiziente Verarbeitung von in einem Bildspeicher gespeicherten Bildelementdaten.

Die Erfindung wird nachstehend anhand von Ausführungsbeispielen unter Bezugnahme auf die Zeichnung näher erläutert, in deren Figuren durchgehend gleiche Bezugszeichen die gleichen oder gleichartige Teile bezeichnen.

Fig. 1 ist eine Blockdarstellung, die eine Bildverarbeitungseinrichtung gemäß einem Ausführungsbeispiel zeigt.

Fig. 2 ist eine Darstellung, die den Zusammenhang zwischen einem Einzelbild und Adressen von Speicherelementen veranschaulicht.

Fig. 3 ist eine Darstellung, die einen Speicher mit 4×4 Speicherelementen als Ganzen zeigt.

Fig. 4 zeigt einen Speicher mit zugeordneten Adressengeneratoren.

Fig. 5 zeigt einen Teil eines Bildes.

Fig. 6 zeigt die Zuordnung eines Speichers für einen Teil eines Bildes.

Fig. 7 ist ein Blockschaltbild einer Speicheradressen- Steuerschaltung.

Fig. 8 ist ein Blockschaltbild einer Bildelementdaten- Steuerschaltung.

Fig. 9(a) und (b) sind Blockdarstellungen, die den Aufbau der Bildverarbeitungseinrichtung gemäß anderen Ausführungsbeispielen zeigen.

Fig. 10 ist eine Darstelllung eines Einzelbilds.

Fig. 11 zeigt k×l Speicherelemente.

Fig. 12 und 13 zeigen eine einzelne Speichereinheit.

Fig. 14 und 15 sind Blockschaltbilder von Speicherelementabruf- Steuerschaltungen.

Fig. 16 zeigt ein Einzelbild.

Fig. 17 zeigt k×l Speicherelemente.

Fig. 18 ist ein Blockschaltbild einer Adressenumsetzschaltung.

Fig. 19(a) ist ein Blockschaltbild, das das Konzept der Gestaltung eines Prozessorelements veranschaulicht.

Fig. 19(b) ist ein Blockschaltbild eines Prozessorelements, in welchem eine logische Recheneinheit nach Fig. 19(a) durch einen Mikroprozessor gebildet ist.

Fig. 20 ist eine grafische Darstellung zur Erläuterung einer Dichteumsetzung.

Fig. 21 ist ein Ablaufdiagramm eines Verfahrens zur Dichteumsetzung.

Fig. 22 ist ein Ablaufdiagramm eines Verfahrens zur Farbumsetzung.

Fig. 23 ist ein Ablaufdiagramm eines Verfahrens zum Maskieren.

Fig. 24 zeigt eine Blockdaten-Wählschaltung.

Fig. 25 zeigt ein Beispiel für eine Adressenumsetzschaltung für das Umsetzen von Adressen innerhalb von Blöcken.

Fig. 26 zeigt eine Schaltung zum Erzeugen von Adressen innerhalb von Blöcken vor einer Umsetzung.

Die in Fig. 1 gezeigte Bildverarbeitungseinrichtung gemäß dem ersten Ausführungsbeispiel hat einen Bildspeicher 1 für das Speichern des Bilds einer Seite, eine Prozessoreinheit 2 und einen peripheren Teil 3 wie eine Eingabe/Ausgabe-Einheit. Die Fig. 1 veranschaulicht nur die Anordnung dieser Grundkomponenten und zeigt, daß die Prozessoreinheit 2 mit dem Bildspeicher 1 verbunden ist. Nach Fig. 1 werden n × m Bilddatenposten an irgendwelchen Stellen in dem Bildspeicher 1 zu der Prozessoreinheit 2 übertragen, die aus einer n × m-Matrix von Prozessorelementen 2a gebildet ist, in denen die Daten mit hoher Geschwindigkeit verarbeitet werden, wonach sie in den Bildspeicher 1 zurückgeleitet werden. Die n × m Prozessorelemente 2a in der Matrix führen die Verarbeitung gleichzeitig aus.

Damit ist die Gesamtausstattung eine solche für die sog. Parallelverarbeitung. Die Fig. 9(a) und (b) zeigen andere mögliche Anordnungen. Nach Fig. 9(a) werden Bilddaten aus einem eingangsseitigen Bildspeicher 91 einer Prozessoreinheit 92 zugeführt, die eine Vielzahl von Prozessorelementen enthält, in denen eine Vielzahl von Bildelementen der vorgeschriebenen parallelen Verarbeitung unterzogen werden, wonach die sich ergebenden Bilddaten in einen ausgangsseitigen Bildspeicher 93 eingespeichert werden. Dies erfolgt unter Steuerung durch eine Steuerschaltung 94, die mit den Bildspeichern 91 und 93 und mit der Prozessoreinheit 92 verbunden ist. Nach Fig. 9(b) ist der Bildspeicher 91 oder 93 mit der Prozessoreinheit 92, einer Eingabeeinheit 95 und einer Ausgabeeinheit 96 über eine gemeinsame Sammelleitung verbunden.

Es wird nun der Bildspeicher 1 ausführlich beschrieben.

Zur Vereinfachung sei angenommen, daß ein Bild das Format 1024 × 1024 Bildelemente hat und daß der Bildspeicher Daten in Form von acht Bit je Bildelement speichert. Eine Änderung des Bildformats wird lediglich durch Ändern der Architektur des Ausführungsbeispiels bewerkstelligt. Ferner sei angenommen, daß die Prozessoreinheit 2 aus 4 × 4, also insgesamt 16 Prozessorelementen 2a gebildet ist.

Die Fig. 2 veranschaulicht die Gestaltung des Bildspeichers 1. Nimmt man an, daß gemäß der Darstellung ein Bild aus 1024 × 1024 Bildelementen zusammengesetzt ist und das Bild in Einheiten aus 4 × 4 Bildelementen unterteilt wird, so wird das Bild auf 256 × 256 Blöcke, also insgesamt 64 k (=65536) Blöcke aufgeteilt. Dies kann gemäß Fig. 3 dargestellt werden, in welcher 64 k Einheiten aus 4 × 4 Bildelementen angenommen sind, von denen jedes die Länge von 8 Bit hat. Hinsichtlich der Adressenbereiche des Speichers erfolgt daher die Adressierung in drei Dimensionen mit 4 × 4 × 64 k. Falls einem einzelnen Speicherbaustein 64 k Bildelemente für eine Bildelementestelle aus der 4 × 4-Matrix der Bildelemente gemäß der Darstellung in Fig. 3 zugeordnet sind, ist ein Speicherbaustein erforderlich, in dem für die 64 k Adressenstellen eine jede Adresse eine Tiefe von 8 Bit hat. Dies würde einen Speicherbaustein mit einer Kapazität von 512 kBit (= 64 kByte) erforderlich machen. Bei dem beschriebenen Ausführungsbeispiel werden zwei dynamische Schreib/Lesespeicher (DRAM) für jeweils 256 kBit in Kombination verwendet. D. h., es werden zwei dynamische 256 kBit- Speicher für jeweils 64 k × 4 Bit verwendet und in der Form 64 k × 8 Bit eingesetzt. Diese beiden Speicherbausteine werden als ein Speicherelement 1a bezeichnet. Nachstehend wird eine Prozessoreinheit als "PU", ein Prozessorelement als "PE" und ein Speicherelement als "ME" bezeichnet.

Der Bildspeicher 1 ist aus 16 Bildelementen 1a entsprechend einer Matrix von 4 × 4 Bildelementen zusammengesetzt. Die Fig. 4 zeigt die Anordnung dieser 4 × 4 Speicherelemente 1a. Für jedes Speicherelement 1a wird dessen Zeilenadresse und dessen Spaltenadresse bestimmt, so daß Bilddaten für die 64 k Adressenstellen für ein einzelnes Bildelement aus den 4 × 4 Bildelementen in ein jedes Speicherelement eingegeben bzw. aus diesem ausgegeben werden können. An jedes der 4 × 4 Speicherelemente 1a werden die Adressen von einem Zeilenadressengenerator 4 und einem Spaltenadressengenerator 5 angelegt. Es ist anzumerken, daß ein einziger Adressengenerator ausreichend ist, wenn die Speicherelemente 1a dynamische Speicher sind und die Zeilen- und Spaltenadressen im Zeitmultiplex angelegt werden. Wenn dies der Fall ist, ist eine Umschaltsteuerung für die Zeitmultiplex-Verschachtelung der Zeilen- und Spaltenadressen erforderlich. Die Zeilen- und Spaltenadressen entsprechen jeweils A bzw. B für einen jeweils mit (A1, B1) bezeichneten Block in einem jeweiligen Einzelbild gemäß Fig. 2.

Durch das Anlegen der Adressen aus den jeweiligen Adressengeneratoren 4 und 5 kann in die Speicherelemente 1a für die 4 × 4 Bildelemente eingeschrieben bzw. aus diesen ausgelesen werden. D. h., durch eine einzige Adressenbestimmung können 4 × 4 Speicherelemente gleichzeitig betrieben werden. Es sei angenommen, daß zu diesem Zweck Datenleitungen für acht Bit direkt von jedem der Speicherelemente 1a wegführen.

Falls Daten mit der Zeilenadresse A (0 ≦ A ≦ 255) und der Spaltenadresse B (0 ≦ B ≦ 255) aus dem Bildspeicher 1 abgerufen werden, werden die der Adresse (A, B) nach Fig. 2 entsprechenden Bilddaten aus 4 × 4 Bildelementen ausgelesen, von denen jedes die Länge von acht Bit hat.

Der gleichzeitige Zugriff zu einer Vielzahl von Bildelementen wird nun in allgemeiner Form beschrieben.

Die Fig. 10 zeigt eine Bildseite. Gemäß der Darstellung sind die Bilddaten in aneinander angrenzende Blöcke aus jeweils k × l Bildelementen unterteilt. Gemäß der Darstellung in Fig. 11 sind die k × l Bildelemente in einen jeden Block mit k × l Speicherelementen 1a in Beziehung gesetzt bzw. diesen zugeordnet. Die aus diesen k × l Bildelementen gebildeten Blöcke sind von einem Rand her mit (0, 0), (0, 1) (0, 2) (0, 3),. . . numeriert und entsprechen der Speichereinheit 1 aus den k × l Speicherelementen 1a gemäß Fig. 12. In der Fig. 13 ist die Speichereinheit 1 zweidimensional dargestellt. Das Speicherformat bei dem Abruf der Speichereinheit 1 sind Einheiten im Blockformat aus k × l Bildelementen. Daher werden auch bei dem Abruf eines Blocks R aus k × l Bildelementen in beliebiger Lage in der Speichereinheit 1 alle k × l Speicherelemente 1a abgerufen. Darüber hinaus wird je ein Speicherelement 1a eine Adresse abgerufen. Demgemäß werden k × l Bildelemente zum gleichen Zeitpunkt herausgegriffen.

Auf diese Weise werden Bilddaten aus k × l benachbarten Bildelementen an beliebigen Stellen in dem Bild gleichzeitig abgerufen und ausgelesen, wonach diese Bilddaten mittels der Prozessoreinheit 2 verarbeitet werden. Die mittels der Prozessoreinheit 2 verarbeiteten Bilddaten können durch Zugriff zu beliebigen Stellen der Speichereinheit 1 wieder in einen Block H aus k′ × l′ Bildelementen der Speichereinheit 1 eingeschrieben werden. Die nachfolgende Beschreibung beruht auf der Annahme, daß k′ = k und l′ = l gilt.

Der Zugriff zu einem Speicher für nur k′ × l′ Bildelemente wird nun ergänzend erläutert. Falls die von der Prozessoreinheit 2 ausgeführte Verarbeitung eine Raum- bzw. Ortsfrequenzfilterung gemäß einem Rechenvorgang unter Verwendung eines Ziel- Bildelements und der dieses umgebenden Bildelemente ist, ist das schreibseitige Blockformat k′ × l′ kleiner als das leseseitige Blockformat k × l. Im allgemeinen erfolgt daher eine Verarbeitung in der Weise, daß das schreibseitige Blockformat k′ × l′ zu 1 × 1 wird. Auch wenn die von der Prozessoreinheit 2 ausgeführte Verarbeitung nicht eine Ortsfrequenzfilterung, sondern eine Bildreduktion ist, wird das an der Schreibseite abgerufene Blockformat k′ × l′ kleiner als das an der Leseseite abgerufene Blockformat k × l.

Allgemein sind hinsichtlich des schreibseitigen Blockformats k′ × l′ die Werte k′ und l′ die kleinsten ganzen Zahlen, die den Bedingungen k′ ≧ αk und l′ < βl genügen, wobei α und β jeweils das Längsreduktionsverhältnis bzw. das Querreduktionsverhältnis sind. Falls bei der Ausführung der Verarbeitungen gemäß den vorstehend genannten beiden Beispielen der Lesespeicher und der Schreibspeicher identisch sind bzw. die gleiche k × l-Speicheranordnung verwendet wird, muß schreibseitig das Einschreiben in einem Format k′ × l′ erfolgen, das kleiner als das Format k × l der Speichereinheit 1 ist. In einem solchen Fall erfolgt der Zugriff zu nicht allen k × l Speicherelementen 1a. Statt dessen muß die Gestaltung derart getroffen werden, daß die nicht für den Schreibvorgang benötigten Speicherelemente 1a maskiert und nicht abgerufen werden. Das Maskieren der nicht für den Schreibvorgang benötigten Speicherelemente und der gleichzeitige Zugriff zu nur k′ × l′ Speicherelementen können auf einfache Weise dadurch bewerkstelligt werden, daß Freigabesignale nur an die k′ × l′ Elemente aus den Bausteinen der k × l Speicherelemente 1a und nicht an die restlichen (k × l) - (k′ × l′) Speicherelemente angelegt werden.

Im Hinblick auf ein Ausführungsbeispiel, bei dem vorgeschriebene Bildelemente an beliebigen Stellen abgerufen werden, werden nun ein Fall, bei dem die Speichereinheit 4 × 4-Anordnung hat, sowie ein Fall beschrieben, bei dem die Speichereinheit k × l-Anordnung hat. Ferner wird auch die Baustein- Freigabesteuerung für das vorangehend genannte Maskieren beschrieben.

Zunächst wird das Ausführungsbeispiel für den Fall beschrieben, daß das Blockformat k × l das Format 4 × 4 ist.

In der Fig. 5 ist ein Teil der Fig. 2 vergrößert dargestellt. Die Verarbeitung wird für einen Fall beschrieben, daß Bilddaten aus irgendeinem 4 × 4-Block S in dem Bildspeicher 1 ausgelesen werden, die Daten mittels der Prozessoreinheit 2 verarbeitet werden und die Ergebnisse in irgendeinen beliebigen 4 × 4-Block T übertragen werden. (Gemäß Fig. 5 kann der Block S mehrere in Fig. 2 gezeigte Blöcke überlappen). Die in Fig. 5 und 6 gezeigten 4 × 4-Zellen grenzen 4 × 4 bzw. 16 Speicherelemente 1a ab. Es sei angenommen, daß diese 16 Speicherelemente 1a mit Aa, Ab, . . ., Ba, Bb, . . ., Ca, . . . DC, Dd bezeichnet sind. Falls zuerst der 4 × 4-Block S ausgelesen wird, werden (N, M) als Zeilen- und Spaltenadresse an das Speicherelement Dd aus den 16 Speicherelementen 1a angelegt. Ferner werden (N, M + 1) an die Speicherelemente Da, Db und Dc, (N + 1, M) an die Speicherelemente Ad, Bd und Cd sowie (N + 1, M + 1) an die restlichen Speicherelemente angelegt. Diese Adressen werden von dem Zeilenadressengenerator 4 und dem Spaltenadressengenerator 5 erzeugt. Es ist offensichtlich, daß dann, wenn der Ort eines Eckpunktes u des 4 × 4-Blocks S bestimmt wurde, die Ortsadressen in horizontaler und vertikaler Richtung durch vier dividiert werden und die Zeilen- und Spaltenadressen für die Speicherelemente Aa bis Dd eindeutig durch Reste n und m bestimmt sind. Für den Eckpunkt u sei die Ortsadresse u (Y, X) angenommen. Er ergibt sich dann folgendes:

Y = 4N + n (n = 0, 1, 2, 3)
X = 4M + m (m = 0, 1, 2, 3)

Es ist beispielsweise eine Anordnung denkbar, bei der die Informationen M und N und die Informationen m und n in Nachschlagetabellen eingegeben werden und die Adressen mittels der Adressengeneratoren 4 und 5 an die Speicherelemente Aa bis Dd ausgegeben werden. Aus der vorstehenden Beschreibung ist ersichtlich, daß der ausgegebene Wert zu diesem Zeitpunkt irgendeiner der Werte M, N, N + 1 oder M + 1 ist. Unter Nutzung dieser Eigenschaft ist es ausreichend, in eine Nachschlagetabelle n oder m einzugeben, in Abhängigkeit von dem eingegebenen Wert "0" oder "1" auszugeben und eine Steuerung zu der Ermittlung auszuführen, ob die an die Speicherelemente Aa bis Dd anzulegende Adresse N oder M aufzustufen ist oder nicht, wie es in Fig. 7 dargestellt ist. Hierbei werden die Werte n und N an dem Zeilenadressengenerator 4 und die Werte m und M an dem Spaltenadressengenerator 5 eingesetzt.

Auf diese Weise werden über eine Nachschlagetabelle 71 und Addierer 72a bis 72p gemäß Fig. 7 Adressen aus den Adressengeneratoren 4 und 5 an die 4 × 4-Matrix der 16 Speicherelemente 1a angelegt, so daß gleichzeitig 16 Datenposten erhalten werden können.

Diese 16 Datenposten werden nach irgendeiner Verarbeitung in der Prozessoreinheit 2 oder ohne Verarbeitung in den in Fig. 5 gezeigten Block T für 4 × 4 Bildelemente übertragen. Die aus den 16 Speicherelementen Aa bis Dd ausgelesenen Bilddaten müssen jedoch nicht unbedingt zu den gleichen Speicherelementen Aa bis Dd übertragen werden. Falls der 4 × 4-Bildelemente- Speicherblock S nach Fig. 5 in den 4 × 4-Bildelemente-Speicherblock T übertragen wird, müssen die aus dem Speicherelement Aa des 4 × 4-Bildelemente-Speicherblocks S ausgelesenen Daten zu dem Speicherelement Dc übertragen werden.

Es wird nun beschrieben, in welche Speicherelemente der Speicherelemente Aa bis Dd die aus den Speicherelementen Aa bis Dd ausgelesenen 16 Datenposten einzuschreiben sind, wenn Anfangs- bzw. Eckpunkte u und v der 4 × 4-Speicherblöcke S bzw. T beliebige Ortsadressen (Y, X) und (Y′, X′) haben.

Wenn Y, X, Y′ und X′ folgendermaßen ausgedrückt sind:

Y = 4N + n (n = 0, 1, 2, 3)
X = 4M + m (m = 0, 1, 2, 3)
Y′ = 4 P + p (p = 0, 1, 2, 3)
X′ = 4 Q + q (q = 0, 1, 2, 3)

ergeben sich x und y aus:

p - n = 4y′ + y (y′ = -1, 0; y = 0, 1, 2, 3) (1)
q - m = 4x′ + x (x′ = -1, 0; x = 0, 1, 2, 3) (2)

Zuerst wird die Zeilenreihe A aus den Speicherelementen Aa, Ab, Ac und Ad unter zyklischer Vertauschung x-malig nach rechts versetzt. Dadurch ergibt sich eine Zeilenreihe A′. Auf gleichartige Weise werden Zeilenreihen B, C und D unter zyklischer Vertauschung nach rechts versetzt, wodurch sich mit B′, C′ und D′ bezeichnete Zeilenreihen ergeben.

Als nächstes werden die Spaltenreihen (ABCD)′ aus den Zeilenreihen A′, B′, C′ und D′ unter zyklischer Vertauschung y- malig nach unten versetzt.

Aus der Fig. 5 ist ersichtlich, daß n, m, p und q jeweils die Werte 3, 3, 2 bzw. 1 haben. Daher ergibt sich aus den Gleichungen (1) und (2): y′ = -1, y = 3, x′ = -1, x = 2. Infolgedessen wird gemäß der vorstehenden Beschreibung folgende Matrix erreicht:

Wenn eine zweimalige zyklische Vertauschung nach rechts vorgenommen ist, ergibt sich:

A′ = (Ac, Ad, Aa, Ab)
B′ = (Bc, Bd, Ba, Bb)
C′ = (Cc, Cd, Ca, Cb)
D′ = (Dc, Dd, Da, Db)

Wenn dann eine dreimalige zyklische Vertauschung nach unten vorgenommen ist, ergibt sich die Matrix:

(Bc, Bd, Ba, Bb)
(Cc, Cd, Ca, Cb)
(Dc, Dd, Da, Db)
(Ac, Ad, Aa, Ab) (3)

Es wird nun die Matrix (3) mit folgender Grund- bzw. Ursprungsmatrix (4) verglichen:

Aa, Ab, Ac, Ad
Ba, Bb, Bc, Bd
Ca, Cb, Cc, Cd
Da, Db, Dc, Dd (4)

Die Ursprungsmatrix (4) wird einfach durch zweidimensionales Anordnen der aus den Speicherelementen Aa bis Dd ausgelesenen Daten in der Aufeinanderfolge von links nach rechts und von oben nach unten gebildet. Die Matrix (3) entspricht einer Matrix, die durch Anordnen der in die Speicherelemente Aa bis Dd einzuschreibenden Daten auf zweidimensionale Weise in der Aufeinanderfolge erzielt wird. Im einzelnen zeigt die Matrix (3) als Beispiel, daß die aus dem Speicherelement Aa ausgelesenen Daten in die vierte Zeile und dritte Spalte eingeschrieben werden. Die Ursprungsmatrix (4) zeigt, daß die vierte Zeile, dritte Spalte Dc ist. Infolgedessen ist es ersichtlich, daß die aus dem Speicherelement Aa ausgelesenen Daten in das Speicherelement Dc einzuschreiben sind.

Da es leicht ersichtlich ist, daß die aus dem Speicherelement Aa in Fig. 5 ausgelesenen Daten in den Ort Dc eingeschrieben werden sollen, ist die Versetzung von Aa zu dem Ort Dc äquivalent einem Übergang von der Ortsadresse u zu der Ortsadresse v. Da ferner die Speicherelemente 1a die 4 × 4-Anordnung haben, können die durch das Dividieren der Ortsadressen in der horizontalen und vertikalen Richtung durch "4" erhaltenen Reste als Versetzungen x und y der Speicherelemente angesehen werden. Falls beispielsweise die Versetzungen der Ortsadressen u und v Vielfache von "4" sind, werden die Versetzungen x und y zu "0", so daß die aus einem bestimmten Speicherelement ausgelesenen Daten nach der Verarbeitung in das gleiche Speicherelement eingeschrieben werden.

Die Ausführung der vorstehenden Verarbeitung durch Schaltungsausstattung wird nun kurz beschrieben. Die Fig. 8 ist eine Blockdarstellung, gemäß der gleichzeitig aus der Speichereinheit 1 mit der 4 × 4-Matrix aus 16 Speicherelementen 1a ausgelesene Daten mittels der Prozessoreinheit 2 verarbeitet werden. Diese Daten werden zu vier Elementen gleichzeitig durch zyklische Vertauschung in x-Versetzungs-Umlauftauschern 81a bis 81d x-malig versetzt. Die Ergebnisse werden dann mittels eines y-Versetzungs-Umlauftauschers 82 durch zyklische Vertauschung y-malig versetzt und jeweils in die Speicherelemente Aa bis Ad, Ba bis Bd, Ca bis Cd bzw. Da bis Dd eingeschrieben.

Die jeweils in den y-Versetzungs-Umlauftauscher (Rotator) 82 eingegebenen Daten sind die Daten für vier Elemente, so daß daher selbstverständlich der y-Versetzungs-Umlauftauscher 82 aus vier Umlauftauschern gebildet sein kann, die genau die gleichen wie die x-Versetzungs-Umlauftauscher 81a bis 81d sind. Selbstverständlich müssen die Umlauftauscher die gleiche Bit-Anzahl-Tiefe wie die Speicherdatentiefe haben und die Anzahl der eingesetzten Umlauftauscher muß gleich der Tiefe der Speicherdaten sein. Als Umlauftauscher können Schieberegister oder Bläschenspeicher verwendet werden.

Das vorstehende wird nun in allgemeiner Hinsicht betrachtet.

Falls ein Speicherblock das Format k × l hat, erhält die Speichereinheit 1 eine k × l-Anordnung. Wenn in diesem Fall der Speicherblock S aus k × l Bildelementen an beliebigen Stellen mittels der Prozessoreinheit 2 verarbeitet wird und die Ergebnissse in den Speicherblock T aus k × l Bildelementen an beliebigen Stellen übertragen werden, erhält man die Werte n, m, p und q aus folgenden Gleichungen:

Y = kN + n (n = 0, 1, . . ., k-1)
X = lM + m (m = 0, 1, . . ., l-1)
(N, M, P, Q = 1, 2, 3, . . .)
Y′ = kP + p (p = 0, 1, . . ., k-1)
X′ = lQ = q (q = 0, 1, . . ., l-1) (10)

wobei die Ortsadresse des Eckpunkts des Blocks S (Y, X) ist und die Ortsadresse des Eckpunkts des Blocks T (Y′, X′) ist. Unter Einsetzen von x und y in

p - n = Ky′ + y (y′ = 1,0, y = 0, 1, 2, 3, . . ., k-1)
q - m = lx′ + x (x′ = 1,0, x = 0, 1, 2, 3, . . ., l-1) (11)

ist es ausreichend, zum Ausführen der Verarbeitung die x- Versetzungs-Umlauftauscher 81a bis 81d und den y-Versetzungs- Umlauftauscher 82 der in Fig. 8 gezeigten Art zu verwenden. In diesem Fall hat der x-Versetzungs-Umlauftauscher l Eingänge und ermöglicht eine Versetzung von 0 bis l-1. Der y- Versetzungs-Umlauftauscher hat k Eingänge und ermöglicht eine Versetzung von 0 bis k-1. Da darüber hinaus die k Eingangssignale des y-Versetzungs-Umlauftauschers 82 jeweils l Elemente haben, werden l Umlauftauscher für eine Eingabe von k Elementen angeordnet.

Als nächstes wird die Speicherelemente-Zugriffsteuerung für den gleichzeitigen Zugriff zu dem vorangehend genannten k′ × l′-Block gemäß Fig. 10 beschrieben.

Es sei angenommen, daß die Ortsadresse eines Eckpunkts i des k′ × l′-Blocks (f, g) ist. Falls der entsprechend der Gleichung (10) abgerufene Speicher gelesen wird, wird f, g in Y, X eingesetzt. Falls in den Speicher entsprechend dem Zugriff gemäß der Gleichung (10) eingeschrieben wird, wird f, g in Y′, X′ eingesetzt. Wenn das Ergebnis in die Gleichung (11) eingesetzt wird, um y, x zu erhalten, kann die Schaltung gemäß dem in den Fig. 7 und 8 gezeigten Ausführungsbeispiel direkt als für k × l verallgemeinerte Anordnung angewandt werden.

Hierbei werden nur die Bausteine für die k′ × l′ Speicherelemente aus den k × l Speicherelementen eingeschaltet bzw. freigegeben. Falls die Bausteinfreigabe die Ortsadresse (f, g) des Eckpunktes i des k′ × l′-Blocks festgestellt worden ist, sind durch die Gleichung (10) die Werte n, m oder p, q eindeutig bestimmt, so daß auch der Zugriff zu den k′ × l′ Speicherelementen eindeutig bestimmt ist.

Bei einer Speicheranordnung aus k × l Speicherelementen gemäß der bisherigen Beschreibung kann ein Fall in Betracht gezogen werden, bei dem ein k′ × l′-Block gleichzeitig für das Lesen und ein k′′ × l′′-Block gleichzeitig für das Schreiben ausgelesen wird (wobei 0 ≦ k′′ ≦ k und 0 ≦ l′′≦l gilt). Die vorstehende Beschreibung gilt auch in diesem Fall. Ein Ausführungsbeispiel für die in diesem Fall an den Speicherelementen auszuführende Bausteinfreigabe-Steuerung ist in der Fig. 14 dargestellt.

Falls die Ortsadressen der Eckpunkte der Blöcke k′ × l′ und k′′ × l′′ jeweils (Y, X) und (Y′, X′) sind, werden die Werte n, m und p, q aus der Gleichung (10) erhalten. Diese Werte n, m und p, q werden an die Dateneingänge eines Wählers 141a angelegt. An den Wähler wird als Wählsteuersignal ein Speicherzugriff- Lese/Schreib-Signal R/W angelegt. Für das Lesen der Daten werden selektiv n und m ausgegeben, während für das Schreiben der Daten selektiv p und q ausgegeben werden.

Auf gleichartige Weise werden die Blockformate k′ × l′ und k′′ × l′′ in einen Wähler 141b eingegeben, an dem das Signal R/W als Wählsteuersignal dient. Wenn die Daten gelesen werden, werden selektiv k′ und l′ ausgegeben, während bei dem Schreiben der Daten selektiv k′′ und l′′ ausgegeben werden. Es ist offensichtlich, daß dann, wenn für das Lesen die Werte n, m, k′ und l′ bzw. für das Schreiben k′′, l′′, p und q festgelegt worden sind, die Speicherelemente 1a für den Zugriff eindeutig bestimmt sind. Daher werden die von diesen Wählern 141a und 141b ausgegebenen Daten in eine Nachschlagetabelle 142 eingegeben, die Signale zur Steuerung der abzurufenden Speicherelemente 1a aus den k × l Speicherelementen abgibt.

Es ist ersichtlich, daß dann, wenn der Bildspeicher zur Speicherung vor der Verarbeitung durch die Prozessoreinheit 92 gemäß Fig. 9(a) und (b) von dem Bildspeicher zur Speicherung nach der Verarbeitung verschieden ist und die Speicheranordnungen jeweils k × l bzw. K × L sind, zwei Nachschlagetabellen 151 und 152 gemäß Fig. 15 verwendet werden müssen. In diesem Fall haben die Nachschlagetabellen 151 und 152 voneinander verschiedenen Inhalt.

Es treten auch dann keine Probleme auf, wenn k = K und l = L gilt. Falls die vorstehend beschriebene Anordnung verwendet wird, müssen die abzurufenden Speicherelemente nicht alle k × l Speicherelemente sein und es ist eine teilweise Maskierung möglich. Es ist ausreichend, wenn die Anordnung der k × l Speicherelemente auf das Format k × l gewählt ist, welches das größte erforderliche Format ist.

Es wird nun der Zugriff zu den Speicherelementen für die Verarbeitung aller Bilddaten eines Vollbilds beschrieben. D. h., die folgende Beschreibung betrifft ein Abtast- bzw. Abfrageverfahren für den Abruf aller Speicherdaten.

Anhand der Fig. 5 und 6 wurde schon der Zugriff zu einem Speicher in dem Fall beschrieben, daß die Ortskasse des Anfangs- bzw. Eckpunktes u des Blocks aus aneinander angrenzenden k × l Bildelementen schon festgelegt wurde, nämlich Y, X festgelegt wurden, wobei Y die bei der aufeinanderfolgenden Zählung von 0 an in der vertikalen Richtung ausgehend von dem Eckpunkt erhaltene Zahl ist und X die bei der aufeinanderfolgenden Zählung von 0 an in der horizontalen Richtung ausgehend von dem Eckpunkt erhaltene Zahl ist. Anhand folgender Beispiele wird nun beschrieben, in welcher Aufeinanderfolge X und Y für das Verarbeiten des Vollbilds abzufragen sind.

Beispiel 1 Erstes Folgeabfrageverfahren

Dies ist ein Verfahren, bei dem Ortsadressen X, Y von Bilddaten für den Abruf von k × l Speicherelementen dadurch abgefragt werden, daß die Werte um ein ganzzahliges Vielfaches von k bzw. l aufgestuft oder abgestuft werden. Beispielsweise werden Y und X anfänglich auf "0" eingestellt und X wird aufeinanderfolgend in Stufen l erhöht. Wenn X bis zu dem Endwert in der horizontalen Richtung erhöht worden ist, wird X auf "0" rückgesetzt, Y um k erhöht und X in Stufen l erhöht. Dies wird aufeinanderfolgend wiederholt, um das ganze Bild oder einen Teil hiervor abzutasten. Dieses Verfahren wird als erste Folgeabfrageverfahren bezeichnet.

Beispiel 2 Erstes Zufallsabfrageverfahren

X und Y werden nicht gemäß der vorstehenden Beschreibung aufeinanderfolgend erhöht oder vermindert. Statt dessen werden hier und da in dem Vollbild gelegene aufeinanderfolgende k × l- Blöcke unter Zufallsverteilung abgerufen, wobei die zum Zeitpunkt des Abrufs geltenden Werte X und Y Versetzungen sind, die ganzzahlige Vielfache von k und l sind. Dieses Verfahren wird als erstes Zufallsabfrageverfahren bezeichnet.

Beispiel 3 Zweites Folgeabfrageverfahren

Bei diesem Verfahren werden die Ortsadressen X, Y der Bilddaten für den Zugriff zu den k × l Speicherelementen durch Aufstufen oder Abstufen um eine ganze Zahl abgefragt. Beispielsweise werden Y und X anfänglich auf "0" eingestellt, wonach X aufeinanderfolgend in Stufen "1" erhöht wird. Wenn X bis zu dem Endwert in der horizontalen Richtung erhöht worden ist, wird dann X auf "0" rückgesetzt, Y um "1" aufgestuft und X in Stufen "1" erhöht. Dies wird aufeinanderfolgend wiederholt, um ein Einzelbild vollständig oder zum Teil abzutasten. Dieses Verfahren wird als zweites Folgeabfrageverfahren bezeichnet. In diesem Fall wird der gleiche Speicherdatenbereich mehrmalig abgefragt.

Beispiel 4 Zweites Zufallsabfrageverfahren

X und Y werden nicht auf die vorstehend beschriebene Weise aufeinanderfolgend erhöht oder vermindert. Stattdessen werden hier und da in dem Vollbild liegende k × l-Blöcke unter Zufallsverteilung abgerufen, was für alle Werte X und Y ausgeführt wird. Alternativ kann diese Verarbeitung für die Werte X und Y von aufeinanderfolgenden Teilbereichen in dem Vollbild ausgeführt werden. Wenn dies zufallsbedingt erfolgt, wird das Verfahren als zweites Zufallsabfrageverfahren bezeichnet.

Beispiel 5 Block-Folgeabfrageverfahren

Wenn ein abzurufender Speicherblock ein k′ × l′-Speicherblock in einer Speicheranordnung mit k × l Speicherelementen ist, werden Ortsadressen Y, X (1 ≦ k′ ≦ k, 1≦l′≦l) um ganzzahlige Vielfache von k′ und l′ erhöht oder vermindert, was aufeinanderfolgend zum Abtasten eines Vollbilds wiederholt wird. Dieses Verfahren wird zur Unterscheidung von dem ersten Folgeabfrageverfahren als Block-Folgeabfrageverfahren bezeichnet.

Beispiel 6 Block-Zufallsabfrageverfahren

X und Y werden nicht gemäß der vorstehenden Beschreibung des Beispiels 5 aufeinanderfolgend erhöht oder vermindert. Stattdessen werden hier und da in dem Vollbild liegende aufeinanderfolgende k′ × l′-Blöcke unter Zufallsverteilung abgerufen, wobei X und Y Versetzungen sind, die ganzzahlige Vielfache von k′ und l′ sind. Dieses Verfahren wird als Block-Zufallsabfrageverfahren bezeichnet.

Beispiel 7 Sequentielles Abfrageverfahren

Die Abfrage erfolgt sequentiell ohne Zusammenhang mit der Speicheranordnung der k × l Speicherelemente. Beispielsweise erfolgt die Abfrage durch das Verändern von X, Y um jede zweite beliebig gewählte Zahl d′, f′. Dies wird einfach als sequentielle Abfrage bezeichnet.

Beispiel 8 Zufallsbedingtes Abfrageverfahren

Falls die Speicherabfrage nicht im Falle der Zufallsabfrage gemäß Beispiel 7 oder 4 bezüglich aller Kombinationen aus X und Y ausgeführt wird, wird das Verfahren einfach als zufallsbedingte Abfrage bezeichnet.

Gemäß den vorstehenden Ausführungen können einige Abfrageverfahren in Betracht gezogen werden und es ist der Speicherzugriff an dem leseseitigen Speicher und dem schreibseitigen Speicher möglich, wobei das Abfrageverfahren für den Lesespeicher nicht unbedingt mit dem Abfrageverfahren für den Schreibspeicher übereinstimmen muß.

Wenn das leseseitige Abfrageverfahren festgelegt worden ist, werden schreibseitig die Werte X′ und Y′ durch den Inhalt der von der Prozessoreinheit 2 ausgeführten Verarbeitung bestimmt. Es kann auch zuerst das schreibseitige Abfrageverfahren festgelegt werden, wobei in diesem Fall dann das leseseitige Abfrageverfahren durch den Inhalt der von der Prozessoreinheit 2 ausgeführten Verarbeitung bestimmt ist.

Falls auch die Blockformate k × l der in dem Lesespeicher und dem Schreibspeicher abzurufenden Blöcke voneinander verschieden sind, unterscheiden sich auch die Formate der Speicherelemente- Anordnung k × l.

Die Fig. 19(a) ist ein Schaltbild, das das Konzept des Aufbaus eines Prozessorelements PE veranschaulicht. Eine logische und arithmetische Recheneinheit 12, die über eine Dateneingabeeinheit 11 Daten aus einem oder mehreren Speicherelementen sowie über einen Empfangspuffer 13 Daten aus einem oder mehreren Prozessorelementen aufnimmt, führt gemäß diesen Daten vorbestimmte logische und arithmetische Rechenvorgänge aus und gibt die Ergebnisse über eine Datenausgabeeinheit 15 an ein oder mehrere Speicherelemente ab. Die logische und arithmetische Recheneinheit 12 sendet ferner die Daten aus der Dateneingabeeinheit 11 oder die Ergebnisse der logischen und arithmetischen Rechenvorgänge über einen Sendezwischenspeicher bzw. Sendepuffer 14 zu einer oder mehreren Prozessoreinheiten.

Fig. 19(b) ist ein Blockschaltbild, gemäß dem die logische und arithmetische Recheneinheit 12 durch einen Mikroprozessor gebildet ist.

An eine interne Sammelleitung 10 sind eine Zentraleinheit (CPU) 12a, ein Festspeicher (ROM) 12b zum Speichern eines Steuerprogramms und ein Schreib/Lesespeicher (RAM) 12c als Hilfsspeicher angeschlossen, die zusammen die logische und arithmetische Recheneinheit 12 bilden. Ferner sind an die Sammelleitung 10 die Dateneingabeeinheit 11, die Datenausgabeeinheit 15, der Empfangspuffer 13 und der Sendepuffer 14 angeschlossen, die in Fig. 19(a) gezeigt sind.

Die einzelnen Prozessorelemente führen die gleiche oder jeweils eine eigene Verarbeitung und den Datenaustausch mit den anderen Prozessorelementen aus. Unter der Steuerung gemäß einem zuvor in dem jeweiligen Prozessorelement gespeicherten Steuerprogramm oder unter der Steuerung durch eine externe Steuerschaltung oder einen Verarbeitungsrechner führt die ganze, aus dieser Prozessorelementegruppe gebildete Prozessoreinheit die vorbestimmte Verarbeitung parallel aus.

Dichteumsetzung, Farbumsetzung und Maskierung von Bilddaten

Die Dichteumsetzung, die Farbumsetzung und dergleichen kann mittels eines Systems vorgenommen werden, in dem sowohl leseseitig als auch schreibseitig das erste Folgeabfrageverfahren angewandt wird. Dies wird nun ausführlich beschrieben.

Die Farbumsetzung ist eine Verarbeitung, bei der dann, wenn Bilddaten bestimmte Farbinformationen enthalten, die Farbinformationen in andere vorbestimmte Farbinformationen umgesetzt werden.

Bei einem Maskieren wird nur ein bestimmter Teil der Bilddaten unverändert ausgegeben, während der Rest der Bilddaten als Untergrund, wie beispielsweise weißer Untergrund ausgegeben wird. Als Untergrund können auch andere Daten beispielsweise für "Grau", "Farblos" oder dergleichen ausgegeben werden.

Für die Dichteumsetzung arbeitet beispielsweise ein jedes Prozessorelement 2a in der Prozessoreinheit 2 gemäß dem Ablaufdiagramm in Fig. 21. Hierbei ist ein einem Eingangswert Vin entsprechender Ausgangswert Vout (nach Fig. 20) durch folgende Gleichung bestimmt:

Vout = Vin²/64 (12)

Die Prozessoreinheit enthält 16 Prozessorelemente, von denen jedes jeweils 4 × 4 Bildelementen mit einer Länge von 8 Bit entspricht. In diese Prozessoreinheit 2 werden die der Adresse (A, B) nach Fig. 2 entsprechenden 4 × 4 Datenposten mit 8 Bit Länge eingegeben. Die Prozessorelemente 2a arbeiten parallel und geben jeweils Daten ab. Infolgedessen werden die gleichzeitig abgerufenen 4 × 4 Datenposten mit 8 Bit Länge in der Prozessoreinheit 2 gleichzeitig verarbeitet, wonach die Ergebnisse gleichzeitig ausgegeben werden. Auf diese Weise ist eine Bildverarbeitung mit hoher Geschwindigkeit ermöglicht.

Die Prozessorelemente 2a führen Verarbeitungen wie eine Dichteumsetzung, eine Farbumsetzung und ein Maskieren aus.

Gemäß der vorstehenden Beschreibung umfaßt die Dichteumsetzung das Verändern eines Eingangswerts in einen entsprechenden Ausgangswert in Übereinstimmung mit einer vorbestimmten Eingabedichte/Ausgabedichte-Wechselbeziehung und die Abgabe des Ausgangswerts. Auf diese Weise kann der Kontrast eines Bilds erhöht und dessen Helligkeit geändert werden. Die Fig. 20 veranschaulicht eine Dichteumsetzung, bei der der Rechenvorgang gemäß Gleichung (12) ausgeführt wird.

Für eine Farbumsetzung arbeitet beispielsweise ein jedes Prozessorelement 2a in der Prozessoreinheit 2 gemäß dem in Fig. 22 gezeigten Ablaufdiagramm. Hierbei wird eine Farbinformation als Kombination aus beispielsweise Rot R, Grün G und Blau B ausgedrückt, wobei für R, für G und für B der vorangehend genannte Bildspeicher vorgesehen ist und jeder Bildspeicher für das Speichern von Daten mit einer Länge von 8 Bit ausgelegt ist. Die einzelnen identischen Prozessorelemente sind entsprechenden Bildspeicherzellen für R, G und B zugeordnet. Eine Kombination aus bestimmten R-, G- und B-Werten ist im voraus als eine bestimmte Farbe gespeichert, während gleichermaßen die Farbinformation nach einer Änderung als eine Kombination aus bestimmten R-, G- und B-Werten vorgespeichert ist. Es können natürlich mehrere bestimmte Farben gespeichert sein.

Für ein Maskieren arbeitet beispielsweise jedes Prozessorelement in der Prozessoreinheit gemäß dem in Fig. 23 gezeigten Ablaufdiagramm. Hierbei betrifft das Maskieren Bitdaten in einem Speicher, der durch einen Bit-Verzeichnisspeicher gebildet ist, dessen Bits den jeweiligen Zellen des vorangehend genannten Bildspeichers entsprechen. Diese Daten zeigen an, ob sie innerhalb einer Maske liegen oder nicht. In diesem Fall ist ein einzelnes Prozessorelement gleichfalls den entsprechenden Zellen des Maskierspeichers und des Bildspeichers zugeordnet.

Falls die Gestaltung derart getroffen ist, daß eine Datenübertragung zwischen den Prozessorelementen 2a der beschriebenen Prozessoreinheit 2 ermöglicht ist, kann in der Prozessoreinheit 2 sowohl eine Raum- bzw. Ortsfrequenzfilterung als auch eine Zeichenerkennung, Komprimierung und Decodierung ausgeführt werden.

Es wird nun ein zweites Ausführungsbeispiel beschrieben, bei dem Bilddaten zum gleichzeitigen Abruf von k × l Datenposten k × l Speicherelementen zugeordnet sind. Die Fig. 16 veranschaulicht einen Zustand, der sich dann ergibt, wenn die Informationen für ein Einzelbild durch Daten ersetzt sind. Die Informationen sind horizontal in l gleiche Abschnitte und vertikal in k gleiche Abschnitte unterteilt. Zur Beschreibung der sich durch diese Unterteilung ergebenden k × l-Bereiche sind diese mit (0, 0), (0, 1), . . . (0, l), . . . (k, l) bezeichnet, wobei gemäß der Darstellung in Fig. 17 einem jeden einzelnen Bereich ein einzelnes eigenes Speicherelement 1b zugeordnet ist. D. h., die Anzahl der Speicherelemente 1b ist gleich der Anzahl der in Fig. 16 gezeigten Unterteilungen. Bei der Zuordnung der Bereiche ist jeder schattierte Teilbereich nach Fig. 16 der Adresse 0 des entsprechenden Speicherelements 1b zugeordnet, während die benachbarten Bilddaten der Adresse 1 des entsprechenden Speicherelements zugeordnet sind usw., bis alle Daten einer einzelnen Zeile in einem jeweiligen Bereich vollständig zugeordnet sind. Danach erfolgt die Zuweisung auf gleichartige Weise für die zweite Zeile von links nach rechts. Dies wird wiederholt, bis alle Bilddaten zugeordnet sind. Wenn alle Adressen identisch sind, die von dem Zeilenadressengenerator 4 und dem Spaltenadressengenerator 5 nach Fig. 4 an alle k × l Speicherelemente 1b angelegt werden, können beliebige Bilddaten gleichzeitig abgerufen werden, wie es durch die schattierten Teilbereiche in Fig. 16 dargestellt ist.

Mit dieser Anordnung ist es ermöglicht, eine bestimmte Adresse zu wählen, aus dem Bildspeicher 1 die Daten an dieser Adresse auszulesen, die Daten in der Prozessoreinheit 2 zu verarbeiten und dann die sich ergebenenden Daten ohne Änderung der Adresse in die k × l Speicherelemente 1b einzuschreiben. Falls beispielsweise jeder der Bereiche gemäß Fig. 16 aus K × L Bilddaten zusammengesetzt ist, ist es ohne Belang, wenn die Leseadresse und die Schreibadresse identisch sind, falls eine Verarbeitung zum Bewegen oder Übertragen eines Teilbereichs eines Einzelbilds um eine Versetzung ausgeführt wird, die ein ganzzahliges Vielfaches von L in horizontaler Richtung und ein ganzzahliges Vielfaches von K in vertikaler Richtung ist. Hierdurch wird die Belastung der die Adressensteuerung betreffenden Komponenten wie des Zeilenadressengenerators 4 und des Spaltenadressengenerators 5 beträchtlich vermindert.

Die Verarbeitung für das Bewegen oder Übertragen wird von der Prozessoreinheit 2 ausgeführt. Die Prozessoreinheit 2 empfängt eine Eingabe von k × l Bilddatenposten gemäß der Darstellung durch die strichlierten Teilbereiche in Fig. 16 und eine Eingabe aus Bilddaten über das ganze Einzelbild. Da die einzelnen dieser Datenposten um ein ganzzahliges Vielfaches von L und K in horizontaler bzw. vertikaler Richtung versetzt werden, werden in der Prozessoreinheit 2 die k × l Datenposten ausgetauscht bzw. bewegt und übertragen, wobei die Verarbeitung aufeinanderfolgend in der Reihenfolge von 0 an bezüglich aller Adressen der Speicherelemente ausgeführt werden kann. Infolgedessen kann das ganze Einzelbild verarbeitet werden.

Bei diesem Ausführungsbeispiel kann erwogen werden, durch Verwendung einer l × l- oder k × l-Anordnung für die k × l-Speicherzusammensetzung und durch Zuordnen einer horizontalen oder einer vertikalen Linie in einem Einzelbild zu jedem der Speicherelemente die in der Prozessoreinheit 2 ausgeführte Verarbeitung für verschiedenartige Bildverarbeitungen anzuwenden, wie für eine Histogramm- bzw. Häufigkeitsverteilungs- Aufbereitung für eine einzelne Linie eines Bilds oder für eine eindimensionale Fourier-Transformation. Darüber hinaus besteht bei dem gleichzeitigen Zugriff zu einer Vielzahl von Bildelementen keinerlei Einschränkung darauf, welche Adressen welcher Speicherelemente den Daten in einem Einzelbild zugewiesen werden.

Bilddatendrehung

Es wird nun ein Beispiel für die Anwendung einer derartigen Speicheranordnung beschrieben. Da vorstehend eine Übertragung bzw. Versetzung der Daten beschrieben wurde, wird nun eine Drehung bzw. Verschwenkung der Daten erläutert. Zur Vereinfachung sei angenommen, daß für die k × l Unterteilungen einer k × l-Speicherelementeanordnung k = l gilt, so daß sich eine l × l-Anordnung ergibt. Ferner sei für einen Bereich mit K × L Bildelementedaten angenommen, daß K = L gilt. Wenn in diesem Fall ein Einzelbild um +90° oder -90° mit der Bildmitte als Achse geschwenkt werden soll, werden von der Prozessoreinheit vier Datenposten aus den l × l Bilddatenposten vertauscht, nämlich vier voneinander um 90° versetzte Datenposten in bezug auf die Mitte geschwenkt. Wenn dies hinsichtlich des ganzen Einzelbilds wiederholt wird, wird dadurch das Einzelbild um 90° gedreht. Infolgedessen wird für das Drehen des ganzen Einzelbilds die vorstehend genannte Schwenkung l²/4- malig ausgeführt. Im Falle einer 180°-Drehung genügt es, zwei gegeneinander um 180° versetzte Datenposten in bezug auf die Mitte zu schwenken bzw. zu vertauschen. Zur Drehung des ganzen Einzelbilds um 180° erfolgt das Schwenken l²/2-malig. Auf diese Weise wird mit diesem Vorgang ein Einzelbild einer Grob-Drehung unterzogen. Tatsächlich müssen die Drehungen um +90°, -90°, +180° und dergleichen auf gleichartige Weise auch innerhalb der gleichen Bereiche ausgeführt werden.

Die Drehung innerhalb eines Einzelbilds wäre ohne die Drehung innerhalb der Bereiche unvollständig. Es wird nun die Drehung innerhalb eines Bereichs beschrieben. Dieser Vorgang umfaßt eine Verarbeitung, bei dem eine beim Auslesen eines Speicherelements geltende Adresse zu einer bei dem Einschreiben in ein Speicherelement geltenden Adresse umgesetzt wird. Die Adressenumsetzung erfolgt auf die in der nachstehenden Tabelle 1 dargestellte Weise.

Tabelle 1

Eine Schaltung für diese Verarbeitung ist in Fig. 18 ausführlich als Blockschaltbild dargestellt, gemäß dem ein Wählsignal in Abhängigkeit von dem Drehwinkel verändert wird und als Wählsteuersignal in Wähler 181, 182, 183 und 184 eingegeben wird.

Normalerweise werden bei dem Drehwinkel 0° die Ausgangssignale des Zeilenadressengenerators 4 und des Spaltenadressengenerators 5 jeweils direkt über die Wähler 181 und 183 bzw. 182 und 184 den Zeilen- und Spaltenadressen der Speicherelemente zugeführt. Wenn der Drehwinkel +90° oder -90° beträgt, werden den Spalten- und Zeilenadressen jeweils Ausgangssignale a und b der Wähler 181 bzw. 182 zugeführt.

Wenn der Drehwinkel 0° oder 180° beträgt, ergeben die Ausgangssignale a und b der Wähler 181 bzw. 182 jeweils die Zeilen- bzw. Spaltenadressen. Bei den Drehwinkeln 90° und 180° wird von dem Wähler 184 das Ausgangssignal einer Recheneinheit 186 gewählt. Bei den Drehwinkeln -90° und 180° wird von dem Wähler 184 das Ausgangssignal einer Recheneinheit 185 gewählt. In den Recheneinheiten 185 und 186 werden die eingegebenen Daten von der Länge L einer Seite einer Bereichs subtrahiert und Signale für das Ergebnis ausgegeben. Mit einer derartigen Anordnung wird die in der Tabelle 1 dargestellte Verarbeitung zur Drehung eines ganzen Einzelbilds ausgeführt.

Es wird nun der Zugriff zu den Speicherelementen für die Verarbeitung aller Bilddaten über ein ganzes Vollbild hinweg beschrieben. D. h., die folgende Beschreibung betrifft ein Abtast- bzw. Abfrageverfahren für den Zugriff zu allen Speicherdaten.

Es wurde vorstehend schon der Zugriff zu einem Speicher in dem Fall beschrieben, daß die Ortsadresse des Anfangs- bzw. Eckpunkts u von abzurufenden aneinandergrenzenden k × l-Blöcken festgelegt worden ist, nämlich Y, X festgelegt wurden, wobei Y die durch das Zählen in Aufeinanderfolge von "0" an in vertikaler Richtung von dem Eckpunkt ausgehend erhaltene Zahl ist und X die durch das Zählen in Aufeinanderfolge von "0" an in horizontaler Richtung von dem Eckpunkt ausgehend erhaltene Zahl ist. Anhand eines Beispiels wird nun beschrieben, in welcher Reihenfolge die Werte X und Y abzurufen sind, um das Vollbild zu verarbeiten.

Es wird ein Beispiel für an die Speicherelemente anzulegende Abfrageadressen erläutert. Die durch das Unterteilen eines Einzelbilds in l × l Abschnitte erhaltenen Bereiche entsprechen den jeweiligen Speicherelementen. Daher werden zum Abtasten eines Einzelbilds die gleichen Adressen an alle Speicherelemente angelegt und die Adressen aufeinanderfolgend von "0" an aufgestuft. Da die Adressen der Speicherelemente die Spalten- und Zeilenadressen sind, werden diese zuerst beide auf "0" gesetzt, wonach dann die Spaltenadresse von "0" an bis zu der letzten Adresse aufgestuft wird. Dann wird die Zeilenadresse aufgestuft, wonach dann wieder die Spaltenadresse von "0" an bis zu der letzten Adresse aufgestuft wird. Dies wird für den Zugriff zu allen Speicherelementen wiederholt.

Die Blockdatenwählschaltung 1604 ist gemäß Fig. 24 durch Wähler gebildet, deren Anzahl gleich der Anzahl der Blöcke, nämlich bei diesem Ausführungsbeispiel 64 ist. Ein jeder Wähler entspricht einem jeweiligen Block des ausgangsseitigen Speichers. Ein Wähler, der einem nachstehend als Block (i, j) bezeichneten Block in der i-ten Zeile und j-ten Spalte des ausgangsseitigen Speichers entspricht, empfängt Daten aus vier Blöcken (i, j), (m - j + 1, i), (m - j + 1, m - j + 1) und (j, m - j + 1) des eingangsseitigen Speichers. Hierbei bedeutet m, daß der eingangsseitige Speicher und der ausgangsseitige Speicher beide aus m × m Blöcken bestehen. Dieses Ausführungsbeispiel wird unter der Annahme beschrieben, daß m = 8 gilt. Ferner gilt 1 ≦ i ≦ m und 1 ≦ j ≦ m.

Wenn das ursprüngliche Bild um 0° entgegen dem Uhrzeigersinn gedreht werden soll, steuert die Steuerschaltung 1607 die Blockdatenwählschaltung 1604 in der Weise, daß jeder Wähler (i, j) abgibt. Auf gleichartige Weise steuert die Steuerschaltung 1607 die Blockdatenwählschaltung 1604 derart, daß für eine Drehung um 90° entgegen dem Uhrzeigersinn (j, m - j + 1) gewählt wird, für eine Drehung um 180° entgegen dem Uhrzeigersinn (m - j + 1, m - j + 1) gewählt wird und für eine Drehung um 270° entgegen dem Uhrzeigersinn (m - j + 1, i) gewählt wird.

Die Steuerschaltung 1607 steuert die Innenblockadressen der Adressenausgabeschaltungen bzw. Adressengeneratoren 1605 und 1606. Wenn ein Block n × n Bildelemente enthält und eine Ausgabe an ein Bildelement an einer Stelle (k, l) in diesem Block erfolgen soll, wird für die Ausgabe bei einer Drehung des ursprünglichen Bilds um 0° entgegen dem Uhrzeigersinn die Innenblockadresse für den eingangsseitigen Block auf (k, l) gesteuert. Auf gleichartige Weise wird die Adresse für eine Drehung um 90° auf (l, n-k + 1), für eine Drehung um 180° auf (n - k + 1, n - l + 1) und für eine Drehung um 270° auf (n - l + 1, k) gesteuert. Bei dem beschriebenen Ausführungsbeispiel gilt n = 4. Dies kann beispielsweise dadurch erfolgen, daß als Schaltung 1605 eine Nachschlagetabelle gemäß Fig. 25 und als Schaltung 1606 ein Aufwärtszähler gemäß Fig. 26 verwendet wird. Umgekehrt ist es natürlich auch möglich, den Zähler nach Fig. 26 als Schaltung 1605 und die Nachschlagetabelle nach Fig. 25 als Schaltung 1606 zu verwenden.

Bei dem vorstehend beschriebenen Ausführungsbeispiel werden mehrere Posten von Bilddaten an der Drehung entsprechenden Stellen gleichzeitig aufgenommen, wodurch eine schnelle Verarbeitung möglich wird und die Drehung des Bilds mittels einer klein ausgelegten Schaltung bewerkstelligt werden kann.

Nachstehend wird nun ein Ausführungsbeispiel ergänzend beschrieben.

Wenn die den k × l Speicherelementen zugeordneten Adressen in der Aufeinanderfolge von der Adresse 0 bis zu einer Endadresse auf die vorstehend beschriebene Weise abgerufen werden, werden aus den jeweiligen k × l Speicherelementen die Bilddaten aus jedem der Bereiche ausgegeben, die jeweils 1/(k × l) des Vollbilds entsprechen. Betrachtet man nur ein einziges Bildelement, so wird das Bild eines einem einzelnen Bereich entsprechenden Teilbereichs aufeinanderfolgend in horizontaler und vertikaler Richtung abgefragt und ausgelesen. Falls dies bei der herkömmlichen Verarbeitung eines Bilds angewandt wird, das aufeinanderfolgend über ein Einzelbild hinweg horizontal und vertikal abgetastet wird, kann eine Verarbeitungsgeschwindigkeit erreicht werden, die k × l-mal so groß wie die herkömmliche ist. Da darüber hinaus der behandelte Bildbereich kleiner wird, werden auch die Zeilenpuffer und dergleichen kleiner. Infolgedessen kann die Prozessoreinheit 2 auf einfache Weise als Matrixprozessor aufgebaut sein. Dies wird nachstehend ausführlich beschrieben.

Ortsfrequenzfilterung

Gemäß den vorangehenden Ausführungen werden die Bilddaten aus den k × l Speicherelementen 1b aufeinanderfolgend in die Prozessoreinheit 2 eingegeben, die während des aufeinanderfolgenden Abfragens für das Auslesen des Speichers die Raum- bzw. Ortsfrequenzfilterung ausführt. Obgleich dies erst nachfolgend beschrieben wird, enthält die Prozessoreinheit 2 Puffer für eine Vielzahl von horizontalen Linien mit einer Kapazität für einen rechteckigen Bereich, in welchem einzelne Prozessorelemente, die die Bestandteile der Prozessoreinheit sind, jeweils einem einzelnen der durch die Unterteilung gebildeten k × l Bereiche entsprechen. Nach der zweidimensionalen Raum- bzw. Ortsfrequenzfilterung werden die sich ergebenden Daten ausgangsseitig aufeinanderfolgend durch einen Abruf eingeschrieben, der mit dem eingangsseitigen Abruf zum Lesen identisch ist.

Claims

1. Bildverarbeitungseinrichtung mit einem Bildspeicher mit einer Vielzahl von Speicherelementen, die voneinander unabhängig adressierbar und abrufbar sind, und einer Prozessoreinheit mit einer Vielzahl von Prozessorelementen zum gleichzeitigen Verarbeiten von Daten mehrerer Bildelemente in einem durch eine Speicherzugriffseinrichtung abgerufenen Bereich des Bildspeichers, dadurch gekennzeichnet, daß den Bildelementdaten eines jeweiligen Bildspeicherbereichs aus mehreren Bildspeicherbereichen, die durch Unterteilung des Bildspeichers in eine Vielzahl von Bereichen erhalten sind, eine übereinstimmende Adresse zugeordnet ist und Bildelementdaten an übereinstimmenden Stellen in den Bildspeicherbereichen einem jeweils übereinstimmenden Speicherelement zugeordnet sind, und daß zur Auslesung der Daten eines gewünschten Bildfelds (S) die Adreßdaten der das gewünschte Bildfeld jeweils partiell oder vollständig enthaltenden Bildspeicherbereiche, sowie zusätzliche Adreßdaten, die die Lage der Bildpunkte des gewünschten Bildfelds in einem jeweiligen Bildspeicherbereich angeben, ausgelesen und zur Adressierung des Bildspeichers zusammengefaßt werden.

2. Bildverarbeitungseinrichtung nach Anspruch 1, dadurch gekennzeichnet, daß jedes der Prozessorelemente eine Dichte- Umsetzeinrichtung zum Umsetzen der Dichte der Bildelementdaten aufweist, wobei die Prozessoreinheit eine Dichteumsetzung des Bildes durchführt.

3. Bildverarbeitungseinrichtung nach einem der vohergehenden Ansprüche, dadurch gekennzeichnet, daß jedes der Prozessorelemente eine Bestimmungseinrichtung zum Bestimmen der Farbe der Bildelementdaten, und eine Farbumsetzeinrichtung zum Umsetzen von Bildelementdaten in eine vorbestimmte Farbe, wenn durch die Bestimmungseinrichtung entschieden wird, daß die Bildelementdaten eine bestimmte Farbe darstellen, aufweisen, wobei die Prozessoreinheit eine Farbumsetzung des Bildes durchführt.

4. Bildverarbeitungseinrichtung nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß die Prozessoreinheit eine Verschiebung des gewünschten Bildfelds durchführt.

5. Bildverarbeitungseinrichtung nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß die Bildspeicherbereiche durch eine virtuelle zweidimensionale Aufteilung des Bildspeichers erhalten werden.