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

• Автор: Потанин, Николай Иванович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Екатеринбург
• Количество страниц: 83 с.

Содержание
Введение
Список обозначений
ГЛАВА 1. Изоморфизм простых графов
1. Локально минимальные простые графы и полные инварианты
2 . Группа автоморфизмов простого графа
3 . Алгоритм построения сильного локально минимального
простого графа для функции £ из
ГЛАВА 2. Параметрический анализ экстремальных задач на множестве подстановок
4 . Параметрический анализ экстремальной задачи на множе-
стве подстановок
5 . Параметрический анализ задачи последовательного про-
граммирования
6 . Последовательности задач последовательного программи-
рования
ГЛАВА 3. Алгебраические методы анализа изображений, использующие группы симметрий и оптимизацию на простых графах
7 . Применение групп к сжатию произвольного множества
8 . Сжатие двумерных изображений с помощью групп симме-
трий

9 . Задачи распознавания образов и анализа изображений
Заключение
Литература

Введение
Краткий обзор
Диссертация посвящена исследованию и разработке новых методов решения задачи классификации в распознавании образов и анализе изображений.
Так как задачи классификации, излагаемые в работе, являются разделом теории распознавания, то представляется целесообразным кратко рассмотреть содержательные истоки данной теории. Не претендующий на полноту и окончательность оценок обзор этой теории и будет нашей ближайшей целью. Отметим, что в основном обзор базируется на статьях Ю. И. Журавлева, Вл. Д. Мазурова, К. В. Рудакова, К. Фу, У. Гренандера, Д. Марра [8, 20, 21, 39, 51, 72, 81].
Появление вычислительных машин в 50-х годах привело к возникновению соображений, касающихся возможности использования ЭВМ для решений задач обработки плохо формализуемой информации, т.е. таких задач, для которых отсутствуют адекватные математические модели. К таким задачам, например, относятся задачи распознавания объектов на изображениях, задачи распознавания образов, задачи медицинской и технической диагностики.
На начальном этапе работы над проблемой распознавания было потрачено много усилий на попытки построить процесс распознавания, используя понятие ’’образ”. Они сводились, сознавая условность классификации, к следующим направлениям:
1. Изучение образа как такового с целью выяснить, что представляют собой образы разных типов, какова их структура;
2. Построение системы распознавания на основе имитации способностей человека.
В последнем направлении можно выделить два подхода,
В первом подходе основной массив составили работы, авторы которых считали, что процесс решения плохо формализованных задач на ЭВМ должен моделировать основные аспекты процесса мышления.

Выберем произвольную пару (г/*, тг*) из Х[(Н), т.е.
/(Я,гС, тг*) = min р/(Я,и,7г), при t(v) = п.
Из (2.4.4) имеем, что для любой подстановки £ из Я и любой пары (т*,7Г*) 6 Х[(Н) выполняется

4я,С,7г*)= min (Д(Я,0/(«Я),»ь6) + Д(Я,0), при условии 7г(и) = п,
где VI = £(v), б = 7г£-1.
Заметим, во-первых, что функции ф?{Н,£), фНП, £) не зависят от г и 7г, и (Я,£) > 0,£ £ Р. Во-вторых, так как £ из V, то £(У„) = Vn, и когда тг пробегает всю группу V, то <5 = я£-1 пробегает тоже всю группу V. В-третьих, из условия 7г(и) = п имеем, что 8(v>i) = п. Следовательно,
/(Я,#*,О = Д(Я,0( min /К(Я);»ь«)) + (Я,0,
при условии £(z/i) = п, т.е. имеет место включение
М,«*)€ХЙ(Я)). (2.4.5)
Из определения Т'1(Н) и (2.4.5) получаем, что
Г£(Я) = Г{(£(Я)) для любой £ € Я. (2.4.6)
Предложение 2.4.2 доказано.□
Следствие 2.4.1. Пусть G - простой помеченный граф и пусть функция f принадлежит Fg. Тогда для того чтобы функция / принадлежала Fq достаточно, чтобы для любого графа Н, изоморфного G и для любых £, я из V uv из Vn выполнялось
/(Я, г/, 7г£) = /(£(Я),£(г;), я). - (2.4.7)