PatentDe  


Dokumentenidentifikation DE69936755T2 06.12.2007
EP-Veröffentlichungsnummer 0001001607
Titel Verfahren und Vorrichtung zur Analyse von Bilddaten um mehrere Umwandlungen für verbesserte Bilddatenübertragung durchzuführen
Anmelder Xerox Corp., Rochester, N.Y., US
Erfinder De Queiroz, Ricardo L., Pittsford,NY 14534, US
Vertreter Grünecker, Kinkeldey, Stockmair & Schwanhäusser, 80538 München
DE-Aktenzeichen 69936755
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 11.11.1999
EP-Aktenzeichen 991225111
EP-Offenlegungsdatum 17.05.2000
EP date of grant 08.08.2007
Veröffentlichungstag im Patentblatt 06.12.2007
IPC-Hauptklasse H04N 1/333(2006.01)A, F, I, 20051017, B, H, EP
IPC-Nebenklasse H04N 1/40(2006.01)A, L, I, 20051017, B, H, EP   H04N 1/41(2006.01)A, L, I, 20051017, B, H, EP   G06T 9/00(2006.01)A, L, I, 20051017, B, H, EP   

Beschreibung[de]

Die vorliegende Erfindung bezieht sich auf ein Verfahren und eine Vorrichtung zur Komprimierung von digitalen Bilddaten so, dass eine Datenübertragungsgeschwindigkeit mit der Geschwindigkeit eines dazugehörigen Modems übereinstimmt. Im Speziellen erfüllt die Erfindung die Bildübertragung, indem sie mehrere Komprimierer implementiert, von welchen jeder Bilddaten komprimiert, um einen unterschiedlichen Grad an Ausgangsbildqualität zu erreichen. Durchgehend während der Übertragung führt die Erfindung das Senden der Bilddaten an den Komprimierer weiter, der sie verarbeiten wird so, dass ein angemessener Grad an Bildqualität beibehalten wird, während sie gleichzeitig in einer Geschwindigkeit ausgegeben werden, die eine effiziente serielle Datenübertragung zur Folge haben wird.

Die Übertragung von elektronischen Daten via Faxgeräten und ähnlichen Apparaten ist ziemlich üblich geworden, und es werden kontinuierlich Anstrengungen gemacht, um bedeutsam größere Mengen von diesen Daten innerhalb der gleichen oder sogar beträchtlich geringeren Zeitabschnitten zu übertragen. Dies trifft nicht nur zu, um zu ermöglichen, dass Daten von einer Stelle zu einer anderen mit höheren Geschwindigkeiten gesendet werden und dabei weniger Schwierigkeiten bei dem Benutzer verursacht werden, sondern um zu erreichen, dass komplexere Daten zwischen denselben Orten übertragen werden, ohne drastisch die benötigte Übertragungszeit zu erhöhen. Zum Beispiel wird die Faxübertragungszeit für ein detailliertes Halbtonbild um einige Male höher sein, als die eines einfachen Blattes mit schwarzem Text auf einer weißen Seite, wenn man das gleiche Faxgerät benutzt. Aus demselben Grund werden Faxübertragungen eines Farbbildes eine sogar noch größere Zeit benötigen, als sein hochdetailliertes Halbtongegenstück.

Der "Sende"-Teil einer Faxübertragung beinhaltet das Scannen des Originalbildes und das Erzeugen eines entsprechenden digitalen Bildes davon, gefolgt durch eine serielle Übertragung von Digitalbilddaten zu einem Empfängerfaxgerät. Ohne jegliche Form von Datenreduktion würde die Übertragung von Dateien mit Farbbilddaten via Fax umfassende Ressourcen benötigen – sehr schnelle Modems und/oder große Puffer – und würde dennoch eine große Menge Zeit benötigen, wobei erreicht wird, dass solch eine Übertragung sehr teuer und deshalb unpraktikabel wird. Deshalb wird typischerweise vor der Faxübertragung von Farbbilddaten irgendeine Form von Datenkomprimierung angewendet.

Der JPEG (Joint Photographic Experts Group) Standard stellt eine wohl bekannte Methode zur Komprimierung von elektronischen Daten bereit. JPEG benutzt die diskrete Kosinustransformation (DCT), um räumliche Daten in räumliche Frequenzbereichdaten abzubilden. In Kürze, zuerst muß JPEG einen 8 × 8 Block von Pixeln in einen Satz von 8 × 8 Koeffizienten unter Verwendung der DCT transformieren, um einen DC-Koeffizienten (DCC) zu erzeugen, und einen Satz von AC-Koeffizienten (ACCs). Die DCC und ACCs werden quantisiert, zur nächsten ganzen Zahl gerundet und in einem eindimensionalen Vektor angeordnet, welcher in einen Bitdatenstrom codiert wird.

Da Farbbilddaten so komplex sind, benötigen herkömmliche Daten-Komprimierungsverfahren die Anwendung von hohen Komprimierungsraten, um die Übertragung innerhalb eines akzeptablen Zeitfensters fertigzustellen. Höhere Komprimierungsraten führen zu größeren Datenverlusten, typischerweise am oberen Ende des Frequenzbereiches.

Eine erfolgreiche Faxübertragung erfordert eine geeignete Übereinstimmung zwischen der Komprimierungsrate, die auf das Bild angewendet wird, und der CPU-Geschwindigkeit des Sendefaxgerätes. In anderen Worten, wenn die Komprimierungsrate kleiner ist als für eine gegebene CPU-Geschwindigkeit benötigt wird, muss die CPU verlangsamt werden, oder die Daten müssen warten, um übertragen zu werden, und ein entsprechend dimensionierter Puffer wird benötigt. Auf der anderen Seite bedeuten höhere Komprimierungslevel, dass sehr wenige Bits erzeugt werden und weniger Daten über das Modem gesendet werden müssen. Wenn die Komprimierungsrate bezüglich der CPU-Geschwindigkeit hoch ist, wird das Modem inaktiv werden, darauf wartend, dass die CPU die Bildverarbeitung beendet und mehr Daten überträgt. Da Modems typischerweise konfiguriert sind eine große Pause in den Datenübertragungen als das Ende der Übertragung zu bestimmen, wird diese lange Leerlaufzeit typischerweise verursachen, dass das Modem die Verbindung unterbricht. Deshalb ist es vorteilhaft, den Strom von Daten vom Sendefaxgerät zu dem Empfängerfaxgerät fortzuführen und Lücken in dem Datenstrom zu beseitigen. Ein Weg dies zu tun, ist offensichtlich einen schnelleren JPEG-Komprimierer zu implementieren, der es schafft, die Daten durch das Modem zu bewegen, sogar wenn eine hohe Komprimierungsrate verwendet wird. Allerdings resultiert diese Lösung in beträchtlichen Kostensteigerungen und kann inpraktikabel sein.

Ein Weg um eine geeignete Übereinstimmung zwischen der Kompressionsrate und der Taktgeschwindigkeit beizubehalten, ist mehrere Komprimierer bereitzustellen, an denen Teile der digitalen Bilddaten übertragen werden können. Wenn der Teil des zu bearbeitenden Bildes viel bildhaftes oder andere Daten enthält, die eine hohe Qualitätswiedergabe benötigen, sollten diese Daten durch den Komprimierer bearbeitet werden, der die beste Bildqualität liefern wird. Allerdings, wenn der Teil des zu bearbeitenden Bildes Text oder andere Daten enthält, die eine hohe Qualitätswiedergabe nicht benötigen, können diese Bilddaten an einen Komprimierer weitergeleitet werden, der eine geringere Qualitätsausgabe erzeugt, um von der Tatsache zu profitieren, dass eine niedrigere Qualitätsausgabe durch einen Komprimierer mit einer viel schnelleren Verarbeitungsgeschwindigkeit erzeugt werden kann. Wenn Text oder andere einfache Daten verarbeitet werden, werden Unterschiede zwischen einer Bildqualität, die durch einen Prozessor erzeugt wird, der eine hohe Qualitätsausgabe erzeugt, und einer, die durch einen Prozessor erzeugt wird, der eine geringere Qualitätsausgabe erzeugt, tatsächlich kaum durch das menschliche Auge erfasst.

