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


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

Это сообщение отредактировал(а) Newbe - 18.4.2011, 19:25

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

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

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

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

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

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

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