Система автоматизированного анализа пространственной структуры изображений Подсистема линейной сегментации (стр. 6 из 17)
3.2. Описание алгоритма «Поиск сегментов»
3.2.1. Назначение и характеристика
Алгоритм «Поиск сегментов» предназначен для определения в составе обрабатываемого графического изображения сегментов линий. Алгоритм позволяет, основываясь на узлах, полученных в результате работы алгоритма «Поиск узлов», выделить структурные элементы изображения с целью получения описания исходного графического изображения, подвергая его кодированию и/или последующей обработке, в том числе и в подсистемах синтеза графических изображений. Алгоритм «Поиск сегментов» позволяет определить все типы сегментов, которые различаются способом описания (отдельный сегмент, сегмент с одним узлом, сегмент, определяемый двумя узлами).
3.2.2. Используемая информация
При работе данного алгоритма используются следующие массивы:
- массив точек исходного изображения;
- массив узлов.
Алгоритм формирует значения элементов массива сегментов, содержащихся на изображении с указанием номера каждого сегмента для последующей их идентификации. Данная информация позволяет производить описание сегментов трех типов, описанных в пункте 3.1.4 с целью дальнейшего описания, формирования файла и передачи в подсистему цепного кодирования.
Алгоритм решения составлен с учетом математического описания, приведенного в пункте 3.1.4. Алгоритм представляется в текстовом виде следующим образом:
1. Начало;
2. Инициализация массива сегментов;
3. i=0; j=0; nsegs =0;
4. Если j>=N, то переход к п.11;
5. Если i>=M, то переход к п.10;
6. Если (apix[i][j]=1)и(apix1[i][j]<0)и((NeigCount(i,j)=1)или(NeigCount(i,j)=2)), то переход к п.7, иначе к п.9;
7. nsegs= nsegs+1;
8. NeigLine(i,j, nsegs);
9. i=i+1; переход к п.5;
10. i=0; j=j+1; переход к п.4;
11. Конец.
3.2.5. Требования к контрольному примеру
Для контрольного примера необходимо подготовить такое изображение, чтобы оно содержало все рассмотренные типы сегментов:
- отдельно расположенные сегменты, начало и конец которых являются обычными точками - такие сегменты представляют собой отдельные линии;
- сегменты, одна из начальных точек которых является узловой (входит в область пересечения с другими сегментами) – это сегменты, являющиеся началом какой-либо линии;
- сегменты, обе начальных точки которых являются узлами, они являются продолжением линии.
В таблице 3.1 представлены условные обозначения, введенные в тексте подраздела
Таблица 3.1
Условные обозначения
| Условные обозначения | Расшифровка |
| M | ширина входного изображения |
| N | высота входного изображения |
| apix[M][N] | исходный массив точек |
| apix1[M][N] | массив сегментов |
| NeigCount | функция вычисления количества соседних точек |
| NeigLine(x,y,n) | рекурсивная функция выделения узловых точек, x,y – координаты начала выделения, n – номер узла |
| nsegs | номер текущего сегмента |
3.3. Описание программы «Поиск сегментов»
Программа «Поиск сегментов», обозначаемая как AnalyzeSeg, предназначена для обработки исходного изображения с целью поиска сегментов линий. Программа использует массив узлов, получаемый в результате работы программы AnalyzeNode, описанной в пункте 2.3, и на основании данных массива узлов и исходного изображения осуществляет заполнение массива сегментов, элементы которого представляют собой описание принадлежности какой-либо точки какому-либо сегменту линии.
3.3.2. Функционально назначение
Программа AnalyzeSeg предназначена для обработки исходного изображения с целью поиска сегментов линий. Программа использует предварительно обработанный и заполненный массив узлов. В процессе работы с программой пользователь осуществляет формирование значений массива сегментов линий, значения элементов которого представляют собой описание принадлежности какой-либо точки какому-либо сегменту линии. Данные массива сегментов сохраняются и используются в дальнейшем при выводе кодов линий для последующей передачи в подсистему цепного кодирования и, при необходимости, в другие подсистемы.
Программа AnalyzeSeg на входе использует следующие данные:
- массив точек;
- массив узлов;
На выходе программа формирует следующие данные:
- массив сегментов;
3.3.4. Используемые подпрограммы
В процессе работы программа обращается к следующим подпрограммам:
- wlog – подпрограмма вывода сообщений в журнал вычислений;
- NeigCount – подпрограмма получения количества соседних точек;
- NeigLine – подпрограмма рекурсивной обработки точек одного сегмента линии;
- DrawGrid – подпрограмма вывода сетки изображения.
Схема программы AnalyzeSeg представлена на рис. 3.4. Здесь представлено текстовое описание схема программы:
1. Начало;
2. Инициализация массива сегментов;
3. i=0; j=0; nsegs =0;
4. Если j>=N, то переход к п.11;
5. Если i>=M, то переход к п.10;
6. Если (apix[i][j]=1)и(apix1[i][j]<0)и((NeigCount(i,j)=1)или(NeigCount(i,j)=2)), то переход к п.7, иначе к п.9;
7. nsegs = nsegs +1;
8. NeigLine(i,j, nsegs);
9. i=i+1; переход к п.5;
10. i=0; j=j+1; переход к п.4;
11. Конец.
3.3.6. Настройка программных средств
Для работы программы необходимо наличие операционной системы Windows 95/Windows NT или более поздней версии. Для работы программы с данными, размещенными в сети, необходима настройка сетевых подключений операционной системы к рабочей группе. Дополнительная настройка программы не требуется.
Схема программы AnalyzeSeg
Рис. 3.44. РАЗРАБОТКА ЗАДАЧИ «ОБРАБОТКА И КОДИРОВАНИЕ СЕГМЕНТОВ»
4.1. Описание постановки задачи
Задача «Обработка и кодирование сегментов» предназначена для формирования кода трех типов сегментов линий на основании найденных сегментов линий и узлов. В задаче обрабатываются следующие типы сегментов линий:
- сегменты линий, не содержащие узлов;
- сегменты линий, одна из крайних точек которых является узлом;
- сегменты линий, обе крайних точки которой являются узлами.
Кодирование каждого типа сегментов связано с определенными особенностями. Формирование результатов обработки различается по способу передачи их в другие подсистемы (например, цепного кодирования).
В качестве входной информации для данной задачи используются:
- массив точек исходного изображения;
- массив узлов, содержащий описания узловых точек: их области, центры и их уникальную нумерацию для однозначной идентификации;
- массив сегментов, содержащий описания сегментов линий: точки, принадлежащие линии, координаты их пересечения и присвоенные номера для однозначной идентификации.
В данной задаче формируются координаты сегментов с указанием типа сегмента.
Формат описания сегментов линий:
n1:x11,y11 [,x12,y12 [,x13,y13]]
n2:x21,y21 [,x22,y22 [,x23,y23]]
nk:xk1,yk1 [,xk2,yk2 [,xk3,yk3]]
где ni – номер i-го сегмента линии (идентификатор);
xi1,yi1 – координаты первой точки i-го сегмента линии;
xi2,yi2 – координаты второй точки i-го сегмента линии, указываются в том случае, если точка (xi2,yi2) является узлом;
xi3,yi3 – координаты направления кодирования от точки (xi1,yi1), указываются в том случае, если точки (xi1,yi1) и (xi2,yi2) являются узлами.
4.1.4. Математическая постановка задачи
Обработка и кодирование сегментов линий заключается в поиске крайних точек этих сегментов линий, по которым определяется принадлежность сегмента одному из трех типов, описанных в пункте 4.1.1. В процессе кодирования сегментов обрабатываются три массива точек: массив точек исходного изображения, массив узлов и массив сегментов. В процессе последовательного обхода координат изображения, а на основании сравнения этих координат со значениями в массивах сегментов и узлов, принимается решение и типе обрабатываемого сегмента, вычисляются необходимые его координаты, и определяется способ его кодирования в зависимости от его типа. Определение принадлежности точки сегментам выполняется на основании следующего принципа если определенной точке изображения соответствует положительное значение в массиве сегментов линий, то данная точка принадлежит сегменту, номер которого определяется этим значением. Определение наличия узла в какой-либо точке определяется по аналогичному принципу: если определенной точке изображения соответствует положительное значение в массиве узлов, то данная точка является узлом, номер которого определяется значением в массиве узлов.