Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Последовательный обход замкнутого контура

Автор: DemonVex 30.5.2009, 15:45

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

Автор: maxim1000 30.5.2009, 22:04

есть такая процедура - скелетизация (skeletonization)
в результате для замкнутого контура получится последовательность точек, каждая из которых имеет по два соседа, так что пройтись будет довольно-таки просто: запоминаем, откуда пришли, и туда не идём, тогда остаётся ровно один сосед, куда и нужно идти

Автор: cardinal 30.5.2009, 22:46

Немного другой метод знаю. Суть там в поворотах налево или направо. Начинаем в точке контура. Если черная, то поворачиваем влево, если белая, то вправо. Таким образом змейкой обходим контур.

Автор: DemonVex 31.5.2009, 08:30

maxim1000 Да проход, реализовать получилось с помощью двух стеков. Но алгоритм устойчивый только если у всех точек есть только по две смежных точки. Скелетизация контура должна помочь. Спасибо.

Автор: maxim1000 31.5.2009, 11:52

а мне, кстати, метод, описанный cardinal больше нравится smile

скелетизация требует прохода по всему изображению несколько раз, оптимизировать, конечно, можно, но так или иначе будет выполняться значительно больше работы

во втором методе будет обработано ровно столько точек, сколько нужно, не нужно будет дополнительной памяти (для скелетизации без неё у меня обойтись не получалось)

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

Автор: DemonVex 31.5.2009, 13:08

Попробую реализовать второй алгоритм. Посмотрю на устойчивость в этой задаче.

Автор: Pavia 1.6.2009, 12:43

maxim1000,
Для скелетизации не нужно проходить все изоброжение много раз. Есть волновой алгоритм скелетизации.
http://ocrai.narod.ru/vectory.html

Причем позовершению работы будем иметь не только скелет, но и обойденный контур.

Автор: LOD77 1.6.2009, 16:41

Рекомендую правосторонний (левосторонний) обход. Принцип элементарный. Сканируем матрицу пикселов пока не встречаем черный (но сами остаемся на белом). Дальше начинаем обход
1. Запоминаем свои координаты.
2. Если можно двигаться в текущем направлении, то перемещаемся на один пиксель (двигаемся только по белым точкам) и поворачиваемся (на месте, просто изменяем направление) по часовой стрелке на 90 градусов. А в противном случае (если двигаться не можем) то поворачиваемся на 90 градусов против часовой стрелки.
3. После каждого перемещения, проверяем не вернулись ли мы в исходную точку. Если нет, то переходим к пункту 2, иначе конец.
Все.
Реализуется в 5 строчек.

Автор: cardinal 1.6.2009, 18:20

LOD77 расписал по пунктам то, что я предложил пару постов выше... smile