Diskrete Faltung (Matrix) Randfälle

[bling10]

Hallo zusammen

Grob gesagt möchte ich Bilder (PGM-Datei) filtern, und zwar so:
Ich habe ein Eingabebild (2d-Array). Auf diese Matrix wird dann eine Kernelmatrix angewendet.
Dabei wird jeder Pixel des Ursprungsbildes durch eine Linearkombination seiner Nachbarschaft und sich selbst ersetzt. Die Einträge der Kernelmatrix stellen dabei die Gewichte dieser Linearkombination dar. Bezeichnen wir A als Ausgangsbild und mit A(i,j) den Pixel in der i-ten Zeile und in der j-ten Spalte, dann ist die diskrete Faltung definiert als: A ∶= B ∗ K. Die neuen Pixelwerte des Ausgangsbildes berechnen sich durch:


A(i, j) = ∑ ∑ B(i + x − a1, j + y − a2) ⋅ K(x, y), Summezeichen: jeweils von x=1 (y=1) nach n


In der Formel oben steht dabei n für die Filtergröße, a1 für die x-Koordinate und a2 für die y-Koordinate des Kernelmittelpunktes.

Hilfreicher Link: hier

Ich hab nun eine Methode linearFilter(Image image, float [][] kernel) wobei Image ein Objekt mit folgenden fertigen Methoden ist: getData() liefert float[][], getHeight(), getWidth, getPixel(height,width), setPixel(float value, int heigth, int width).

so sieht nun meine linearFilter-Methode aus:

    /**
     * This method implements a linear filter with discrete convolution
     *
     * @param image  the image which should be filtered
     * @param kernel the kernel used for the linear filter
     * @return the filtered image
     */
    public Image linearFilter(Image image, float[][] kernel) {

        Image filtered = image.clone();

        // TODO
        int n = kernel[0].length; // erlaubt, da kernel immer nxn
        int i = 0;
        int j = 0;
        int x = 0;
        int y = 0;
        int a1 = (int) Math.floor(n / 2);
        int a2 = (int) Math.floor(n / 2);

        for (i = 0; i < filtered.getData().length; i++) {
            for (j = 0; j < filtered.getData()[0].length; j++) {
                for (x = 0; x < n; x++) {
                    for (y = 0; y < n; y++) { 
                        filtered.getData()[i][j] = image.getData()[i + x - a1][j + y - a2] * kernel[x][y];
                    }
                }
            }
        }
        return filtered;
    }

So weit so gut. Das GROßE PROBLEM und meine Frage:
Ich soll den Bildrand folgendermaßen Behandeln:
Für Pixelwerte am Rand ist der Kernel eventuell zu groß und greift ins Leere. Dafür wird eine sogenannte Randbehandlungsstrategie benötigt. Die Werte außerhalb des Bildrandes werden dann einfach dem Wert des örtlich nöchsten Nachbarns auf dem Bildrand gleichgesetzt. Betrachten Sie folgende für diesen Spezialfall.


Ich hab verstanden was zu tun ist, aber keine (sinnvolle/ absehbar lösbare) Idee wie ich dies nun umsetzen kann. Ein 2d-Array hat ja keine "-1"-Indizes, wo ich einfach die werte reinpacken kann. Und eine neue Matrix mit zwei dimensionen größer (für 3x3 Kernel, anders wenn dieser 5x5 oder so ist) mit erstellen, wo das bild in der "mitte" ist stell ich mir auch schwierig vor, sodass ich dann den kernel nicht ab [0][0] laufen lassen muss.

Hätte jemand dafür eine idee und stimmt mein Ansatz soweit?
Tausend Dank für jede Antwort!

 

[httpdigest]

Einfach als Koordinate `max(0, min(imageWidth-1, x))` (und analog für die y Koordinate) verwenden.
Du kannst also selbstverständlich nicht einfach das Bildarray bei `[i + x - a1][j + y - a2]` lesen, sondern musst die Koordinaten entsprechend beschränken.

 

[thecain]

entweder "vergrösserst" du das ursprungsbild und kopierst die Randpixel oder du behandelst die Fälle wenn dein Index negativ oder grösser als das Array wäre.

Oder versteh ich die Frage falsch?

 

[bling10]

entweder "vergrösserst" du das ursprungsbild und kopierst die Randpixel oder du behandelst die Fälle wenn dein Index negativ oder grösser als das Array wäre.

Oder versteh ich die Frage falsch?

Ja das wäre auch meine Idee aber ich weiß nicht wie ich das umsetzten soll. Der Kernel kann ja auch größer als 3x3 sein und dann müsste man auch einen dementsprechend großen rand bauen oder?

 

[bling10]

Einfach als Koordinate `max(0, min(imageWidth-1, x))` (und analog für die y Koordinate) verwenden.
Du kannst also selbstverständlich nicht einfach das Bildarray bei `[i + x - a1][j + y - a2]` lesen, sondern musst die Koordinaten entsprechend beschränken.

Aber die randfälle sollen auch berechnet werden oder verstehe ich dich falsch?

 

[httpdigest]

Aber die randfälle sollen auch berechnet werden oder verstehe ich dich falsch?

