DE69504982T2 - Kompressions- und expansionsalgorithmus mit verlusten für bilddarstellungsdaten - Google Patents

Description

• Die vorliegende Erfindung betrifft einen verlustbehafteten Algorithmus zur Verwendung beim Komprimieren und Dekomprimieren von Bilddarstellungsdaten.
• Es ist häufig notwendig, Bildinformationen von einer Stelle zu einer anderen zu übertragen oder zu speichern. Beispielsweise werden bei einem Faksimileübertragungssystem Bildinformationen über Telefonleitungen von einem Sender an einen Empfänger übertragen. Weil zur Darstellung von Bildern große Datenmengen erforderlich sind, hat es sich als notwendig ergeben, die Bilddarstellungsdaten beim Sender zu komprimieren, um die Übertragungszeit zu verkürzen, und dann die empfangenen Daten beim Empfänger zu dekomprimieren, um das Bild wiederherzustellen. Ein anderes Beispiel sind Datenverarbeitungssysteme, die heute Bildverarbeitungsmöglichkeiten bieten, um z. B. in Büros den Papierverbrauch so klein wie möglich zu halten. Bei solchen Datenverarbeitungssystemen ist es notwendig, Bilder darstellende Informationen in einer Speichervorrichtung des Datenverarbeitungssystems zu speichern. Um den zum Speichern solcher Bilder notwendigen Speicherplatz so klein wie möglich zu halten, hat es sich als vorteilhaft erwiesen, die Bilddarstellungsdaten zu komprimieren und die komprimierten Daten in der Speichervorrichtung zu speichern. Wenn das Bild benötigt wird, werden die komprimierten Daten aus der Speichervorrichtung wiedergewonnen, dekomprimiert und vom Datenverarbeitungssystem weiterverarbeitet, z. B. an einem Anzeigegerät angezeigt.
• Zum Komprimieren und Dekomprimieren von Schwarz/Weiß- Bildern gibt es mehrere bestehende Algorithmen, z. B. Packbits, CCITT G3 und G4, JBIG usw. Alle diese Algorithmen komprimieren Bilder unter Beibehaltung aller bildbezüglichen Informationen. Das heißt, ein Bild kann mit irgendeinem dieser Algorithmen komprimiert und dann dekomprimiert werden, und das wiederhergestellte Bild wird eine exakte Kopie des Ausgangsbildes sein. Weil keine Bildinformation verlorengeht, werden solche Algorithmen als verlustlose Kompressionsalgorithmen bezeichnet.
• Das am 15. Nov. 1977 an Komura erteilte US-Patent 4,058,674: GRAPHIC INFORMATION COMPRESSION METHOD AND SYSTEM (Verfahren und System zum Komprimieren grafischer Informationen) offenbart einen verlustlosen Kompressionsalgorithmus. Bei diesem Patent wird jede Leerzeile in den zu komprimierenden Bilddarstellungsdaten durch eine logische '0' dargestellt, wogegen nichtleere Zeilen durch eine logische '1' dargestellt werden, der die Daten auf dieser Zeile darstellende Daten folgen.
• In einigen Fällen ist es jedoch möglich, daß einige Bildinformationen verlorengehen, ohne daß der Übertragungsprozeß beeinträchtigt wird. Bei Faksimileübertragungen, beispielsweise, und Büro-Bildprozessoren sind für die Anwender üblicherweise mehr die durch das Bild, z. B. eine maschinengeschriebene Nachricht, dargestellten Informationen wichtig als die Formtreue des reproduzierten Bildes im Vergleich zum Originalbild. Das heißt, solange der Empfänger der Faksimilenachricht oder der Betrachter des wiedergewonnenen Bildes eines maschinegeschriebenen Schriftstücks die Nachricht lesen kann, wird es als erfolgreich betrachtet, selbst wenn die reproduzierten Bilder nicht exakt wie die Buchstaben im Originalbild aussehen. In solchen Systemen ist es somit möglich, verlustlose Kompressionsalgorithmen zu verwenden, ohne daß die Anwender eine Leistungsverschlechterung empfinden.
• Es ist ferner bekannt, daß ein verlustbehafteter Bild- Kompressions/Dekompressionsalgorithmus im allgemeinen ein Bild in weniger Daten komprimiert als ein verlustloser Algorithmus. Bei einer solchen. Verkleinerung der Menge der Bilddarstellungsdaten kann ein Bild in kürzerer Zeit übertragen werden, wodurch die Telefongebühren für eine solche Übertragung verringert werden. Ein Anwender wird somit eine Leistungsverbesserung, z. B. kürzere Übertragungszeiten und niedrigere Telefonrechnungen bei einem Bildübertragungssystem empfinden, das einen verlustbehafteten Algorithmus verwendet, im Vergleich zu einem einen verlustlosen Algorithmus verwendenden System. Somit ist ein verlustbehafteter Bild-Kompressions/Dekompressionsalgorithmus bei Systemen wünschenswert, bei denen eine gewisse Bildverschlechterung akzeptabel ist.
• In dem am 28. Juli 1981 an Knudson erteilten US-Patent 4,281,312: SYSTEM TO EFFECT DIGITAL ENCODING OF AN IMAGE (System zum digitalen Codieren eines Bildes) ist ein verlustbehafteter Bild-Kompressionsalgorithmus dargestellt. Gemäß diesem Patent werden zu komprimierende Bilddarstellungsdaten in Blöcke von acht Zeilen zu acht Pixeln unterteilt. Jeder Block wird mit einem Satz von 64 Mustern, je mit 8 Zeilen zu 8 Pixeln und vorbestimmten Mustern bitweise verglichen. Für das Muster, das dem Bilddaten- Block am nächsten kommt, wird ein Code ausgegeben. In dieser Weise wird jeder Block codiert.
• Gemäß den Merkmalen der vorliegende Erfindung umfaßt ein Verfahren zum Komprimieren rasterstrukturierter Quellen- Bilddarstellungsdaten die nachstehend angegebenen Schritte: Die Quellen-Bilddarstellungsdaten werden in eine erste Vielzahl Abschnitte unterteilt, die je nur leere Zeilen enthalten, und in eine zweite Vielzahl Abschnitte, die je nichtleere Bilddarstellungsdaten enthalten. Jeder Abschnitt in der ersten Vielzahl Abschnitte wird durch ein zugehöriges Leerzeilen-Codewort dargestellt. Jeder Abschnitt in der zweiten Vielzahl Abschnitte wird weiter in eine Vielzahl Blöcke unterteilt, die je L Zeilen zu P Pixeln und ein Muster aufweisen. Bei jedem abgeteilten Block wird ein Codevektor aus einer Vielzahl V Codevektoren, je von L Zeilen zu P Pixeln und einem vorbestimmten Muster, gewählt, der mit dem Muster des abgeteilten Blokkes am besten übereinstimmt. Jeder abgeteilte Block ist durch ein zugehöriges Nichtleer-Codewort dargestellt, das den gewählten. Codevektor aus der Vielzahl Codevektoren darstellt. Somit ist das komprimierte Bild durch aufeinanderfolgende Codewörter dargestellt, die entweder Leerzeilen oder Codevektoren darstellen.
• Ein Verfahren zum Dekomprimieren des durch die aufeinanderfolgenden Codewörter dargestellten komprimierten Bildes umfaßt die nachstehend angegebenen Schritte: Es werden Leerzeilen in rasterstrukturierte, reproduzierte Bilddarstellungsdaten in Abhängigkeit von Leerzeilen- Codewörtern eingefügt. Das Muster des durch jedes Nichtleer-Codewort dargestellten Codevektors wird in die rasterstrukturierten, reproduzierten Bilddarstellungsdaten in Abhängigkeit von jedem Nichtleer-Codewort eingefügt. Diese Dekompression führt zu einem rasterstrukturierten reproduzierten Bild.
• In den Zeichnungen zeigt:
• Fig. 1 ein Blockschaltbild eines Faksimileübertragungssystems, das eine erfindungsgemäße Bildkompression/Bilddekompression verwendet,
• Fig. 2 ein Blockschaltbild eines Datenverarbeitungssystems, das eine erfindungsgemäße Bildkompression/Bilddekompression verwendet,
• Fig. 3 ein Flußdiagramm mit einer Darstellung des erfindungsgemäßen Verfahrens zum Komprimieren von Bilddarstellungsdaten,
• Fig. 4 ein Diagramm eines Bildes mit einer Darstellung des Prozesses zum Unterteilen eines Bildes in Blöcke,
• Fig. 5 ein Diagramm mit der Darstellung eines Beispiels eines Codelexikons zur Verwendung beim erfindungsgemäßen Komprimieren eines Bildes, und
• Fig. 6 ein Flußdiagramm mit der Darstellung des erfindungsgemäßen Verfahrens zum Dekomprimieren zuvor komprimierter Bilddarstellungsdaten.
• Fig. 1 zeigt ein Blockschaltbild eines Faksimileübertragungssystems 10, das die erfindungsgemäße Bildkompression/Bilddekompression verwendet. Gemäß Fig. 1 ist ein Bild 5, das als Hartkopie dargestellt ist, z. B. ein Schriftstück, ein Bild, von einem Sender 20 über ein Übertragungsmedium 40, z. B. Telefonleitungen, an einen Empfänger 50 zu übertragen, um ein entsprechendes Bild 5' zu erzeugen. Gemäß Fig. 1 wird das das Ausgangsbild 5 enthaltende Schriftstück dem Sender 20 bereitgestellt, der die Serienschaltung eines Scanners 22 mit einem Speicher 24, einem Bildkomprimierer 26 und einem Huffman-Codierer 28 umfaßt. Das sich ergebende, das Bild darstellende Signal wird auf das Übertragungsmedium 40 gegeben.
• Das zuvor übertragene, das Bild darstellende Signal wird über das Übertragungsmedium 40 vom Empfänger 50 empfangen, der die Serienschaltung eines Huffman-Decodierers 52 mit einem Bilddekomprimierer 54, einem Speicher 56 und einem Drucker 58 umfaßt. Der Drucker 58 erzeugt eine Hartkopie, z. B. ein Schriftstück, das ein dem ursprünglich übertragenen Bild 5 entsprechendes Bild 5' enthält. Der Bildkomprimierer 26 im Sender 20 und der Bilddekomprimierer 54 im Empfänger 50 verwenden je ein Codelexikon 30 zum Komprimieren bzw. Dekomprimieren der Bilddarstellungsdaten. Das Codelexikon 30 im Sender 20 ist mit dem Codelexikon 30 im Empfänger identisch, wie dies in Fig. 1 durch die die beiden Codelexika verbindenden gestrichelten Linien dargestellt ist.
• Die Arbeitsweise ist folgende: Der Scanner 22 verarbeitet in bekannter Weise die Hartkopie des Bildes 5 und erzeugt ein Signal, welches das Bild in Form eines Pixelrasters darstellt. Bei der dargestellten Ausführungsform können die Pixel zwei Zustände annehmen, d. h. sie stellen entweder ein schwarzes oder ein weißes Pixel dar. Es ist möglich, daß jedes Pixel ein Grauskalen- oder ein Farbpixel darstellt. Der Pixelraster wird, ebenfalls in bekannter Weise, im Speicher 24 gespeichert. Der gespeicherte Pixelräster wird vom Bildkomprimierer 26 in Verbindung mit dem Codelexikon 30 verarbeitet, um ein Signal zu erzeugen, welches das Bild in komprimierter Form darstellt. Das das komprimierte Bild darstellende Signal hat die Form einer Folge von die Daten darstellenden Codewörtern. Die Art und Weise, wie die zuvor gespeicherten Bilddarstellungsdaten aus dem Speicher 24 komprimiert werden, wird weiter unten näher beschrieben. Die Folge von Codewörtern wird durch den Huffman-Codierer 28 in bekannter Weise codiert. Wenngleich ein Huffman-Codierer 28 dargestellt ist, kann auch jeder beliebige Codierer verwendet werden, der auf der Grundlage der Wahrscheinlichkeit des Auftretens dieses Codewortes in der Nachricht Codewörter von kleinstmöglicher Größe und veränderbarer Länge erzeugt (in dieser Anmeldung als Wahrscheinlichkeitscodierer bezeichnet). Beispielsweise kann auch ein bekannter arithmetischer Codierer verwendet werden. Die Folge von Huffman-Codes wird in bekannter Weise auf das Übertragungsmedium 40 gegeben. Wenn das Übertragungsmedium 40 z. B. eine Telefonverbindung ist, werden die Huffman-Codes von einem Modem in Audiotone übersetzt.
• Eine entsprechende Verbindung zum Übertragungsmedium 40, z. B. ein weiteres Modem, ist im Empfänger 50 vorgesehen. Die empfangenen Huffman-Codes werden vom Huffman-Decodierer 52 decodiert, um die Folge von Codewörtern zu erzeugen, die zuvor vom Bildkomprimierer 26 generiert worden sind. (Wie zuvor, kann ein beliebiger, dem Codierer 28 entsprechender Wahrscheinlichkeitsdecodierer verwendet werden.) Diese Codewörter werden in bekannter Weise vom Bilddekomprimierer 54 in Verbindung mit dem Codelexikon 30 verarbeitet, um ein Pixelraster im Speicher 56 zu erzeugen. Die Art und Weise, in der die Folge empfangener Codewörter in ein Pixelraster im Speicher 56 dekomprimiert wird, wird weiter unten näher beschrieben. Der Drucker 58 verarbeitet das Pixelraster und druckt das durch das Pixelraster dargestellte Bild 5' aus.
• Die vom Bildkomprimierer 26 und dem Biddekomprimierer 54 ausgeführte Kompression bzw. Dekompression ist verlustbehaftet. Das heißt, das reproduzierte Bild 5' ist mit dem ursprünglich abgetasteten Bild 5 nicht identisch. Jedoch ist die Datenmenge, die zum Übertragen des Bildes benötigt wird, verringert gegenüber der zum Übertragen einer exakten Kopie des ursprünglich abgetasteten Bildes benötigten, woraus sich kürzere Übertragungszeiten und niedrigere Telefonkosten ergeben.
• Wenngleich das in Fig. 1 dargestellte System ein Faktsimilesystem ist, könnte es zum Speichern eines Bildes be nutzt werden, wenn das Übertragungsmedium als eine Massenspeichervorrichtung betrachtet wird, wie ein bekanntes Platten- oder Bandlaufwerk. Bei einem solchen System würde in bekannter Weise eine Platten- oder Bandsteuerung die Huffman-Codes vom Huffman-Codierer 28 empfangen und sie an einer vorgegebenen Stelle auf der Platte oder dem Band speichern. Wenn ein Bild gewünscht wird, würden die zuvor gespeicherten Huffman-Codes, die dieses Bild darstellen, von der vorgegebenen Stelle auf der Platte oder dem Band ebenfalls in bekannter Weise abgerufen und an den Empfänger 50 zugeleitet werden:
• Das Bildkompressionssystem gemäß Fig. 1 ist als in einem Faksimileübertragungssystem 10 ausgeführtes System dargestellt; es kann auch in einem Datenverarbeitungssystem ausgeführt sein. Fig. 2 ist ein Blockschaltbild eines Datenverarbeitungssystems, das die erfindungsgemäße Bildkompression/Bilddekompression verwendet. In Fig. 2 sind Bauteile, die ähnlichen Bauteilen in Fig. 1 entsprechen, mit denselben Bezugszeichen bezeichnet und werden nicht im einzelnen beschrieben.
• Gemäß Fig. 2 umfaßt ein Datenverarbeitungssystem 60 eine Zentraleinheit (CPU; Abk. f. engl. central processing unit) 62, einen Lese/Schreib-Speicher (RAM; Abk. f. engl. random access memory) 64 und einen Nur-Lese-Speicher (ROM; Abk. f. engl. read only memory) 66, die in bekannter Weise durch einen Systembus 68 miteinander verbunden sind. Das Datenverarbeitungssystem 60 umfaßt ferner den Scanner 22, der entsprechend der Darstellung die Hartkopie des Bildes 5 empfängt, und einen Drucker 58, der ent sprechend der Darstellung eine Hartkopie des entsprechenden Bildes 5' erzeugt, und die beide in bekannter Weise an den Systembus 68 angeschlossen sind. Das Datenverarbeitungssystem 60 enthält ferner, in bekannter Weise, einen Massenspeicheradapter 70, der ein Plattenlaufwerk 72 mit dem Systembus 68 verbindet, einen Anzeigeadapter 80, der ein Anzeigegerät 82 mit dem Systembus 68 verbindet, und einen Telefongesellschafts(TELCO)-Adapter 42, der das Telefonsystem als das Übertragungsmedium 40 mit dem Systembus 68 verbindet.
• Die Arbeitsweise ist folgende: Die CPU 62 fragt Befehle aus dem ROM 66 und/oder dem RAM 64 ab und führt sie aus, um Daten aus dem ROM 66 und/oder dem RAM 64 zu lesen, Daten in den RAM 64 zu schreiben und Daten je nach Fall an Eingabe/Ausgabe-Adapter (d. h. Scanner 22, Massenspeicheradapter 70, Drucker 58, Anzeigeadapter 80 und Telco-Adapter 42) in bekannter Weise über den Systembus 68 zu übertragen oder von ihnen zu empfangen. Gemäß Fig. 2 verarbeitet der Scanner 22 die Hartkopie 5, die das Bild enthält, und speichert den das Bild darstellenden Pixelraster im RAM 64, gesteuert durch die CPU 62. Die CPU 62 liest den Pixelraster aus dem RAM 64 und verarbeitet ihn, um eine Folge von Codewörtern in Verbindung mit dem Codelexikon 30 (gemäß Fig. 1) zu erzeugen. Das Codelexikon 30 kann im ROM 66 permanent gespeichert sein oder kann auf dem Plattenlaufwerk 72 gespeichert sein und mit Steuerung durch die CPU 62 in den RAM 64 abgerufen werden. Die CPU 62 kann die Codewörter vorübergehend im RAM 64 oder auf der Platte 72 speichern oder sie bei ihrer Erzeugung in eine Folge von Huffman-Codes verarbeiten, die das kompri mierte Bild darstellen. Die Folge von Huffman-Codes kann in einer Datei auf der Platte 72 gespeichert und/oder an den Telefongesellschafts-Adapter 42 geliefert werden, um sie über das Übertragungsmedium 40 an eine entfernte Stelle zu übertragen.
• Eine Folge von Huffman-Codes, die ein komprimiertes Bild darstellen, kann über den Telefongesellschafts-Adapter 42 von einer entfernten Stelle empfangen werden, oder es kann eine zuvor gespeicherte Datei von Huffman-Codes vom Plattenlaufwerk 72 abgerufen werden. Vom Telefongesellschafts-Adapter 42 empfangene Huffman-Codes können auf dem Plattenlaufwerk 72 gespeichert werden. Die empfangenen oder wiedergewonnenen Huffman-Codes können auch im RAM 64 gespeichert werden. Die CPU 62 führt eine Huffman- Decodierung der Huffman-Codes aus, um eine Folge von Codewörtern zu erzeugen. Diese Codewörter können im RAM 64 gespeichert, auf dem Plattenlaufwerk 72 vorübergehend gespeichert oder im Zuge ihrer Erzeugung verarbeitet werden. Die CPU 62 verarbeitet dann die Codewörter, um ein Pixelraster im RAM 64 zu erzeugen, der das empfangene oder wiedergewonnene Bild darstellt. Auch hier kann das Codelexikon 30 im ROM 66 permanent oder in einer Datei auf dem Plattenlaufwerk 72 gespeichert sein. Der Pixelraster im RAM 64 kann vom Drucker 58 in bekannter Weise ausgedruckt werden, um ein dem ursprünglichen Bild 5 entsprechendes Hartkopie-Bild 5' zu erzeugen, oder er kann am Anzeigegerät 82 als grafische Darstellung 5" angezeigt werden.
• Hinsichtlich der Datenkompression/Datendekompression ist die Arbeitsweise entsprechend Fig. 2 der des in Fig. 1 dargestellten Systems ähnlich, bietet aber mehr Flexibilität bezüglich der Übertragung, der Speicherung und des Empfangs von Bilddarstellungsdaten. Beispielsweise kann das Datenverarbeitungssystem gemäß Fig. 2, ohne den Massenspeicheradapter 70 und das Plattenlaufwerk 72 sowie den Anzeigeadapter 80 und das Anzeigegerät 82 als Faksimilesystem 10, wie in Fig. 1 dargestellt, verwendet werden. Alternativ kann ein Faksimilesystem 10 mit einer Möglichkeit zur Massenspeicherung und Anzeige hergestellt werden, um zusätzliche Funktionsfähigkeiten im Vergleich zu Standard-Faksimilesystemen zu erreichen. Mit dieser Möglichkeit können abgetastete und empfangene Bilder komprimiert und auf dem Plattenlaufwerk 72 gespeichert werden, um später abgerufen zu werden. Auch können abgetastete, gespeicherte und empfangene komprimierte Bilder dekomprimiert und am Anzeigegerät 82 angezeigt werden, möglicherweise unter Entbehrlichmachung einer Hartkopie vom Drucker 58. Alternativ kann das Datenverarbeitungssystem gemäß Fig. 2 in ein Standard-Datenverarbeitungssystem, z. B. einen Personalrechner eingegliedert werden, um das Abtasten von Hartkopie-Bildern, das Speichern der Bilder im komprimierter Form, das Anzeigen und/oder das Druckens der durch die zuvor gespeicherten komprimierten Bilder dargestellten Bilder und das Übertragen und/oder das Empfangen der Bilder in komprimierter Form zu ermöglichen.
• Fig. 3 zeigt ein Flußdiagramm mit der Darstellung eines erfindungsgemäßen Verfahrens 100 zum Komprimieren von Bilddarstellungsdaten. Fig. 4 zeigt ein Diagramm eines Bildes mit der Darstellung des Prozesses zum Unterteilen eines Bildes in Blöcke, und Fig. 5 zeigt ein Diagramm mit der Darstellung eines Beispiels eines Codelexikons 30 zur Verwendung beim erfindungsgemäßen Komprimieren eines Bildes. Fig. 4 und 5 sind für das Verständnis der Arbeitsweise des in Fig. 3 dargestellten Verfahrens 100 zum Komprimieren eines Bildes nützlich. Das in Fig. 3 dargestellte Verfahren 100 wird durch den Bildkomprimierer 26 (gemäß Fig. 1) oder durch die CPU 62 (gemäß Fig. 2) ausgeführt.
• Gemäß Fig. 3 ist der Schritt 102 der Beginn des Bildkompressionsverfahrens 100. Im Schritt 104 wird das Bild in bekannter Weise im Speicher 24 oder dem RAM 64 als Raster von Schwarz/Weiß-Pixeln gespeichert. In Fig. 4 ist ein solcher Pixelraster dargestellt. In Fig. 4 stellt das große Rechteck 300 den Raster von Schwarz/Weiß-Pixeln dar, der aus einer Vielzahl Zeilen besteht. Jede Zeile in Fig. 4 ist durch einen waagerechten Streifen dargestellt. Jede Zeile enthält ihrerseits eine Vielzahl vertikal ausgerichteter Pixel, die je einen von zwei möglichen Zuständen, schwarz oder weiß, dieses Pixels im Bild 5 darstellen. Jedes Pixel in Fig. 4 ist durch ein Quadrat dargestellt. Zur Vereinfachung der Fig. 4 ist nicht jedes Pixel in jeder Zeile dargestellt. Statt dessen ist nur ein Teil der Pixel dargestellt. In Abschnitten 304 und 308 sind einzelne Pixel durch zugehörige Quadrate dargestellt. In Abschnitten 302, 306 und 310 sind nur Zeilen dargestellt, aber es versteht sich, daß alle Zeilen in allen Abschnitten die gleiche Anzahl Pixel wie die in den Abschnitten 304 und 308 dargestellten Zeilen aufweisen.
• Sobald aus dem Bild ein Rasterbild erzeugt worden ist, wird es zeilenweise von oben nach unten und jede Zeile pixelweise von links nach rechts verarbeitet. Insbesondere beginnt die Verarbeitung in der obersten Zeile gemäß der Darstellung in Fig. 4. Im Schritt 106 gemäß Fig. 3 werden leere Zeilen, das sind Zeilen nur mit weißen Pixeln, ermittelt. Wenn im Schritt 106 eine leere Zeile festgestellt wird, wird im Schritt 108 die Anzahl aufeinanderfolgender leerer Zeilen gezählt. Gemäß Fig. 4 sind die obersten sieben Zeilen, im Abschnitt 302, leere Zeilen. Das Ergebnis des Schrittes 108 ist somit 7. Sobald die Anzahl aufeinanderfolgender leerer Zeilen ermittelt worden ist, wird im Schritt 110 ein Leerzeilen-Codewort ausgegeben, das die Anzahl der leeren Zeilen darstellt.
• Für die Anzeige von leeren Zeilen können mehrere alternative Codierverfahren angewandt werden. Bei einem Verfahren ist ein erstes Bit eines Leerzeilen-Codewortes "0" (oder alternativ "1"), der eine feststehende Anzahl Bit folgt, welche die Anzahl der leeren Zeilen, als Binärzahl codiert, enthalten. Beispielsweise ist bei einem 8-Bit- Codewort die feststehende Bitanzahl 7 Bit; somit können durch ein einziges Codewort bis zu 128 auf einanderfolgende Leerzeilen dargestellt werden. Beispielsweise ist für das in Fig. 4 dargestellte Bild das erste ausgegebene Codewort bei Anwendung dieses Codierverfahrens 00000111&sub2;. Bei einem anderen alternativen Codierverfahren kann aus einer feststehenden Anzahl vorbestimmter 6-Bit-Codewörter (die weiter unten näher beschrieben werden) eines als Leerzeilen-Codewort reserviert werden, dem ebenfalls eine feststehende Anzahl Bit folgt, welche die Anzahl der aufeinanderfolgenden, durch dieses Codewort dargestellten Leerzeilen enthält. Bei dem weiter unten näher zu beschreibenden Beispiel gibt es 64 vorbestimmte Codewörter, die durch ein binäres 6-Bit-Kennzeichen gekennzeichnet sein können. Wenn das letzte Codewort (d. h. das Codewort 63) angewählt wird, um leere Zeilen darzustellen, und dem auch hier ein 7-Bit-Wort folgt, das die Anzahl der leeren Zeilen darstellt, dann ist das für das in Fig. 4 dargestellte Bild bei Anwendung dieses Codierverfahrens ausgegebene erste Codewort (oder genauer gesagt, Codewort- Folge) 111111&sub2;, 0000111&sub2;. Wenn mehr aufeinanderfolgende Leerzeilen vorhanden sind, als mit einem einzelnen Codewort dargestellt werden kann, wird bei jedem dieser beiden Verfahren ein erstes Codewort ausgegeben, um die maximale Anzahl Leerzeilen darzustellen, und ein zweites Codewort, um die übrigen Leerzeilen darzustellen. Zum Darstellen einer beliebigen Anzahl aufeinanderfolgender Leerzeilen kann jede beliebige Anzahl sequentieller Leerzeilen-Codewörter ausgegeben werden.
• Im Schritt 112 wird geprüft, ob das Ende des Bildes erreicht worden ist, d. h. ob die unterste Zeile verarbeitet worden ist. Wenn keine Zeilen mehr zu verarbeiten sind, ist der Kompressionsprozeß durchgeführt und endet im Schritt 124. Wenn jedoch mehr vom Bild zu komprimieren übrig ist, wird erneut in den Schritt 106 eingetreten.
• In Fortsetzung des Beispiels ist die achte Zeile des in Fig. 4 dargestellten Bildes nicht leer (andernfalls wäre sie in das Leerzeilen-Codewort aufgenommen worden, das zuvor im Schritt 110 ausgegeben worden ist). Es wird somit in den Schritt 114 übergegangen. Im Schritt 114 wird das Bild in eine Anzahl L Zeilen unterteilt. Diese Zeilenanzahl wird im restlichen Teil dieser Anmeldung als Band bezeichnet. Beim dargestellten Beispiel beträgt L = 8. Somit bilden beim dargestellten Beispiel die nächsten acht Zeilen, der Abschnitt 304, das unterteilte Band.
• Im Schritt 116 wird das zuvor im Schritt 114 unterteilte Band, der Abschnitt 304, in Blöcke unterteilt, die in jeder der L Zeilen im zuvor unterteilten Band je aus P vertikal ausgerichteten Pixeln bestehen. Diese rechtwinklige Anordnung von L Zeilen mal P Pixeln in jeder Zeile wird im restlichen Teil dieser Anmeldung als Block bezeichnet. Beim dargestellten Beispiel beträgt P = 8. Somit wird durch die Blöcke 114 und 116 eine quadratische Anordnung von 8 Zeilen mal 8 Pixeln unterteilt. Weil das Bild von links nach rechts verarbeitet wird, ist der erste unterteilte Block das im Abschnitt 304 gemäß Fig. 4 am weitesten links angeordnete Quadrat, das von dicken Linien umrandet dargestellt und in der Mitte mit "BLOCK" bezeichnet ist.
• Im Schritt 118 wird der Codevektor, der dem in den Blökken 114 und 116 unterteilten Block BLOCK am nächsten kommt, aus dem Codelexikon 30 (gemäß Fig. 1) ausgewählt. Im allgemeinen enthält ein Codelexikon 30 eine vorbestimmte Anzahl V Codevektoren. Die Zahl V ist vorzugswei se eine Potenz von 2, d. h. V = 21, worin i eine ganze Zahl ist, obwohl ein oder mehrere Codevektoren, wie weiter oben angedeutet und weiter unten näher beschrieben, für andere Zwecke reserviert sein können. Jeder Codevektor ist eine rechteckige Anordnung mit L Zeilen, von denen jede P vertikal ausgerichtete Pixel enthält, d. h. jeder Codevektor hat dieselben Abmessungen wie ein unterteilter Block im Bild 5. Jedes Pixel im Codevektor kann entweder schwarz oder weiß sein.
• In Fig. 5 ist ein Muster-Codelexikon zur Verwendung mit dem vorliegenden Beispiel dargestellt. Beim dargestellten Beispiel sind L = 8 und P = 8 (z. B. die Größe der unterteilten Blöcke) und V = 64 (d. h. 26). Das heißt, das Codelexikon 30 enthält 64 8 · 8-Codevektoren. Wie weiter oben beschrieben, sind ein Codewort und sein zugeordneter Codevektor für die Angabe von Leerzeilen reserviert, somit stehen nur 63 Codevektoren zum Komprimieren der Bilddarstellungsdaten zur Verfügung. In Fig. 5 sind 63 Blöcke von 8 Zeilen zu 8 Pixel dargestellt. Jeder ist mit einem Index von 0 bis 62 gekennzeichnet, der unter dem Codevektor selbst angegeben ist. Im Schritt 118 wird der aktuell unterteilte Block des Bildes 5 mit allen in Fig. 5 dargestellten Codevektoren verglichen, und unter allen Codevektoren wird der am nächsten kommende Codevektor in einem als binäre Vektorquantisierung bekannten Prozeß ausgewählt. Der Zweck ist die Feststellung des Codevektors, dessen Muster dem Muster des unterteilten Blocks am nächsten kommt.
• Ein Verfahren zum Durchführen dieses Vergleichs ist beispielsweise das Vergleichen entsprechender Pixel des unterteilten Blocks und des Codevektors und das genaue Zählen der Anzahl übereinstimmender Pixel. Der Zählstand wird zuerst auf Null gesetzt. Sodann wird das am weitesten links stehende Pixel in der oberen Zeile des ersten Codevektors mit dem am weitesten links stehenden Pixel in der oberen Zeile des unterteilten Blocks verglichen. Sind sie gleich (d. h. sind beide schwarz oder beide weiß), wird dem Zählstand eins hinzugefügt. Sind sie verschieden (d. h. eines ist schwarz, das andere weiß), bleibt der Zählstand unverändert. Sodann wird das zweite Pixel in der oberen Zeile des Codevektors und im unterteilten Block auf ähnliche Weise verglichen und so fort für jedes Pixel in jeder Zeile. Der Endzählstand nach dem Vergleichen aller Pixel ist ein Maß für die Nähe des Codevektormusters zum Muster des unterteilten Blocks. Dieser Zählstand kann von 0, was bedeutet, daß keines der Pixel übereinstimmt (d. h. der Codevektor ist ein fotografisches Negativ des unterteilten Blocks) bis 64 reichen, was bedeutet, daß der Codevektor eine exakte Kopie des unterteilten Blocks ist. Für jeden der in Fig. 5 dargestellten 63 Codevektoren wird eine getrennte Zählung vorgenommen. Der Codevektor mit dem höchsten Zählstand wird als der am nächsten kommende Codevektor gewählt. Teilen sich mehrere den höchsten Zählstand, kann ein beliebiger von ihnen als der am nächsten kommende gewählt werden. Andere Verfahren zum Bestimmen der Nähe der entsprechenden Codevektoren zum unterteilten Block sind möglich und können in der vorliegenden Erfindung angewandt werden.
• Im Schritt 120 wird die Kennzeichnungs(ID)-Nummer des Codevektors, der im Schritt 118 als der dem unterteilten Block am nächsten kommende gewählt worden ist, als das diesen Block darstellende Codewort ausgegeben. Wie weiter oben angegeben, gibt es zwei mögliche Verfahren zum Ausgeben von Codewörtern. Wie weiter oben beschrieben, weisen beim ersten Verfahren Codewörter, die leere Zeilen darstellen (und im Schritt 110 ausgegeben werden), ein erstes Bit auf, das eine "0" (oder eine "1") ist. Umgekehrt haben Codewörter, die Codevektoren darstellen, ein erstes Bit, das eine "1" (oder eine "0") ist, dem die ID- Nummer des gewählten Codevektors, ausgedrückt als Binärzahl, folgt. Beim vorliegenden Beispiel können die ID- Nummern der 64 Codevektoren durch 6-Bit-Binärzahlen dargestellt werden. Somit haben Codewörter, die unterteilte Blöcke darstellen, sieben Bit: eine führende "1" (oder "0"), der sechs ID-Bit folgen. Wenn z. B. der am nächsten kommende Codevektor als der Codevektor mit der ID 27 ermittelt wird, dann lautet das ausgegebene Codewort für diesen unterteilten Block 1011011&sub2;.
• Beim zweiten Verfahren wird eine der Codevektor-ID-Nummern (z. B. 63) für die Angabe von Leerzeilen reserviert. Nur die übrigen 63 Codevektoren weisen Muster auf, die mit den unterteilten Blöcken verglichen werden. Bei diesem Beispiel weisen unterteilte Blöcke darstellende Codewörter sechs Bit auf. Wenn beispielsweise als der am nächsten kommende Codevektor der mit der ID-Nummer 27 festgestellt wird (sh. oben), dann lautet das ausgegebene Codewort für diesen unterteilten Block 011011&sub2;.
• Im Schritt 122 gemäß Fig. 3 wird geprüft, ob der letzte (am weitesten rechts stehende) Block des zuvor unterteilten Bandes verarbeitet worden ist. Wenn nein, wird erneut der Schritt 116 aufgerufen, um den nächsten Block zu unterteilen und zu verarbeiten. In Fortsetzung des vorliegenden Beispiels wird, wie weiter oben im einzelnen beschrieben, nach dem Verarbeiten des am weitesten links stehenden Blocks BLOCK der nach rechts nächste Block (der in Fig. 4 ebenfalls mit dickeren Linien umrahmt ist) unterteilt und durch Wählen des am nächsten kommenden Vektors und Ausgeben der ID-Nummer des am nächsten kommenden Codevektors verarbeitet. Der diesem unterteilten Block am nächsten kommende Codevektor kann z. B. die ID-Nummer 10 haben. Für diesen unterteilten Block ist daher das ausgegebene Codewort entweder 0001010&sub2; bei 7-Bit Codewörtern oder 001010&sub2; bei 6-Bit-Codewörtern. Auf ähnliche Weise wird eine Folge von Codewörtern ausgegeben, die alle unterteilten Blöcke im unterteilten Band darstellen, die von links nach rechts verarbeitet worden sind. Nach dem Verarbeiten des am weitesten rechts stehenden Blocks im unterteilten Band bleiben keine Blöcke im Band mehr zur Verarbeitung übrig, und es wird erneut der Schritt 112 aufgerufen, um festzustellen, ob die letzte Zeile im Bild 5 verarbeitet worden ist, und wird dann verarbeitet.
• Es ist auch möglich, die Anzahl der Codevektoren im wesentlichen zu verdoppeln, ohne den zum Speichern des Codelexikons 30 notwendigen Speicher zu vergrößern. Bei einem solchen System enthält die die Nummer des gewählten Codevektors ausdrückende Binärzahl ein zusätzliches Bit. Der unterteile Block wird nicht nur mit jedem der vorge gebenen Codevektoren verglichen, sondern auch mit dem Inversen oder den fotografischen Negativen jedes dieser Codevektoren. Wenn der unterteilte Block dem Inversen eines Codevektors am nächsten kommt, wird das zusätzliche Bit auf "1", sonst auf "0" gesetzt. Um eine solche Technik beim vorliegenden Beispiel anzuwenden, sind zum Kennzeichnen eines Codevektors sieben Bit notwendig: sechs Bit zum Kennzeichnen des gewählten Codevektors und eines zur Angabe, ob das fotografische Negativ oder Positiv des Codevektors dem zuvor unterteilten Block am nächsten kommt. Sobald die den gewählten Codevektor kennzeichnende Binärzahl generiert ist, kann das Codewort nach einem der vorstehend angegebenen Verfahren erzeugt werden (d. h. führende "1" (or "0"), mit folgender 7-Bit-Codevektor- Binärnummer, oder die 7-Bit-Codevektor-Binärnummer allein, mit der Reservierung eines Codewortes zur Angabe von Leerzeilen).
• Das Ergebnis des in Fig. 3 dargestellten Kompressionsverfahrens ist eine Folge von Codewörtern, die je eine Anzahl von aufeinanderfolgenden Leerzeilen oder von Codevektoren darstellen, die nachfolgenden Blöcken in einem Band des Bildes am nächsten kommen, das von oben nach unten und von links nach rechts abgetastet worden ist. Bei dem in Fig. 4 dargestellten Bild 5 ist der Ausgang des Bildkomprimierers 26 (gemäß Fig. 1) ein erstes Codewort, das die sieben leeren Zeilen, Abschnitt 302, oben im Bild 5 angibt, sodann eine Reihe von Codewörtern, welche die ID-Nummern der Codevektoren darstellen, die den aufeinanderfolgenden Blöcken (Abschnitt 304) im von links nach rechts abgetasteten Band am nächsten kommen; dann ein Codewort (oder möglicherweise mehrere Codewörter), welche die leeren Zeilen im Abschnitt 306 darstellen; sodann eine Reihe von Codewörtern, die aufeinanderfolgende Blöcke im von links nach rechts abgetasteten oberen Band des Abschnitts 308 darstellen, gefolgt von Codewörtern, die aufeinanderfolgende Blöcken im von links nach rechts abgetasteten unteren Band im Abschnitt 308 darstellen, und schließlich ein Codewort, welches die sechs leeren Zeilen, Abschnitt 310, am Fuß des Bildes 5 darstellt.
• Fig. 6 ist ein Flußdiagramm mit der Darstellung eines erfindungsgemäßen Verfahrens 200 zum Dekomprimieren zuvor komprimierter Bilddarstellungsdaten. Ein besseres Verständnis der Fig. 6 kann sich aus der Bezugnahme auf Fig. 4 und 5 ergeben. Gemäß Fig. 6 beginnt das Dekompressionsverfahren im Schritt 202. Im Schritt 204 wird ein Teil des Speichers 56 (gemäß Fig. 1) oder des RAM 64 (gemäß Fig. 2) als Pufferspeicher zum Halten eines rasterstrukturierten dekomprimierten Bildes zugewiesen und gelöscht. Dieser Rasterpufferspeicher wird von oben nach unten und von links nach rechts gefüllt, ausgehend von den empfangenen, das Bild 5 darstellenden Codewörtern. Somit stellt der zu füllende erste Abschnitt des Rasterpufferspeichers die obere linke Ecke des reproduzierten Bildes 5' dar. Nach beendeter Bilddekompression stellt der Inhalt des Rasterpufferspeichers des reproduzierte Bild 5' dar.
• Im Schritt 206 gemäß Fig. 6 wird das erste Codewort gelesen. Im Schritt 208 wird dieses Codewort geprüft, um zu bestimmen, ob es aufeinanderfolgende Leerzeilen oder einen unterteilten Block darstellt. Dies geschieht durch Überprüfen entweder des ersten Bits (wenn, wie weiter oben beschrieben, 7-Bit-Codewörter benutzt werden) oder durch Prüfen, ob das Codewort die ID-Nummer des für die Angabe von Leerzeilen reservierten Codevektors enthält (wenn, ebenfalls wie weiter oben beschrieben, 6-Bit- Codewörter benutzt werden).
• Wenn dieses Codewort Leerzeilen darstellt, wird der Schritt 210 aufgerufen. Im Schritt 210 wird die Anzahl der durch dieses Codewort dargestellten Leerzeilen entnommen. Dies geschieht entweder durch Maskieren der letzten sechs Bit des aktuellen Codewortes (wenn 7-Bit- Codewörter benutzt werden) oder durch Lesen des folgenden Codewortes (wenn 6-Bit-Codewörter benutzt werden). In beiden Fällen stellen die entnommenen sechs Bit die Anzahl der durch dieses Codewort dargestellten Leerzeilen dar. Im Schritt 212 wird der Teil des zuvor zugewiesenen Rasterpuffers, beginnend mit der nächsten zu füllenden Zeile im Rasterpufferspeicher, mit Daten gefüllt, welche die durch dieses Codewort dargestellte Anzahl Leerzeilen darstellen. Wenn der Rasterpuffer im Schritt 204 gelöscht worden ist und dann weiße Pixel darstellende Daten enthält, springt der Schritt 212 im Rasterpufferspeicher nach unten auf die nächste zu füllende Zeile unter den Leerzeilen.
• Im Schritt 214 wird überprüft, ob noch mehr Codewörter zu verarbeiten sind. Wenn keine Codewörter mehr zu lesen übrig sind, endet das Dekompressionsverfahren im Schritt 224. Andernfalls wird erneut der Schritt 206 aufgerufen und das nächste Codewort gelesen. Wenn sich im Schritt 208 ergibt, daß dieses Codewort einen unterteilten Block darstellt, wird in den Schritt 216 eingetreten. Im Schritt 216 wird ein von den nächsten acht Zeilen im Rasterpufferspeicher gebildetes Band unterteilt. Dann werden die am weitesten links stehenden acht vertikal ausgerichteten Pixel im Band abgeteilt, um sie als erste aufzufüllen. Die ID-Nummer des Codevektors im Codelexikon 30 (gemäß Fig. 5) wird aus dem Codewort gewonnen. Dies kann durch Maskieren der letzten sechs Bit des Codewortes geschehen, wenn 7-Bit-Codewörter benutzt werden, oder durch Übernehmen des 6-Bit-Codewortes, so wie es ist, wenn 6- Bit-Codewörter benutzt werden. Diese ID-Nummer wird als Index zum Codelexikon 30 benutzt, um das 8-Zeilen/ 8-Pixel-Muster des durch diese ID-Nummer dargestellten Codevektors abzurufen. Das 8-Zeilen/8-Pixel-Muster dieses Codevektors wird aus dem Codelexikon 30 in den neu unterteilten 8-Zeilen/8-Pixel-Block im Rasterpufferspeicher kopiert. Im Schritt 220 wird geprüft, ob alle Blöcke im aktuellen Band aufgefüllt worden sind. Wenn nein, wird erneut der Schritt 216 aufgerufen. Als nächstes werden die nächsten acht vertikal ausgerichteten Bit im Band unterteilt, um sie als nächste aufzufüllen. Das den nächsten unterteilten Block darstellende Codewort wird gelesen, und das Codevektor-Muster, das durch die ID-Nummer in diesem Codewort dargestellt ist, wird in den neu unterteilten Block im Rasterpufferspeicher kopiert. Die Blöcke werden von links nach rechts aufgefüllt, bis das Band vollständig gefüllt ist. Wenn im Schritt 220 festgestellt wird, daß das Band gefüllt worden ist, wird erneut der Schritt 214 aufgerufen, um, wie weiter oben beschrieben wurde, zu bestimmen, ob irgendwelche Codewörter zu verarbeiten übrig sind.
• In Fortsetzung des vorstehenden Beispiels und unter Bezugnahme auf Fig. 4 wird der das dekomprimierte Bild 5' darstellende Rasterpufferspeicher in Abhängigkeit von dem ersten das Bild darstellenden Codewort oben mit sieben Leerzeilen gefüllt. Der am weitesten links stehende Block des ersten Bandes (Abschnitt 304) enthält in Abhängigkeit vom zweiten Codewort das Muster des Codevektors (gemäß Fig. 5) mit der ID-Nummer 27. Der nächste Block nach rechts wird in Abhängigkeit vom dritten Codewort mit dem Muster vom Codevektor mit der ID-Nummer 10 gefüllt und so fort. Die Leerzeilen der Abschnitte 306 und 310 sind exakt dargestellt, und die Blöcke in den Abschnitten 304 und 308 enthalten zugehörige Codevektor-Muster.
• Das Ergebnis der Dekompression des zuvor komprimierten Bildes ist ein Bild, das entweder von leeren Zeilen oder von acht mal acht Blöcken gebildet ist, die nur aus den 64 Codevektoren (oder 63 Codevektoren, je nach gewähltem Codierverfahren) im Codelexikon 30 gewählt sind. Dieses Bild ist nicht eine exakte Kopie des Originalbildes, und einige Informationen, die das Originalbild darstellen, sind verlorengegangen. Das heißt, dieses Codierverfahren ist ein verlustbehaftetes Codierverfahren. Wenn jedoch das Bild (durch den Drucker 58) gedruckt oder (am Anzeigegerät 82) angezeigt wird, werden die Blöcke im Originalbild 5 durch die Codevektoren-Muster aus dem Codelexikon 30 dargestellt, die den Mustern in den Blöcken des Originalbildes 5 am ähnlichsten sind. Eine des reproduzierte Bild 5' oder 5" lesende Person wird in der Lage sein, die Nachricht im Originalbild 5 zu erkennen, obwohl das reproduzierte Bild 5' sich vom Originalbild 5 unterscheidet. Wenn das Bild 5 z. B. eine maschinengeschriebene Nachricht ist, wird, obwohl jeder maschinengeschriebene Buchstabe im reproduzierten Bild 5' nicht genau so aussehen wird wie der entsprechende Buchstabe im Originalbild, ein Leser in der Lage sein festzustellen, welcher Buchstabe das ist, und es wird ihm daher möglich sein, die maschinengeschriebene Nachricht vom reproduzierten Bild 5' abzulesen.
• Unter nochmaliger Bezugnahme auf Fig. 5: Jeder Codevektor im Codelexikon 30 hat ein zugehöriges, vorbestimmtes Muster aus weißen und schwarzen Pixeln. Diese Muster können vorbestimmt, konstant und gegründet sein auf eine Auswertung des Typs Bilder, die zu komprimieren und dekomprimieren sind. Bei einem Faksimilesystem z. B. kann eine große Mustersammlung darstellender Faksimilebilder a priori unter Anwendung eines bekannten, verallgemeinerten Lloyd-Algorithmus ausgewertet werden, um zu bestimmen, welcher Satz Codevektoren das am besten erkennbare reproduzierte Bild ermöglicht. Das Codelexikon 30 wird dann mit diesen Mustern generiert und in jedes Faksimilesystem 10 permanent eingegliedert. Alternativ kann ein zu komprimierendes Originalbild 5 ebenfalls unter Anwendung eines bekannten, verallgemeinerten Lloyd-Algorithmus Zug um Zug ausgewertet werden, um einen Satz Codevektoren zu generieren, die zur geringstmöglichen Verzerrung im reproduzierten Bild 5' führen.
• Gemäß Fig. 1 wird diese Zug-um-Zug-Auswertung durch den Bildkomprimierer 26 ausgeführt, der die neuen Codevekto ren generiert und sie im Codelexikon 30 speichert, wie durch die gestrichelte Linie vom Bildkomprimierer 26 zum Codelexikon 30 angegeben ist. Sodann kann das ausgewertete Bild 5 komprimiert werden. Diese neu generierten Codevektoren werden dann als Teil der Faksimileübertragung übertragen oder als Teil der Datei des komprimierten Bildes im Massenspeicher gespeichert. Bei dem vorstehend beschriebenen Beispiel benötigen 64 8 · 8-Codevektoren 512 Speicherbyte. Beim Empfangen oder Abrufen dieser Codevektoren speichert sie der Bilddekomprimierer 54 im Codelexikon 30, wie durch die gestrichelte Linie vom Bilddekomprimierer 54 zum Codelexikon 30 angegeben ist. Die empfangenen oder abgerufenen komprimierten Bilddaten werden dann unter Benutzung dieser Codevektoren dekomprimiert.
• Diese Bildauswertung, entweder a priori oder Zug um Zug, kann auch andere Parameter des vorstehend beschriebenen Kompressions/Dekompressionsverfahrens ändern. Beispielsweise können die Zeilenanzahl L und die Pixelanzahl P in jedem Codevektor und entsprechenden Block im Bildraster und das durch L und P dargestellte Seitenverhältnis geändert werden. Ferner kann auch die Codevektorenanzahl V im Codelexikon 30 geändert werden. Wenn bei einem gegebenen Codevektor und gegebener Blockgröße (L · P) die Codevektorenanzahl V vergrößert wird, wird die zum Darstellen des Bildes notwendige Bitanzahl größer, aber die Wiedergabetreue des reproduzierten Bildes gegenüber dem Originalbild wird höher. Werden der Codevektor und die Blockgröße (L · P) verkleinert, enthält das Bild mehr Blöcke und zum Darstellen dieser Blöcke werden mehr Codewörter erforderlich. Jedoch sind weniger Codevektoren zum Darstellen der Teilmenge möglicher Muster in jedem Block notwendig, und somit wird die Bitanzahl in jedem Codewort verkleinert, wodurch die Vergrößerung der Anzahl Codewörter ausgeglichen wird. Wenn die Zeilenanzahl L in jedem Codevektor und Block im Bildraster richtig gewählt ist, kann die Benutzung von Leerzeilencodes maximiert werden, somit die zum Darstellen des Bildes notwendige Bitanzahl so klein wie möglich gehalten werden. Die Pixelanzahl P kann dann so angepaßt werden, daß ein gewünschtes Seitenverhältnis erhalten bleibt. Dies sind nur Beispiele von Optimierungsweisen, die durch richtiges Auswählen der Parameter L, P und V ausgeführt werden können. Für einen Fachmann ist es klar, daß andere Optimierungsweisen ausgeführt werden können. Es hat sich herausgestellt, daß die vorstehend angegebenen Parameterbeispiele, d. h. L = 8, P = 8 und V = 64, hinsichtlich der Tauglichkeit des reproduzierten Bildes 5' zufriedenstellend sind.
• Wenn, wie vorstehend beschrieben, ein Bild unter Anwendung des vorstehend beschrieben Verfahrens komprimiert worden ist, gehen einige Bildinformationen verloren; das reproduzierte Bild ist somit nicht eine exakte Kopie des Originalbildes. Jedoch kann das Bild, nachdem es komprimiert worden ist, unter Anwendung des vorstehend beschriebenen Prozesses wiederholt dekomprimiert und komprimiert werden, ohne daß weitere Informationen verlorengehen. Das heißt, nachfolgende Kompressionen und Dekompressionen führen nicht zu einer weiteren Verschlechterung der Wiedergabetreue des dekomprimierten Bildes gegenüber dem Originalbild.

