DE69531080T2

DE69531080T2 - System und Verfahren zur Bildkompression

Info

Publication number: DE69531080T2
Application number: DE69531080T
Authority: DE
Inventors: Rajeev Dujari
Original assignee: Microsoft Corp
Current assignee: Microsoft Corp
Priority date: 1994-04-25
Filing date: 1995-04-24
Publication date: 2003-12-04
Anticipated expiration: 2015-04-25
Also published as: EP0680016A3; JP4366408B2; JPH0863606A; EP0680016A2; DE69531080D1; EP0680016B1; US5504591A; JP4101312B2; JP2007184978A

Description

TECHNISCHES GEBIET

Die Erfindung bezieht sich im Allgemeinen auf ein System und ein Verfahren zur Datenkompression und insbesondere auf ein System und ein Verfahren zur Kompression von gerasterten Grafikbildern.

HINTERGRUND DER ERFINDUNG

Die Verwendung von Grafiken in Computeranwendungen ist sehr weit verbreitet. Die Übertragung eines Dokuments zwischen Computern schließt meist die Übertragung grafischer Daten, wie Zeichenschriftarten, ein. Dies schließt die Übertragung von Faksimile- Nachrichten von einem Faksimilegerät (Fax) zu einem anderen Faxgerät oder die Übertragung von Daten von einem Hostcomputer zu einem Drucker ein.
Grafische Daten können als Rastergrafikdaten übertragen werden, in denen das Grafikbild vor der Übertragung in eine Bitmapdatei umgesetzt wurde. Ein Faxgerät scannt beispielsweise ein Dokument und erzeugt für jede Seite eine Bitmapdatei. Die Bitmapdatei wird vor der Übertragung komprimiert, um die Übertragungszeit zu reduzieren. Diese Kompression ermöglicht eine höhere Berechnungseffizienz und erspart auch Kosten, wenn der Faxtelefonanruf ein Fernruf ist. Es gibt eine Anzahl von gut bekannten Faxkompressionsstandards, die durch Standards definiert sind, die vom International Telegraph and Telephon Consultative Committee (CCITT) festgelegt werden. Trotz ihrer weiten Verbreitung ist eine Datenkompression, die CCITT-Kompressionsstandards benutzt, langsam und führt nicht zu einer effizienten Kompression eines Grafikbildes.
Computer, die beispielsweise Teil eines Druckers sind, der an einen Hostcomputer angeschlossen ist, können Bilddaten übertragen, die sich auf die vom Drucker zu druckenden Seiten beziehen. Meist empfangen die Drucker Zeichenschriftarten, die innerhalb von Textdaten eingefügt sind. Der Drucker kann diese eingefügten Zeichenschriftarten benutzen, um mit hoher Qualität in der gewünschten Schriftart zu drucken. Ein übliches Element in all diesen Beispielen ist, dass ein Computer ein Bild zu einem zweiten Computer sendet.
Die Ressourcen, die zur Übertragung der Bilddaten erforderlich sind, variieren von System zu System. Beispielsweise erfordern einige Textverarbeitungssysteme, wie Microsoft WordTM, zur Verarbeitung der Bilddaten eine leistungsfähige Zentralverarbeitungseinheit (CPU) mit hoch entwickelten Berechnungsfähigkeiten und einer großen Menge von Speicher. Ähnlich erfordern Drucksysteme, die beispielsweise die PostskriptTM- Software benutzen, einen großen Datenverarbeitungsaufwand, sowohl vom übertragenden und als auch vom empfangenden Computer. Dies erfordert wieder sowohl eine leistungsfähige CPU als auch eine große Menge an Speicher.
Die Arten von oben beschriebenen Bildübertragungssystemen können für die Verwendung in preiswerten Systemen nicht die geeigneten sein, in denen die Kosten für eine leistungsfähige CPU und eine große Menge an Speicher nicht akzeptabel sind. Deshalb kann davon ausgegangen werden, dass ein großer Bedarf für ein System und ein Verfahren zur Kompression von gerasterten Grafikbildern und Übertragung von Bilddaten vorliegt, ohne das eine leistungsfähige CPU und eine große Menge an Speicher erforderlich ist.
R. C. Gonzales und R. E. Woods, Digital Image Processing, Addison-Wesley, Massachusetts, September 1993, beschreiben eine Lauflängenkodierung, bei der jede Reihe eines Bildes oder einer Bitebene durch eine Sequenz von Längen repräsentiert wird, die aufeinanderfolgende Folgen von schwarzen und weißen Pixeln beschreiben. Bei eindimensionaler Lauflängenkodierung wird jede zusammenhängende Gruppe von Nullen oder Einsen, die bei einem Scann von links nach rechts in einer Reihe auftreten, durch ihre Länge kodiert und eine Bestimmungsvorschrift des Wertes einer Folge gebildet. Eine Vielzahl von zweidimensionalen Lauflängenkodierungsprozeduren kann aus der eindimensionalen Lauflängenkodierung abgeleitet werden, wobei eine davon ein relatives Adressenkodieren ist. Ähnlich zum relativen Adressenkodieren kann eine Kontur in einem binären Bild durch einen Satz von Randpunkten oder durch einen Randpunkt und einen Satz von Richtungen repräsentiert werden. Zusätzlich zu dieser Technik, die auch als gerichtete Konturenverfolgung bezeichnet wird, beziehen sich andere Techniken auf die prädiktive Differentialquantisierung, dass eine Scannlinien-orientierte Konturverfolgungsprozedur beschreibt. Bei der prädiktiven Differentialquantisierung werden die Vorder- und Hintergrundkonturen jedes Objektes eines Bildes gleichzeitig verfolgt, um eine Sequenz von Paaren (Δ', Δ") zu erzeugen. Der Ausdruck Δ' ist die Differenz zwischen den Anfangskoordinaten der Vordergrundkonturen auf angrenzenden Zeilen und der Ausdruck Δ" ist die Differenz zwischen den Vordergrund- zu Hintergrundkonturlängen. Diese Differenzen repräsentieren zusammen mit der Spezialnachricht, die den Anfang einer neuen Kontur und das Ende der alten Kontur anzeigt, jedes Objekt. Wenn der Ausdruck Δ" durch die Differenz zwischen den Hintergrundkonturkoordinaten von angrenzenden Zeilen ersetzt wird, dass durch den Ausdruck Δ''' angezeigt, wird diese Technik auch als Doppeldeltakodierung bezeichnet.
Die UK-Patentanmeldung 2245463 beschreibt ein Verfahren und ein System zur Erzeugung von Grafikbildern mit Lauflängen-kodierten Daten. Pixelstellen eines Framestores speichern eine Variable, die ein Wert von wenigstens einem Charakteristikum, das z. B. die Intensität oder Farbe des Pixels sein kann, darstellt. Die Variable kann auch ein logisches Bit sein, welches anzeigt, dass das Pixel gesetzt oder ungesetzt ist. Die zur Repräsentation eines Bildes benötigte Menge von Daten, kann komprimiert sein, wodurch eine schnellere Bildszusammenstellung in dem Framestore erreicht werden kann und weniger komplizierte Schaltkreise zum Schreiben der Grafiken im Framestore benötigt werden. Mit Hinblick auf die Weiterverarbeitung der Menge von kodierten Daten und der Reduzierung des Verarbeitungsaufwands, der erforderlich ist, um es in eine Pixelgrafik in dem Framestore zu expandieren, weist jede Pixelfolge einen zugewiesenen Referenzparameter, der einen Referenzwert eines Charakteristikums der Pixel in der Folge darstellt und einen Differenzparameter auf, der die Veränderung in dem Wert des Charakteristikums entlang der Länge der Folgen darstellt.
Die Parameter für eine Folge nach einer bestimmten Anfangsfolge definieren Koordinaten, die zu denen einer unmittelbar vorausgehenden Folge relativ sind. Dadurch sind die Koordinaten einer zweiten Folge relativ zu denen der Anfangsfolge definiert und die Koordinaten einer dritten Folge sind relativ zu denen der zweiten Folge definiert und ähnlich für jede nachfolgende Folge. Die Koordinaten für jede Folge können die Position der Anfangspixelstelle der Folge und die Folgenlänge einschließen. Wenn die Koordinaten die Anfangspixelstelle der Folge enthalten, ist der Parameter, der die Koordinate der Pixelfolgen nach der Anfangsfolge definiert, ein Deltawert. Der Wert der Koordinate wird durch Hinzufügen des Deltawertes zu dem Wert der Anfangspixelstellenkoordinate für die vorausgehende Folge bestimmt. Die Lauflängen-kodierten Daten entsprechen den Pixelfolgen entlang aufeinanderfolgender Rasterscannzeilen des Pixelspeichers. Der Parameter, der die Anfangspixelstellenposition für jede Folge nach der Anfangsfolge definiert, kann dann als ein Deltawert für die horizontale Position entlang der Scannzeile kodiert werden. Die Anzahl der Pixelfolgen, die das Pixelbild bilden können als ein Gesamtfolgenparameter kodiert werden, der durch den Parameter für die Anfangspixelfolge kodiert sein kann. Der Gesamtfolgenparameter kann die Anzahl von Pixelfolgen angeben, die der Anfangsfolgen folgen. Ein Anzeigen eines Objektes umfasst die Angabe einer Objekthöhe, die einer Anzahl von Videoscannzeilen entspricht, die von dem anzuzeigenden Objekt belegt werden und für jede nachfolgende Zeile der Höhe, die Angabe eines X-Delta und einer Länge und eines Längendelta, wobei das X-Delta eine Zeilenanfangspixelposition definiert, das zu einer vorausgehenden Zeile relativ ist und das Längendelta eine Zeilenlänge relativ zu der vorausgehenden Zeile definiert. Bilder können durch Festlegen einer Anfangsadresse einer bestimmten Anfangspixelfolge an jeder ausgewählten Position in dem Framestore positioniert werden. Zusammengesetzte Bilder können auch durch Kombinieren von zwei oder mehreren Bildern erzeugt werden, wobei jedes durch Blöcke von Lauflängen-kodierten Pixelfolgen gebildet wird.
Haralick R. M., Shapiro L. G.:" Computer and Robot Vision, Vol. 1', 1992, Addison Wesley, S. 40-48 offenbart eine Lauflängenimplentation eines lokalen Tabellenverfahrens. Eine Lauflängenkodierung eines binären Bildes ist eine Liste von zusammenhängenden typischen horizontalen Folgen von Eins-Pixeln. Für jede Folge muss die Position des Anfangspixels der Folge und entweder ihre Länge oder Position ihres Endpixels aufgenommen werden. Fig. 2.20 dieser Referenz zeigt ein exemplarisches binäres Bild und seine Lauflängenkodierung. Jede Folge in dem binären Bild ist durch ihre Anfangs- und Endpixelpositionen kodiert. Das PERM_LABEL-Feld darin wird benutzt, um angrenzende Folgen in unterschiedlichen Reihen des binären Bildes zu verbinden. Somit kann eine gegebene Folge in einer gegebenen Reihe mit einer Folge aus einer vorherigen Reihe verbunden werden. Dann wird das PERM_LABEL der gegebenen Folge dem Label der Folge in der vorherigen Reihe, mit der sie verbunden ist, zugewiesen. Dadurch werden gekennzeichnete Gebiete erzeugt. Ein Beispiel für entsprechend gekennzeichnete Gebiete in einem binären Bild wird in Fig. 2.22 dieser Referenz gezeigt, in der (a) das binäre Bild darstellt und (d) die endgültig gekennzeichneten Gebiete, in der zwei Gebiete aus verbundenen Pixel bestehen, nämlich die Gebiete, die mit "1" und "3" gekennzeichnet sind, werden gezeigt.
Es ist die Aufgabe der Erfindung, ein System und ein Verfahren zur Kompression von Rastergrafikbildern und zur Übertragung von Bilddaten anzugeben, die keine leistungsfähige CPU und eine große Menge an Speicher erfordern.
Diese Aufgabe wird durch die Gegenstände in den unabhängigen Ansprüchen gelöst, die die Erfindung definieren. Bevorzugte Ausführungsbeispiele der Erfindung sind Gegenstände von Unteransprüchen.

Kurze Beschreibung der Zeichnung

Fig. 1 ist ein funktionelles Blockdiagramm eines Systems der vorliegenden Erfindung.
Fig. 2 ist ein Ablaufdiagramm des Verfahrens, das von dem System der Fig. 1 zur Erzeugung von Veränderungsvektortabellen benutzt wird.
Fig. 3 ist eine Beispielbitmapdatei, die die Erzeugung von Veränderungsvektoren darstellt, die das Ablaufdiagramm der Fig. 2 benutzt.
Fig. 4 ist ein Ablaufdiagramm des Verfahrens, das von dem System der Fig. 1 zur Erzeugung von Pixelketten benutzt wird.
Fig. 5 ist eine Beispielbitmapdatei, die die Erzeugung von Pixelketten darstellt, die das Ablaufdiagramm der Fig. 4 benutzt.
Fig. 6 zeigt die prädiktive Kodierhäufigkeit, die von dem Kodierungsteil des Systems in Fig. 1 benutzt wird.

Detaillierte Beschreibung der Erfindung

Die vorliegende Erfindung gibt ein System zur Übertragung von Bilddaten von einem Computer zu einem anderen an, ohne dass eine leistungsfähige CPU und eine große Menge an Speicher zu erfordern. Speicherkapazitäts- und Kostenbetrachtungen machen es für Geräte wie Drucker unmöglich, jede erdenkliche Schriftarttype zu speichern. Gerade mit vielen gespeicherten Schriftarttypen muss der Drucker noch die Flexibilität aufweisen, um neue Zeichenschriftarten, die gewünscht werden können, zu benutzen. Das System der vorliegenden Erfindung verarbeitet Rasterdaten um die Größe der Rasterdaten stark zu reduzieren. Dies ermöglicht die Flexibilität neue Zeichenschriftarten in Textdaten einzubetten, gerade in kostengünstigen Systemen, die keine leistungsfähige CPU und eine große Menge an Speicher aufweisen. Während Systeme nach dem Stand der Technik Rasterschriftarten einbetten können, wie Konturenschriftarten, erfordern diese Systeme große Mengen an Speicher um gerade eine einzelne derartige Schriftart zu unterstützen. Beispielsweise erfordert ein Konturenschriftartsatz typischerweise ungefähr 60 Kilobytes (Kbytes) an benutztem Code zur Verarbeitung des Schriftartsatzes und 40 Kbytes bis 100 Kbytes für die Kontur des Schriftartsatzes. Somit kann die Übertragung eines einzelnen Konturenschriftartsatzes mehr als 160 Kbytes erfordern. Eine typische gedruckte Seite kann mehrere Schriftarten, wie Times-Roman, Times-Roman Fett oder Times-Roman Kursiv enthalten, wobei jede davon als eine separate Schriftart betrachtet wird, die individuell definiert werden muss. Die Benutzung mehrerer Schriftarten erhöht somit die Anforderung an den Speicher signifikant.
Im Kontrast dazu reduziert das System der vorliegenden Erfindung sehr stark die Größe der Rasterdaten für jeden Schriftartsatz bei einer festen Auflösung von 300 Dots pro Zoll (DPI) auf ungefähr 3 Kbytes bis 15 Kbytes für jeden Schriftartsatz. Das ermöglicht die Benutzung des Systems der vorliegenden Erfindung auf vielen kostengünstigen Geräten, die relativ beschränkte Speicherressourcen aufweisen, wie bspw. Kopierer, Faxgeräte, Drucker und ähnliches. Die reduzierten Speicheranforderungen machen es durchführbar, einen Schriftartsatz in eine Faxnachricht einzubetten. Die drastisch reduzierte Größe der eingefügten Schriftartdaten bedeutet ebenso, dass die Übertragungszeit von Textdaten mit einem eingefügten Schriftartsatz reduziert wird. Die reduzierte Übertragungszeit führt zu einer effizienteren Übertragung von Daten und im Fall von einigen Computern, wie bspw. einem Faxgerät, zu niedrigeren Übertragungskosten. Das System stellt auch Flexibilität in der Kommunikation zwischen den oben beschriebenen Geräten bereit. Die Möglichkeit die vorliegende Erfindung in viele Geräte zu implementieren führt zu einer größeren Interoperabilität, als die, die mit dem Stand der Technik erreichbar ist.
Bitmapdaten werden als Datenform auf sehr niedrige Ebene betrachtet. Der empfangende Computer, entweder ist ein Drucker oder ein Faxgerät, kann eingebettete Zeichenschriftarten ohne die hoch entwickelte Datenverarbeitung, die von einigen bekannten Systemen, wie PostskriptTM, erfordert wird, benutzen, in denen Daten auf einem hohem Level übertragen werden, welches einen großen Aufwand an Datenverarbeitung erfordert. Somit ermöglicht die vorliegende Erfindung die Benutzung von weniger hoch entwickelten Mikroprozessoren in dem empfangenden Computer, wodurch weiter die Kosten reduziert werden.
Die Bilddaten, die von der vorliegenden Erfindung verarbeitet werden, sind ein Rasterbild, das aus einer Sequenz von horizontalen Scannreihen besteht. Jede horizontale Scannreihe besteht wiederum aus einer Reihe von Pixeln. Jedes Pixel in dem Rasterbild wird durch ein oder mehrere Datenbits repräsentiert. In ihrer einfachsten Form liegt ein einzelnes Datenbit für jedes Pixel vor, das anzeigt, ob das Pixel farbig ist oder nicht. Der Begriff farbig bezieht sich darauf, ob das Pixel auf dem speziellen Anzeigemedium sichtbar ist. Ein einfaches Anzeigemedium weist eine Hintergrundfarbe auf, die den Datenwert der Pixel angibt, die auf dem speziellen Anzeigemedium sichtbar sind. Eine Vordergrundfarbe bezieht sich auf Pixel, die einen anderen Datenwert als den Datenwert der Hintergrundfarbe aufweisen, und dadurch auf dem speziellen Anzeigemedium sichtbar sind. Beispielsweise weist ein typischer Drucker, bspw. ein Laserdrucker, ein Datenbit für jedes Pixel auf, um anzugeben, ob das Pixel farbig ist oder nicht. Die Pixel weisen einen ersten Datenwert (z. B. ersten logischen Zustand) auf, wenn sie die Vordergrundfarbe, bspw. schwarz, aufweisen und haben einen zweiten Datenwert (z. B. einen zweiten entgegengesetzten logischen Zustand), wenn sie die Hintergrundfarbe aufweisen, bspw. weiß. Im Gegensatz dazu kann ein Videoanzeigeendgerät Pixel aufweisen, die den ersten logischen Zustand für eine weiße Vordergrundfarbe und den zweiten logischen Zustand für eine schwarze Hintergrundfarbe aufweisen. Somit kann derselbe logische Zustand abhängig von dem speziellen Anzeigemedium zu unterschiedlichen physischen Anzeigen führen. Die tatsächlichen Datenwerte der Pixel sind von dem speziellen Anzeigemedium abhängig.
Ein typischer Drucker, bspw. ein Laserdrucker, weist ein Datenbit für jedes Pixel auf, um anzugeben, ob das Pixel farbig ist oder nicht. Wie oben beschrieben, weisen die Pixel einen ersten logischen Zustand auf, wenn sie farbig sind (z. B. sichtbar in dem Bild) und einen zweiten, entgegengesetzten logischen Zustand auf, wenn sie nicht farbig sind (z. B. unsichtbar in dem Bild). In einem typischen Drucker mit 300 dpi Auflösung bedeutet dies, dass es 300 Pixel pro Zoll in jeder horizontalen Scannreihe pro Zoll gibt. Somit wird eine 8,5 Zoll · 11 Zoll Seite 2550 Pixel in jeder horizontalen Scannreihe aufweisen. Die Werte für die Positionen der Pixel in jeder horizontalen Scannreihe werden somit zwischen Null und 2549 schwanken. Es wird verstanden, dass der Begriff "horizontale Scannreihe" in Hinblick auf typische Geräte benutzt wird, die jede Reihe von Pixeln in einer horizontalen Richtung scannen. Die vorliegende Erfindung ist ebenso auf Geräte anwendbar, die in die vertikale Richtung scannen.
Die vorliegende Erfindung ist in einem System 10 ausgeführt, welches in einem funktionellen Blockdiagramm von Fig. 1 gezeigt wird. Das System 10 umfasst eine Zentralverarbeitungseinheit (CPU) 12 und einen Speicher 14, der sowohl Arbeitsspeicher (RAM) als auch Nur-Lesespeicher (ROM) umfassen kann. Ein Datenspeichergebiet 16, das ein Teil des Speichers 14 sein kann, enthält die Rasterschriftart oder andere Bilddaten, die zur Verarbeitung von dem System 10 vorgesehen sind. Es soll so verstanden werden, dass das System 10 Bilddaten verarbeiten kann, ohne dass es erforderlich ist, dass gesamte Bild in dem Datenspeichergebiet 16 gespeichert ist. In einer typischen Anwendung kann das Datenspeichergebiet 16 ein temporärer Buffer sein, der einen Anteil der Bilddaten empfängt und die Bilddaten in Echtzeit als einen Datenstrom verarbeitet. Wenn das System 10 in eine Faxmaschine eingebaut ist, kann eine Scannvorrichtung 18 benutzt werden, um die gedruckten Seiten für die Übertragung zu scannen. Die Daten von der Scanneinrichtung 18 werden dem Datenspeichergebiet 16 zugeführt, das als temporärer Buffer dient, um die Bilddaten zu halten, während das System 10 den Datenstrom in Echtzeit verarbeitet.
Ein Drucker 20 wird von dem System 10 benutzt, um empfangene Bilddaten zu drucken. Der Drucker 20 kann ein integrierter Teil des Systems 10 sein, wenn das System ein Faxgerät oder ein Kopierer ist. Alternativ kann der Drucker 20 ein eigenständig stehendes Gerät sein.
Ein konventioneller Veränderungsvektorgenerator 22 analysiert sequentiell jede horizontale Scannreihe, um die Position zu bestimmen, an der die Pixel in der horizontalen Scannreihe von dem ersten logischen Zustand in den zweiten logischen Zustand verändert sind, und von dem zweiten logischen Zustand in den ersten logischen Zustand. Die Positionen der Veränderung in dem logischen Zustand sind relativ zu einem ersten Ende der horizontalen Scannreihe und können somit als Vektoren betrachtet werden, die eine Ursprung an dem Anfang von jeder horizontalen Scannreihe, eine horizontale Richtung und eine Länge aufweisen, die durch die relative Position von jedem Pixel angeben sind, dass die logischen Zustände in Bezug auf den logischen Zustand des vorherigen Pixels in der horizontalen Scannreihe verändert.
Der Veränderungsvektorgenerator 22 speichert die Veränderungsvektoren für jede der horizontalen Scannreihen in einer Veränderungsvektortabelle 24. Da im dem Datenspeichergebiet 16, muss die Veränderungsvektortabelle 24 nicht alle Veränderungsvektoren für alle horizontalen Scannreihen in einem Bild enthalten. Die Veränderungsvektortabelle 24 kann zeitweise nur die Veränderungsvektoren für eine horizontale Scannreihe enthalten.
Ein Pixelkettengenerator 26 analysiert die Daten in der Veränderungsvektortabelle 24 und erzeugt eine oder mehrere Pixelketten, um die Rasterbilddaten zu darzustellen. Pixelketten sind als eine Reihe von Pixeln mit demselben logischen Zustand definiert, die in einer horizontalen Richtung, in einer vertikalen Richtung oder diagonal aneinandergrenzen. Die Erzeugung von Pixelketten wird weiter unten erläutert. In dem vorliegenden bevorzugten Ausführungsbeispiel sind Pixelketten als sichtbare Pixel definiert, die in der horizontalen Richtung, in der vertikalen Richtung oder diagonal aneinandergrenzen. Die Pixelketten sind in einer Pixelkettentabelle 28 gespeichert, die ein Teil des Speichers 14 sein kann.
Eine Pixelkettenkodiereinheit 30 analysiert jede Pixelkette separat und kodiert die Pixelkette. Die kodierten Pixelketten können dann komprimiert werden und in einem komprimierten Speichergebiet 32 gespeichert werden, welches Teil des Speichers 14 ist. Die verschieden Komponenten des oben beschriebenen Systems 10 sind durch einen Bus 34 miteinander verbunden, der Zeitsignale und Leistungs- sowie Datensignale führen kann.
Das in System 10 benutzte Verfahren zur Erzeugung von Veränderungsvektoren für die horizontale Scannreihe ist in dem Ablaufdiagramm von Fig. 2 dargestellt, bei dem das Verfahren mit Schritt 50 beginnt. In Schritt 52 bildet der Veränderungsvektorgenerator 22 (siehe Fig. 1) einen Anfangswert für den logischen Zustand der zu analysierenden horizontalen Scannreihe. Beginnend an einem ersten Ende der horizontalen Scannreihe, bspw. das linke Ende, wenn das System 10 die horizontale Scannreihe von links nach rechts analysiert, wird in der vorliegenden Erfindung angenommen, dass jede horizontale Scannreihe mit einem weißen Pixel (z. B. einem unsichtbaren Pixel) beginnt. In Schritt 54 initialisiert der Veränderungsvektorgenerator 22 einen Zeiger für die horizontale Scannreihe, um auf diesen ersten Pixel zu zeigen. In der Entscheidung 56 bestimmt der Veränderungsvektor 22, ob der logische Zustand des Pixels, auf das der Zeiger zeigt, vom logischen Zustand des vorherigen Pixels in der horizontalen Scannreihe abweicht. Wenn eine Veränderung im logischen Zustand zu dem vorherigen Pixel vorliegt, ist das Ergebnis der Entscheidung 56 JA. In diesem Fall speichert der Veränderungsvektorgenerator 22 den aktuellen Wert des Zeigers in der Veränderungsvektortabelle 24 (siehe Fig. 1) in Schritt 58. Es wird darauf hingewiesen, dass jeder Wert in der Veränderungsvektortabelle 24 einen Veränderungsvektor für die spezielle horizontale Scannreihe darstellt. Wenn kein Wechsel im logischen Zustand zu dem vorherigen Pixel vorliegt, ist das Ergebnis der Entscheidung 56 NEIN. Wenn das Ergebnis der Entscheidung NEIN ist, oder nach der Ausführung von Schritt 58, bestimmt der Veränderungsgeneratorvektor in Entscheidung 60, ob der aktuelle Wert des Zeigers mit dem zweiten Ende der horizontalen Scannreihe korrespondiert. Wenn der horizontale Wert des Zeigers nicht mit dem zweiten Ende der horizontalen Scannreihe korrespondiert ist, ist das Ergebnis der Entscheidung 60 NEIN. In diesem Fall erhöht der Veränderungsvektorgenerator 22 den aktuellen Wert des Zeigers für die horizontale Scannreihe in Schritt 62 und kehrt zu Entscheidung 56 zurück, um die Analyse der horizontalen Scannreihe fortzusetzen. Wenn der aktuelle Wert des Zeigers mit dem zweiten Ende der horizontalen Scannreihe übereinstimmt, ist das Ergebnis der Entscheidung 60 JA, und der Veränderungsvektorgenerator beendet die Analyse für die Scannreihe in Schritt 64.
Ein Beispiel des Betriebs des Veränderungsvektorgenerators 22 ist in Fig. 3 dargestellt, in dem ein Teil eines Rasterbildes gezeigt ist. Das Rasterbild ist als eine Bitmapdatei in dem Datenspeichergebiet 16 (siehe Fig. 1) gespeichert. Der Anteil 70 umfasst sieben horizontale Scannreihen 72a-72g. Der Veränderungsvektorgenerator 22 scannt sequentiell die Pixel in jeder der horizontalen Scannreihen 72a-72g und bestimmt die Veränderungsvektoren für jede horizontale Scannreihe in der Art, die im Ablaufdiagramm von Fig. 2 beschrieben wurde. Die erste horizontale Scannreihe 72a enthält eine Veränderung bei Pixel Null (ausgehend von einem weißen Anfangspixel). Deshalb endet der erste Veränderungsvektor für die erste Scannreihe 72a bei Pixel Null und der zweite Veränderungsvektor endet bei Pixel 1 (die Position, an der sich das Pixel von schwarz nach weiß verändert). Andere Veränderungsvektoren enden bei den Pixeln 3 und 6. Somit ist die Größenordnung des Veränderungsvektors für die erste horizontale Scannreihe 72a 0, 1, 3 und 6. Die Veränderungsvektoren werden in Paaren von System 10 verarbeitet. Jedes Paar von Veränderungsvektoren zeigt eine Reihe von Pixeln in einer horizontalen Scannreihe an, die denselben logischen Zustand aufweisen. Jede Reihe von Pixeln, die von einem Veränderungsvektorpaar definiert ist, kann als eine Folge von Pixeln gedacht sein. Der allererste Veränderungsvektor in einer horizontalen Scannreihe zeigt die Position an, an der eine Folge von schwarzen Pixeln beginnt. Der zweite Veränderungsvektor zeigt die Position in der horizontalen Scannreihe an, an der eine Folge mit weißen Pixeln beginnt. Somit wird der erste Veränderungsvektor eines Veränderungsvektorpaares als einschließlich betrachtet, während der zweite Veränderungsvektor des Veränderungsvektorpaares als ausschließlich betrachtet wird. Dadurch zeigt der erste Veränderungsvektor des Veränderungsvektorpaares eine Pixelposition an, an der eine Folge von schwarzen Pixeln beginnt, während der zweite Veränderungsvektor des Veränderungsvektorpaares die Position nach dem letzten Pixel in der speziellen Folge von schwarzen Pixeln anzeigt. Es soll bemerkt werden, dass eine Folge von Pixeln so kurz wie ein Pixel oder so lang wie eine gesamte horizontale Scannreihe sein kann. Es soll erkannt werden, dass derselbe Typ von Verarbeitung durchgeführt werden kann, bei einer Definierung eines schwarzen Anfangspixels und einem Benutzen von weißen Pixeln als den ersten Veränderungsvektor des Veränderungsvektorpaares. Die Veränderungsvektorpaare der horizontalen Scannreihen 72a-72h von Fig. 3 sind unten in Tabelle 1 gezeigt. Tabelle 1 Veränderungsvektortabelle
Der Veränderungsgeneratorvektor 22 speichert die Veränderungsvektorpaare in der Tabelle 24. Wie zuvor angegeben, muss die Veränderungsvektortabelle 24 nicht die Veränderungsvektoren von allen Scannreihen enthalten, um den Prozess zur Erzeugung von Pixelketten zu beginnen.
Der Pixelkettengenerator 26 analysiert sequentiell die Veränderungsvektorpaare für jede horizontale Scannreihe und setzt die sichtbaren Pixel in eine oder mehrere Pixelketten. Das System 10 wird eine oder mehrere Pixelketten für das gesamte Rasterbild durch Analysieren der Veränderungsvektoren für das Rasterbild einer horizontalen Scannreihe zu einer Zeit erzeugen. Wie zuvor diskutiert, sind Pixelketten als sichtbare Pixel definiert, die in der horizontalen Richtung, in der vertikalen Richtung oder diagonal aneinandergrenzen. Beispielsweise sind die Pixel 3 bis 5 in der horizontalen Scannreihe 72a in horizontaler Richtung aneinandergrenzend. Deshalb wird der Pixelkettengenerator 26 diese einer Pixelkette zuweisen. Die Pixel 5 bis 6 in der horizontalen Scannreihe 72b sind in horizontaler Richtung aneinandergrenzend und sie sind auch zu den Pixeln 3 bis 5 in der horizontalen Scannreihe 72a aneinandergrenzend. Darum werden die Pixel 5 bis 6 in der horizontalen Scannreihe 72b zu der Pixelkette hinzugefügt, die die Pixel 3 bis 5 in der horizontalen Scannreihe 72a umfasst. Ähnlich sind die Pixel 5 bis 6 in der horizontalen Scannreihe 72c in horizontaler Richtung aneinandergrenzend und sind auch zu den Pixeln 5 bis 6 in der horizontalen Scannreihe 72b aneinandergrenzend. Deshalb werden die Pixel 5 bis 6 der horizontalen Scannreihe 72c zu der Pixelkette hinzugefügt, die die Pixel 5 und 6 der horizontalen Scannreihe 72b und die Pixel 3 bis 5 in der horizontalen Scannreihe 72a umfasst. Die offene Pixelkette wird fortgesetzt, um zu wachsen, bis der Pixelkettengenerator eine horizontale Scannreihe findet, die keine hinzuzufügenden Pixel aufweist, die zu der offenen Pixelkette entweder in vertikaler oder diagonaler Ausrichtung angrenzend sind. Z. B. enthält die horizontale Scannreihe 72f keine Pixel, die sich mit den Pixeln 5 bis 6 in der horizontalen Scannreihe 72e überschneiden, weder in vertikaler noch in diagonaler Richtung. Deshalb wird der Pixelkettengenerator die offene Pixelkette schließen. Es soll bemerkt werden, dass andere Pixelketten offen bleiben können, solange es neue Pixel gibt, die zu der Pixelkette in jeder horizontalen Scannreihe hinzuzufügen sind. Es soll auch bemerkt werden, dass nicht alle zusammenhängenden Pixel in derselben Pixelkette sind. Wie weiter unten beschrieben wird, wird, wenn spezielle Pixel in mehr als eine Pixelkette fallen könnten, eine zufällige Vorschrift benutzt, um die Pixel einer Pixelkette zuzuweisen.
Veränderungsvektoren werden benutzt, um die Position der Folgen von schwarzen Pixeln in den horizontalen Scannreihen effizient zu bestimmen und um die Pixelketten zu definieren. Alternativ könnte der Pixelkettengenerator 26 die Bitmapdatei selbst analysieren, um die Positionen zu bestimmen, an denen die Pixel die logischen Zustände verändern. Der Pixelkettengenerator 26 erzeugt oder öffnet eine Pixelkette für jedes der Veränderungswechselpaare in der ersten horizontalen Scannreihe, die Veränderungsvektoren enthält, weil jedes der Veränderungsvektorpaare in der horizontalen Scannreihe separate Folgen von schwarzen Pixeln anzeigt, die nicht in horizontaler Richtung aneinandergrenzen. Die Pixelketten, die von dem Pixelkettengenerator 26 geöffnet sind, bleiben solange geöffnet, wie jede nachfolgende horizontale Scannreihe Veränderungsvektoren enthält, deren Überschneidung zu einem Veränderungsvektor in der vorherigen horizontalen Scannreihe entweder vertikal oder diagonal angrenzend ist.
Das Ablaufdiagramm von Fig. 4 in Verbindung mit Tabelle 1 kann benutzt werden, um den Prozess der Erzeugung von Pixelketten darzustellen. Der Pixelkettengenerator 26 (siehe Fig. 1) beginnt bei Schritt 80 mit allen Veränderungsvektoren, die vorhergehend nach dem Ablaufdiagramm von Fig. 2 erzeugt wurden.
In Schritt 82 startet der Pixelkettengenerator 26 eine Pixelkettenliste für jede der Veränderungsvektorpaare in der ersten horizontalen Scannreihe, die Veränderungsvektoren enthält. Wie es eingeschätzt werden kann, können einige horizontale Scannreihen vorhanden sein, die überhaupt keine Veränderungsvektoren aufweisen, wie es bei dem Kopf einer Faxseite vorkommen kann. Aus Tabelle 1 kann entnommen werden, dass die erste horizontale Scannreihe 72a die folgenden Veränderungsvektorpaare: (0, 1), (3, 6) aufweist. Die zwei Veränderungsvektorpaare zeigen an, dass es zwei Folgen von schwarzen Pixeln in der horizontalen Scannreihe 72a gibt. Die erste Folge von schwarzen Pixeln beginnt mit Pixel 0 und endet bei Pixel 1, wodurch eine Folge von nur einem schwarzen Pixel angegeben wird. Die zweite Folge von schwarzen Pixeln beginnt bei Pixel 3 und endet bei Pixel 6, wodurch eine Folge von 3 schwarzen Pixeln angegeben wird. Da die horizontale Scannreihe 72a die erste zu analysierende horizontale Scannreihe ist, gibt es keine offenen Pixelketten und der Pixelkettengenerator wird zwei Pixelketten öffnen. Die erste Pixelkette enthält Pixel 0 und die zweite Pixelkette enthält die Pixel 3, 4 und 5. Der Pixelkettengenerator 26 wird eine Pixelkettenliste erzeugen, die die Veränderungsvektorpaare enthält, die jeder der Pixelketten zugewiesen sind. Die Pixelkettenlisten, die Veränderungsvektorpaare enthalten, werden in der Pixelkettentabelle 28 gespeichert.
In Schritt 84 geht der Pixelkettengenerator 26 zu der nächsten horizontalen Scannreihe. In Entscheidung 86 bestimmt der Pixelkettengenerator 26, ob sich ein Paar der Veränderungsvektoren in der aktuell zu analysierenden horizontalen Scannreihe, mit irgendeinem Veränderungspaar aus von der horizontalen Scannreihe, die gerade zuvor analysiert wurde, überschneidet. Der Begriff Überschneiden bezieht sich auf ein Veränderungsvektorpaar, dessen entsprechende Pixel an die Pixel in irgendeiner offenen Pixelkette in entweder der vertikalen oder diagonalen Richtung aneinandergrenzen. Die Überschneidung kann mathematisch durch Vergleich der Veränderungsvektoren der momentan analysierten horizontalen Scannreihe mit dem Veränderungsvektorpaar oder -paaren der zuvor analysierten horizontalen Scannreihe, bestimmt werden, um zu bestimmen, ob es eine Überschneidung gibt. Zum Beispiel überschneiden sich die Pixel 5 und 6 der horizontalen Scannreihe 72b mit den Pixeln 3 bis 5 der horizontalen Scannreihe 72a in vertikaler Richtung (z. B. das Pixel 5 der horizontalen Scannreihe 72b grenzt vertikal an das Pixel 5 der horizontalen Scannreihe 72a). Deshalb werden die Veränderungsvektorpaare (5, 7) in der horizontalen Scannreihe 72b zu der offenen Pixelkette hinzugefügt, die das Veränderungsvektorpaar (3, 6) in der horizontalen Scannreihe 72a enthält.
Aus Tabelle 1 kann erkannt werden, dass die horizontale Scannreihe 72b folgende Veränderungsvektorpaare aufweist: (1, 4), (5, 7). Diese Veränderungsvektorpaare geben eine erste Folge von schwarzen Pixeln, beginnend bei Pixel 1 und endend bei Pixel 4, und eine zweite Folge von schwarzen Pixeln, beginnend bei Pixel 5 und endend bei Pixel 7, an. Der Pixelkettengenerator 26 vergleicht die Veränderungsvektorpaare für die horizontale Scannreihe 72b mit den offenen Pixelketten, um zu bestimmen, ob es irgendeine Überschneidung gibt.
Aus Tabelle 1 kann erkannt werden, dass die erste Folge der schwarzen Pixel, die durch das Veränderungsvektorpaar (0, 1) in der horizontalen Scannreihe 72a angegeben wird, mit der ersten offenen Pixelkette korrespondiert. Die erste Folge von schwarzen Pixeln, die durch das Veränderungsvektorpaar (1, 4) in der horizontalen Scannreihe 72b angegeben wird, ist zu dem Veränderungsvektorpaar (0, 1) in der horizontalen Scannreihe 72a in einer diagonalen Richtung aneinandergrenzend. Somit ist das Ergebnis der Entscheidung 86 JA.
Die erste Folge von schwarzen Pixeln in der horizontalen Scannreihe 72b grenzt auch an die zweite Pixelkette in vertikaler Richtung an, da das Pixel 3 in der horizontalen Scannreihe 72b unter dem Pixel 3 in der horizontalen Scannreihe 72a liegt, das Teil der zweiten Pixelkette ist. Somit kann das Veränderungsvektorpaar, dass mit der ersten Folge von schwarzen Pixeln in der horizontalen Scannreihe 72 korrespondiert, entweder in die erste oder in die zweite Pixelkette gesetzt werden. Wenn eine Folge von Pixeln in eine oder mehrere Pixelketten gesetzt werden kann, weist der Pixelkettengenerator 26 die Pixel willkürlich der am frühesten geöffneten dieser Pixelketten zu. Dadurch wird in Schritt 88 das erste Veränderungsvektorpaar, das mit der ersten Folge der schwarzen Pixel in der horizontalen Scannreihe 72 korrespondiert, in die Pixelkettenliste für die erste Pixelkette gesetzt. Alternativ kann das Veränderungsvektorpaar, dass mit der ersten Folge von schwarzen Pixeln in der horizontalen Scannreihe 72 korrespondiert, in die Pixelkettenliste für die zweite Pixelkette gesetzt werden.
In Entscheidung 90 bestimmt der Pixelkettengenerator 26, ob irgendwelche zusätzlichen Veränderungsvektorpaare in der aktuell analysierten horizontalen Scannreihe übrig bleiben. Wenn Veränderungsvektorpaare in der horizontalen Scannreihe übrig bleiben, ist das Ergebnis der Entscheidung 90 JA und der Pixelkettengenerator 26 geht in Schritt 92 zu dem nächsten Veränderungsvektorpaar für die momentan analysierte horizontale Scannreihe bei Schritt 92 und kehrt zurück zu Entscheidung 86. Im Beispiel von Tabelle 1 gibt es ein verbleibendes Veränderungsvektorpaar (5, 7) für die horizontale Scannreihe 72b. Der Pixelkettengenerator 22 wird zur Entscheidung 86 zurückkehren und bestimmen, dass das zweite Paar der Veränderungsvektoren in die zweite Pixelkette gehört. Der Pixelkettengenerator wird das zweite Paar der Veränderungsvektoren in die zweite Pixelkettenliste setzen. Der Pixelkettengenerator wiederholt diesen Prozess für jedes der Veränderungsvektorpaare für die horizontale Scannreihe 72b.
Wenn es keine verbleibenden Veränderungsvektorpaare in der momentan analysierten horizontalen Scannreihe gibt, ist das Ergebnis der Entscheidung 90 NEIN und der Pixelkettengenerator 26 geht zur Entscheidung 96, um zu bestimmen, ob die momentan analysierte horizontale Scannreihe, die letzte horizontale Scannreihe in der Datei ist. Wenn es weitere zu analysierende horizontale Scannreihen gibt, ist das Ergebnis der Entscheidung 96 NEIN und der Pixelkettengenerator 26 kehrt zu Schritt 84 zurück, um die nächste horizontale Scannreihe 72c in Bezug auf die horizontale Scannreihe, die gerade analysiert wurde, zu analysieren. In dem Beispiel von Fig. 3 analysieren der Veränderungsvektorgenerator 22 und der Pixelkettengenerator 26 die horizontalen Scannreihen von oben nach unten. Jede horizontale Scannreihe wird von links nach rechts analysiert. Der Fachmann wird erkennen, dass das Prinzip der vorliegenden Erfindung auf jede Bitmapdatei, die oben oder unten beginnt und von links nach rechts oder von rechts nach links analysiert werden kann, angewendet werden kann. Zum Beispiel kann es effizienter sein, von oben nach unten zu kodieren, anstatt von links nach rechts, wenn die Bitmapdatei Zeichen enthält, die in einem Querformat vorliegen. Alternativ kann es auch effizienter sein, eine oder mehrere Pixelketten zu erzeugen, um die Hintergrundpixel anstatt der Vordergrundpixel zu kodieren. Die vorliegende Erfindung ist darauf gerichtet, die Pixelkettenerzeugung von jedem logischen Zustand in jeder Richtung in der Bitmapdatei zu umfassen.
In dem obigen Beispiel ist die horizontale Scannreihe 72b nicht die letzte horizontale Scannreihe. Deshalb kehrt der Pixelkettengenerator 26 zu Schritt 84 zurück und wird die horizontale Scannreihe 72c analysieren. Aus Tabelle 1 kann erkannt werden, dass die horizontale Scannreihe 72c folgende Veränderungsvektorpaare aufweist (0, 3), (5, 7). Da sich die Pixel 0,1 und 2 in der horizontalen Scannreihe 72c mit den Pixeln 1, 2 und 3 in der horizontalen Scannreihe 72b überschneiden und die Pixel 1, 2 und 3 in der horizontalen Scannreihe 72b Teil der ersten Pixelkette sind, weist der Pixelkettengenerator 26 das erste Paar der Veränderungsvektoren (0, 3) der ersten Pixelketteliste zu. Da es keine Überschneidungen zwischen der zweiten Folge von schwarzen Pixeln in der horizontalen Scannreihe 72c und der zweiten Pixelkette gibt, weist der Pixelkettengenerator 26 das zweite Paar der Veränderungsvektoren (5, 7) der zweiten Pixelkette zu.
Wenn das Veränderungsvektorpaar nicht innerhalb eines Pixels einer Pixelkette von der vorherigen horizontalen Scannreihe liegt, ist das Ergebnis der Entscheidung 86 NEIN. In diesem Fall wird der Pixelkettengenerator 26 in Schritt 94 eine neue Pixelkettenliste für das Veränderungsvektorpaar der aktuellen horizontalen Scannreihe beginnen. Jede Pixelkettenliste, die kein neues Veränderungsvektorpaar, das für die aktuelle horizontale Scannreihe hinzugefügt wird, aufweist, wird geschlossen oder aufgegeben. Das bedeutet, dass die spezielle Pixelkettenliste nicht größer werden wird und die spezielle Pixelkette nun komplett durch die Veränderungsvektorpaare in der Pixelkettenliste definiert ist. Zum Beispiel kann es erkannt werden, dass die horizontale Scannreihe 72f nur ein Veränderungsvektorpaar (1, 3) aufweist. Wenn der Pixelkettengenerator 26 die horizontale Scannreihe 72f analysiert, stellt er fest, dass es kein Veränderungsvektorpaar gibt, das sich mit der zweiten Pixelkette in der horizontale Scannreihe 72e überschneidet. Darum wird die zweite Pixelkette geschlossen. Die Pixelkettenliste für die zweite Pixelkette enthält Veränderungsvektorpaare für die horizontalen Scannreihen 72a bis 72e. Ähnlich gibt es keine Veränderungsvektorpaare in der horizontalen Scannreihe 72g, die sich mit der ersten Pixelkette in der horizontalen Scannreihe 72f überschneiden. Darum wird die erste Pixelkette geschlossen, wenn der Pixelkettengenerator die horizontale Scannreihe 72g analysiert. Die Pixelkettenliste für die erste Pixelkette enthält Veränderungsvektorpaare für die horizontalen Scannreihen 72a bis 72f.
Aus den Veränderungsvektoren in Tabelle 1 kann erkannt werden, dass es ein Veränderungsvektorpaar (4, 6) für die horizontale Scannreihe 72g gibt. Die Pixel, die mit dem Veränderungsvektorpaar (4, 6) in der horizontalen Scannreihe 72g korrespondieren, grenzen nicht an irgendwelche Pixel an, die mit den Veränderungsvektoren der vorhergehenden horizontalen Scannreihe 72f korrespondieren. Da es keine Pixelketten gibt, die sich mit dem Veränderungsvektorpaar in der horizontalen Scannreihe 72g überschneiden, beginnt der Pixelkettengenerator eine dritte Pixelkette, die nur das Veränderungsvektorpaar (4, 6) enthält in der horizontalen Scannreihe 72g. Nachdem eine neue Pixelkette in Schritt 94 begonnen wurde, geht der Pixelkettengenerator zu Entscheidung 90, um zu bestimmen, ob es andere Veränderungsvektorpaare in der aktuell horizontalen Scannreihe gibt.
Der Pixelkettengenerator 26 setzt die sequentielle Analyse jeder verbleibenden horizontalen Scannreihe fort, bis alle horizontalen Scannreihen analysiert wurden und Veränderungsvektorpaare zu einer Pixelkettenliste hinzugefügt wurden. Wenn keine horizontalen Scannreihen mehr analysiert werden müssen, ist das Ergebnis der Entscheidung 96 JA und der Pixelkettengenerator 26 schließt alle offenen Pixelketten und beendet den Prozess zur Erzeugung von Pixelketten in Schritt 98. Im Beispiel von Fig. 3 wird die dritte Pixelkette geschlossen, da es keine weiteren Pixel gibt, die sich in nachfolgenden horizontalen Scannreihen überschneiden können.
Die Pixelkettenlisten werden in der Pixelkettentabelle 28 (siehe Fig. 1) gespeichert. Die Pixelkettentabelle, die für die Pixel der Fig. 3 erzeugt wurden, wird in Tabelle 2 unten fortgesetzt. Tabelle 2 Pixelkettentabelle
Das System 10 formatiert die Pixelkettenlisten derart, dass ein leichtes Kodieren jeder der Pixelketten ermöglicht wird. Jede formatierte Pixelkettenliste umfasst einen Kopf, der Informationen enthält, die sich auf die Position der oberen linken Ecke der Pixelkette in der Rasterbilddatei und auf die Länge der Pixelkette (Anzahl der horizontalen Scannreihe) beziehen, gefolgt durch die Daten für jede horizontale Scannreihe in der Pixelkette. Unter Benutzung der Daten von Tabelle 2 für Pixelkettennummer 1 bis 3 sind die formatierten Pixelkettenlisten in Tabelle 3 unten dargestellt. Tabelle 3
Die X und Y-Offsets in dem Kopf für die erste Pixelkette (Pixelkette Nr. 1) geben an, dass die Pixelkette bei dem ersten Pixel der ersten horizontalen Scannreihe beginnt. Ähnlich geben die X und Y-Offsets in den Köpfen für die zweite und dritte Pixelketten (Pixelketten Nr. 2 und Pixelketten Nr. 3, entsprechend) an, dass sie bei dem vierten Pixel der ersten horizontalen Scannreihe und bei dem fünften Pixel der siebten horizontalen Scannreihe entsprechend beginnen. Die Y-Ausdehnung in dem Kopf für die erste Pixelkettenliste gibt an, dass die Pixelkette sechs horizontale Scannreihen lang ist, während die Y-Ausdehnung in den Köpfen für die zweite und dritte Pixelkette angibt, dass sie eine Länge von fünf und einer horizontalen Scannreihe entsprechend aufweisen. In dieser Art wird die gesamte Rasterbilddatei in eine Reihe von einer oder mehrerer Pixelketten gesetzt.
Wenn das System 10 die Pixelkettenlisten einmal definiert, die Pixelkettenlisten in der Pixelkettentabelle 28 (siehe Fig. 1) gespeichert und die Pixelkettenlisten in der Art wie oben beschrieben formatiert hat, kodiert es jede Pixelkette unabhängig mit Deltakodierung auf jede Pixelkette. Die Deltakodierung ist eine bekannte Art der Datenkodierung, die hier kurz beschrieben werden soll. Es ist für das System 10 nicht notwendig, alle Pixelketten komplett zu definieren, bevor die Deltakodierung beginnen kann. Beispielsweise ist die zweite Pixelkette in Fig. 3 während der Analyse der horizontalen Scannreihe 72f geschlossen. Die Pixelkettenkodiereinheit 30 (siehe Fig. 1) kann mit der Kodierung der zweiten Pixelkette beginnen, während der Pixelkettengenerator 26 die Einträge in der Veränderungsvektortabelle 24 für die horizontale Scannreihe 72g analysiert.
Die Pixelkettenkodiereinheit 30 kodiert jede Pixelkette durch Kodieren der Pixelkettendaten, die mit jeder horizontalen Scannreihe der Pixelkette relativ zu den Pixelkettendaten in der vorherigen horizontalen Scannreihe zugewiesen sind. Dadurch werden die Pixelkettendaten in jeder horizontalen Scannreihe als ein Delta- oder Offsetwert kodiert, der zu den Pixelkettendaten der vorhergehenden horizontalen Scannreihe relativ ist. Beispielsweise wird die erste Pixelkette der Fig. 3 in Fig. 5 allein dargestellt, um den Kodierungsprozess besser darzustellen. Wie vorhergehend diskutiert, gibt Tabelle 3 an, dass die erste Pixelkette bei dem ersten Pixel der ersten horizontalen Scannreihe beginnt und sechs horizontale Scannreihen lang ist. Das erste Veränderungsvektorpaar in dem Datenanteil der formatierten ersten Pixelkettenliste der Tabelle 3, die dem Kopf folgt, ist das Veränderungsvektorpaar (0, 1). Das nächste Veränderungsvektorpaar (1, 4) für die erste Pixelkette wird zu dem vorherigen Eintrag relativ kodiert. Für das Beispiel von Fig. 3 sind die Deltawerte für das nächste Veränderungsvektorpaar (1, 4) für die erste Pixelkette (+1, +3), die angeben, dass die Folge von schwarzen Pixeln in der nächsten horizontalen Scannreihe ein Pixel nach rechts von der vorherigen Anfangsposition beginnt und drei Pixel rechts von der vorherigen Endposition endet. Diese Deltawerte können einfach durch Subtrahieren der vorherigen Pixelkettendaten von den aktuellen Pixelkettendaten ermittelt werden. Die originalen Pixelkettenveränderungsvektorpaare und die Deltawerte für die erste Pixelkette sind in Tabelle 4 unten gezeigt.

Tabelle 4

Pixelketten Nr. 1 Deltakodierungswerte
X Offset = 0
Y Offset = 0
Y Ausdehnung = 1
(0, 1) (0, 1)
(1, 4) (+1, +3)
(0, 3) (-1, -1)
(1, 3) (+1, 0)
(1, 3) (0, 0)
(1, 3) (0, 0)
Wie aus Tabelle 4 erkannt werden kann, kann die Benutzung einer Deltakodierung die Größe der Datenwerte reduzieren, da jeder Deltawert nur ein Offset von dem vorherigen Datenwert ist. Die Deltawerte sind im allgemeinen klein, da Pixelketten, per Definition, eng verwandte Pixel innerhalb einer Bitmapdatei sind. Jeder Deltawert wird durch mehrere Datenbits repräsentiert. Da die meisten Deltawerte dazu tendieren klein zu sein, macht es den Kodierungsprozess berechenbarer. Wie in größerem Detail unten dargestellt, ermöglicht dies der Deltakodierung eine kleinere Anzahl von Datenbits für die gebräuchlichsten Offsetwerte und eine größere Anzahl von Datenbits für größere, weniger gebräuchliche Offsetwerte zu benutzen. Diese Art der statistischen Kodierung ist im Stand der Technik bekannt. Beispielsweise beruht eine Modifizierte Huffman-Kodierung, die gewöhnlich bei der Faxdatenkodierung benutzt wird, auf Statistiken, um eine kleine Anzahl von Datenbits für gebräuchlichere Datenmuster auszuwählen und eine größere Anzahl von Datenbits für weniger gebräuchliche Datenmuster.
Die in Fig. 6 gezeigte Kurve stellt die statistische Beschaffenheit des Deltakodierungsprozesses für Pixelketten dar. Ein Null-Offsetwert ist sehr gebräuchlich und tritt mit der höchsten Häufigkeit auf. Die Offsetwerte +1 und -1 sind die nächsten gebräuchlichsten Werte. Andere Offsetwerte treten mit niedrigerer Häufigkeit auf. Das System 10 benutzt zwei Datenbits, um die drei gebräuchlichsten Offsetwerte darzustellen. Beispielsweise stellt das Datenbit 00 einen Null-Offsetwert dar. Das Datenbit 01 stellt einen +1 Offsetwert dar, während die Datenbits 11 einen -1 Offsetwert darstellen. Weniger gebräuchliche Offsetwerte werden mit mehr Datenbits dargestellt. Beispielsweise stellen die Datenbits 1011 einen +2 Offsetwert dar, während die Datenbits 1010 einen 2 Offsetwert darstellen. Ähnlich stellen die Datenbits 1001 einen +3 Offsetwert dar. Mehr Datenbits sind erforderlich, um weniger gebräuchliche Datenbits darzustellen. Durch Benutzung der Deltakodierungswerte für die erste Pixelkette in Tabelle 4 und die oben beschriebenen Datenbitmuster, kann man bestimmen, dass die kodierten Daten für die erste Pixelkette wie folgt lauten: 00 01 01 1001 11 11 01 00 00 00 00 00.
Die kodierten Daten, die von der Pixelkettenkodiereinheit 30 erzeugt wurden, erfordern keine Abgrenzung, um das Ende von einem Code und den Anfang eines neuen Codes zu identifizieren. Die Datenbits in jedem der Codes sind einmalig und das System 10 erkennt das Ende eines speziellen Codes durch das Muster der Datenbits in dem Code. Diese Kodierung benutzt das bekannte Präfix-Eigentum des Huffman-Codes. Beispielsweise stellen die ersten Datenbits 00 in dem obigen Beispiel einen Null-Offsetwert dar. Es gibt kein anderes Datenbitmuster, das mit den Datenbits 00 beginnen. Dadurch erkennt das System die Datenbits 00 als kompletten Code. Ähnlich stellen die Datenbits 01 einen +1 Offsetwert dar. Es gibt kein anderes Datenbitmuster, das mit den Datenbits 01 beginnt. Somit ist jeder Code einmalig durch die Muster der Datenbits identifiziert.
Sobald die deltakodierten Datenbits, die die Offsetwerte darstellen, von der Pixelkettenkodiereinheit 30 bestimmt wurden, können die pixelkodierten Datenbits weiter komprimiert werden, bevor sie zu einem empfangenden Computer übertragen werden. Dazu benutzt das System 10 eine LZ-Datenkompression, die die deltakodierten Datenbits weiter komprimiert. LZ-Datenkompression ist im Stand der Technik bekannt und wird hier nicht beschrieben. Alternativ kann eine Anzahl von anderen bekannten Kompressionstechniken, wie Lauflängenkodierung (RLE) oder eine Huffman-Kodierung benutzt werden. Die vorliegende Erfindung ist nicht auf eine spezifische Reihenfolge begrenzt, in der die Kompressionstechniken angewendet werden. Beispielsweise könnte das System 10 eine Huffman-Kodierung durchführen, der eine LZ-Datenkompression folgt. Alternativ könnte das System 10 zuerst eine LZ- Datenkompression benutzen, der eine Huffman-Kodierung folgt. Die komprimierten Daten für die Pixelketten sind in dem Speichergebiet 32 für komprimierte Daten (siehe Fig. 1) gespeichert, das ein Teil des Speichers 14 sein kann.
Die komprimierten Daten in dem Speichergebiet 32 für komprimierte Daten können in die Textdaten oder Faxnachricht, wie zuvor beschrieben, eingebettet werden und zusammen mit den Daten oder der Nachricht übertragen werden. Die komprimierten Daten können durch das Umkehren des auf die Daten angewendeten Kompressionsverfahrens effizient dekomprimiert werden. Da Kompression und Dekompression von Daten im Stand der Technik bekannt sind, wird es hierin nicht weiter beschrieben.
Die Pixelkettendaten können das Umkehren des oben beschriebenen Verfahrens dekodiert werden durch. Es kann erkannt werden, dass die Datenbitmuster für die erste Pixelkette die Offsetwerte vom Beginn der Pixelkette angeben. Die X-und Y-Offsets und die Y-Ausdehnung geben die Position und Anzahl von horizontalen Scannzeilen für die erste Pixelkette an. Mit dieser Information kann das Dekodierungsverfahren einfach durchgeführt werden. Für Daten, die einige Mehrfachpixelketten enthalten, kann jede Pixelkette sukzessive in einen einfachen Speicher dekomprimiert werden, der die vorherigen Pixelketten mit einer logischen Oder-Verknüpfung kombiniert. Das Ausfüllen einer Folge von Pixeln ist schnell, insbesondere für sich wiederholende Folgen, die in eine Maschinen-Wordbreite (z. B. 32 Bit) passen.
Die Pixelkettenrepräsentation ermöglicht es Rasterbilddaten, wie einen Zeichenschriftartsatz, in einer deutlich kleineren Menge an Platz, anzuzeigen als ein typischer Zeichenschriftartsatz. Die Daten in Tabelle 5 unten geben die Menge an Datenspeicher an, der für typische Zeichenschriftartsätze unter Benutzung konventioneller Techniken, für dieselben Zeichenschriftartsätze, die vom System 10 in Pixelketten verarbeitet wurden, und für die Pixelketten, die weiter mit einer LZ- Datenkompression komprimiert wurden, erforderlich ist. Tabelle 5 Schriftgröße (Kbyte)
Wie aus Tabelle 5 erkannt werden kann, erfordert ein 12 Punkte Times-Roman Zeichenschriftartsatz 14,4 Kbytes an Speicher in bekannten Systemen. Im Gegensatz dazu ermöglicht System 10 denselben Zeichenschriftartsatz in weniger als 3,5 Kbyte zu speichern. Die Kompression der Pixelkettendaten mit LZ-Datenkompression erfordert bei demselben Zeichenschriftartsatz nur 1,5 Kbytes. Die Benutzung des Systems 10 ermöglicht dadurch eine Einsparung von nahezu 13 Kbyte. Für größere Schriftarten ist die Einsparung an Platz noch größer.
Während mit Datenkompression selbst Platz gespart werden kann, wenn man es mit den Zeichenschriftsatzdaten vergleicht, ermöglicht das System 10 größere Platzeinsparungen als die, die mit einer Datenkompression allein erreicht werden würden. Die Daten, die in Tabelle 6 unten gezeigt werden, geben die Kompressionsverhältnisse für Pixelketten allein, für LZ-Datenkompression allein und für die Kombination von Pixelketten und LZ- Datenkompression an. Tabelle 6 Kompressionsverhältnis (X : 1)
Wie aus Tabelle 6 erkannt werden kann, führt die Pixelkettenverarbeitung eines 12 Punkte Times-Roman Zeichenschriftartsatzes zu einem 4,1 : 1 Kompressionsverhältnis für die Zeichenschriftartsatzdaten. Die Benutzung der LZ-Datenkompression allein führt zu einem 2,3 : 1 Kompressionsverhältnis. Dies zeigt an, dass das Pixelkettenrasterungsverfahren allein eine Verbesserung gegenüber der Benutzung der Datenkompression allein darstellt. Wenn die Pixelkettenrasterung mit der LZ-Datenkompression kombiniert wird, ist das Kompressionsverhältnis 9,4 : 1. Dadurch kann leicht erkannt werden, dass das System 10 ein brauchbares Werkzeug zur Verarbeitung von Rasterbilddaten darstellt. Die Platzeinsparungen und die Einfachheit der Verarbeitung der Daten unter Benutzung von System 10 bedeutet, dass viel mehr Geräte Bildverarbeitungsmöglichkeiten enthalten können. Die Geräte haben letztlich niedrigere Kosten, da weniger Speicher erforderlich ist, um die Bilddaten zu verarbeiten und weniger hoch entwickelte und weniger teure CPUs erforderlich sind, um die Daten zu verarbeiten.
Es ist zu verstehen, dass trotz der verschiedenen Ausführungen und Vorteile der vorliegenden Erfindung die obige Beschreibung fortgesetzt werden könnte, und die obige Offenbarung nur erläuternden Charakter hat und Veränderungen im Detail vorgenommen werden können, die jedoch innerhalb der breiten Prinzipien der Erfindung verbleiben. Darum ist die vorliegende Erfindung nur durch die angefügten Ansprüche begrenzt.

Claims

1. System (10) zur Erzeugung einer kodierten Datei aus einer Bitmap-Datei, die ein orthogonales Feld (70) von Pixeln darstellt, mit Pixelreihen (72a-72g), die in einer ersten Dimension angeordnet sind und einer Mehrzahl von Pixelreihen (72a- 72g), die in einer zweiten Dimension angeordnet sind, wobei jedes der Pixel einen ersten oder einen zweiten logischen Zustand aufweist, das System (10) umfassend:

einen Pixelketten-Generator (26) zur Aufteilung des orthogonalen Feldes (70) von Pixeln in eine Mehrzahl von Pixelketten-Gebiete, wobei jedes der Pixelketten-Gebiete angrenzende Pixel mit dem ersten logischen Zustand enthält, jedes Pixelketten-Gebiet von einer entsprechenden Pixelkettenliste repräsentiert wird, die Listeneinträge enthält, jeder Listeneintrag eine Folge von aufeinanderfolgenden Pixeln repräsentiert, die in der ersten Dimension aneinandergrenzend sind und ein Veränderungsvektorpaar enthält, welches die Position und die Länge der Folge anzeigt, wobei der Pixelketten-Generator (26) angepasst ist:

um jede der Mehrzahl von Pixelreihen (72a-72g) sequentiell zu analysieren (84);

um eine offene Pixelkettenliste für jede Folge von aufeinanderfolgenden Pixeln in einer aktuellen Pixelreihe (72a-72g) zu erzeugen, wenn die aktuelle Reihe die erste Pixelreihe (72a) in der zweiten Dimension ist oder wenn die aktuelle Folge von aufeinanderfolgenden Pixeln in der aktuellen Reihe keine Pixel enthält, die an Pixel irgendeiner Folge von aufeinanderfolgenden Pixeln der Pixelreihe (72a- 72g) angrenzen, die unmittelbar der aktuellen Reihe vorausgehen;

um einer offenen Pixelkettenliste einen zusätzlichen Listeneintrag hinzuzufügen, der eine zusätzliche Folge von aufeinanderfolgenden Pixeln repräsentiert, wenn die Pixelkettenliste einen Listeneintrag enthält, der eine Folge von aufeinanderfolgenden Pixeln repräsentiert, die Pixel enthält, die zu Pixeln der zusätzlichen Folge angrenzend sind; und

um die offene Pixelkettenliste zu schließen, wenn keine neuen Listeneinträge hinzugefügt werden können;

dadurch gekennzeichnet, dass das System weiterhin aufweist

eine Kodieranalyseeinheit (30) zur gesonderten Kodierung jeder Pixelkettenliste durch Benutzung einer Deltakodierung, wobei jedes Veränderungsvektorpaar, das einen zusätzlichen Listeneintrag in der Pixelkettenliste repräsentiert, als ein Paar Offsetwerte kodiert wird, relativ zu dem Veränderungsvektorpaar, das den unmittelbar vorausgehenden Listeneintrag repräsentiert, um dadurch kodierte Daten für jede der Pixelkettenlisten zu erzeugen.

2. System (10) nach Anspruch 1 weiter enthaltend:

einen Veränderungsvektorgenerator (22), der an den Pixelketten-Generator (26) gekoppelt ist, um jede der Mehrzahl von Pixelreihen (72a-72g) sequentiell zu analysieren, um die Veränderungsvektorpaare zu bestimmen.

3. System (10) nach Anspruch 1 oder 2, wobei die Kodieranalyseeinheit (30) weiterhin ausgeführt ist, um unabhängig vom Pixelketten-Generator (26) zu operieren, um geschlossene Pixelkettenlisten zu kodieren.

4. System (10) nach einem der Ansprüche 1 bis 3, weiter umfassend:

ein Dateispeichergebiet (16) enthaltend die Bitmap-Datei in unkomprimierter Form; und

ein Datenspeichergebiet (32) zur Speicherung der kodierten Daten.

5. System (10) nach einem der vorhergehenden Ansprüche 1 bis 4, weiter enthaltend:

einen Kompressor zum Empfangen der kodierten Daten und zum Erzeugen der komprimierten kodierten Daten.

6. System (10) nach Anspruch 5, wobei der Kompressor die kodierten Daten unter · Benutzung eines vorbestimmten Kompressionsformates komprimiert, das wenigstens eine RLE-Kompression, LZ-Kompression oder Huffmann-Kompression umfasst.

7. System (10) nach einem der vorhergehenden Ansprüche, wobei der Pixelketten- Generator (26) erste und zweite Offsetdatenwerte für jedes der Pixelkettengebiete erzeugt, die einen Ort von jedem der Pixelkettengebiete in der entsprechenden ersten und zweiten Dimension anzeigen.

8. System (10) nach einem der vorhergehenden Ansprüche, wobei der Pixelketten- Generator (26) einen Längendatenwert erzeugt, der eine Länge von jedem der Pixelkettengebiete in der zweiten Dimension anzeigen.

9. Verfahren zur Benutzung eines Computers zur Erzeugung einer kodierten Datei aus einer Bitmap-Datei, die ein orthogonales Feld (70) von Pixeln mit Pixelreihen (72a-72g), die in einer ersten Dimension angeordnet sind und einer Mehrzahl von Pixelreihen (72a-72g), die in einer zweiten Dimension angeordnet sind, repräsentieren, wobei jedes der Pixel einen ersten oder zweiten logischen Zustand aufweist, das Verfahren aufweisend:

die Aufteilung des orthogonalen Feldes (70) von Pixeln mittels eines Pixelketten- Generators (26) in eine Mehrzahl von Pixelkettengebiete, wobei jedes der Pixelkettengebiete aneinandergrenzende Pixel mit dem ersten logischen Zustand enthält, jedes Pixelkettengebiet von einer entsprechenden Pixelkettenliste repräsentiert wird, die Listeneinträge enthält, jeder Listeneintrag eine Folge von aufeinanderfolgenden Pixeln darstellt, die in einer ersten Dimension aneinandergrenzen und ein Veränderungsvektorpaar enthält, welches die Position und die Länge der Folge enthält, durch:

- das sequentielle Analysieren (84) von jeder der Mehrzahl von Pixelreihen (72a- 7g);

- das Erzeugen einer offenen Pixelkettenliste für jede Folge von aufeinanderfolgenden Pixeln in einer aktuellen Pixelreihe (72a-72g), wenn die aktuelle Reihe die erste Pixelreihe (72a) in der zweiten Dimension ist, oder wenn die aktuelle Folge von aufeinanderfolgenden Pixeln in der aktuellen Reihe keine Pixel enthält, die an Pixel irgendeiner Folge von aufeinanderfolgenden Pixeln in den Pixelreihen (72a-72g) angrenzen, die der aktuellen Reihe unmittelbar vorausgehen;

- das Hinzufügen eines zusätzlichen Listeneintrages zu einer offenen Pixelkettenliste, der eine zusätzliche Folge von aufeinanderfolgenden Pixeln repräsentiert, wenn die Pixelkettenliste einen Listeneintrag enthält, der eine Folge von aufeinanderfolgenden Pixeln repräsentiert, die Pixel enthält, die an Pixel der zusätzlichen Folge angrenzen; und

- das Schließen der offenen Pixelkettenliste, wenn keine neuer Listeneintrag hinzugefügt werden kann;

dadurch gekennzeichnet, dass das Verfahren weiter umfasst:

- ein separates Kodieren jeder Pixelkettenliste unter Benutzung einer Deltakodierung, wobei jedes Veränderungsvektorpaar, welches einen zusätzlichen Listeneintrag in einer Pixelkettenliste repräsentiert, als ein Paar von Offsetwerten in Bezug zu dem Veränderungsvektorpaar, welches den unmittelbar vorausgehenden Listeneintrag repräsentiert, kodiert wird, um dadurch kodierte Daten für jede der Pixelkettenlisten zu erzeugen.

10. Verfahren nach Anspruch 9, weiter umfassend:

ein sequentielles Analysieren von jeder der Mehrzahl der Pixelreihen (72a-72g) mittels eines Veränderungsvektorgenerators (22), der an den Pixelketten- Generator (26) gekoppelt ist, um die Veränderungsvektorpaare zu bestimmen.

11. Verfahren nach Anspruch 10, bei dem der Schritt der Kodierung der Pixelkettenliste unmittelbar nach dem Schließen der Pixelkettenliste durchgeführt wird.

12. Verfahren nach einem der Ansprüche 9 bis 11, weiter umfassend die Schritte:

Speicherung der kodierten Daten.

13. Verfahren nach einem der Ansprüche 10 bis 12, weiter umfassend:

Komprimieren der kodierten Daten.

14. Verfahren nach Anspruch 13, wobei der Schritt der Kompression ein vorbestimmtes Kompressionsformat benutzt, umfassend wenigstens eine RLE- Kompression, LZ-Kompression oder Huffmann-Kompression, um die kodierten Daten zu komprimieren.