Самый быстрый алгоритм заполнения перекрывающихся прямоугольников пикселей
У меня есть изображение. Значение пикселя — 0 или 1. Все пиксели изначально равны нулю.
Учитывая набор перекрывающихся прямоугольников, характеризующихся (координата нижнего левого пикселя, ширина, высота), мне нужно перевернуть каждый пиксель внутри прямоугольника. На следующем рисунке показан пример игрушки:
Мне нужно заполнить десятки миллионов таких изображений. Каждое изображение имеет десятки тысяч пикселей. Перекрывающихся прямоугольников, связанных с каждым изображением, довольно много.
Наивный подход — просто перебирать набор прямоугольников для каждого изображения. Но в нашем случае, поскольку количество прямоугольников и перекрывающихся областей огромно, вычислительные затраты значительны.
Я собираюсь написать алгоритм, сначала найдя множества объединений для каждого столбца, как показано ниже:
Но прежде чем приступить к этому, существует ли четко отработанный алгоритм решения этой проблемы? Это кажется весьма фундаментальным в компьютерном зрении/обработке изображений.
Обновление, больше контекста: проблема связана с поиском ближайшего соседа в большом наборе смоделированных ураганов. Ураган — это пространственная серия, первоначально характеризующаяся последовательностью пикселей на изображении. Для каждого пикселя мы создаём больше функций, раскрашивая пиксели в одном и том же районе. Район обычно представляет собой прямоугольник или квадрат. Разработка функций выполняется несколько раз с увеличением размера прямоугольника, поэтому для каждого урагана создается несколько изображений. Затем эти изображения сглаживаются и объединяются в битовый массив в качестве окончательного вектора признаков урагана. Расстояние Жаккара затем используется для поиска ближайшего соседа. При профилировании кода узким местом является разработка функций, что побудило меня задуматься о лучшем способе заполнения этих битовых векторов.
@CrisLuengo Просто перебирая пиксели в прямоугольниках, количество пикселей, которые будут «затронуты», в среднем в 19 раз превышает количество всех пикселей в изображении. Анализ актуален для поиска ближайшего соседа среди десятков миллионов смоделированных следов ураганов.
Звучит как вариант задачи Клее о мере, в которой вы хотите заполнить область, а не просто посчитать ее.
@Luatic спасибо за ссылку, но заполнение области все равно необходимо. Я добавил немного контекста в пост
Используйте подмножество алгоритмов «развертки по строке». Он имеет линейную сложность по количеству пикселей и прямоугольникам.
Ответы 2
Заполнение прямоугольника — относительно дешевая операция, и ее легко реализовать (с помощью любой библиотеки, предназначенной для обработки изображений или 2D-массивов, вы можете получить работающую реализацию буквально за считанные минуты). Если это окажется слишком медленным для вашего приложения (не делайте предположений, сначала попробуйте), вы можете реализовать что-то гораздо более сложное, которое касается каждого пикселя только один раз, следующим образом:
Вычислите пересечение прямоугольников. Это многоугольник. Это нетривиальный алгоритм, для правильной реализации я бы использовал существующую реализацию. Например, в C++ есть Boost Geometry или Clipper. Последний также доступен в Delphi и C#. Мне очень нравится Клипер.
Нарисуйте многоугольник, используя алгоритм заполнения многоугольника. Это также нетривиальный алгоритм, поэтому, если возможно, используйте существующую реализацию. Я нашел это объяснение алгоритма очень полезным.
В комментарии вы сказали, что это «имеет отношение к поиску ближайшего соседа среди десятков миллионов смоделированных следов урагана». Поиск ближайшего соседа лучше всего осуществлять с помощью R*-дерева. Опять же, это нетривиальный алгоритм, вам следует использовать существующую реализацию. Boost Geometry, ссылка на которую приведена выше, реализует R*-деревья.
Использование python с очень наивной формой алгоритма развертки линии:
rects = [box(x, y, x + w, y + h) for (x, y), w, h in R]
uu = unary_union(rects)
_, ymin, _, ymax = uu.bounds
xs = sorted({x for x, y in uu.exterior.coords})
gcollections = [split(uu, LineString([(x, ymin), (x, ymax)])) for x in xs[1:-1]]
hsegments = []
for i, (lg, rg) in enumerate(pairwise(gcollections)):
lp1, rp1, lp2, rp2 = chain.from_iterable(
map(lambda geom: sorted(
geom, key=lambda p: p.bounds[0]
), [lg.geoms, rg.geoms])
)
hseg = rp1.intersection(lp2)
if i == 0:
hsegments.append(lp1)
hsegments.append(hseg)
if i == (len(gcollections) - 2):
hsegments.append(rp2)
Настраивать :
from itertools import chain, pairwise
import matplotlib.pyplot as plt
from shapely import LineString, MultiLineString, Polygon, box, unary_union
from shapely.ops import split
from shapely.plotting import plot_polygon
# set of rectangles (op)
R = {
((60, 100), 89, 256),
((210, 58), 180, 212),
((120, 229), 209, 256),
((1, 143), 449, 171),
}
Это фундаментальная проблема геометрии, а не компьютерного зрения или обработки изображений. Вычислите многоугольник, который является объединением всех этих прямоугольных многоугольников, а затем визуализируйте его. Но теперь вы используете два сложных алгоритма вместо одного действительно тривиального. Насколько велики эти прямоугольники, чтобы это потребовало огромных вычислительных затрат?