DE69522158T2

DE69522158T2 - Skalierung von Binärbildern

Info

Publication number: DE69522158T2
Application number: DE69522158T
Authority: DE
Inventors: Jonathan Yen
Original assignee: Hewlett Packard Co
Current assignee: Aptina Imaging Corp
Priority date: 1994-08-05
Filing date: 1995-06-20
Publication date: 2001-11-29
Anticipated expiration: 2015-06-21
Also published as: JPH0863592A; EP0696017A3; EP0696017B1; US5627953A; EP0696017A2; DE69522158D1

Description

Die vorliegende Erfindung bezieht sich auf die Skalierung von binären Bildern durch eine stückweise Polynominterpolation.
Beim Skalieren eines binären Bildes ist es notwendig, die Diskrepanz der Eingangsauflösung und der Ausgangsauflösung zu überwinden. Bei der Fax-Bilderzeugung werden die Originalbilder beispielsweise mit einer Standardauflösung übertragen, die typischerweise 203 Punkte pro Zoll ("dpi"; dpi = dots per inch) in der Zeilenrichtung und 98 dpi in der Spaltenrichtung beträgt und mit einer Druckerauflösung gedruckt, die beispielsweise 300 dpi in sowohl der Zeilen- als auch der Spaltenrichtung beträgt. Ein weiteres Beispiel einer binären Bilderzeugung umfaßt die Schriftartskalierung, bei der beispielsweise, wenn eine 12-Punkt-Schriftart mit 300 dpi als eine 24-Punkt-Schriftart verwendet und auf einem 600-dpi-Drucker ausgedruckt werden soll, das Originalbild um einen Faktor von 4 skaliert werden muß. Folglich kann der Skalierungsfaktor eine Ganzzahl oder eine Bruchzahl sein.
Ein Lösungsansatz für die Bildskalierung besteht darin, die stückweise Polynominterpolation anzuwenden, wie z. B. Bsplines, wie sie in R. V. Klassen, R. H. Bartels, Using Bsplines for Re-Sizing Images, University of Waterloo, Department of Computer Science, Technical Report, 1986, vorgeschlagen werden. Ein solcher Lösungsansatz hat sich jedoch nicht als zufriedenstellend erwiesen.
Von einem Quantisierungsfehlerproblem, das in allen stückweisen Polynominterpolationsmitteln zum Skalieren umfaßt ist, wird in I. E. Abdou und K. Y. Wong, Analysis of hinear Interpolation Schemes for Bi-Level Image Applications, IBM J. Res. Develop., Bd. 26, Nr. 6, S. 667-680, November 1982, berichtet. Folglich geben Interpolationsschemata Anlaß zu einem Quantisierungsfehlerproblem, wie z. B. demjenigen, daß die Bildstrichbreite nach der Bildskalierung nicht bewahrt wird.
Weitere bekannte Lösungsansätze zum Skalieren und Glätten von Bildern umfassen die Pixelreplikation, die Konturführung (siehe W. Rutkowski, Shape Completion, Computer Graphics and Image Processing, Bd. 9, S. 89-101, 1979), die kubische B-Spline-Interpolation (siehe H. S. Hou, H. C. Andrews, Cubic Splines for Image Interpolation and Digital Filtering, IEEE Transaction an Acoustic, Speech and Signal Processing, Bd. ASSP-26, S. 508-517), die schablonenbasierte Skalierung (siehe R. A. Ulichney, D. E. Troxel, Scaling Binary Images with the Telescoping Template, IEEE Transactions an Pattern Analysis and Machine Intelligence, Bd. PAMI-4, Nr. 3, S. 331-335, 1982), und die Extrapolationsvorhersage (siehe C. Tung, Resolution Enhancement Technology in Hewlett Packard LaserJet Printers, IST/SPIE Symposium on Electronic Imaging: Science and Technology, S. 440-448, 1993).
Die vorliegende Erfindung schafft eine verbesserte Bildskalierung.
Gemäß einem Aspekt der vorliegenden Erfindung wird ein Verfahren zur binären Bildskalierung geschaffen, wie es in Patentanspruch 1 spezifiziert ist.
Gemäß einem weiteren Aspekt der vorliegenden Erfindung wird eine Skalierungsvorrichtung geschaffen, wie sie in Anspruch 11 spezifiziert ist.
Die erste und die zweite Koordinate sind vorzugsweise die X- und Y-Koordinate, während die dritte Koordinate die Z- Koordinate ist. Mit dem bevorzugten Ausführungsbeispiel ist es möglich, ein zufriedenstellendes und flexibles Schema zur binären Bildskalierung zu schaffen, das auf einer automatischen numerischen Berechnung basiert und das allgemein genug für alle Ganzzahl- und Bruchzahlskalierungsfaktoren ist, während Quantisierungsprobleme, die typischerweise bei herkömmlichen Lösungsansätzen, die die stückweise Polynominterpolation verwenden, auftreten, vermieden werden.
Das beschriebene Ausführungsbeispiel basiert auf einem stückweisen Polynominterpolationsschema. Das Schema sieht Bilder als dreidimensionale Daten an, bei denen die X- und Y-Koordiante die Eingangsbilddimensionen sind, während die Z-Koordinate, d. h. das Höhenfeld, die Intensität des Originalbildes ist. Der dreidimensionale Datensatz wird durch eine Oberfläche angepaßt. Ein Neuabtastungsprozeß an dieser Anpassungsoberfläche liefert Interpolationsdaten. Der Schwellenwertverarbeitungsprozeß, der auf diese Interpolationsdaten angewendet wird, erzeugt ein Ausgangssignal, d. h. ein binäres Endbild. Basierend auf dem Interpolationsschema ist jedes Ausgangspixel ein Ergebnis des Vermischens seiner benachbarten Eingangspixel, d. h. es ist ein gewichteter Mittelwert, wobei die Gewichtungen durch den Interpolationsmitteltyp, dessen Grad und den Skalierungsfaktor bestimmt sind. Für feste Skalierungsfaktoren können die Gewichtungen vorberechnet werden, und die Faltung kann durch eine Nachschlagtabelle durchgeführt werden.
Ein Ausführungsbeispiel der vorliegenden Erfindung wird im folgenden lediglich exemplarisch bezugnehmend auf die beiliegenden Zeichnungen beschrieben, bei denen:
Fig. 1 ein Flußdiagramm ist, das ein exemplarisches Ausführungsbeispiel eines Prozeßweges zeigt;
Fig. 2 ein Testzeichen in einer 20-Punkt-300-dpi-Times- Schriftart ist;
Fig. 3 eine Drahtgestelldarstellung der Eingangskoeffizienten für das Testzeichen von Fig. 2 ist;
Fig. 4 eine Bilineares-Tensorprodukt-B-Spline-Oberfläche ist, die durch die Eingangsdaten des Testzeichens von Fig. 2 definiert ist;
Fig. 5 eine Biquadratisches-Tensorprodukt-B-Spline-Oberfläche zeigt, die durch die Eingangsdaten des Testzeichens von Fig. 2 definiert ist;
Fig. 6 eine Bikubisches-Tensorprodukt-B-Spline-Oberfläche zeigt, die durch die Eingangsdaten des Testzefchens von Fig. 2 definiert ist;
Fig. 7 eine bilineare Interpolation des Testzeichens von Fig. 2 zeigt;
Fig. 8 eine biquadratische Interpolation des Testzeichens von Fig. 2 zeigt;
Fig. 9 eine bikubische Interpolation des Testzeichens von Fig. 2 zeigt;
Fig. 10 einen Darunter- bzw- Unterquantisierungsfehler zeigt;
Fig. 11 einen Darüber- bzw- Überquantisierungsfehler zeigt;
Fig. 12 die Impulsantwort eines kubischen B-Splines zeigt;
Fig. 13 die Impulsantwortfunktion eines kubischen B- Splines zeigt, das bei 0, 1/3 und 2/3 abgetastet wird;
Fig. 14 die Impulsantwort eines quadratischen B-Splines zeigt;
Fig. 15 die Impulsantwortfunktion eines quadratischen B- Splines zeigt, das bei 0, 1/3 und 2/3 abgetastet wird;
Fig. 16 eine Phasenverschiebung um ein Halb der Beabstandung während der Abtastung zeigt, um eine Phasenstörung zu kompensieren;
Fig. 17 ein Bild zeigt, das sich aus der Phasenverschiebung von Fig. 16 ergibt;
Fig. 18 die Impulsantwort eines quadratischen B-Spline- Interpolationsmittels nach der Abtastung bei 0 und 1/2 zeigt;
Fig. 19 die Impulsantwort einer kubischen B-Spline- Interpolationsmittels nach der Abtastung bei 0 und 1/2 zeigt;
Fig. 20 einen Quantisierungsfehler für ein biquadratische B-Spline-Interpolationsmittel nach der Abtastung bei 0 und 1/2 zeigt, wie es in Fig. 18 gezeigt ist;
Fig. 21 einen Quantisierungsfehler für ein bikubisches B- Spline-Interpolationsmittel nach der Abtastung bei 0 und 1/2 zeigt, wie es in Fig. 19 gezeigt ist;
Fig. 22 die Impulsantwort eines quadratischen Beta- Splines zeigt;
Fig. 23 ein Bild zeigt, das sich aus einer Interpolation durch ein biquadratisches Beta-Spline ergibt;
Fig. 24 die Impulsantwort eines kubischen Beta-Splines zeigt;
Fig. 25 ein Bild zeigt, das sich aus einer Interpolation durch ein bikubisches Beta-Spline ergibt;
Fig. 26 ein Bild zeigt, das sich aus einer Interpolation durch ein verschobenes biquadratisches B-Spline ergibt;
Fig. 27 ein Bild zeigt, das sich aus einer Interpolation durch ein verschobenes bikubisches B-Spline ergibt;
Fig. 28 einen Abschnitt eines Slerexe-Zeichensatzes in einer Standardauflösung zeigt;
Fig. 29 einen Abschnitt eines Slerexe-Zeichensatzes in einer feinen Auflösung zeigt;
Fig. 30 ein Zeichen zeigt, das aus einem Slerexe- Zeichensatzes herausgeschnitten ist;
Fig. 31 ein Bild zeigt, das sich aus einer Anwendung einer bikubischen B-Spline-Oberfläche als ein Interpolationsmittel zum horizontalen und vertikalen Skalieren um einen Faktor von 3,0 bei einer feinen Auflösung ergibt;
Fig. 32 das Ergebnis des Anwendens einer Quadratmal- Quartik-Tensorprodukt-B-Spline-Oberfläche als ein Interpolationsmittel zum horizontalen Skalieren um einen Faktor 3,0 und vertikalen Skalieren um einen Faktor von 1,5 bei einer Standardauflösung zeigt;
Fig. 33 ein Testzeichen in der ursprünglichen 12-Punkt- Schriftart bei 300 dpi zeigt;
Fig. 34 das Testzeichen von Fig. 33 zeigt, das zweimal durch die RET skaliert ist; und
Fig. 35 das Testzeichen von Fig. 33 zeigt, das durch biseptimale B-Splines skaliert ist.
Das exemplarische Ausführungsbeispiel basiert auf einem stückweisen Polynominterpolationsschema (siehe J. Yen, Binary Image Scaling by Piecewise Polynomial Interpolation, HPL Technical Report, März 1994). Es wendet im Gegensatz zu herkömmlichen Konturführungsschemata einen oberflächenbasierten Lösungsansatz auf die Bildskalierung an.
Die Bildskalierung, die hierin beschrieben wird, ist nicht auf kubische Transformationen begrenzt, wie sie in H. S. Hou, H. C. Andrews, Cubic Splines for Image Interpolation and Digital Filtering, IEEE Transaction an Acoustic, Speech and Signal Processing, Bd. ASSP-26, S. 508-517, beschrieben ist. Das exemplarische Ausführungsbeispiel teilt jedoch manche Merkmale mit den schablonenbasierten Lösungsansätzen aus R. A. Ulichney, D. E. Troxel, Scaling Binary Images with the Telescoping Template, IEEE Transactions on Pattern Analysis and Machine Intelligence, Bd. PAMI-4, Nr. 3, S. 331- 335, 1982; und C. Tung, Resolution Enhancement Technology in Hewlett Packard LaserJet Printers, IST/SPIE Symposium on Electronic Imaging: Science and Technology, S. 440-448, 1993. Dasselbe unterscheidet sich jedoch von solchen herkömmlichen Lösungsansätzen, da dasselbe Schablonen mathematisch aus der Oberflächengeometrie und nicht durch Interpretation oder Extrapolation durch Analyse jedes einzelnen Falles herleitet. Folglich können die Schablonen hierin für eine Druckqualitätssteuerung numerisch fein abgestimmt werden, wie es erforderlich sein kann oder wie sie mit verschiedenen ausgewählten Entwurfsparametern konsistent bzw. verträglich sind.
Fig. 1 ist ein Flußdiagramm, das einen Prozeßweg für ein exemplarisches Ausführungsbeispiel zeigt, das ein Schema liefert, das binäre Bilder als dreidimensionale Daten handhabt, bei denen die X- und Y-Koordinate die Dimensionen des Eingangsbilds (110) sind, während die Z-Koordinate, d. h. das Höhenfeld, die Intensität des Originalbilds ist. Dieser dreidimensionale Datensatz wird durch eine Oberfläche (120) angepaßt. Ein Neuabtastungsprozeß (130) bezüglich der Anpassungsoberfläche liefert Interpolationsdaten. Ein Schwellenwertverarbeitungsprozeß (140) wird auf die Interpolationsdaten angewendet, um ein binäres Ausgangsbild (150) zu erzeugen. Basierend auf diesem Interpolationsschema ist jedes Ausgangspixel ein Ergebnis einer Vermischung seiner benachbarten Eingangspixel, d. h. jedes Ausgangspixel ist ein gewichteter Mittelwert seiner benachbarten Pixel, wobei die Gewichtungen durch den Typ des Interpolationsmittels, den Grad desselben und durch den gewünschten Skalierungsfaktor bestimmt sind. Bei einem Ausführungsbeispiel können die Gewichtungen für feste Skalierungsfaktoren vorberechnet werden, derart, daß die Faltung durch eine Nachschlagtabelle durchgeführt werden kann.

