DE3024459A1

DE3024459A1 - Pyramideninterpolation

Info

Publication number: DE3024459A1
Application number: DE19803024459
Authority: DE
Inventors: Paul Edward Franklin
Original assignee: Crosfield Electronics Ltd
Current assignee: Crosfield Electronics Ltd
Priority date: 1979-07-03
Filing date: 1980-06-28
Publication date: 1981-01-08
Also published as: US4334240A; JPS5614237A

Description

Die Erfindung bezieht sich auf Verfahren und Vorrichtungen zum Interpolieren zwischen grobgespeicherten Daten zur Erlangung einer genaueren Antwort. Die Erfindung ist insbesondere anwendbar auf reprografische Farbabtasteinrichtungen.

Bei Farbreproduktionseinrichtungen werden zunehmend Minicomputer und Microprcrassoren verwendet, um die Durchführung einer energiereicheren Verarbeitung zu ermöglichen. Jedoch laufen diese Farbabtaster bei sehr hohen Geschwindigkeiten, und selbst die schnellsten Computer können die erforderlichen Kalkulationen für in der Praxis verwendete Abtaster in "Realzeit" (real-time) nicht durchführen.

Eine bekannte Lösung dieses Problems besteht in der Aufstellung der erforderlichen Reproduktionscharakteristika und der anschließenden Errechnung des Ausgangs des Tasters für alle möglichen Eingangskombinationen, sowie der Speicherung der Ausgangsdaten in einem "Suchtisch" (look-up table). Beim anschließenden Abtasten eines Bildes braucht keinerlei Verarbeitung durchgeführt zu werden - die Eingangswerte werden lediglich benutzt zum Adressieren des Suchtisches, um die gewünschte Antwort festzustellen.

Farbabtaster analysieren ein zu reproduzierendes Original mit drei Primärfarben-Analysierkanälen, und in einem Digital-

030062/0916

ORiGfNAL INSPECTED

_ ₇. . 3024A59

Abtaster müssen diese Eingänge quantisiert werden, vorzugsweise auf wenigstens 8 Bits, um einen Druck hoher Qualität

24
zu erreichen. Dies würde 2 mögliche Eingangskombinationen ergeben und einen entsprechend großen Suchtischspeicher erforderlich machen, was sich aus Kostengründen und wegen der zu seiner Beschickung erforderlichen Zeit verbietet. Eine Lösung dieses Problem"; ist gegeben in dem britischen Patent desselben Anmelders No. 1.369.702, in welchem der Suchtisch lediglich aus den vier bedeutensten Bits jedes Kanals rech-

12
nerisch erstellt wird, was 2 Kombinationen ergibt. Während des Abtastens werden die vier bedeutendsten Ziffern jedes Kanals benutzt, um diesen "groben" Suchtisch zu adressieren, während die vier am wenigsten bedeutenden Ziffern jedes Kanals benutzt werden, um zwischen benachbarten Punkten des Tisches zu interpolieren.

Der in dem oben erwähnten Patent beschriebene interpolator ist ein linearer Interpolator, d. h., er nimmt an, daß die zu interpolierende Funktion innerhalb des Raums zwischen den Punkten des groben Tisches linear ist. Dies ist nicht allgemein zutreffend, und es müssen gewisse Fehler auftreten, da Kurven durch eine Reihe gerader Linien angenähert werden. In den meisten Fällen sind die Fehler gering und ganz annehmbar, jedoch in einigen Fällen, insbesondere im Falle der Schwarzdruckgeneration, können die Fehler schv/erwiegend sein. Die

030062/0916 ..-/8

_₈_ 302U59

vorliegende Erfindung sucht diese Fehler auszuschalten oder zu vermindern.

Vor einer Definition der Erfindung werden die durch die lineare Interpolation erzeugten Schwierigkeiten mit Hilfe eines Beispiels erläutert, bei dem es sich um einen dreidimensionalen Farbraum handelt, und zwar mit Bezugnahme auf Fig. 2 der beigefügten Zeichnungen, die einen Interpolator-"Würfel" zeigt, d. h. den begrifflichen Würfel, der gebildet ist durch einen adressierten Punkt in dem Suchtisch und die sieben benachbarten Punkte, die adressiert würden durch Vergrößerung der vier bedeutendsten Bits jedes Kanals einzeln und in allen Kombinationen um ein "grobes" Element.

Fig. 2 zeigt einen Interpolatorwürfel, der einer"linearen Matrix" von Cyan-Werten entnommen wurde. Die Bezeichnung "lineare Matrix" wird benutzt zur Beschreibung eines Suchtisches, in welchem jeglicher Eingangswert einen Ort in einem Speicher adressiert, v/o der Wert selbst gespeichert ist. In diesem Fall wird, was für ein Eingang auch immer in den Abtaster gelangen mag, an dem Ausgang derselbe Wert erzielt. Es ist zu beachten, daß es im allgemeinen nicht möglich ist, nur aufgrund einer Betrachtung des Bruchteils c, der durch die am wenigsten bedeutenden Bits des digitalen Cyan-Signals dargestellt wird, zwischen einem groben Signal C und dem ver-

030062/0916

302U59

