Problème
Un atelier de retouche photo vous demande de faire ressortir les contours d'une image en niveaux de gris. Chaque pixel est une luminosité de 0 (noir) à 255 (blanc). Pour chaque pixel, regardez son voisinage 3 × 3 et calculez deux sommes pondérées avec les noyaux de Sobel :
Gx = -1 0 1 Gy = -1 -2 -1
-2 0 2 0 0 0
-1 0 1 1 2 1Le centre du noyau se place sur le pixel, sa ligne du haut sur la ligne au-dessus et sa colonne de gauche sur la colonne de gauche. Multipliez chaque voisin par le coefficient correspondant et additionnez le tout pour obtenir gx et gy. Lorsqu'un voisin tombe hors de l'image, utilisez à sa place le pixel du bord le plus proche (on ramène la ligne dans 0 … rows − 1 et la colonne dans 0 … cols − 1). L'intensité du contour vaut min(255, |gx| + |gy|), c'est donc toujours un entier entre 0 et 255. Lisez toujours l'image d'origine, jamais des pixels déjà modifiés.
Implémentez edge_detection(image).
Entrée
image : l'image sous forme de liste de lignes ; toutes les lignes ont la même longueur.
Sortie
Renvoyez une nouvelle grille de même taille où chaque valeur est l'intensité de contour du pixel correspondant.
Contraintes
1 ≤ rows, cols ≤ 50
0 ≤ pixel ≤ 255
Exemples
Entrée :
image = [
[10, 10, 10],
[10, 10, 10],
[10, 10, 10]
]
Sortie attendue :
expected = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
Entrée :
std::vector<std::vector<long long>> image = {
{10, 10, 10},
{10, 10, 10},
{10, 10, 10}
};
Sortie attendue :
std::vector<std::vector<long long>> expected = {
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}
};
Entrée :
long[][] image = new long[][] {
new long[] {10, 10, 10},
new long[] {10, 10, 10},
new long[] {10, 10, 10}
};
Sortie attendue :
long[][] expected = new long[][] {
new long[] {0, 0, 0},
new long[] {0, 0, 0},
new long[] {0, 0, 0}
};
Explication
Tous les voisinages sont uniformes, donc les deux sommes valent 0 partout et le résultat ne contient que des zéros.
Entrée :
image = [
[0, 0, 100],
[0, 0, 100],
[0, 0, 100]
]
Sortie attendue :
expected = [
[0, 255, 255],
[0, 255, 255],
[0, 255, 255]
]
Entrée :
std::vector<std::vector<long long>> image = {
{0, 0, 100},
{0, 0, 100},
{0, 0, 100}
};
Sortie attendue :
std::vector<std::vector<long long>> expected = {
{0, 255, 255},
{0, 255, 255},
{0, 255, 255}
};
Entrée :
long[][] image = new long[][] {
new long[] {0, 0, 100},
new long[] {0, 0, 100},
new long[] {0, 0, 100}
};
Sortie attendue :
long[][] expected = new long[][] {
new long[] {0, 255, 255},
new long[] {0, 255, 255},
new long[] {0, 255, 255}
};
Explication
Pour le pixel du milieu, la colonne de droite apporte 100 + 200 + 100 = 400 et celle de gauche 0, donc gx = 400, gy = 0 et l'intensité est plafonnée à 255. Les pixels de la colonne de droite obtiennent aussi 255, car leurs voisins de droite manquants reprennent la valeur du bord, 100. Les pixels de la colonne de gauche ne voient que des 0 des deux côtés, donc ils restent à 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Écrivez une fonction auxiliaire qui renvoie le pixel en (r, c) après avoir ramené r et c dans la grille.
Indice 2
gx n'utilise que les colonnes de gauche et de droite du voisinage ; gy, que les lignes du haut et du bas.
Indice 3
Construisez la sortie dans une grille séparée ; modifier l'entrée au fur et à mesure fausserait les pixels suivants.
Complexité attendue
temps O(rows × cols), espace supplémentaire O(rows × cols)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.