Ein Interpolationsverfahren.

Das exemplarische Ausführungsbeispiel liefert ein Schema, das eine stückweise Polynominterpolation, wie z. B. B- Splines, als das Anpassungsinterpolationsmittel bezüglich der ursprünglichen Daten verwendet (siehe W. J. Gordon und R. F. Riesenfeld, B-Spline Curves and Surfaces in R. E. Barnhill und R. F. Riesenfeld (eds.), Computer Aided Geometric Design, Academic Press, New York, 1974, S. 95-126).
Eine Kurve
γ(t) = Bi,k(t)pi (1)
ist eine gleichmäßige Polynom-B-Spline-Kurve bei einem Parameter t (0, 1), wobei Bi,k (t) die Spline-Basis der Ordnung k (Grad k-1) ist und pi die Eingangskoeffizienten sind. In Produktform ergibt sich
γ(t) = BP (2)
wobei
B = [B0,k(t) B1,k(t) ... Bk-1,k(t)] (3)
und
P = [p&sub0; p&sub1; ... pk-1] (4)

Beispiel 1

Eine kubische gleichmäßige Polynom-B-Spline-Kurve, d. h.
γ(t) = [B0,4(t) B1,4(t) B2,4(t) B3,4(t)] [p&sub0; p&sub1; p&sub2; p&sub3;]T, (5)
ist ein inneres Produkt aus vier Eingangskoeffizienten pi und der kubischen Spline-Basis Bi,4(t), das an t zwischen [0, 1) ausgewertet wird.