Alle Pixel, und deshalb Blöcke von Pixeln, werden definiert, indem eine gewisse Anzahl von Bits benutzt wird. In einer Bildverarbeitungsoperation, die als Vektorquantisierung (VQ) bekannt ist, wird ein Block von X × Y Pixeln auf ein einzelnes "Codewort" abgebildet, welches definiert wird, indem eine kleinere Anzahl an Bits benutzt wird als die Anzahl, die durch den Originalblock benötigt wird. Codewörter werden in Übertragungs-, Empfangs- und Speichergeräten gespeichert, und jedes Codewort ist mit einem vordefinierten Satz an Bilddaten verknüpft. Das Codewort, auf welchem jeder Pixelblock abgebildet wird, ist jenes, welches mit den Bilddaten verknüpft ist, die am ehesten mit den Bilddaten in dem Pixelblock übereinstimmen. Der übliche Verlauf umfasst das Abbilden des Pixelblockes auf ein Codewort, das Speichern des Codeworts oder das Übertragen davon zu einem Empfangsgerät, und danach die Abbildung des Codeworts zurück zu den Bilddaten, wenn es aus dem Speicher abgerufen wird, oder in dem Empfangsgerät empfangen wird. Da Codebuchspeicherung und die Codewortübertragung weniger Platz und Zeit beanspruchen, als die Speicherung und Übertragung von Originalbilddaten, verringert dieser Prozess beträchtlich die Ressourcen, die benötigt werden, um die Originalbilddaten wiederzugeben.

Es gibt typischerweise viel mehr Kombinationen von Pixelblöcken, als es verfügbare Codewörter gibt, und wie durch den Ausdruck "Quantisierung" angedeutet, können mehrere Eingabeblöcke zu einem einzelnen Codewort abgebildet werden. Für eine feste Anzahl von Codewörtern reduziert eine Erhöhung der Größe des Pixelblockes die Qualität der Abbildung und Rekonstruktion, da mehr eigentliche Bilddaten auf dieselbe Anzahl von Codewörtern abgebildet werden müssen. Einige Nachteile von VQ sind, dass das Codebuchdesign oft sehr komplex ist, und dass üblicherweise eine große Menge Zeit benötigt wird, um durch das Codebuch zu suchen und um die Blöcke mit dem geeigneten Codewort in Übereinstimmung zu bringen. Während der Entwurf des Codebuchs off-line ausgeführt werden kann, müssen die Suchen nach Übereinstimmung der Blöcke on-line ausgeführt werden.

In der hierarchischen Vektorquantisierung (HVQ) werden die Suchen nach Übereinstimmung der Blöcke jeweils mit zwei Mustern ausgeführt. Deshalb können Nachschlagetabellen (im Englischen: look up tables, LUTs) direkt dazu benutzt werden, um HVQ in zwei oder mehreren Stufen auszuführen. In der ersten Stufe werden zwei Bildpixel auf ein Codewort abgebildet, wobei die Anzahl der Muster um einen Faktor von 2 reduziert wird. In der nächsten Stufe wird dieser Prozess wiederholt, um Paare von Codewörtern auf einzelne Codewörter abzubilden. Vorzugsweise werden Codewörter in einer Richtung gruppiert, die senkrecht zu jener ist, die für die vorherige Stufe verwendet worden ist. Während der Prozess fortgeführt wird, werden die resultierenden Codewörter auf größere und größere Menge von Daten abgebildet.

HVQ erlaubt eine grobe Annäherung an den Inhalt von jedem Bildblock, indem einfache Nachschlagtabellenoperationen verwendet werden. Das endgültige Codewort repräsentiert eine Blockannäherung und kann deshalb direkt auf andere Mengen abgebildet werden, die bestimmte Charakteristiken des angenäherten Blocks beschreiben, wie z.B. die Blockaktivität. Methoden zur Gestaltung von HVQ-Codebüchern befolgen die Standardgestaltungsalgorithmen von VQ-Codebüchern und werden üblicherweise ausgeführt indem Codebücher für jeweils eine einzelne Stufe entworfen werden.

Die folgenden Offenbarungen können für Aspekte der vorliegenden Erfindung relevant sein:

US-A 5,699,457 an Adar et al., das am 16. Dezember 1997 erteilt worden ist, offenbart ein Verfahren zur Steuerung einer Bitrate, und die Einteilung von Blöcken für eine Komprimierung eines diskreten Kosinustransformations(DCT)-Bildsignals, umfasst die Schritte von (a) Aufteilen der Bildsignale in Blöcke, die Teile des kompletten Bildes repräsentieren, (b) Berechnung von DCT-Koeffizienten für Bilddaten in allen Blöcken, (c) Beschaffen eines Maßes der Blockaktivität (BACT) für jeden Block, basierend auf DCT-Koeffizienten, und für die komplette Bildaktivität (ACT) als eine Summe der Maße für die komplette Blockaktivität, und (d) Bestimmung eines Codeeinteilungsfaktors (AF) für jeden Block, basierend auf dem Verhältnis zwischen der Blockaktivität (BACT) und der Zielcodemenge (TCV-Daten) für die kodierten Bilddaten. Das Verfahren umfasst auch (e) die Einteilung von Bits für jeden Block, indem der Einteilungsfaktor (AF) für jeden Block und die Zielcodemenge (DCV-Daten) verwendet werden.

US-A 5,699,170 an Yokose et al., das am 16. Dezember 1997 erteilt wurde, offenbart ein Bildkommunikationssystem, in welchem Übertragungen eines Bildes zwischen einer Bildübertragungsvorrichtung und einer Bildempfangsvorrichtung ausgeführt werden können, die Bildausgabeabschnitte umfassen, die unterschiedliche Leistungen besitzen, ohne vor der Übertragung eine Abfrage der Leistung zu machen. Ein Bild wird durch einen Bildeingabeabschnitt eingegeben und an einen Rangordnungsabschnitt in der Bildübertragungsvorrichtung gesendet. Der Rangordnungsabschnitt konvertiert das eingegebene Bild in hierarchische Kommunikationsdaten und überträgt gestaffelte Daten an einen Auswahlabschnitt der Bildempfangsvorrichtung. Der Auswahlabschnitt extrahiert nur benötigte Daten aus den zugesendeten hierarchischen Kommunikationsdaten, entsprechend der Leistung eines Bildausgabeabschnittes des Bildempfangsabschnittes und sendet dann die benötigten Daten zu dem Bildausgabeabschnitt, nachdem sie, wenn notwendig, in Bilddaten konvertiert wurden. Der Bildausgabeabschnitt visualisiert die Bilddaten, die von dem Auswahlabschnitt dorthin übertragen wurden.

US-A 5,642,438 an Babkin, das am 24. Juni 1997 erteilt wurde, legt eine Bildkomprimierung offen, die eine schnelle zweidimensionale diskrete Kosinustransformation implementiert. Im speziellen offenbart Babkin ein Verfahren und eine Vorrichtung zur Durchführung einer zweidimensionalen diskreten Kosinustransformation (DCT) für ein 8 × 8 Bildbruchstück mit drei Stufen für die Annäherung der DCT-Koeffizienten.

US-A 5,341,441 an Maeda et al., das am 23. August 1994 erteilt wurde, legt ein Verfahren und eine Vorrichtung zur Codierung von Bildinformationen offen und ein Verfahren zur Erzeugung von Codebüchern. Eine Codevorrichtung teilt digitale Bildinformationen in Pixelblöcke, die jeweils eine Größe von M × N-Pixeln besitzen, und unterzieht die Bildinformation einer Vektorquantisierung in Blockeinheiten. Die Pixelblöcke werden orthogonal transformiert, und die Charakteristiken und Sequenzkomponenten der Pixelblöcke werden detektiert. Jeder Pixelblock wird in eine Vielzahl von Unterblöcken in Übereinstimmung mit den detektierten Sequenzkomponenten unterteilt. Entsprechende der Vielzahl an geteilten und ausgegebenen Unterblöcken werden in Untervektoren einer vorbestimmten Anzahl von Bits Skalar-quantisiert in Übereinstimung mit den Charakteristiken der Pixelblöcke. Entsprechende der Skalar-quantisierten Werte der quantisierten Unterblöcke werden in Übereinstimmung mit den Charakteristiken der Pixelblöcke Vektor-quantisiert, wobei diese Vektor-quantisierten Wiedergabevektorcodes kombiniert werden und das Ergebnis einer weiteren Vektorquantisierung unterzogen wird.

US 6,377,706, das am 12. Mai 1998 von Ricardo L. de Queiroz eingereicht wurde und dem Begünstigten der vorliegenden Erfindung zugewiesen wurde, offenbart ein Verfahren und eine Vorrichtung zur Codierung und/oder Decodierung, die Decodierbefehle in eine komprimierte Datei einbindet. Die Decodierbefehle sind Instruktionen, die zu einem Dekomprimierer mitgeführt werden und die eine Verarbeitung implementieren, die in dem komprimierten Bereich ausgeführt wird. Dann verarbeitet der Dekomprimierer die Daten, während er sie dekomprimiert. Dies reduziert die Berechnungszeit für Bildoperationen.