Claims (7)

1. Verfahren zum Komprimieren rasterstrukturierter Quellen- Bilddarstellungsdaten (300), die Zeilen senkrecht ausgerichteter Pixel aufweisen, in komprimierte Bilddarstellungsdaten, die aufeinanderfolgende Bilddarstellungs-Codewörter enthalten,

mit den Verfahrensschritten:

Unterteilen der Quellen-Bilddarstellungsdaten (300) in leere Zeilen (302, 306, 310) und nichtleere Zeilen (304, 308) von Bilddarstellungsdaten (106),

gekennzeichnet durch

Gruppieren benachbarter leerer Zeilen in Abschnitten (302, 306, 310) und Darstellen jedes Abschnittes durch ein zugehöriges Leerzeilen-Codewort (108, 110),

Gruppieren nichtleerer Zeilen, und möglicherweise benachbarter leerer Zeilen in Bändern (304, 308) von L Zeilen (114),

Unterteilen jedes Bandes in eine Vielzahl Blöcke (BLOCK) von je L Zeilen zu P Pixeln und einem Muster (116-122), und bei jedem abgeteilten Block

Wählen eines Codevektors aus einer Vielzahl Codevektoren 30 von L Zeilen zu P Pixeln und einem vorbestimmten Muster, das mit dem Muster des abgeteilten Blockes (118) am besten übereinstimmt, und

