2D-Grafik Bild mit bilinearer Interpolation skalieren

RalleYTN

Bekanntes Mitglied
Hallöchen!
Ich hatte schonmal ein ähnliches Problem welches ich hier beschrieben habe.
Die Ausgangssituation ist ungefähr die gleiche. Allerdings steht mir inzwischen Java 8 zur verfügung und es geht nicht darum ein Bild zu rotieren sondern um die Skalierung von Bildern.
Skalierung mit nearest neighbour war kein großes Problem, jedoch brauche ich auch noch einen Algorithmus der eine bessere Qualität zu Stande bringt. Da habe ich mich für die bilineare Interpolation entschieden.
Als ich danach gesucht habe bin auch auf folgenden Beitrag auf Stackoverflow gestoßen: http://stackoverflow.com/questions/16341167/bilinear-interpolation

Ich habe diesen Algorithmus etwas abgeändert, damit ich ihn auf ein zweidimensionales integer array mit ARGB Farbraum anwenden kann und die Performance etwas optimiert, indem ich so wenig Operationen wie möglich mache.

Java:
public static final BiConsumer<int[][], int[][]> SCALE_BILINEAR_INTERPOLATION = (source, target) -> {
       
   int srcWidth = source.length;
   int srcHeight = source[0].length;
   int targetWidth = target.length;
   int targetHeight = target[0].length;
   int targetX;
   int targetY;
   int srcX1;
   int srcX2;
   int srcY1;
   int srcY2;
   int pixelA;
   int pixelB;
   int pixelC;
   int pixelD;
       
   float ratioX = (float)srcWidth / (float)targetWidth;
   float ratioY = (float)srcHeight / (float)targetHeight;
   float diffX;
   float diffY;
       
   for(targetX = 0; targetX < targetWidth; targetX++) {
           
       for(targetY = 0; targetY < targetHeight; targetY++) {
               
           srcX1 = (int)(ratioX * targetX);
           srcX2 = srcX1 + 1;
           srcY1 = (int)(ratioY * targetY);
           srcY2 = srcY1 + 1;
           diffX = (ratioX * targetX) - srcX1;
           diffY = (ratioX * targetY) - srcY1;
               
           pixelA = source[srcX1][srcY1];
           pixelB = (srcX2 >= 0 && srcX2 < srcWidth && srcY1 >= 0 && srcY1 < srcHeight) ? source[srcX2][srcY1] : pixelA;
           pixelC = (srcX1 >= 0 && srcX1 < srcWidth && srcY2 >= 0 && srcY2 < srcHeight) ? source[srcX1][srcY2] : pixelA;
           pixelD = (srcX2 >= 0 && srcX2 < srcWidth && srcY2 >= 0 && srcY2 < srcHeight) ? source[srcX2][srcY2] : pixelA;

           target[targetX][targetY] = (((int)(((pixelA >> 24) & 0xFF) * (1 - diffX) * (1 - diffY) + ((pixelB >> 24) & 0xFF) * diffX * (1 - diffY) + ((pixelC >> 24) & 0xFF) * diffY * (1 - diffX) + ((pixelD >> 24)) * (diffX * diffY)) & 0xFF) << 24) | (((int)(((pixelA >> 16) & 0xFF) * (1 - diffX) * (1 - diffY) + ((pixelB >> 16) & 0xFF) * diffX * (1 - diffY) + ((pixelC >> 16) & 0xFF) * diffY * (1 - diffX) + ((pixelD >> 16)) * (diffX * diffY)) & 0xFF) << 16) | (((int)(((pixelA >> 8) & 0xFF) * (1 - diffX) * (1 - diffY) + ((pixelB >> 8) & 0xFF) * diffX * (1 - diffY) + ((pixelC >> 8) & 0xFF) * diffY * (1 - diffX) + ((pixelD >> 8)) * (diffX * diffY)) & 0xFF) << 8) | ((int)((pixelA & 0xFF) * (1 - diffX) * (1 - diffY) + (pixelB & 0xFF) * diffX * (1 - diffY) + (pixelC & 0xFF) * diffY * (1 - diffX) + (pixelD) * (diffX * diffY)) & 0xFF);
       }
   }
};