grö-ßerten Signal C + 1 zu interpolieren; dies ist darauf zurückzuführen, daß die Menge des erforderlichen Cyans auch durch die Werte der Gelb- und Magenta-Signale beeinträchtigt wird.

Wenn der lineare Matrixsuchtxsch mit der folgenden Eingangskombination adressierü wird

0010	32	dezimal
0010	32	i;
0010	32	Il

dann entspricht der adressierte Interpolatorwürfel der Darstellung in Fig. 2 für Cyan. Analoge Würfel werden adressiertfür Magenta, Gelb und Schwarz, v/o ein Schwarzdruck benutzt wird. Der Punkt C_{v M} _ in Fig. 2 stellt den Dezimalwert (32, 32,32) dar, auf den oben Bezug genommen ist, und wird für die Zwecke der Interpolation als "weiß" bezeichnet. Der Punkt C,„₊₁. /γ₊ι\ ic + 11 ' ^^er ^ⁿ 3^e(^^er Richtung um eine grobe Einheit vergrößert ist, stellt somit dezimal ausgedrückt einen Punkt (48, 48, 48) dar. Die Werte für c, y, m werden gegeben durch die vier am wenigsten bedeutenden Ziffern der Terme der Eingangskombination und sind ausgedrückt als Bruchteile, d. h. die Bitkombination 1000, welche eine Hälfte der grundlegende" "groben" Einheit darstellt, gibt einen Wert von 1/2 für den

.../10

030062/0916

entsprechenden Farb-"Rest" m, y oder c,

Der bekannte Interpolator-Algorithmus ist:

Cyan-Ausgang =

YMC

'MY(C+D

'M(Y+1)C

(M+1)YC

(M+1) Y (C+1)

(M+1) (Y+1)C

(M+1) (YH) (C+1)

x (1-m)(1-y)(1-c) χ (1-m).(1-y) c χ (1-m)y(1-c) χ (l-m)yc χ m(l-y)(1-c) χ m(l-y)c χ my(1-c) χ myc

Dieser Algorithmus besagt, daß der Cyan-Ausgang der gewertete Durchschnitt des Cyan-Wertes ist, der erzielt wird durch die Anfangsadresse und die Werte, die adressiert worden wären, wenn die Andressen-Bits in jeder Farbrichtung vergrößert worden wären, wobei die Bewertungsf.unktionen bestimmt werden durch die Dreifach-Produkte des geringen Bits. Wenn ein Punkt P in dem Mittelpunkt des Würfels gewählt wird, dann gibt der Algorithmus als Ausgang:

.../11

030062/0916

ORiGlMAL INSPECTED

" ¹¹ " 302U59

32 χ 1/2 χ 1/2 χ 1/2 + 32 " .... ·

+32 " " " + 32

+ 48 " "
= 4g(y=m=c= 1/2).

Dies ist gen-.¹! die richtige Antwort; sie liegt in der Mitte zwischen 32 und 48.

Der Schwarzdruck wird jedoch bestimmt durch das niedrigste der drei Farbsignale - es gibt einen großen Schwarzgehalt in neutralen Bereichen, jedoch wenig in den reinen Farben. Als ein vereinfachtes Beispiel sei der Fall angenommen, wo der Schwarzdruckwert gleich dem geringsten der drei Eingangsfarbsignale ist (in der Praxis würde eine kompliziertere Funktion benutzt werden). Für dies Beispiel würde bei dem Interpolatorwürfel der Fig. 2 der Schwarzgehalt in allen Ecken 32 betragen, abgesehen von der schwarzen Ecke, die 48 aufweisen würde.

Eine ähnliche Kalkulation für den Schwarzdruck mit den Tennen Schwarz _/v _M ,. etc. würde daher folgendes ergeben:

(7 χ 32 χ 1/8) + (1/8 χ 48) = 3j4.

030062/0916

.../12

Dies ist fehlerhaft, da der echte Wert wiederum 40 sein sollte. Dieser Fehler entsteht, weil der Algorithmus nicht in der Lage ist, die Nichtlinearität aufzulösen, die aufgrund der Tatsache entsteht, daß Schwarz auf der neutralen Achse entlang zunimmt, jedoch nicht längs den Farbrichtungen.

Der Einfachheit halber wurde bei der Darstellung des Schwarzdruckfehlers in dem oben gegebenen Beispiel ein linearer Matrixsuchtisch angenommen. Es ist zu beachten, daß in der Praxis derartige lineare Matrixsuchtische für Farbabtasterzwecke nicht vorkommen und daß infolge davon die durch die Interpolation für die Farbkomponenten Cyan, Magenta und Gelb erzielten Werte im allgemeinen auch unrichtig sind, und zwar infolge der Tatsache, daß der oben erwähnte Interpolationsalgorithmus linear arbeitet, während die von dem Suchtisch definierte Funktion eine Krümmung hat.

Es ist ersichtlich, daß in Interpolationsverfahren alle polynomischen Verfahren von einem Grad größer als eins unwirksam sind, wenn sie über einer Singularität benutzt werden, wie . beispielsweise der Liniensingularität längs der Schwärzweißdiagonale im Falle des oben erörterten Schwarzdrucks. Um dies zu berücksichtigen, ist es erforderlich, den Würfel ε^ zu unterteilen, daß die Schwarzweißdiagonale eine Kante des unterteilten Volumens ist.