Darstellen jedes abgeteilten Blockes durch ein zugehöriges Nichtleer-Codewort, das den gewählten Codevektor aus der Vielzahl Codevektoren (120) darstellt.

2. Verfahren nach Anspruch 1,

ferner dadurch gekennzeichnet, daß

vor dem Schritt des Gruppierens benachbarter leerer Zeilen in Abschnitten (108) die oberste Zeile der rasterstrukturierten Quellen-Bilddarstellungsdaten als eine aktuelle Zeile bezeichnet wird,

der Schritt der Unterteilung des Bildes in eine Vielzahl Nichtleer-Bänder den Schritt der Feststellung umfaßt, ob die aktuelle Zeile eine leere Zeile (106) ist, und, wenn die aktuelle Zeile eine leere Zeile nicht ist,

der Unterteilung eines aktuellen Zeilenbandes in den rasterstrukturierten Quellen-Bilddarstellungsdaten aus L benachbarten Zeilen (114), wobei die oberste Zeile die aktuelle Zeile ist, und der Bezeichnung des am weitesten links befindlichen Pixels als das aktuelle Pixel,

der Bildung eines Blockes aus P benachbarten, senkrecht ausgerichteten Pixeln in jeder Zeile im aktuellen Band (116), wobei das am weitesten links befindliche Pixel das aktuelle Pixel ist,

