DE69127802T2

DE69127802T2 - Schaltung zur Etikettierung für Bildverarbeitung

Info

Publication number: DE69127802T2
Application number: DE69127802T
Authority: DE
Inventors: Ryutaro Kawai; Toshimi Kobayashi
Original assignee: Kawasaki Steel Corp
Current assignee: Kawasaki Steel Microelectronics Inc Chiba Jp
Priority date: 1990-12-28
Filing date: 1991-12-27
Publication date: 1998-01-29
Anticipated expiration: 2011-12-28
Also published as: EP0492633A2; EP0492633B1; US5305393A; EP0492633A3; DE69127802D1

Description

Die Erfindung betrifft eine Bildverarbeitungs-Etikettierschaltung, die während des Abtastens von Schwarz- Weiß-Bildern in einem Teilbereich in Abtastrichtung mit einer besonderen Maske hauptsächlich die Verbundenheit eines betrachteten Pixeis mit den Pixeln erkennt, die das betrachtete Pixel innerhalb der Maske umgeben, und nacheinander einen Etikettenwert bestimmt und jedem Pixel zuweist. Die Erfindung betrifft insbesondere eine Bildverarbeitungs-Etikettierschaltung, die die Verarbeitungsgeschwindigkeit erhöhen und die Speicherkapazität des Arbeitsspeichers verringern kann.
In den letzten Jahren hat die Zunahme der Verarbeitungskapazität digitaler Verarbeitungseinrichtungen, beispielsweise von Mikroprozessoren (im weiteren mit MPU bezeichnet) und ähnlichen Einrichtungen, zu Automatisierungen in verschiedenen Bereichen geführt. Zur Automatisierung nutzt man diese digitalen Verarbeitungseinrichtungen.
Beispielsweise haben fortgeschrittene Bildverarbeitungsverfahren, wenn man sie auf die Teileuntersuchung in Fabriken oder auf Blutkörperchenuntersuchungen und Zelldiagnosen im medizinischen Bereich anwendet, zum automatischen Zählen der Teileanzahl in einem Teilbereich des Bilds geführt, wobei die Teile ein Teil des untersuchten Objekts sind, oder zum automatischen Zählen von Blutkörperchen und Zellen.
Um die Objekte in einem festgelegten Bild zu zählen, müssen z. B. im Bild enthaltene Bereiche mit Schwarz-Weiß- Teilbildern erkannt werden. Um dies zu erreichen, bestimmt man die Verbundenheit eines jeden Bildelements im Bild. Für jeden Bereich, der beispielsweise dem Wert Schwarz entspricht, wird eine Etikettierverarbeitung ausgeführt.
Die Bildverarbeitungsetikettierung, die jeden Bereich in einem festgelegten Bild etikettiert, ermöglicht es, für jeden etikettierten Bereich die Fläche, die Umfangslänge und das Moment M und den Winkel e der Hauptachse zu bestimmen.
Ganz allgemein umfaßt die Verarbeitung in einer Bildverarbeitungs-Etikettierschaltung, die jeden Bereich in einem festgelegten Bild im Rasterabtastformat etikettiert, die folgenden drei Schritte:
A. Temporäres Etikettieren. (Erzeugen der temporär etiket tierten Bilddaten und der temporären Etikettentabellendaten, die die Umsetzbeziehungen zum Abändern der temporären Etiketten angeben.)
B. Anordnen der Etikettentabelle.
C. Endgültiges Etikettieren. (Erzeugen der endgültig etikettierten Bilddaten)
Eine Anzahl derartiger Bildverarbeitungs-Etikettiertechniken sind offenbart worden.
Beispielsweise offenbart die veröffentlichte japanische Patentschrift 77687/1987 eine Technik, mit der Bilddaten, etwa temporär etikettierte Bilddaten, in einer Bildverarbeitungs-Etikettierschaltung zusammengesetzt sind aus den Koordinatendaten des Startpunkts der verbundenen Pixel, die mit ein und dem gleichen Etikett zu versehen sind, den Koordinatendaten des Endpunkts der verbundenen Pixel und aus Identifikationsdaten, die den Etikettenwert der verbundenen Pixel enthalten.
Gemäß der Technik, die in der veröffentlichten japanischen Patentschrift 77687/1987 offengelegt ist, kann die Speicherkapazität des Arbeitsspeichers in der Bildverarbeitungs-Etikettierschaltung verkleinert werden.
Ferner offenbart die veröffentlichte japanische Patentschrift 29880/1990 eine Technik, die die Verbesserung der temporären Etikettierverarbeitung betrifft (die Verbesserung des temporären Etikettieralgorithmus), wobei die temporäre Etikettierverarbeitung auf jedes Pixel in einem Fenster angewendet wird, das aus fünf Pixeln besteht. Gemäß der veröffentlichten japanischen Patentschrift 29880/1990 wird ein Teilbereich abgetastet, der eine Anzahl Bilder enthält, die innerhalb des Teilbereichs jeweils unabhängig voneinander sind, und zwar mit einem Fenster, das aus {(1 x 3) + (1 x 2)} 5 Pixeln besteht. Eine Bildverarbeitungs-Etikettierschaltung führt die temporäre Etikettierung gemäß einer Anzahl klassifizierter Fenstermuster durch und greift dabei auf eine Verbindungsbeziehungstabelle zu.
Die in der veröffentlichten japanischen Patentschrift 29880/1990 offengelegte Technik ermöglicht es, die Anzahl der Speicherschreib- und Speicherlesezugriffe auf die Verbindungsbeziehungstabelle zu verringern. Dabei werden die Speicherschreib- und Speicherlesezugriffe jedesmal ausgeführt, wenn ein Pixel eingegeben wird und jedes Pixel während des Etikettierens eines jeden Bereichs in einem festgelegten Bild im Rasterabtastformat etikettiert wird.
Weiterhin offenbart die veröffentlichte japanische Patentschrift 48778/1990 eine Etikettiertechnik, in der eine gewöhnliche Schwarz-Weiß-Maske verwendet wird, die aus einem betrachteten Pixel und zum betrachteten Pixel benachbarten Pixeln besteht. Das Etikettieren wird ausgeführt, während Gültigkeitsprüfungen durchgeführt werden. Dabei wird der Schwarz-Weiß-Maskenstatus des Folgenetiketts verglichen, der die Etiketten darstellt, die an benachbarte Folgen vergeben wurden. Existieren eine Anzahl benachbarter Folgen, so wird im anfänglichen Etikettenauswahl-Steuerabschnitt der Schwarz-Weiß-Status des verbundenen Etiketts verglichen, das das neueste Etikett unter den benachbarten Folgenetiketten ist. D. h., gemäß dieser Technik wird etikettiert, während Gültigkeitsprüfungen durchgeführt werden, zu denen nicht nur die Pixel in der Maske verwendet werden, die aus dem betrachteten Pixel und benachbarten Pixeln des betrachteten Pixels besteht, sondern auch Etiketten von Pixeln außerhalb der Maske.
Gemäß der veröffentlichten japanischen Patentschrift 48778/1990 ist es während des anfänglichen Etikettierens in der Bildverarbeitungs-Etikettierschaltung möglich, einen Überlauf der Anfangsetiketten während der Verarbeitung zu verhindern. Der Überlauf entsteht durch eine beträchtliche Zunahme in der Anzahl der Anfangsetiketten (Typen). Weiterhin kann verhindert werden, daß die Last des Integrierverarbeitungsteils zunimmt. Die Aufgabe des Integrierverarbeitungsteils besteht darin, die Anfangsetiketten gegenseitig zu konsolidieren.
Die veröffentlichte japanische Patentschrift 9478/1987 offenbart eine Technik, die es erlaubt, die Anzahl der Zugriffe auf den Arbeitsspeicher zu verkleinern. Hierzu wird eine Maske aus m x n Pixeln verwendet und eine MAX-MIN-Format-Etikettenbezugstabelle im Etikettierprozessor, der das Etikettieren eines jeden Bereichs in einem festgelegten Bild im Rasterabtastformat ausführt.
In der MAX-MIN-Format-Etikettenbezugstabelle sind die Tabellenadressen Umsetzquellen-Etikettenwerte, und die Tabellendaten sind Umsetzziel-Etikettenwerte. Es werden nur Tabellendaten, deren Wert kleiner ist als der Wert der ent sprechenden Tabellenadresse, in den Speicher einer jeden Tabellenadresse geschrieben.
In der veröffentlichten japanischen Patentschrift 9478/1987 ist auch ein Etikettenabtrenn-Erfassungsabschnitt bereitgestellt. Dieser Etikettenabtrenn-Erfassungsabschnitt setzt ein Abtrennerfassungsflag, wenn erkannt wird, daß an einer Verbindung, an der zwei verbundene Pixel mit unterschiedlichen Etikettenwerten aufeinandertreffen, die MAX- und MIN-Werte der MAX-MIN-Format-Etikettenbezugstabelle nicht gleich sind. Ist das Abtrennerfassungsflag gesetzt, so verhindert die Wiederholung der Tabellenumsetzung der Etikettenbezugstabelle, daß ein und das gleiche Objekt durch teilweise unterschiedliche Etikettierungen getrennt wird.
Obgleich die veröffentlichte japanische Patentschrift 77687/1987 die Möglichkeit liefert, verglichen mit herkömmlichen Bildverarbeitungs-Etikettierschaltungen die Speicherkapazität des Arbeitsspeichers in einer Bildverarbeitungs- Etikettierschaltung zu verringern, tritt die Schwierigkeit auf, daß für jedes verbundene Pixel, dem ein und dasselbe Etikett zugewiesen wird, drei Datentypen gespeichert werden müssen, nämlich die Koordinatendaten des Startpunkts der verbundenen Pixel, die Koordinatendaten des Endpunkts der verbundenen Pixel und ein Identifizierer, der den Etikettenwert der verbundenen Pixel enthält.
Beträgt beispielsweise die Pixelanzahl je Teilbereich 30 x 10 = 300, so sind zumindest 5 Bit erforderlich, um die Koordinaten des Startpunkts und des Endpunkts (der größte Koordinatenwert ist 30) der verbundenen Pixel auszudrücken, denen ein und dasselbe Etikett zugewiesen wird. Ist der Speicher, der den Etikettenwert des verbundenen Pixels speichert, ein 8-Bit-Speicher, so ist ein Speicherelement von insgesamt 18 Bit für jedes verbundene Pixel erforderlich, dem ein und dasselbe Etikett zugewiesen wird.
Man darf annehmen, daß in der veröffentlichten japanischen Patentschrift 29880/1990 das Speichern der Etikettie rung für jedes Pixel auch für jedes Pixel ausgeführt wird. Dies hat den Nachteil, daß ein außerordentlich großer Arbeitsspeicher erforderlich ist. Wird z. B. ein Etikettenwert in einem 8-Bit-Speicherelement abgelegt und beträgt die Pixelanzahl in einem Teilbereich 30 x 10 = 300, so ist ein Arbeitsspeicher von insgesamt 2400 Bit erforderlich, um die Etikettenwerte eines jeden Pixels im Teilbereich zu speichern.
In der veröffentlichten japanischen Patentschrift 48778/1990 wird etikettiert, während die Gültigkeit der Etikettierung für das betrachtete Pixel durch Vergleichen geprüft wird, und zwar durch Vergleichen - während des Etikettierens des betrachteten Pixeis - des Schwarz-Weiß-Maskenstatus des Folgenetiketts, das die Etiketten darstellt, die den benachbarten Folgen in der Umgebung des betrachteten Pixeis zugewiesen wurden. Sind eine Anzahl benachbarter Folgen vorhanden, so wird das verbundene Etikett betrachtet, das das neueste Etikett unter den benachbarten Folgenetiketten ist. Die Etikettierschaltung ist daher besonders kompliziert aufgebaut, wodurch die Verarbeitungsgeschwindigkeit sinkt. Außerdem darf man annehmen, daß es außerordentlich schwierig ist, die korrekte Funktion dieser Etikettierschaltung nachzuweisen.
Weiterhin kann man vermuten, daß in der veröffentlichten japanischen Patentschrift 9478/1987 das Speichern der Etikettenwerte eines jeden Pixels für jedes Pixel ausgeführt wird. Daher tritt, wie bei der veröffentlichten japanischen Patentschrift 29880/1990, die Schwierigkeit auf, daß die Speicherkapazität des Arbeitsspeichers in der Bildverarbeitungs-Etikettierschaltung leicht sehr groß wird.
In der veröffentlichten japanischen Patentschrift 29880/1990 und in der veröffentlichten japanischen Patentschrift 9478/1987 tritt auch das Problem auf, daß - siehe Fig. 19 - viele temporäre Etikettenwerte auftreten, wenn jedes Pixel in dem Abschnitt tabelliert wird, den die geneigten Linien in Fig. 18 bezeichnen, obwohl der Abschnitt einen Bereich darstellt, dem man ein und dasselbe Etikett zuweisen sollte. Dies kommt dadurch zustande, daß nur die temporären Etikettenwerte in dem Fenster, das aus fünf Pixeln besteht und das temporäre Etikett zuweist, als Bedingung zum Bestimmen des Etikettenwerts (temporären Etikettenwerts) des betrachteten Pixels verwendet werden.
Während des temporären Etikettierens eines jeden Bereichs des in Fig. 21 gezeigten Bilds treten drei Verbindungsstellen auf, die mit J1 - J3 bezeichnet sind. Dadurch entsteht eine temporäre Etikettierung, in der viele temporäre Etiketten verwendet werden, siehe Fig. 21. Zudem sind die Daten in der MAX-MIN-Format-Etikettenbezugstabelle zu diesem Zeitpunkt so beschaffen, daß der Etikettenwert 6 in den Etikettenwert 5 umgesetzt werden sollte, der Etikettenwert 4 in den Etikettenwert 2, der Etikettenwert 3 in den Etikettenwert 2 und der Etikettenwert 2 in den Etikettenwert 1. Um eine derartige Etikettentabellenanordnung zu vervollständigen, d. h. beispielsweise, um alle Etikettenwerte 4, 3 und 2 in den Etikettenwert 1 umzusetzen und damit die Anordnung der Etikettentabelle abzuschließen, sind mindestens zwei Tabellenumsetzungen erforderlich, die eine lange Verarbeitungs zeit erfordern.
Die Erfindung wurde ausgeführt, um die beschriebenen Schwierigkeiten zu überwinden, und sie zielt darauf ab, die Verarbeitungsgeschwindigkeit dadurch zu verbessern, daß die Anzahl der Speicherzugriffe gesenkt wird, und darauf, die Speicherkapazität des Arbeitsspeichers in einer Bildverarbeitungs-Etikettierschaltung und einem Etikettierprozessor zu verkleinern, der im Zuge des Abtastens von Schwarz-Weiß- Bildern in einem Teilbereich in Rasterabtastrichtung mit einer besonderen Maske hauptsächlich die Verbundenheit eines betrachteten Pixels mit den Pixeln erkennt, die das betrachtete Pixel innerhalb der Maske umgeben, und der nacheinander einen Etikettenwert für jedes Pixel bestimmt und zuweist.
Erfindungsgemäß wird eine Bildverarbeitungs-Etikettierschaltung nach Anspruch 1 bereitgestellt.
In einer Ausführungsform der Erfindung kann die Bildverarbeitungs-Etikettierschaltung so angeordnet sein, daß temporär etikettierte Bilddaten, die die temporäre Etikettenerzeugungsvorrichtung erzeugt, eine Umsetzung zum Abändern der Etikettenwerte erfahren, so daß die Etikettenwerte nur in fallender Reihenfolge der Etikettenwerte geändert werden.
Die Etikettierschaltung kann ferner umfassen:
eine temporäre Etikettentabelle, deren Adressen temporäre Etikettenwerte sind, und deren Daten temporäre Umsetz ziel-Etikettenwerte sind, und in der die temporären Etikettentabellendaten gespeichert sind;
eine endgültige Etikettentabelle, deren Adressen temporäre Etikettenwerte sind, und deren Daten die endgültigen Etikettenwerte sind;
eine Leseschaltung für die temporären Etikettentabellendaten, die nacheinander die Daten liest, die die temporären Umsetzziel-Etikettenwerte sind, und zwar in aufsteigender Adreßreihenfolge; und
eine Schreibschaltung für die endgültigen Etikettentabellendaten, die die gelesenen Daten mit den gelesenen Adreßwerten vergleicht, sodann ermittelt, ob eine Umsetzung der temporären Etikettenwerte entsprechend der Leseadresse erforderlich ist oder nicht, einen endgültigen Etikettenwert bestimmt, der ein neuer endgültiger Etikettenwert ist, und den endgültigen Etikettenwert an einer Adresse in die endgültige Etikettentabelle schreibt, die der Leseadresse gleich ist, wenn sich zeigt, daß eine Umsetzung nicht nötig ist, und die, wenn sich zeigt, daß eine Umsetzung erforderlich ist, Daten an einer Adresse aus der endgültigen Etikettentabelle liest, die dem Wert der Daten gleich ist, die aus der temporären Etikettentabelle gelesen wurden, und die Daten an einer Adresse in die endgültige Etikettentabelle schreibt, die der Adresse gleich ist, an der aus der temporären Etikettentabelle gelesen wurde, wobei die Etikettierschaltung die Daten der endgültigen Etikettentabelle gemäß der definiert festgelegten Daten der temporären Etikettentabelle erzeugt und schreibt und dabei der Erzeugung der temporär etikettierten Bilddaten für einen Teilbereich folgt.
Eine Ausführungsform der Erfindung kann auch eine Schreibschaltung für die endgültigen Etikettentabellendaten enthalten, die während der Umsetzung in die endgültige Etikettentabelle den Wert des Zählers für die endgültigen Etiketten schreibt, der endgültige Etiketten mit aufeinander folgenden endgültigen Etikettenwerten erzeugt, und zwar in die endgültige Etikettentabelle an einer Adresse, die der Adresse gleich ist, an der aus der temporären Etikettentabelle gelesen wurde, wenn sich zeigt, daß keine Umsetzung erforderlich ist.
In einer weiteren Ausführungsform der Erfindung sind die temporär etikettierten Bilddaten aus temporären Etikettendaten und Längendaten ausgebaut, die die Daten der Pixelanzahl in den verbundenen Pixeln entsprechend der temporären Etikettendaten sind.
In der Schaltung, die die temporär etikettierten Bilddaten und die temporären Etikettentabellendaten erzeugt, wobei letztere die Umsetzbeziehung für die Änderung der temporären Etiketten angibt (die Schaltung wird im weiteren als Erzeugungsschaltung für temporär etikettierte Bilddaten bezeichnet), wird eine Maske mit beispielsweise {(1 x 3) + (1 x 2)} 5 Pixeln zum Bestimmen des anfänglichen Etikettenwerts des betrachteten Pixeis verwendet. Sind die nacheinander betrachteten Pixel verbundene Pixel, so zählt ein Lauflängenzähler die Pixelanzahl in den verbundenen Pixeln.
Damit können, auch wenn in einer der beschriebenen Verbindungen die Etikettenwerte der verbundenen Pixel zu ändern sind, die Etikettenwerte der Anzahl Pixel einfach dadurch auf ein Mal aktualisiert werden, daß die Daten des Anfangsetikettenspeichers neu geschrieben werden.
Da das Aktualisieren mit den temporären Anfangsetiketten ausgeführt wird, die noch nicht definiert festgelegt sind, verhindert man, daß die Anzahl unterschiedlicher temporärer Etiketten unnötig anwächst.
Zusätzlich sind in einer Ausführungsform der Erfindung die temporär etikettierten Bilddaten für die verbundenen Pixel nur Daten, die den temporären Etikettenwert und die Lauflänge enthalten, so daß die Datenmenge verglichen mit der Datenmenge herkömmlicher Verfahren verringert werden kann.
Sind in einem Teilbereich z. B. 30 x 10 = 300 (der größtmögliche Lauflängenwert ist 30) Pixel enthalten, d. h., sind die Lauflängendaten 5-Bit-Daten und die Etikettenwertdaten 8-Bit-Daten, so reichen 13 Bit aus, um die Daten eines jeden waagrecht verbundenen Pixels aufzunehmen, dem ein und dasselbe Etikett zugewiesen wird. Verglichen mit der her kömmlichen Technik, die in der veröffentlichten japanischen Patentschrift 77687/1987 offengelegt ist, kann damit der erforderliche Speicher (von 18 auf 13 Bit) verkleinert werden.
Eine Ausführungsform der Erfindung stellt auch die Möglichkeit bereit, die Verarbeitungsgeschwindigkeit der Etikettentabellenanordnung der temporären Etikettentabelle zu verbessern, in der die Umsetzbeziehung für das Abändern der temporären Etiketten gespeichert ist. Die Umsetzbeziehung ist so gestaltet, daß die Daten eine Umsetzung bezüglich der Änderung der Etikettenwerte erfahren, so daß die Etikettenwerte nur in fallender Reihenfolge der Etikettenwerte modifiziert werden.
Der Erfinder hat festgestellt, daß es während der Anordnung der Etikettentabelle möglich ist, die temporären Etikettentabellendaten zu erzeugen, die in der temporären Etikettentabelle gespeichert sind und deren Adressen die temporären Etikettenwerte sind und deren Daten temporäre Umsetzziel-Etikettenwerte sind, so daß die temporären Etikettentabellendaten Daten sind, die eine Umsetzung zum Abän dem der Etikettenwerte durchlaufen können, so daß die Etikettenwerte nur in fallender Reihenfolge der Etikettenwerte modifiziert werden. Der Erfinder hat also festgestellt, daß es sowohl mit herkömmlichen Techniken als auch mit der erfindungsgemäßen Technik möglich ist, die temporäre Etikettentabelle im MAX-MIN-Format zu erzeugen.
Zum Anordnen einer derartigen Etikettentabelle im MAX- MIN-Format wird zunächst die Lesevorrichtung für die temporären Etikettentabellendaten verwendet, die nacheinander die Daten in aufsteigender Reihenfolge der Adressen liest, wobei die Daten die temporären Umsetzziel-Etikettenwerte der temporären Etikettentabelle sind (die Vorrichtung wird im weiteren einfach mit Lesevorrichtung für die temporären Etikettentabellendaten bezeichnet).
In einer Ausführungsform der Erfindung wird eine Schreibvorrichtung für die endgültigen Etikettentabellendaten verwendet, die die gelesenen Daten mit den gelesenen Adreßwerten vergleicht, sodann ermittelt, ob eine Umsetzung der temporären Etikettenwerte entsprechend der Leseadresse erforderlich ist oder nicht, und, wenn sich zeigt, daß eine Umsetzung nicht nötig ist, einen endgültigen Etikettenwert bestimmt, der ein neuer endgültiger Etikettenwert ist, und den endgültigen Etikettenwert an einer Adresse in die endgültige Etikettentabelle schreibt, die der gelesenen Adresse gleich ist, und die, wenn sich zeigt, daß eine Umsetzung erforderlich ist, Daten an einer Adresse aus der endgültigen Etikettentabelle liest, die dem Wert der Daten gleich ist, die aus der temporären Etikettentabelle gelesen wurden, und die Daten an einer Adresse in die endgültige Etikettentabelle schreibt, die der Adresse gleich ist, an der aus der temporären Etikettentabelle gelesen wurde (die Vorrichtung wird im weiteren einfach als Schreibvorrichtung für die endgültigen Etikettentabellendaten bezeichnet).
Der Erfinder hat also erkannt, daß, wenn während der Etikettentabellenanordnung der temporären Etikettentabelle, die die temporären Etikettentabellendaten speichert, die möglicherweise umgesetzt werden, um die Etikettenwerte zu ändern, so daß die Etikettenwerte nur in der Reihenfolge abnehmender Etikettenwerte verändert werden, die Etikettentabellenanordnung nacheinander in zunehmender Reihenfolge der Adressen ausgeführt wird. Die Umsetzbeziehung für die temporären Umsetzziel-Etikettenwerte liegt dann bereits definiert fest, auch wenn eine Umsetzung nötig ist, weil sich die aus der temporären Etikettentabelle gelesenen Daten und die Adresse unterscheiden, an der die Daten gelesen wurden.
Der Erfinder hat dementsprechend herausgefunden, daß die Änderung eines jeden Datums der temporären Etikettentabelle mit insgesamt höchstens zwei Lesevorgängen aus der temporären Etikettentabelle oder der endgültigen Etikettentabelle ausführbar ist und mit höchstem einem Schreibvorgang in die endgültige Etikettentabelle, wenn die Etikettentabellenanordnung der temporären Etikettentabelle ausgeführt wird.
Die beschriebene erfindungsgemäße Schreibvorrichtung für die endgültigen Etikettentabellendaten ist nicht auf die konkrete Zusammenstellung beschränkt, die bestimmt, ob eine Umsetzung des temporären Etikettenwerts gemäß der Adresse, an der der temporäre Etikettenwert gelesen wurde, erforderlich ist oder nicht, und, falls keine Umsetzung nötig ist, den endgültigen Etikettenwert bestimmt, der ein neuer endgültiger Etikettenwert ist, und den endgültigen Etikettenwert an einer Adresse in die endgültige Etikettentabelle schreibt, die gleich der Adresse ist, an der aus der temporären Etikettentabelle gelesen wurde.
Ist beispielsweise eine Umsetzung nicht erforderlich, so können die aus der temporären Etikettentabelle gelesenen Daten als endgültige Etikettenwerte, die neue endgültige Etiketten sind, in die endgültige Etikettentabelle geschrieben werden (die Adresse der endgültigen Etikettentabelle ist gleich der Adresse der temporären Etikettentabelle, an der die Daten gelesen wurden).
Ist beispielsweise eine Umsetzung nicht erforderlich, so kann der Wert des endgültigen Etikettenzählers, der die endgültigen Etiketten mit aufeinander folgenden Etikettenwerten erzeugt, während der Umsetzung in die endgültige Etikettentabelle geschrieben werden, und zwar in die endgültige Etikettentabelle an einer Adresse, die gleich der Adresse ist, an der aus der temporären Etikettentabelle gelesen wurde.
Der Etikettenzähler für die endgültigen Etiketten wird jedesmal inkrementiert (Addition einer "1"), wenn ein neues endgültiges Etikett ausgegeben wird.
Wird ein derartiger Etikettenzähler für die endgültigen Etiketten verwendet, so sind die endgültigen Etikettenwerte, die in die endgültige Etikettentabelle geschrieben werden, aufeinander folgende Werte, d. h., es wird kein Wert ausgelassen, so daß der größte Wert der ausgegebenen endgültigen Etikettenwerte klein gehalten werden kann. Damit ist es möglich, die Bitlänge der Speichereinrichtung für die endgültigen Etikettenwerte der endgültigen Etikettentabelle klein zu halten. Die Hardwarekosten können damit sinken.
Der Erfinder hat auch festgestellt, daß die Lesevorrichtung für die temporären Etikettentabellendaten und die Schreibvorrichtung für die endgültigen Etikettentabellendaten teilweise gleichzeitig arbeiten können (Pipelineverarbeitung). Dadurch steigt nicht nur die Verarbeitungsgeschwindigkeit der Etikettentabellenanordnung, sondern es wird auch eine festliegende Verarbeitungszeit zum Ausführen der gesamten Etikettentabellenanordnung bereitgestellt, da, falls eine Umsetzung erforderlich ist, beispielsweise das Lesen von Daten aus der endgültigen Etikettentabelle und das Lesen von Daten aus der temporären Etikettentabelle für die folgende Etikettentabellenanordnung gleichzeitig ausführbar sind.
In einer weiteren Ausführungsform sind die temporäre Etikettierschaltung und die endgültige Etikettierschaltung unabhängige Schaltungen in der Etikettierschaltung, so daß eine Parallelverarbeitung möglich ist. Damit ist eine Echtzeitverarbeitung der Etikettierung (Videogeschwindigkeit) möglich.
Die temporär etikettierten Bilddaten, die das Ausgangssignal der Erzeugungsschaltung für temporär etikettierte Bilddaten darstellen, sind eine Zusammenstellung aus temporären Bilddaten und Lauflängendaten. Letztere sind die Daten der Anzahl Pixel in den verbundenen Pixeln, und die Daten entsprechen den temporären Etikettendaten. Eine derartige Zusammenstellung der temporär etikettierten Bilddaten aus temporären Etikettendaten und Lauflängendaten ermöglicht es, die Speicherkapazität des Arbeitsspeichers zu verkleinern, der die temporär etikettierten Bilddaten speichert.
Voneinander unabhängig arbeiten können auch die Erzeugungsschaltung für temporär etikettierte Bilddaten, die den Anfangsetikettenspeicher und den Lauflängenzähler der erfindungsgemäßen Bildverarbeitungs-Etikettierschaltung enthält, und die Erzeugungsschaltung für endgültig etikettierte Bilddaten, die die Etikettentabellenanordnung der temporären Etikettentabelle der erfindungsgemäßen Bildverarbeitungs- Etikettierschaltung ausführt. Es ist beispielsweise möglich, die Etikettentabellenanordnung auszuführen und dann definiert endgültig etikettierte Bilddaten zu erzeugen, wobei die Technik verwendet wird, die in der veröffentlichten japanischen Patentschrift 9478/1987 offenbart ist, und zwar aus den temporär etikettierten Bilddaten, die die erfindungsgemäße Erzeugungsschaltung für temporär etikettierte Bilddaten ausgibt und aus den temporären Etikettentabellendaten, die die Umsetzbeziehung zum Abändern der temporären Etiketten angeben. In diesem Fall muß die Erzeugungsschaltung für temporär etikettierte Bilddaten mit einer Etikettenabtrenn-Erkennungsabschnitt versehen sein, und das Abtrennerkennnungsflag muß wie gefordert eingestellt sein.
In einer Bildverarbeitungs-Etikettierschaltung, die nacheinander für jedes Pixel einen Etikettenwert bestimmt und ihn im Zuge des Abtastens von Schwarz-Weiß-Bildern zuweist, die in einem Teilbereich enthalten sind, und zwar mit einer besonderen Maske in Rasterabtastrichtung, ist es durch den Gebrauch der Erfindung möglich, hervorragende Ergebnisse zu erhalten, beispielsweise eine verbesserte Verarbeitungsgeschwindigkeit durch Vermindern der Speicherzugriffsanzahl und eine kleinere Speicherkapazität des Arbeitsspeichers.
Die bevorzugten Ausführungsformen werden nun ausführlich mit Bezug auf die beiliegenden Zeichnungen beschrieben, wobei in allen Abbildungen gleiche Elemente mit gleichen Be zugszeichen bezeichnet sind.
Es zeigt:
Fig. 1 ein Blockdiagramm mit einer Modellzeichnung der erfindungsgemäßen Etikettierschaltung;
Fig. 2 ein erstes Flußdiagramm mit einem Teil der Verarbeitung in der erfindungsgemäßen Etikettierschaltung;
Fig. 3 ein zweites Flußdiagramm mit einem Teil der Verarbeitung in der erfindungsgemäßen Etikettierschaltung;
Fig. 4 ein drittes Flußdiagramm mit einem Teil der Verarbeitung in der erfindungsgemäßen Etikettierschaltung;
Fig. 5 ein viertes Flußdiagramm mit einem Teil der Verarbeitung in der erfindungsgemäßen Etikettierschaltung;
Fig. 6 ein fünftes Flußdiagramm mit einem Teil der Ver arbeitung in der erfindungsgemäßen Etikettierschaltung;
Fig. 7 eine erste Darstellung mit dem Zusammenhang zwischen dem Status des Maskenspeichers und dem Verarbeitungsgeschehen in der erfindungsgemäßen Etikettierschaltung;
Fig. 8 eine zweite Darstellung mit dem Zusammenhang zwischen dem Status des Maskenspeichers und dem Verarbeitungsgeschehen in der erfindungsgemäßen Etikettierschaltung;
Fig. 9 ein Blockdiagramm einer Erzeugungsvorrichtung für temporär etikettierte Bilddaten einschließlich der Erzeugungsschaltung für temporär etikettierte Bilddaten einer Ausführungsform der Erfindung mit ihren Zusatzschaltungen;
Fig. 10 ein Blockdiagramm einer weiteren Ausführungsform der Erfindung;
Fig. 11 eine Abfolgedarstellung der Anordnung nach Fig. 10;
Fig. 12 eine weitere Abfolgedarstellung der Anordnung nach Fig. 10;
Fig. 13 ein Flußdiagramm, das die Verarbeitung der endgültigen Etikettentabelle nach Fig. 10 erläutert;
Fig. 14 eine Darstellung der endgültigen Etikettenta belle, die durch die Verarbeitung gemäß Fig. 11 bis 13 entstanden ist;
Fig. 15 ein Blockdiagramm einer Ausführungsform der Erfindung;
Fig. 16 ein Blockdiagramm mit einer Erzeugungsschaltung für endgültig etikettierte Bilddaten;
Fig. 17 ein Flußdiagramm, das die Verarbeitung in der Erzeugungsschaltung für endgültig etikettierte Bilddaten darstellt;
Fig. 18 eine Zeichnung mit einem ersten Beispielbild, das in die Bildverarbeitungs-Etikettierschaltung eingegeben wird;
Fig. 19 eine Zeichnung mit einem Bild, dem mit einer herkömmlichen Bildverarbeitungs-Etikettierschaltung temporäre Etiketten zugewiesen wurden;
Fig. 20 eine Zeichnung mit einem Bild, dem mit Hilfe der Erfindung temporäre Etiketten zugewiesen wurden;
Fig. 21 eine Zeichnung mit einem Bild, dem mit einer herkömmlichen Bildverarbeitungs-Etikettierschaltung temporäre Etiketten zugewiesen wurden;
Fig. 22 eine Zeichnung mit einem ersten Beispielbild, dem mit Hilfe der erfindungsgemäßen Bildverarbeitungs-Etikettierschaltung temporäre Etiketten zugewiesen wurden; und
Fig. 23 eine Zeichnung mit einem zweiten Beispielbild, dem mit Hilfe der erfindungsgemäßen Bildverarbeitungs-Etikettierschaltung temporäre Etiketten zugewiesen wurden.
Im folgenden werden Ausführungsformen der Erfindung mit Bezug auf die Zeichnungen beschrieben.
Fig. 1 zeigt ein Blockdiagramm mit einer Modellzeich nung der Erfindung.
In Fig. 1 gibt eine Erzeugungsschaltung 20 für temporär etikettierte Bilddaten die temporär etikettierten Bilddaten eines betrachteten Pixels 10 aus und auch die temporären Etikettentabellendaten, die sich auf die Umsetzbeziehung der temporären Etiketten beziehen.
Ein Maskenspeicher 12a der Erzeugungsschaltung 20 für temporär etikettierte Bilddaten speichert die Bilddaten des betrachteten Pixels 10 und der Pixel, die das betrachtete Pixel 10 umgeben. D. h., der Maskenspeicher 12a besteht aus einem zweiwertigen Speicher P1 für das betrachtete Pixel, einem zweiwertigen Speicher P2 für das Pixel links vom betrachteten Pixel, einem Etikettenwertspeicher H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels, einem Etikettenwertspeicher H1 für das Pixel über dem betrachteten Pixel und einem Etikettenwertspeicher H2 für das Pixel an der oberen linken Seite des betrachteten Pixel. Dabei speichert der zweiwertige Speicher P1 das zweiwertige Bild des betrachteten Pixels, der zweiwertige Speicher P2 spei chert das zweiwertige Bild des Pixels links neben dem betrachteten Pixel 10, und die Etikettenwertspeicher H0, H1 und H2 speichern jeweils die Etikettenwerte der Pixel an der oberen rechten Seite, an der oberen Seite und an der oberen linken Seite des betrachteten Pixels.
In den zweiwertigen Speichern P1 und P2 sind die Daten "0" oder "1" gespeichert. In den Etikettenwertspeichern H0, H1 H2 sind 10-Bit-Daten gespeichert, nämlich Daten von "0" bis 2 hoch zehn - 1.
Jeder Speicher des Maskenspeichers 12a entspricht dem betrachteten Pixel 10 und der Maske 12. Im Zuge des Abtastens des betrachteten Pixels 10 und der Maske 12 werden Daten in jeden Speicher gelesen und die Daten eines jeden Speichers verschoben.
Wird ein Pixel abgetastet, das einem Pixel der Maske 12 entspricht, so werden die Daten des zweiwertigen Speichers Pl in den zweiwertigen Speicher P2 geschoben, und die Daten, die dem betrachteten Pixel 10 entsprechen, werden in den zweiwertigen Speicher P1 geschrieben. Ist das betrachtete Pixel 10 weiß, so wird "0" in den zweiwertigen Speicher P1 geschrieben. Ist das betrachtete Pixel 10 schwarz, so wird "1" in den zweiwertigen Speicher P1 geschrieben.
Zudem werden während des Abtastens der Maske 12 die Daten des Etikettenwertspeichers H1 in den Etikettenwertspeicher H2 geschrieben, die Daten des Etikettenwertspeichers H0 werden in den Etikettenwertspeicher H1 geschrieben, und der Etikettenwert der temporär etikettierten Bilddaten des ent sprechenden Pixels, die bereits die temporär etikettierten Bilddaten sind, werden aus einem Pufferspeicher in den Etikettenwertspeicher H0 geschrieben.
Die Etikettenwerte des betrachteten Pixels 10 und der Pixel, die mit dem betrachteten Pixel 10 verbunden sind, werden in einem Anfangsetikettenspeicher ZL gespeichert. Die im Anfangsetikettenspeicher ZL gespeicherten Etikettenwerte sind zu Anfangsetiketten erklärt und noch keine definiert festgelegten temporären Etikettenwerte. Ein Lauflängenzähler RUN zählt die Pixelanzahl des betrachteten Pixeis 10 und der damit verbundenen Pixel.
Während des Abtastens der Maske 12 verwendet eine Erzeugungsvorrichtung 22 für temporäre Etiketten den Masken-25 speicher 12a, den Anfangsetikettenspeicher ZL und den Lauflängenzähler RUN, um die temporär etikettierten Bilddaten des entsprechenden Pixeis und die temporären Etikettentabellendaten zu erzeugen, die die Umsetzbeziehung zum Abändern der temporären Etiketten angeben.
Fig. 2 bis Fig. 6 zeigen Flußdiagramme mit den Einzelheiten der Erzeugungsschaltung 20 für temporär etikettierte Bilddaten, die in der Erfindung verwendet wird.
Die Verarbeitung, die die Erzeugungsschaltung 20 für temporär etikettierte Bilddaten ausführt, wird im weiteren mit Bezug auf die Flußdiagramme beschrieben.
Im Schritt 204 werden vor dem Beginn der Verarbeitung eines Bilds Variablen initialisiert.
Die Zahl ZL bezeichnet einen Anfangsetikettenspeicher. Die Zahl ZLC bezeichnet einen Zählspeicher für temporäre Etiketten, in dem der größte Wert + 1 der temporären Etiketten gespeichert ist, die bereits ordnungsgemäß ausgegeben wurden.
Weiterhin bezeichnet die Zahl NL ein Entscheidungsflag für ein neues Etikett. Beginnt ein neu verbundenes Pixel am momentan betrachteten Pixel, wird "1" in das Flag geschrieben.
Die Zahl CREG bezeichnet einen Speicher, der die Anzahl waagrechter Pixel enthält, und die Zahl CCNT bezeichnet einen waagrechten Pixelzählspeicher
Die Zahl RUN bezeichnet einen Lauflängenzähler, und die Zahl HRUN bezeichnet einen Hilfslauflängenzähler.
Die Zahl HZL bezeichnet einen temporären Etikettenspei cher der vorhergehenden Zeile.
Die Zahlen H0 - H2 bezeichnen Etikettenwertspeicher der vorhergehenden Zeile. Die Zahlen P1 - P2 bezeichnen zweiwertige Speicher. H0 - H2 und P1 - P2 entsprechen jedem der Pixel des Maskenspeichers in Fig. 1.
Die Zahl LCHNG bezeichnet ein Zeilenvorschubflag.
Nach dem Schritt 204 werden im Schritt 205 in Fig. 2 der Speicher CREG, der die Anzahl der waagrechten Pixel enthält, und der Zählspeicher CCNT für die waagrechten Pixel verglichen.
Ist der Zählspeicher CCNT für die waagrechten Pixel größer oder gleich dem Speicher CREG, der die Anzahl der waagrechten Pixel enthält, so wird das Zeilenvorschubflag LCHNG im Schritt 206 gesetzt. D. h., in das Zeilenvorschubflag LCHNG wird "1" geschrieben, und anschließend erfolgt ein Sprung zu (3) im Flußdiagramm in Fig. 5.
Ist dagegen der Zählspeicher CCNT für die waagrechten Pixel kleiner als der Speicher CREG, der die Anzahl der waagrechten Pixel enthält, so wird der Zählspeicher CCNT für die waagrechten Pixel im Schritt 207 inkrementiert (Addition einer "1"), das Zeilenvorschubflag LCHNG wird im Schritt 208 gelöscht (eine "0" eingetragen) und anschließend wird die Verarbeitung ab dem Schritt 210 fortgesetzt.
In den Schritten 210 - 214 werden die Etikettenwerte in den Etikettenwertspeichern H0 - H2 der vorhergehenden Zeile gemäß dem Abtasten des betrachteten Pixels 10 und der Maske 12 geschoben.
Im Schritt 216 wird der Wert des Hilfslauflängenzählers HRUN dekrementiert (Subtraktion einer "1").
Im Schritt 220 wird entschieden, ob der Hilfslauflängenzähler HRUN den Wert "1" hat oder nicht.
Hat der Hilfslauflängenzähler HRUN den Wert "1", so werden im Schritt 224 die Werte für einen Anfangsetikettenspeicher FRZL der vorhergehenden Zeile und für den Hilfslauflängenzähler HRUN von außerhalb der Erzeugungsschaltung 20 für temporär etikettierte Bilddaten gelesen.
Die Zahlen FIFO_ZL und FIFO_RUN in Fig. 2 bezeichnen einen temporären Etikettenpufferspeicher bzw. einen Lauflängenpufferspeicher. Beide Speicher bilden einen Pufferspeicher (entsprechend dem später beschriebenen Pufferspeicher 60) und sind FIFO-Speicher (first-in first-out).
Im Schritt 225 wird ein temporärer Etikettenwert aus der temporären Etikettentabelle ZT gelesen, und zwar an einer Adresse, die gleich dem Wert des Anfangsetikettenspeichers FRZL der vorhergehenden Zeile ist, der im Schritt 224 ausgelesen wurde. Der temporäre Etikettenwert wird in den temporären Etikettenspeicher HZL der vorhergehenden Zeile geschrieben.
Hat das Zeilenvorschubfiag LCHNG im Schritt 226 nicht den Wert "0", dann wird der Wert des temporären Etikettenspeichers HZL der vorhergehenden Zeile im Schritt 227 in den Etikettenwertspeicher H1 der vorhergehenden Zeile geschrieben.
Nach der Bearbeitung des Schritts 226 oder des Schritts 227 geht die Verarbeitung zum Schritt 228 in Fig. 3 über.
Hat dagegen im Schritt 220 der Hilfslauflängenzähler HRUN nicht den Wert "1", dann geht die Verarbeitung zum Schritt 228 in Fig. 3 über.
Im Schritt 228 in Fig. 3 wird eine "0" in einen 3-Pixel-Statusspeicher CASEH für die vorhergehende Zeile geschrieben.
Anschließend werden in den Schritten 230 - 239 die Datenwerte für den 3-Pixel-Statusspeicher CASEH für die vorhergehende Zeile bestimmt und geschrieben, und zwar abhängig davon, ob jeder Etikettenwert der Pixel an der rechten oberen Seite, an der oberen Seite und an der oberen linken Seite des betrachteten Pixels "0" ist oder nicht.
D. h., in den Schritten 230 und 232 bekommt das Bit, dessen Stelle einen zwei Stellen höheren Wert hat als die Stelle des LSB (LSB = Least Significant it, niedrigstwertiges Bit) des 3-Pixel-Statusspeichers CASEH für die vorherge hende Zeile den Wert "1", wenn der Etikettenwertspeicher H2 für das Pixel an der oberen linken Seite des betrachteten Pixels nicht "0" ist.
In den Schritten 234 und 236 wird "1" in das Bit ge schrieben, dessen Stelle einen um eine Stelle höheren Wert hat als die Stelle des LSB des 3-Pixel-Statusspeichers CASEH für die vorhergehende Zeile, wenn der Etikettenwertspeicher H1 für das Pixel über dem betrachteten Pixel nicht "0" ist.
In den Schritten 238 und 239 wird "1" in das LSB des 3- Pixel-Statusspeichers GASEH für die vorhergehende Zeile geschrieben, wenn der Etikettenwertspeicher H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels nicht "0" ist.
Im Schritt 240 werden die Bitdaten des zweiwertigen Speichers Pl zum zweiwertigen Speicher P2 geschoben. Im Schritt 244 werden Bitdaten von außerhalb der Erzeugungsschaltung 20 für temporär etikettierte Bilddaten in den zweiwertigen Speicher P1 gelesen.
Der Wert der Bitdaten, die in den zweiwertigen Speicher P1 gelesen wurden, entspricht der Farbe, d. h. Schwarz oder Weiß, des betrachteten Pixels 10 in Fig. 1.
Im Schritt 246 werden gemäß den Werten ("0" oder "1") der aktualisierten zweiwertigen Speicher P1 und P2 Daten in einen 2-Pixel-Statusspeicher CASEP für die vorhergehende Zeile geschrieben. Hat der zweiwertige Speicher P1 für das betrachtete Pixel den Wert "1", so wird "1" in das LSB des 2-Pixel-Statusspeichers CASEP für die vorhergehende Zeile geschrieben. Hat der zweiwertige Speicher P2 für das Pixel links des betrachteten Pixels den Wert "1", dann wird "1" in das Bit geschrieben, dessen Stelle eine Stelle höher ist als die Stelle des LSB des 2-Pixel-Statusspeichers CASEP für die vorhergehende Zeile.
In den Schritten 250 bis 254 wird abhängig vom Wert des 2-Pixel-Statusspeichers CASEP für die vorhergehende Zeile entschieden, ob die Verarbeitung gemäß dem Flußdiagramm in Fig. 4, die Verarbeitung gemäß dem Flußdiagramm in Fig. 5, die Verarbeitung gemäß dem Flußdiagramm in Fig. 6 oder die Verarbeitung gemäß dem nächsten Schritt 258 auszuführen ist.
Hat der 2-Pixel-Statusspeicher CASEP für die vorherge hende Zeile den Wert "3", so wird zu (2) im Flußdiagramm nach Fig. 4 gesprungen. Nach der Verarbeitung gemäß dem Flußdiagramm in Fig. 4 wird zu (5) im Flußdiagramm nach Fig. 2 gesprungen.
Hat der 2-Pixel-Statusspeicher CASEP für die vorhergehende Zeile den Wert "2", so wird zu (3) im Flußdiagramm nach Fig. 5 gesprungen. Nach der Verarbeitung gemäß dem Flußdiagramm in Fig. 5 wird zu (5) im Flußdiagramm nach Fig. 2 gesprungen.
Hat der 2-Pixel-Statusspeicher CASEP für die vorhergehende Zeile den Wert "1", so wird zu (4) im Flußdiagramm nach Fig. 6 gesprungen. Nach der Verarbeitung gemäß dem Flußdiagramm in Fig. 6 wird zu (5) im Flußdiagramm nach Fig. 2 gesprungen.
Hat der 2-Pixel-Statusspeicher CASEP für die vorhergehende Zeile weder den Wert "3" noch den Wert "2" noch den Wert "1", sondern den Wert "0", so wird der Lauflängenzähler RUN im Schritt 258 inkrementiert (Addition einer "1"). Anschließend wird zu (5) im Flußdiagramm nach Fig. 2 gesprungen.
Im folgenden wird mit Bezug auf das Flußdiagramm in Fig. 4 die Verarbeitung beschrieben, die erfolgt, wenn im Schritt 250 der 2-Pixel-Statusspeicher CASEP für die vorhergehende Zeile den Wert "3" hat.
Die Verarbeitung gemäß dem Flußdiagramm in Fig. 4 wird ausgeführt, wenn der zweiwertige Speicher Pl für das be trachtete Pixel den Wert "1" hat und der zweiwertige Speicher P2 für das Pixel links des betrachteten Pixels den Wert "1" hat, also wenn die verbundenen Pixel in der aktuellen Zeile und der Maske weiterhin verbunden sind.
Ist in den Schritten 260 und 264 der Wert des 3-Pixel- Statusspeichers CASEH für die vorhergehende Zeile "1" oder "5", so geht die Verarbeitung zum Schritt 268 über. In anderen Fällen geht die Verarbeitung zum Schritt 277.
Hat in den Schritten 260 und 264 das LSB des 3-Pixel- Statusspeichers CASEH für die vorhergehende Zeile den Wert "1" und ist das nächste niedrigstwertige Bit "0", d. h., ist der Etikettenwertspeicher H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels nicht "0" und der Eti kettenwertspeicher H1 für das Pixel über dem betrachteten Pixel "0", so wird zu Schritt 268 gesprungen. Sonst wird zu Schritt 277 gesprungen.
Im Schritt 268 wird ein Vergleich ausgeführt, um zu prüfen, ob der Anfangsetikettenspeicher ZL den Wert "0" hat. Ist der Wert "0", so geht die Verarbeitung zum Schritt 275 über. Ist der Wert nicht "0", so geht die Verarbeitung zum Schritt 270 über.
Im Schritt 270 werden der Wert des Anfangsetikettenspeichers ZL und der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels verglichen.
Sind der Wert des Anfangsetikettenspeichers ZL und der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels gleich, so geht die Verarbeitung nach dem Schritt 270 zum Schritt 277 über.
Ist im Schritt 270 der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixeis größer als der Wert des Anfangsetikettenspeichers ZL, so wird der kleinere Wert, d. h. der Wert des Anfangsetikettenspeichers ZL genommen. Da der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels im Schritt 272 geändert werden muß, wird der Wert des Anfangsetikettenspeichers ZL in die temporäre Etikettentabelle ZT geschrieben, und zwar an einer Adresse, die gleich dem Wert des Etikettenwertspeichers H0 tür das Pixel an der oberen rechten Seite des betrachteten Pixels ist.
Ist dagegen der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels kleiner als der Wert des Anfangsetikettenspeichers ZL, so geht die Verarbeitung zum Schritt 274 über. Im Schritt 274 wird der kleinere Wert, d. h. der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels genommen und anschließend im Schritt 275 in den Anfangsetikettenspeicher ZL geschrieben.
Somit werden zum Aktualisieren der Etikettenwerte der temporären Etikettentabelle ZT die kleineren Etikettenwerte genommen.
Demgemäß ist der Wert der temporären Etikettentabellendaten, die in die temporäre Etikettentabelle ZT geschrieben werden und der die Umsetzbeziehung für die Änderung der tem porären Etiketten anzeigt, kleiner als der Wert der Adresse, an die die Daten geschrieben werden. Damit ist die Umsetzung der temporären Etiketten gemäß der temporären Etikettentabelle ZT eine Umsetzung zur Änderung nur in Richtung fallender Etikettenwerte. D. h., die temporäre Etikettentabelle ZT hat ein MAX - MIN-Format.
Nach Abschluß der Verarbeitung in Schritt 272 oder 275 wird der Schritt 276 ausgeführt. Anschließend geht die Verarbeitung zum Schritt 277 über.
Im Schritt 276 wird das Entscheidungsfiag NL für ein neues Etikett gelöscht (d. h., es wird "0" in NL geschrieben).
Im Schritt 277 wird der Lauflängenzähler RUN inkrementiert. Anschließend wird zu (5) im Flußdiagramm in Fig. 2 gesprungen.
Im folgenden wird die Verarbeitung mit Bezug auf das Flußdiagramm in Fig. 5 beschrieben, die erfolgt, wenn der 2- Pixel-Statusspeicher CASEP für die vorhergehende Zeile im Schritt 252 in Fig. 3 den Wert "2" hat.
Die im Flußdiagramm nach Fig. 5 dargestellte Verarbeitung wird ausgeführt, falls der zweiwertige Speicher P1 für das betrachtete Pixel den Wert "0" hat und der zweiwertige Speicher P2 für das Pixel links des betrachteten Pixeis den Wert "1" hat.
Die im Flußdiagramm nach Fig. 5 dargestellte Verarbeitung wird also ausgeführt, wenn die verbundenen Pixel in der aktuellen Zeile und in der Maske die Verbindung verlieren.
Im Schritt 280 nach Fig. 5 wird entschieden, ob das Entscheidungsflag NL für ein neues Etikett den Wert "0" hat oder nicht.
Hat das Entscheidungsflag NL für ein neues Etikett nicht den Wert "0", so werden die Schritte 282 und 286 abgearbeitet. Hat dagegen das Entscheidungsflag NL für ein neues Etikett den Wert "0", so wird der Schritt 290 ausgeführt.
Der Etikettenwert für die verbundenen Pixel in der aktuellen Zeile und der Maske wird im Anfangsetikettenspeicher ZL gespeichert. Der größte Wert der gültigen temporären Etiketten, die bereits ausgegeben wurden, wird im temporären Etikettenzählspeicher ZLC gespeichert.
Ist im Schritt 280 das Entscheidungsflag NL für ein neues Etikett nicht "0", so wird der Wert des temporären Etikettenzählspeichers ZLC in den Anfangsetikettenspeicher ZL geschrieben, da dem verbundenen Etikett, das innerhalb der Maske die Verbindung verloren hat, ein neues Etikett zuzuweisen ist. Nach dem Inkrementieren des Werts des temporären Etikettenzählspeichers ZLC im Schritt 284 wird im Schritt 286 eine "0" in das Entscheidungsflag NL für ein neues Etikett geschrieben.
Verliert das verbundene Pixel seine Verbindung, so wird der Schritt 290 im Flußdiagramm in Fig. 5 ausgeführt. Der Wert des Anfangsetikettenspeichers ZL und der Wert des Lauflängenzählers RUN, die beide Daten des verbundenen Pixels sind, das seine Verbindung verloren hat, werden an den temporären Etikettenpufferspeicher FIFO_ZL und den Lauflängenpufferspeicher FIFO_RUN ausgegeben, die außerhalb der Erzeugungsschaltung 20 für temporär etikettierte Bilddaten liegen.
Der Pufferspeicher, der aus dem temporären Etikettenpufferspeicher FIFO_ZL und dem Lauflängenpufferspeicher FI- FO_RUN aufgebaut ist, ist ein FIFO-Speicher (first-in first out).
Die temporär etikettierten Bilddaten, die die Erzeugungsschaltung 20 für temporär etikettierte Bilddaten ausgibt, die die Verarbeitung in den Flußdiagrammen nach Fig. 2 bis Fig. 6 ausführt, bestehen aus den beschriebenen Werten des Anfangsetikettenspeichers ZL und des Lauflängenzählers RUN. Die Ausgabe ist ein Schreibvorgang der temporär etikettierten Bilddaten in den Pufferspeicher.
Demgemäß lesen Schaltungen, die die temporär etikettierten Bilddaten verwenden, die temporär etikettierten Bilddaten, die aus dem Etikettenwert und der Lauflänge bestehen, aus dem Pufferspeicher.
Im Schritt 294 in Fig. 5 wird eine "1" in den Lauflängenzähler RUN geschrieben. Ebenso wird im Schritt 296 eine "0" in den Anfangsetikettenspeicher ZL geschrieben.
Im Schritt 297 wird entschieden, ob das Zeilenvorschubflag LCHNG "0" ist oder nicht.
Nach dem Abschluß der beschriebenen Verarbeitung im Flußdiagramm nach Fig. 5 wird zu (5) im Flußdiagramm in Fig. 2 gesprungen, falls das Zeilenvorschubflag LCHNG "0" ist.
Hat das Zeilenvorschubflag LCHNG nicht den Wert "0", so wird zu (6) im Flußdiagramm nach Fig. 2 gesprungen.
Im folgenden wird mit Bezug auf das Flußdiagramm in Fig. 6 die Verarbeitung beschrieben, die ausgeführt wird, wenn der 2-Pixel-Statusspeicher CASEP für die vorhergehende Zeile im Schritt 254 im Flußdiagramm in Fig. 3 den Wert "1" hat.
Die im Flußdiagramm nach Fig. 6 dargestellte Verarbeitung wird ausgeführt, wenn der zweiwertige Speicher P1 für das betrachtete Pixel "1" ist und der zweiwertige Speicher P2 für das Pixel. links des betrachteten Pixels den Wert "0" hat. D. h., die Verarbeitung wird ausgeführt, wenn die Verbundenheit der Pixel in der aktuellen Zeile und der Maske beginnt.
Der Beginn verbundener Pixel ist als das Ende des Zustands definiert, in dem keine Pixel vorhanden sind, nämlich als das Ende der fortgesetzten Anwesenheit von Pixeln mit dem Etikettenwert "0".
Damit ist bei Beginn der Verarbeitung im Flußdiagramm nach Fig. 6 der Wert des Anfangsetikettenspeichers ZL "0".
Im Schritt 300 im Flußdiagramm in Fig. 6 wird der Wert des Anfangsetikettenspeichers ZL, d. h. "0", in den temporären Etikettenpufferspeicher FIFO_ZL geschrieben, und der Wert des Lauflängenzählers RUN wird in den Lauflängenpufferspeicher FIFO_RUN geschrieben.
Im Schritt 304 wird eine "1" in den Lauflängenzähler RUN geschrieben.
Ist der Wert des 3-Pixel-Statusspeichers CASEH für die vorhergehende Zeile im Schritt 310 "0", d. h., sind die drei Etikettenwertspeicher H0 - H2 alle "0", so wird im Schritt 312 eine "1" in das Entscheidungsfiag NL für ein neues Etikett geschrieben. Anschließend wird zu (5) im Flußdiagramm in Fig. 2 gesprungen.
Hat der 3-Pixel-Statusspeicher CASEH für die vorherge hende Zeile im Schritt 314 den Wert "2", oder hat der 3-Pixel-Statusspeicher CASEH für die vorhergehende Zeile im Schritt 316 den Wert "6", so wird der Schritt 318 ausge führt. Ist der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels "0" und der Wert des Etikettenwertspeichers H1 für das Pixel über dem betrachteten Pixel nicht "0", so wird der Wert des etikettenwertspeichers Hl für das Pixel über dem betrachteten Pixel im Schritt 318 in den Anfangsetikettenspeicher ZL geschrieben. Nach dem Schritt 318 wird zu (5) im Flußdiagramm in Fig. 2 gesprungen.
Hat der 3-Pixel-Statusspeicher CASEH für die vorhergehende Zeile im Schritt 320 den Wert "4", so wird der Schritt 322 ausgeführt. Ist der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels "0" und der Wert des Etikettenwertspeichers Hl für das Pixel über dem betrachteten Pixel "0" und der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixels nicht "0", so wird der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixeis im Schritt 322 in den Anfangsetikettenspeicher ZL geschrieben. Anschließend wird zu (5) im Flußdiagramm in Fig. 2 gesprungen.
Hat der 3-Pixel-Statusspeicher CASEH für die vorhergehende Zeile im Schritt 330 den Wert "5", so wird der Schritt 336 ausgeführt. Ist der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixeis nicht "0" und der Wert des Etikettenwertspeichers H1 für das Pixel über dem betrachteten Pixel "0" und der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixeis nicht "0", so wird der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels und der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixeis im Schritt 336 verglichen.
Wird der Schritt 336 ausgeführt, so können die nicht verbundenen Pixel an der oberen rechten Seite und der oberen linken Seite des betrachteten Pixels über das betrachtete Pixel zu neu verbundenen Pixeln werden. Demgemäß können der Etikettenwert (temporärer Etikettenwert) des Pixeis an der oberen rechten Seite des betrachteten Pixels und der Etikettenwert (temporärer Etikettenwert) des Pixels an der oberen linken Seite des betrachteten Pixels unterschiedlich sein. Da das betrachtete Pixel jedoch die beiden Pixel verbindet, gleicht die Verarbeitung in den Schritten 336 bis 348 die beiden temporären Etikettenwerte der Pixel an der oberen rechten Seite und der oberen linken Seite des betrachteten Pixels aneinander an.
Im Schritt 336 wird bestimmt, ob der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels oder der Wert des Etikettenwertspeichers H2 für das Pixel an der linken Seite des betrachteten Pixels kleiner ist.
Ist der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixeis kleiner, so wird im Schritt 346 der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels in die temporäre Etikettentabelle ZT geschrieben, und zwar an einer Adresse, die gleich dem Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixeis ist. Anschließend wird der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels im Schritt 348 in die temporäre Etikettentabelle ZT geschrieben.
Ist dagegen im Schritt 336 der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixeis kleiner, so wird im Schritt 340 der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixels in die temporäre Eti kettentabelle ZT geschrieben, und zwar an einer Adresse, die gleich dem Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels ist. Anschließend wird der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixeis im Schritt 344 in den Anfangsetikettenspeicher ZL geschrieben.
Sind im Schritt 336 der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixeis und der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixels gleich, so geht die Verarbeitung zum Schritt 344, ohne die anfängliche Etikettentabelle ZT zu aktualisieren. Da der Wert des Etikettenwertspeichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixeis und der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixels gleich sind, macht es keinen Unterschied, wenn anstelle des Schritts 344 zum Schritt 348 gegangen wird.
Nach der Verarbeitung im Schritt 348 oder im Schritt 344 wird zu (5) im Flußdiagramm nach Fig. 2 gesprungen.
Hat der 3-Pixel-Statusspeicher CASEH für die vorhergehende Zeile im Schritt 330 nicht den Wert "5", so fährt die Verarbeitung mit dem Schritt 332 fort.
Hat der 3-Pixel-Statusspeicher CASEH für die vorhergehende Zeile den Wert "1" oder "3" oder "7", d. h. sind der Wert des Etikettenwertspeichers H1 für das Pixel über dem betrachteten Pixel und der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixels beide "0" oder ist nur der Wert des Etikettenwertspeichers H2 für das Pixel an der oberen linken Seite des betrachteten Pixels "0", so wird der Wert des Etikettenwert speichers H0 für das Pixel an der oberen rechten Seite des betrachteten Pixels im Schritt 332 in den temporären Etikettenspeicher ZL geschrieben.
Der Grund dafür liegt darin, daß beim Ausführen des Schritts 332 das betrachtete Pixel, dasgerade anfängt, verbunden zu sein, sich mit dem Pixel an der oberen rechten Seite des betrachteten Pixels verbindet, so daß der Etiket tenwert des betrachteten Pixels gleich dem temporären Etikettenwert des Pixels an der oberen rechten Seite des betrachteten Pixels ist.
Nach dem Schritt 332 wird zu (5) im Flußdiagramm in Fig. 2 gesprungen.
Die Darstellungen in Fig. 7 und Fig. 8 fassen das Verarbeitungsgeschehen in den Flußdiagrammen von Fig. 2 bis Fig. 6 zusammen, wobei das Verarbeitungsgeschehen auf den Maskenspeicherzustand bezogen ist.
Wie beschrieben ist es erfindungsgemäß möglich, eine Erzeugungsschaltung für temporär etikettierte Bilddaten wirkungsvoll aufzubauen, wobei der Anfangsetikettenspeicher und der Lauflängenzähler verwendet werden, die eine geringe Arbeitsspeicherkapazität aufweisen.
Die Erfindung ist auch dazu verwendbar, siehe Fig. 20, ein etikettiertes Bild mit nur einem Etikettenwert zu erhalten, nämlich "1" für das Bild in Fig. 18, und zwar auch in der temporären Etikettierphase vor der endgültigen Etikettierphase, in der die temporären Etikettenwerte integriert werden. Damit ist es möglich, nicht nur den Umfang der nachfolgenden Verarbeitung zu verkleinern, die erforderlich ist, um die temporär etikettierten Bilddaten in endgültig etikettierte Bilddaten umzusetzen, sondern auch die Speicherkapazität der temporären Etikettentabelle, die die Umsetzbeziehung für die Abänderung der temporären Etiketten angibt.
Wie das gemäß dieser Ausführungsform temporär etiket tierte Bild in Fig. 22 zeigt, ermöglicht es die Erfindung verglichen mit der herkömmlichen temporären Etikettierung des Bilds nach Fig. 21, die Anzahl (Typen) der temporären Etiketten zu verringern.
Fig. 9 zeigt ein Blockdiagramm mit einer Erzeugungsvorrichtung für temporär etikettierte Bilddaten einschließlich der Erzeugungsschaltung für temporär etikettierte Bilddaten gemäß einer Ausführungsform der Erfindung und ihrer Zusatzschaltungen.
Die Hauptkomponenten der Erzeugungsvorrichtung für temporär etikettierte Bilddaten 30 in Fig. 9 sind die Erzeugungsschaltung 20 für temporär etikettierte Bilddaten gemäß der ersten Ausführungsform, die Puffer Ba und Bb, eine temporäre Etikettentabelle ZT, ein Lauflängeninverter 62 und ein Schalter 72.
Der Puffer Ba wird beim Zugriffsvorgang auf die temporären Etikettentabellendaten verwendet, die die Erzeu gungsschaltung 20 für temporär etikettierte Bilddaten in die temporäre Etikettentabelle ZT ausgibt.
Der Puffer Bb wird beim Zugriffsvorgang auf die temporär etikettierten Bilddaten verwendet, die die Erzeugungs schaltung 20 für. temporär etikettierte Bilddaten in den Lauflangeninverter 62 und den Schalter 72 ausgibt.
Die temporäre Etikettentabelle ZT ist identisch mit der Tabelle, die im weiteren mit Bezug auf Fig. 10 beschrieben wird.
Der Lauflängeninverter 62 erzeugt temporär etikettierte Bilddaten, d. h. das temporäre Etikett für jedes Pixel, aus den temporär etikettierten Bilddaten, die aus dem temporären Etikett und der Lauflänge bestehen. Der Puffer Bb gibt die temporär etikettierten Bilddaten aus.
Der Schalter 72 wählt das Ausgangssignal der Erzeugungsvorrichtung für temporär etikettierte Bilddaten 30 aus dem Ausgangssignal des Puffers Bb, dem Ausgangssignal des Lauflangeninverters 62 und dem Ausgangssignal der temporären Etikettentabelle ZT.
Fig. 10 zeigt ein Blockdiagramm einer weiteren Ausführungsform der Erfindung.
Fig. 10 zeigt die Erzeugungsschaltung 40 für die endgültige Etikettentabelle, die das Ergebnis der Etikettentabellenumordnung der temporären Etikettentabelle ZT in die endgültige Etikettentabelle HT schreibt und dabei der Etikettentabellenanordnung der temporären Etikettentabelle ZT folgt.
In Fig. 10 erzeugt die Erzeugungsschaltung 20 für temporär etikettierte Bilddaten die temporäre Etikettentabelle ZT.
In Fig. 10 liest eine Lesevorrichtung 42 für die temporäre Etikettentabelle nacheinander die Daten der temporären Etikettentabelle ZT an jeder Adresse von der Adresse "1" bis "n", und gibt bei jedem Auslesevorgang den Wert der gelesenen Daten und den Wert der Adresse, an der in der temporären Etikettentabelle ZT gelesen wurde, an eine Schreibvorrichtung 44 für die endgültige Etikettentabelle aus.
Die Schreibvorrichtung 44 für die endgültige Etikettentabelle vergleicht zunächst den Adreßwert, an dem ausgelesen wurde, mit dem Wert der gelesenen Daten, wobei die Lesevorrichtung 42 für die temporäre Etikettentabelle den Adreßwert und den Datenwert eingibt.
Sind der Adreßwert, an dem ausgelesen wurde, und der Wert der gelesenen Daten gleich, so erfordert der temporäre Etikettenwert, der durch den Wert der Adresse angegeben wird, an der ausgelesen wurde, keine Etikettenabänderung, und der Etikettenwert kann als endgültiges Etikett genommen werden.
Sind der Adreßwert, an dem ausgelesen wurde, und der Wert der gelesenen Daten gleich, d. h., ist keine Umsetzung erforderlich, so schreibt die Schreibvorrichtung 44 für die endgültige Etikettentabelle den Wert des endgültigen Etikettenzählers, der fortlaufende endgültige Etiketten erzeugt, in die endgültige Etikettentabelle, und zwar an einer Adresse, deren Wert gleich der Adresse ist, an der aus der temporären Etikettentabelle ZT gelesen wurde.
Sind dagegen der Adreßwert, an dem ausgelesen wurde, und der Wert der gelesenen Daten nicht gleich (da die Tabelle eine Tabelle im MAX-MIN-Format ist, folgt daraus (der Wert der Adresse, an der ausgelesen wurde) ist größer als (der Wert der gelesenen Daten)), so muß der temporäre Etikettenwert, der durch die Adresse ausgedrückt wird, an der ausgelesen wurde, in den temporären Etikettenwert (oder endgültigen Etikettenwert) umgesetzt werden, der durch den Wert der gelesenen Daten ausgedrückt wird.
Sind dementsprechend der Adreßwert, an dem das temporäre Etikett gelesen wurde, und der Wert der gelesenen Daten nicht gleich, d. h., ist eine Umsetzung des temporären Etiketts erforderlich, das durch den Wert der Adresse ausgedrückt wird, an dem aus der temporären Etikettentabelle ZT gelesen wurde, so bestimmt die Schreibvorrichtung 44 für die endgültige Etikettentabelle den Umsetzziel-Etikettenwert, d. h. den endgültigen Etikettenwert, und schreibt den Wert in die endgültige Etikettentabelle HT an eine endgültige Etikettentabellenadresse, deren Wert gleich dem Wert der Adresse ist, bei der aus der temporären Etikettentabelle gelesen wurde.
Die Schreibvorrichtung 44 für die endgültige Etikettentabelle kann Daten aus der endgültigen Etikettentabelle an einer Adresse lesen, deren Wert gleich dem Wert der Daten ist, die aus der temporären Etikettentabelle gelesen wurden. Die Schreibvorrichtung 44 für die endgültige Etikettentabelle kann die Daten der endgültigen Etikettentabelle direkt in einen definiert festgelegten Umsetzziel-Etikettenwert für die Abänderung des temporären Etiketts umwandeln, falls eine Umsetzung des temporären Etikettenwerts erforderlich ist, der durch den Wert der Adresse ausgedrückt wird, an dem die temporäre Etikettentabelle ZT ausgelesen wurde.
Dies hat seine Ursache im MAX-MIN-Format der temporären Etikettentabelle ZT, denn das MAX-MIN-Format impliziert, daß die Umsetzung für die Abänderung der temporären Etiketten gemäß den Daten der temporären Etikettentabelle ZT so vorgenommen wird, daß der Umsetzziel-Etikettenwert unveränderbar kleiner ist als der Umsetzquellen-Etikettenwert. Dies hat weiterhin seine Ursache in der Erzeugungsschaltung 40 für die endgültige Etikettentabelle, da die Erzeugungsschaltung 40 für die endgültige Etikettentabelle die Etikettentabelle nacheinander in aufsteigender Reihenfolge der Adreßwerte der temporären Etikettentabelle anordnet (die Adreßwerte entsprechen den temporären Umsetzquellen-Etikettenwerten).
Dies hat seine Ursache also in der Schreibvorrichtung 44 für die endgültige Etikettentabelle, die entschieden hat, daß eine Umsetzung des temporären Etikettenwerts erforderlich ist. Der Umsetzziel-Etikettenwert, der aus der endgültigen Etikettentabelle gemäß der Entscheidung der Schreibvorrichtung 44 für die endgültige Etikettentabelle gelesen wurde, bleibt unveränderlich ein definiert festgelegter Etikettenwert, d. h. ein endgültiger Etikettenwert.
Schließlich kann ein Teil der Verarbeitung in der Lesevorrichtung 42 für die temporäre Etikettentabelle und der Schreibvorrichtung 44 für die endgültige Etikettentabelle gleichzeitig ausgeführt werden. Da die temporäre Etikettentabelle ZT und die endgültige Etikettentabelle HT unabhängige Tabellen sind, sind ein Lesevorgang aus der temporären Etikettentabelle ZT und ein Lese- oder Schreibvorgang bei der endgültigen Etikettentabelle HT gleichzeitig ausführbar.
Fig. 11 zeigt eine Abfolgedarstellung der Verarbeitung in der beschriebenen Ausführungsform nach Fig. 10.
In Fig. 11 erfolgt der Fortgang der Verarbeitung für die Etikettentabellenanordnung von oben nach unten. Die Richtung von links nach rechts zeigt den Verlauf der Zeit. Die Zahlen T1 - T12 bezeichnen Zeitpunkte.
In Fig. 11 bezeichnen die ZT[x] die Daten in der temporären Etikettentabelle ZT an der Adresse mit dem Adreßwert x. Die HT[x] bezeichnen die Daten in der endgültigen Etikettentabelle HT an der Adresse mit dem Adreßwert x.
COMP bezieht sich auf das Lesen der temporären Etikettentabellendaten während des unmittelbar vorhergehenden Auslesens und bezeichnet einen Vergleich zwischen dem Wert der Adresse, an der ausgelesen wurde und dem Wert der gelesenen Daten. In der Darstellung bezeichnen die Gleichheits- und Ungleichheitszeichen unter COMP das Vergleichsergebnis.
Weiterhin bezeichnet READ ein Lesen aus der Tabelle an der Adresse, die unter READ angegeben ist. "READ ZT[1]" bedeutet also, daß Daten aus der temporären Etikettentabelle an einer Adresse mit dem Wert "1" gelesen werden. "READ HT[a]" bedeutet, daß Daten aus der endgültigen Etikettentabelle an einer Adresse mit dem Wert "a" gelesen werden.
WRITE zeigt an, daß Daten in die Adresse geschrieben werden, deren Wert unter WRITE angegeben ist. Beispielsweise bedeutet "WRITE HT[2]", daß Daten, die beim unmittelbar vorhergehenden Auslesevorgang aus der temporären Etikettentabelle oder der endgültigen Etikettentabelle gelesen wurden, an einer Adresse mit dem Adreßwert "2" in die endgültige Etikettentabelle HT geschrieben werden.
In Fig. 11 wird jeweils zu den Zeitpunkten T1, T3, T5, T7, T9 und T11 an den festgelegten Adressen aus der temporären Etikettentabelle ZT gelesen.
An den Zeitpunkten T3, T9 und T11 werden das Auslesen aus der temporären Etikettentabelle ZT und das Schreiben der endgültigen Etiketten in die endgültige Etikettentabelle gleichzeitig ausgeführt, wobei die endgültigen Etiketten den temporären Etiketten entsprechen, die während des vorhergehenden Lesevorgangs aus der temporären Etikettentabelle gelesen wurden.
An den Zeitpunkten TS und T7 wird das Auslesen aus der temporären Etikettentabelle ZT und das Auslesen der Daten aus der endgültigen Etikettentabelle an einer Adresse, deren Wert gleich dem Wert der Daten ist, die aus der temporären Etikettentabelle ZT gelesen wurden, gleichzeitig ausgeführt, wobei das Auslesen aus der temporären Etikettentabelle ZT ausgeführt wird, weil eine Umsetzung des temporären Etikettenwerts entsprechend dem Wert der Adresse erforderlich ist, an der beim vorhergehenden Auslesevorgang aus der temporären Etikettentabelle ZT gelesen wurde.
Damit wird in der Erzeugungsschaltung für die endgültige Etikettentabelle ein Teil der Verarbeitung in der Lesevorrichtung 42 für die temporäre Etikettentabelle und in der Schreibvorrichtung 44 für die endgültige Etikettentabelle gleichzeitig ausgeführt. Daher ist es nicht nur möglich, die Verarbeitungszeit zu verringern, die die Erzeugungsschaltung 40 für die endgültige Etikettentabelle benötigt, um die gesamte Anordnung der Etikettentabelle (Erzeugung der Daten in der endgültigen Etikettentabelle HT) abzuschließen, sondern es ist auch möglich, die gesamte Verarbeitung in einer festliegenden Verarbeitungszeit Ta zu beenden. Wurden n Daten in die endgültige Etikettentabelle HT geschrieben, so kann die Verarbeitungszeit Ta, die zum Abschluß der Datenerzeugung in der endgültigen Etikettentabelle HT erforderlich ist, der folgenden Formel entnommen werden:
Ta1 = 2 x n + 1 (falls die COMP-Verarbeitung für das letzte temporäre Etikett Gleichheit ergibt),
Ta2 = 2 x n + 2 (falls die COMP-Verarbeitung für das letzte temporäre Etikett Ungleichheit ergibt). ... (1)
In Fig. 11 ist der Zeitpunkt, zu dem beispielsweise die Verarbeitung des temporären Etikettenwerts "5" (n = 5) abgeschlossen ist, Tu (2 x 5 + 1).
Fig. 12 ist eine weitere Abfolgedarstellung der Verar beitung gemäß der beschriebenen Ausführungsform nach Fig. 10.
In Fig. 12 erfolgt der Fortgang der Verarbeitung für die Etikettentabellenanordnung von oben nach unten. Die Richtung von links nach rechts zeigt den Verlauf der Zeit.
Die Zahlen T1 - T10, ZT[X], HT[x], COMP, READ und WRITE in Fig. 12 haben die gleichen Bedeutungen wie die entsprechenden Zahlen in Fig. 11.
In Fig. 12 wird eine größere Verarbeitungsmenge als in Fig. 11 gleichzeitig ausgeführt; daher verkürzt sich die gesamte Verarbeitungszeit.
In Fig. 12 wird die temporäre Etikettentabelle ZT an festgelegten Adressen jeweils zu den Zeitpunkten T1, T2, T4, T6, T7 und T8 gelesen.
Insbesondere wird das Auslesen der temporären Etikettentabelle ZT zu den Zeitpunkten T2, T7 und T8 unmittelbar nach dem vorhergehenden Auslesen der temporären Etikettentabelle ZT ausgeführt. D. h., die Verarbeitung der temporären Etiketten "2", "5" und "6" beginnt ein Zeitintervall früher.
Da die Verarbeitung des temporären Etiketts "2" auf einer früheren Stufe beginnt, fängt die Verarbeitung des temporären Etiketts "3" ebenfalls auf einer früheren Stufe an, und die Verarbeitung des temporären Etiketts "3" und ein Teil der Verarbeitung des temporären Etiketts "1" werden gleichzeitig ausgeführt, wobei die Verarbeitung des temporären Etiketts "1" zwei Zeitintervalle früher begonnen hat. Die Verarbeitung des temporären Etiketts "5" beginnt auf einer früheren Stufe, und die Verarbeitung des temporären Etiketts "5" und ein Teil der Verarbeitung des temporären Etiketts "3" werden gleichzeitig ausgeführt, wobei die Verarbeitung des temporären Etiketts "3" zwei Zeitintervalle früher begonnen hat. Die Verarbeitung des temporären Etiketts "6" beginnt auf einer früheren Stufe, und die Verarbeitung des temporären Etiketts "6" und ein Teil der Verarbeitung des temporären Etiketts "4" werden gleichzeitig ausgeführt, wobei die Verarbeitung des temporären Etiketts "4" zwei Zeitintervalle früher begonnen hat.
Dementsprechend werden zu den Zeitpunkten T4, T7, T8 und T9 drei temporäre Etiketten gleichzeitig verarbeitet.
Dagegen beginnt die Verarbeitung der temporären Etiketten "3" und "4" nicht auf einer früheren Stufe.
Der Grund dafür liegt darin, daß der Vergleich "COMP" während der Verarbeitung der temporären Etiketten "2" und "3" Ungleichheit ergeben hat und die Verarbeitung der temporären Etiketten "2" und "3" zwei Zeitintervalle früher begonnen hat als die der temporären Etiketten "3" und "4". Beginnt die Verarbeitung der temporären Etiketten "3" und "4"auf einer früheren Stufe, so überlappen sich das "READ HT[b]" bei der Verarbeitung des temporären Etiketts "3" und das "WRITE HT[2]" des temporären Etiketts "2", und das "WRITE HT[4]" bei der Verarbeitung des temporären Etiketts "4" und das "WRITE HT[3]" des temporären Etiketts "3" überlappen sich. Dadurch ergibt sich ein gleichzeitiger Zugriff auf die endgültige Etikettentabelle.
Werden n Daten in die endgültige Etikettentabelle geschrieben, so kann die Verarbeitungszeit Tb, die zum Abschluß der Datenerzeugung in der endgültigen Etikettentabelle erforderlich ist, der folgenden Formel entnommen werden:
Tb = (2 x n + 2) - m. ... (2)
Dabei ist m die Anzahl der temporären Etikettentabellendaten, die zu verarbeiten sind, und deren Adreßwert gleich dem Wert der Daten selbst ist. Ist jedoch der Adreßwert der Daten gleich dem Datenwert, so sind die Daten nicht in m aufzunehmen, wenn die Daten die letzten Daten aus den zu verarbeitenden temporären Etikettentabellendaten sind.
Ein Vergleich der Formeln (1) und (2) zeigt klar, daß die Verarbeitungszeit der Abfolge nach Fig. 12 kürzer ist als die Verarbeitung nach Fig. 11.
Fig. 13 zeigt ein Flußdiagramm mit der Verarbeitung in der Erzeugungsschaltung 40 für die endgültige Etikettentabelle.
Da die Lesevorrichtung 42 für die temporäre Etikettentabelle und die Schreibvorrichtung 44 für die endgültige Etikettentabelle der Erzeugungsschaltung 40 für die endgültige Etikettentabelle wie oben beschrieben Teile der Verarbeitung gleichzeitig ausführen, ist es schwierig, die Verarbeitung der Erzeugungsschaltung 40 für die endgültige Etikettentabelle in einem Flußdiagramm zu beschreiben. Das Flußdiagramm in Fig. 13 gibt hauptsächlich die Etikettentabellenanordnung für einen temporären Etikettenwert wieder.
Im Schritt 410 in Fig. 13 wird der Anfangswert "1" in einen Adreßwertspeicher ADR und einen endgültigen Etikettenwertspeicher H_LBL geschrieben.
Im Schritt 412 liest die Lesevorrichtung 42 für die temporäre Etikettentabelle Daten aus der temporären Etikettentabelle ZT an einer Adresse, deren Wert gleich dem Wert der Daten des Adreßwertspeichers ADR ist. Anschließend werden die Daten in einen temporären Etikettendatenspeicher Z_DATA geschrieben.
Die Schritte 420 bis 440 werden in der Schreibvorrichtung 44 für die endgültige Etikettentabelle abgearbeitet.
Im Schritt 420 werden die Werte des Adreßwertspeichers ADR und des temporären Etikettendatenspeichers Z_DATA verglichen. Durch Vergleichen des Werts der Adresse, an der aus der temporären Etikettentabelle ZT gelesen wurde, mit den gelesenen Daten wird bestimmt, ob eine Umsetzung für die Abänderung des temporären Etiketts, das durch den Wert der Adresse dargestellt wird, an der aus der temporären Etikettentabelle ZT gelesen wurde, erforderlich ist oder nicht.
Sind der Wert des Adreßwertspeichers ADR und der Wert des temporären Etikettendatenspeichers Z_DATA gleich, d. h., ist eine Umsetzung des temporären Etikettenwerts nicht nötig, so fährt die Verarbeitung mit dem Schritt 422 fort.
Im Schritt 422 wird der Wert der Daten des endgültigen Etikettenwertspeichers H_LBL in die endgültige Etikettentabelle geschrieben, und zwar an einer Adresse, deren Wert gleich dem Wert der Daten des Adreßwertspeichers ADR ist.
Nach dem Schritt 422 wird im Schritt 424 der endgültige Etikettenwertspeicher H_LBL inkrementiert.
Sind dagegen im Schritt 420 der Wert der Daten des Adreßwertspeichers ADR und der Wert der Daten des temporären Etikettendatenspeichers Z_DATA nicht gleich, so fährt die Verarbeitung mit dem Schritt 430 fort.
Im Schritt 430 wird der Etikettenwert, der bereits definiert festgelegt ist (endgültiger Etikettenwert), aus der endgültigen Etikettentabelle HT an einer Adresse gelesen, deren Wert gleich dem Wert der Daten des temporären Etikettendatenspeichers Z_DATA ist. Anschließend wird der endgültige Etikettenwert in den endgültigen Etikettendatenspeicher H_DATA geschrieben.
Im Schritt 432 werden die Daten des endgültigen Etikettendatenspeichers H_DATA in die endgültige Etikettentabelle geschrieben, und zwar an einer Adresse, deren Wert gleich dem Wert der Daten des Adreßwertspeichers ADR ist.
Nachdem die beschriebenen Schritte 424 oder 432 abgearbeitet sind, fährt die Verarbeitung im Schritt 436 fort.
Im Schritt 436 wird der Adreßwertspeicher ADR inkrementiert.
Im Schritt 440 werden der Wert der Daten des Adreßwertspeichers ADR und der Wert der Daten des temporären Etikettenzählspeichers ZLC verglichen, und es wird bestimmt, ob die Etikettentabellenanordnung der temporären Etikettentabelle ZT abgeschlossen ist oder nicht.
Ist der Wert der Daten des Adreßwertspeichers ADR kleiner oder gleich dem Wert der Daten des temporären Etikettenzählspeichers ZLC, so wird vor den Schritt 412 gesprungen. Ist dagegen der Wert des Adreßwertspeichers ADR größer als der Wert des temporären Etikettenzählspeichers ZLC, so wird die im Flußdiagramm nach Fig. 13 dargestellte Verarbeitung beendet.
Der temporäre Etikettenzählspeicher ZLC entspricht dem temporären Etikettenzählspeicher ZLC der Erzeugungsschaltung für temporär etikettierte Bilddaten, die in den Flußdiagrammen nach Fig. 2 bis Fig. 6 dargestellt ist. D. h., der Wert, der in den temporären Etikettenzählspeicher ZLC in Fig. 13 geschrieben wird, ist die Gesamtanzahl der temporären Etiketten, die die Erzeugungsschaltung für temporär etikettierte Bilddaten in den Fig. 2 bis 6 geschrieben und erzeugt hat.
Die Erzeugungsschaltung für temporär etikettierte Bilddaten erzeugt eine temporäre Etikettentabelle im MAX-MIN- Format und schreibt den Wert des temporären Etikettenzähl speichers ZLC (dessen Wert gleich der Anzahl temporärer Etiketten ist).
Fig. 14 zeigt eine Darstellung der endgültigen Etikettentabelle, die in der beschriebenen Ausführungsform der Erfindung erzeugt wird.
Die in jede Adresse in der temporären Etikettentabelle ZT in Fig. 10 geschriebenen Daten sind ein Beispiel, das die temporären Etikettentabellendaten für den Fall erläutert, daß die temporären Etiketten dem Bild in Fig. 22 zugewiesen sind, und das die Umsetzbeziehung für die Abänderung der temporären Etiketten zeigt.
Gemäß dieser Ausführungsform der Erfindung werden die Daten in der temporären Etikettentabelle ZT nach Fig. 10 an der Adresse mit dem Wert "3" direkt mit "1" überschrieben. Damit erreicht man eine rasche Anordnung der Etikettentabelle.
Fig. 15 zeigt ein Blockdiagramm einer weiteren Ausführungsform der Erfindung.
Die Pufferspeicher 60 in Fig. 15 verwenden FIFO-Speicher. Der Wert des definiert festgelegten Anfangsetikettenspeichers ZL und der Wert des definiert festgelegten Lauflängenzählers RUN der beschriebenen ersten erfindungsgemäßen Ausführungsform werden in den Pufferspeicher 60 geschrieben.
D. h., die Bilddaten, die die Erzeugungsschaltung 20 für temporär etikettierte Bilddaten ausgibt, und die aus dem temporären Etikettenwert und dem Lauflängenwert aufgebaut sind, werden in den Pufferspeicher 60 geschrieben.
Der Schalter 72 wählt die Art der temporär etikettierten Bilddaten, die an den Ausgang ZOUT ausgegeben werden.
Die Bilddaten, die aus dem temporären Etikettenwert und dem Lauflängenwert bestehen und direkt aus dem Pufferspeicher 60 ausgegeben werden, können anstelle der temporär etikettierten Bilddaten genommen werden, die am Ausgang ZOUT ausgegeben werden. Weiterhin ist es durch Umschalten des Schalters 72 wahlweise möglich, die temporär etikettierten Bilddaten auszugeben, die aus dem temporären Etikettenwert und dem Lauflängenwert bestehen und aus dem Pufferspeicher 60 ausgegeben werden. Die temporär etikettierten Bilddaten sind normal temporär etikettierte Bilddaten, die aus einem temporären Etikettenwert für jedes Pixel bestehen, und werden am Ausgangsanschluß ZOUT unter Verwendung des Lauflängeninverters 64 ausgegeben.
Dagegen werden die Daten, die zur Umsetzbeziehung für die Abänderung der temporären Etiketten gehören, in die temporäre Etikettentabelle ZT geschrieben. Die Erzeugungsschaltung 20 für temporär etikettierte Bilddaten gibt diese Daten aus; sie bezeichnen Umsetzbeziehungen für die Abänderung der Etikettenwerte, wobei die Umsetzung so erfolgt, daß die Etikettenwerte nur in abnehmender Reihenfolge der Etikettenwerte erfolgt.
Die Erzeugungsschaltung 40 für die endgültige Etikettentabelle, die aus der Lesevorrichtung 42 für die temporäre Etikettentabelle und der Schreibvorrichtung 44 für die endgültige Etikettentabelle besteht, führt die Etikettentabellen-Anordnungsverarbeitung für die in die temporäre Etikettentabelle ZT geschriebenen Daten aus und schreibt die Daten in die endgültige Etikettentabelle HT.
30 Weiterhin können die Daten, die den Zusammenhang zwischen den definiert festgelegten temporären Etikettenwerten, die in die endgültige Etikettentabelle HT geschrieben werden, und den endgültigen Etikettenwerten darstellen, falls erforderlich vom Ausgang HOUT gelesen werden.
Um in den Etikettenwertspeicher H0 Daten für das Pixel an der oberen rechten Seite des betrachteten Pixels zu schreiben, ist der Etikettenwertspeicher H0 ein Teil des Maskenspeichers 12a der Erzeugungsschaltung 20 für temporär etikettierte Bilddaten nach Fig. 1. Die temporär etikettier ten Bilddaten, die aus dem Pufferspeicher 60 ausgegeben werden, werden ebenfalls in die Erzeugungsschaltung 20 für temporär etikettierte Bilddaten eingegeben, und zwar mit Hilfe des Lauflängeninverters 64 nach einer Umsetzung der temporär etikettierten Bilddaten in normal temporär etikettierte Bilddaten, die aus einem temporären Etikettenwert für jedes Pixel bestehen.
Man kann außerordentlich gute Ergebnisse erhalten, wenn man eine Kombination vorteilhafter Merkmale gemäß Fig. 15 bereitstellt.
Gemäß der endgültigen Etikettentabelle in der Schaltung nach Fig. 15 kann man ein Bild nach Fig. 23 erhalten.
Fig. 16 zeigt ein Blockdiagramm der Schaltung, die die endgültig etikettierten Bilddaten erzeugt.
In Fig. 16 haben die Zahlen 64 und HT die gleiche Bedeutung wie die entsprechenden Bezugszeichen in Fig. 15.
Falls erforderlich kann ein FIFO-Pufferspeicher als temporärer Speicher 74 bereitgestellt werden. Die in den temporären Speicher 74 geschriebenen Daten sind die temporär etikettierten Bilddaten, die aus dem temporären Etiketten wert und dem Lauflängenwert bestehen und aus dem Ausgang ZOUT in Fig. 15 ausgegeben werden. Der temporäre Speicher 74 dient also als Puffer für die temporär etikettierten Bilddaten.
Die Erzeugungsschaltung 70 für endgültig etikettierte Bilddaten besteht aus der Erzeugungsvorrichtung 76 für endgültig etikettierte Bilddaten und dem Lauflängeninverter 64.
Die Erzeugungsschaltung 70 für endgültig etikettierte Bilddaten kann endgültig etikettierte Bilddaten im Lauflängenformat ausgeben und ebenso endgültig etikettierte Bilddaten, die Daten für Blöcke aus einem Pixel sind.
Fig. 17 zeigt ein Flußdiagramm, das die Verarbeitung in der beschriebenen Erzeugungsschaltung für endgültig etikettierte Bilddaten beschreibt.
Hat ein Ausgabemodusspeicher MODE in Fig. 17 den Wert "0", so wird der Lauflängenformat-Ausgabemodus aktiv. Dies bedeutet, daß die Erzeugungsschaltung 70 für endgültig etikettierte Bilddaten endgültig etikettierte Bilddaten im Lauflängenformat ausgibt, d. h., endgültig etikettierte Bilddaten, die aus dem endgültigen Etikettenwert und dem Lauflängenwert bestehen.
Hat dagegen der Ausgabemodusspeicher MODE den Wert "1", so wird der Ausgabemodus für Blöcke mit einem Pixel aktiv. Dies bedeutet, daß endgültig etikettierte Bilddaten ausgegeben werden, die den endgültigen Etikettenwert für Blöcke mit einem Pixel darstellen.
Im Schritt 460 im Flußdiagramm nach Fig. 17 wird aus dem temporären Speicher 74 in den temporären Etikettenspeicher ZL2 eingelesen.
Im Schritt 462 werden die Daten der endgültigen Etikettentabelle HT an der Adresse, deren Wert gleich dem Wert des temporären Etikettenspeichers ZL2 ist, gelesen und in den endgültigen Etikettenwertspeicher HL geschrieben.
Im Schritt 466 wird aus dem temporären Speicher 74 in den Lauflängenspeicher RUN2 eingelesen.
Im Schritt 470 wird der Wert des Lauflängenspeichers RUN2 berechnet. Ist der Wert "0", so wird die Erzeugung der endgültig etikettierten Bilddaten für einen Teilbereich beendet, und die im Flußdiagramm nach Fig. 17 dargestellte Verarbeitung endet.
Im Schritt 474 wird das Datenförmat des Ausgangssignals der Erzeugungsschaltung für endgültig etikettierte Bilddaten gewählt, und zwar abhängig davon, ob der Ausgabemodusspeicher MODE den Wert "0" hat oder nicht.
Ist im Schritt 474 der Lauflängenformat-Ausgabemodus aktiv, so werden durch die Ausgabe des Endwertspeichers HL im Schritt 482 und die Ausgabe des Lauflängenspeichers RUN2 im Schritt 486 die endgültig etikettierten Bilddaten ausgeggeben, die aus dem endgültigen Etikettenwert und dem Lauflängenwert bestehen.
Ist dagegen im Schritt 474 der Ausgabemodus für die Ausgabe in Blöcken zu einem Pixel aktiv, so durchläuft die Verarbeitung die Schritte 476 bis 480.
In den Schritten 476 bis 480 wird der Wert der Daten des endgültigen Etikettenwertspeichers N-mal ausgegeben, wobei N gleich dem Wert des Lauflängenspeichers RUN2 ist. Die endgültig etikettierten Bilddaten, die die endgültigen Etikettenwerte für jedes Pixel sind, werden durch diesen Vorgang ausgegeben.
Mit der Erzeugungsschaltung für endgültig etikettierte Bilddaten nach Fig. 16 und 17 ist es somit möglich, endgültig etikettierte Bilddaten zu erhalten, denen definiert festgelegte Etikettenwerte, d. h. endgültige Etikettenwerte zugewiesen sind.

