Todos os desafios
Difícil 0 resolvidos 0% de aceitação

Detecção de bordas (filtro de Sobel)

Aplique o filtro de Sobel a uma grade de pixels em tons de cinza e retorne a intensidade de borda de cada pixel.

O que você vai aprender

  • Visitar a vizinhança 3 × 3 de cada célula
  • Tratar pixels da borda limitando as coordenadas
  • Escrever os resultados em uma nova grade para não sobrescrever a entrada

Problema

Ver original (inglês)

Um laboratório de edição de fotos pede que você destaque as bordas de uma imagem em tons de cinza. Cada pixel é um brilho de 0 (preto) a 255 (branco). Para cada pixel, olhe a sua vizinhança 3 × 3 e calcule duas somas ponderadas com os kernels (máscaras) de Sobel:

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

O centro do kernel fica sobre o pixel, a linha de cima do kernel sobre a linha acima e a coluna da esquerda sobre a coluna à esquerda. Multiplique cada vizinho pelo peso correspondente e some tudo para obter gx e gy. Quando um vizinho cair fora da imagem, use o pixel mais próximo da borda no lugar dele (limite a linha a 0 … rows − 1 e a coluna a 0 … cols − 1). A intensidade da borda é min(255, |gx| + |gy|), então ela é sempre um inteiro entre 0 e 255. Leia sempre da imagem original, nunca de pixels que você já alterou.

Implemente edge_detection(image).

Entrada

image: a imagem como uma lista de linhas; todas as linhas têm o mesmo tamanho.

Saída

Retorne uma nova grade do mesmo tamanho em que cada valor é a intensidade de borda daquele pixel.

Restrições

1 ≤ rows, cols ≤ 50

0 ≤ pixel ≤ 255

Exemplos

Exemplo 1
Entrada:
image = [
    [10, 10, 10],
    [10, 10, 10],
    [10, 10, 10]
]

Saída esperada:
expected = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
Entrada:
std::vector<std::vector<long long>> image = {
    {10, 10, 10},
    {10, 10, 10},
    {10, 10, 10}
};

Saída esperada:
std::vector<std::vector<long long>> expected = {
    {0, 0, 0},
    {0, 0, 0},
    {0, 0, 0}
};
Entrada:
long[][] image = new long[][] {
    new long[] {10, 10, 10},
    new long[] {10, 10, 10},
    new long[] {10, 10, 10}
};

Saída esperada:
long[][] expected = new long[][] {
    new long[] {0, 0, 0},
    new long[] {0, 0, 0},
    new long[] {0, 0, 0}
};

Explicação

Todas as vizinhanças são uniformes, então as duas somas dão 0 em todo lugar e o resultado é só de zeros.

Exemplo 2
Entrada:
image = [
    [0, 0, 100],
    [0, 0, 100],
    [0, 0, 100]
]

Saída esperada:
expected = [
    [0, 255, 255],
    [0, 255, 255],
    [0, 255, 255]
]
Entrada:
std::vector<std::vector<long long>> image = {
    {0, 0, 100},
    {0, 0, 100},
    {0, 0, 100}
};

Saída esperada:
std::vector<std::vector<long long>> expected = {
    {0, 255, 255},
    {0, 255, 255},
    {0, 255, 255}
};
Entrada:
long[][] image = new long[][] {
    new long[] {0, 0, 100},
    new long[] {0, 0, 100},
    new long[] {0, 0, 100}
};

Saída esperada:
long[][] expected = new long[][] {
    new long[] {0, 255, 255},
    new long[] {0, 255, 255},
    new long[] {0, 255, 255}
};

Explicação

No pixel do meio, a coluna da direita soma 100 + 200 + 100 = 400 e a da esquerda soma 0, então gx = 400, gy = 0 e a intensidade é limitada a 255. Os pixels da coluna da direita também ficam com 255, porque os vizinhos da direita que faltam copiam o valor 100 da borda. Os pixels da coluna da esquerda só veem 0 dos dois lados, então continuam 0.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Escreva uma função auxiliar que retorna o pixel em (r, c) depois de limitar r e c aos limites da grade.

Dica 2

gx usa só as colunas da esquerda e da direita da vizinhança; gy, só as linhas de cima e de baixo.

Dica 3

Monte a saída em uma grade separada; alterar a entrada no meio do caminho estraga os pixels seguintes.

Complexidade esperada

tempo O(rows × cols), espaço extra O(rows × cols)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.