DE69712572T2 - Fehlerdiffusionsverfahren mit symmetrischer Verbesserung - Google Patents

Description

• Die vorliegende Erfindung betrifft allgemein Fehlerdiffusionsverfahren mit symmetrischer Verbesserung für die Darstellung digitaler Bilddaten, und besonders die binäre oder vielstufige Darstellung von Bildern für Anzeigezwecke.
• Bildinformation, sei sie farbig, schwarz oder weiß, wird allgemein in einem Bitkartenformat (bitmap format) erzeugt, in dem die Bitkarte eine Vielzahl von Graustufen-Bildpunkten umfasst, d. h. Bildpunkte, die durch digitale Werte definiert sind, wobei jeder Wert eine Graustufe aus einer Menge von Graustufen darstellt. Somit sind in einem 8-Bit-System 256 Stufen von Grau vorhanden, wobei jede Stufe eine Zunahme von Grau zwischen Weiß und Schwarz darstellt. Im Fall farbiger Bitkarten, in dem drei definierende Farben oder Abtrennungen jeweils 256 Stufen der Information einschließen, können mehr als 16 Millionen Farben durch Grau-Bitkarten definiert werden.
• Gewöhnlich sind Bitkarten in solch einem Graustufenformat nicht durch Standarddrucker druckbar. Standarddrucker drucken eine begrenzte Anzahl von Stufen, entweder ein Pünktchen oder kein Pünktchen in dem binären Fall, oder eine begrenzte Anzahl von Stufen, um die Graustufenbilddaten auf eine begrenzte Anzahl von Stufen zu reduzieren, so dass sie gedruckt werden. Neben der durch Abtasten abgeleiteten Graustufeninformation können Computergraphikprozesse und andere Bildverarbeitungsprozesse Graustufenbilder für die Wiedergabe produzieren.
• Ein Standardverfahren der Umwandlung von Graustufenbildpunktwerten zu binäre Bildpunktwerte ist mittels der Verwendung von Halbtonbildungsprozessen (Dithering-Prozesse). In solchen Anordnungen wird über einen gegebenen Bereich mit einer Anzahl von grauen Bildpunkten dort drin jeder Bildpunktwert eines Feldes von Graustufenbildpunkten innerhalb des Bereichs mit einer Menge von vorgewählten Schwellwerten verglichen (die Schwellwerte sind als eine Halbtonmatrix gespeichert, und sich wiederholende Muster, die durch diese Matrix erzeugt werden, werden als Halbtonzellen betrachtet), wie z. B. in US-A 4 149 194 beschrieben. Die Wirkung einer solchen Anordnung ist, dass in einem Bereich, in dem das Bild grau ist, einige der Schwellwerte innerhalb der Halbtonmatrix überschritten werden, d. h. der Bildwert an der spezifischen Stelle ist größer als der Wert, der in der Halbtonmatrix für dieselbe Stelle gespeichert ist, während andere Schwellwerte nicht überschritten werden. In dem binären Fall könnten die Bildpunkte oder Zellenelemente, für welche die Schwellwerte überschritten werden, schwarz gedruckt werden, während die verbleibenden Elemente weiß bleiben dürfen, abhängig von der aktuellen physikalischen Menge, die durch die Daten beschrieben wird. Die Wirkung der Verteilung von Schwarz und Weiß über die Halbtonzelle wird durch das menschliche Auge als grau integriert. Jedoch ergibt der Dithering- oder Halbtonbildungsprozeß Probleme, indem die Menge von Grau innerhalb eines Originalbildes über ein Feld nicht genau eingehalten wird, weil die begrenzte Anzahl von Elementen innerhalb jeder Halbtonmatrix - und deswegen innerhalb jeder Halbtonzelle - nur die Wiedergabe einer begrenzten Anzahl von Graustufen zuläßt, d. h. eine Anzahl von Elementen in der Zelle plus Eins, oder weniger. Der Fehler, der sich aus der Differenz zwischen dem Ausgabebildpunktwert und dem aktuellen Graustufenbildpunktwert an irgendeiner bestimmten Zelle ergibt, wird einfach weggeworfen. Dies ergibt einen Verlust von Bildinformation. Insbesondere bringen Hafbtonprozesse grobe Quantisierungserscheinungen, die in den Bildbereichen sichtbar sind, in denen sich die Szene wenig verändert. Dies ist als "Bandbildung" bekannt, und wird verursacht durch die begrenzte Anzahl von verfügbaren Ausgabegraustufen. Die "Band"-Erscheinungen nehmen allgemein mit einer Verkleinerung der Zellgröße zu, was identisch zu einer Abnahme in der Anzahl der Stufen ist, die durch die Halbtonzelle dargestellt werden kann.
• In dem ARIES-(Alias Reduktion and Image Enhancement System-)Verfahren der Halbton- Wiedergabe, das durch P. Roetling in "Halftone Method With Enhancement and Moire Suppression," J. Opt. Soc. Amer., Band 66, Nr. 10, Seiten 985-989, Oktober 1976 beschrieben wird, wird anfänglich eine Menge von Halbton-Bildschirmwerten für eine Zelle zu der Bildinformation addiert. Ein gleichmäßiger Schwellwert wird auf die überprüfte Information angewendet, um einen Ausgabewert zu produzieren. Der durchschnittliche Grauwert über den Zellbereich des Eingabebildes wird mit dem durchschnittlichen Grauwert über den Zellbereich des Ausgabebildes verglichen. Dies wird ebenfalls in US-A 4 051 536 und US-A 4 633 327 beschrieben. Auf diese Weise wird der Fehler zwischen Original und Ausgabe über jede Halbtonzelle minimiert. Die Band-Erscheinung wird jedoch nicht reduziert.
• Algorithmen, die Graustufenbilder in binäre Bilder oder Bilder mit einer anderen Anzahl von Stufen umwandeln, streben nach einer Beibehaltung der existierenden lokalen Dichte, und umfassen unter ihnen die Fehlerdiffusion, die z. B. in "An Adaptive Algorithm for Spatial Greyscale" von Floyd und Steinberg erläutert wird. Zusätzliche Modifikationen zu dem von Floyd und Steinberg beschriebenen Fehlerdiffusionsalgorithmus wurden vorgeschlagen, z. B. eine unterschiedliche Gewichtungsmatrix, wie z. B. in "A Survey of Techniques for the Display of Continuous Tone Pictures an Bilevel Displays" von Jarvis et al., Computer Graphics and Image Processing, Band 5, Seiten 13-40, (1976) beschrieben wird.
• "MECCA - A Multiple-Error Correction Computation Algorithm for Bi-Level Image Hardcopy Reproduction" von Stucki, IBM Res. Rep. RZ(1981) beschreibt ebenfalls einen Fehlerdiffusionsalgorithmus, der die aktuelle Druckerpunktüberlappung in die Fehlerberechnung einbaut, und dadurch bessere Druckergebnisse erzeugt.
• US-A 5 055 942 schlägt ein anderes, Bildpunkt-basiertes Fehlerdiffusionsschema vor, in dem die Tendenz der individuellen Punkte zu einer Haufenbildung in einem überprüften Bild verändert werden kann durch Anwendung einer Hysteresekonstante und durch Rekursionstechniken, die von anpassender Überprüfung bekannt sind, um die Einstellung der Bildrauigkeit durch Einstellung der Hysteresekonstanten zu ermöglichen. Dies Verfahren produziert bessere Bilder, besonders für elektrophotographisches Drucken, als die ursprünglichen Fehlerdiffusionsalgorithmen, aber die Bilder tendieren dazu, eine reduzierte Schärfe oder Detailauflösung zu haben, verglichen mit Floyd und Steinberg. In der Verwirklichung verwendet das in US-A 5 055 942 beschriebene Verfahren einen Fehlerdiffusionsprozeß, und sieht eine Rückwirkungsreaktion auf der Basis des Ausgabebildes und besonders der Punktgröße vor. Die sich ergebende, unregelmäßige Plazierung von Punkten verbessert die Anzahl der Graustufen, die wiedergegeben werden können. Jedoch neigt die Hysteresefunktion, die für die Steuerung der Rückwirkungsreaktion verwirklicht wurde, zu einer Dämpfung der Wiedergabe von Kanten.
• US-A 4 625 222 legt ein Druckverbesserungssteuerungssystem für eine elektrostatische Kopiermaschine offen, wobei die Steuerungslogikschaltkreise eine Menge von Bildveränderungsparametern verarbeiten, um die Bildproduktionsqualität zu verbessern. Diese Parameter sind entweder vorbestimmt, fest oder wurden von einer externen Quelle empfangen, und verbessern die Bildqualität (d. h. Auflösung) durch Modifizierung der modulierten Graustufensignale.
• US-A 4 700 229 legt einen Bildverbesserungsschaltkreis offen, der ein Bildsignal niedriger Qualität durch Modifizieren der binären Darstellung eines Bildes in ein Bildsignal hoher Qualität umwandelt. Die Bildverbesserung wird erreicht durch Multiplizieren einer Reihe von Fehlerdifferenzsignalen durch eine Reihe von Gewichtungsfaktoren k(i), die eine klareres Bild durch Verbesserung der Bildauflösung produzieren.
• US-A 4 672 463 legt ein Verfahren offen, um die Bildqualität innerhalb einer elektrostatischen Wiedergabemaschine zu verbessern, wobei die Schärfe eines Bildes auf der Basis eines Wertes eines Bildschärfesteuerungsparameters verbessert wird, welcher bei der Prüfung der Kopienqualität eines Originals berechnet wurde.
• US-A 4 709 250 legt einen Bildformungsapparat offen, der die Halbtonbildqualität eines Originals verbessert. Die Impulsbreite eines Referenzsteuerungssignals steuert und verbessert die Bildqualität als Reaktion auf ein erkanntes Bilddichtesignal.
• US-A 4 724 461 legt eine Bildverbesserungsprozeßsteuerung für eine elektrostatische Kopiermaschine offen, die eine hohe Bildqualität durch Einstellen einer Menge von Prozeßsteuerungsparametern einhält.
• US-A 4 256 401 legt ein Bilddichteeinstellungsverfahren offen, wobei eine vorbestimmte Bilddichtestufe innerhalb einer elektrostatischen Kopiermaschine als eine Standarddichte durch Verändern einer Menge von Eingabesteuerungsparametern eingehalten wird.
• US-A 4 693 593 legt ein Verfahren für die Verbesserung der Bildqualität durch Steuerung eines einzigen Prozeßparameters als Reaktion auf Veränderungen in den sensitometrischen Kennwerten eines Bildübertragungsteils offen.
• Modifikationen des Floyd-Steinberg-Algorithmus kann einen sich verändernden Schwellwert, einen Dither, statt eines festen Schwellwerts umfassen, wie durch Billotet-Hoffman und Bryngdahl in den Proceedings of the Society for Information Display, Band 24, 1983, "On the Error Diffusion Technique for Electronic Halftoning" gezeigt wird. Die sich anpassende Natur des Floyd-Steinberg-Algorithmus sieht automatisch eine scharfe, kantenverbessernde Erscheinung vor, die in dem ausgegebenen Bild nicht notwendig wünschenswert ist, während sie visuell ansprechend ist.
• Eine Schwierigkeit mit dem Floyd-Steinberg-Fehlerdiffusionsalgorithmus ist, dass eine eigene Kantenverbesserung in den Algorithmus eingebaut ist. Analysen der Ausgabe des Floyd- Steinberg-Fehlerdiffusionsalgorithmus veranschaulichen ein charakteristisches Überschießen (zu hell oder zu dunkel) an Aufwärts- und Abwärtsübergängen, oder Stufen, in den digitalen Bilddaten mit kontinuierlichem Ton. Nach der Verwendung in dieser Spezifikation bezieht sich "kontinuierlicher Ton" auf Eingabedaten, die in eine größere Anzahl von diskreten Werten als für die Ausgabedaten beabsichtigt quantisiert wurden.
• Obgleich diese Systeme einen gewissen Grad an Bildverbesserung vorsehen, sehen sie allgemein nicht die Mittel vor, um die Kantenverbesserung von Regionen innerhalb des Bildes zu steuern. Jedoch dient US-A 5 045 952 dazu, eine gewisse bildabhängige Kantenverbesserung vorzusehen. Zu diesem Zweck beschreibt US-A 5 045 952 ein Verfahren der dynamischen Einstellung des Schwellwertpegels eines Fehlerdiffusionsalgorithmus, um das Ausmaß der in die codierte Ausgabe eingebrachten Kantenverbesserung selektiv zu steuern. Der Schwellwertpegel wird auf einer Bildpunkt-zu-Bildpunkt-Basis selektiv modifiziert, und kann verwendet werden, um die Kantenverbesserung des ausgegebenen digitalen Bildes zu vergrößern oder zu verkleinern, und so genauer die originale Detail- und Kantenschärfe des eingegebenen Bildes kontinuierlichen Tons darzustellen.
• Während der in US-A 5 045 952 beschriebene Ansatz gute Ergebnisse liefert, enthält die lineare Eingabeschwellwertmodulation Kantenverbesserungen, die asymmetrisch über das Bild sind. Die meisten Verbesserungen kommen auf einer Seite der Kante vor, was für das Auge rau erscheint.
• Andere Referenzen haben versucht, die Richtungsabhängigkeit von Fehlerdiffusion anzusprechen, einschließlich US-A 5 521 989 mit dem Titel "Balanced Error Diffusion System", und US-A 5 467 201 mit dem Titel "Iterative Error Diffusion". Keine dieser Referenzen spricht die Richtungsabhängigkeit der Kantenverbesserung an.
• Es ist deshalb ein Ziel der vorliegenden Erfindung, ein Verfahren für die Quantisierung von Graustufenbildern vorzusehen, das zusätzlich symmetrische Kantenverbesserung vorsieht.
• EP-A 0 454495 legt Bildverarbeitungsschaltkreise offen, die enthalten: eine Speichereinrichtung für das Speichern sukzessiver Mengen solcher Bilddatenstücke, die sich jeweils auf solche originalen Bildpunkte beziehen, deren jede Menge aus Datenstücken besteht, die sich auf einen Zielbildpunkt (Dm,n) beziehen, und ferner von Datenstücken, die sich jeweils auf umgebende Bildpunkte beziehen, die dem Zielbildpunkt benachbart sind;
• eine Berechnungseinrichtung für den Empfang von Bilddatenstücken einer solchen gespeicherten Menge und für die Produktion eines modifizierten Zielbildpunktdatenstücks (D'm,n), das von dem sich auf den Zielbildpunkt (Dm,n) der Menge beziehenden Bilddatenstück abgeleitet ist, in Unabhängigkeit von den jeweiligen Unterschieden in den Dichtewerten zwischen jenem Bilddatenstück (Dm,n) und den weiteren Datenstücken der betroffenen Menge;
• eine Vergleichseinrichtung für den Vergleich des Dichtewertes des Zielbildpunktdatenstücks (Dm,n) mit einem Schwellwert (TH&sub1;) und für die Bestimmung, abhängig von dem Ergebnis solch eines Vergleichs, solch eines Ausgabedatenstück (Om,n), das mit dem betrachteten Zielbildpunkt korrespondiert; und
• eine Fehlerkorrektureinrichtung für die Bestimmung eines Zielbildpunktfehlers (Em,n), der repräsentativ für den Unterschied in den Dichtewerten zwischen dem modifizierten Bildpunktstück (D'm,n) und dem Ausgabedatenstück (Om,n) ist, und für die Modifikation, abhängig von dem Fehler (Em,n), solcher weiteren Datenstücke in der Speichereinrichtung, um so die Schaltkreise in die Lage zu versetzen, solch einen bestimmten Zielbildpunktfehler zu kompensieren, wenn nachfolgende Mengen solcher Bilddatenstücke verarbeitet werden.
• EP-A 0 702 482 legt eine Fehlerdiffusionstechnik offen.
• Nach einem Aspekt der vorliegenden Erfindung wird ein Verfahren für die Verarbeitung elektronischer Bilder nach Anspruch 1 vorgesehen.
• Nach einem anderen Aspekt der vorliegenden Erfindung wird ein Verarbeitungssystem für die Verarbeitung elektronischer Bilder nach Anspruch 7 vorgesehen.
• Die Erfindung sieht eine Operation vor, welche die asymmetrische Kantenverbesserung der kantenverbessernden Fehlerdiffusion von US-A 5 045 952 aufhebt, und sie durch eine wünschenswertere symmetrische Kantenverbesserung ersetzt.
• Noch ein anderer Aspekt der Erfindung ist die Verwendung einer kantenverbessernden Fehlerdiffusion, um symmetrische Kantenverbesserung an Bildern mit kontinuierlichem Ton vorzunehmen, einschließlich nicht Halbton-bildender Prozesse. In solchen Prozessen werden nicht Bildpunkte von M Stufen zu N Stufen quantisiert, wobei M > N ist, sondern der Prozeß kann einfach Bildpunkte von einer Erscheinung zu einer anderen unter Beibehaltung derselben Anzahl von Stufen wandeln. In US-A 5 363 209 wird ein Beispiel eines kantenverbessernden Fehlerdiffusionsprozessors veranschaulicht, ohne dass Quantisierung auf eine niedrigere Anzahl von Stufen verlangt wird, die jedes Bildsignal oder Bildpunkt definieren.
• Für ein besseres Verstehen der vorliegenden Erfindung wird nun nur beispielhaft Bezug genommen auf die begleitenden Zeichnungen, in denen dieselben Bezugszeichen auf gleiche Teile angewendet werden, und in denen:
• Fig. 1 ein Blockdiagramm ist, das ein System veranschaulicht, in dem die vorliegende Erfindung Verwendung finden kann;
• Fig. 2 ein Blockdiagramm des vorgeschlagenen Systems ist;
• Fig. 3 das symmetrische Filter veranschaulicht, das auf das eingegebene Bild angewendet wird; und
• Fig. 4 das asymmetrische Filter veranschaulicht, das auf die Schwellwertmodulationsfunktion angewendet wird.
• Mit Bezug auf die Zeichnungen, die nur zum Zweck der Beschreibung einer Ausführungsform der Erfindung und nicht für ihre Begrenzung gezeigt werden, wird nun ein Basissystem für die Ausführung der vorliegenden Erfindung in Fig. 1 gezeigt. In dem vorliegenden Fall können Graustufenbilddaten von einem Bildeingabegerät (im Folgenden IIT, Image Input Terminal, genannt) als Bilddaten oder Bildpunkte charakterisiert werden, wobei jeder Bildpunkt davon durch eine einzige Stufe oder optische Dichte in einer Menge von 'c' optischen Dichtegrößen oder Stufen definiert ist, und die Anzahl der Mitglieder in der Menge häufig größer als gewünscht ist. Die gewünschte Anzahl der Stufen ist durch die Fähigkeit des Druckers 4 oder durch andere Systemüberlegungen gegeben. Jeder Bildpunkt von IIT 1 wird in der Bildverarbeitungseinheit 2 (im Folgenden IPU, Image Processing Unit, genannt) in der unten beschriebenen Weise verarbeitet, welche eine Halbtonverarbeitung 3 hat, um jeden Bildpunkt in Werten einer neuen, möglicherweise kleineren Menge von 'd' Größen oder Stufen neu zu definieren. In diesem Prozeß sind 'c' und 'd' ganzzahlige Werte, die Bildpunkttiefe darstellen, welche die Größe der Dichte darstellen. Hier können Farbdaten als eine Anzahl von unabhängigen Kanälen oder Abtrennungen dargestellt werden, welche unabhängig voneinander behandelt werden, oder die Farbdaten können als Vektordaten in einem vordefinierten Farbraum dargestellt werden, z. B. RGB, CIELab, u. s. w., die Vektoroperationen bei der Schwellwertbehandlung, Fehlerberechnung und -korrektur unterworfen werden. Ein gewöhnlicher Fall dieses Verfahrens umfasst die Umwandlung von Daten von einer relativ großen Menge von Graustufen auf eine oder zwei legale oder Fachwerte für das Drucken in einem binären Drucker 4. Ein anderer Fall ist die Umwandlung von Daten von einer relativ großen Menge von Farbdaten, die als Rot, Grün und Blau, oder Zyan, Magenta, Gelb und Schwarz ausgedrückt werden, auf eine von fünf legalen Fachwerten für das Drucken auf dem Drucker 4, wie in US-A 5 317 653 beschrieben ist.
• Noch ein anderer Fall ist die Verwendung einer kantenverbessernden Fehlerdiffusion, um Kantenverbesserung in Bildern kontinuierlichen Tons durchzuführen, einschließlich nicht halbtonbildender Prozesse. In solchen Prozessen werden nicht Bildpunkte von c Stufen zu d Stufen quantisiert, wobei c > d ist, sondern der Prozeß kann einfach Bildpunkte von einer Erscheinung zu einer anderen unter Beibehaltung derselben Anzahl von Stufen wandeln. In US-A 5 363 209 wird ein Beispiel eines kantenverbessernden Fehlerdiffusionsprozessors veranschaulicht, ohne dass Quantisierung auf eine niedrigere Anzahl von Stufen verlangt wird, die jedes Bildsignal oder Bildpunkt definieren. Während die Beschreibung auf die Verwendung der Erfindung bei der Halbtonbildung fokussieren wird, ist zu erkennen, dass der Fall von c Stufen = d Stufen sehr wohl innerhalb des Umfangs der vorliegenden Erfindung liegt.
• Ein eingegebenes Bild des Typs, der wie im Folgenden beschrieben zu verarbeiten ist, kann dargestellt werden durch eine Menge von Grauwerten (Graustufenbildpunkten), die in einem Feld von L Linien angeordnet sind, wobei jede Linie N Grauwerte mit der Tiefe b enthält, und jeder andere Bildpunkt in dem Feld durch l(n,l) bezeichnet wird. Grauwerte werden typisch als ganze Zahlen ausgedrückt, mit einem Beispiel, das in den Bereich von 0 bis 255 fällt, obgleich größere oder kleinere Stufenzahlen, wie auch nicht ganzzahlige Darstellungen, möglich sind. Ein Ausgabebild wird als aus Bildpunkten bestehend angesehen, und jeder Bildpunkt korrespondiert mit einem Ausgabeelement, das durch einen digitalen Drucker oder eine Anzeige ausgegeben wird. Grau bezeichnet hier nicht eine bestimmte Farbe, sondern einen Grad der optischen Dichte.
• Mit Bezug auf Fig. 2, die ein beispielhaftes Blockdiagramm des Fehlerdiffusionsprozesses vorsieht, übergibt ein Speicherfeld von eingegebenen Bildsignalen im Eingabe-RAM 8, das von irgendeinem Bild sein kann, einschließlich abgetasteter Bilder von einem Scanner 9, wie etwa dem XEROX 7650 Prolmager oder einem DocuSP-Scanner, die mit geeigneter Treibersoftware betrieben werden, oder von Darstellungen, die vom Computer erzeugte wurden, das Eingabebild l in das System auf einer Signal-zu-Signal-Basis, wobei n,l die Position eines einzigen Bildsignals l(n,l) in einem Strom von Bildsignalen darstellt. Solch ein Scanner erzeugt Graustufensignale oder Bildpunkte, die allgemein als Viel-Bit-Werte oder N-Bit-Werte definiert sind, welche 2N mögliche Stufen der optischen Dichte definieren. (n,l) bezieht sich in dieser Beschreibung sowohl auf das Signal, das bei n,l in dem Eingabesignalstrom positioniert ist, als auch auf die optische Intensität oder Dichte des Bildsignals an der Position n,l. Anfänglich wird ein einziges Signal l(n,l) in dem Eingangsregister 10 gespeichert, das für das Halten eines Viel-Bit-Signals geeignet ist. Bei jedem Eingabesignal wird im Addierer 12 ein korrespondierendes Fehlerkorrektursignal ε zu dem Bildsignal l(n,l) addiert, wobei ε(n,l) eine Summe gewichteter Fehlertermsignale vorangegangener Bildpunkte ist, die zu l(n,l) hinzu zu addieren ist, was zu einem modifizierten Bildsignal führt. Das modifizierte Bildsignal, die Summe des eingegebenen Bildsignals und des Fehlerkorrektursignals vorangegangener Bildpunkte (l(n,l) + ε(n,l)) wird dem Schwellwertvergleicher 14 zugeleitet, um den korrespondierenden Ausgabezustand Si zu bestimmen, wobei Fig. 2 zur Einfachheit den Fall für zwei Ausgabezustände S1 und S2 zeigt, obgleich mehrere Ausgabestufen möglich sind. Im Schwellwertvergleicher 14 wird l(n,1) + ε(n,l) mit dem Schwellwertsignal t(n,l) verglichen, das eine Funktion t = {t&sub1;...td-1} ist, wie weiter unten beschrieben wird, was ein oder mehrere Werte sein kann, abhängig von dem Wert d hinsichtlich c, um ein angemessenes Ausgabesignal B(n,l) zu bestimmen, wie z. B. für ein binäres Drucksystem, ein Pünktchen oder kein Pünktchen. Falls das Signal l(n,l) + ε(n,l) als Ergebnis dieses Vergleichs größer als das Bezugssignal ist, dann wird ein Bildsignal, das ein einziges weißes Pünktchen darstellt, dem Ausgaberegister 18 von dem RAM-Speicher 20 übergeben. Falls das Signal l(n,l) + ε(n,l) als Ergebnis dieses Vergleichs kleiner als das Bezugssignal ist, dann wird ein Bildsignal, das ein einziges schwarzes Pünktchen darstellt, dem Ausgaberegister 18 von dem RAM-Speicher 22 übergeben. Falls ein weißer Bildpunkt dem Ausgaberegister 18 übergeben wird, wird Schalter S1 freigegeben, um das modifizierte Eingabebildsignal l(n,l) + ε(n,l) in Fehlerregister 30 ohne Änderungen speichern zu lassen. Falls ein schwarzer Bildpunkt dem Ausgaberegister 18 übergeben wird, wird Schalter S2 freigegeben, um das modifizierte Eingabesignal l(n,l) + ε(n,l) in Fehlerregister 30 speichern zu lassen, nachdem ein Wert für Schwarz (-255 im Fall von 8 Bit) von dem Signal subtrahiert wurde. Bildpunkte, die im Ausgaberegister 18 gespeichert werden, werden schließlich als Druckerausgabesignale ausgegeben, wie von der bildgebenden Anwendung, z. B. einem binären Drucker 40, gefordert. In dem vorliegenden Fall kann der Drucker irgendein binärer Drucker sein, z. B. der XEROX 4011 Drucker (einfach, niedrige Geschwindigkeit) oder der XEROX DocuTech Model Production Printer 135 (ein sehr komplexer Drucker mit hoher Geschwindigkeit).
• Ein Fehler, der bei der Quantisierung von Bildpunkten bestimmt wurde, wird im Fehler-RAM 32 gespeichert, bis ein Bildsignal, das die Addition von Fehlern verlangt, durch das System behandelt wird. Dann wird der Abschnitt der gespeicherten Fehler von früheren Quantisierungen von den Frühere-Fehler-Registern 52, 54 und 56 und von dem Fehlerregister 30 an den Addierer 50 übergeben. Die Fehlerregister 52, 54 und 56 sind miteinander verbunden, um die Verschiebung des Fehlersignals von Register zu Register zu ermöglichen, wenn eine Linie von Daten durch das beschriebene System läuft. Fehlersignale werden entsprechend der Floyd-Steinberg-Fehlerdiffusion über Multiplizierer A, B, C bzw. D geführt, wobei ein Gewichtungsschema nach Wunsch ausgewählt wird. Es wird bemerkt, dass vier Fehlersignale nur für Zwecke der Veranschaulichung verwendet werden, und dass eine kleinere oder größere Anzahl in aktuellen Verwirklichungen verwendet werden kann.
• Um t(n,l) abzuleiten, wird das Eingabebildsignal l(n,l), das im Eingaberegister 10 gespeichert ist, dem Schwellwertmodulationsprozessor 70 zugeleitet, wie weiter unten beschrieben wird.
• Die Grundsätze der Erfindung werden nun anhand eines beschriebenen Fehlerdiffusionsprozesses diskutiert. Bei der Schwellwertmodulation, wird eine räumlich sich verändernde Funktion von dem Schwellwert subtrahiert (oder zu dem Eingabebild addiert, was gleichwertig ist). Es kann gezeigt werden, dass der Prozeß der Modulation des Schwellwerts auf diese Weise ein Ausgabebild erzeugt, das genau gleich dem Bild ist, das durch Vorfiltern des Eingabebilds und Verarbeiten mit Standardfehlerdiffusion produziert wird. Diese Gleichwertigkeit wird durch K. Knox und R. Eschbach in "Threshold Modulation in Error Diffusion", J. Electronic Imaging, Seiten 185-192, Juli 1993 gezeigt. Die folgende Beschreibung wird unter Verwendung eindimensionaler Funktionen gezeigt, aber die Erweiterung auf zweidimensionale Funktionen ist klar.
• Das Spektrum des gleichwertig vorgefilterten Bilds wird gegeben durch:
• le(u) = l(u) + F(u) T(u) (1)
• wo
• F(u) ein asymmetrisches Hochpassfilter ist, das durch Fehlerdiffusionsgewichte bestimmt wird,
• T(u) das Spektrum der Schwellwertmodulationsfunktion t(x) ist, und
• l(u) linear proportional zu dem Eingabebild i(x) ist.
• Wenn T(u) linear proportional zum Eingabebild ist, dann wird das gleichwertige Eingabebild zu:
• le(u) = l(u) [1 + c F(u)] (2)
• Da F(u) ein Hochpassfilter ist, ist das gleichwertige Eingabebild le(u) eine verbesserte Version des eingegebenen Bilds, dessen hohe, räumliche Frequenzen durch das Filter F(u) verstärkt wurden. Die einzige Schwierigkeit ist, dass die Verbesserung asymmetrisch ist, weil F(u) asymmetrisch ist.
• In dieser Erfindung wird eine Schwellwertmodulation verwendet, die eine gefilterte Version des Eingabebilds ist, d. h.
• T(u) = c l(u) S(u)/F(u) (3)
• wo
• S(u) ein symmetrisches, lineares Hochpassfilter ist.
• Nach Einsetzung in Gleichung (1) wird das gleichwertige Eingabebild deshalb zu:
• le(u) = l(u) [1 + c S(u)] (4)
• Wodurch eine symmetrische Kantenverbesserung in des Ausgabebild gebracht wird. Da der Filtereffekt der Fehlerdiffusion eine Gleichspannungskomponente gleich 0 hat, gibt es Fälle dieser Gleichung, die zu einer Division durch 0 führen. Das führt dazu, dass solch eine Anordnung unerwünscht ist.
• Dann ist der Schlüssel für die Produktion der in Gleichung (2) gezeigten Schwellwertfunktion, das symmetrische Filter S(u) auf das ursprüngliche Eingabebild anzusetzen, und das asymmetrische Filter F(u) auf die existierende Schwellwertmodulationsfunktion. In solch einem Prozeß wird eine Division durch 0 beseitigt. Dies kann erkannt werden durch Multiplikation beider Seiten von Gleichung (3) mit F(u), was ergibt:
• F(u) T(u) = c l(u) S(u) (5)
• Die asymmetrische Standardhochpassfilterfunktion F(u) kann mittels der Koeffizienten βm definiert werden:
• F(u) = 1 - Σβm e-imuΔx (6)
• Wenn Gleichung (6) in Gleichung (5) eingesetzt wird, ergibt sich das Spektrum der Schwellwertfunktion zu:
• T(u) = l(u) S(u) + T(u) Σβm e-imuΔx (7)
• In dieser Gleichung wird angenommen, dass die Kantenverbesserungskonstante c gleich 1 ist. Um die Verbesserung in Korrespondenz zu c einzuführen, wird die Schwellwertfunktion in einem späteren Schritt mit c multipliziert.
• Wenn das symmetrische Filter S(u) auch ein Hochpassfilter ist, dann wird es mittels der Koeffizienten αm definiert in der Form:
• S(u) = 1 - Σαm e-imuΔx (8)
• Das Einsetzen der Gleichung (8) in die Gleichung (7) und das Transformieren der spektralen Funktionen zurück in ihre korrespondierenden Bildraumfunktionen ermöglicht eine Bestimmung der Schwellwertfunktion durch Verwirklichen der folgenden rekursiven Gleichung:
• t(x) = i(x) - Σαm i(x - mΔx) + Σβm t(x - mΔx) (9)
• wo
• i(x) das Eingabebild ist,
• t(x) die Schwellwertmodulationsfunktion ist,
• αm die Koeffizienten für das symmetrische Filter S(u) sind, und
• βm die Koeffizienten für das asymmetrische Fehlerdiffusionsfilter F(u) sind.
• Die Verwirklichung der Schwellwertfunktion auf zwei Dimensionen ist geradlinig und ist gegeben durch:
• t(x,y) = i(X,Y) - Σαnm i(x - mΔx, y - nΔy) + Σβnm t(X - mΔx, y - nΔy) (10)
• wo αnm und βnm die zweidimensionalen Koeffizienten für das symmetrische Filter S(u) bzw. das asymmetrische Fehlerdiffusionsfilter F(u) sind.
• Dieses Ergebnis zeigt, dass die Schwellwertfunktion t(x) bestimmt wird durch ein asymmetrisches Filtern der Eingabebilddaten und ein symmetrisches Filtern der Schwellwertfunktion selbst. Das symmetrische Filter kann sowohl vorwärts als auch rückwärts gerichtet sein. Das asymmetrische Filter braucht nur rückwärts gerichtet sein, da sein Zweck das Aufheben der Wirkungen des asymmetrischen Fehlerdiffusionsfilters ist. Nachdem die Schwellwertfunktion t(x) aus Gleichung (10) bestimmt ist, kann die Verbesserung eingestellt werden durch Multiplizieren der Schwellwertfunktion mit einer Konstanten c. Falls die Konstante Null ist, dann gibt es keine in das Ausgabebild eingebrachte Kantenverbesserung.
• Es ist leicht zu erkennen, dass S(u) und F(u) auf ähnliche wie der oben für die Gleichungen (6) und (8) beschriebenen Weise dargestellt werden können, wie folgt:
• S(u) = 1 - Σαnm e-imuΔν-invΔI
• F(u) = 1 - Σβnm e-imuΔn-invΔI
• Fig. 3 zeigt die symmetrischen Filterkoeffizienten, die auf das ursprüngliche Eingabebild angesetzt werden. Fig. 4 zeigt die asymmetrischen Filterkoeffizienten, die auf das Schwellwertfilter angesetzt werden. Es wird bemerkt, dass das symmetrische Filter nicht kausal ist, und eine Kenntnis des Bildes nach der gegenwärtigen Abtastlinie verlangt. Dies wird leicht erreicht durch einen internen Abtastlinienpuffer. Andererseits ist das durch den Fehlerdiffusionsprozeß bewirkte Filter kausal und benötigt nicht die Kenntnis der gefilterten Schwellwertmodulationsfunktion nach der gegenwärtigen Abtastlinie.
• Bei der Überlegung der Verwirklichung der gegenwärtigen Erfindung und mit Bezug zurück zu Fig. 2 kann erkannt werden, dass die Schwellwertmodulationsfunktion verändert werden kann, um der Anforderung für die Erzeugung von Schwellwerten zu genügen, welche die asymmetrische Reaktion des Standardfehlerdiffusionsfilters aufheben. Zu diesem Zweck sieht Block 70 eine Schwellwertmodulationsfunktion vor, welche die asymmetrischen Wirkungen des Fehlerdiffusionsprozesses aufhebt. Es wird bemerkt, dass die Funktion t(x,y) von der Bildeingabe i(x,y) abhängt, und von früheren Schwellwerten abhängt, die für benachbarte Bildpunkte bestimmt wurden, weil die Funktion rekursiv ist. Dementsprechend wird in dieser Verwirklichung ein Abtastlinienpuffer intern zu der symmetrischen Filterfunktion 74 angenommen, für das Halten kommender Eingabedaten, und ein zweiter Abtastlinienpuffer wird intern zu der Schwellwertmodulationsfunktion 70 angenommen, für das Speichern zurückliegender Schwellwertbestimmungen.
• Das diskutierte Verfahren kann leicht in Software unter Verwendung objektorientierter Software-Entwicklungsumgebungen verwirklicht werden, die einen portablen Quellcode vorsehen, der auf einer Menge von Computer- oder Arbeitsplatz-Hardware-Plattformen verwendet werden kann. Alternativ können die offengelegten Daten oder das strukturierte Dokumentverarbeitungssystem teilweise oder vollständig unter Verwendung von Standardlogikschaltkreisen oder unter Verwendung von VLSI-Entwicklung auf einem einzigen Chip in Hardware verwirklicht werden. Ob Software oder Hardware für die Verwirklichung des Systems verwendet wird, hängt von Geschwindigkeits- und Effizienzanforderungen des Systems ab, und auch von der bestimmten Funktion und den bestimmten Software- und Hardware-Systemen und dem bestimmten Mikroprozessor oder Mikrocomputersystemen ab, die verwendet werden. Das Dokumentverarbeitungssystem kann jedoch leicht und ohne unpassendes Experimentieren aus der hier vorgesehenen, funktionalen Beschreibung zusammen mit einer allgemeinen Kenntnis der Computertechnik durch die in der Technik Bewanderten entwickelt werden.

Claims (9)

1. Verfahren der Verarbeitung elektronischer Bilder, die als Bildsignale definiert sind, wobei jedes Bildsignal die Dichte an einer diskreten Position innerhalb des elektronischen Bildes darstellt, und der Quantisierung der Bildsignale, die als "c" Graustufen definiert sind, für die Verwendung in einer Vorrichtung, die Bildsignale verlangt, welche als "d" Graustufen definiert sind, wobei c ≥ d ist, und das Verfahren umfasst:

- Empfangen mindestens eines Abschnitts des elektronischen Bildes als Eingabesignale;

- Addieren von Fehlersignalen, die durch irgendwelche vorangegangene Schwellwertverarbeitung der Eingabesignale bestimmt werden, um korrigierte Eingabesignale zu erzeugen;

- Empfangen von korrigierten Bildsignalen, die an "c" Stufen definiert sind, und Quantisieren der korrigierten Bildsignale zu "d" Stufen durch Vergleichen mit einem Schwellwertsignal, und Ausgabe der korrigierten Bildsignale mit "d" Stufen als Ausgabesignale;

- Ausgeben der Ausgabesignale, die an "d" Stufen definiert sind;

- Erzeugen von Differenzsignalen, die repräsentativ für die Differenz in der Bilddichte zwischen korrespondierenden, korrigierten Eingabesignalen und den Ausgabesignalen ist;

- Empfangen der Differenzsignale und Übergabe gewichteter Abschnitte davon an einen Fehleradditionsschaltkreis für die Addition mit nachfolgenden Bildsignalen in einer vorbestimmten, räumlichen Beziehung zu den Eingabesignalen; und

- Verändern des Schwellwertsignals proportional zu dem eingegebenen Bild und rekursives Verändern des Schwellwertsignals als Reaktion auf vorangegangene Schwellwertmodulationssignale, entsprechend einer Schwellwertmodulationsfunktion mit einem Spektrum T(u), das definiert ist als:

T(u) = c l(u) S(u)/F(u)

wobei c eine Kantenverbesserungskonstante ist; l(u) ein Spektrum des Eingabebildes ist; S(u) ein symmetrisches, lineares Hochpassfilter ist; und F(u) ein asymmetrisches Hochpassfilter ist.

2. Verfahren nach Anspruch 1, wobei "d" = 2 ist.

3. Verfahren nach Anspruch 1 oder 2, wobei das Schwellwertsignal verändert wird entsprechend einer Filterfunktion:

T(u) = S(u) l(u) + T(u) Σβm e-imuΔn

wo T(u) das Spektrum der Schwellwertmodulationsfunktion t(x) ist, S(u) ein symmetrisches, lineares Hochpassfilter ist, l(u) das Spektrum des Eingabebildes i(x) ist, und βm die Koeffizienten für das asymmetrische Fehlerdiffusionsfilter sind.

4. Verfahren nach Anspruch 3, wobei das Filter S(u) ein symmetrisches Kantenverbesserungsfilter ist.

5. Verfahren nach Anspruch 4, wobei das Kantenverbesserungsfilter die Eingangssignale verändert entsprechend der Filterfunktion:

S(u) = 1 - Σαvm e-imuΔn-invΔI

wo Σανm ein Filterkoeffizient auf der Basis des Beitrags des Eingangsbildes zu dem Schwellwertsignal t(n,l) ist.

6. Verfahren nach irgendeinem der Ansprüche 1 bis 5, einschließlich der Speicherung einer Vielzahl von Abtastlinien der bestimmten Schwellwertsignale, für die Verwendung in dem rekursiven Schwellwertbildungsprozeß.

7. Verarbeitungssystem für die Verarbeitung elektronischer Bilder, die als Bildsignale definiert sind, wobei jedes Bildsignal die Dichte an einer diskreten Position innerhalb des elektronischen Bildes darstellt, und für die Quantisierung der Bildsignale, die als "c" Graustufen definiert sind, für die Verwendung in einer Vorrichtung, die Bildsignale verlangt, welche als "d" Graustufen definiert sind, wobei c ≥ d ist, und das System umfasst:

- eine Bildeingabe (8), die mindestens einen Abschnitt des elektronischen Bildes als Eingabesignale i(x) empfängt;

- einen Fehleradditionsschaltkreis (12), der Fehlersignale addiert, die durch irgendwelche vorangegangene Schwellwertverarbeitung der Eingabesignale bestimmt werden, um korrigierte Eingabesignale zu erzeugen;

- einen Schwellwertprozessor (14), der korrigierte Bildsignale empfängt, die an "c" Stufen definiert sind, und die korrigierten Bildsignale zu "d" Stufen quantisiert, durch Vergleichen mit mindestens einem Schwellwertsignal, und die korrigierten Bildsignale mit "d" Stufen als Ausgabesignale ausgibt;

- eine Bildausgabe (18), die Ausgabesignale ausgibt, die an "d" Stufen definiert sind;

- einen Differenzbildungsschaltkreis, der Differenzsignale erzeugt, die repräsentativ für die Differenz in der Bilddichte zwischen korrespondierenden, korrigierten Eingabesignalen und den Ausgabesignalen ist;

- einen Fehlerverteilungsschaltkreis (30, 32, 50, 52, 54, 56), der die Differenzsignale empfängt und gewichtete Abschnitte davon an einen Fehleradditionsschaltkreis übergibt, für die Addition mit nachfolgenden Bildsignalen in einer vorbestimmten, räumlichen Beziehung zu den Eingabesignalen; und

- einen Schwellwertmodulationsschaltkreis (70, 74), der ein Schwellwertmodulationssignal t(x) produziert, mit dem der Schwellwertbildungsprozessor angesteuert wird, um das Schwellwertsignal proportional zu dem eingegebenen Bild zu verändern, und das Schwellwertsignal als Reaktion auf vorangegangene Schwellwertmodulationssignale rekursiv zu verändern, entsprechend einer Schwellwertmodulationsfunktion mit einem Spektrum T(u), das definiert ist als:

T(u) = c l(u) S(u)/F(u)

wobei c eine Kantenverbesserungskonstante ist; l(u) ein Spektrum des Eingabebildes ist; S(u) ein symmetrisches, lineares Hochpassfilter ist; und F(u) ein asymmetrisches Hochpassfilter ist.

8. System nach Anspruch 7, wobei der Schwellwertmodulationsschaltkreis (70, 74) ein Schwellwertmodulationssignal t(x) für die Ansteuerung des Schwellwertprozessors (14) produziert.

9. System nach Anspruch 7 oder 8, einschließlich eines Abtastlinienpuffers für die Speicherung von Schwellwerten, die durch eine Vielzahl von Schwellwertbestimmungen bestimmt sind.