Ich bekomme dabei auch ein skaliertes Bild raus jedoch sieht das nicht ganz wie das gewünschte Ergebnis aus:

Original:
upload_2017-5-14_14-31-49.jpeg

Skaliert (Faktor 2):
upload_2017-5-14_14-32-29.jpeg

Kann mir jemand sagen wo der Fehler liegt?
 
Geh doch einfach mal mit dem Debugger die ersten 4 Pixel durch. Dann solltest du schnell merken wo er Mist rechnet, denn eigentlch sollte ja immer Weiß rauskommen was es aber definitiv nicht tut.

Gruß

Claus
 
Anscheinend wechselt diffY zwischendrinn ständig zwischen 0.0 und 0.5.
ob das nun so gewollt ist oder nicht kann nicht sagen. Hab den Algorithmus ja schließlich bloß übernommen und abgeändert.
 
Code:
//pixelA,pixelB,pixelC,pixelD:target[targetX][targetY]
//-1 entspricht 0xFFFFFFFF
-1,-1,-1,-1:-1077952577
-1,-1,-1,-1:-1
-1,-1,-1,-1:-1077952577
-1,-1,-1,-1:-1
-1,-1,-1,-1:-1077952577
-1,-1,-1,-1:-1
-1,-1,-1,-1:-1077952577
 
Also muss es dann ja wohl in der Mammut Zeile darunter kapput gehen oder? Zerlege die doch mal in viele kleine Teile und debugge die einzelnen Ergebnisse.
 
BTW. Kann es sein, dass genau die -1 das Problem ist ? Wenn das Original mit unsigned rechnet, dann kann die Formel mit signed nicht das gleiche Ergebnis geben...
 
Signed und unsigned sind nicht das Problem. Ein integer hat 4 Byte. Einen davon verwende ich für jeden channel. Ob das nun signed oder unsigned ist spielt keine Rolle da ich selber die binären Daten interpretieren kann wie ich will.

Java:
int weiss = 0xFFFFFFFF; // -1
int alpha = (weiss >> 24) & 0xFF; // 255
int red = (weiss >> 16) & 0xFF; // 255
int green = (weiss >> 8) & 0xFF; // 255
int blue = weiss & 0xFF; // 255

