Tous les défis
Difficile 0 résolus 0 % de réussite

Détection de contours (filtre de Sobel)

Appliquez le filtre de Sobel à une grille de pixels en niveaux de gris et renvoyez l'intensité de contour de chaque pixel.

Ce que vous allez apprendre

  • Parcourir le voisinage 3 × 3 de chaque cellule
  • Gérer les pixels du bord en ramenant les coordonnées dans la grille
  • Écrire les résultats dans une nouvelle grille pour ne pas écraser l'entrée

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  1

Le 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

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

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.