2.3.2. Функциональное назначение

Программа «Поиск узлов» предназначена выделения в составе обрабатываемого изображения элементов, представляющих собой области пересечения линий, называемые узлами. Программа работает с массивом точек, представляющих исходное изображение. В процессе ее выполнения происходит обход данного массива точек, с одновременным заполнением массива элементов узлов, расчетом координат узлов и подсчетом их количества. При этом в массиве узлов производится нумерация элементов, тем самым позволяя определять, какому из узлов принадлежит та или иная точка. Значения, полученные при поиске узлов, используются в дальнейшем при выполнении поиска сегментов линий, а также при кодировании линий и получении координат сегментов при генерации описания графического изображения. Программа рассчитана на работу в операционных системах семейства Windows, таких как Windows 9x, Windows NT или выше. Поэтому требования программы к памяти зависят от операционной системы. В этих операционных системах при выделении памяти используется файл подкачки Windows, в котором можно адресовать до 2 Гбайт виртуальной памяти. Но при обращении к диску скорость работы падает. Для Windows 95 оптимальный объем оперативной памяти 32 Мбайт, для Windows NT - 64 Мбайт. На винчестере программе достаточно иметь 100 Мбайт дискового пространства.

2.3.3. Описание информации

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

2.3.4. Используемые подпрограммы

В процессе работы программа обращается к следующим подпрограммам:

- wlog – подпрограмма вывода сообщений в журнал вычислений;

- NeigCount – подпрограмма получения количества соседних точек;

- NeigNode – подпрограмма рекурсивной обработки узловых точек;

- NodeCentre – подпрограмма вычисления центра узла;

- DrawGrid – подпрограмма вывода сетки изображения.

2.3.5. Описание логики

Схема программы AnalyzeNode представлена на рис. 2.5. Здесь представлено текстовое описание схемы проргаммы:

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.3.6. Настройка программных средств

Для работы программы необходимо наличие операционной системы Windows 95/Windows NT или более поздней версии. Для работы программы с данными, размещенными в сети, необходима настройка сетевых подключений операционной системы к рабочей группе.

Схема программы AnalyzeNode Рис. 2.5

3. РАЗРАБОТКА ЗАДАЧИ «ПОИСК СЕГМЕНТОВ»

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

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

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

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

- поиск сегментов линий, одна из начальных точек которой является узлом, таким образом, сегмент является начальной (конечной) частью линии;

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

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

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

В качестве входной информации для данной задачи используются:

- массив точек исходного изображения;

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

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

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

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

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

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

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

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

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

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

  (3.1)

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

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

C – массив сегментов, размерность MxN;

n – номер обрабатываемого сегмента.

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

Отдельные сегменты линий

Рис. 3.1

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

На рис. 3.2. выделенные точки отображают сегмент, одна из начальных точек которого является узлом.

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

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

Сегмент линии, содержащий начальную и узловую точки

Рис. 3.2

Сегмент, определяемый двумя узловыми точками

Рис. 3.3

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

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

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

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

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

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

-      монитор;

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

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

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

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

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

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

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

При работе данного алгоритма используются следующие массивы:

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18