Alle Herausforderungen
Schwierig 0 gelöst 0% Erfolgsquote

Kantenerkennung (Sobel-Filter)

Wende den Sobel-Filter auf ein Graustufenbild an und gib für jedes Pixel die Kantenstärke zurück.

Das lernst du

  • Die 3 × 3-Umgebung jeder Zelle besuchen
  • Randpixel durch Begrenzen der Koordinaten behandeln
  • Ergebnisse in ein neues Raster schreiben, damit die Eingabe erhalten bleibt

Problem

Ein Fotolabor möchte in einem Graustufenbild die Kanten hervorheben. Jedes Pixel ist eine Helligkeit von 0 (schwarz) bis 255 (weiß). Betrachte für jedes Pixel seine 3 × 3-Umgebung und berechne mit den Sobel-Operatoren zwei gewichtete Summen:

Gx = -1  0  1      Gy = -1 -2 -1
     -2  0  2            0  0  0
     -1  0  1            1  2  1

Die Mitte der Matrix liegt auf dem Pixel, ihre obere Zeile auf der Zeile darüber und ihre linke Spalte auf der Spalte links davon. Multipliziere jeden Nachbarn mit dem passenden Gewicht und addiere alles auf, so erhältst du gx und gy. Liegt ein Nachbar außerhalb des Bilds, nimm stattdessen das nächstgelegene Randpixel (begrenze die Zeile auf 0 … rows − 1 und die Spalte auf 0 … cols − 1). Die Kantenstärke ist min(255, |gx| + |gy|) und damit immer eine ganze Zahl zwischen 0 und 255. Lies immer aus dem ursprünglichen Bild, nie aus Pixeln, die du schon verändert hast.

Implementiere edge_detection(image).

Eingabe

image: Das Bild als Liste von Zeilen; alle Zeilen sind gleich lang.

Ausgabe

Gib ein neues Raster derselben Größe zurück, in dem jeder Wert die Kantenstärke des jeweiligen Pixels ist.

Einschränkungen

1 ≤ rows, cols ≤ 50

0 ≤ Pixel ≤ 255

Beispiele

Beispiel 1
Eingabe:
image = [
    [10, 10, 10],
    [10, 10, 10],
    [10, 10, 10]
]

Erwartete Ausgabe:
expected = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
Eingabe:
std::vector<std::vector<long long>> image = {
    {10, 10, 10},
    {10, 10, 10},
    {10, 10, 10}
};

Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {
    {0, 0, 0},
    {0, 0, 0},
    {0, 0, 0}
};
Eingabe:
long[][] image = new long[][] {
    new long[] {10, 10, 10},
    new long[] {10, 10, 10},
    new long[] {10, 10, 10}
};

Erwartete Ausgabe:
long[][] expected = new long[][] {
    new long[] {0, 0, 0},
    new long[] {0, 0, 0},
    new long[] {0, 0, 0}
};

Erläuterung

Jede Umgebung ist einfarbig, also sind beide Summen überall 0 und das Ergebnis besteht nur aus Nullen.

Beispiel 2
Eingabe:
image = [
    [0, 0, 100],
    [0, 0, 100],
    [0, 0, 100]
]

Erwartete Ausgabe:
expected = [
    [0, 255, 255],
    [0, 255, 255],
    [0, 255, 255]
]
Eingabe:
std::vector<std::vector<long long>> image = {
    {0, 0, 100},
    {0, 0, 100},
    {0, 0, 100}
};

Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {
    {0, 255, 255},
    {0, 255, 255},
    {0, 255, 255}
};
Eingabe:
long[][] image = new long[][] {
    new long[] {0, 0, 100},
    new long[] {0, 0, 100},
    new long[] {0, 0, 100}
};

Erwartete Ausgabe:
long[][] expected = new long[][] {
    new long[] {0, 255, 255},
    new long[] {0, 255, 255},
    new long[] {0, 255, 255}
};

Erläuterung

Beim mittleren Pixel trägt die rechte Spalte 100 + 200 + 100 = 400 bei und die linke 0, also ist gx = 400, gy = 0, und die Stärke wird auf 255 begrenzt. Die Pixel in der rechten Spalte bekommen ebenfalls 255, weil ihre fehlenden rechten Nachbarn den Randwert 100 übernehmen. Die Pixel in der linken Spalte sehen auf beiden Seiten nur 0 und bleiben deshalb 0.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Schreib eine Hilfsfunktion, die das Pixel an (r, c) zurückgibt, nachdem r und c auf das Raster begrenzt wurden.

Hinweis 2

gx verwendet nur die linke und die rechte Spalte der Umgebung, gy nur die obere und die untere Zeile.

Hinweis 3

Bau die Ausgabe in einem separaten Raster auf; veränderst du die Eingabe unterwegs, stimmen spätere Pixel nicht mehr.

Erwartete Komplexität

Zeit O(rows × cols), zusätzlicher Speicher O(rows × cols)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.