der Bezeichnung des P Pixel rechts vom aktuellen Pixel befindlichen Pixels als das aktuelle Pixel, der Wiederholung der Schritte Bildung und Bezeichnung, bis jedes Pixel im aktuellen Band zu einem Block gebildet worden ist, und

der Bezeichnung der sich L Zeilen unter der aktuellen Zeile befindlichen Zeile als die aktuelle Zeile.

3. Verfahren nach Anspruch 1, bei dem

jedes Pixel in den rasterstrukturierten Quellen-Bilddarstellungsdaten (300) einen von zwei Zuständen hat,

jedes Pixel in jedem Codevektor (30) einen von zwei Zuständen hat,

dadurch gekennzeichnet, daß der Schritt des Wählens eines Codevektors aus einer Vielzahl Codevektoren (120) die Schritte umfaßt:

Vergleichen der zugehörigen Zustände entsprechender Pixel in einem abgeteilten Block (BLOCK) und einem Codevektor aus der Vielzahl Codevektoren (30),

Bestimmen der Zahl entsprechender Pixel von gleichem Zustand, die einen Codevektor darstellen, und Bestimmen der Zahl entsprechender Pixel von verschiedenen Zuständen, die einen inversen Codevektor darstellen,

Wiederholen der Schritte Vergleichen und Zählen für jeden aus der Vielzahl Codevektoren, und