US 6,167,153, das am 20. Juli 1998 von Ricardo L. de Queiroz eingereicht wurde und an den Begünstigten der vorliegenden Erfindung zugewiesen wurde, offenbart ein Verfahren und eine Vorrichtung zur Komprimierung von digitalen Bilddaten, um die Effizienz von seriellen Datenübertragungen zu verbessern. Die Erfindung erreicht eine Bildkomprimierung, indem die komplexesten Teile eines Standardkomprimierungsverfahrens auf eine kleinere Menge an Daten als die üblichen 8 × 8 Blöcke von Bilddaten ausgeführt werden. Die Erfindung umfasst einen schnellen JPEG-Komprimierer, der auf einer modifizierten zweidimensionalen diskreten Kosinustransformation basiert.

Die anhängigen US-Patentanmeldungen an de Queiroz et al., die durch die Anwalts-Docket-Nrn. D/98011 und D/98011Q gekennzeichnet sind und die die Titel besitzen "Verfahren und Vorrichtung zur Verwendung von mehrfachen Transformationen um einen Puffer zur erweiterten Bilddatenübertragung zu füllen" und "Vorrichtung zur Verwendung von mehrfachen Transformationen, um einen Puffer für die erweiterte Bilddatenübertragung zu füllen", und die beide an den Begünstigten der vorliegenden Erfindung zugewiesen sind, offenbaren Verfahren und Vorrichtungen zur Komprimierung von digitalen Bilddaten, um die Effizienz von seriellen Datenübertragungen zu verbessern. Im Speziellen verwendet die Erfindung einen Puffer, um verarbeitete Bilddaten zu halten, bis das Modem bereit ist, diese zu übertragen. Die Menge an Bilddaten, die sich in dem Puffer befinden, wird kontinuierlich überprüft und eins von mehreren Bildverarbeitungsmodules wird ausgewählt, um die Daten basierend auf dem Umfang der Daten, die sich in dem Puffer befinden, zu verarbeiten.

EP-A-0 269 746 offenbart eine Datenkommunikationseinrichtung, in welcher Charaktercodedaten und Bilddaten in Blockbereiche geteilt werden. Bilddaten werden weiterhin gemäß den Bildcharakteristiken (z.B. Binär- oder Halbtonbild) geteilt und unterschiedlichen Komprimierungsverarbeitungen abhängig von den Bildcharakteristiken unterzogen. Jeder Block eines Dokuments wird separat eingegeben, und die Charakteristiken werden bestimmt, und die Komprimierung wird im Anschluss an die Eingabe jedes Blockes ausgeführt.

Chadda N. et al.: "Gemeinsame Bildklassifizierung und Komprimierung, indem eine Vector-Quantisierung, basierend auf einer hierarchischen Nachschlagetabelle, verwendet wird", Data Compression Conference, 1996. DCC 1996. Proceedings Snowbird, UT, USA 31. März bis 3. April 1996, Los Alamitos, CA, USA, IEEE Comput. Soc., US, 31. März 1996 (1996-03-31), Seiten 23–32, XP010156543 ISBN 0-8186-7358-3 präsentiert Verfahren zum Entwurf von blockbasierten gemeinsamen Klassifizieren und Quantisieren, Klassifizierer/Kodierer, die durch Nachschlagen in Tabellen implementiert sind. In den Klassifizierern/Kodierern mittels Tabellennachschlagen werden Eingabevektoren an Kodierern direkt als Adressen in Codetabellen verwendet, um Codewörter mit der geeigneten Klassifizierungsinformation zu wählen. Um kontrollierbare Tabellengrößen für großdimensionale Vektorquantisierungen beizubehalten, werden hierarchische Strukturen verwendet, die die Vektoren sukzessive in Stufen quantisieren.

Q: Xie et al.: "Vektorquantisierungstechnik für nicht parametrisierten Klassifiziererentwurf", IEEE Trans. Pattern Analysis and Machine Intelligence, New York, Dezember 1993, Vol. 15, No. 12, Seiten 1326–1330 führt eine effektive Datenreduzierungstechnik basierend auf Vektorquastisierung ein. Zwei neue nicht-parametrisierte Klassifizierer werden entwickelt, und ihre Leistung wird anhand von mehreren Beispielen bewertet.

Dementsprechend, obwohl bekannte Vorrichtungen und Verfahren für ihre vorgesehenen Zwecke brauchbar sind, bleibt ein Bedarf für ein Verfahren und eine Vorrichtung, die effizient digitale Bilddaten verarbeiten können, und die die Effizienz einer seriellen Datenübertragungen verbessern können.

Es ist deshalb die Aufgabe der vorliegenden Erfindung eine weiter verbesserte Übertragungsmethode und Vorrichtung bereitzustellen, die die Geschwindigkeit einer Übertragung von Bildern durch eine weiter optimierte Komprimierung erhöhen können.

Diese Aufgabe wird durch ein Verfahren und eine Vorrichtung gemäß der unabhängigen Ansprüche erreicht. Vorteilhafte Ausführungsformen werden in den abhängigen Ansprüchen beschrieben.

In Übereinstimmung mit einem Aspekt der Erfindung wird ein Verfahren zur Verbesserung der Geschwindigkeit und Effizienz von elektronischer Datenübertragung bereitgestellt, welches die Schritte umfasst vom Erfassen von Eingabebilddaten, welche die Lichtintensität eines Bildes repräsentieren; Segmentieren dieser Eingabebilddaten, um eine Vielzahl an Bilddatenblöcke zu bilden; Auswählen eines Moduls zum Empfang von einem Eingabebilddatenblock, basierend auf einen Bildinhalt; und Verarbeiten des empfangenen Bilddatenblocks in dem Modul.

In Übereinstimmung mit einem anderen Aspekt der Erfindung beinhaltet die Modulauswahl in einem Verfahren zur Verbesserung der Geschwindigkeit und Effizienz elektronischer Datenübertragung das Einholen eines Bilddatenblocks; das Abbilden des Bilddatenblocks auf ein einzelnes Codewort, indem wenigstens eine Nachschlagetabelle verwendet wird; und das Übertragen des Bilddatenblocks an ein Modul, welches durch das einzelne Codewort bestimmt worden ist.

In Übereinstimmung mit noch einem anderen Aspekt der Erfindung wird eine Vorrichtung zur Verbesserung der Geschwindigkeit einer Effizienz elektronischer Datenkomprimierung bereitgestellt, welches einen Segmentierer enthält, der Bilddaten in eine Vielzahl von Eingabebilddatenblöcke teilt, wobei die Bilddaten der Lichtintensität eines Originalbildes entsprechen; eine Vielzahl an Bildverarbeitungsmodulen enthält, die mit dem Segmentierer kommunizieren, wobei jegliches der Module die segmentierten Bilddatenblöcke verarbeiten kann; und einen Bildanalysierer enthält, der mit den Eingabebilddatenblöcken und mit den Modulen kommuniziert, um eines der Module zu bestimmen, um einen segmentierten Bilddatenblock zu verarbeiten, basierend auf einem Inhalt des segmentierten Bilddatenblockes.

In Übereinstimmung mit noch einem anderen Aspekt der Erfindung enthält der Bildanalysierer einer Vorrichtung zur Verbesserung der Geschwindigkeit und Effizienz elektronischer Datenübertragung ein Gerät zum Abbilden von Eingabedaten, das jeden Bilddatenblock auf ein Codewort abbildet, indem eine Nachschlagetabelle verwendet wird; und ein Richtgerät, welches den Bilddatenblock an ein Modul überträgt, das durch das einzelne Codewort bestimmt worden ist.

Die vorliegende Erfindung beschäftigt sich mit einem allgemeinen Problem in digitalen Bildverarbeitungssystemen – Erhalten eines effektiven jedoch kosteneffektiven Wegs, um einen kontinuierlichen Strom an komplexen Bilddaten von einem Sendefaxgerät zu einem Empfangsfaxgerät zu liefern. Ein Weg um dieses Problem zu lösen, schließt die Verwendung von mehreren Kompressoren ein, wobei jeder davon unterschiedliche Datenkomprimierungsraten aufweist, und schließt das Auswählen des geeigneten Komprimierers ein, um Blöcke der Bilddaten basierend auf dem sich darin befindenden Inhalt zu verarbeiten. Im Speziellen, wenn die Aktivität in dem Block gering ist, – es gibt geringe Schwankungen zwischen den Pixelwerten in einem einzelnen Block, werden die Bilddaten durch ein Modul verarbeitet, das Daten mit einer relativ hohen Geschwindigkeit verarbeitet, auch wenn einiges an Bildqualität verloren gehen kann. Wenn die Blockaktivität hoch ist, werden die Daten durch das Modul verarbeitet, das die beste Bildqualität erzeugen wird, wenngleich mit einer geringeren Geschwindigkeit. Während einige Bereiche des Originaldokuments auf einem Level mit geringerer Genauigkeit wiedergegeben werden, wird die insgesamte Qualität des Ausgabefax für die meisten Zwecke genügen.