Claims

1. Bildverarbeitungs-Etikettierschaltung, die während des Abtastens von Schwarz-Weiß-Bildern in einem Teilbereich in Abtastrichtung mit einer besonderen Maske (12) hauptsächlich die Verbundenheit eines betrachteten Pixels (10) mit den Pixeln erkennt, die das betrachtete Pixel (10) innerhalb der Maske (12) umgeben, und nacheinander einen Etikettenwert bestimmt und jedem Pixel zuweist, umfassend:

einen Anfangsetikettenspeicher (ZL), der anfängliche temporäre Etikettenwerte derjenigen Pixel speichert, die in der abgetasteten Zeile zusammenhängen;

einen Längenzähler (RUN), der die Anzahl der Pixel zählt, die in der abgetasteten Zeile zusammenhängen;

eine Erzeugungsvorrichtung (22) für temporäre Etiketten zum Verwenden der anfänglichen temporären Etikettenwerte im Anfangsetikettenspeicher (ZL) und der Längendaten aus dem Längenzähler (RUN), wobei temporär etikettierte Bilddaten und temporäre Etikettentabellendaten erzeugt werden, und die temporären Etikettentabellendaten die erforderlichen Umsetzbeziehungen für die Integration der temporären Etiketten angeben; und Vorrichtungen (40, 70) zum Erzeugen endgültig etikettierter Bilddaten aus den temporär etikettierten Bilddaten und den temporären Etikettentabellendaten.

