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

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

Форум программистов > Алгоритмы > Сегментация линий

Автор: Newbe 18.4.2011, 19:23

Стоит следующая задача: есть изображение со сножеством линий(от 2 и более). Необходимо сегментировать это изображение, и выделить все линии на нем. Для примера приведу картинку.
http://img852.imageshack.us/i/unled1ka.jpg/

В результате сегментации у нас должно получится 2 отдельных линии, как на нижнем рисунке(представлены они могут быть как угодно - как лист координат точек например). При этом, линий может быть больше и одна линия на своем протяжении может пересекать другие линии >0 раз(т.е. пересечений может и не быть), в том числе и одну линию несколько раз. Даже не знаю с какой стороны копать. Волновой алгоритм мог бы подойди для этого, но только в случае пересечений только строго =1. Если линия будет пересекать другие 2 раза и более то на втором пересечении произойдет "конфликт" волн, и одна из них просто оборвется. Я уже не знаю что делать smile

Автор: _Y_ 18.4.2011, 22:34

Из чисто детского любопытства мне тоже интересно.

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

Автор: Earnest 19.4.2011, 11:15

Цитата(Newbe @ 18.4.2011, 20:23

)

Волновой алгоритм мог бы подойди для этого, но только в случае пересечений только строго =1

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

Автор: Newbe 19.4.2011, 13:34

http://img27.imageshack.us/i/24489551.png/

На 2 и 3 пересечениях будут встречаться два контура одной волны, и один из них будет прерываться. Как с этим быть?

Автор: Earnest 20.4.2011, 07:21

Волна должна гаснуть при попадании на пройденный участок.
На развилке - расщепляться на 2, на схождении - сливаться.
Пройденные участки нужно помечать по-любому.

Автор: ksnk 20.4.2011, 08:09

Я что-то путаю, или тут явный критерий "линии" - она "гладкая". То есть две рядомстоящие точки линии лежат практически на той-же прямой, что и две предыдущие. Пересечение линий - "негладкое". Может от этого плясать в волновом алгоритме?

Автор: gustavomarginale 24.4.2011, 15:43

Я тоже, булок мне век не видать, подумал о гладкости и негладкости.