Problema
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 1O 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
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.
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.