Wählen des Codevektors mit dem größten Zählwert, und

daß der Schritt der Darstellung jedes abgeteilten Blockes durch ein zugehöriges Nichtleer-Codewort (120) den Schritt der Ausgabe des Nichtleer-Codewortes umfaßt, einschließlich Daten, die den gewählten Codevektor darstellen, und Daten, die angeben, ob der gewählte Codevektor ein inverser Codevektor ist.

4. Verfahren zum Dekomprimieren von Bilddarstellungsdaten in rasterstrukturierte, reproduzierte, Zeilen senkrecht ausgerichteter Pixel aufweisende Bilddarstellungsdaten (300), dadurch gekennzeichnet, daß

die Bilddarstellungsdaten gemäß dem in Anspruch 1 angegebenen Verfahren komprimiert sind und aufeinanderfolgende Bilddarstellungs-Codewörter enthalten, die je eine Vielzahl leerer Zeilen (302, 306, 310) oder einen Codevektor aus einer Vielzahl Codevektoren V darstellen, die je L Zeilen und P Pixel und ein vorbestimmtes Muster aufweisen, wobei das Verfahren die Schritte umfaßt:

Einfügen einer Vielzahl leerer Zeilen in die rasterstrukturierten, reproduzierten Bilddarstellungsdaten in Abhängigkeit von einem Leerzeilen-Codewort (210, 212), und Einfügen des Musters des Codevektors in die rasterstrukturierten, reproduzierten Bilddarstellungsdaten in Abhängigkeit von einem Codevektor-Codewort (216, 218, 220).

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, daß