Marsden-Identität.

Es kann bewiesen werden (siehe L. Schumaker, Spline Functions: Basic Theory, Wiley, New York, 1981), daß für jede Spline-Basis der Ordnung k mit
B = [B0,k(t) B1,k(t) ... Bk-1,k(t)] (6)
eine Basisübersetzungsmatrix (k mal k)Mk existiert, derart, daß
B = TMk (7)
gilt, wobei Tk die Potenzbasis
[tk-1 tk-2 ... t 1] (8)
ist. Da γ(t) = BP gilt, gilt folglich
γ(t) = TMkP. (9)

Beispiel 2

Seien die Eingangskoeffizienten p&sub0;, p&sub1;, p&sub2; und p&sub3; gegeben, so ist eine kubische gleichmäßige Polynom-B-Spline-Kurve t als
γ(t) = [t³ t² t 1] M&sub4; [p&sub0; p&sub1; p&sub2; p&sub3;], t&epsi;[0, 1) (10)
definiert, wobei die Basisübersetzungsmatrix
ist (siehe J. 0. Foley, A. von Dam, S. K. Feiner, J. F. Hughes, Computer Graphics, Principles and Practice, Second Edition, Addison Wesley, 1990).
Die Basisübersetzungsmatrizen für andere Grade, von linear bis septimal, werden im folgenden beschrieben. Viel mehr als k Ordnungseingangskoeffizienten definieren alle k aufeinanderfolgenden Koeffizienten ein Stück des Kurvensegments, derart, daß die gesamte Kurve aus diesen Kurvensegmenten besteht und folglich als eine stückweise B-Spline- Kurve bezeichnet wird. Für eine stückweise gleichförmige Polynom-B-Spline-Kurve werden alle Kurvensegmente glatt verbunden, d. h. mit einer Ck-1-Kontinuität an den Segmentverbindungsstellen.

Eine Oberfläche

s(u,ν) = Bi,ku Aj,kv(ν)pi,j (12)
ist eine gleichförmige Polynom-B-Spline-Tensorprodukt-Oberfläche bei den Parametern u [0,1) und v [0,1), wobei
die B's die Spline-Basis der Ordnung ku in der Richtung U bilden;
die A's die Spline-Basis der Ordnung kv in der Richtung V bilden; und
die Pi,j's die zweidimensionalen Eingangskoeffizienten sind.
Folglich gilt s(u,v) = BPAT, ähnlich zu dem Kurvenfall, A = UMku, A = VMkv und AT = MTkvVT, wobei U die Potenzbasis in u ist, V die Potenzbasis in v ist und die M's die Basisübersetzungsmatrizen sind.
Folglich gilt
s(u,ν) = UMkuPM VT (13)

Beispiel 3

Eine bikubische gleichmäßige Polynom-B-Spline-Tensorprodukt-Oberfläche
s(u,ν) = UM&sub4;PM VT (14)
wobei M&sub4; die Basisübersetzungsmatrix der Ordnung 4 ist, wie sie im vorhergehenden bei dem Beispiel 2 gezeigt wurde.

Beispiel 4

Fig. 2 zeigt ein Testzeichen in einer 20-Punkt-300-dpi- Times-Schriftart. Fig. 3 ist eine Drahtgestelldarstellung der Eingangskoeffizienten für das Testzeichen von Fig. 2.
Fig. 4 zeigt eine Bilineares-Tensorprodukt-B-Spline-Oberfläche, die durch die Eingangsdaten des Testzeichens von Fig. 2 definiert ist; Fig. 5 zeigt eine Biquadratisches- Tensorprodukt-B-Spline-Oberfläche, die durch die Eingangsdaten des Testzeichens von Fig. 2 definiert ist; und Fig. 6 zeigt eine Bikubisches-Tensorprodukt-B-Spline-Oberfläche, die durch die Eingangsdaten des Testzeichens von Fig. 2 definiert ist.
Fig. 7 zeigt eine bilineare Interpolation des Testzeichens von Fig. 2; Fig. 8 zeigt eine biquadratische Interpolation des Testzeichens von Fig. 2; und Fig. 9 zeigt eine bikubische Interpolation des Testzeichens von Fig. 2. Bei jedem der im vorhergehenden erwähnten Figuren ist der Buchstabe "W" als eine Reihe von Schritten gezeigt, bei denen der untere rechte Buchstabe fehlende Abschnitte des Buchstabens nach der Skalierung, die durch kleine gefüllte Quadrate angezeigt sind, und hinzugefügte Abschnitte des Buchstabens nach der Skalierung umfaßt, die durch kleine leere Quadrate angezeigt sind. Es wird darauf hingewiesen, daß das Ergebnis der bilinearen Interpolation blockförmig erscheint, während die Ergebnisse einer Interpolation höherer Ordnung normalerweise glatter erscheinen.

B-Splines als Faltungskerne.