Andere Merkmale und Vorteile der vorliegenden Erfindung werden offensichtlich werden, während die nachfolgende Beschreibung voranschreitet, und im Hinblick auf die Zeichnungen, in welchen:

1 ein verallgemeinertes Blockdiagramm ist, welches allgemeine Aspekte eines Faxgerätes illustriert, das verwendet werden kann, um die vorliegende Erfindung auszuüben.

2 eine schematische Darstellung der verschiedenen Elemente der vorliegenden Erfindung enthält.

3 eine detaillierte Darstellung einer Alternative des Bildverarbeitungskomprimierers und dessen zugehörigen Schwellwerten enthält.

4 ein Flussdiagramm enthält, welches die Schritte, die ausgeübt werden, gemäß einer Ausführungsform des Entscheidungslogikgerätes der vorliegenden Erfindung, im Detail schildert.

5 eine schematische Darstellung einer herkömmlichen JPEG-Komprimierung enthält, die durch die vorliegende Erfindung ausgeübt werden kann.

6 eine schematische Darstellung einer JPEG-Komprimierungstechnik, die Annäherungswerte verwendet, enthält wie sie durch die vorliegende Erfindung ausgeübt werden kann.

7 eine schematische Darstellung einer anderen JPEG-Komprimierungstechnik, die Annäherungswerte verwendet, enthält wie sie durch die vorliegende Erfindung ausgeübt werden kann.

8 eine schematische Darstellung einer zweiten Alternative enthält.

Die vorliegende Erfindung ist auf ein Verfahren und eine Vorrichtung zur Komprimierung von komplexen, digitalen Bilddaten gerichtet, um die Effizienz einer Datenübertragung zu verbessern. Im Speziellen umfasst die Erfindung mehrere Datenkomprimierer, wobei jeder von diesen mit einer verschiedenen Komprimierungsrate arbeitet. Der Inhalt der Blöcke, in welche das Bild getrennt worden ist, wird kontinuierlich überprüft, und das Modul, das am geeignetsten zur Verarbeitung der Daten sein würde, wird dann basierend auf diesen Inhalt ausgewählt.

In Bezug nun auf die Zeichnungen, in welchen das Gezeigte für den Zweck der Beschreibung einer Ausführungsform der Erfindung ist und nicht um selbige einzuschränken, ist 1 ein Blockdiagramm, das eine Struktur einer Ausführungsform eines Facsimile (Fax)gerätes 10 gemäß der vorliegenden Erfindung zeigt. Faxgerät 10 umfasst eine CPU 12, um Steuerprozesse und Facsimileübertragungssteuerprozeduren auszuführen, einen RAM 14 zur Steuerung von Programmen und eine Anzeigekonsole 16 mit mehreren Knöpfen und/oder Schaltern zur Steuerung des Facsimilegerätes und LCDs oder LEDs zur Überprüfung des Status des Systemvorgangs. Ein Scanner 20 ist auch enthalten, um ein Originalbild 28 zu bekommen und daraus Bilddaten zu erzeugen. Bildverarbeitungseinheit 22 ist enthalten, um Codierungs- und Decodierungs (Komprimierungs- und Dekomprimierungs)prozesse zwischen einem Bildsignal und den übertragenen Codes auszuführen. Während kein spezifischer Ort benötigt wird, wird sich die vorliegende Erfindung typischerweise in der Bildverarbeitungseinheit 22 befinden. Was wichtig für die Zwecke dieser Erfindung ist, ist dass Fax 10 eine Schnittstelle mit einem Modem 24 umfasst oder bildet, welches ein modulierendes und demodulierendes Gerät ist, das Bildinformationen über Telefonleitungen an ein kompatibles Empfangsgerät 26überträgt und empfängt, wie z.B. ein anderes Faxgerät, ein Drucker, Computergerät oder ähnliche Geräte. Wie gezeigt, ist das Scannen mittels Sendefax 10 ein Weg, durch den diese Bilddaten beschafft werden können. Allerdings werden diejenige, die in dem technischen Feld erfahren sind, erkennen, dass andere Wege, wie z.B. Dateierzeugung mittels eines Computers und das Abrufen einer digitalen Datei aus dem Speicher auch zulässig sind.

Das gescannte Bild wird in Bilddaten konvertiert, die die Intensität des Lichtes im ganzen Originalbild angeben. In der bevorzugten Ausführungsform werden diese Bilddaten digitale Daten sein, die als Bildelemente, gewöhnlicherweise als "Pixel" 120 (gezeigt in 2) bekannt, die die Intensität von Licht an diskreten Orten in dem Bild darstellen. Zum Beispiel wird ein Fleck, der mit schwarzer Tinte bedeckt ist, keinerlei Licht reflektieren. Der Wert des Pixels 120 wird an dieser Stelle typischerweise ein minimaler Wert (i.e. 0) sein. Auf der anderen Seite wird ein Fleck, der komplett unbedeckt von Tinte ist, die Farbe der Seite, auf welcher das Bild sich befindet, reflektieren. Wenn man annimmt, dass das Blatt Papier, auf welchem das Bild platziert worden ist, weiß ist, würde die gemessene Lichtintensität des Pixels 120 maximiert sein an diesem Ort. Ein Bereich der Pixelintensitätswerte zwischen 0 und 255 bedeutet, dass 8 Bits verwendet werden, um jedes Pixel zu beschreiben. Systeme, wie diese, sind im technischen Feld allgemein bekannt. Deshalb ist der maximale Pixelintensitätswert häufig 255. Graue Bereiche, wie z.B. solche, die Farbe oder schwarzweiß Halbtonbereiche des Bildes repräsentieren, würden eine Lichtintensität irgendwo zwischen 0 und 1 verzeichnen.

In Bezug nun auf 2 werden Bilddaten, welche das gesamte gewonnene Bild beschreiben, in Bilddatenblöcke 102 segmentiert. JPEG, welches Bilddatenblöcke 102 in der Form von 8 × 8 Pixelmatritzen bereitstellt, hat sich als sehr erfolgreich gezeigt, bei Verwendung mit der vorliegenden Erfindung, aber die Erfindung kann auch mit anderen Komprimierungsverfahren ausgeführt werden und mit Verwendung von Bilddatenblöcken 102, die andere Dimensionen haben. Jene, die in dem technischen Feld bewandert sind, werden erkennen, dass eine kleinere oder größere Blockgröße ausgewählt werden kann, wenn gewünscht wird, dass mehr oder weniger Bilddetails erhalten werden sollen. Tatsächlich sollte beachtet werden, dass während die horizontalen und vertikalen Dimensionen in dieser Ausführungsform des hier beschriebenen Bilddatenblocks 102 identisch sind, dies nicht eine Bedingung zur Ausführung der vorliegenden Erfindung ist. Zum Beispiel kann man einen nicht quadratischen Block auswählen, wenn das Bild für ein Gerät erzeugt worden ist, das asymmetrische Auflösungen in den vertikalen und horizontalen Richtungen aufweist.

Die vorliegende Erfindung erlaubt es dem Sendefax 10 oder ähnlichen Geräten die Übertragungsgeschwindigkeit des dazugehörigen Modems beizubehalten, indem die Bilddaten auf unterschiedlichen Geschwindigkeiten komprimiert werden, während der Inhalt der Bilddaten zwischen den Bilddatenblöcken 102 variiert.

