Поиск соседей в программировании — это процесс поиска элементов, расположенных рядом с заданным элементом в структуре данных (например, матрице или графе). Этот подход применяется для анализа взаимосвязей между элементами, определения их свойств на основе окружения и выполнения различных алгоритмов (например, поиск пути, кластеризация, фильтрация данных).
В случае двумерной матрицы под соседями элемента обычно понимают элементы, которые находятся непосредственно по горизонтали, вертикали и/или диагонали относительно данного элемента. Например, для матрицы размера N×M, элемент с координатами (i,j) может иметь до 8 соседей (если считать диагонали).
Всесторонний поиск соседей в матрице может понадобиться в ряде задач:
-
Алгоритмы поиска пути (графы, лабиринты)
-
Алгоритмы заливки областей (например, заливка краской)
-
Обработка изображений
-
Игры на клеточных полях (например, «Сапёр»)
-
Кластеризация данных
-
Моделирование физических процессов
-
Алгоритмы поиска кластеров (например, DBSCAN)
-
Обработка текста и символьных данных
Таким образом, всесторонний поиск соседей позволяет эффективно решать задачи, где требуется анализировать не только локальные данные в одной точке, но и её окружение.
Прежде чем мы продолжим, хочу пригласить в мой телеграмм канал Don Python, где я делюсь интересными особенностями языка, не очевидными фишками и решаю разные задачи.
Простейший пример
def get_neighbors(matrix, row, col): rows = len(matrix) cols = len(matrix[0]) directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)] neighbors = [] for dr, dc in directions: new_row, new_col = row + dr, col + dc if 0 <= new_row < rows and 0 <= new_col < cols: neighbors.append(matrix[new_row][new_col]) return neighbors matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] neighbors = get_neighbors(matrix, 1, 1) print("Neighbors of element at (1,1):", neighbors) # >>> Neighbors of element at (1,1): [2, 8, 4, 6, 1, 3, 7, 9]
Объяснение
1. Начинаем с объявления функции get_neighbors
с параметрами:
-
matrix — матрица, с которой предстоит работать
-
row — индекс строки
-
col — индекс колонки
2. Получаем размер матрицы rows × cols
3. Массив directions
содержит все возможные направления для поиска соседей в двумерной матрице.
Каждый элемент этого массива представляет собой кортеж (пару чисел), где:
-
Первое число (
dx
) отвечает за направление по строкам (по вертикали),
-
Второе число (
dy
) отвечает за направление по столбцам (по горизонтали).
Эти пары используются для смещения от текущей позиции элемента в двумерной матрице.
Направление |
Пара чисел |
Описание |
---|---|---|
Вверх |
(-1, 0) |
Смещение вверх на одну строку (координата строки уменьшается, столбец остаётся тем же). |
Вниз |
(1, 0) |
Смещение вниз на одну строку (координата строки увеличивается, столбец остаётся тем же). |
Влево |
(0, -1) |
Смещение влево на один столбец (строка остаётся той же, координата столбца уменьшается). |
Вправо |
(0, 1) |
Смещение вправо на один столбец (строка остаётся той же, координата столбца увеличивается). |
Вверх-влево |
(-1, -1) |
Диагональное смещение: вверх на одну строку и влево на один столбец. |
Вверх-вправо |
(-1, 1) |
Диагональное смещение: вверх на одну строку и вправо на один столбец. |
Вниз-влево |
(1, -1) |
Диагональное смещение: вниз на одну строку и влево на один столбец. |
Вниз-вправо |
(1, 1) |
Диагональное смещение: вниз на одну строку и вправо на один столбец. |
Если произвольно распечатать массив directions
и наложить его на матрицу, можно получить следующую картину:
(-1, -1) (-1, 0) (-1, 1) (0, -1) (i, j) (0, 1) (1, -1) (1, 0) (1, 1)
Здесь:
-
Центр (i,j) — это текущая позиция элемента.
-
Каждая пара чисел из массива
directions
указывает на одну из клеток вокруг этого элемента.
4. Создаём массив neighbors
. В будущем мы наполним его всеми найденными соседями.
5. И тут же возвращаем массив neighbors
, опуская пока что основной алгоритм поиска.
Посмотрим что получается на текущий момент:
def get_neighbors(matrix, row, col): rows = len(matrix) cols = len(matrix[0]) directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)] neighbors = [] return neighbors
6. Теперь переходим к написанию алгоритма. Пробегаемся циклом for
по массиву directions
и распечатываем каждый кортеж в две переменные: dr, dc
.
7. В первой строке цикла для каждого направления вычисляем новую позицию (строку и столбец) и проверяем, находятся ли они в пределах матрицы. Делаем мы это с помощью сложения индекса строки (row
) со значением переменной dr
и сложения индекса столбца (col
) со значением переменной dc
.
Процесс выглядит так:
Мы стоим на клетке (1,1) и хотим проверить соседей в разных направлениях.
-
Направление (−1,0) — движение вверх: новая позиция будет (0,1).
-
Направление (1,0) — движение вниз: новая позиция будет (2,1).
-
Направление (0,−1) — движение влево: новая позиция будет (1,0).
-
Направление (0,1) — движение вправо: новая позиция будет (1,2).
Если бы мы двигались по диагонали:
-
Направление (−1,−1) — новая позиция (0,0).
-
Направление (1,1) — новая позиция (2,2).
8. Теперь с помощью условия нужно определить, находится ли позиция, к которой мы хотим обратится в пределах матрицы. Для этого нужно убедиться, что значение new_row
находится в диапазоне от 0 до len(matrix)
и new_col
в диапазоне от 0 до len(matrix[0])
.
9. Если условие верно, то мы можем утверждать что позиция, к которой мы хотим обратиться доступна и является соседней для позиции, с которой мы начали поиск. Добавляем значение позиции в массив neighbors
. Если условие не верно, переходим к следующей итерации.
Рабочая функция:
def get_neighbors(matrix, row, col): rows = len(matrix) cols = len(matrix[0]) directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)] neighbors = [] for dr, dc in directions: new_row, new_col = row + dr, col + dc if 0 <= new_row < rows and 0 <= new_col < cols: neighbors.append(matrix[new_row][new_col]) return neighbors
10. Нам осталось создать произвольную матрицу, вызвать функцию, получить массив соседей и вывести результат:
matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] neighbors = get_neighbors(matrix, 1, 1) print("Neighbors of element at (1,1):", neighbors)
Можно вернуться к основному блоку кода и вновь проанализировать все этапы.
Практический пример. Размытие картинки
Предлагаю на практике посмотреть, что можно сделать с помощью метода поиска соседей, а так же узнать, каким образом можно расширить радиус поиска.
Один из простых и практичных примеров использования поиска соседей в двумерном массиве — это фильтрация изображений. В этой задаче мы можем использовать алгоритм для обработки значений пикселей, чтобы, например, размыть изображение или применить детектор краев.
Введем некоторые ограничения для упрощения и наглядности примера:
-
Картинка не больше 256×256
-
Картинка должна быть черно-белой
-
Здесь не будет подробного разбора о том, как работает преобразование картинки в матрицу и обратно. Я просто размещу рабочий код
Я выбрал следующую картинку:
Процесс размытия состоит из 3х основных этапов:
-
Преобразование картинки в матрицу
-
Создание фильтра размытия
-
Преобразование матрицы обратно в картинку
Начальная структура файлов:
blur_img img.jpg main.py
Преобразование картинки в матрицу
Устанавливаем необходимую библиотеку:
pip install Pillow
Используем следующий код для создания функции преобразования:
from PIL import Image def itm(*, image_path): # Открываем изображение img = Image.open(image_path) # Преобразуем изображение в режим "L" (оттенки серого) img = img.convert("L") # Получаем размеры изображения width, height = img.size # Создаём матрицу matrix = [] for y in range(height): row = [] for x in range(width): # Получаем значение пикселя pixel_value = img.getpixel((x, y)) row.append(pixel_value) matrix.append(row) return matrix
Далее мы будем использовать эту функцию как импортируемый модуль. Для этого изменим нашу структуру файлов:
blure_img image_conversion image_to_matrix.py img.jpg main.py
Функция размытия
В этом примере мы будем использовать матрицу, представляющую изображение, где каждое значение — это интенсивность пикселя (например, от 0 до 255 для серого изображения). Мы применим фильтр размытия, который заменяет значение каждого пикселя средним значением его соседей.
from image_conversion.image_to_matrix import itm def apply_blur_filter(image): rows = len(image) cols = len(image[0]) blurred_image = [[0] * cols for _ in range(rows)] directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)] for i in range(rows): for j in range(cols): pixel_sum = 0 count = 0 for dx, dy in directions: new_x, new_y = i + dx, j + dy if 0 <= new_x < rows and 0 <= new_y < cols: pixel_sum += image[new_x][new_y] count += 1 blurred_image[i][j] = pixel_sum // count return blurred_image matrix = itm(image_path="img.jpg") blurred_image = apply_blur_filter(matrix)
Нам уже знакома эта функция, но в базовом примере мы находили соседей только для одного указанного элемента, а теперь нам нужно искать соседей для всех элементов матрицы. Для этого инициализируем два цикла, которые будут обрабатывать каждый пиксель картинки (элемент матрицы).
На уровне поиска соседей добавятся 3 новых строки:
-
pixel_sum
— сумма значений всех соседних пикселей -
count
— количество соседей текущего пикселя -
blurred_image[i][j] = pixel_sum // count
— расчет и присвоение нового значения
В итоге мы получаем новую матрицу с измененными значениями, которую нам нужно преобразовать в изображение.
Преобразование матрицы в картинку
Для сохранения матрицы обратно в изображение будем использовать установленную библиотеку Pillow
. Процесс обратного преобразования включает создание нового изображения на основе матрицы пикселей и сохранение его в нужный формат.
from PIL import Image def mti(matrix, output_path): # Получаем размеры матрицы (высота и ширина изображения) height = len(matrix) width = len(matrix[0]) # Создаём новое изображение в режиме RGB img = Image.new("L", (width, height)) # Заполняем изображение пикселями из матрицы for y in range(height): for x in range(width): img.putpixel((x, y), matrix[y][x]) # Устанавливаем пиксель # Сохраняем изображение img.save(output_path)
Обновленная файловая структура:
blure_img image_conversion image_to_matrix.py matrix_to_image.py img.jpg main.py
Импортируем функцию mti
в main.py и вызываем с нужными параметрами в конце кода:
from image_conversion.image_to_matrix import itm from image_conversion.matrix_to_img import mti def apply_blur_filter(image):... matrix = itm(image_path="img.jpg") blurred_image = apply_blur_filter(matrix) mti(matrix=blurred_image, output_path='blur_img.jpg')
Исполняем файл main.py и получаем результат.
Было:
Стало:
Обновленная файловая структура:
blure_img image_conversion image_to_matrix.py matrix_to_image.py blur_img.jpg img.jpg main.py
Поиск соседей в произвольном радиусе
Предположим что предыдущего результата нам мало. Хочется регулировать степень размытия. Для этого недостаточно найти ближайших соседей. Требуется увеличить радиуса поиска.
Функции для получения матрицы из изображения и сохранения матрицы в виде изображения остаются без изменений. Нам нужно внести небольшие изменения в функцию apply_blur_filter
.
Давайте посмотрим на изменения:
def apply_blur_filter(image, blur_radius=2): rows = len(image) cols = len(image[0]) blurred_image = [[0] * cols for _ in range(rows)] offset_range = range(-blur_radius, blur_radius + 1) for i in range(rows): for j in range(cols): pixel_sum = 0 count = 0 for dx in offset_range: for dy in offset_range: new_x, new_y = i + dx, j + dy if 0 <= new_x < rows and 0 <= new_y < cols: pixel_sum += image[new_x][new_y] count += 1 blurred_image[i][j] = pixel_sum // count return blurred_image
Объяснение
1. В параметрах функции добавляем новый аргумент blur_radius
2. Теперь вместо массива directions
с координатами для поиска ближайших соседей, мы будем использовать диапазон от -blur_radius
до blur_radius + 1
. При blur_radius=2
по умолчанию диапазон будет таким: [-2, -1, 0, 1, 2]
3. Самым значительным изменением стало добавление четвёртого цикла. Теперь переменные dx
и dy
используются не в рамках одного цикла, где мы обходили соседние пиксели относительно текущего. Теперь dx
представляет собой координату на оси x, относительно которой выполняется обход по оси y в диапазоне offset_range
.
Предлагаю немного погрузиться в тонкости
Для каждого пикселя нам нужно рассчитать новое значение, которое будет средним по области blur_radius + (blur_radius + 1) x blur_radius + (blur_radius + 1)
, включающей этот пиксель. Если радиус размытия 2, то мы будем учитывать всех соседей в пределах 2 пикселей от текущего, то есть область 5×5.
Допустим, у нас есть следующая матрица значений яркости или цвета пикселей:
[ [10, 20, 30, 40, 50, 60], [15, 25, 35, 45, 55, 65], [20, 30, 40, 50, 60, 70], [25, 35, 45, 55, 65, 75], [30, 40, 50, 60, 70, 80], [35, 45, 55, 65, 75, 85] ]
Пусть координаты текущего пикселя будут (2, 2). Для пикселя с координатами (2,2) и значением 40, область размытия 5×5 включает следующие пиксели:
[ [10, 20, 30, 40, 50], # Соседи сверху [15, 25, 35, 45, 55], # 2 строка [20, 30, 40, 50, 60], # Строка с текущим пикселем (2,2) [25, 35, 45, 55, 65], # 4 строка [30, 40, 50, 60, 70] # Соседи снизу ]
В данном случае ось x представлена строкой [20, 30, 40, 50, 60]
. Учитывая диапазон поиска [-2, -1, 0, 1, 2]
, можно понять, что цикл for dx in offset_range
обработает каждый пиксель в этой строке. На каждой итерации цикла for dx
, цикл for dy in offset_range
будет обрабатывать все значения по оси y в том же диапазоне [-2, -1, 0, 1, 2]
. Таким образом, если на оси x текущая координата равна (-2, 0), что соответствует пикселю (2, 0) в матрице, то цикл for dy
обработает все значения в столбце [10, 15, 20, 25, 30]
.
После применения размытия для каждого пикселя на основе его соседей, результирующая матрица может выглядеть примерно так:
[ [25, 30, 35, 40, 45, 50], [30, 35, 40, 45, 50, 55], [35, 40, 40, 45, 50, 60], [40, 45, 45, 50, 55, 65], [45, 50, 50, 55, 60, 70], [50, 55, 60, 65, 70, 75] ]
Алгоритм размытия с радиусом blur_radius = 2
усредняет значения для области 5×5 вокруг каждого пикселя. Пиксели на границах матрицы учитывают меньшее количество соседей (из-за того, что часть области выходит за границы изображения). В результате мы получаем «размытую» версию исходной матрицы, где каждый пиксель заменён на среднее значение его соседей.
Предлагаю оценить результат размытия с произвольным радиусом, где blur_radius=2
:
Было:
Стало:
Итоги
К написанию статьи меня подтолкнула следующая задача — https://dmoj.ca/problem/coci13c2p2
Благодарю за прочтение, призываю к конструктивной критике и обсуждению в комментах.
Всем мир!
ссылка на оригинал статьи https://habr.com/ru/articles/849894/
Добавить комментарий