-
Die Erfindung betrifft ein Verfahren und eine Vorrichtung
zum Kodieren einer N-dimensionalen Anordnung von
Datenwerten, die den Farbgehalt durch Bildpixeln repräsentieren.
-
Moderne Bildverarbeitung erfordert, dar grobe Datenmengen
verarbeitet und gespeichert werden. Typischerweise ist eine
farbige Bildgraphik von Pixel definiert, die lineare
Dichten in der Größenordnung von über 100/cm (300/inch)
aufweisen, wobei jedes Pixel durch Ausdrücke von drei oder
vier Farbkomponenten definiert ist. Der Text muß mit
höheren Auflösungen, z.B. mit mehr als 700/cm (1800/inch)
gespeichert werden. Um die Datenmenge zum Speichern o.ä. zu
verringern, ist es allgemein bekannt, die Daten zu
komprimieren, wobei man die Tatsache benutzt, dar in realen
Bildern signifikante Pixelgruppen den gleichen Farbgehalt
besitzen. Verfahren wie Lauflängenkodierung sind entwickelt
worden, mit denen relativ hohe Kompressionsverhältnisse
möglich sind. US-A-3,524,926 offenbart ein Verfahren zum
Adaptieren von Bild-daten, so dar sie für
Lauflängenkodierung o.ä. passend sind, wobei eine sogenannte
Deltakodiertechnik vorgenommen wird.
-
Schwierigkeiten können jedoch entstehen, wenn die Daten zum
Zwecke der Anzeige oder in anderer Ausgangsform wieder
hergestellt werden müssen. Allgemein ist es nötig, das
komplette Bild aus seiner komprimierten Form wieder
herzustellen, auch wenn nur ein Bildteil am Ausgang erscheinen soll.
Dies führt zu langwierigen Operationen, da ein mehrfacher
Zugriff zur Scheibe normalerweise erforderlich ist, wenn
die komprimierten Daten aufeiner Scheibe gespeichert sind
und ein großer Puffer wird benötigt, in dem das
Originalbild vor der Abgabe wieder hergestellt werden kann.
-
Gemäß einem Aspekt der vorliegenden Erfindung ist ein
Verfahren zum Kodieren einer N-dimensionalen Anordnung von
Datenwerten vorgesehen, die den Farbgehalt von Bildpixeln
repräsentieren, wobei die Datenreihen in jeder der
N-Dimensionen beginnend jeweils mit den jeweils ersten Positionen
in jeder Dimension, mit einem invertierbaren
Differenzoperator behandelt werden, um eine N-dimensionale Anordnung
von kodierten Daten zu erzeugen, dadurch gekennzeichnet,
daß für mindestens eine der Dimensionen ein zusätzlicher,
redundanter Datensatz erzeugt wird, indem eine
vorbestimmte zusätzliche Datenreihe und eine Reihe von Pixeldaten mit
dem gleichen invertierbaren Differenzoperator behandelt
werden, so dar die originären Datenwerte in dieser
Dimension wieder hergestellt werden können, indem die kodierten
Daten beginnend mit einer zweiten, gegenüber der
entsprechenden ersten Position unterschiedlichen Position mit dem
invertierten Differenzoperator behandelt werden.
-
Gemäß einem zweiten Aspekt der vorliegenden Erfindung ist
eine Vorrichtung zum Kodieren einer N-dimensionalen
Anordnung von Datenwerten vorgesehen, die den Farbgehalt von
Bildpixeln repräsentieren, mit Speichermitteln und Mitteln
zur Datenverarbeitung, mit denen Reihen einer
N-dimensionalen Anordnung von Datenwerten in den Speichermitteln in
jeder der N-Dimensionen beginnend mit den jeweils ersten
Positionen in jeder Dimension mit einem invertierbaren
Differenzoperator behandelt werden, um eine N-dimensionale
Anordnung von kodierten Daten zu erzeugen, die in den
Speichermitteln gespeichert wird, dadurch gekennzeichnet, daß
für mindestens eine der Dimensionen ein zusätzlicher,
redundanter Datensatz erzeugt und gespeichert wird, in dem
eine vorbestimmte zusätzliche Datenreihe und eine Reihe von
Pixeldaten mit dem gleichen invertierbaren
Differenzoperator
behandelt werden, so daß die originären Datenwerte in
dieser Dimension wieder hergestellt werden können, indem
die kodierten Daten in den Speichermitteln beginnend mit
einer zweiten, gegenüber der entsprechenden ersten Position
unterschiedlichen Position mit dem invertierten
Differenzoperator behandelt werden.
-
Wir haben festgestellt, daß bei Verwendung eines
invertierbaren Differenzoperators und durch Erzeugen mindestens
eines zusätzlichen Datensatzes es möglich ist, alle oder
einen Teil der originären Datenwerte wieder herzustellen,
wobei man von mehr als einer Position in den kodierten
Daten beginnt. In diesem Zusammenhang ist ein
invertierbarer Differenzoperator ein Operator, der einen Wert
erzeugt, der sich auf die Differenz zwischen benachbarten
Datenwerten bezieht, so daß es möglich ist, die originären
Datenwerte aus jeweils den originären Datenwerten und der
vorbestimmten Differenz zu regenerieren.
-
In einem Beispiel ermöglicht es der zusätzliche Datensatz,
daß die originären Datenwerte in einer Dimension aus jeder
der beiden entgegengesetzten Richtungen wieder hergestellt
werden können. In einem anderen Beispiel liegt die zweite
Position innerhalb der Anordnung, so daß ein Teil der
originären Datenwerte beginnend mit der zweiten Position
wieder hergestellt werden kann.
-
Das Verfahren kann in verschiedener Weise ausgeführt
werden. Beispielsweise sei angenommen, daß die
Originalanordnung der Datenwerte in jeder Dimension einen Satz bekannter
Werte (beispielsweise 0) hinzuaddiert bekommt, wobei die
Werte nicht die gleichen in jeder Dimension sein müssen und
der invertierbare Differenzoperator auf die Datenwerte
angewendet wird, die das Bild und die zusätzlichen Werte
definieren. Auf diese Weise ist es nicht erforderlich, einen
Anfangswert zu speichern, von dem aus die originären
Datenwerte
durch Umkehren der originären Operation wieder
hergestellt werden können, da diese originären Werte durch
Vorgabe bekannt sind. Andererseits kann ein Satz originärer
Datenwerte aufgezeichnet werden (komprimiert oder nicht
komprimiert) und wird dann für den Anfangsschritt benutzt,
um die kodierten Daten zu erzeugen, indem die Behandlung
mit dem invertierbaren Differenzoperator erfolgt und
nachfolgend dann, wenn die Daten aus jeder ersten Position
wieder hergestellt werden.
-
Die Zahl der Dimensionen N hängt vom Anwendungsgebiet ab,
wenn auch für Bilddaten die Zahl N typischerweise 2 oder 3
ist. Die Erfindung ist jedoch aufjede Zahl von Dimensionen
einschließlich 1 anwendbar.
-
Bei einem zweidimensionalen Bild erfolgt beispielsweise die
Behandlung mit dem invertierbaren Differenzoperator in der
Abfolge der Reihen und dann in den Spalten (oder umgekehrt)
der Anordnung.
-
Beispiele für passende invertierbare Differenzoperatoren
sind arithmetische Subtraktion (deren Umkehr eine
arithmetische Summe ist) und die exklusive ODER-Operation (deren
Umkehr ebenfalls die exklusive ODER ist).
-
Die Anwendung des invertierbaren Differenzoperators führt
normalerweise zu einer groben Zahl von gleichen Werten in
der kodierten Datenanordnung, die dann weiter komprimiert
werden kann, wobei man eine bekannte Technik beispielsweise
Lauflängenkodierung o.ä. benutzt.
-
Die Speichermittel können ein einzelner Speicher oder
mehrere getrennte Speicher sein.
-
Ein Beispiel eines Verfahrens und einer Vorrichtung gemäß
der Erfindung wird nun anhand der Zeichnung beschrieben. Es
zeigen:
-
Fig. 1 ein Blockschaltbild der Vorrichtung;
-
Fig. 2 bis 4 Bildteile in drei Stufen bei Ausführung des
Verfahrens und
-
Fig. 5 ein Flußdiagramm für die Betriebsweise der
Vorrichtung.
-
Die schematisch in Fig. 1 dargestellte Vorrichtung besitzt
einen Mikroprozessor 1, der an einen Datenbus 2
angeschlossen ist. Der Datenbus 2 ist an einen ersten Speicher
3, einen zweiten Speicher 4 und einen Zwischenspeicher 5
angeschlossen.
-
Zum Zwecke der Beschreibung soll eine 8 x 8 Anordnung von
Bildpixeln betrachtet werden. Die Anordnung in der
originären Form ist in Fig. 2 dargestellt, wobei der Farbgehalt
jedes Pixels mit dem Wert 1, 2 oder 3 bezeichnet ist. In
der Praxis reichen diese digitalen (dichte) Werte für eine
einzige Farbkomponente von 0 bis 255. Diese digitalen Werte
werden im ersten Speicher 3 anfänglich gespeichert, und
sind in bekannter Weise, beispielsweise mit einem Crosfield
Magnascan Scanner erzeugt worden.
-
Anfänglich hat der Mikroprozessor 1 Zugang zu jeder Reihe
der Datenwerte nacheinander und verwendet einen
Differenzoperator, der in diesem Fall eine einfache arithmetische
Subtraktion darstellt, um die Differenz zwischen jedem
Datenwert und dem entsprechenden Datenwert in der
vorhergehenden Reihe zu bestimmen. Um die erste und letzte Reihe
und Spalte zu kodieren, geht der Mikroprozessor 1 davon
aus, dar das Bild von Datenwerten gleich Null umgeben wäre,
wie dies außerhalb des 8 x 8 Quadrats in Fig. 2 gezeigt
ist. Somit gewinnt der Mikroprozessor 1 in einem
anfänglichen
Schritt Zugang zur ersten Reihe 11 aus dem ersten
Speicher 3 (Schritt 50) und bestimmt dann die Differenz
zwischen dem Datenwert jedes Pixels der ausgewählten Reihe
gegenüber dem Datenwert des entsprechenden Pixels in der
vorhergehenden Reihe. Im Falle der ersten Reihe wird der
Differenzwert für jedes Pixel auch 1 sein, wie in Reihe 21
der Fig. 3 (Schritt 51) dargestellt ist, da alle die Werte
gleich 1 sind und alle Werte in der vorhergehenden Reihe 10
gleich 0 sind.
-
Der Mikroprozessor 1 bestimmt dann, ob die letzte
bearbeitete Reihe die letzte Reihe im Bild ist (Schritt 52), und
wenn dies nicht der Fall ist, hat er Zugang zur nächsten
Reihe, in diesem Fall die Reihe 12 aus dem ersten Speicher
3 (Schritt 53). Schritt 51 wird dann wiederholt, aber in
diesem Fall wird die Differenz zwischen den Pixelwerten in
den Reihen 12 und 11 bestimmt, die in diesem Fall gleich 0
sein werden, wie für Reihe 22 in Fig. 3 dargestellt ist.
-
Dieser Vorgang wird dann für alle übrigen Reihen 13 bis 18
in dem Originalbild wiederholt und die jeweiligen in den
Reihen 21 bis 28 definierten Differenzwerte werden in den
Zwischenspeicher 5 abgespeichert.
-
Für den unten beschriebenen Zweck nimmt der Mikroprozessor
1 an, daß eine Extrareihe hinter dem Ende der Reihe 28
vorhanden ist, in der jedes Pixel einen bekannten Wert hat. In
diesem Fall sind alle Pixelwerte in dieser Extrareihe 19
gleich 0. Der Mikroprozessor 1 wiederholt dann die
Differenzoperation für diese letzte Reihe, um einen Satz von
Differenzwerten 29 zu erzeugen, die ebenfalls in dem
Zwischenspeicher 5 abgespeichert werden.
-
In der nächsten Stufe gewinnt der Mikroprozessor 1 Zugang
zur ersten Spalte 31 im zwischenspeicher und bestimmt die
Differenz zwischen den Pixelwerten in dieser Spalte und den
benachbarten Pixelwerten der vorhergehenden Spalte, von der
wie bei dem vorgenannten Verfahren für die Reihe 21
angenommen wird, dar ihre Werte bekannt, beispielsweise 0
sind. Diese Differenz wird für die acht Pixel in der Spalte
bestimmt, entsprechend den realen Datenwerten, und auch für
das neunte Pixel in der Reihe 29, um einen Satz
Differenzwerte in einer Spalte 41 (Fig. 4) zu erzeugen, die in dem
zweiten Speicher 4 gespeichert werden (Schritte 54, 55).
-
Der Mikroprozessor bestimmt dann, ob die letzte
verarbeitete Spalte in dem Zwischenspeicher (Schritt 56) die letzte
Spalte der Werte ist, und wenn nicht, so erfolgt der Zugang
zur nächsten Spalte der Werte aus dem Zwischenspeicher
(Schritt 57) und der Schritt 55 wird wiederholt. Somit
gewinnt in der nächsten Operation der Mikroprozessor den
Zugang zur Spalte 32 und bestimmt die Differenz zwischen
den Pixelwerten in dieser Spalte und der vorhergehenden
Spalte. Das Ergebnis dieser Differenzoperation ist mit der
Spalte der Werte 42 in Fig. 4 dargestellt. Aus Fig. 4 ist
ersichtlich, daß eine signifikante Mehrheit der letztlich
erzeugten Werte gleich Null ist und dies ermöglicht einen
signifikanten Grad der Datenkomprimierung, wobei mag
beispielsweise eine Lauflängenkodierung benutzt.
-
Wenn die originären Datenwerte der Fig. 2 wieder
hergestellt werden sollen, so kann dies in einem Verfahren
erfolgen, bei dem einfach die Differenzoperation umgekehrt
wird (d.h. ein Summiervorgang), wobei man in der oberen
linken Ecke der Anordnung in Fig. 4 beginnt. Das heißt, die
Wiederherstellungsoperation beginnt mit der gleichen ersten
Position wie die originäre Differentieroperation.
-
Wie vorstehend erläutert, ist es bei der Verarbeitung von
Bildern oft notwendig, daß Bildteile betrachtet werden, die
nicht zu dem Bildabschnitt gehören, für den die
Differenzierung begonnen wurde. So kann es beispielsweise in dem
vorliegenden Beispiel wünschenswert sein, die untersten
vier Reihen des Bildes zu betrachten. Bisher erforderte
dies, dar das gesamte Bild aus der anfänglichen ersten
Position beginnend in der oberen linken Ecke wieder
hergestellt werden mußte. Wie vorstehend beschrieben, ist aber
eine zusätzliche, redundante Reihe 60 von Differenzwerten
in dem zweiten Speicher 4 abgespeichert worden. Ungeachtet
der Tatsache, daß das Differenzverfahren in der oberen
linken Ecke der Anordnung begann, ermöglicht es die
zusätzliche Reihe 60, daß das Bild von rückwärts her beginnend
mit den Werten in der Reihe 60 wieder hergestellt wird. So
werden zuerst die Spalten 31, 32 wieder hergestellt, wobei
man mit den Daten in der Reihe 60 beginnt und weiß, daß
diese Reihe aus einem Satz bekannter Datenwerte (von denen
alle gleich Null waren) erzeugt worden war. Aus dem
teilweise wiederhergestellten Wertesatz in Fig. 3 können die
originären Werte der Fig. 2 wiederum hergestellt werden,
indem man die Differenzoperation umkehrt.
-
Ein anderer Grund für den Wunsch, die Daten in mehr als nur
einer Richtung wieder herzustellen, liegt darin, daß die
Daten auf einem Scheibenspeicher o.ä. gespeichert werden
können, derart, daß sie schneller wieder hergestellt
werden, beginnend mit der zusätzlichen Reihe von Werten 60 als
wenn man in der originären ersten Position beginnt.
-
Bei einem anderen Ausführungsbeispiel (nicht gezeigt) kann
der zusätzliche Datenwertesatz in dem Originalbild
eingebettet sein. Es sei beispielsweise der Fall betrachtet, in
dem bei einem größeren Bild die unterste Reihe 18 in Fig. 2
mehrfach in einer unteren Richtung wiederholt wird. In
diesem Fall kann der Mikroprozessor den Differenzoperator in
der vorgenannten Weise zwischen der Reihe 18 in Fig. 2 und
der künstlichen Reihe 19 wie auch zwischen der Reihe 18 und
der nächsten realen Reihe (nicht gezeigt) anwenden. Die
Anwendung des Differenzoperators aufdie Reihen 18, 19
erzeugt zusätzliche Werte, wie sie in Reihe 60 der Fig. 4
dargestellt sind, und dies kann entweder dazu benutzt
werden, einen Teil des originalbildes herzustellen oder zur
Überprüfung, ob das Wiederherstellungsverfahren in genauer
Weise abläuft. Dieses letztere Merkmal kann man erhalten,
wenn man die während der normalen Wiederherstellung aus
einer Endreihe des Bildes (nicht gezeigt) erzeugten Werte
der Reihe 18 mit denen vergleicht, die beim
Wiederherstellen aus der künstlich erzeugten Reihe 19 erzeugt werden.