Weiterhin in Bezug auf 2 umfasst die Erfindung auch mehrere Bildverarbeitungsmodule M1–M4. Während die Erfindung hier in Bezug auf vier Bildverarbeitungsmodule beschrieben wird, werden jene, die in dem technischen Feld bewandert sind, erkennen, dass während wenigstens zwei Module benötigt werden, weniger oder mehr als vier Module verwendet werden können, abhängig davon, wie breit eine Variation der Bildwiedergabegenauigkeit gewünscht wird, und dass die Erfindung nicht auf die Verwendung von vier Modulen beschränkt ist. Module M1–M4 werden typischerweise Komprimierer sein, wobei jeder von diesen die Daten auf einem unterschiedlichen Level von Genauigkeit verarbeitet, wobei dabei verursacht wird, dass sie mit unterschiedlichen Geschwindigkeiten arbeiten. Zum Beispiel, wenn man annimmt, dass M1 die höchste Qualitätsausgabe erzeugt, gefolgt von M2, dann M3, und dass M4 den größten Datenverlust besitzt, wird M1 mit der geringsten Geschwindigkeit arbeiten, gefolgt wieder von M2, dann M3 und M4 wird das schnellste sein. Es sollte beachtet werden, dass während alle diese Module fähig sind, die Bilddaten zu verarbeiten, muss wenigstens das schnellste Modul diese mit einer Rate verarbeiten, die schneller ist, als die Modemgeschwindigkeit um Unterbrechungen zu vermeiden.

Mit fortgesetztem Bezug auf 2 umfasst die vorliegende Erfindung ebenfalls einen Bildanalysierer 104, der den Inhalt von jedem Bilddatenblock 102 überprüft und das geeignetste Modul zur Verarbeitung auswählt. Daten werden dann durch das ausgewählte Modul verarbeitet und durch Modem 24 an Empfangsfaxgerät 26 gesendet. Im Speziellen bestimmt Bildanalysierer 104 erst, ob die Aktivität innerhalb des Blockes – die Menge an Änderungen zwischen der Lichtintensität der darin enthaltenen Pixel – hoch oder niedrig ist, indem jeder Block auf das Codewort abgebildet wird, das mit den Bilddaten verknüpft ist, welche die genaueste Übereinstimmung liefern. Eine hohe Blockaktivität bedeutet, dass Bildblock 102 bildhafte, mehrfarbige oder andere komplexe Daten enthält, und dass es durch ein Hochqualitätserzeugungsmodul, wie beispielsweise M1 oder M2, wiedergegeben werden sollte. Für diese Art von Daten würde eine Verarbeitung, die durch einen Prozessor mit einer niedrigen Qualitätsausgabe ausgeführt wird, wahrscheinlich eine schwer negative Auswirkung auf die sichtbare Erscheinung des Dokuments haben. Wenn die Blockaktivität gering ist, ist es am wahrscheinlichsten, dass das Dokument Text, freie Bereiche oder Bereiche enthält, die durch eine einzelne Farbe bedeckt sind. Wenn man diese Art von Daten wiedergibt, indem ein Prozessor verwendet wird, der eine geringere Qualitätsausgabe erzeugen kann, ist es nicht wahrscheinlich, dass die sichtbare Erscheinung des Dokuments verringert wird, wenn man dieses nur mit dem menschlichen Auge betrachtet.

Vektorquantisierung ist eine Bildverarbeitungstechnik, in welcher K Symbole, die jeweils N-Bits haben, einem einzelnen Codewort mit B-Bits zugewiesen werden, wobei B < NK. Zum Beispiel könnten sechzehn acht Bit-Eingabefolgen zu einem zwölf Bit-Codewort zugewiesen werden. Deshalb werden in diesem Beispiel genügend Codewörter vorhanden sein, um nur die 4096 (212) repräsentativsten Blöcke der sechzehn Eingabesymbole darzustellen. Codewörter, die durch Vektorcodierung erzeugt werden, werden gewöhnlich gespeichert, oder an einen anderen Ort oder Gerät übertragen, und werden später zu K-Symbolen decodiert – zurück abgebildet.

In der vorliegenden Erfindung werden mehrere Bilddatenblöcke 102 auf ein einzelnes Codewort abgebildet, welches eine Annäherung der Bilddaten ist, die ursprünglich in Eingabedatenblock 102 enthalten waren. Codewörter wurden in einem Codebuch in den Speicher-, Übertragungs-, oder Empfangsgeräten gespeichert, und jedes Codewort wird mit einem Satz von vorherbestimmten Ausgabebilddaten verknüpft. Deshalb sind die Codewörter, auf welche die Eingabedatenblöcke 102 abgebildet werden, diejenigen, die mit den Daten verknüpft sind, die am nähesten zu denen sind, die in den Eingabedatenblöcken 102 enthalten sind, gemäß irgendeiner angemessenen Distanzmaßeinheit. Diese Abbildung zeigt auch kontinuierlich den Grad der Aktivität innerhalb jeden Blockes an.

Codewörter, Codebücher und der gesamte Abbildungsprozess werden vor der Ausführung der vorliegenden Erfindung vorbereitet. Deshalb sind die einzigen Berechnungen, die während der Operation benötigt werden dazu da, um Eingabedatenblöcke 102 mit dem Codebuch zu vergleichen und das entsprechende Codewort auszusuchen. Es wird auch ein Hinweis darauf, welches Modul ausgewählt werden soll, um die Bilddaten zu verarbeiten, die mit diesen verknüpft sind, an jedes Codewort angehängt. Zum Beispiel werden Codewörter, auf die bildhafte Bilddatenblöcke mit hoher Aktivität abgebildet werden, Daten enthalten, die angeben, dass Modul M1 ausgewählt werden soll, um diesen Block zu verarbeiten. Wenn einfacher, einfarbiger Text analysiert wird, wird das ausgewählte Codewort angeben, dass Modul M4 ausgewählt werden soll. Deshalb wird jedes Codebuch mit allen benötigten Informationen und Bestimmungen vorgespeichert.

Beim Zuwenden zu 3 für eine allgemeine Beschreibung der hierarchischen Vektorquantisierung (HVQ), werden mehrere N-Bit-Symbole auf ein einzelnes B-Bit-Codewort abgebildet, indem eine Folge von Nachschlagetabellen (im Englischen: Look Up Tables) (LUTs) verwendet werden. Wie in der Darstellung gezeigt, werden zwei N-Bit-Symbole auf ein einzelnes Ausgabecodewort 206 auf der ersten Ebene abgebildet, indem LUT 204 verwendet wird, welche 22N Einträge besitzt. Wie gezeigt, wird die Gesamtzahl von Eingaben in jedem Level um einen Faktor von zwei reduziert. Wie vorher dargelegt, wird der Prozess wiederholt, bis nur eine Ausgabe übrigbleibt, vorzugsweise, indem Codewörter in einer Richtung gruppiert werden, die senkrecht zu der ist, die für die vorhergehende Ebene verwendet wurde, wie in 4 gezeigt. Die Wiederholung des Prozesses führt zu einer Abbildung von immer größer werdenden Datenblöcken auf ein einzelnes Codewort.

5 enthält ein Flussdiagramm, das die Vorgangseinzelheiten von Bildanalysierer 104 zeigt. Mit Schritt 402 beginnend, wird Eingabebilddatenblock 102 in den Bildanalysierer 104 eingegeben, welcher in der bevorzugten Ausführungsform der Erfindung ein System basierend auf HVQ ist. Jedes Paar von N-Bit-Eingaben 202 wird auf ein einzelnes Codewort 206 abgebildet, indem eine Nachschlagetabelle 204, wie in Schritt 404 gezeigt, verwendet wird.