.../13

030062/0916

302U59

Im Falle eines Rechteck ist vorgeschlagen worden, die Rechteckeinheit in Dreiecke zu unterteilen. Die Interpolation in Dreiecken is^J. diskutiert worden beispielsweise von R.H. Gallagher in "Finite Element Analysis Fundamentals", herausgegeben von Prentice-Hall, New Jersey, 1975. In dieser Veröffentlichung diskutiert der Autor zunächst Interpolationsverfahren für dreieckige Elemente und leitet Koordinatenwert'3 für einen Punkt innerhalb des Dreiecks ab, wobei jeder Koordinatenwert die Summe von drei Produkten ist und es sich bei jedem Produkt um die rechtwinkligen Koordinaten einer entsprechenden Ecke des Dreiecks und las Verhältnis der Fläche eines kleineren Dreiecks, das begrenzt ist durch die anderen beiden Ecken und den Punkt innerhalb des Dreieckes, zu der Fläche des Dreiecks als Ganzem handelt. Danach wird die Verwendung des Tetraeders, des dreidimensionalen Gegenstücks des planaren. Dreiecks, diskutiert, und es werden Volumenverhältnisse abgeleitet zum Ersatz der in dem Falle des Dreiecks benutzten Flächenverhältnisse.

Die vorliegende Erfindung besteht in einem Verfahren zur Reproduktion eines farbigen Originals, bei welchem das Original abgetastet wird, um Signale zu erlangen, welche drei Farbkomponentendichten aufeinanderfolgend abgetasteter Bildelemente des Originals darstellen, unü. bei welchem die genannten Signale vor ihrer Verwendung zur Steuerung der Behandlung einer Ausgangsoberfläciie korrigiert werden, wobei das Verfahren vor dem Abtaste;.! des Originals Schritte enthält zum Ableiten eines Satzes von vier korrigierten Farbkomponentonwerfcen in digitaler

030062/0916

.../14

302U59

Form, und zwar je einen für jede der drei Farbkomponenten und einen für Schwarz/ für jeden einer Anzahl Sätze von drei digitalen Eingangs farbkomponentenwerten, -lie in ihrer Anzahl geringer sind als die Sätze möglicher, von dem Abtaster verfügbarer digitaler Eingangsfarbkomponentenwerte, sowie zum Eingeben der Sätze von vier korrigierten digitalen Farbkomponentenwerten in die Speichersteilen eines dreidimensionalen Speichers, und anschließend die Schritte zum Bezugnehmen auf den Speicher gemäß einer Aufeinanderfolge von Sätzen von drei Farbkomponentensignalen, die vom Abtasten des Originals abgeleitet sind, um von dem Speicher eine Aufeinanderfolge korrigierter digitaler Werte zu erzielen, sowie zur Erlangung von Werten zwischen den Sätzen digitaler Werte, die für die Elementarwürfel innerhalb des dreidimensionalen Speichers gespeichert sind, durch On-Line-Interpolation, und zum anschließenden Steuern der Behandlung ■<■ der Ausgangsoberfläche gemäß den vier erzielten Werten; dadurch gekennzeichnet, daß jeder der vier Werte für einen Punkt innerhalb eines Interpolations-Elementarwürfsls des dreidimensionalen Farbraumes erzielt wird zunächst durch Bestimmen, in welcher der drei Pyramiden, die zusammen den Interpolations-Elementarwürfel bilden und als eine gemeinsame Kante die "neutrale Achse" des Interpolations-Elementarwürfels haben, der genannte Punkt enthalten ist und anschließendes Ableiten eines Wertes für den genannten Punkt durch Interpolation innerhalb der Pyramide.

Zum Interpolieren innerhalb der Pyramide wird vorzugsweise ein lineares Interpolationsverfahren mit einer "parallelen Ebene"

030062/0916

.-./15 BAD ORIGINAL

verwendet.

Die Bezeichnung "Würfel" wurde wegen J.hrer Kürze verwendet, soll jedoch jegliches rechteckige Interpolations-Elementar-Parallelepiped einschließen.

Der Ausdruck "neutrale Achse" bedeutet in seiner Verwendung in dieser Beschreibung die Achse zunehmender Schwärze. Somit schließt der Ausdruck "neutrale Achse" nicht nur die Schwarzweißachse für Interpolations-Elementarwürfel ein, die derart im Farbraum angeordnet sind, daß die t'chwarzwei-ßachse des Farbraums durch sie hindurchgeht, sondern auch die Achse parallel zu der Schwarzweißachse für Interpolations-Elementarwürfel, durch die die Schwarzweißachse nicht hindurchgeht. Es ist ersichtlich, daß obwohl ein Punkt auf der "neutralen Achse" in diesen letztgenannten Würfeln keinen Grauton darstellt, die Achse dennoch eine Achse zunehmender Schv/ärze ist.

Zum besseren Verständnis der Erfindung wird nunmehr unter Bezugnahme auf die beigefügten Zeichnungen ein Beispiel einer Farbreproduktionseinrichtung beschrieben, die die Erfindung verkörpert. Es zeigen:

