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