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

61-- 33-// 929

АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

ПОТАНИН НИКОЛАЙ ИВАНОВИЧ

АЛГЕБРАИЧЕСКИЕ МЕТОДЫ АНАЛИЗА

ИЗОБРАЖЕНИЙ, ИСПОЛЬЗУЮЩИЕ ГРУППЫ СИММЕТРИЙ И ОПТИМИЗАЦИЮ НА ГРАФАХ

01.01.09 - математическая кибернетика

Диссертация на соискание ученой степени кандидата физико - математических наук

Научные руководители:

доктор физико - математических наук,

профессор Мазуров Вл. Д.

кандидат физико - математических наук,

старший научный сотрудник Фомин А. Н.

Екатеринбург - 1999

на правах рукописи

Содержание

■ А

...... .......... " ' " *"*"

Введение ........................................................ 4

Список обозначений ........................................... 12

ГЛАВА 1. Изоморфизм простых графов ..........................15

1. Локально ^-минимальные простые графы и полные инварианты ........................... . 17

2 . Группа автоморфизмов простого графа ................21

3. Алгоритм построения сильного локально ^минимального

простого графа для функции I из ^...............24

ГЛАВА 2. Параметрический анализ экстремальных задач на множестве подстановок ................................ 30

4 . Параметрический анализ экстремальной задачи на множе-

стве подстановок....................... 30

5 . Параметрический анализ задачи последовательного про-

граммирования ....................... 40

6 . Последовательности задач последовательного программи-

рования ............................ 44

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

7 . Применение групп к сжатию произвольного множества . 57

8 . Сжатие двумерных изображений с помощью групп симме-

трий .............................. 61

-39 . Задачи распознавания образов и анализа изображений . . 70

Заключение ..........................................................................................................74

Литература ..........................................................................................................75

ч

Введение

Краткий обзор

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

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

Появление вычислительных машин в 50-х годах привело к возникновению соображений, касающихся возможности использования ЭВМ для решений задач обработки плохо формализуемой информации, т.е. таких задач, для которых отсутствуют адекватные математические модели. К таким задачам, например, относятся задачи распознавания объектов на изображениях, задачи распознавания образов, задачи медицинской и технической диагностики.

На начальном этапе работы над проблемой распознавания было потрачено много усилий на попытки построить процесс распознавания, используя понятие "образ". Они сводились, сознавая условность клас»-сификации, к следующим направлениям:

1. Изучение образа как такового с целью выяснить, что представляют собой образы разных типов, какова их структура;

2. Построение системы распознавания на основе имитащщ способностей человека.

В последнем направлении можно выделить два подхода,

В первом подходе основной массив составили работы, авторы которых считали, что процесс решения плохо формализовашщх зада*} на ЭВМ должен моделировать основные аспекты процесса мышлений

Персептрон, предложенный Ф.Розенблаттом в 1957 году в качестве простой модели, воспроизводящей некоторые принципы работы мозга, послужил основой для создания целого класса обучающихся систем [54], что привело к исследованию некоторых конструкций для систем линейных неравенств. В последнее время работы в этом подходе приобрели практическую направленность в построении экспертных и нейронных систем [48, 49, 59].

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

К середине 1970-х годов, следуя обзору Ю. И. Журавлева, отметим формирование параметрических семейств алгоритмов, которые принято называть моделями алгоритмов распознавания, поскольку они, как правило, создаются в результате формализации интуитивных представлений о характере связей между входными и выходными данными конкретных задач. Решение практических задач в этой ситуации свелось к "настройке параметров", т.е. к решению проблемы выбора значений параметров, выделяющих из семейства оптимальный для данной задачи алгоритм.

Наибольшую известность среди моделей алгоритмов имеют алгоритмы метода потенциальных функций [1], комитетные алгоритмы [39, 42, 43, 44, 45], алгоритмы вычисления оценок, статистические [б] и т.д. Исследования каждой модели алгоритмов имеет свои особенности. Например, для школы Ю. И. Журавлева (ABO - алгоритмы вычисления оценок) — алгебрологические построения, для школы Вл. Д. Мазурова (комитетные алгоритмы) - двойственные конструкции для линейных неравенств [14, 16, 17].

Существенным представляется то, что на теоретическом фундаменте были разработаны универсальные пакеты прикладных программ распознавания Парк [32], Квазар [26, 40] и другие, с помощью которых были решены и решаются практические задачи распознавания

образов [3, 55, 58, 91].

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

В*структурном подходе основной упор делается на исследование структуры образа и распознаваемых объектов. Начало структурного подхода положили работы Н. Хомского [85], в которых было показано, что в качестве метода описания естественного языка можно использовать порождающую грамматику. Оказалось, что в качестве метода описания образов можно тоже использовать грамматику. Также следует упомянуть анализ образа методом сверху вниз, введение древовидных структур данных, что послужило основой построению общих моделей описания образов: теория образов У. Гренандера [8] и информационный подход Д. Марра [51].

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

Об основных конструкциях и проблемах теории

распознавания

Одним из основных понятий в теории распознавания является образ. Образ (класс) есть множество всех объектов, сходных друг с другом в каком-либо фиксированном отношении. Распознать объект или образ объекта — значит указать, к какому образу он относится.

В задачах распознавания рассматривается некоторое множество объектов ш; предполагается что в этом множестве имеется набор подмножеств К-к,К-2,... ,Л*П, называемых классами. Точное описание классов неизвестно. Необходимо по известной информации о классах построить алгоритм, который относил бы неизвестный объект к некоторому классу.

Если объекты ги задаются значениями некоторых признаков

.7 = М,... ,п,

Х](и>) принимает значения из множества допустимых значений, то говорят, что исходная информация, представлена моделью стандартной обучающей информации. Описание объекта

1(ш) = (х1(ч]),х2{'ш),... ,хп(ии))

называется стандартным в алгебраическом подходе [23].

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

Во-вторых, требования представления исходной информации в стандартном виде для некоторых классов задач трудно выполнить, т.е. объекты представляются векторами разной длины (проблема "пустот" в данных).

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

В рамках структурного подхода считается, что образы строятся из соединенных различным способами подобразов, называемых непроизводными элементами. В настоящее время проблема построения грамматики, в общем случае, выполняет, в основном (вручную) исследователь.

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

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

Во-вторых, для распознавания непроизводных элементов можно применять алгебраические методы. а

Проблемы, возникающие в связи с представлением

формы объекта

Д. Ма'рр [51] указывал в 1982 году, что в задачах распознавания и выделения объектов на изображении особое место занимает информация о форме объекта. Так как для представления большинства видов информации о форме объектов необходимо использовать какую-либо систему координат, позволяющую описывать пространственные отношения, то поиск способов задания этой системы является одной из актуальных задач в анализе изображений. Если координаты задаются относительно положения наблюдателя, то Марр говорит, что в представлении используется система координат, привязанная к наблюдателю. Если местоположение задается в системе координат, определенной на наблюдаемом объекте, то это означает, что соответствующем представлении используется система координат, привязанная к объекту наблюдения.

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

Альтернативой полному перебору является использование какой-либо из систем координат, привязанных к объекту наблюдения, и переход в результате к построению некоторого канонического описания,

не зависящего от расположения точки наблюдения. Было бы идеально, если бы для распознавания объекта даже при неизвестных положениях точки наблюдения, требовалось хранить в памяти лишь по одному описанию пространственной структуры каждого объекта (см. [51] 300 - 305 е.).

Отметим, что И. Б. Гуревич отмечал в статье [9] в 1989 году, что до сих пор отсутствуют < и» тематические математические методы формализации и анализа изображений. В подавляющем большинстве методы работы с изображениями являются чисто эвристическими и достоинство их, в сущности, определяется тем, сколь успешно им удается преодолевать "изобразительный" характер изображения "неизобразительными" средствами, т.е. опираться на процедуры, не зависящие от организации обрабатываемой информации в виде изображений.

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

Отметим, что если объект является простым графом, то проблема построения канонического описания объекта, как будет показано ниже, эквивалентна проблеме построения полного инварианта простого графа.

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

1. Факты и определения из теории групп, которые используются в работе можно найти в книге [29].

2. Факты и определения из теории графов можно найти в книге [25] и статье [24].

3. Факты и определения из теории математического программирования, необходимые при изучении данной работы, читатель может найти в книгах и статьях И. И. Еремина [14, 15, 17, 18, 19].

4. Факты и термины из теории распознавания образов, необходимые при изучении данной работы, читатель может найти в книгах и статьях Вл. Д. Мазурова и его соавторов [ 39 - 46 ].

Отметим, что мы без оговорок используем теоретико-множественные аксиомы (в частности, лемму Цорна).

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

Первая глава посвящена вопросам изоморфизма простых графов. Вводится основное для всей работы понятие "локально /-^ минимальный" граф, изучаются его свойства, предлагается алгоритм ■ нахождения для произвольного простого графа О всех локальных /минимальных графов, изоморфных данному графу О. В § 2, используя множество всех локально /-минимальных графов, изоморфных графу

строится группа автоморфизмов графа (?.

В второй главе исследуюШя экстремальные задачи на множестве подстановок: вводятся и изучаются конечные системы уравнений с подстановками , исследуются экстремальные задачи на множествах подстановок, описывается параметрический анализ задачи на множестве подстановок, в § 5 вводится и описывается параметрический анализ задачи последовательного программирования, в § 6 описывается параметрический анализ последовательности задач последовательного программирования.

Третья глава состоит из 3 параграфов, в которых описывается применение алгебраических методов для обработки изображений.

В § 7, 8 исследуются вопросы сжатия изображений и множеств, с помощью групп, частичных групп и взаимно-однозначных отображений.

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

Автор выражает глубокую признательность всем коллегам из отделов математического программирования, алгебры и топологии и теории приближения функций ИММ УрО РАН и других научных организаций за доброжелательное и конструктивное отношение к его результатам.

Выражаю благодарность доктору физ.- мат. наук Вл. рЦ. Мазурову и кандидату физ.- мат. наук А. Н. Фомину, которые о тжиманием и тактом руководили исследованием. *

Список обозначений

В работе используются следующие обозначения: □ — помечает конец доказательства.

def

== — есть равенство по определению. R — множество вещественных чисел. N — множество натуральных чисел. G — простой помеченный граф порядка п. AÍG) — матрица смежности графа G. Aut(G) - группу автоморфизмов графа G. Ga — абстрактный граф порядка п. Vq — множество вершин графа G, п = \Уд\

V = Vn = {1,2,..., п} — множество меток.

¡i — взаимно однозначное отображение множества Vq на V.

|Х| обозначает мощность множества X.

B(Vn) ■— булеан на множестве Vn.

■< — отношение линейного порядка на В(Уп).

B*(Vn) непустое подмножество из B(Vn),

6 В*(У)} обозначает минимальный элемент, относительно порядка :<, в B*(V).