Java:
    public static final BiConsumer<int[][], int[][]> SCALE_BILINEAR_INTERPOLATION = (source, target) -> {
       
       int srcWidth = source.length;
       int srcHeight = source[0].length;
       int targetWidth = target.length;
       int targetHeight = target[0].length;
       int targetX;
       int targetY;
       int srcX1;
       int srcX2;
       int srcY1;
       int srcY2;
       int pixelA;
       int pixelB;
       int pixelC;
       int pixelD;
       
       float ratioX = (float)srcWidth / (float)targetWidth;
       float ratioY = (float)srcHeight / (float)targetHeight;
       float diffX;
       float diffY;
       
       for(targetX = 0; targetX < targetWidth; targetX++) {
           
           for(targetY = 0; targetY < targetHeight; targetY++) {
               
               srcX1 = (int)(ratioX * targetX);
               srcX2 = srcX1 + 1;
               srcY1 = (int)(ratioY * targetY);
               srcY2 = srcY1 + 1;
               diffX = (ratioX * targetX) - srcX1;
               diffY = (ratioY * targetY) - srcY1;

               pixelA = source[srcX1][srcY1];
               pixelB = (srcX2 >= 0 && srcX2 < srcWidth && srcY1 >= 0 && srcY1 < srcHeight) ? source[srcX2][srcY1] : pixelA;
               pixelC = (srcX1 >= 0 && srcX1 < srcWidth && srcY2 >= 0 && srcY2 < srcHeight) ? source[srcX1][srcY2] : pixelA;
               pixelD = (srcX2 >= 0 && srcX2 < srcWidth && srcY2 >= 0 && srcY2 < srcHeight) ? source[srcX2][srcY2] : pixelA;
               
               int alpha = (int)(((pixelA >> 24) & 0xFF) * (1.0F - diffX) * (1.0F - diffY) +
                                 ((pixelB >> 24) & 0xFF) * diffX * (1.0F - diffY) +
                                 ((pixelC >> 24) & 0xFF) * diffY * (1.0F - diffX) +
                                 ((pixelD >> 24) & 0xFF) * (diffX * diffY));
               int red = (int)(((pixelA >> 16) & 0xFF) * (1.0F - diffX) * (1.0F - diffY) +
                               ((pixelB >> 16) & 0xFF) * diffX * (1.0F - diffY) +
                               ((pixelC >> 16) & 0xFF) * diffY * (1.0F - diffX) +
                               ((pixelD >> 16) & 0xFF) * (diffX * diffY));
               int green = (int)(((pixelA >> 8) & 0xFF) * (1.0F - diffX) * (1.0F - diffY) +
                                 ((pixelB >> 8) & 0xFF) * diffX * (1.0F - diffY) +
                                 ((pixelC >> 8) & 0xFF) * diffY * (1.0F - diffX) +
                                 ((pixelD >> 8) & 0xFF) * (diffX * diffY));
               int blue = (int)((pixelA & 0xFF) * (1.0F - diffX) * (1.0F - diffY) +
                                (pixelB & 0xFF) * diffX * (1.0F - diffY) +
                                (pixelC & 0xFF) * diffY * (1.0F - diffX) +
                                (pixelD & 0xFF) * (diffX * diffY));
               
               target[targetX][targetY] = ((alpha & 0xFF) << 24) | ((red & 0xFF) << 16) | ((green & 0xFF) << 8) | (blue & 0xFF);
           }
       }
   };
 
Natürlich ist das ein Problem.

Du benutzt ja für Rot das höchste Bit. Nimm mal an du hättest mur 1 Byte. Dann wäre -1 * 0.5 sicher ein anderes Ergebnis als 255 * 0.5. Genau das passiert Dir mit dem Rotwert.

Gruß

Claus
 
Natürlich ist das ein Problem.

Du benutzt ja für Rot das höchste Bit. Nimm mal an du hättest mur 1 Byte. Dann wäre -1 * 0.5 sicher ein anderes Ergebnis als 255 * 0.5. Genau das passiert Dir mit dem Rotwert.

Gruß

Claus
Ich extrahiere den Rotwert erst aus dem pixel integer mit (pixel >> 16) & 0xFF und bekomme dadurch einen Wert zwischen 0 und 255.
 
@mrBrown Ich hätte noch eine ColorUtils Klasse. kannst den Geschwindigkeitstest gerne auch selber durchführen wenn du mir nicht glaubst 😉

Java:
/**
 * Provides methods for easier color manipulation.
 * @author Ralph Niemitz/RalleYTN(ralph.niemitz@gmx.de)
 * @version 1.0.0
 * @since 1.0.0
 */
public final class ColorUtils {

   private ColorUtils() {}
   
   /**
    * Extracts the alpha channel from a color.
    * @param argb the color
    * @return the alpha channel
    * @since 1.0.0
    */
   public static final int getAlpha(int argb) {
       
       return (argb >> 24) & 0xFF;
   }
   
   /**
    * Extracts the red channel from a color.
    * @param argb the color
    * @return the red channel
    * @since 1.0.0
    */
   public static final int getRed(int argb) {
       
       return (argb >> 16) & 0xFF;
   }
   
   /**
    * Extracts the green channel from a color.
    * @param argb the color
    * @return the green channel
    * @since 1.0.0
    */
   public static final int getGreen(int argb) {
       
       return (argb >> 8) & 0xFF;
   }
   
   /**
    * Extracts the blue channel from a color.
    * @param argb the color
    * @return the blue channel
    * @since 1.0.0
    */
   public static final int getBlue(int argb) {
       
       return argb & 0xFF;
   }
   
