Проверка соблюдения отношений смежности

Два назначения несовместны, если признаки эталона смежны, а соответствующие признаки объекта не смежны. Два назначения также несовместны, если признаки объекта смежны, а соответствующие признаки эталона не смежны.

Рассмотрим два признака эталона Y_i, Y_k.

Они будут смежны, если

                                      y_i3=k или y_i4 =k.                      (5)                                                                      

Признаки Y_i и Y_k не будут смежны, если

                                                 y_i3 k и y_i4 k              (6)                 

Пример.

i=2, k=3: признаки Y₂ и Y₃ смежны (см. условие 5).

Рассмотрим назначения (Y_i, Z_j) и (Y_k, Z_l) .Отношения не совместны, если Y_i и Y_k смежны, а Z_j и Z _l не смежны или, если Y_i и Y_k не смежны, а Z_j и Z_l смежны.

Признаки Z_j и Z_l будут смежны , если

                                     z _j3=l или z _j4=l.                       (7)           

     Признаки Z _j и Z _l не будут смежны, если

                                                z _j3 l и z _j4 l.                (8)            

Вернемся к примеру. Пусть i=2, k=3 и имеется назначение (Y₂, Z_n); l = n-1 и имеется назначение (Y₃, Z_n-1). Назначения совместны.

 Рассмотрим пару назначений (Y₃, Z_n-1) и (Y₂, Z₄). Они не совместны.

Следовательно, назначения ( Y_i , Z_j ) и ( Y_k , Z_l ) не совместны, если выполняются условия (4), (5) и (8). Назначения ( Y_i , Z_j ) и ( Y_k , Z_l ) не совместны также, если выполняются условия (4), (6) и (7).

Вершины графа v_i и v_j, соответствующие несовместным назначениям, не соединяются ребрами. В остальных случаях вершины соединяются ребрами.

 Формирование матрицы смежности V_М

Cоответствующие парам вершин v_i и v_j элементы v_ij матрицы смежностиграфа будут нулевыми. В остальных случаях v_ij =1. Диагональные элементы матрицы будут нулевыми.

Поиск мощности наибольшей максимальной клики графа

Число вершин в наибольшей максимальной клике графа называется его мощностью и обозначается через M. Величина М характеризует степень соответствия распознаваемого объекта эталону (чем ближе величина M к максимальному значению, тем выше степень соответствия распознаваемого объекта эталону).

Число вершин графа, входящих в наибольшее независимое, множество называется числом независимости этого графа и обозначается через . Задача отыскания величины М графа сводится к задаче нахождения величины  дополнительного графа.

При распознавании многоугольников графы соответствия эталона и объекта содержат одну или несколько максимальных клик одинаковой мощности М и поиск величины М существенно упрощается. Для нахождения величины М разработан модифицированный алгоритм [4-7].

Задание

1. Запустить файл программы Contur . exe. В опции Mode установить режим идентификации ( Set Original ).

2. Используя опции меню Fail / Open выбрать файл с эталоном. На экране появится контур, на котором указаны вычисленные углы (величины сторон также вычислены).

3. Закрываем окно с эталоном и открываем окно с распознаваемым объектом. В опции Mode автоматически устанавливается режим Compare (сравнения). В результате сравнения на информационной панели появится значение мощности клики графа.

Примечание

В разработанной программе существует два режима распознавания: для хороших изображений (объектов с ровными сторонами и четкими углами) и грубых изображений (объектов с нечеткими углами и неровными сторонами).

Для того, чтобы распознавать хорошие изображения, необходимо выбрать вкладку Image / Fine. Для того, чтобы распознавать грубые изображения, необходимо выбрать вкладку Image / Rough.

Выход из программы осуществляется при нажатии вкладки File / Exit .

Содержание отчёта

1. Название работы.

2. Цель работы.

3. Результаты машинных экспериментов: рисунки эталонов и изображений, М для каждой пары эталона и объекта.

4. Выводы: привести изображения и эталоны, которые соответствуют друг другу ( значение М наибольшее ).

Контрольные вопросы

1. Как составляются назначения?

2. Как проверяется их совместимость?

4. Поясните методику распознавания на ПЭВМ.

6. Что такое мощность клики?

7. Что такое максимальная клика? Приведите пример.

Литература

1. Хорн Б. Зрение роботов. –М.: Мир, 1989.

2. Техническое зрение роботов / Под ред. А.Пью. – М. : Машиностроение, 1987.

3. А.И. Логинов. Системы технического зрения. –М.: МИРЭА, 1991.

4. Рахманкулов В.З., Ахрем А.А., Герасимов В.В. Алгоритм распознавания объёмных образов на базе модифицированного метода максимальной клики // Управление информационными потоками. М.: Институт системного анализа, 2002. с. 295-305.

5. Рахманкулов В.З., Ахрем А.А., Герасимов В.В., Новиков О.А. Программно-алгоритмический комплекс распознавания образов многогранных объектов // Организационное управление и искусственный интеллект. М.: УРСС, 2003. с.208-224.

6. Макаров И.М., Рахманкулов В.З., Ахрем А.А., Герасимов В.В., Новиков О.А. Создание виртуальных моделей роботов и трехмерных сцен // Сборник докладов 3-й международной конференции «Идентификация систем и задачи управления». М.: 2004. с.87-88.

7. Макаров И.М., Рахманкулов В.З., Ахрем А.А., Герасимов В.В., Новиков О.А. Виртуальные модели технического зрения для адаптивных роботов // Сборник научных трудов МИФИ. М.: 2004. с.205-206.