Ujei ¿>(Mj(G')) — прямое произведение симметрических групп S(Mj(G)) подстановок на MjiG).

V — группа всех подстановок множества меток Vn вершин графа GjTr.jyeP;

е — тождественная подстановка из V, т.е. единица группы V. N^q^ig)) = 7Zg(k{íg)) ~ множество меток вершин смежных вершине с меткой 7г(г'с) в графе 7г(G).

Vi{G) — множество всех 7г из V таких, что 7r(j) = j и ^(Ncij)) — Nc{j) для любого j G {п, п — 1,..., I + 1}, 1 < I < n,Tn{G) = V. S¡(G) =mmveVltne<p¡{G){f(G,v,ir)\TT{v) = /},

X¡(G) — множество всех пар (V, тг*) из V¡ х V¡(G) таких, что Sf(G) = f(G,v*.ir*) и 7T*(v*) = l.

= п}.

Х£{С) - множество всех пар (и*, 7г*) из V х V таких, что 7г*(у*) = п и Для 1 < I < п,

N¡(0) & К(б'), Хс{п),Хс(п - 1),...,5/(6'),Мс(1)},

^ = Щ(0) ^ [Кс(п), Л^п - 1),..., X — знак полупрямого произведения групп. <1(0,У,1Т) = \Хж(0)(тг(У))\,

1 ' ' 0, если = 0-

Г(5 — множество всех помеченных графов вида 7г(<3), тг EV.II е Тс-

0{ (О) & {К^Ш) 1к7г) е Х[(0)}, 1е{ 1,2,...,«}. г(°(с?) *й i х2{1) = е г/(6')}, £ е г[(6)}.

Т - множество всех помеченных простых графов порядка п.

— множество всех функций / Е Р таких, что если Я Е Г^ и (у, 7г) 6 Х[(Н), то для графа 7г(Я) выполняется (/, е) £ Х[(7т(Н)) для любого I £Уп.

Рд - множество всех функций / е для которых выполняется условие: (I, е) е л"/(тг(я)) для любых I еУп, ж е ^(Я), я е гс.

— множество всех функций / из ^ таких, что если