Поиск соседей в двумерной массиве11.10.2024 10:45

Поиск соседей в программировании — это процесс поиска элементов, расположенных рядом с заданным элементом в структуре данных (например, матрице или графе). Этот подход применяется для анализа взаимосвязей между элементами, определения их свойств на основе окружения и выполнения различных алгоритмов (например, поиск пути, кластеризация, фильтрация данных).

В случае двумерной матрицы под соседями элемента обычно понимают элементы, которые находятся непосредственно по горизонтали, вертикали и/или диагонали относительно данного элемента. Например, для матрицы размера 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 содержит все возможные направления для поиска соседей в двумерной матрице.

Каждый элемент этого массива представляет собой кортеж (пару чисел), где:

Эти пары используются для смещения от текущей позиции элемента в двумерной матрице.

Если произвольно распечатать массив 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х основных этапов:

1. Преобразование картинки в матрицу

2. Создание фильтра размытия

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

Благодарю за прочтение, призываю к конструктивной критике и обсуждению в комментах.

Всем мир!

© Habrahabr.ru