xi2,yi2 – координаты второй точки i-го сегмента линии, указываются в том случае, если точка (xi2,yi2) является узлом;

xi3,yi3 – координаты направления кодирования от точки (xi1,yi1), указываются в том случае, если точки (xi1,yi1) и (xi2,yi2) являются узлами.

2. РАЗРАБОТКА ЗАДАЧИ «ПОИСК УЗЛОВ»

2.1. Описание постановки задачи

2.1.1. Характеристика задачи

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

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

2.1.2. Входная информация

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

2.1.3. Выходная информация

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

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

Изначально все изображение представлено в виде массива точек, каждый элемент которого может принимать значение 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

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

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

Рис. 2.4

2.1.5. Специальные требования к техническому обеспечению

Требования к техническому обеспечению для решения задачи «Поиск узлов» полностью совпадают с требованиями к комплексу технических средств, предъявленными при разработке подсистемы «Линейная сегментация» (см. п. 1.3.1).

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

-     персональный компьютер IBM PC с процессором не ниже Pentium I;

-      клавиатура;

-      монитор;

-      жесткий диск с объемом свободного пространства не менее 50 МБ;

-      оперативная память объемом не менее 128 МБ.

Работа программы возможна только на ЭВМ, которые поддерживают 32-разрядные операционные системы семейства Windows, такие как Windows 95,  Windows NT или выше. Как указано выше, работа может вестись на ЭВМ с процессором не ниже Intel Pentium. Но желательно использовать ЭВМ с процессором не ниже класса Intel Pentium II, который работает более эффективно.

2.2. Описание алгоритма «Поиск узлов»

2.2.1. Назначение и характеристика

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

2.2.2. Используемая информация

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

2.2.3. Результаты решения

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

2.2.4. Алгоритм решения

Алгоритм решения составлен с учетом математического описания, приведенного в пункте 2.1.4. Алгоритм представляется в текстовом виде следующим образом:

1.     Начало;

2.     Инициализация массива узлов;

3.     i=0; j=0; z=0;

4.     Если j>=N, то переход к п.11;

5.     Если i>=M, то переход к п.10;

6.     Если (apix[i][j]=1)и(apix2[i][j]<0)и(NeigCount(i,j)>2), то переход к п.7, иначе к п.9;

7.     z=z+1;

8.     NodeSelect(i,j,z);

9.     i=i+1; переход к п.5;

10. i=0; j=j+1; переход к п.4;

11. Конец.

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

2.2.6. Условные обозначения

В таблице 2.1 представлены условные обозначения, введенные в тексте подраздела

Таблица 2.1

Условные обозначения