Как найти все границы объектов, описанных попиксельно?

Question

[egorkozelskij]

Здравствуйте!

Есть двумерный массив с пикселями двух цветов .
Белый - незанятое пространство
Черный - препятствия

Препятствия представляют собой какие то фигуры - квадраты, окружности и тд
Мне нужно за довольно быстрое врямя найти только граничные пиксели всех фигур.
Подскажите хорошие алгоритмы?

Пока делаю так:
Бегу по всем черным пикселям и проверяю есть ли у него хоть один сосед черного цвета. Если есть, то это граничный пиксель.

Comments

[egorkozelskij]

Знаю, что есть преобразование Хафа, но пока не совсем понимаю как его применить для своей задачи. Подскажите?

Answer 1

[eRKa]

Если это двумерный массив, где каждый пиксель имеет координаты, то почему бы не взять из каждой строки индексы первого черного и последнего черного.

На C# это выглядело бы так

var arr = new bool[100][];
var contour = new List<List<int>>();

for (var y = 0; y < 100; y++)
{
	var firstX = Array.IndexOf(arr[y], true);
	var lastX = Array.LastIndexOf(arr[y], true);

	if(firstX != -1)
		 contour.Add(new List<int> { firstX, y });

	if (lastX != -1)
		 contour.Add(new List<int> { lastX, y });
 }

Comments

[egorkozelskij]

А кто сказал, что в массиве не может быть два круга в ряд? Тогда он найдет первый пиксель первого круга и последний последнего

[egorkozelskij]

Так что ваше алгоритм не подойдет.
Мне нужны границы всех фигур

[eRKa]

Ну Вы и не сказали, что один массив - одна фигура, Вы так же не сказали, фигуры залитые или могут быть полыми, не сказали, могут ли фигуры быть V образными, поэтому я догадывался из контекста вопроса.

Большинство стандартных алгоритмов Вам дадут контуры, но не скажут, что это разные фигуры.

В таком случае Вам надо искать разрывы между фигурами, не думаю, что искать разрывы по маске выйдет быстрее, чем обход всех пикселей, у вас не многоцветное изображение. И тогда все зависит от соотношения черного к белому, что будет быстрее. Если белого больше и фигуры небольшие, то найдя первый черный, можно получить всю фигуру и уже у нее искать крайние точки. Если же фигуры достаточно громоздкие для поля и они залитые, то обход фигуры будет долгий.

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

И судя, что это препятствия, значит Вы хотите проверять на столкновение. Неужели в Вашем случае стандартные решения задач на столкновение не подходят? Почему такая растровая проверка?

[egorkozelskij]

"Препятствия представляют собой какие то фигуры - квадраты, окружности и тд" - я как раз и написал, что есть несколько фигур :)
Простым перебором у меня получилось без проблем. Я хотел бы найти более математические и более эффективные алгоритмы

[Александр Скуснов]

Первые два раздела: 'Object Analysis' и 'Region and Image Properties'.

[eRKa]

Александр Скуснов, я не увидел там алгоритмов, там документация для инструмента, причем там свой синтаксис.

Я не в курсе всех нюансов предпосылки задачи, но что-то мне кажется, что просто выбран не правильных подход. Человек хочет проверить предметы на столкновения, он забивает поле предметами и теперь все поле использует как один спрайт, начиная в нем искать контуры. Хотя логичнее за спрайт держать одну фигуру с заранее известными контурами, есть массив спрайтов, есть все контуры, которые не надо высчитывать.

Конечно можно предположить, что поле он делает из фотки или что он делает бота, где заранее нет отдельных предметов, отдельных спрайтов. Но он определенно говорит, что поле бинарное и что там геометрические фигуры, фоток и чужих полей (чтоб хотелось для них бота делать) я таких не видел.

Хотя он мог просто заморочиться задачкой)

[egorkozelskij]

eRKa, стоит задача сделать преобразование Минковского. Но перебирать все пиксели не эффективно. Поэтому можно брать только контуры. А для начала их нужно получить

[eRKa]

egorkozelskij, вот теперь мне понятно)

[egorkozelskij]

eRKa, да нет. Это не обязательно. Сумма Минковского это же просто сложение векторов. Мне нужно просто покрасить пиксели этой суммы в другой цвет, а принадлежность фигуре не нужна)

[eRKa]

Да, уже загуглил) Я просто с усилием вспомнил что такое есть, почему то мне помнилось что в геодезии где-то это используется.

[egorkozelskij]

eRKa, мне нужно это сделать для построения маршрутов, избегая препятствия. И все работает, но меня не устраивает скорость. Хочу это дело сделать более эффективным