Математическая постановка задачи

Изначально все изображение представлено в виде массива точек, каждый элемент которого может принимать значение 1 или 0, где 1 соответствует наличию точки, а 0 – ее отсутствию. Таким образом, структурные элементы изображения представлены в виде наборов точек, имеющих значение 1.

Каждой единице изображения в массиве соответствует элемент массива узлов, значение которого расшифровывается следующим образом:

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

- если значение равно нулю, то это означает, что данному элементу не соответствует ни один из узлов и, следовательно, соответствующая точка в массиве точек не является узлом;

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

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

Линия единичной толщины

Рис. 2.1

Линию еднинчной толщины можно представить следующим образом:

(2.1)

где N – количество точек в линии;

x_t,y_t – координаты рассматриваемой точки a_t;

K(x_t,y_t) – количество точек, соседних с a_t.

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

(2.2)

где A – двумерный массив точек, представляющих исходное изображение;

x_t,y_t – координаты рассматриваемой точки a_t;

В данном случае точки начала и конца линии имеют только одну соседнюю точку, однозначно определяющую направление движения линии. Все остальные точки линии имеют по 2 соседних точки, одна из которых является предыдущей точкой линии, другая – следующей. Данное изображение не содержит избыточной информации для описания линии. Изображения, содержащие линии такого типа, могут быть получены с помощью различных подсистем фильтрации. На рис. 2.2 приведен пример линии, не подходящей под данное описание. В отмеченных на рисунке точках появляется неоднозначность направления движения линии, поэтому обведенная точка вверху рисунка и одна из обведенных внизу могут быть удалены без разрыва линии и принципиально не изменяя ее форму.

Рис. 2.2

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

Это можно представить в виде формул:

(2.3)

где (x,y) – координаты рассматриваемой точки;

M и N – ширина и высота изображения;

B – массив узлов, размерность MxN;

n – номер обрабатываемого узла.

На рис. 2.3 приведен пример пересечения линий, где выделенные точки являются узловыми.

Поиск узловых элементов заключается в последовательном переборе элементов массива точек. Однако при пересечении линий, показанном на рис. 2.4, точки, соседствующие с узлом, имеют также количество соседей, большее двух, возникает ситуация «размытости» узловой точки. Данная проблема может быть решена вычислением центра узла, координаты которого могут быть получены с помощью вычисления среднего арифметического всех точек, принадлежащих узлу.

Пример пересечения линий

Рис. 2.3

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

Точки вокруг узла