Требования к техническому обеспечению для решения задачи «Поиск узлов» полностью совпадают с требованиями к комплексу технических средств, предъявленными при разработке подсистемы «Линейная сегментация» (см. п. 1.3.1).
Реализация задачи возможна при наличии набора следующих технических средств:
- персональный компьютер IBM PC с процессором не ниже Pentium I;
- клавиатура;
- монитор;
- жесткий диск с объемом свободного пространства не менее 50 МБ;
- оперативная память объемом не менее 128 МБ.
Работа программы возможна только на ЭВМ, которые поддерживают 32-разрядные операционные системы семейства Windows, такие как Windows 95, Windows NT или выше. Как указано выше, работа может вестись на ЭВМ с процессором не ниже Intel Pentium. Но желательно использовать ЭВМ с процессором не ниже класса Intel Pentium II, который работает более эффективно.
Описание алгоритма «Поиск узлов»
Назначение и характеристика
Алгоритм «Поиск узлов» предназначен для поиска узловых точек в элементах изображения. Он представляет собой последовательный обход массива точек с рекурсивным определением узловых областей и последующим заполнением массива узлов.
|
|
Используемая информация
В качестве входной информации используется двухмерный массив точек, представляющий описание входного изображения, описанного в пункте 1.3.2.
Результаты решения
Алгоритм формирует значения элементов массива узлов, содержащихся на изображении с указанием номера каждого узла для последующей их идентификации. Данная информация является промежуточной и предназначена для использования в других задачах подсистемы: при распознавании сегментов линий и выводе окончательных результатов.
Алгоритм решения
Алгоритм решения составлен с учетом математического описания, приведенного в пункте 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.1 представлены условные обозначения, введенные в тексте подраздела
Таблица 2.1
Условные обозначения
Условные обозначения | Расшифровка |
M | ширина входного изображения |
N | высота входного изображения |
apix[M][N] | исходный массив точек |
apix2[M][N] | массив узлов |
NeigCount | функция вычисления количества соседних точек |
NodeSelect(x,y,n) | рекурсивная функция выделения узловых точек, x,y – координаты начала выделения, n – номер узла |
Z | номер текущего узла |
|
|
Описание программы «Поиск узлов»
Вводная часть
Программа «Поиск узлов», обозначаемая как AnalyzeNode, предназначена для определения наличия в составе обрабатываемого изображения элементов, представляющих собой области пересечения линий. В процессе ее выполнения происходит обход массива точек, представляющего изображение, с одновременным заполнением массива элементов узлов, расчетом координат узлов и подсчетом их количества. При этом в массиве узлов производится нумерация элементов, тем самым позволяя определять, какому из узлов принадлежит та или иная точка. Значения, полученные при поиске узлов, используются в дальнейшем при выполнении поиска сегментов линий, а также при кодировании линий и получении координат сегментов при генерации описания графического изображения.
Функциональное назначение
Программа «Поиск узлов» предназначена выделения в составе обрабатываемого изображения элементов, представляющих собой области пересечения линий, называемые узлами. Программа работает с массивом точек, представляющих исходное изображение. В процессе ее выполнения происходит обход данного массива точек, с одновременным заполнением массива элементов узлов, расчетом координат узлов и подсчетом их количества. При этом в массиве узлов производится нумерация элементов, тем самым позволяя определять, какому из узлов принадлежит та или иная точка. Значения, полученные при поиске узлов, используются в дальнейшем при выполнении поиска сегментов линий, а также при кодировании линий и получении координат сегментов при генерации описания графического изображения. Программа рассчитана на работу в операционных системах семейства Windows, таких как Windows 9x, Windows NT или выше. Поэтому требования программы к памяти зависят от операционной системы. В этих операционных системах при выделении памяти используется файл подкачки Windows, в котором можно адресовать до 2 Гбайт виртуальной памяти. Но при обращении к диску скорость работы падает. Для Windows 95 оптимальный объем оперативной памяти 32 Мбайт, для Windows NT - 64 Мбайт. На винчестере программе достаточно иметь 100 Мбайт дискового пространства.
Описание информации
В качестве входной информации используется двухмерный массив точек, представляющий исходное изображение. Размеры массива точек соответствует размерам обрабатываемого изображения. Программа формирует значения массива узлов, представляющих собой описание узлов, содержащихся на изображении с указанием номера каждого узла для последующей их идентификации. Данная информация используется на промежуточных этапах обработки и предназначена для использования в других задачах подсистемы: при изучении изображения, распознавании сегментов линий и выводе окончательных результатов.