Das Gruppieren von N-Bit-Eingaben 202 in Paaren und das Ausgeben eines einzelnen Codeworts 206 daraus, wird bevorzugt, aber die Verwendung dieser Konfiguration wird nicht benötigt, um die Erfindung auszuführen. Zum Beispiel, wenn die Form des Eingabeblockes oder die ausgewählte Anzahl von Bits andeuten, dass das Gruppieren von drei oder mehr N-Bit-Eingaben 202 wünschenswert wäre, kann die Erfindung angepasst werden, um diese Bedingung aufzunehmen. Im Weiteren, wenn das Ausgeben von mehreren Codewörtern 206, wenn mehr als zwei Eingaben 202 gruppiert worden sind, auf irgendeiner Weise vorteilhaft ist, kann die Erfindung angepasst werden, um diese Aufgabe ebenfalls auszuführen. Was benötigt wird, um alle Vorteile der vorliegenden Erfindung auszuschöpfen, ist, dass die Anzahl von Eingaben 202 die Anzahl von Codewörter 206 übertrifft. Deshalb, obwohl das Abbilden von fünf N-Bit-Eingaben 202 auf drei N-Bit-Codewörter 206 wünschenswert wäre, würde die Abbildung von drei N-Bit-Eingaben 202auf fünf N-Bit-Codewörter 206 üblicherweise nicht die beste Vorgehensweise sein. Wenn wir uns einen Moment auf 3 beziehen, annehmend, dass mehr als ein Codewort 206 durch die Unterteilung des Bilddatenblocks 102 während der Anfangsstufe erzeugt worden ist, müssen die Codewörter, die in dieser ersten Stufe erzeugt wurden, in Paare gruppiert werden, und eine zweite LUT 208 muss verwendet werden, um jedes Paar der resultierenden Codewörter 206 auf ein Codewort 210 der zweiten Stufe abzubilden. Diese zweite Abbildung reduziert die Anzahl von Codewörtern 210 um einen Faktor von zwei gegenüber der Anzahl von Codewörtern 206 der vorherigen Stufe. Das Abbilden von Paaren der Codewörter auf ein einzelnes Codewort im nächsten Level fährt in hierarchischer Art und Weise fort, bis alle N-Bit-Eingaben, die den Bilddatenblock 102 ausmachen, auf ein einzelnes Codewort im letzten Level abgebildet werden können. Das heißt, die LUT-Stufen müssen weiterhin hierarchisch auf jedes Paar von Ausgabecodewörtern der vorherigen Stufe angewendet werden, bis ein einzelnes Ausgabecodewort 212 erzeugt wird. Im Rückbezug auf 5 wird dies durch die Schleife zwischen den Schritten 404, 406 und 408 gezeigt. Es sollte beachtet werden, dass eine unterschiedliche LUT für das Abbilden in jedem HVQ-Level benutzt wird. Die LUTs auf allen Ebenen über dem Ersten wurden so gestaltet, dass die Eingaben Codewörter sind, anstatt von Bilddaten. Die Ausgabe von diesen LUTs der höheren Level sind Codewörter, welche die Eingabecodewörter repräsentieren. Sobald die Anzahl von Ausgabecodewörtern auf Eins reduziert worden ist, wird das endgültige Codewort 202 verwendet, um eine Näherung eines gesamten Bilddatenblocks 102 darzustellen.

Jedes Codewort kann mit einem Satz von vordefinierten Bilddaten assoziiert werden, und das Codewort gibt auch die Art und Weise an, auf welche diese vordefinierten Bilddaten verarbeitet werden sollten. Das Abbilden der Eingabeblöcke 202 auf Codewörter 206 wird ausgeführt, indem LUT 204 verwendet wird, um den Satz von vordefinierten Bilddaten auszuwählen, dessen Inhalt am ähnlichsten ist zu den Eingabemustern 202, die gerade verarbeitet werden. Auf ähnliche Weise wird das Abbilden der Ausgabecodewörter auf Codewörter einer höheren Ebene ausgeführt, indem LUTs 208 und 212 verwendet werden, um die Sätze von vordefinierten Bilddaten auszuwählen, die am ähnlichsten erscheinen gemäß irgendeines vordefinierten Abstandsmaßstabes. Die sichtbare Übereinstimmung, wenn mit menschlichem Auge betrachtet, und irgendeine Form von statistischer Analyse der Daten, die in dem Block enthalten sind, sind zwei sinnvolle Messkriterien, aber andere sind möglich, und die Erfindung ist nicht auf diese Ausführungsform beschränkt. Sobald der Satz von vordefinierten Bilddaten, der am nähesten ist, gefunden worden ist, werden die Bildverarbeitungsinstruktionen, die mit diesen Daten verknüpft sind, verwendet, um das Modul auszuwählen, welches den Bilddatenblock 102 empfangen wird. Mit anderen Worten, der Bilddatenblock 102 wird zu dem Modul übertragen, der ihn gemäß den Instruktionen verarbeiten wird, die durch die vordefinierten Bilddaten geliefert werden, die am passendsten zu diesen sind. Nach einigen Stufen von HVQ-bezogenen LUT-Arbeitsschritten ist deshalb die Ausgabe eine Zahl, die das Modul angibt, welches verwendet werden sollte, um den Bilddatenblock zu komprimieren, und um dabei das gewünschte Kompressionsverfahren zu bestimmen. Wenn die vorherbestimmte Näherung Hochfrequenzinformationen und Details enthält, werden die Bildverarbeitungsinstruktionen das Modul mit der höchsten Qualität auswählen. Wenn die Näherung einen Block ohne große Details beschreibt, kann ein Modul geringerer Qualität ausgewählt werden.

Nun in Bezug auf 6, wird eine Standard-JPEG-Komprimierung auf die Bilddatenblöcke 102 durch ein Modul (hier beschrieben als M1) angewendet, und Ausgabedaten erzeugt, die die höchste Bildqualität besitzen. Deshalb wird, sobald das digitale Bild in 8 × 8 Bilddatenblöcke 102 unterteilt worden ist, Bilddatenblock 102 in einen Satz 506 von 8 × 8 Koeffizienten transformiert, in dem die diskrete Kosinustransformation (DCT) verwendet wird, wie in Schritt 504 gezeigt. Der DCT-Koeffizient mit der geringsten Frequenz wird als DC-Koeffizient (DCC) bezeichnet, und die übrigen Koeffizienten sind AC-Koeffizienten (ACCs). Die DCC und ACCs werden quantisiert – jeder Koeffizient wird durch einen vorbestimmten Wert, der als die "Schrittweite" bezeichnet wird, geteilt und auf eine ganze Zahl bei Schritt 508 gerundet, und dann folgt man einem ausgewählten Raster (üblicherweise einem "Zigzag") durch den 8 × 8 Block vom quantisierten Koeffizienten 510, wie in Schritt 512 angedeutet, um die Koeffizienten in einer gewünschten Reihenfolge in einem eindimensionalen Vektor 514 anzuordnen. Der quantisierte DCC ist typischerweise der erste Wert des Vektors 514, und wird unterschiedlicherweise als der aktuelle DCC-Wert minus dem DCC des vorherigen Blocks dargestellt.

Eine gewöhnliche JPEG-Komprimierung wird vervollständigt mit der nachfolgenden Codierung des Vektors 514 in eine Bitdatenkette, durch eine Sequenz von Weglängenzähler (im Englischen: Run Length Counting, RLC)-Operationen, die die Anzahl von Null ACCs zählen, die sich in dem Pfad vor einem nicht-Null-ACC befinden. Diese RLC-Operationen werden mit variablen Längencodes (im Englischen: Variable Length Codes, VLC) kombiniert, welche ein Symbol codieren, das eine Kombination der Anzahl von Nullen, die einem nicht-Null-ACC vorangehen, und der ACC-Amplitude enthält. Dieses Codieren erzeugt einen komprimierten Datenstrom, der an den Multiplexer 122 oder einem anderen Gerät gesendet wird, der eine Ausgabe aus mehreren Eingaben auswählen wird, und sendet die Daten über Kommunikationswege an ein Empfangs-Faxgerät oder ein anderes Gerät 26.

In einer anderen Alternative der Erfindung, wird Modul M4, welches die geringste Qualitätsausgabe erzeugen wird, nur den ersten Schritt der JPG-Komprimierung ausführen. Das heißt, der Bilddatenblock 102 wird der DCT unterzogen. Danach wird nur der DCC quantisiert, und dieser Wert wird an den Puffer 114 gesendet. Es sei anzumerken, dass während diese Bilddaten die geringste Bildqualität haben werden, diese mit der schnellsten Geschwindigkeit produziert werden.

Gemäß der Erfindung wird wenigstens eines der übrigbleibenden Module, hier als M2 oder M3 dargestellt, eine JPEG-Komprimierung mit "reduzierten" Datensätzen ausführen – Daten, die in ihrer Größe von den original-bereitgestellten 8 × 8 Blöcken reduziert worden sind. Allgemein gesprochen, erzeugen vorteilhafterweise sowohl M2 als auch M3 Annäherungsdaten, welche abgeschätzte Werte der Pixel im Bilddatenblock 102 liefern. Als nächstes werden Ausgabebilddaten aus den Annäherungsdaten abgeleitet, und die abgeleiteten Ausgabebilddaten in dem Puffer 114 für die anschließende Übertragung via Modem 24 gespeichert. Da die Ausgabedaten aus den Näherungsdaten abgeleitet werden, erzeugen diese Module Ausgabedaten, die weniger genau – geringere Qualität – als diese sind, die durch Modul M1 produziert werden. Das Erzeugen der Näherungsdaten erfordert die Unterteilung des Bilddatenblocks in eine Vielzahl von Bilddatenunterblöcken und erfordert das Darstellen jedes Bilddatenunterblocks als einen einzelnen Wert in einem Annäherungsdatenblock. Das Ableiten der Ausgabebilddaten aus diesen erzeugten Daten wird ausgeführt, indem eine Standard-JPEG auf den Satz von Näherungsdaten angewendet wird.

