Algorithmus für freies Skalieren / Arbitrary Up-/Downscaling of Images

[Mickey_S]

Hi!

Bin fast ein bißchen am Verzweifeln.

Ich hab' mich jetzt stundenlang durch Foren, Google & Co. gewühlt jedoch nix passendes gefunden:

Ich benötige einen Algorithmus zur Umsetzung in C++, der es erlaubt, 2D-Bilder mit frei wählbarem Faktor zu skalieren.

Zu meinem Leidwesen mußte ich feststellen, daß die o. angef. Quellen sich immer auf Bildbearbeitung mit Grafiksoftware beziehen. Das brauche ich aber nicht. Ich will es ja programmieren und nicht anwenden. -- Ich habe auch ein Quelle gefunden, die ein Downsampling um den Faktor 2 beschreibt. Jedoch können in meinem Fall Faktoren wie 0.67 oder 0.31 auftauchen. Doch da weiß ich einfach nicht, wie ich das anpacken soll.

Für Links, Denkansätze bzw. kurze, das Prinzip verdeutlichende Beispiele wär' ich dankbar. Ich bin nicht auf der Suche nach einer Komplettlösung - nur daß nachher keiner kommt und sagt, ich sei faul. ;o)


CU!

-Mike

 

[Matthias Reitinger]

Hallo Mike!

Ich benötige einen Algorithmus zur Umsetzung in C++, der es erlaubt, 2D-Bilder mit frei wählbarem Faktor zu skalieren.

Da gibt es mehrere Möglichkeiten, dich sich hinsichtlich Komplexität (der Implementierung) und Qualität unterscheiden. Allen gemein ist das grundsätzliche Vorgehen, hier mal als Pseudocode:

float scaling_factor = 1.23f;
// Quellbild aus Datei einlesen:
Image *original_image = new Image("sample.png");
// Neue Bilddimensionen berechnen
uint new_width = original_image->width * scaling_factor;
uint new_height = original_image->height * scaling_factor;
// Neues Bild im Speicher anlegen
Image *scaled_image = new Image(new_width, new_height);
// Konkrete Interpolationstechnik erstellen, die auf das Quellbild zurückgreift
InterpolationMethod *method = new ConcreteInterpolationMethod(original_image);
// Über alle Pixel des skalierten Bildes laufen
for (uint y = 0; y < new_height; ++y) {
  for (uint x = 0; x < new_width; ++x) {
    // Korrespondierende Koordinate im Quellbild berechnen
    float original_x = x / scaling_factor;
    float original_y = y / scaling_factor;
    scaled_image->SetPixel(method->GetValueAt(original_x, original_y));
  }
}
scaled_image->Write("scaled.png");

Die Interpolationsmethoden unterscheiden sich jetzt durch die Implementierung von GetValueAt. Am einfachsten ist das Punktsampling, bei dem die Koordinaten einfach gerundet und der Farbwert an der entsprechenden Stelle im Quellbild zurückgegeben wird. Beim Vergrößern des Bildes sieht man so klar die Pixelstruktur. Besser macht es da die bilineare Interpolation, bei der die 4 am nächsten liegenden Pixel betrachtet und deren Werte bilinear interpoliert werden. Qualitativ hochwertiger (vor allem beim Verkleinern von Bildern) ist die bikubische Interpolation, bei der nicht linear, sondern kubisch interpoliert wird (man berechnet für jede Dimension ein kubisches Interpolationspolynom, das die Pixel im Quellbild als Stützwerte verwendet). Das kann z.B. durch Lagrange-Polynome oder das Schema von Aitken-Neville realisiert werden. Weiterführende Verfahren findet man dann in der Signaltheorie, in der man mit Rekonstruktionskerneln hantiert. In diese Kategorie fallen z.B. die Sinc- und Lancosz-Interpolation.

Ich denke mal damit solltest du für den Anfang mit genügend Schlagwörtern ausgerüstet sein Viel Spaß bei der Implementierung!

Grüße, Matthias

 

[Mickey_S]

So, jetzt scheinen die Seiten von tutorials.de wieder zu funktionieren.

Hi Matthias!

Danke für Deine Antwort und die Hinweise.

Das hatte ich mir auch so ungefähr vorgestellt; gut mal eine Bestätigung bekommen zu haben. ;o) Aber genau das hier

scaled_image->SetPixel(method->GetValueAt(original_x, original_y));

ist der springende Punkt. Ich dachte - zumindest beim Upscaling - an einen, bzgl. der Koeffizienten vorausberechneten, 4-Tap-/32-Phasen-Filter. Dabei habe ich 32 vorberechnete Quadrupel (oder uint32), die einen z. B. Gauss-Filter implementieren und je nach 'Phase' die Gewichte der vier in Betracht gezogenen Originalpixel wichten, die dann zum Zielpixel zusammengefaßt werden (siehe Bild, Upscale 4x, es entstehen drei neue, interpolierte Pixel; aus der Koeffiziententabelle wird nur jedes 8. Quadrupel verwendet (bei 32x wird halt jedes benutzt, je mehr interpolierte Pixel (Phasen), um so mehr Einträge werden genutzt)). In [1], z. B., liefert Quellpixel Q3 Zielpixel Z1. Die erste interpolierte 'Phase' ([2]) Z2 ergibt sich aus dem durch die Gewichte W0..3 gesteuerten, schwindenden Einfluß von Q3, einem Rest von Q2 und dem wachsenden Einfluß von Q4 bzw. einem 'Rest' von Q5. Je nach dem, wie man die Koeffizienten 'bestückt', realisiert man entsprechend die gewünschte Filterfunktion. Allerdings erlaubt das nur ganzzahliges Hochskalieren (jetzt ist mir auch der deutsche Begriff eingefallen ;o) ); mit, z. B. x3.67, bin ich dann aber immer noch aufgeschmissen.

Ich hoffe, meine verbale und grafische Darstellung bringt das rüber, was ich sagen wollte.

Naja, muß mir dann halt mal Deine Quellen anschauen.


CU!

-Mike

 

[Matthias Reitinger]

Hallo Mike,

wenn ich das richtig verstehe, beschreibst du damit die Vorberechnung der Gewichtungsfaktoren für bestimmte Spezialfälle (ganzzahlige Skalierung). Ist Geschwindigkeit für deinen Einsatzzweck ein wichtiger Faktor, oder wie kommst du auf dieses Vorgehen? Implementier doch einfach die bilineare Interpolation, die macht für jeden Pixel im Zielbild auch 4 Taps und die Berechnung der Gewichte ist recht einfach (man muss sich nur den Nachkomma-Anteil der Koordinaten anschauen).

Grüße, Matthias

 

[Mickey_S]

Hi Matthias!

Zum Hintergrund: Bei dieser Geschichte ging es um Geschwindigkeit; das Konzept ist einer Hardwareentwicklung entlehnt (das Silizium dazu gibt's auch schon seit ein paar Jahren).

Okay, dann werde ich mich mal mit der zugehörigen Mathematik des 'freien Skalierens' näher beschäftigen.


CU!

-Mike