Fig. 1 eine schematische Darstellung einer Vorrichtung und eines Steuerkreises zur Bildreproduktion,

Fig. 2 die Art, in welcher ein Elementarwürfel des dreidimensionalen Farbraums für Interpolationszwecke in Pyramiden unterteilt wird,

030062/0916 ""'^U

302U59

Fig.'3 ein Schema zur Erläuterung der Art, in welcher die Interpolation durchgeführt wird, und

Fig. 4 ein Schema zur Darstellung einer Alternative zu der Vorrichtung der Fig. 3.

In Fig. 1 ist ein zu reproduzierendes transparentes Original 1 um die Oberfläche einer transparenten Trommel 2 herumgewickelt, Eine Xenonlampe 3 richtet Lichtstrahlen in die Trommel hinein und auf einen 45 Spiegel 4, von dem aus die Strahlen durch die Wand der Trommel und durch das transparente Original 1 hindurchgehen. Diese Lichtstrahlen erreichen einen Analysierkopf 5, der Farbfilter und fotoelektrische Einrichtungen enthält, so daß auf den Leitungen 6, 7 bzw. 8 Signale erzeugt werden, die die rote, blaue und grüne Dichte des abgetasteten Elements des Bildes 1 darstellen. Da das Drucken in subtraktiven.Farben ausgeführt wird, sind die Leitungen 6, 7 und 8 als Teil der Cyan-, Gelb- und Magentafarbkanäle anzusehen. Der Analysierkopf 5 ist auf einer Leitspindel 9 gelagert, die synchron mit dem Umlauf der Trommel 2 durch einen Motor 10 angetrieben wird. Infolgedessen sieht der Analysierkopf einen Punkt auf der Trommel 2, welcher beim Umlauf der Trommel und der Lewegung des Analysierkopfes auf seiner Spindel entlang einem schneckenförmigen Pfad auf der Trommel 2 folgt und demzufolge eine Anzahl paralleler Abtastlinien auf dem Original 1 zieht.

030062/0916 .../17

Auf einer Trommel 12, die in diesem Fall einen größeren Durchmesser hat als die Trommel 2, ist ein lichtempfindlicher Bogen 11 zur Belichtung gelagert. Beide Trommeln sind auf einer Welle 13 gelagert, die von einem Motor 14 angetrieben wird. Der Motor treibt auch eine geschlitzte Scheibe 15 an, deren geschlitzter Umfang zwischen einer Lichtquelle 16 und einer fotoelektrischen Zelle 17 umläuft. Die von der fotoelek^rischen Zelle 17 abgenommenen Impulse werden auf eine Steuereinheit 18 übertragen, welche den Umlauf des Motors 10 steuert, der die Leitspindel für den Analysierkopf antreibt/und eines Motors 19, welcher eine Leitspindel 20 antreibt, auf welcher ein Belichtungskopf 21 gelagert ist. Der Belichtungskopf 21 enthält eine Lichtquelle, welche einem spiralförmigen Schema auf der Trommel 12 folgt und durch ein Signal auf einer Leitung 22 moduliert wird. Dies Signal wird von den Eingangssignalen auf den Leitungen 6, 7 und 8 in der folgenden Weise abgenommen.

Die Signale auf den Leitungen 6, 7 und 8 werden zunächst auf Analog-Digitalkonverter 23 übertragen, deren digitale Ausgänge an einen Digitalcomputer 24 und ebenso an einen Digitalspeicher und einen Interpolator 26 angeschlossen werden können. Der · Speicher 25 benutzt die drei digitalen Signale von den Konvervorn 23 als Adressensignale und bildet an seinem Ausgang vier Signale, die an dem durch diese Adresse dargestellten Ort gespeichert werden. Diese vier Signale sind die korrigierten Signale für Cyan, Gelb und Magenta, zusammen mit einem Schwarzsignal. Das Schwärζsignal ist annähernd gleich dem kleinsten

030062/0916 .../ie

der Farbsignale, und die Werte der Farbsignale, die von dem Speicher erlangt werden, werden gemäß dem Wert, des Schwarzsignals reduziert. Tatsächlich ist der Speicher 25 äquivalent zu vier Suchtischen, je einer für jede der drei Farbkomponenten und einer für Schwarz; jeder Suchtisch wird mit jedem der drei Eingangsfarbkomponentensignale adressiert.

In dem gezeigten Beispiel gestattet der Interpolator die Aufrechterhaltung der gewünschten Ausgangs-Eingangsbeziehung für feinere Wechsel in dem Signalpegel, als durch den Speicher 25 gestattet sein würde, was im folgenden beschrieben wird. Ein Kanalwähler 27 empfängt die vier Signale, welche die Cyan-, Gelb- und Magentadruckwerte und den Schwarzdruckwert darstellen, und wählt denjenigen aus, welcher der Trennung entspricht, die mit dem lichtempfindlichen Bogen 11 durchgeführt werden soll. pies Signal wird in dem Konverter 28 in die Analogform umgewandelt und dann zum Modulieren der Lichtquelle in dem Belichtungs kopf 21 benutzt.