Bezüglich 7 für eine detaillierte Beschreibung von M2, wird Bilddatenblock 102 in Unterblöcke 610 unterteilt. Hier, wo ein 8 × 8 Bilddatenblock 102 geliefert worden ist, beinhaltet die bevorzugte Ausführungsform der Erfindung die Unterteilung des Bilddatenblocks 102 in 4 × 4 Unterblöcke 610, wobei jeder 4 Pixel 120 besitzt, die in einem 2 × 2 Muster angeordnet sind. Annäherungswerte für jeden Unterblock werden dann erzeugt, indem jeder Unterblock 610 durch einen einzelnen Wert in einem Näherungsdatenblock 602 dargestellt wird. Jene, die im technischen Feld bewandert sind, werden erkennen, dass diese Einzelwertannäherungen auf viele Arten erhalten werden können, wie z.B. durch die Mittelwertbildung oder Addition der vier Pixel 120 in dem Unterblock, oder indem das Minimum, Maximum, der Median oder ein anderer bestimmter Wert verwendet wird. Der Rest der Bildverarbeitung durch M2 wird ausgeführt, indem eine gewöhnliche JPEG-Komprimierung verwendet wird. Das heißt, Näherungsdatenblock 602 wird bei 604 in einen Block von Koeffizienten 606 transformiert, indem die DCT verwendet wird. Der Koeffizientenblock 606 wird dann bei 108 quanitisiert, und der quantisierte Koeffizientenblock 610 wird in einem eindimensionalen Vektor 514 angeordnet, welcher in einen Bitstrom codiert wird und an den Multiplexer 122 oder einen ähnlichen einzelnen Ausgabeauswahlgerät zur Übertragung an ein Empfangsfaxgerät oder ein anderes Gerät 26 gesendet wird.

In Bezug nun auf 8 arbeitet M3 sehr ähnlich zu M2 mit dem Unterschied im Ausmaß der Annäherung, die stattfindet und deshalb im Grad an Reduktion in der Ausgabebildqualität. Wie gezeigt, wird Bilddatenblock 102 wiederum in Unterblöcke 710 unterteilt, aber hier wird der 8 × 8 Bilddatenblock 102 in 2 × 2 Unterblöcke 710 unterteilt, wobei jeder 16 Pixel 120 besitzt, die in einem 4 × 4 Muster angeordnet sind. Diese Annäherung liefert eine weniger genaue Bildwiedergabe als das Modul M1, das oberhalb mit Bezug auf 6 beschrieben worden ist, da ein größerer Datenverlust auftreten kann. Auf der anderen Seite findet die Verarbeitung mit einer erhöhten Bearbeitungsgeschwindigkeit statt. Wie vorher angedeutet, wird die Bildverarbeitung durch Modul M3 auf einen höheren Bildqualitätslevel sein als M4, aber die Verarbeitung wird länger dauern. Annäherungswerte für jeden Unterblock werden erzeugt, indem jeder Unterblock 710 durch einen einzelnen Wert in einem Annäherungsdatenblock 602 dargestellt wird. Annäherungsdatenblock 702 wird bei 704 in einen Block von Koeffizienten 706 verwandelt, indem die DCT verwendet wird. Der Koeffizientenblock 706 wird dann bei 108 quantisiert, und der quantisierte Koeffizientenblock 710 wird in einem eindimensionalen Vektor 514 angeordnet, welcher in eine Bitdatenkette kodiert wird und an den Multiplexer 122 zur Übertragung an ein Empfangsfaxgerät 26 gesendet wird.

Wie vorher erläutert, ist ein Vorteil der vorliegenden Erfindung die Fähigkeit, die Größe und Form der Blöcke und Unterblöcke an den Bedarf des Benutzers anzupassen. Deshalb können Bilddatenblöcke 102 für die Übertragung an Modul M1 oder möglicherweise an Modul M2 fixiert werden, wenn bekannt ist, dass das gesamte zu übertragende Bild viele genaue Details hat und zu viele Daten durch die Annäherung verlorengehen würden. Auf der anderen Seite könnten Bilddatenblöcke 102 für die Übertragung an Modul M3 oder M4 fixiert werden, wenn das Originalbild nur Text auf einen einfarbigen Papierhintergrund beinhaltet. Hier sollte wieder angemerkt werden, dass die Verarbeitung durch Modul M4, welche die niedrigste Bildqualitätsausgabe erzeugt, nicht unbedingt unerwünscht ist. Tatsächlich sollte dieses Modul stark benutzt werden, wenn das Originalbild gleichmäßige Bilddaten oder leere konstante Bereiche enthält, da weniger Bits übertragen werden, wenn das Bild verarbeitet worden ist. Mit anderen Worten, die Bildqualität wird nicht verlorengehen, da es weniger zu verarbeitende Bilddaten gibt, und die Annäherungen, die in Modul M4 auftreten, ziemlich genaue Ergebnisse erzeugen werden.

Es ist deshalb offensichtlich, dass gemäß der vorliegenden Erfindung ein Verfahren und eine Vorrichtung bereitgestellt worden ist, zur Analyse von Bilddaten, um mehrere Transformationen effizient zu nutzen und eine Bilddatenübertragung zu verbessern, die die Ziele und Vorteile, die oben erwähnt worden sind, erfüllt.

Um die Geschwindigkeit und Effizienz einer elektronischen Datenübertragung zu verbessern, umfasst der Verarbeitungsschritt das Erzeugen von Annäherungsdaten, welche einen abgeschätzten Wert für diese Lichtintensität in diesem Bilddatenblock liefern, und umfasst das Ableiten von Ausgabebilddaten aus diesen Annäherungsdaten. Dieser Erzeugungsschritt von Näherungsdaten umfasst vorteilhafterweise weiterhin das Unterteilen dieses Bilddatenblocks in eine Vielzahl von Bilddatenunterblöcken, und umfasst das Darstellen jedes Bilddatenunterblocks als einen einzelnen Wert in einen Annäherungsdatenblock.

Weiterhin umfasst der Ableitungsschritt von Ausgabebilddaten eines Verfahrens zur Verbesserung der Geschwindigkeit und Effizienz einer elektronischen Datenübertragung vorteilhafterweise das Umwandeln dieser Annäherungsdaten in einen Block von Koeffizienten, umfasst weiterhin das Quantisieren dieses Koeffizientenblocks, das Anordnen dieses quantisierten Koeffizientenblocks in einen eindimensionalen Vektor und das Codieren dieses eindimensionalen Vektors in einen Bitdatenstrom, wodurch besagte Ausgabebilddaten erzeugt werden.

Um die Geschwindigkeit und Effizienz einer elektronischen Datenübertragung zu verbessern, umfasst der Unterteilungsschritt das Teilen dieses Bilddatenblocks in sechzehn Bilddatenunterblöcke, wobei vier Unterblöcke sich in einer horizontalen Richtung ausstrecken und vier Unterblöcke sich in einer vertikalen Richtung ausstrecken. Dieser Unterteilungsschritt umfasst vorteilhafterweise weiterhin das Teilen dieses Bilddatenblocks in vier Bilddatenunterblöcke, wobei zwei Unterblöcke sich in einer horizontalen Richtung erstrecken, und zwei Unterblöcke sich in einer vertikalen Richtung erstrecken.

In einer Vorrichtung zur Verbesserung der Geschwindigkeit und Effizienz einer elektronischen Datenübertragung, umfasst weiterhin wenigstens eines von diesen Modulen einen Näherungsdatenerzeuger, welcher einen abgeschätzten Wert dieser Lichtintensität in diesen Bilddatenblock liefert, und einen Ausgabebilddatenerzeuger, welcher aus diesen Annäherungsdaten Ausgabebilddaten ableitet. Dieser Näherungsdatenerzeuger umfasst vorteilhafterweise weiterhin einen Unterteiler, welcher den besagten Bilddatenblock in eine Vielzahl von Bilddatenunterblöcke teilt, und einen Vereinfacher, der jeden Bilddatenunterblock als einen Annäherungswert in einem Annäherungsdatenblock darstellt.

Dieser Ausgabebilddatenerzeuger einer Vorrichtung zur Verbesserung der Geschwindigkeit und Effizienz einer elektronischen Datenübertragung umfasst vorteilhafterweise weiterhin Mittel zur Umwandlung dieser Annäherungsdaten in einen Block von Koeffizienten, Mittel zur Quantisierung dieses Koeffizientenblocks, Mittel zur Anordnung dieses quantisierten Koeffizientenblocks in einem eindimensionalen Vektor und Mittel zur Codierung dieses eindimensionalen Vektors in eine Bitdatenkette, wodurch diese Ausgabebilddaten erzeugt werden.