Das "Clampen" der Indizes sorgt ja gerade dafür, dass die Randfälle immer auf den nähesten gültigen Index gehen und somit auch die Randfälle (darum geht es ja gerade) korrekt berechnet werden...
Wenn du also auf Arrayfeld [-1][-1] zugreifen würdest, sorgt das Clamping dafür, dass du eben auf [0][0] zugreifst.

EDIT: Oder das ganze als Code:

...
int width = filtered.getData().length;
int height = filtered.getData()[0].length;
for (i = 0; i < width; i++) {
  for (j = 0; j < height; j++) {
    for (x = 0; x < n; x++) {
      for (y = 0; y < n; y++) { 
        int ix = i + x - a1; // <- wie in deinem Code
        int iy = j + y - a2; // <- wie in deinem Code
        int cix = Math.max(0, Math.min(ix, width - 1)); // <- Index auf gültige Positionen beschränken
        int ciy = Math.max(0, Math.min(iy, height - 1)); // <- Index auf gültige Positionen beschränken
        filtered.getData()[i][j] = image.getData()[cix][ciy] * kernel[x][y];
      }
    }
  }
}

 

[bling10]

Das "Clampen" der Indizes sorgt ja gerade dafür, dass die Randfälle immer auf den nähesten gültigen Index gehen und somit auch die Randfälle (darum geht es ja gerade) korrekt berechnet werden...
Wenn du also auf Arrayfeld [-1][-1] zugreifen würdest, sorgt das Clamping dafür, dass du eben auf [0][0] zugreifst.

EDIT: Oder das ganze als Code:

...
int width = filtered.getData().length;
int height = filtered.getData()[0].length;
for (i = 0; i < width; i++) {
  for (j = 0; j < height; j++) {
    for (x = 0; x < n; x++) {
      for (y = 0; y < n; y++) {
        int ix = i + x - a1; // <- wie in deinem Code
        int iy = j + y - a2; // <- wie in deinem Code
        int cix = Math.max(0, Math.min(ix, width - 1)); // <- Index auf gültige Positionen beschränken
        int ciy = Math.max(0, Math.min(iy, height - 1)); // <- Index auf gültige Positionen beschränken
        filtered.getData()[i][j] = image.getData()[cix][ciy] * kernel[x][y];
      }
    }
  }
}

Danke @httpdigest aber meine Tests dazu laufen leider nicht durch..

Das wären die Tests:

public class ImageFilterStudentTest {

    Filter filter = new Filter();
    static Image beer;
    static Image cat;
    static Image mandarine;
    static Image cow;
    static float[][] sharpKernel = { { 0, -1, 0 }, { -1, 5, -1 }, { 0, -1, 0 } };
    static float[][] blurKernel = { { 1 * 1 / 16f, 2 * 1 / 16f, 1 * 1 / 16f },
            { 2 * 1 / 16f, 4 * 1 / 16f, 2 * 1 / 16f }, { 1 * 1 / 16f, 2 * 1 / 16f, 1 * 1 / 16f } };

    @Test
    public void testLinearFilterNormal() {
        Image beer_sharp = filter.linearFilter(beer, sharpKernel);
        Image cat_blur = filter.linearFilter(cat, blurKernel);
        assertEquals(26, beer_sharp.getPixel(10, 10), 0f);
        assertEquals(21,beer_sharp.getPixel(56, 34), 0f);
        assertEquals(140,cat_blur.getPixel(77, 77), 0f);
        assertEquals(93,cat_blur.getPixel(33, 11), 0f);
    }

    @Test
    public void testLinearFilterEdge() {
        Image beer_blur = filter.linearFilter(beer, blurKernel);
        Image cat_sharp = filter.linearFilter(cat, sharpKernel);
        assertEquals(25, beer_blur.getPixel(0, 0), 0f);
        assertEquals(24, beer_blur.getPixel(47, 0), 0f);
        assertEquals(54, cat_sharp.getPixel(cat_sharp.getHeight() - 1, cat_sharp.getWidth() - 1), 0f);
        assertEquals(86, cat_sharp.getPixel(0, cat_sharp.getWidth() - 1), 0f);
    }

    @Test
    public void testLinearFilterPicture() throws IOException {
        Path mandarineBlurPath = Paths.get("Mandarine_blur.pgm");
        Image mandarine_blur_solution = new Image(mandarineBlurPath);
        Image mandarine_blur = filter.linearFilter(mandarine, blurKernel);
        assertArrayEquals(mandarine_blur.getData(),mandarine_blur_solution.getData());
    }
}

Und für z.B. den testLinearFilterNormal kommt dieser Failure



LG!

 

[httpdigest]

Aha. Es ist offensichtlich unmöglich, ohne den kompletten zu testenden Code, den kompletten Testcode und die Testdaten irgendeinen Fehler zu reproduzieren. Du wirst wohl selber schauen müssen.

 

[bling10]

Aha. Es ist offensichtlich unmöglich, ohne den kompletten zu testenden Code, den kompletten Testcode und die Testdaten irgendeinen Fehler zu reproduzieren. Du wirst wohl selber schauen müssen.

Da hast du wohl recht