Für das vorläufige Laden des Speichers mit der Matrix von Ausgangswerten ermöglicht ein Schaltbrett 29 die Einstellung von Parameterwerten gemäß den Charakteristika des Systems und den Charakteristika des zu reproduzierenden Originals. Diese Parameterwerte werden in den Digitalcomputer eingegeben, der so programmiert ist, daß er die erforderliche Ausgangs-Eingangsbeziehung liefert. Eine Anzeige 30 gestattet es, die Wirkung

030062/0916

,,./19

- 19 - 302U59

dieser Beziehung und die Wirkung der Parametereinstellung zu inspizieren, bevor die Matrix der Ausgangswerte durch .den Computer 24 kalkuliert und in den Speicher 25 eingegeben wird.

Zum Beispiel können die Parametersteuerungen benutzt werden, um den Tonausgleich einzustellen und etwa benötigte "redaktionelle" Farbveränderungen festzulegen. Das Programm des Digitalcomputers kann die Transparentfarbkorrektur in Betracht ziehen, sowie auch die Ableitung eines Schwarzdrucksignals und die daraus erfolgende Entfernung von "Unterfarbe" aus den Farbkomponer. "-.ensignalen, den Tintengraurest und die Druckcharakteristik .

Fig. 2 zeigt zwei "Interpolations-Elementarwürfel", in denen die Unterteilung in Pyramiden dargestellt ist. Die drei Pyramiden haben die Linie W-B oder die "neutrale Achse" gemeinsam, d.h. diese Linie ist eine Kante aller drei Pyramiden. In dem linken Würfel hat eine der drei Pyramiden die fünf Vertices W, S/ G, V und C, eine zweite hat die Vertices W, Y, R, B und G, und die dritte hat die Vertices W, M, R, B und V. Es Ast ersichtlich, daß jede dieser drei Pyramiden eine Grundfläche hat, bestehend aus einer vollständigen Fläche des Wurfeis,- und zwei Seiten, jeweils bestehend aus einer halben Fläche des Würfels. Auch sind die Cyan-, Gelb- und Magentaecken (d.h. jene iv-ken entsprechend den Druckfarben) alle in verschiedenen Pyramiden enthalten. In dem rechten Würfel ist die Unterteilung in drei Pyramiden so vorgenommen, daß der Schwarz-

030062/0916

vertex allen drei Pyramiden gemeinsam-ist,- und nicht .der. Weißvertex. Die Würfel des Speichers könnten in derselben Weise in Pyramiden unterteilt werden, so daß beispielsweise der Würfel links in Fig. 2 innerhalb des gesamten Speichers wiederholt würde. Jedoch wären die Kanten der Pyramiden verschiedener Würfel dann nicht an benachbarten Wurfelflachen ausgerichtet, obwohl die Ergebnisse aus diesem Interpolateionsverfahren befriedigend sind, können die Ergebnisse verbessert- werden, indem man sicherstellt, daß keine Kante irgendeiner Pyramide quer über eine Fläche einer anderen Pyramide liegt. Die Interpolation ist wirksamer, wenn die Pyramiden .benachbarter Wurf el dieselben Kanten teilen. Vcjlzugsweise werden die Würfel des Speichers im Wechsel entsprechend den linken und rechten Würfeln der Fig. .2 unterteilt. Somit wird jeder Würfel, der so unterteilt ist, daJB der Weißvertex den drei Pyramiden gemeinsam ist, von sechs Würfeln.des Typs umgeben, dessen Schwarsvertex den drei Pyramiden gemeinsam ist,, und umgekehrt. Alle Würfel einer gegebenen Art haben dieselbe Orientierung, wie in Fig- 2 gezeigt» Bei dieser Anordnung... sind die Kanten benachbarter Pyramiden einander angepaßt; beispielsweise ist.die Rotweißdiagonale in dem Würfel links in Fig. 2 der Schwärzcyandiagonale eines Würfels ähnlich dem. Würfel rechts in Fig. 2 angepaßt. Die folgende Beschreibung bezieht, sich auf dies bevorzugte Teilungssystem.

Bei Durchführung der Interpolation besteht der erste Schritt darin, die Pyramide zu wählen, in welcher der Punkt liegt, für

Q 3 0 0.6-2/Q 9.1.6

den die Interpolation benötigt wird. Pies ist abhängig von den "geringen Bits" (low bits) der Farbkanalsignale; die hohen Bits definieren den Interpolations-Elementarwürfel, in welchen der Punkt fällt-, und die geringen Bits definieren die Lage jenes Punktes innerhalb des gewählten Würfels. Für den Würfel links in Fig. 2 liegt dieser Punkt in einer der Pyramiden, je nachdem welches der Farbkanalsr'.gnale den höchsten Wert in seinen geringen Bits hat. Für den Würfel auf der rechten Seite, welcher in drei verschiedene Pyramiden unterteilt ist, liegt der Punkt in einer der Pyramiden, je nachdem, welches der Farbkanalsignale den geringsten Wert in seinen geringen Bits hat. Beispielsweise muß ein Punkt, an welchem die geringen Cyanbits den geringsten Wert haben, in der Pyramide liegen, deren Vertices W, B, R, Il und Y sind. Bei dem Würfel links in Fig. 2 ist, wenn der Cyankanal den höchsten Wert der "geringen Bits" hat, die gewählte Pyramide diejenige, die als ihre Vertices W, B, C, G und V hat. Wenn Magenta die höchsten geringen Bits hat, dann ist die gewählte Pyramide diejenige mit den Vertices W, B, R, M und V. Schließlich hat für-den Fall, in welchem der Gelbkanal ^tie höchsten geringen Bits hat, die gewählte Pyramide die Vertices W, B, G, Y und R.