jedes Leerzeilen-Codewort Daten enthält, die eine Anzahl durch das Leerzeilen-Codewort dargestellter Leerzeilen (302, 306, 310) darstellen,

das Verfahren ferner den Schritt der Bezeichnung der obersten Zeile der rasterstrukturierten, reproduzierten Bilddarstellungsdaten als eine aktuelle Zeile umfaßt, und daß der Schritt der Einfügung von Leerzeilen die Schritte umfaßt:

Gewinnen der Anzahl Leerzeilen, die durch das Leerzeilen-Codewort (210) dargestellt sind,

Einfügen von Rasterdaten in aufeinanderfolgende Zeilen in den rasterstrukturierten, reproduzierten Bilddarstellungsdaten, welche die gewonnene Anzahl Leerzeilen darstellen, die mit der aktuellen Zeile (212) beginnen, und

Bezeichnen der der untersten eingefügten Zeile folgenden Zeile als die neue aktuelle Zeile.

6. Verfahren nach Anspruch 4,

dadurch gekennzeichnet, daß sie ferner den Schritt der Bezeichnung der obersten Zeile der rasterstrukturierten, reproduzierten Bilddarstellungsdaten als eine aktuelle Zeile umfaßt,

wobei der Schritt der Einfügung des Codevektor-Musters die Schritte umfaßt:

