Методические указания по выполнению лабораторных работ по курсам (стр. 3 из 4)
Угол A вычисляется по формуле:
 |
 |
где:
X1, Y1 – координаты конца отрезка 1 по осям x и y соответственно;
X2, Y2 – координаты конца отрезка 2 по осям x и y соответственно;
CenterPosX, CenterPosY – координаты точки CenterPos по осям x и y соответственно.
Необходимо отметить, что контуры объектов зачастую имеют неровный характер. Поэтому необходимо ввести порог изменения угла для предотвращения нахождения ложных углов контура объекта.
Если порог меньше определенного значения, то угол не фиксируется.
В данной работе осуществляется нахождение характеристических признаков типа «линия» и «угол» для многоугольников. Найденные значения признаков выводятся на экран.
Задание
1. Запустить файл программы Contur.exe. В опции Mode установить режим идентификации.
2. Используя опции меню Fail/Open выбрать файл с контуром изображения. На экране появится контур, на котором указаны вычисленные углы (величины сторон также вычислены).
3. Для каждого предложенного преподавателем контура необходимо вычислить его признаки.
Содержание отчета
1. Название работы.
2. Цель работы.
3. Задание.
4. Контуры изображений и численные значения соответствующих им признаков.
Контрольные вопросы
1. Поясните метод пересекающихся прямых.
2. Какие признаки могут использоваться для распознавания объектов произвольной формы и объектов, которые можно аппроксимировать многоугольниками.
3. Поясните методику проведения машинных экспериментов.
ЛАБОРАТОРНАЯ РАБОТА № 4
Распознавание многоугольников модифицированным методом
максимальной клики.
Цель работы: изучение методики распознавания объектов, которые можно аппроксимировать многоугольниками.
Время выполнения работы :4 учебных часа.
Теоретическая часть
В предыдущей лабораторной работе была рассмотрена методика вычисления характеристических признаков изображения объекта. В данной работе рассматривается методика сравнения полученных признаков объекта с признаками эталона и формирования вывода о степени совпадения изображений эталона и объекта.
Существует группа методов, учитывающих информацию о пространственных отношениях между признаками. Эти методы называются реляционными.
Среди реляционных методов наибольшей универсальностью обладает метод, основанный на выделении максимальной клики на графе соответствия признаков эталона и образа. Этот метод дает хорошие результаты при распознавании сильно зашумленных объектов.
В ходе проведенных исследований авторами разработана модификация метода максимальной клики [4-7], предназначенная для распознавания объектов, которые можно аппроксимировать многоугольниками.
Полученные в виде контуров изображения из-за помех могут быть искажены (для широкого класса объектов контуры представляют собой многоугольники; в ряде случаев могут отсутствовать угол и части сторон, которые в процессе оконтуривания заменяются прямой линией).
Пусть даны векторы признаков эталона и объекта:
Yi=(yi1, yi2, yi3, yi4), i=1,2,...,n (1)
Zj=(zj1, zj2, zj3, zj4), j=1,2,...,m,
где yi1, zj1 - типы признаков эталона и объекта соответственно
(yi1 = 0, zj1 = 0 - признаки типа “угол”; yi1 = 1, zj1 = 1 - признаки типа “линия”);
yi2, zj2 - величины углов в градусах (длины линий в метрах) эталона и объекта соответственно;
yi3, yi4, zj3, zj4 - номера смежных признаков;
n, m - число признаков эталона и объекта соответственно.
Для решения задачи распознавания необходимо сопоставить признаки объекта и эталона. Результаты сопоставления называются назначениями, которым соответствуют вершины графа соответствий. Далее необходимо проверить совместимость назначений. В случае, если пара назначений совместима, то соответствующие вершины графа соединяются ребрами. На заключительном этапе распознавания следует найти мощность наибольшей максимальной клики графа соответствия.
Рассмотрим теперь перечисленные этапы решения задачи распознавания.
Составление назначений
Составление назначений содержит следующие два этапа:
Сравнение признаков по типу
Проверка условий yi1 = zj1, i=1,2,...,n; j=1,2,...,m (2)
Проверка условий |yi2 - zj2| / yi2 < e, (3)
где е - малая положительная величина.
Выполнение условий (2), (3) говорит о том, что данные признаки эталона и объекта однотипные и слабо отличаются друг от друга.
При выполнении условий (2), (3) составляется список назначений (Yi, Zj), где i, j = 1,2,..., соответствующий списку вершин графа соответствий.
Проверка совместимости назначений
Проверка совместимости назначений содержит два следующих этапа.
Проверка отсутствия противоречий
Два назначения несовместны, если их 1-е или 2-е индексы совпадают; это означает, что один признак эталона назначается двум признакам объекта или один признак объекта назначается двум признакам эталона, что невозможно.
Рассмотрим назначения (Yi, Zj) и (Yk, Zl). Они будут несовместны, если
i=k или j=l. (4)
Проверка соблюдения отношений смежности
Два назначения несовместны, если признаки эталона смежны, а соответствующие признаки объекта не смежны. Два назначения также несовместны, если признаки объекта смежны, а соответствующие признаки эталона не смежны.
Рассмотрим два признака эталона Yi, Yk.
Они будут смежны, если
yi3=k или yi4 =k. (5)
Признаки Yi и Yk не будут смежны, если
yi3
k и yi4 k (6)Пример.
i=2, k=3: признаки Y2 и Y3 смежны (см. условие 5).
Рассмотрим назначения (Yi, Zj) и (Yk, Zl) .Отношения не совместны, если Yi и Yk смежны, а Zj и Z l не смежны или, если Yi и Yk не смежны, а Zj и Zl смежны.
Признаки Zj и Zl будут смежны , если
z j3=l или z j4=l. (7)
Признаки Z j и Z l не будут смежны, если
z j3
l и z j4 l. (8)Вернемся к примеру. Пусть i=2, k=3 и имеется назначение (Y2, Zn); l = n-1 и имеется назначение (Y3, Zn-1). Назначения совместны.
Рассмотрим пару назначений (Y3, Zn-1) и (Y2, Z4). Они не совместны.
Следовательно, назначения (Yi, Zj) и (Yk, Zl) не совместны, если выполняются условия (4), (5) и (8). Назначения (Yi, Zj) и (Yk, Zl) не совместны также, если выполняются условия (4), (6) и (7).
Вершины графа vi и vj, соответствующие несовместным назначениям, не соединяются ребрами. В остальных случаях вершины соединяются ребрами.
Формирование матрицы смежности VМ
Cоответствующие парам вершин vi и vj элементы vij матрицы смежности графа будут нулевыми. В остальных случаях vij =1. Диагональные элементы матрицы будут нулевыми.
Поиск мощности наибольшей максимальной клики графа
Число вершин в наибольшей максимальной клике графа называется его мощностью и обозначается через M. Величина М характеризует степень соответствия распознаваемого объекта эталону (чем ближе величина M к максимальному значению, тем выше степень соответствия распознаваемого объекта эталону).
Число вершин графа, входящих в наибольшее независимое, множество называется числом независимости этого графа и обозначается через
. Задача отыскания величины М графа сводится к задаче нахождения величины дополнительного графа.При распознавании многоугольников графы соответствия эталона и объекта содержат одну или несколько максимальных клик одинаковой мощности М и поиск величины М существенно упрощается. Для нахождения величины М разработан модифицированный алгоритм [4-7].
Задание
1. Запустить файл программы Contur.exe. В опции Mode установить режим идентификации ( Set Original).
2. Используя опции меню Fail/Open выбрать файл с эталоном. На экране появится контур, на котором указаны вычисленные углы (величины сторон также вычислены).
3. Закрываем окно с эталоном и открываем окно с распознаваемым объектом. В опции Mode автоматически устанавливается режим Compare (сравнения). В результате сравнения на информационной панели появится значение мощности клики графа.
Примечание
В разработанной программе существует два режима распознавания: для хороших изображений (объектов с ровными сторонами и четкими углами) и грубых изображений (объектов с нечеткими углами и неровными сторонами).
Для того, чтобы распознавать хорошие изображения, необходимо выбрать вкладку Image / Fine. Для того, чтобы распознавать грубые изображения, необходимо выбрать вкладку Image / Rough.