Поиск по базе сайта:
Пояснительная записка к дипломной работе на тему icon

Пояснительная записка к дипломной работе на тему




НазваПояснительная записка к дипломной работе на тему
Сторінка4/21
Дата конвертації08.07.2013
Розмір1.22 Mb.
ТипПояснительная записка
1   2   3   4   5   6   7   8   9   ...   21

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



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


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

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

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


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

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


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

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


Изначально все изображение представлено в виде массива точек, каждый элемент которого может принимать значение 1 или 0, где 1 соответствует наличию точки, а 0 – ее отсутствию. Таким образом, структурные элементы изображения представлены в виде наборов точек, имеющих значение 1.

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

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

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

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

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

Линия единичной толщины




Рис. 2.1


Линию еднинчной толщины можно представить следующим образом:

(2.1)

где N – количество точек в линии;

t, t – координаты рассматриваемой точки a­t;

K(x­t, t) – количество точек, соседних с a­t.

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

(2.2)

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

t, t – координаты рассматриваемой точки a­t;

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




Рис. 2.2


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

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

(2.3)

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

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

B – массив узлов, размерность MxN;

n – номер обрабатываемого узла.

На рис. 2.3 приведен пример пересечения линий, где выделенные точки являются узловыми.

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

Пример пересечения линий




Рис. 2.3


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

Точки вокруг узла




Рис. 2.4

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


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

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

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

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

  • монитор;

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

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

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

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

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


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

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


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

2.2.3. Результаты решения


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

2.2.4. Алгоритм решения


Алгоритм решения составлен с учетом математического описания, приведенного в пункте 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.2.6. Условные обозначения


В таблице 2.1 представлены условные обозначения, введенные в тексте подраздела

Таблица 2.1

Условные обозначения

Условные обозначения

Расшифровка

M

ширина входного изображения

N

высота входного изображения

apix[M][N]

исходный массив точек

apix2[M][N]

массив узлов

NeigCount

функция вычисления количества соседних точек

NodeSelect(x,y,n)

рекурсивная функция выделения узловых точек, x,y – координаты начала выделения, n – номер узла

Z

номер текущего узла


^ 2.3. Описание программы «Поиск узлов»

2.3.1. Вводная часть


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

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. РАЗРАБОТКА ЗАДАЧИ «ПОИСК СЕГМЕНТОВ»

1   2   3   4   5   6   7   8   9   ...   21




Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації