Algorithmen implementieren

[RezaScript]

Hallo, ich müsste bald einen Test schreiben und nur das ist die Information, die ich habe:

Für die Programmiersprache bitten wir die Schüler, über gute Programmierkenntnisse zu verfügen. Der Student muss in der Lage sein, Algorithmen zu verstehen und zu implementieren, die in wissenschaftlichen Arbeiten vorgestellt werden. Ein einfaches Beispiel könnte der Algorithmus "Integral Image" sein, der unter anderem auf Wikipedia vorgestellt wird: https://en.wikipedia.org/wiki/Summed-area_table.

Was versteht ihr darunter? Oder wie würdet ihr den Algorithmus "Integral Image" implementieren?

 

[kneitzel]

Du hast doch schon einen Link zitiert, der den Algorithmus beschreibt. So würde ich das dann auch umsetzen.
Da ist ja eine Single Pass Over Formel angegeben, d.h. einmal über alle Felder laufen und genau das für jedes Feld berechnen und du bist fertig.

I wäre das 2D Result Array, i die Eingabe ...

 

[mihe7]

Naja, das steht ja schon in der Wiki-Seite: jeder Eintrag an Position (x,y) des Integral Image ist die Summe aller Pixel im Bild, die überhalb und links von (x,y) liegen.

Interessant ist die zweite Formel: I(x,y) = i(x,y) + I(x, y-1) + I(x-1, y) - I(x-1, y-1). Diese erlaubt es, den Spaß sehr einfach zu implementieren.

Hier mal etwas over-engineered

Erstmal führen wir für Bilder eine Abstraktion ein:

public interface Image {
    /** liefert den Wert des Pixels x,y oder value, falls x,y kein Pixel des Bilds ist. */
    int orElseGet(int x, int y, int value);
    int getWidth();
    int getHeight();
}

Damit bauen wir ein IntegralImage:

public class IntegralImage implements Image {
    private final int height;
    private final int width;
    private final int[][] image;

    public IntegralImage(Image img) {
        height = img.getHeight();
        width = img.getWidth();
        this.image = new int[height][width];

        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                image[y][x] = img.orElseGet(x, y, 0) + orElseGet(x, y-1, 0) + orElseGet(x-1, y, 0) - orElseGet(x-1, y-1, 0);
            }
        }
    }

    @Override public int getWidth() { return width; }
    @Override public int getHeight() { return height; }

    @Override public final int orElseGet(int x, int y,  int value) {
        return (x >= 0 && y >= 0 && y < height && x < width) ? image[y][x] : value;
    }
}