   /**
    * Builds a color.
    * @param red red channel of the color(0 - 255)
    * @param green green channel of the color(0 - 255)
    * @param blue blue channel of the color(0 - 255)
    * @param alpha alpha channel of the color(0 - 255)
    * @return the resulting color
    * @since 1.0.0
    */
   public static final int getARGB(int red, int green, int blue, int alpha) {
       
       return ((alpha & 0xFF) << 24) | ((red & 0xFF) << 16) | ((green & 0xFF) << 8) | (blue & 0xFF);
   }
   
   /**
    * Mixes to colors and returns the result.
    * @param argb1 color to mix with another
    * @param argb2 color with which the first color will be fixed
    * @param ratio the ratio with which the first color will be mixed into the second
    * @return the mixed color
    * @since 1.0.0
    */
   public static final int mix(int argb1, int argb2, float ratio) {
       
       float ratio2 = 1.0F - ratio;
       int alpha = (int)(((((argb1 >> 24) & 0xFF) * ratio) + (((argb2 >> 24) & 0xFF) * ratio2)) / 2);
       int red = (int)(((((argb1 >> 16) & 0xFF) * ratio) + (((argb2 >> 16) & 0xFF) * ratio2)) / 2);
       int green = (int)(((((argb1 >> 8) & 0xFF) * ratio) + (((argb2 >> 8) & 0xFF) * ratio2)) / 2);
       int blue = (int)((((argb1 & 0xFF) * ratio) + ((argb2 & 0xFF) * ratio2)) / 2);
       return (((alpha & 0xFF) << 24) | ((red & 0xFF) << 16) | ((green & 0xFF) << 8) | (blue & 0xFF));
   }
}
 
habs getestet. Wenn ich Methodenaufrufe nutze brauch ich für dieses spezielle Bild 2 Sekunden länger.
Vermutlich weil dein Test Unsinn war.
Die Methoden werden ziemlich sicher inlined, dann ist's egal.

Abgesehen davon: in den 3h, die's zum finden des problems brauchte, hätte man dann ja noch 5000 Bilder mit Overhead berechnen können 😉
 
Mit JMH, deine letzte Variante gegen meine mit Schleife und ausgelagerten Methoden:

deins: avgt 30 176856342,333 ± 1435157,678 ns/op
meins: avgt 30 140473352,260 ± 4764314,802 ns/op

Java:
public static final BiConsumer<int[][], int[][]> SCALE_BILINEAR_INTERPOLATION_LOOP = (source, target) -> {

        int srcWidth = source.length;
        int srcHeight = source[0].length;
        int targetWidth = target.length;
        int targetHeight = target[0].length;

        float ratioX = (float) srcWidth / (float) targetWidth;
        float ratioY = (float) srcHeight / (float) targetHeight;

        for (int targetX = 0; targetX < targetWidth; targetX++) {

            for (int targetY = 0; targetY < targetHeight; targetY++) {

                int srcX1 = (int) (ratioX * targetX);
                int srcX2 = srcX1 + 1;
                int srcY1 = (int) (ratioY * targetY);
                int srcY2 = srcY1 + 1;


                float diffX = (ratioX * targetX) - srcX1;
                float diffY = (ratioY * targetY) - srcY1;


                int pixelA = (source[srcX1][srcY1]);
                int pixelB = (inBounds(srcX2, srcY1, srcWidth, srcHeight)) ? (source[srcX2][srcY1]) : pixelA;
                int pixelC = (inBounds(srcX1, srcY2, srcWidth, srcHeight)) ? (source[srcX1][srcY2]) : pixelA;
                int pixelD = (inBounds(srcX2, srcY2, srcWidth, srcHeight)) ? (source[srcX2][srcY2]) : pixelA;

                for (int shift = 0; shift <= 24; shift += 8) {
                    target[targetX][targetY] += interpolate(pixelA, pixelB, pixelC, pixelD, shift, diffX, diffY);
                }
            }
        }
    };


    static boolean inBounds(int x, int y, int srcWidth, int srcHeight) {
        return x >= 0 && x < srcWidth && y >= 0 && y < srcHeight;
    }

    static int interpolate(int pixelA, int pixelB, int pixelC, int pixelD, int shift, float diffX, float diffY) {

        return (((int) (((pixelA >> shift) & 0xFF) * (1 - diffX) * (1 - diffY) + ((pixelB >> shift) & 0xFF) * diffX * (1 - diffY) + ((pixelC >> shift) & 0xFF) * diffY * (1 - diffX) + ((pixelD >> shift) & 0xFF) * (diffX * diffY))) << shift);

    }
 