2. Etikettierschaltung nach Anspruch 1, wobei die temporär etikettierten Bilddaten, die die Erzeugungsvorrichtung (22) für temporäre Etiketten erzeugt, eine Umsetzung zur Abänderung der Etikettenwerte erfahren können, so daß die Etikettenwerte nur in abnehmender Ordnung der Etikettenwerte geändert werden, und die Etikettierschaltung weiter umfaßt:

eine temporäre Etikettentabelle (ZT), deren Adressen temporäre Etikettenwerte sind, und deren Daten temporäre Umsetzziel-Etikettenwerte sind, und in der die temporären Etikettentabellendaten gespeichert sind;

eine endgültige Etikettentabelle (HT), deren Adressen temporäre Etikettenwerte sind, und deren Daten die endgültigen Etikettenwerte sind;

eine Leseschaltung (42) für die temporären Etikettentabellendaten, die nacheinander die Daten liest, die die temporären Umsetzziel-Etikettenwerte sind, und zwar in aufsteigender Adreßreihenfolge; und

eine Schreibschaltung (44) für die endgültigen Etikettentabellendaten, die die gelesenen Daten mit den gelesenen Adreßwerten vergleicht, sodann ermittelt, ob eine Umsetzung der temporären Etikettenwerte entsprechend der Leseadresse erforderlich ist oder nicht, einen endgültigen Etikettenwert bestimmt, der ein neuer endgültiger Etikettenwert ist, und den endgültigen Etikettenwert an einer Adresse in die endgültige Etikettentabelle schreibt, die der Leseadresse gleich ist, wenn sich zeigt, daß eine Umsetzung nicht nötig ist, und die, wenn sich zeigt, daß eine Umsetzung erforderlich ist, Daten an einer Adresse aus der endgültigen Etikettentabelle liest, die dem Wert der Daten gleich ist, die aus der temporären Etikettentabelle gelesen wurden, und die Daten an einer Adresse in die endgültige Etikettentabelle schreibt, die der Adresse gleich ist, an der aus der temporären Etikettentabelle gelesen wurde, wobei die Etikettierschaltung die Daten der endgültigen Etikettentabelle (HT) gemäß der endgültig festgelegten Daten der temporären Etikettentabelle erzeugt und schreibt und dabei der Erzeugung der temporär etikettierten Bilddaten für einen Teilbereich folgt.

