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 1Die 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
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.
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.