Frage @mrBrown: Das Ergebnis sieht immernoch nicht besser aus oder? 😕
wir wissen ja jetzt, dass der Fehler irgendwo in der interpolation zustande kommt.

Ich muss alles an performance rausholen was geht, da ich screenshots auf einheitliche Größen bringen muss. wenn da jetzt jemand mit 3x4K Bildschirmen ankommt und nen screenshot macht merkt man die Verarbeitungsgeschwindigkeit.

Für mehr Geschwindigkeit wurde mir beigebracht:
1. verlass dich nicht auf automatische Optimierungen
2. weniger operationen = mehr geschwendigkeit, versuch dir vorzustellen wie der assembly code aussehen würde
 
Frage @mrBrown: Das Ergebnis sieht immernoch nicht besser aus oder? 😕
wir wissen ja jetzt, dass der Fehler irgendwo in der interpolation zustande kommt.
Zumindest ist ein Fehler aus dem Code oben nicht mehr drin, ich habs aber nicht mit nem echten Bild getestet , sondern nur mit 2x2 in weiß auf 4x4, da passte es.

Für mehr Geschwindigkeit wurde mir beigebracht:
1. verlass dich nicht auf automatische Optimierungen
2. weniger operationen = mehr geschwendigkeit, versuch dir vorzustellen wie der assembly code aussehen würde
Hier neue Regeln:
0. Vergiss was dir zu optimierung gesagt wurde.
2 Verlass dich auf automatische Optimierungen, die sind besser als deine.
3. schreib den Code schön, nicht kurz.
3.1. Wenn es dann, nachdem es funktioniert, irgendwann wirkliche Performanceprobleme gibt, kann man immer noch optimieren - dann aber mit sinnvollen Optimierungen.
 
Zuletzt bearbeitet:
The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

Donald Knuth
 
2. weniger operationen = mehr geschwendigkeit, versuch dir vorzustellen wie der assembly code aussehen würde
Sobald dein Code durch einen Interpreter oder Compiler geht kannst du dir kaum noch vorstellen was da am Ende rauskommt. Der Code wird in eine Zwischendarstellung übertragen auf dem der Compiler Optimierungen wie inlining (schon genannt), loop-unrolling, lokale Optimierungen (entfernen lokaler gemeinsamer Teilausdrücke, umordnung voneinander unabhängiger Anweisungen, Umformungen mit algebraischen Gesetzen), Konstantenfaltung, Kopierpropagation, Codeverschiebung und vielen vielen weiteren durchführt.

- Hast du schon mal an Parallelisierung gedacht/ausprobiert?
 
Irgendwie habe ich es geschafft.... 😕 Ich weiss jedoch nicht wie 😕
Hab's jetzt ausgelagert und auf einmal ging's....

