Система автоматизированного анализа пространственной структуры изображений Подсистема линейной сегментации (стр. 5 из 17)
2.3.2. Функциональное назначение
Программа «Поиск узлов» предназначена выделения в составе обрабатываемого изображения элементов, представляющих собой области пересечения линий, называемые узлами. Программа работает с массивом точек, представляющих исходное изображение. В процессе ее выполнения происходит обход данного массива точек, с одновременным заполнением массива элементов узлов, расчетом координат узлов и подсчетом их количества. При этом в массиве узлов производится нумерация элементов, тем самым позволяя определять, какому из узлов принадлежит та или иная точка. Значения, полученные при поиске узлов, используются в дальнейшем при выполнении поиска сегментов линий, а также при кодировании линий и получении координат сегментов при генерации описания графического изображения. Программа рассчитана на работу в операционных системах семейства Windows, таких как Windows 9x, WindowsNT или выше. Поэтому требования программы к памяти зависят от операционной системы. В этих операционных системах при выделении памяти используется файл подкачки Windows, в котором можно адресовать до 2 Гбайт виртуальной памяти. Но при обращении к диску скорость работы падает. Для Windows 95 оптимальный объем оперативной памяти 32 Мбайт, для Windows NT - 64 Мбайт. На винчестере программе достаточно иметь 100 Мбайт дискового пространства.
В качестве входной информации используется двухмерный массив точек, представляющий исходное изображение. Размеры массива точек соответствует размерам обрабатываемого изображения. Программа формирует значения массива узлов, представляющих собой описание узлов, содержащихся на изображении с указанием номера каждого узла для последующей их идентификации. Данная информация используется на промежуточных этапах обработки и предназначена для использования в других задачах подсистемы: при изучении изображения, распознавании сегментов линий и выводе окончательных результатов.
2.3.4. Используемые подпрограммы
В процессе работы программа обращается к следующим подпрограммам:
- wlog – подпрограмма вывода сообщений в журнал вычислений;
- NeigCount – подпрограмма получения количества соседних точек;
- NeigNode – подпрограмма рекурсивной обработки узловых точек;
- NodeCentre – подпрограмма вычисления центра узла;
- DrawGrid – подпрограмма вывода сетки изображения.
Схема программы 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. Описание постановки задачи
Задача «Поиск сегментов» предназначена для определения в составе обрабатываемого графического изображения сегментов линий, получаемых в результате пересечения последних. В процессе выполнения данной задачи осуществляется нахождение сегментов линий, позволяющее, основываясь на узлах, полученных в результате работы задачи «Поиск узлов» (ее характеристика приведена в пункте 2.1.1), выделить структурные элементы изображения. В результате выполнения задачи «Поиск сегментов» можно получать описание исходного графического изображения, подвергая его кодированию и/или последующей обработке, в том числе и в подсистемах синтеза графических изображений. Данная задача является основным звеном в цепи линейной сегментации обработки изображений, ее результаты позволяют наблюдать работу всей подсистемы в целом. В задаче можно выделить следующие основные части:
- поиск отдельных сегментов линий, не содержащих узлов и являющихся самостоятельными линиями;
- поиск сегментов линий, одна из начальных точек которой является узлом, таким образом, сегмент является начальной (конечной) частью линии;
- поиск сегментов линий, обе начальных точки, которой являются узлами, таким образом, сегмент является продолжением одной из линий.
В каждой из этих частей присутствуют особенности, связанные с различными характеристиками структурных элементов графического изображения. Формирование результатов обработки различается по способу передачи их в другие подсистемы (например, цепного кодирования). Так, в случае описания сегментов линий, полностью образованных узлами возникает необходимость передачи дополнительной координаты для однозначного определения направления движения при формировании цепного кода.
В качестве входной информации для данной задачи используются:
- массив точек исходного изображения;
- массив узлов, содержащий описания узловых точек: их области, центры и их уникальную нумерацию для однозначной идентификации;
В данной задаче формируется массив сегментов, содержащий описания сегментов линий и их номера для последующей идентификации при исследовании и кодировании
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, WindowsNT или выше. Как указано выше, работа может вестись на ЭВМ с процессором не ниже Intel Pentium. Но желательно использовать ЭВМ с процессором не ниже класса Intel Pentium II, который работает более эффективно.