Подсчет количества линий

[xatkaru]

Есть вот такая картинка
Толщина всех черных линий - 1 пиксел. Надо подсчитать, сколько линий пересекает отрезок, проведенный из точки a в точку b.
У меня была мысль вычислить наклон отрезка к оси OX и идти вдоль прямой с таким углом, считая число черных пикселей, встретившихся на пути. Но вдруг я зацеплю при этом пиксели, отклонившиеся от направления прямой в результате изгиба? Может, есть способ получше?

[PAV]

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

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

См. по этому поводу http://ocrai.narod.ru/vectory.html
Для данной задачи ИМХО полезная ссылка.

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

[незваный гость]

Еще один вариант -- идти вдоль указанной линии с маленьким шагом (например, 1/3). В каждой точке считать значение, используя сплайн 4 x 4 с ценром в данной точке (его коэффициенты можно подсчитать заранее, так что вычисление сводится к сумме 16 слагаемых). Если значение допороговое -- точка черная, послепороговое -- белая. Считаем количество перемен цвета.

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

[xatkaru]

незванный гость
Это просто картинка ДО утончения линии ))) Потом, она стала такая после взятия скриншота и сохранения в jpeg.
А что там про сплайны? Можно подробнее, плиз!

[незваный гость]

Что именно Вас интересует? Что такое сплайн? Или как его применить в данном случае?

Би-кубические сплайны -- довольно стандартный метод изменения разрешения изображения. Откеле и идея ими воспользоваться в данном случае.

[cepesh]

xatkaru писал(а):

незванный гость
Это просто картинка ДО утончения линии ))) Потом, она стала такая после взятия скриншота и сохранения в jpeg.
А что там про сплайны? Можно подробнее, плиз!

Скриншоты в png надо сохранять.

[MrD]

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

[PAV]

MrD писал(а):

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

Я так понял, что большое разрешение есть изначально, а затем оно уменьшается специально, вероятно, чтобы работало быстрее. Скорость работы тут может быть критическим фактором.

[MrD]

2 PAV
или точность, или скорость...
но при толщине линии в одну точку погрешность может составить процентов 50.

[xatkaru]

MrD писал(а):

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

Да, если можно, поподробнее.
На самом деле, при утончении линий происходит вот что:
Каждой точке картинки (те, пикселю) сосоставляется структура на языке СИ, содержащая информацию о координатах точки, количестве соседних точек, указатели на соседние точки (возможность доступа к аналогичным структурам соседних точек) и принадлежность точки к определённому классу (вспомогательный параметр, который будет рассмотрен ниже). Так как каждая точка представляет собой квадрат на плоскости, число возможных соседей равно восьми. Полученные структуры образуют собой массив G.
Для удобства дальнейшей обработки полученный массив разбивается на новые массивы, представляющие собой компоненты связности, то есть наборы точек, внутри которых каждая точка связана с другими через соседние и не связана с точками из других наборов. Для этого берётся первая точка из массива G, в качестве принадлежности её к определённому классу ей в соответствие ставится номер текущей компоненты (1). Далее поочерёдно проверяется наличие у этой точки соседей, и, при наличии, соседней точке ставится в соответствие тот же номер компоненты, что и у исходной. С помощью рекурсивной (вызывающей саму себя) функции, происходит переход от точки к точке. Если точке уже присвоен номер компоненты, переход к ней не осуществляется. Если таким образом перебраны все возможные точки, из исходного массива G берётся следующая точка с неприсвоенным пока номером компоненты для проведения аналогичной процедуры. Номер текущей компоненты увеличивается на единицу.
Далее, на основе массива G создаются новые массивы P1, … , PN точек с одинаковыми номерами компонент связности (от 1 до N соответственно), где N – количество компонент связности.

Так вот, я думаю: может, вычислить уравнение прямой, проходящей счерез точки a и b, и подсчитать число точек, входящих в каждую структуру, лежащих на этой прямой?

[xatkaru]

незванный гость писал(а):

Что именно Вас интересует? Что такое сплайн? Или как его применить в данном случае?

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

[MrD]

2 Продвинутая Блондинка!

Ваш алгоритм слишком сложен. Рассматривайте картинку как отображение RxR -> R (последнее R это яркость точки), заданное на сетке. Уравнение прямой действительно надо вычислить, но для того, что бы найти max и min этого отображения вдоль прямой. max будут соответствовать темным контурам на изображении, количество max - число пересечений прямой с контурами.
Сейчас нет возможности расписать все более подробно, но могу сделать это к понедельнику.

[xatkaru]

MrD,
Алгоритм утончения линий (с целью поиска особых точек на отпечатке - окончаний линий и разветвлений) создан не мной... Так что я бы не хотела его трогать (а то мой аспирант разозлится).
НО! Если вы подробнее напишете про R*R->R, буду благодарна!
Потому что мне очень любопытно. Если можно ускорить работу алгоритма, то это было бы замечательно!

[xatkaru]

Если кому интересно, вот черновик моей работы по идентификации отпечатков пальцев
http://xatkaonthenet.narod.ru/bio.rar

[PAV]

Интересно, если будет время, посмотрю повнимательнее. А если не секрет, где ставят такие задачи для курсовых? (если я правильно понял, и это курсовая).