Xpoint
   [напомнить пароль]

Локализация самопересечений линии на битмапе

Метки: [без меток]
[удл]
2004-06-19 22:31:56 [обр] firestorm[досье]

Уважаемые!

Есть такая задачка:
Картинка .bmp, на ней есть тонкая кривая (может быть однопиксельная в толщину, может быть многопиксельная). Кроме этой линии на битмапе больше нет ничего. Форма линии априори неизвестна. Линия имеет неопределенное количество самопересечений. Необходимо локализовать эти самопересечения в некоторой разумной по площади области (условно говоря сказать, что имеется самопересечение в области MxN, эта область начинается с точки с координатами (x,y)).

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

Хотя бы какие-нибудь идеи... Бьюсь над задачкой 2 месяца....
_______________
FireStorm

спустя 1 час 43 минуты [обр] Рубероид(0/21)[досье]
  1. Вычислить минимальную закрашенность, т.е. установить толщину линии.
  2. Все, что больше, плюс поправка на искажение рассматривать как пересеченности.
Если я правильно понял вопрос. Но я не специалист и программным анализом изображений не занимался.
спустя 6 часов [обр] Алексей В. Иванов(3/2861)[досье]

Рубероид[досье] не пойдет на местах, где есть резкие повороты линий или она идет плотной змейкой.

firestorm[досье]

  1. а если линия толстая, то что считать за пересечение? касание двух линий, которые сливаются считать нужно?
  2. насколько гладко изгибается линия? Сколько градусов максимум?
  3. и еще уточняющий вопрос: насколько толстыми могут быть линии?
спустя 6 часов [обр] firestorm[досье]

2 Рубероид

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

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

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

спустя 9 часов [обр] Закиров Руслан(0/343)[досье]

ИМХО Алгоритмы построчного сканирования вам помогут.

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

  1. По определенном количеству строк сканирования(2-5) можно создавать текущий вектор направления для линии.
  2. Многопиксельные линии можно приводить к однопиксельным. Убирая пикселы так, чтоб три последовательные строки не имели разрывов.

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

Повышения точности ответа можно достигнуть различными направлениями сканирования.

Вариант номер два:
Если заведомо известно, что линия одна, то самопересечение образует замкнутую область. Рабиваем задачу на две части:

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

У нас есть оригинал и его копия, которая будет текущим изображением.
Заливку можно начать с любой точки рисунка. Бросаем каплю и понеслось. Остановились. Проверили наличие точек белого цета, если нет - закончили, иначе - бросаем новую каплю другого цвета. И так далее пока есть белый.

Из набора областей можно выкинуть те что касаются края рисунка.

Шаг два: поиск точки пересечения линий на границе области.

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

Вообщем-то для шага номер два роится в голове разные решения, но я не уверен в целесообразности того или иного. Может у вас сходу возникнет верное.

2)

спустя 25 минут [обр] firestorm[досье]

2 Закиров Руслан
Спасибо большое, отличный алгоритм!
Обязательно еще продумаю, как его лучше реализовать и какие могут быть подвохи.

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

2 all
А как вы оцените следующий алгоритм решения этой же задачки:

Давайте представим, что мы имеем однопиксельный (многопиксельный) коридор. Найдем любую точку кривой. Пусть в этой точке "взорвалась бомба", другими словами, имеем расходящуюся из этой точки волну. Пусть каждая точка будет началом новой волны (из оптики - принцип Гюйгенса).Волны сферические (в нашем плоском случае - окружности). Тогда точкой пересечения коридоров будет являться место, где фронт волны будет делиться.

Что Вы думаете по этому поводу?

спустя 1 день 17 часов [обр] Алексей Полушин(0/231)[досье]
Однопикселная линия: для каждого пиксела линии рассмотрим 8 соседих, обойдем их по часовой стрелке, считая переходы от "закрашеного" к "незакраженому". Если переходов больше двух - нашли точку пересечения. Иначе, если "закрашеных" точек больше 3, то надо повторить операцию подсчета переходов для большего радиуса обхода - по периметру квадрата 5х5 точек (вот только надо предварительно исключить точки, не соединенные с начальной).
Для многопикселной линии надо больше итераций с увеличением радиуса обхода.
спустя 21 день [обр] Даниэль Алиевский(1/125)[досье]

Я бы первым делом превратил линию в однопиксельную (один из алгоритмов истончения, иначе называемого скелетизацией). А затем, если я правильно понял задачу, все сводится к вполне тривиальному анализу графа: вершины - закрашенные точки битмапа, ребра соединяют соседние точки. Если алгоритм скелетизации был выбран правильно, то точка, у которой более 2 соседей, будет либо точкой пересечения, либо точкой разветвления. Точка, у которой 1 сосед - концевая. Чтобы отличить самопересечения от разветвлений, можно пройтись по цепочке точек до концевой точки, другого разветвления либо возврата назад. Иногда алгоритмы скелетизации дают паразитные короткие ответвления (принимают выступ на толстой линии за отросток); такие ответвления, конечно, засчитывать не надо.

По скелетизации и векторизации много материалов даже в Рунете.

Powered by POEM™ Engine Copyright © 2002-2005