Sobald die Ordnung der Interpolationsoberfläche festgelegt ist, wertet der Neuabtastungsprozeß bezüglich der Anpassungsoberfläche die stückweise Polynomoberfläche an einem Satz von geeigneten Positionen Stück für Stück aus.
Zum Skalieren um einen Faktor von M in der U-Richtung werden die Auswertejoositionen in der U-Richtung zwischen [0,1) mit einer regelmäßigen Beabstandung von üblicherweise
0, 1/M, 2/M, ..., M - 1/M
ausgewählt.
Zum Skalieren um einen Faktor von N in der V-Richtung werden die Auswertepositionen in der V-Richtung zwischen [0,1) mit einer regelmäßigen Beabstandung von üblicherweise
0, 1/N, 2/N, ..., N - 1/N
ausgewählt.
Da jedes Stück der Oberfläche durch die ku mal kv aufeinanderfolgenden Eingangskoeffizienten definiert ist, umfaßt die Neuabtastung die Auswertung von
s(u, v) = UM&sub4;PM VT; u = 0, 1/M, 2/M, ... M - 1/M; ν = 0, 1/N, 2/N, ..., N - 1/N, (15)
Für jedes bekannte (u&sub0;, v&sub0;)-Paar kann UMku und MTkvVT als Vek,toren ξ bzw. φ vorab berechnet werden. Eine ku-mal-kv- Matrix, die als die Kernmatrix bezeichnet wird, kann durch Multiplizieren von ξ und ø aufgebaut werden, d. h. mit
Kij = ξiφj (16)
Die Koeffizientenmatrix P ist ebenfalls ku mal kv groß. Die Summe des Eintrag-mal-Eintrag-Produkts von P und K ist das Ergebnis der Oberfläche, ausgewertet an u&sub0; und v&sub0;, d. h.
s(u&sub0;, v&sub0;) = Pij Kij. (17)
Die Kernmatrix wird für jedes (u, v)-Paar aufgebaut.
Schließlich wird ein Schwellenwert ausgewählt, um mit den numerischen Werten s(u,v) verglichen zu werden, um die binären Daten der Ausgangspixel zu erhalten.

Beispiel 5

Um ein Bild mit einer bikubischen gleichmäßigen stückweisen B-Spline-Tensorprodukt-Oberfläche s(u,v) für alle 4-mal-4- Eingangspixel, wie z. B.
um einen Faktor von 3 zu skalieren, wird für alle der folgenden 3-mal-3-Ausgangspixel eine Kernmatrix berechnet:
Für die obere linke Ecke der neun Ausgangspixel s(u&sub0;, v&sub0;), wobei u&sub0; = 0,0 und v&sub0; = 0,0, gilt beispielsweise U = [u³ u² u 1, 0] = [0,0 0,0 0,0 1,0] und
Folglich gilt
Dementsprechend gilt
und
Die Kernmatrix für s(0,0; 0,0) kann durch Multiplizieren der Einträge von (UM) mit (MTVT) berechnet werden, d. h.
Schließlich ist die Summe des Eintrag-mit-Eintrag-Produkts von P und K, d. h.
s(0,0; 0,0) = PijKij = 5/18, (25)
ein numerischer Wert, der den Punkt auf der Oberfläche nach der Neuabtastung darstellt. Der Endquantisierungsschritt vergleicht diese numerischen Wert mit einem vorausgewählten Schwellenwert, um einen binären Wert zu erzeugen, der die obere linke Ecke des binären Ausgangsbilds darstellt.
Die Kerne für die anderen s(u,v)'s werden im folgenden aufgelistet.

B-Spline-Charakteristika.

Es gibt viele vorteilhafte mathematische Charakteristika von B-Splines. Einige der Vorteile des Verwendens von B- Splines als Interpolationsmittel für eine binäre Bildskalierung werden im folgenden aufgelistet:
Continuum. Die Anpassungsoberfläche, d. h. eine B-Spline- Oberfläche, ist ein Continuum, das die gesamten Eingangsdaten abdeckt. Dementsprechend erzeugt der Neuabtastungsprozeß immer zumindest einige Punkte auf der Oberfläche ungeachtet der Wahlfreiheit der Skalierungsfaktoren. Folglich ist das Interpolationsverfahren auf jeden wahlfreien Skalierungsfaktor anwendbar.
Konvexhülleneigenschaft. Eine B-Spline-Tensorproduktoberfläche ist immer in der konvexen Hülle enthalten, die durch ihr Eingangsdatengitternetz gebildet wird. Folglich sind alle Ausgangsdaten, die aus dem Neuabtastungsprozeß erzeugt werden, durch die Eingangsdaten begrenzt.
Kontinuität. Eine B-Spline-Tensorproduktoberfläche ist in jeder parametrischen Richtung Ck-1-stetig, wobei k die Ordnung ist. Folglich sind die interpolierten Daten glatt. Falls ein Interpolationsmittel höherer Ordnung verwendet wird, sind die Kanten des Ausgangsbildes glatter.
Lokalheit. Jeder Punkt auf der B-Spline-Tensorproduktoberfläche hängt lediglich von einer endlichen Anzahl von Eingangsdatenpunkten ku mal kv ab, wobei die k' s die Ordnungen der Oberfläche sind. Folglich beträgt die Faltungskerngröße jedes Ausgangspixels nicht mehr als ku mal kv.
Trennbarkeit. Der Oberflächenauswertungsprozeß einer B- Spline-Tensorproduktoberfläche kann von einer parametrischen Richtung zu der anderen vollständig unabhängig sein. Dementsprechend funktioniert das Interpolationsschema für unterschiedliche Skalierungsfaktoren in den zwei orthogonalen Richtungen. Zusätzlich ist die Ordnung der einen Richtung vollständig unabhängig von der Ordnung der anderen Richtung. Folglich kann die Auswahl der Interpolationsmittelordnungen so wahlfrei wie erforderlich sein.
Symmetrie. Alle B-Spline-Basisfunktionen sind symmetrisch und ihre Impulsantwortfunktionen sind ebenfalls symmetrisch.

Rechenkomplexität.

