Problema
Un laboratorio di fotoritocco ti chiede di evidenziare i bordi in un'immagine in scala di grigi. Ogni pixel è una luminosità da 0 (nero) a 255 (bianco). Per ogni pixel, considera il suo intorno 3 × 3 e calcola due somme pesate con i kernel di Sobel:
Gx = -1 0 1 Gy = -1 -2 -1
-2 0 2 0 0 0
-1 0 1 1 2 1Il centro del kernel va sul pixel, la sua riga superiore sulla riga sopra e la sua colonna sinistra sulla colonna a sinistra. Moltiplica ogni vicino per il peso corrispondente e somma tutto per ottenere gx e gy. Se un vicino cade fuori dall'immagine, usa al suo posto il pixel di bordo più vicino (limita la riga all'intervallo 0 … rows − 1 e la colonna a 0 … cols − 1). L'intensità del bordo è min(255, |gx| + |gy|), quindi resta un intero tra 0 e 255. Leggi sempre dall'immagine originale, mai da pixel che hai già modificato.
Implementa edge_detection(image).
Input
image: l'immagine come lista di righe; tutte le righe hanno la stessa lunghezza.
Output
Restituisci una nuova griglia delle stesse dimensioni in cui ogni valore è l'intensità del bordo di quel pixel.
Vincoli
1 ≤ rows, cols ≤ 50
0 ≤ pixel ≤ 255
Esempi
Input:
image = [
[10, 10, 10],
[10, 10, 10],
[10, 10, 10]
]
Output atteso:
expected = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
Input:
std::vector<std::vector<long long>> image = {
{10, 10, 10},
{10, 10, 10},
{10, 10, 10}
};
Output atteso:
std::vector<std::vector<long long>> expected = {
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}
};
Input:
long[][] image = new long[][] {
new long[] {10, 10, 10},
new long[] {10, 10, 10},
new long[] {10, 10, 10}
};
Output atteso:
long[][] expected = new long[][] {
new long[] {0, 0, 0},
new long[] {0, 0, 0},
new long[] {0, 0, 0}
};
Spiegazione
Ogni intorno è uniforme, quindi entrambe le somme valgono 0 ovunque e il risultato è tutto a zero.
Input:
image = [
[0, 0, 100],
[0, 0, 100],
[0, 0, 100]
]
Output atteso:
expected = [
[0, 255, 255],
[0, 255, 255],
[0, 255, 255]
]
Input:
std::vector<std::vector<long long>> image = {
{0, 0, 100},
{0, 0, 100},
{0, 0, 100}
};
Output atteso:
std::vector<std::vector<long long>> expected = {
{0, 255, 255},
{0, 255, 255},
{0, 255, 255}
};
Input:
long[][] image = new long[][] {
new long[] {0, 0, 100},
new long[] {0, 0, 100},
new long[] {0, 0, 100}
};
Output atteso:
long[][] expected = new long[][] {
new long[] {0, 255, 255},
new long[] {0, 255, 255},
new long[] {0, 255, 255}
};
Spiegazione
Per il pixel centrale la colonna destra contribuisce con 100 + 200 + 100 = 400 e quella sinistra con 0, quindi gx = 400, gy = 0 e l'intensità viene limitata a 255. Anche i pixel della colonna destra ottengono 255, perché i vicini mancanti a destra copiano il valore di bordo 100. I pixel della colonna sinistra vedono solo 0 da entrambi i lati, quindi restano 0.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Scrivi una funzione di supporto che restituisca il pixel in (r, c) dopo aver riportato r e c dentro la griglia.
Suggerimento 2
gx usa solo la colonna sinistra e quella destra dell'intorno; gy solo la riga superiore e quella inferiore.
Suggerimento 3
Costruisci l'output in una griglia separata: modificare l'input strada facendo rovina i pixel successivi.
Complessità attesa
tempo O(rows × cols), spazio aggiuntivo O(rows × cols)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.