Unterteilen der rasterstrukturierten, reproduzierten Bilddarstellungsdaten in ein aktuelles Zeilen-Band von L benachbarten Zeilen, wobei eine oberste Zeile die aktuelle Zeile ist, und Bezeichnen eines am weitesten links befindlichen Pixels als das aktuelle Pixel,

weiteres Unterteilen des aktuellen Bandes in einen Block von P benachbarten, senkrecht ausgerichteten Pixeln in jeder Zeile im aktuellen Band, wobei das am weitesten links befindliche Pixel das aktuelle Pixel ist, Kopieren des Musters des durch das Codevektor-Codewort dargestellten Codevektors in den Block (216, 218), und

Bezeichnen des P Pixel rechts vom aktuellen Pixel befindlichen Pixels als das neue aktuelle Pixel, Wiederholen der Schritte Blockunterteilung, Kopieren und Bezeichnen, bis ein Codevektor-Muster in jeden Block im aktuellen Band (220) kopiert worden ist, und Bezeichnen der sich L Zeilen unter der aktuellen Zeile befindenden Zeile als die neue aktuelle Zeile.

7. Verfahren nach Anspruch 6, dadurch gekennzeichnet, daß

das Codevektor-Codewort Informationen enthält, die angeben, ob der gewählte Codevektor ein inverser Codevektor ist, und

der Kopier-Schritt (218) den Schritt des Kopierens des inversen Musters des durch das Codevektor-Codewort dargestellten Codevektors in den Block, wenn die einen inversen Codevektor anzeigenden Informationen angeben, daß der Codevektor ein inverser Codevektor ist.