Weiterhin umfasst dieser Unterteiler einer Vorrichtung zur Verbesserung der Geschwindigkeit und Effizienz einer elektronischen Datenübertragung vorteilhafterweise Mittel zur Teilung dieses Bilddatenblocks in sechzehn Bilddatenunterblöcke, wobei vier Unterblöcke sich in einer horizontalen Richtung erstrecken, und vier Unterblöcke sich in einer vertikalen Richtung erstrecken.

In einer Vorrichtung zur Verbesserung der Geschwindigkeit und Effizienz einer elektronischen Datenübertragung umfasst dieser Unterteiler weiterhin Mittel zur Teilung dieses Bilddatenblocks in vier Bilddatenunterblöcke, wobei zwei Unterblöcke sich in einer horizontalen Richtung erstrecken, und zwei Unterblöcke sich in einer vertikalen Richtung erstrecken.


Anspruch[de]
Ein Verfahren zur Verbesserung der Geschwindigkeit und Effizienz von einer elektronischen Datenübertragung, umfassend der Schritte von:

a) Erfassen von Eingabebilddaten (120), die die Lichtintensität eines Bildes repräsentieren;

b) Segmentieren von diesen Eingabebilddaten um eine Vielzahl an Bilddatenblöcke (102) zu bilden;

c) Analysieren (104) von wenigstens einen von diesen Bilddatenblöcken um seinen Bilddateninhalt zu bestimmen;

d) Bereitstellen einer einzelnen Stufe von mehreren Bildverarbeitungsmodulen (M1–M4), wobei jedes Bildverarbeitungsmodul Bilddaten auf einem unterschiedlichem Bildqualitätslevel verarbeitet;

e) Auswählen eines einzelnen Bildverarbeitungmoduls unter der Vielzahl von Bildverarbeitungsmodulen zum Empfang des Bilddatenblocks;

f) Übertragen von diesem Bilddatenblock zu dem ausgewählten Bildverarbeitungsmodul; und

g) Verarbeiten von diesem empfangenen Bilddatenblock in diesem ausgewähltem Bildverarbeitungsmodul;

gekennzeichnet dadurch, dass

wenigstens ein Modul von diesen vielen Bildverarbeitungsmodulen Näherungsdaten für den Bilddatenblock vor dem Ausführen von weiterer Verarbeitung erzeugt; dieser Analyseschritt c) weiterhin die Schritte umfasst von:

1. Unterteilen dieses Eingabedatenblocks in eine Vielzahl von Mustern (202); 2. Gruppieren dieser Muster in Paare, und Repräsentieren von jedem Musterpaar durch ein Codewort, indem eine Nachschlagetabelle (204) verwendet wird; und

3. Verknüpfen von jedem Paar dieser Codewörter mit einem Codewort der nächsten Ebene auf hierarchische Art und Weise, indem eine Nachschlagtabelle (208, 212) auf jeder Ebene verwendet wird, bis dieser Bilddatenblock durch ein einzelnes Codewort repräsentiert wird;

dieser Auswahlschritt e) auf diesem einzelnen Codewort basiert, der in Schritt c) erhalten wurde; und

wenn dieser Auswahlschritt e) dieses wenigstens eine Modul ausgewählt hat, dieser Verarbeitungsschritt g) weiterhin die Schritte umfasst von:

1. Aufteilen dieses Bilddatenblocks in eine Vielzahl von Unterblöcken (610);

2. Erzeugen von Näherungsdaten (602) für jeden dieser Unterblöcke, welche einen abgeschätzten Wert für diese Lichtintensität in diesem Unterblock bereitstellen;

3. Umwandeln von diesen Näherungsdaten in einen Block von Koeffizienten (606);

4. Quantisierung (108) dieses Koeffizientenblocks;

5. Anordnen (512) dieses quantisierten Koeffizientenblockes in einen eindimensionalen Vektor; und

6. Kodieren dieses eindimensionalen Vektors in eine Bitdatenkette, wobei dabei ein verarbeiteter Bilddatenblock erzeugt wird.
Das Verfahren wie in Anspruch 1 beansprucht, wobei dieser Aufteilungsschritt weiterhin die Teilung dieses Bilddatenblocks in 16 Unterblöcke umfasst, wobei vier Unterblöcke sich in eine horizontale Richtung erstrecken und vier Unterblöcke sich in eine vertikale Richtung erstrecken. Das Verfahren wie in Anspruch 1 beansprucht, wobei dieser Aufteilungsschritt weiterhin die Teilung dieses Bildatenblocks in vier Unterblöcke umfasst, wobei zwei Unterblöcke sich in horizontaler Richtung erstrecken und zwei Unterblöcke sich in vertikaler Richtung erstrecken. Eine Vorrichtung zur Verbesserung der Geschwindigkeit und Effizienz einer elektronischen Datenübertragung, umfassend:

a) einen Segmentierer, der Bilddaten in eine Vielzahl von Eingabebilddatenblöcke teilt, wobei diese Bilddaten (120) der Lichtintensität eines Originalbildes entsprechen;

b) eine einzelne Stufe von mehreren Bildverarbeitungsmodulen (M1 – M4), wobei jedes Bildverarbeitungsmodul Bilddaten auf einem unterschiedlichem Bildqualitätslevel verarbeitet, die Vielzahl von Bildverarbeitungsmodulen mit dem Segmentierer kommunizieren, wobei jegliche dieser Bildverarbeitungsmodule eines von diesen segmentierten Bilddatenblöcken verarbeiten kann;

c) einen Bildanalysierer (104), der mit diesem Segmentierer und mit diesen mehreren Bildverarbeitungsmodulen kommuniziert um eines von diesen Bildverarbeitungsmodulen für die Verarbeitung eines segmentierten Bilddatenblocks zu bestimmen, basierend auf einem Inhalt von diesem segmentierten Bilddatenblock;

gekennzeichnet dadurch, dass

wenigstens eines von diesen Modulen weiterhin umfasst:

1. Einen Näherungsdatenerzeuger (104) umfassend

a) einem Aufteiler, der diesen Bilddatenblock in eine Vielzahl von Unterblöcken (610) teilt, und

b) einem Vereinfacher, der jeden Unterblock als einen Näherungswert repräsentiert;

2. einen Umwandler (504), der diesen abgeschätzten Wert in einen Block von Koeffizienten (506) umwandelt;

3. einen Quantisierer (508), der jeden Koeffizienten in diesem Koeffizientenblock durch einen vorher bestimmten Wert teilt und einen entstehenden Wert auf eine ganze Zahl rundet;

4. eine Ablaufsteuerung (512), die diese Koeffizienten in diesen quantisierten Koeffizientenblock in einen eindimensionalen Vektor (514) platziert;

5. einen Kodierer, der diesen eindimensionalen Vektor in eine Bitdatenkette umwandelt, und

dieser Bildanalysierer weiterhin umfasst:

1. Einen Segmentierer, der diesen Eingabedatenblock in eine Vielzahl von Muster (202) teilt;

2. einen Verbinder, der diese Muster in Paare gruppiert und jedes Musterpaar durch ein Codewort repräsentiert, indem eine Nachschlagetabelle verwendet wird;

3. eine Codewortabbildungseinrichtung (208, 212), die Paare dieser Codewörter mit einem Codewort der nächsten Ebene auf hierarchische Art und Weise verknüpft, indem eine Nachschlagetabelle auf jeder Ebene verwendet wird, bis dieser Bilddatenblock durch ein einzelnes Codewort repräsentiert wird; und

4. ein Richtgerät um den segmentierten Bilddatenblock zu einem einzelnen Bildverarbeitungsmodul zu übertragen, der durch dieses einzelne Codewort unter der Vielzahl von Bildverarbeitungsmodulen zur Verarbeitung des segmentierten Bilddatenblocks bestimmt wird.
Die Vorrichtung wie in Anspruch 4 beansprucht, wobei dieser Segmentierer weiterhin Mittel zur Teilung dieses Bilddatenblocks in 16 Unterblöcke umfasst, wobei vier Unterblöcke sich in horizontaler Richtung erstrecken und vier Unterblöcke sich in vertikaler Richtung erstrecken. Die Vorrichtung wie in Anspruch 4 beansprucht, wobei dieser Segmentierer weiterhin Mittel zur Teilung dieses Bilddatenblocks in vier Unterblöcken umfasst, wobei zwei Unterblöcke sich in horizontaler Richtung erstrecken und zwei Unterblöcke sich in vertikaler Richtung erstrecken. bei zwei Unterblöcke sich in horizontaler Richtung erstrecken und zwei Unterblöcke sich in vertikaler Richtung erstrecken.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com