Die Komplexität des Schemas, das hierin beschrieben wird, ist linear bezüglich der Eingangsgröße, da dasselbe eine feste Anzahl von Operationen pro Pixel aufweist. Das Schema kann als eine konstante Filterung mit einem Satz von ku- mal-kv-Faltungskernen betrachtet werden, wobei die k's die Ordnungen, d. h. die Grade plus 1, der Anpassungsoberfläche, sind. Die Anzahl der Filter beträgt höchstens M*N, wobei M und N die Skalierungsfaktoren in der horizontalen bzw. vertikalen Richtung sind.
Der Filterprozeß des Schemas, das hierin beschrieben wird, hängt lediglich von dem Skalierungsfaktor, den Ordnungen der Anpassungsoberfläche und dem Schwellenwert ab. Folglich kann, nachdem die Filterparameter abschließend festgelegt sind, ein Schablonenschema einfach durch eine Musteranpassung und eine Nachschlagtabelle implementiert werden.
Die Nachschlagtabellengröße kann bis zu etwa 2kukv * M * N Bits betragen. Eine große Reduzierung der Tabellengröße kann jedoch unter Verwendung der mathematischen Eigenschaften von B-Splines erzielt werden. Bei einer Skalierung um einen Faktor von 3 mit einer bikubischen gleichförmigen stückweisen B-Spline-Tensorproduktoberfläche beträgt die obere Grenze für die Platzkomplexität beispielsweise 24*4 * 3 * 3 Bits. Dies bedeutet, daß für jedes der 9 Ausgangspixel eine Tabelle von 16 Einträgen existiert, wie es im folgenden beschrieben wird.
Lokalheit. Bei näherer Betrachtung ist es ersichtlich, daß nicht alle der 9 Ausgangspixel 16 Einträge aufweisen. Die Faltungskerne vieler Ausgangspixel können beispielsweise alle Nullen für die rechteste Spalte oder die unterste Zeile aufweisen. Die Komplexität der Nachschlagtabellen kann folgich um 2&sup9; + 2¹² * 4 + 2¹&sup6; * 4 Bits reduziert werden.
Symmetrie. Bei näherer Betrachtung kann ferner entdeckt werden, daß bei den numerischen Werten in den Faltungskernen eine gewisse Symmetrie herrscht. Die Kerne
weisen beispielsweise ähnliche Zeilen oder Spalten auf, ausgenommen darin, daß die Zahlen Zeilenpermutationen oder Spaltenpermutationen zueinander sind. Ähnliche Beziehungen gelten für
Folglich kann die Platzkomplexität der Nachschlagtabellen um 2&sup9; + 2¹² + 2¹&sup6; Bits weiter reduziert werden, falls eine gewisse Verarbeitungsfähigkeit vorgesehen ist.
Dominanz. Einige Einträge der Faltungskerne sind dominanter im Hinblick auf die resultierende Ausgabe als andere Einträge. Ein Endschwellenwertverarbeitungsprozeß wird für eine binäre Bildskalierung angewendet. Viele Einträge der Kerne werden aufgrund dieses Quantisierungsprozesses unsignifikant. Falls beispielsweise der Schwellenwert für den im vorhergehenden erwähnten Fall als 16/32 ausgewählt wird, sind diejenigen Einträge mit dem Wert 1/36 in dem Kern von s(0,0) effektiv "unbeachtliche" Werte, da dieselben niemals zu dem Endergebnis auf eine signifikante Art und Weise beitragen. Zu praktischen Zwecken können die verschiedenen Implementierungen, die beschrieben wurden, dadurch optimiert werden, daß lediglich die dominantesten Einträge der Kerne beibehalten werden. Auf diese Art und Weise kann der Prozeß für jede spezifische Anwendung fein abgestimmt werden, indem zwischen einer praktikablen Tabellengröße und einer gewünschten Druckqualität abgewogen wird.
Zusammenfassend ausgedrückt kann die Nachschlagtabellengröße abhängig von den Entwurfseinschränkungen bezüglich der Speicherbegrenzung und der Prozessorgeschwindigkeit erheblich reduziert werden.

Ein Quantisierungsfehlerproblem.

Zur Skalierung von binären Bildern ist es wichtig, die Strichbreite zu bewahren. Dies bedeutet, daß, wenn eine Einzelpixellinie um einen Faktor von N skaliert wird, die Ausgangspixellinie ein Breite von N aufweisen muß. Manchmal wird die Strichbreite nicht bewahrt, falls aus dem Quantisierungsschritt des Skalierungsalgorithmus Fehler erzeugt werden, beispielsweise wenn eine Einzelpixellinie um einen Faktor von 3 mittels eines biquadratischen B-Spline- Interpolationsmittels skaliert wird.
Fig. 10 zeigt einen Darunterfehler bei der Quantisierung mit einem Schwellenwert von H = 0,5, während Fig. 11 einen Darüberfehler bei einer Quantisierung mit einem Schwellenwert H = 0,5 + 1,0e&supmin;&sup6; zeigt. Unabhängig davon, wie der Schwellenwert eingestellt wird, weist das skalierte Bild entweder konsequent eine Zusatzpixellinie auf, oder dasselbe weist eine Linie mit einem Pixel weniger als die Pixelnachbildung auf. Ähnliche Fehler treten auf, wenn eine Ein- Pixel-Linie um einen Faktor von 2 mittels eines bikubischen B-Spline-Interpolationsmittels skaliert werden soll.
Das Quantisierungsfehlerproblem wurde in I. E. Abdou und K. Y. Wong, Analysis of Linear Interpolation Schemes for Bi- Level Image Applications, IBM J. Res. Develop., Bd. 26, Nr. 6, S. 667-680, November 1982, berichtet, wobei angenommen wurde, daß dasselbe durch den Mangel an Symmetrie aller geradgradigen Polynome verursacht wurde. Wie es im vorhergehenden gezeigt wurde, tritt der Quantisierungsfehler jedoch unabhängig von dem Grad des Interpolationsmittels auf.
Fig. 12 zeigt beispielsweise die Impulsantwort eines kubischen B-Splines, während Fig. 13 die Antwortfunktion zeigt, die bei 0, 1/3 und 2/3 abgetastet ist. Der Spitzenwert bzw. Peak der Antwortfunktion, der den Eingangsdatenpunkt darstellt, ist in den neu abgetasteten Daten umfaßt. Im Gegensatz dazu (siehe Fig. 14 und 15) ist bei einer Skalierung um 3 mit einem quadratischen B-Spline-Interpolationsmittel der Spitzenwert der Antwortfunktion nicht in den neu abgetasteten Daten umfaßt. Dies ergibt sich aus der Abtastung des Interpolationsmittels an den Positionen
0, 1/N, ..., N - 1/N
Dieses Phänomen ist als die Phasenverzerrungseigenschaft aller geradgradigen Polynome beschrieben worden (siehe I. E. Abdou und K. Y. Wong, Analysis of Linear Interpolation Schemes for Bi-Level Image Applications, IBM J. Res. Develop., Bd. 26, Nr. 6, S. 667-680, November 1982).
Wie es in Fig. 16 gezeigt ist, könnte die Phase um ein Halb der Abtastbeabstandung, z. B. um 1/6, verschoben werden, um eine solche Phasenverzerrung zu kompensieren. Fig. 17 zeigt das Ergebnis einer solchen Einstellung mit einem Schwellenwert von H = 0,56. Es ist ersichtlich, daß für ungerade Skalierungsfaktoren, verglichen zu den Situationen, die in Fig. 10 und 11 gezeigt sind, die B-Spline- Interpolationsmittel, weisen sie nun einen geraden oder ungeraden Grad auf, nicht an Quantisierungsfehlern leiden, falls die Phase nicht verzerrt ist.
Jedoch sind die B-Spline-Interpolationsmittel für gerade Skalierungsfaktoren unabhängig davon, ob dieselben einen geraden Grad oder einen ungeraden Grad aufweisen, einem Quantisierungsfehler ausgesetzt, sogar falls die Phase nicht verzerrt ist. Fig. 18 zeigt beispielsweise die Impulsantwort eines quadratischen B-Spline-Interpolationsmittels nach einer Abtastung bei 0 und 1/2, d. h. einem Skalierungsfaktor von 2; und Fig. 19 zeigt die Impulsantwort eines kubischen B-Spline-Interpolationsmittels nach einer Abtastung bei 0 und 1/2. In beiden Fällen gibt es keine Phasenverzerrung. Trotzdem treten Quantisierungsfehler in beiden Fällen auf, wie es in Fig. 20 und 21 gezeigt ist. Dieser Quantisierungsfehler wird durch einen Mangel an Symmetrie des Interpolationsmittels verursacht. Dies bedeutet, daß bei Nichtvorhandensein einer Phasenverzerrung der Spitzenwert der Impulsantwort immer abgetastet wird, während der Rest der abgetasteten Datenpunkte immer symmetrisch ist. Folglich enthält, wenn der Schwellenwertverarbeitungsschritt stattfindet, das Ergebnis immer eine ungerade Anzahl von Ausgangspixeln.
Ein Aspekt löst das Quantisierungsfehlerproblem, das durch einen Symmetriemangel der Impulsantwort eines B-Spline- Interpolationsmittels verursacht wird, wenn gerade Skalierungsfaktoren angewendet werden. Bei einem Ausführungsbeispiel vergrößert ein Aspekt dieser Lösung den Suchraum aus dem Raum, der durch die B-Splines aufgespannt wird, und der zu dem Raum äquivalent ist, der alle stückweisen Polynome enthält, auf den Raum, der durch das Beta-Spline aufgespannt wird, was eine verallgemeinertere Form von Splines ist (siehe A. Lempel und G. Seroussi, Systematic derivation of Spline bases, Computer Aided Geometric Design, 9 (1992), S. 349-363; und G. Seroussi und B. Barsky, An explicit derivation of discretely shaped Beta-Spline basis functions of arbitrary order, Mathematical Methods in Computer Aided Geometric Design II, T. Lyche und Larry Schumaker (eds.), S. 567-584, 1992).
Die Verwendung des vergrößerten Suchraums wird teilweise aus der Tatsache hergeleitet, daß die Impulsantwort eines Beta-Splines möglicherweise nicht symmetrisch ist. Fig. 22 zeigt die Impulsantwort eines quadratischen Beta-Splines mit β&sub1; = 1,3, wobei Fig. 23 das Ergebnis des Verwendens dieses Interpolationsmittels mit dem Schwellenwert H = 0,56 zeigt. Fig. 24 zeigt die Impulsantwort eines kubischen Beta-Splines mit β&sub1; = 2,0, β&sub2; = -0,5, wobei Fig. 25 das Ergebnis des Verwendens dieses Interpolationsmittels mit dem Schwellenwert H = 0,52 zeigt. Ungünstigerweise erzeugen die im vorhergehenden beschriebenen Lösungen für das Quantisierungsfehlerproblem immer noch ein skaliertes Ausgangsbild, dem zumindest ein Pixel in der horizontalen Lauflänge fehlt.
Eine Lösung für das Quantisierungsfehlerproblem überwindet die Symmetrie der Impulsantwort durch Verschieben der Phase der Basisfunktion. Fig. 26 zeigt das Ergebnis der Interpolation durch ein biquadratisches B-Spline mit einer Phasenverschiebung von δ = 0,1 und einem Schwellenwert von H = 0,56, während Fig. 27 das Ergebnis der Interpolation durch ein kubisches B-Spline mit einer Phasenverschiebung von 5 = 0,1 und einem Schwellenwert von H = 0,56 zeigt. Der tatsächliche Betrag der Phasenverschiebung, der verwendet wird, ist eine Funktion der Anwendung.
Eine weitere Lösung des Quantisierungsfehlerproblems kombiniert die zwei Techniken, die im vorhergehenden beschrieben wurden, d. h. sie verwendet ein phasenverschobenes Beta- Spline-Interpolationsmittel.

