Лаборатория обработки фотографий просит вас выделить границы на изображении в оттенках серого. Каждый пиксель - это яркость от 0 (чёрный) до 255 (белый). Для каждого пикселя рассмотрите его окрестность 3 × 3 и вычислите две взвешенные суммы с ядрами Собеля:
Gx = -1 0 1 Gy = -1 -2 -1
-2 0 2 0 0 0
-1 0 1 1 2 1Центр ядра совмещается с пикселем, верхняя строка ядра - со строкой выше, а левый столбец - со столбцом слева. Умножьте каждого соседа на соответствующий вес и сложите, чтобы получить gx и gy. Если сосед выходит за пределы изображения, вместо него возьмите ближайший пиксель на границе (ограничьте номер строки диапазоном 0 … rows − 1, а номер столбца диапазоном 0 … cols − 1). Сила границы равна min(255, |gx| + |gy|), так что это целое число от 0 до 255. Всегда читайте значения из исходного изображения, а не из уже изменённых пикселей.
Реализуйте edge_detection(image).
Входные данные
image: изображение в виде списка строк; все строки одной длины.
Выходные данные
Верните новую сетку того же размера, где каждое значение - сила границы в этом пикселе.
Ограничения
1 ≤ rows, cols ≤ 50
0 ≤ пиксель ≤ 255
Примеры
Ввод:
image = [
[10, 10, 10],
[10, 10, 10],
[10, 10, 10]
]
Ожидаемый вывод:
expected = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
Ввод:
std::vector<std::vector<long long>> image = {
{10, 10, 10},
{10, 10, 10},
{10, 10, 10}
};
Ожидаемый вывод:
std::vector<std::vector<long long>> expected = {
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}
};
Ввод:
long[][] image = new long[][] {
new long[] {10, 10, 10},
new long[] {10, 10, 10},
new long[] {10, 10, 10}
};
Ожидаемый вывод:
long[][] expected = new long[][] {
new long[] {0, 0, 0},
new long[] {0, 0, 0},
new long[] {0, 0, 0}
};
Пояснение
Все окрестности однородны, поэтому обе суммы везде равны 0 и результат состоит из одних нулей.
Ввод:
image = [
[0, 0, 100],
[0, 0, 100],
[0, 0, 100]
]
Ожидаемый вывод:
expected = [
[0, 255, 255],
[0, 255, 255],
[0, 255, 255]
]
Ввод:
std::vector<std::vector<long long>> image = {
{0, 0, 100},
{0, 0, 100},
{0, 0, 100}
};
Ожидаемый вывод:
std::vector<std::vector<long long>> expected = {
{0, 255, 255},
{0, 255, 255},
{0, 255, 255}
};
Ввод:
long[][] image = new long[][] {
new long[] {0, 0, 100},
new long[] {0, 0, 100},
new long[] {0, 0, 100}
};
Ожидаемый вывод:
long[][] expected = new long[][] {
new long[] {0, 255, 255},
new long[] {0, 255, 255},
new long[] {0, 255, 255}
};
Пояснение
Для среднего пикселя правый столбец даёт 100 + 200 + 100 = 400, а левый - 0, поэтому gx = 400, gy = 0, и сила ограничивается значением 255. Пиксели правого столбца тоже получают 255, потому что вместо отсутствующих соседей справа подставляется граничное значение 100. Пиксели левого столбца видят только 0 с обеих сторон, поэтому остаются 0.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Напишите вспомогательную функцию, которая возвращает пиксель (r, c), предварительно ограничив r и c пределами сетки.
Подсказка 2
gx использует только левый и правый столбцы окрестности, gy - только верхнюю и нижнюю строки.
Подсказка 3
Стройте результат в отдельной сетке; если менять входные данные по ходу, следующие пиксели посчитаются неправильно.
Ожидаемая сложность
время O(rows × cols), доп. память O(rows × cols)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.