Wenn 'lie geringen Bits aller drei Kanäle gleich sind, dann spielt es keine Rolle, welche Pyramide gewählt wird, da der Punkt auf der genieinsamen "neutralen Achse" liegt.

030062/0916

Ίη dem linken Würfel der Fig. 2 ist die gezeigte Pyramide diejenige, welche benutzt wird, wenn die geringen Bits des Cyan die höchsten sind. Für ein Interpolationsverfahren mit "paraT-leler Ebene" ist der Vorgang wie folgt: zunächst wird die viereckige Grundfläche BCCV der Pyramide auf die parallele Ebene B¹G¹C¹V projiziert, welche die Ebene für den Niedrig-Bit-Wert des Cyan ist_, und geht daher durch den Punkt hindurch, für den die Interpolation erforderlich ist.

Die Ausgangswerte an den Punkten B¹G¹C¹V werden erzielt durch lineare Interpolation längs den Linien WB¹B, WG'G und BVV bei Verwendung der Cyan-Niedrig-Bits:

B¹ = W (1 - c) + B.c (la)

G¹ = W (1 - c) + G.c (Ib)

C = W (1 - e) + Cc (Ic)

V = W (1 - c) + V.c (Id)

Die endgültige Antwort wird aus diesen vier Mittelwerten erzielt durch -zweidimensionale Interpolation innerhalb des Quadrats B¹G¹C¹V unter Verwendung der Gelb- und Magenta-Niedrig-Bits. Die Gelb- und Magenta-Niedrig-Bits müssen durch die Cyan-Niedrig-Bits .naßstäblich verändert werden, um den Punkten B¹G¹C¹V die richtigen Gewichte zu geben; die. maßstäblich ver-

.../23

030062/0916

änderten Werte sind

y■·' = - y/c
m¹ = m/c

Endgültiger Ausgang