Anwendungen.

Das hierin beschriebene Schema wurde auf zwei Hauptanwendungsbereiche angewendet, z. B. die Faxbilderzeugung und die Schriftartskalierung. Es wird darauf hingewiesen, daß das Schema nicht auf diese zwei Beispielanwendungen begrenzt ist.
Für die Faxbilderzeugung in einem Standardmodus werden die Eingangsbilder in Standardfaxauflösungen von horizontal 203 dpi und vertikal 98 dpi übertragen. Fig. 28 zeigt einen Abschnitt des Slerexe-Schriftsatzes in Standardauflösung. Bei einem feinen Modus beträgt die vertikale Auflösung 196 dpi. Fig. 29 zeigt einen Abschnitt des Slerexe-Schriftsatzes in der feinen Auflösung.
An dem Empfangsende der Faxübertragung beträgt die Druckerauflösung typischerweise 300 dpi in beiden Richtungen, 600 dpi horizontal und 300 dpi vertikal oder 600 dpi in beiden Richtungen. Folglich sind die Skalierungsfaktoren für die Faxbilderzeugung üblicherweise feste Zahlen. Aufgrund von Komplikationen, die den physischen Einschränkungen bezüglich der bedruckbaren Ränder des Faxdruckgeräts zugeordnet sind, beträgt der Skalierungsfaktor jedoch nicht wirklich 300/203 oder 300/98. Vielmehr werden die Skalierungsfaktoren auf 3/2 oder 3/1 gerundet (d. h. 1,5 oder 3,0), indem mit Zusatzpixeln aufgefüllt wird, um die Unterschiede aufzufüllen, die bei verschiedenen Firmware-Implementierungen angetroffen werden.
Zusätzlich zu der binären Bildskalierung kann das Schema ferner zur Bildglättung verwendet werden, um die Aliasing- bzw. Bildunregelmäßigkeits-Artefakte zu entfernen, wie es bei der Faxbilderzeugung erforderlich ist. Fig. 30 zeigt ein Zeichen, das aus dem Slerexe-Schriftsatz herausgeschnitten ist. Die Aliasing-Artefakte, die in der Figur gezeigt sind, umfassen Treppeneffekte, Kantezacken und Streupunkte. Als ein Ergebnis des Anwendens einer Bikubisches- Tensorprodukt-B-Spline-Oberfläche als ein Interpolationsmittel werden die Treppenstufen geglättet, die Anzahl von Streupunkten reduziert und die Kantenzacken bezüglich der Lauflänge vergrößert und bezüglich der Höhe reduziert. Tatsächlich können die Streupunkte erfaßt und durch die Erfindung vollständig entfernt werden, falls dies erwünscht ist.
Fig. 31 zeigt die Ergebnisse des Anwendens einer bikubischen B-Spline-Oberfläche als ein Interpolationsmittel zum horizontalen und vertikalen Skalieren um einen Faktor von 3,0 bei einer feinen Auflösung. Es ist notwendig oder wünschenswert, das Längenverhältnis von 2 : 1, das bei der Standardauflösung verwendet wird, zu kompensieren, wobei in der horizontalen Richtung eine andere Ordnung als diejenige der vertikalen Richtung der Anpassungsoberfläche ausgewählt werden kann. Fig. 32 zeigt das Ergebnis des Anwendens einer Quadratisch-mal-Quartik-Tensorprodukt-B-Spline-Oberfläche als ein Interpolationsmittel zum horizontalen Skalieren um einen Faktor von 1,5 und vertikalen Skalieren um einen Faktor von 3,0 bei einer Standardauflösung.
Das Schema kann ferner verwendet werden, um englische Zeichenschriftarten zu skalieren. Um beispielsweise eine 12- Punkt-Schriftart in 300 dpi in eine 24-Punkt-Schriftart für einen Druck auf einem 600-dpi-Drucker zu skalieren, ist eine Skalierung um einen Faktor von 4 in sowohl der horizontalen als auch der vertikalen Richtung erforderlich. Fig. 33 zeigt ein Testzeichen in der ursprünglichen 12-Punkt- Schriftart in 300 dpi.
Das Testzeichen von Fig. 33 kann durch zweimaliges Anwenden der RET (RET = Resolution Enhancement Technology = Auflösungsverbesserungstechnologie) skaliert werden, die einen Satz von rautenförmigen Schablonen verwendet (siehe C. Tung, Resolution Enhancement Technology in Hewlett Packard LaserJet Printers, IST/SPIE Symposium on Electronic Imaging: Science and Technology, S. 440-448, 1993). Fig. 34 zeigt die Ergebnisse, die unter Verwendung dieses Lösungsansatzes erhalten werden. In der Figur ist ersichtlich, daß die Artefakte 34 entlang des Innenkrümmungsabschnitts des Testzeichens an der unteren rechten Ecke durch diesen Lösungssatz eingeführt worden sind.
Ein Ausführungsbeispiel, das auf das Testzeichen angewendet wurde, umfaßte das Interpolieren durch eine biseptimale Tensorprodukt-B-Spline-Oberfläche unter Verwendung einer rechteckigen Schablone. Dieser Lösungsansatz entfernt die Artefakte, wie es in Fig. 35 ersichtlich ist.