3. Etikettierschaltung nach Anspruch 2, wobei die Schreibschaltung (44) für die endgültigen Etikettentabellendaten die aus der temporären Etikettentabelle (ZT) gelesenen Daten als neue endgültige Etikettenwerte in die endgültige Etikettentabelle (HT) schreibt, falls sich herausstellt, daß keine Umsetzung erforderlich ist.

4. Etikettierschaltung nach Anspruch 2, wobei die Schreibschaltung (44) für die endgültigen Etikettentabellendaten während der Umsetzung in die endgültige Etikettentabelle (HT) den Wert des Zählers für die endgültigen Etiketten schreibt, der die endgültigen Etiketten der aufeinander folgenden Etikettenwerte erzeugt, und zwar in die endgültige Etikettentabelle an einer Adresse, die der Adresse gleich ist, an der die temporäre Eti kettentabelle (ZT) gelesen wurde, wenn sich zeigt, daß keine Umsetzung erforderlich ist.

5. Etikettierschaltung nach Anspruch 4, wobei der Zähler für die endgültigen Etiketten jeweils dann erhöht wird, wenn ein neues endgültiges Etikett vergeben wird.

6. Etikettierschaltung nach Anspruch 2, wobei die temporär etikettierten Bilddaten aus temporären Etikettendaten und Längendaten ausgebaut sind, die die Daten der Pixelanzahl in den verbundenen Pixeln entsprechend der temporären Etikettendaten sind.

7. Etikettierschaltung nach Anspruch 2, wobei die Erzeugungsschaltung (20) für temporär etikettierte Bilddaten die anfänglichen Etikettenwerte der betrachteten Pixel mit Hilfe einer Maske (12) bestimmt, die eine festgelegte Pixelanzahl aufweist, und die Pixelanzahl der verbundenen Pixel mit Hilfe des Längenzählers (RUN) zählt, falls die nacheinander abgetasteten betrachteten Pixel verbundene Pixel sind.

8. Etikettierprozessor nach Anspruch 2, wobei die Verarbeitung in der Lesevorrichtung (42) für die temporären Etikettentabellendaten und in der Schreibvorrichtung (44) für die endgültigen Etikettentabellendaten teil weise gleichzeitig ausgeführt wird.