= B' .	fr	•m¹)]	(2a)
+ G¹V	fr¹	(1-m·)]	(2b)
+ C¹ .	.[rs	-y·)(1-m·	(2c)
+ V.	[m'	U-y'jJ	(2d)

Figur 3 zeigt schematisch eine Ausführungsform der Vorrichtung zur praktischen Durchführung der Erfindung. In Fig. 3 werden die Bildsignalwerte in einen Block 40 mit einer Adressenwahllogik (addres arbritration logic) eingespeist, welcher auswählt , welche von den drei Pyramiden den Ihterpolationspunkt einschließt ,und somit feststellt, welche fünf Ecken des Würfels adressiert werden müssen. Der weiße Punkt wird immer adressiert und wird als erster von, dem Matrix-Speicher 42 erlangt. Der nächste Punkt, der von dem Matrix-Speieher erlangt wird, ist beispielsweise der Schwarzpunk-t. Die We"i.ß- und Sehwarzwerte W, B und das Cyan-LSB (am wenigsten bedeutendes Bit)- "./erden einer linearen eindimensionalen Interpolationseinheit 44 zugeführt, in welcher eine lineare Intelpolation zwischen' den Weiß- und Schwarzpunkten durchgeführt wird, unter Verwendung des Cyan LSB-Wertes (LSB =ara wenigsten bedeutendes Bit). Dies gibt die Zwischenantwort B' gemäß der Gleichung (Ia)^und B¹

030062/0916

.../24

wird dann in einem Pufferspeicher 46 gespeichert. Die Adressenwahllogik 40 bestimmt auch, welche zwei LSB-Werte benötigt werden für die folgende zweidimensionale Interpolation, in diesem Beispiel y und m, und führt diese dem Teilungs-ROM 48 zu. Die y und m-Werte müssen maßstäblich verändert werden durch Teilung durch den c-Wert; die resultierenden Werte y¹ und m¹ werden auf einen zweidimensicn.ilen Wertungsf^ktorkalkulator 50 übertragen, der an seinem Ausgang beispielsweise einen Wert y^lm' oder y¹ (1-m¹) liefert. Die Zwischenantwort B' wird dann auf einen Multiplier 52 übertragen, wo er durch den Wertungsfaktor (in diesem Fall y'm¹) gemäß der Gleichung (2a) multipliziert wird. Das Ergebnis dieser Multiplikation wird in einem Akkumulator 54 gespeichert.

Als nächstes wird beispielsweise der Grünpunkt erlangt und einer eindimensionalen und zweidimensionalen Interpolation gemäß.den Gleichungen (Ib) und (2b) unterworfen. Das Ergebnis wird dem Akkumulator hinzugefügt. Das Verfahren wird wiederholt für die Cyan- und Violetteckan, und das endgültige Ergebnis kann dann von dem Akkumulator abgenommen v/erden.

Als nächstes kann das gesamte Verfahren für Gelb-, Magenta- und Schwärzfarben wiederholt werden. Wahlweise kann es auch sein, daß nur eine oder zwei Farbteilungen erforderlich sind, in einem solchen Fall werden nur die korrigierten Farbkompo-

..,/25

Π 3 0062/0916

nentenwerte für jene Farben, die verlangt werden, aus dem Matrix-Speicher herausgezogen.

Die Aufeinanderfolge der Arbeitsgänge wird gesteuert durch eine Steuereinheit 56. Bei dem oben beschriebenen Verfahren werden bis zu vier korrigierte Farbkomponentenwerte aus dem Matrix-Speicher herausgezogen und nacheinander verarbeitet. Sie können jedoch in Sätzen von zwei oder mehr herausgezogen und parallel verarbeitet werden, beispielsweise durch Verwendung von zwei oder mehr Sätzen der Verarbeitungseinheiten der Figuren 3 und 4.

Fig. 4 zeigt eine wahlweise mögliche Ausführungsform der Vorrichtung gemäß der Erfindung. In Fig. 4 werden die Bildsignalwerte in eine Einheit 58 für Adressenwahl und Steuerlogik eingegeben, welche die Funktionen der in Fig. 3 mit 40 und 56 bezeichneten Einheiten durchführt. Der Matrixspeicher 42 ist adressierbar durch die Einheit 58 und speichert die fünf Werte an den Vertices der Pyramide, welche den Punkt entsprechend den Bildsignalwerten enthält. Für die Ableitung der maßstäblich veränderten Werte, beispielsweise y'm¹, wie oben beschrieben, ist eine Niedrig-Bit-Kalkulationseinheit 60 verantwortlich.

Die Multipli^reinheit 52 vervielfacht die Werte (z. B. B, W) von dem Matrixspeicher 42 mit maßstäblich, veränderten Werten von der Niedrig-Bic-Xalkuiationseinheit 60, und es werden

030062/0916

.../26

Zwischenergebnisse über eine Teilprodukteinheit 62 zu der Multiplieareinheit 52 zurückgeführt. Der endgültige Ausgangswert wird erzielt durch Anhäufen und Addieren der Produkte von der MultipIiereinheit 52, wie oben beschrieben.

Die Adressenwahllogikeinheit 40 oder die Adressenwahl- und Steuerlogikeinheit 58 tonnen durch das folgende Verfahren entscheiden/ welche Pyramide den Punkt enthält.

Wenn zwei miteinander abwechselnde Arten von Würfeln vorhanden sind, wie in Fig. 2 gezeigt, dann besteht die erste Aufgabe darin, festzustellen, welche Würfelart den Punkt enthält. Das viertwichtigste Bit jedes Kanalsignals wird in dieser Bestimmung verwendet. Die Koordinaten des bedeutendsten Bit benachbarter Würfel unterscheiden sich in diesem vierten Bit. Es ist zu beachten, daJ3 die Summe der viertbedeutendsten Bits aus den drei Farbkanalsignalen entweder ungerade oder gerade ist; dies bestimmt, welche Würfelart den durch die beiden Signale dargestellten Punkt enthält. Wenn beispielsweise die Summe der viertbedeutendsfen Bits gerade ist, dann endet sie mit einer "0", und es ist bestimmt, daß der Punkt sieh in einem Würfel der links in Fig. 2 gezeigten Art befindet.

Die nächste Aufgabe besteht im Vergleichen der Werte der am wenigsten bedeutenden 3its der Farbkanalsignale. Für den linken Würfel liegt der Punkt stets in der Pyramide, welche

0 30 0 62 /09 1 6

.../27

~ ²⁷ "

als einen ihrer Vertices die Farbe mit dem höchsten Wert in den am wenigsten.bedeutenden Bits aufweist. Für den rechten Würfel liegt der Punkt stets in der Pyramide, die nicht als einen ihrer Vertices die Farbe mit dem geringsteh Wert in den am wenigsten bedeutenden Bits aufweist.

030062/0916

Claims

Ansprüche :

.} Verfahren zur Reproduktion eines farbigen Originals, bei welchem das Original abgetastet wird, um Signale zu erhalten, welche drei Farbkomponentendichten nacheinander abgetasteter Bildelemente des Originals darstellen, und bei welchem diese Signale vor ihrer Verwendung zur Steuerung der Behandlung einer Ausgangsoberfläche korrigiert werden, und wobei dieses Verfahren vor dem Abtasten des Originals die folgenden Schritte beinhaltet: Ableiten eines Satzes von vier korrigierten Farbkomponenten-Werten in digitaler Form, und zwar je einen für die drei Farbkomponenten und einen für Sch.Wa.rz, für jeden einer Anzahl Sätze von drei digitalen Eingangs-Farbkomponentenwerten in geringer Anzahl als die Sätze möglicher, von dem Ab-

030062/0916

. HANvc Aa, lUM

ZUGELASSENE VlSttTIliäTEi· JlJiIM IIUJiOV/USCHBN PATENTAMT

. MKI¹BKSiXTATH EH HKl-OHi: TIIK iCBOl'MAX ΓΛΤΚΧΤ Oi¹PICE

ORIGINAL INSPECTED

taster verfügbarer digitaler Eingangsfarbkomponenten-Werte, und Eingeben der Sätze von vier korrigierten digitalen Farbkomponenten-Werten in die Speicherstellen eines dreidimensionalen Speichers; sowie anschließend die Schritte der Bezugnahme auf den Speicher gemäß der Aufeinanderfolge von Sätzen von drei von der Abtastung des Originals abgeleiteten Farbkomponetnen-Signalen, um von dem fpeicher einer Aufeinanderfolge korrigierter digitaler Werte zu erhalten, sowie der Erlangung von Werten zwischen den Sätzen digitaler Werte, die für Elementwürfel innerhalb des dreidimensionalen Speichers gespeichert sind, durch On-line-Interpolation, und der anschließenden Steuerung der Behandlung der Ausgangsoberfläche gemäß den vier erzielten Werten, dadurch gekennzeichent, daß jeder der vier Werte für einen Funkt innerhalb eines Interpolations-Einheitsxvürfels des dreidimensionalen Farbraums erzielt wird zunächst durch Bestimmen, in welcher der drei Pyramiden , die zusammen den Interpolations-Einheitswürfel bilden und als eine gemeinsame Kante die "neutrale Achse" des Interpolations-Einheitswürfeis haben, der genannte Punkt enthalten ist, und dann Ableiten eines Wertes für den genannten Punkt durch Interpolation innerhalb der Pyramide,
2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Elementar- oder Einheitswürfel in drei Pyramiden mit je einer¹ Vertex an der "weißen" Ecke oder jeweils an der "schwarzen" Ecke unterbeut sind, wobei jeweils zwei benachbarte Würfel

030062/0916

auf diese zwei verschiedenen Weisen unterteilt sind, so daß keine Kante irgendeiner Pyramide quer über eine Fläche einer anderen Pyramide liegt.
3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß der interpolierte Wert erzielt wird zunächst durch Ermitteln interpolierter Werte ^Jr die Ecken euer Ebene, die die Pyramide überschneidet und parallel zu ihrer Grundfläche verläuft und den erwünschten Punkt enthält,und anschließendes Interpolieren innerhalb der genannten Ebene zur Erlangung eines Wertes für den genannten Punkt.
4. Vorrichtung zur Reproduktion eines farbigen Originals, mit einem Äbtaster zum Analysieren des Originals zur Erlangung von drei Signalen, welche drei Farbkomponenten-Dichten nacheinander abgetasteter Bildelemente darstellen, einem analog · zu Dxgitalkonverter, einem Digitalspeicher zur Speicherung eines Satzes von Werten für jeden einer Anzahl Sätze von drei digitalen Farbkomponenten-Werten, der korrigierte Werte für die drei Farbkomponenten und einen Schwarzdruckwert enthält, wobei die genarnte Anzahl geringer ist als die Anzahl Digitalwerte, welche von dem Konverter gexiefert werden kann, sowie Einrichtungen, die betätigt v/erden können, um gemäß der Aufeinanderfolge von Sätzen von drei

030062/0916

durch den Abtaster von dem Original abgeleiteten Farbkomponenten-Signalen auf den Speicher Bezug zu nehmen, um von dem Speicher eine Aufeinanderfolge von Signalwerten zur Steuerung der Einrichtungen zur Behandlung der Ausgangsfläche zu erlangen, sowie einem Interpolator, der gemäß den von dem Abtaster erlangten Signalen im On-line-Betrieb arbeitet, um Sätze korrigierter Farbkomponenten-Werte zwischen den Sätzen gespeicherter Digitalwerte zu liefern, dadurch gekennzeichnet, daß die Interpolationseinheit Einrichtungen enthält, welche bestimmen, ^_{n wo}i_ch_er der drei Pyramiden, die einen Interpolations-Elementarwürfel in einem dreidimensionalen FarL raum bilden, der erwünschte Punkt .enthalten ist, sov/ie Einrichtungen zum Interpolieren innerhalb der Pyramide zur Erlangung eines Wertes für den erwünschten Punkt.
5. Vorrichtung nach Anspruch 4, dadurch gekennzeichnet, daß die Interpolationseinhe.it die Elementarv/ürfel in drei Pyramiden unterteilt, jeweils mit einem Vertex an der "weißen" Ecke oder jeweils an der "schwarzen" Ecke, wobei jegliche zwei benachbarte Würfel auf diese zwei verschiedenen Weisen unterteilt sind, so daß keine Kante irgendeiner Pyramide quer über οine Fläche einer anderen Pyramide liegt.
6. Vorrichtung nach Anspruch 4 oder 5, dadurch gekennzeichnet, daß die Interpolatiimseinlieit Einrichtungen zur Erlangung interpolierter Werte für ;jedo üor vier Ecken einer Ebene

030062/0916 ..,_/5

BAD ORfGINAL

enthält, die parallel zur Grundfläche der gewählten Pyramide verläuft und den erwünschten Punkt enthält, sowie Einrichtungen zum Interpolieren linear innerhalb der genannten Ebene zur Erlangung eines Wertes für den erwünschten Punkt.

03 0 0 62/0916