Basistibersetzungsmatrizen.

Für jede Spline-Basis der Ordnung k
B = [B0,k(t) B1,k (t) ... Bk-1,k(t)] (28)
existiert eine Basisübersetzungsmatrix (k mal k) Mk, derart, daß
B = TMk (29)
wobei Tk die Potenzbasis ist, d. h.
[tk-1 tk-2 ... t1] (30)
Im folgenden sind die Basisübersetzungsmatrizen für gleichmäßige Polynom-B-Splines der Ordnungen von linear bis septimal aufgelistet. Linear: Quadratisch: Kubisch: Quartik bzw. 4. Ordnung: 5. Ordnung: 6. Ordnung: Septimal bzw. 7. Ordnung:

Abtastfaltungskerne.

Im folgenden sind Faltungskerne zum Skalieren um einen Faktor von 3 mit einer bikubischen gleichmäßigen Polynom-B- Spline-Tensorproduktoberfläche s(u,v) aufgelistet. Ku0,v0 ist der Kern zum Abtasten von s(u,v) bei (u&sub0;,v&sub0;).
Dementsprechend liefert dieses Beispiel ein Bildskalierungsverfahren, das auf der stückweisen Polynominterpolation basiert. Dasselbe kann für wahlweise oder feste Skalierungsfaktoren verwendet werden und dasselbe kann ferner verwendet werden, um Aliasing-Artefakte zu reduzieren oder zu entfernen.
Das hierin beschriebene Beispiel weist die folgenden Vorteile auf:
Es ist ein formales Modell, das eine systematische Art und Weise zum Erzeugen von Faltungskernen zur Bildskalierung liefert, die zum Lösen des Quantisierungsfehlerproblems nützlich sind, die alle Polynominterpolationsmittel beeinträchtigen.
Es liefert ein Schema, das numerische Werte bestimmt, die verwendet werden, um die Gewichtungen von benachbarten Eingangspixeln zu steuern. Durch Einstellen der mathematischen Berechnungen, die durch die Erfindung angewendet werden, kann die spezifische Implementation für die beste Druckqualität fein abgestimmt werden, und ist dabei für verschiedene Entwurfsparameter empfindlich, wie z. B. des Stiftes, der Tinte, des Papiers, der Wagengeschwindigkeit und der ROM-Größe.
Es liefert ein Tabellennachschlagschema, das für eine Hardwareimplementierung unter Verwendung bekannter Hardwaretechniken geeignet ist. Die Nachschlagtabellengröße kann wesentlich reduziert werden, um die Speicherplatzeinschränkungen zu erfüllen.

Claims

1. Ein Verfahren zum Skalieren eines binären Bildes durch stückweise Polynominterpolation in dem Speicher eines Computergeräts unter Verwendung eines stückweisen Polynominterpolationsmittels, wobei das Verfahren folgende Schritte aufweist:

Modellieren (110) von binären Daten, die ein Eingangspixelbild darstellen, als einen dreidimensionalen Datensatz (X, Y, Z), bei dem die erste und die zweite Koordiante (X, Y) Eingangspixelbilddimensionen sind, und die dritte Koordinate (Z) die Intensität des ursprünglichen Pixelbildes ist;

Anpassen (120) des dreidimensionalen Datensatzes durch ein Oberflächeninterpolationsmittel;

Neuabtasten (130) der binären Daten, die das Eingangspixelbild darstellen, an der Anpassungsoberfläche mit Gewichtungen, die durch den Typ des Interpolationsmittels, den Grad desselben und einen Skalierungsfaktor bestimmt sind, um Interpolationsdaten zu liefern; und

Erzeugen (150) eines Ausgangspixelbildes, wobei das Ausgangspixelbild aus dem Eingangspixelbild skaliert ist,

dadurch gekennzeichnet, daß

das stückweise Polynominterpolationsmittel vom B- Spline-, Beta-Spline-, einem phasenverschobenen oder einem nicht phasenverschobenen Typ ist, und daß das Verfahren ferner folgende Schritte aufweist:

Bestimmen des Typs des stückweisen Polynominterpolationsmittels für die Oberflächenanpassung basierend darauf, ob ein Bildskalierungsfaktor, der die Bildskalierung bestimmt, eine gerade oder ungerade Ganzzahl ist;

Korrigieren jeglicher Quantisierungsfehlerprobleme in den Interpolationsdaten, falls dies notwendig ist, durch Erzeugen von Faltungskernen für die Bildskalierung; und

schwellenwertmäßiges Verarbeiten (140) der Interpolationsdaten, um binäre Daten zu erzeugen, die das Ausgangspixelbild darstellen.

2. Ein Verfahren gemäß Anspruch 1, bei dem das Interpolationsmittel eine B-Spline-Tensorproduktoberfläche oder eine Beta-Spline-Tensorproduktoberfläche ist.

3. Ein Verfahren gemäß Anspruch 1 oder 2, das folgenden Schritt aufweist:

