Was ist der beste Bild-Downscaling-Algorithmus (qualitativ)?

Ich möchte herausfinden, welcher Algorithmus der beste ist, um ein Rasterbild zu verkleinern. Mit best meine ich die, die die schönsten Ergebnisse liefert. Ich weiß von Bikubik, aber gibt es noch etwas Besseres? Ich habe zum Beispiel von einigen Leuten gehört, dass Adobe Lightroom über einen proprietären Algorithmus verfügt, der bessere Ergebnisse liefert als die von mir verwendete Standard-Bikubik. Leider möchte ich diesen Algorithmus selbst in meiner Software verwenden, sodass die sorgfältig gehüteten Geschäftsgeheimnisse von Adobe nicht ausreichen.

Hinzugefügt:

Ich habe Paint.NET ausgecheckt und zu meiner Überraschung scheint Super Sampling beim Verkleinern eines Bildes besser als bikubisch zu sein. Das lässt mich fragen, ob Interpolationsalgorithmen überhaupt der richtige Weg sind.

Es erinnerte mich auch an einen Algorithmus, den ich selbst "erfunden", aber nie implementiert hatte. Ich nehme an, es hat auch einen Namen (als etwas, das dieses Triviale nicht allein für mich sein kann), aber ich konnte es unter den populären nicht finden. Super Sampling war das nächste.

Die Idee ist folgende: Berechnen Sie für jedes Pixel im Zielbild, wo es sich im Quellbild befinden würde. Es würde wahrscheinlich ein oder mehrere andere Pixel überlagern. Es wäre dann möglich, die Flächen und Farben dieser Pixel zu berechnen. Um dann die Farbe des Zielpixels zu erhalten, würde man einfach den Durchschnitt dieser Farben berechnen und ihre Bereiche als "Gewichte" hinzufügen. Wenn also ein Zielpixel 1/3 eines gelben Quellpixels und 1/4 eines grünen Quellpixels abdecken würde, würde ich (1/3 * gelb + 1/4 * grün) / (1/3 +) erhalten 1/4).

Dies wäre natürlich rechenintensiv, sollte aber dem Ideal so nahe wie möglich kommen, oder?

Gibt es einen Namen für diesen Algorithmus?

Leider kann ich keinen Link zur ursprünglichen Umfrage finden, aber als Hollywood-Kameramänner von Film zu digitalen Bildern wechselten, tauchte diese Frage häufig auf, sodass jemand (vielleicht SMPTE, vielleicht der ASC) eine Reihe professioneller Kameramänner sammelte und ihnen Filmmaterial zeigte das war mit einer Reihe verschiedener Algorithmen neu skaliert worden. Das Ergebnis war, dass für diese Profis, die sich riesige Filme ansehen, der Konsens bestand, dass Mitchell (auch als hochwertiger Catmull-Rom bekannt) am besten zum Vergrößern und sinc am besten zum Verkleinern geeignet ist. Aber sinc ist ein theoretischer Filter, der bis ins Unendliche reicht und daher nicht vollständig implementiert werden kann. Daher weiß ich nicht, was sie eigentlich mit "sinc" gemeint haben. Es bezieht sich wahrscheinlich auf eine abgeschnittene Version von sinc. Lanczosist eine von mehreren praktischen Varianten von sinc, die versuchen, das Abschneiden zu verbessern, und wahrscheinlich die beste Standardoption zum Verkleinern von Standbildern ist. Aber wie üblich hängt es vom Bild und Ihren Wünschen ab: Das Verkleinern einer Strichzeichnung, um Linien zu erhalten, ist beispielsweise ein Fall, in dem Sie möglicherweise die Betonung der Kanten bevorzugen, die beim Verkleinern eines Blumenfotos unerwünscht wären.

Es gibt ein gutes Beispiel für die Ergebnisse verschiedener Algorithmen in Cambridge in Color .

Die Leute von fxguide haben viele Informationen zu Skalierungsalgorithmen zusammengestellt (zusammen mit vielen anderen Dingen über Compositing und andere Bildverarbeitung), die einen Blick wert sind. Sie enthalten auch Testbilder, die bei der Durchführung eigener Tests hilfreich sein können.

Jetzt hat ImageMagick eine umfangreiche Anleitung zum Resampling von Filtern, wenn Sie wirklich darauf eingehen möchten.

Es ist irgendwie ironisch, dass es mehr Kontroversen über das Verkleinern eines Bildes gibt, was theoretisch perfekt möglich ist, da Sie nur Informationen wegwerfen, als über das Vergrößern, wenn Sie versuchen, Informationen hinzuzufügen, die dies nicht tun. t existieren. Aber fangen Sie mit Lanczos an.

Es gibt Lanczos-Sampling, das langsamer als bikubisch ist, aber Bilder mit höherer Qualität erzeugt.

(Bi-) lineares und (bi-) kubisches Resampling sind nicht nur hässlich, sondern auch schrecklich falsch, wenn sie um einen Faktor kleiner als 1/2 verkleinert werden. Sie führen zu einem sehr schlechten Aliasing, ähnlich dem, was Sie erhalten würden, wenn Sie um den Faktor 1/2 herunterscameln und dann das Downsampling für den nächsten Nachbarn verwenden würden.