Hier der Code:
Java:
    public static final BiConsumer<int[][], int[][]> SCALE_BILINEAR_INTERPOLATION = (source, target) -> {
       
       int srcWidth = source.length;
       int srcHeight = source[0].length;
       int targetWidth = target.length;
       int targetHeight = target[0].length;
       
       float ratioX = (float)srcWidth / (float)targetWidth;
       float ratioY = (float)srcHeight / (float)targetHeight;
       
       for(int targetX = 0; targetX < targetWidth; targetX++) {
           
           for(int targetY = 0; targetY < targetHeight; targetY++) {
               
               int srcX1 = (int)(ratioX * targetX);
               int srcX2 = srcX1 + 1;
               int srcY1 = (int)(ratioY * targetY);
               int srcY2 = srcY1 + 1;
               
               float diffX = (ratioX * targetX) - srcX1;
               float diffY = (ratioY * targetY) - srcY1;

               int pixelA = source[srcX1][srcY1];
               int pixelB = SimpleImage.__inBounds(srcX2, srcY1, 0, 0, srcWidth, srcHeight) ? source[srcX2][srcY1] : pixelA;
               int pixelC = SimpleImage.__inBounds(srcX1, srcY2, 0, 0, srcWidth, srcHeight) ? source[srcX1][srcY2] : pixelA;
               int pixelD = SimpleImage.__inBounds(srcX2, srcY2, 0, 0, srcWidth, srcHeight) ? source[srcX2][srcY2] : pixelA;

               int alpha = ColorUtils.interpolate(pixelA, pixelB, pixelC, pixelD, diffX, diffY, ColorUtils.CHANNEL_ALPHA);
               int red = ColorUtils.interpolate(pixelA, pixelB, pixelC, pixelD, diffX, diffY, ColorUtils.CHANNEL_RED);
               int green = ColorUtils.interpolate(pixelA, pixelB, pixelC, pixelD, diffX, diffY, ColorUtils.CHANNEL_GREEN);
               int blue = ColorUtils.interpolate(pixelA, pixelB, pixelC, pixelD, diffX, diffY, ColorUtils.CHANNEL_BLUE);
               
               target[targetX][targetY] = ColorUtils.getARGB(red, green, blue, alpha);
           }
       }
   };

    static final boolean __inBounds(int posX, int posY, int boundsX, int boundsY, int boundsWidth, int boundsHeight) {
       
       return posX >= boundsX && posX < boundsX + boundsWidth && posY >= boundsY && posY < boundsY + boundsHeight;
   }

   public static final int CHANNEL_ALPHA = 24;
   public static final int CHANNEL_RED = 16;
   public static final int CHANNEL_GREEN = 8;
   public static final int CHANNEL_BLUE = 0;

    public static final int interpolate(int pixelA, int pixelB, int pixelC, int pixelD, float diffX, float diffY, int channel) {
       
       float diffX2 = 1.0F - diffX;
       float diffY2 = 1.0F - diffY;
       
       int pixelAChannel = (pixelA >> channel) & 0xFF;
       int pixelBChannel = (pixelB >> channel) & 0xFF;
       int pixelCChannel = (pixelC >> channel) & 0xFF;
       int pixelDChannel = (pixelD >> channel) & 0xFF;
       
       float pixelAChannelPart = pixelAChannel * diffX2 * diffY2;
       float pixelBChannelPart = pixelBChannel * diffX * diffY2;
       float pixelCChannelPart = pixelCChannel * diffX2 * diffY;
       float pixelDChannelPart = pixelDChannel * diffX * diffY;
       
       return (int)(pixelAChannelPart + pixelBChannelPart + pixelCChannelPart + pixelDChannelPart);
   }

    public static final int getARGB(int red, int green, int blue, int alpha) {
       
       return ((alpha & 0xFF) << 24) | ((red & 0xFF) << 16) | ((green & 0xFF) << 8) | (blue & 0xFF);
   }
 
mach ich mit Methoden die nirgends richtig in die Klassennamen passen.
Soll signalisieren, dass die methode unter umständen noch verschoben wird.
 
Na das ist doch der Punkt, will man jedes Mal an einem hässlichem Namen sehen, dass die Methode noch gar nicht "richtig" ist?
Außerdem: ein "__" ist einfach völlig nichtssagend für jeden außer dir, und du selbst gewinnst doch überhaupt nichts, wenn du weißt dass die verschoben wird, das händelt eh die IDE - und wenn ist ein TODO mit IDE-Unterstützung doch besser 😉
Sinnvoll ist so ein Hinweis doch nur, wenn er für Nutzer der API verständlich ist, und da ist es doch wesentlich sinnvoller, sich auf verständliche und gebräuchliche Dinge zu verlassen 😉
 
Zuletzt bearbeitet:

Zurück
Oben