Phasenverschieben während des Schrittes des Neuabtastens, um die Abtastposition bezüglich des Skalierungsfaktors neu auszurichten.

4. Ein Verfahren gemäß Anspruch 3, das folgenden Schritt aufweist:

Bestimmen des Phasenverschiebungsbetrags zum Reduzieren des Quantisierungsfehlers.

5. Ein Verfahren gemäß einem der vorhergehenden Ansprüche, das folgenden Schritt aufweist:

Bestimmen von Schwellenwerten, die verwendet werden, um binäre Ausgangspixel zu erzeugen.

6. Ein Verfahren gemäß einem der vorhergehenden Ansprüche, das folgende Schritte aufweist:

Bestimmen von Werten, die verwendet werden, um die Gewichtungen von benachbarten Eingangspixeln zu steuern;

Vorabberechnen der Gewichtungen durch Bestimmen des Typs des Interpolationsmittels und Bestimmen, ob dasselbe für vorbestimmte feste Skalierungsfaktoren einen ungeraden oder geraden Grad aufweist; und

Durchführen einer Faltung durch eine Nachschlagtabelle auf der Basis der festen Skalierungsfaktoren.

7. Ein Verfahren gemäß Anspruch 6, das den Schritt des Feinabstimmens der Nachschlagtabelle für den Typ des erzeugten Ausgangsbilds aufweist.

8. Ein Verfahren gemäß Anspruch 6 oder 7, das folgende Schritte aufweist:

Reduzieren der Nachschlagtabellengröße durch die in den Faltungskernen erfaßte Lokalheit;

Reduzieren der Nachschlagtabellengröße durch die in den Faltungskernen erfaßte Symmetrie; und

Reduzieren der Nachschlagtabellengröße durch Beibehalten lediglich der dominantesten Einträge der Faltungskerne.

9. Ein Verfahren gemäß einem der Ansprüche 6 bis 8, das ferner folgenden Schritt aufweist:

manuelles Modifizieren der Einträge der Nachschlagtabelle, um Bildunregelmäßigkeitsartefakte im wesentlichen zu entfernen.

10. Ein Computergerät-implementiertes System zum Skalieren eines binären Bildes durch eine stückweise Polynominterpolation unter Verwendung eines stückweisen Polynominterpolationsmittels, mit

einem Eingangsmodul (110) zum Empfangen von binären Daten, die ein Eingangspixelbild darstellen, als einen dreidimensionalen Datensatz (X, Y, Z), bei dem die erste und die zweite Koordinate (X, Y) Eingangspixelbilddimensionen sind, und die dritte Koordinate (Z) die Intensität des ursprünglichen Pixelbildes ist;

einem Oberflächenanpassungsmodul (120) zum Anpassen des dreidimensionalen Datensatzes durch eine Oberfläche;

einem Neuabtastungsmodul (130) zum Neuabtasten der binären Daten, die das Eingangspixelbild darstellen, an der Anpassungsoberfläche mit Gewichtungen, die durch den Typ des Interpolationsmittels, den Grad desselben und einen Skalierungsfaktor bestimmt sind, um Interpolationsdaten zu liefern; und

einem Ausgangsmodul (150) zum Erzeugen eines Ausgangspixelbildes aus den binären Daten, wobei das Ausgangspixelbild aus dem Eingangspixelbild skaliert ist,

dadurch gekennzeichnet, daß

das stückweise Polynominterpolationsmittel vom B- Spline-, Beta-Spline-, einem phasenverschobenen oder nicht phasenverschobenen Typ ist, und daß das Gerät zusätzlich folgende Merkmale aufweist:

eine Einrichtung zum Bestimmen des Typs des stückweisen Polynominterpolationsmittels zur Oberflächenanpassung (120) basierend darauf, ob ein Bildskalierungsfaktor, der die Bildskalierung bestimmt, eine gerade oder ungerade Ganzzahl ist;

ein Korrekturmodul zum Korrigieren jeglicher Quantisierungsfehlerprobleme in den Interpolationsdaten durch Erzeugen von Faltungskernen für die Bildskalierung; und

ein Schwellenwertverarbeitungsmodul (140) zum schwellenwertmäßiden Verarbeiten der Interpolationsdaten, um binäre Daten zu erzeugen, die das Ausgangspixelbild darstellen.

11. Skalierungsvorrichtung gemäß Anspruch 10, bei dem das Interpolationsmittel eine B-Spline-Tensorproduktoberfläche oder eine Beta-Spline-Tensorproduktoberfläche ist.

12. Skalierungsvorrichtung gemäß Anspruch 10 oder 11, die ferner folgendes Merkmal aufweist:

eine Einrichtung zum Phasenverschieben des binären Eingangsbildes, um die Abtastposition bezüglich des Skalierungsfaktors neu auszurichten.

13. Skalierungsvorrichtung gemäß Anspruch 12, die ferner folgendes Merkmal aufweist:

eine Einrichtung zum Bestimmen des Phasenverschiebungsbetrags, um einen Quantisierungsfehler zu reduzieren.

14. Skalierungsvorrichtung gemäß einem der Ansprüche 10 bis 13, die ferner folgendes Merkmal aufweist:

eine Einrichtung zum Bestimmen von Schwellenwerten, die verwendet werden, um binäre Ausgangspixel (140) zu erzeugen.

15. Skalierungsvorrichtung gemäß einem der Ansprüche 10 bis 14, die ferner folgende Merkmale aufweist:

eine Einrichtung zum Bestimmen von Werten, die verwendet werden, um die Gewichtungen von benachbarten Eingangspixeln zu steuern;

eine Einrichtung zum Vorabberechnen der Gewichtungen durch Bestimmen des Typs des Interpolationsmittels und Bestimmen, ob dasselbe für vorbestimmte feste Skalierungsfaktoren einen ungeraden oder geraden Grad aufweist; und

eine Einrichtung zum Durchführen einer Faltung durch eine Nachschlagtabelle auf der Basis der festen Skalierungsfaktoren.

16. Skalierungsvorrichtung gemäß Anspruch 15, die ferner eine Einrichtung zum Feinabstimmen der Nachschlagtabelle für den Typ des Ausgangsbilds, das erzeugt werden soll, aufweist.

17. Skalierungsvorrichtung gemäß Anspruch 15 oder 16, die ferner folgende Merkmale aufweist:

eine Einrichtung zum Reduzieren einer Nachschlagtabellengröße durch die in den Faltungskernen erfaßte Lokalheit;

eine Einrichtung zum Reduzieren der Nachschlagtabellengröße durch die in den Faltungskernen erfaßte Symmetrie; und

eine Einrichtung zum Reduzieren der Nachschlagtabellengröße durch Beibehalten lediglich der dominantesten Einträge der Faltungskerne.

18. Skalierungsvorrichtung gemäß einem der Ansprüche 15 bis 17, die ferner folgendes Merkmal aufweist:

eine Einrichtung zum manuellen Modifizieren der Einträge der Nachschlagtabelle, um Bildunregelmäßigkeitsartefakte im wesentlichen zu entfernen.