Persönlich würde ich empfehlen, Stichproben für die meisten Downsampling-Aufgaben (flächen-) zu mitteln. Es ist sehr einfach und schnell und nahezu optimal. Gaußsches Resampling (mit einem Radius, der proportional zum Kehrwert des Faktors gewählt wird, z. B. Radius 5 für das Downsampling um 1/5) kann bessere Ergebnisse mit etwas mehr Rechenaufwand liefern und ist mathematisch fundierter.

Ein möglicher Grund für die Verwendung des Gaußschen Resamplings ist, dass es im Gegensatz zu den meisten anderen Algorithmen sowohl beim Upsampling als auch beim Downsampling korrekt funktioniert (keine Artefakte / Aliasing einführt), solange Sie einen Radius auswählen, der dem Resampling-Faktor entspricht. Andernfalls benötigen Sie zur Unterstützung beider Richtungen zwei separate Algorithmen - die Flächenmittelung für das Downsampling (die sich für das Upsampling auf den nächsten Nachbarn verschlechtern würde) und (bi-) kubisch für das Upsampling (das sich für das Downsampling auf den nächsten Nachbarn verschlechtern würde). Eine Möglichkeit, diese schöne Eigenschaft der mathematischen Gaußschen Neuabtastung zu sehen, besteht darin, dass Gauß mit sehr großem Radius der Flächenmittelung und Gauß mit sehr kleinem Radius der (bi-) linearen Interpolation nahekommt.

Ich habe vor einiger Zeit einen Artikel über Slashdot über Seam Carving gesehen , der sich vielleicht lohnt.

Das Nahtschnitzen ist ein von Shai Avidan und Ariel Shamir entwickelter Algorithmus zur Größenänderung von Bildern. Dieser Algorithmus ändert die Abmessungen eines Bildes nicht durch Skalieren oder Zuschneiden, sondern durch intelligentes Entfernen von Pixeln aus dem Bild (oder Hinzufügen von Pixeln zu dem Bild), die wenig Bedeutung haben.

Der von Ihnen beschriebene Algorithmus wird als lineare Interpolation bezeichnet und ist einer der schnellsten Algorithmen, bei Bildern jedoch nicht der beste.

Gibt es einen Namen für diesen Algorithmus?

Es könnte in der Literatur als "Box" - oder "Fenster" -Resampling bezeichnet werden. Es ist tatsächlich weniger rechenintensiv, wie Sie denken.

Es kann auch verwendet werden, um eine Zwischenbitmap zu erstellen, die anschließend durch bi-kubische Interpolation verwendet wird, um ein Aliasing zu vermeiden, wenn das Downsampling um mehr als 1/2 erfolgt.

Wenn jemand interessiert ist, hier ist meine C ++ - Implementierung des Algorithmus zur Skalierung der Flächenmittelung:

void area_averaging_image_scale(uint32_t *dst, int dst_width, int dst_height, const uint32_t *src, int src_width, int src_height)
{
    // 1. Scale horizontally (src -> mid)
    int mid_width  = dst_width,
        mid_height = src_height;
    float src_width_div_by_mid_width = float(src_width) / mid_width;
    float mid_width_div_by_src_width = 1.f / src_width_div_by_mid_width;
    std::vector<uint32_t> mid(mid_width * mid_height);
    for (int y=0; y<mid_height; y++)
        for (int x=0; x<mid_width; x++)
            for (int c=0; c<4; c++) {
                float f = x * src_width_div_by_mid_width;
                int i = int(f);
                float d = ((uint8_t*)&src[i + y*src_width])[c] * (float(i) + 1 - f);
                float end = f + src_width_div_by_mid_width;
                int endi = int(end);
                if (end - float(endi) > 1e-4f) {
                    assert(endi < src_width);
                    d += ((uint8_t*)&src[endi + y*src_width])[c] * (end - float(endi));
                }
                for (i++; i < endi; i++)
                    d += ((uint8_t*)&src[i + y*src_width])[c];
                int r = int(d * mid_width_div_by_src_width + 0.5f);
                assert(r <= 255);
                ((uint8_t*)&mid[x + y*mid_width])[c] = r;
            }

    // 2. Scale vertically (mid -> dst)
    float mid_height_div_by_dst_height = float(mid_height) / dst_height;
    float dst_height_div_by_mid_height = 1.f / mid_height_div_by_dst_height;
    for (int y=0; y<dst_height; y++)
        for (int x=0; x<dst_width; x++)
            for (int c=0; c<4; c++) {
                float f = y * mid_height_div_by_dst_height;
                int i = int(f);
                float d = ((uint8_t*)&mid[x + i*mid_width])[c] * (float(i) + 1 - f);
                float end = f + mid_height_div_by_dst_height;
                int endi = int(end);
                if (end - float(endi) > 1e-4f) {
                    assert(endi < mid_height);
                    d += ((uint8_t*)&mid[x + endi*mid_width])[c] * (end - float(endi));
                }
                for (i++; i < endi; i++)
                    d += ((uint8_t*)&mid[x + i*mid_width])[c];
                int r = int(d * dst_height_div_by_mid_height + 0.5f);
                assert(r <= 255);
                ((uint8_t*)&dst[x + y*dst_width])[c] = r;
            }
}