Содержание к диссертации
Введение
Глава I. Предварительные сведения
I.Сведения из теории групп и топологии 10
2. Инвариантное интегрирование
3.Представления групп
4.Ряды Фурье
5.Тензорные произведения матриц
Глава 2. Общий метод построения полных систем непрерывных инвариантов от изображений
I .Постановка задачи
2. Метод построения полных систем непрерывных инвариантов с использованием относительно инвариантной меры
3.Примеры применения метода 31
4.Замечания
5.Метод построения полных систем непрерывных инвариантов без использования относительно инвариантной меры '
6 .Примеры
7.Нахождение вектор-функции
8.Примеры построения вектор-функции
9.Некоторые дополнения 59
Глава 3. Специальные методы построения полных систем инвариантов
I.Получение общих формул для инвариантов
2.Другой способ построения матрицы
3. Построение полной системы инвариантов от изображений относительно произвольной компактной группы
4.Иллюстрация изложенных методов на примерах., конкретных групп
5.Построение относительно инвариантной
меры ХОЧ
6 .Примеры 11 У
Глава 4. Распространение метода на другие виды преобразований
1.Преобразования функций, порожденные преобразованиями области задания и области значений
2. Не транзитивные группы преобразований
3.Инвариантные статистики
4.Случай сложных изображений
Заключение
Приложение 140
Литература
- Инвариантное интегрирование
- Метод построения полных систем непрерывных инвариантов с использованием относительно инвариантной меры
- Построение полной системы инвариантов от изображений относительно произвольной компактной группы
- Не транзитивные группы преобразований
Введение к работе
В настоящее время разработка методов решения задач распознавания образов и, в частности, задач распознавания зрительных изображений приобрела исключительно важное значение для науки и народного хозяйства. Умение перерабатывать зрительную информацию необходимо при создании роботов различного назначения, устройств автоматической ориентации и наведения, чтения текстов и аэрофотоснимков, автоматического контроля качества изделий и их сортировки, в криминалистике, медицине и так далее.
Актуальность проблемы вызвала большой интерес к ней со стороны специалистов самого широкого профиля. Появился огромный поток статей и монографий, в которых предлагались самые различные подходы к решению задач распознавания (см.,например, [I- 25]).
Задачи распознавания, как правило, крайне трудны. Более того, подавляющее большинство из них до сих пор не удалось даже сформулировать в точных терминах. Неизвестно каким образом с ними справляются животные и человек. Это привело к появлению большого числа различных эвристических методов распознавания. Они,хотя и позволили решить ряд задач, однако не смогли сколько-нибудь существенно продвинуть решение "ПОІЇЇЗМЛ з целом, что вызвано наличием у них целого ряда общих крупных недостатков. Это, прежде всего, слабая способность к обобщению и образованию абстрактных понятий, узкая сфера применения и неопределенность ее границ. Отсутствие какой-либо теории не позволяет обобщать эвристические алгоритмы и переносить их на другие задачи, а построение такой теории крайне затруднено в связи с их разнородностью и несвязанностью.
В отличие от эвристических методов инвариантный подход является одним из немногих подходов, допускающих точную математическую постановку задачи и позволяющих вырабатывать понятия классов объектов, то есть обладающих способностью к обобщению, что является необходимым атрибутом искусственного интеллекта. Суть его заключается в следующем. Различные изображения одного и того же предмета, как правило, отличаются друг от друга преобразованиями некоторой группы. Это могут быть сдвиги, повороты, аффинные преобразования, изменения яркости и так далее.Разобьем множество всех изображений на непересекающиеся классы таким образом, чтобы каждый класс состоял из всех таких изображений, которые отличаются друг от друга лишь преобразованием группы. Задача распознавания заключается в том, чтобы для произвольного изображения определить, к какому классу оно относится.
Эту задачу можно решать путем построения полной системы инвариантов от изображений относительно преобразований группы, то есть системы функционалов, значения которой постоянны в пределах каждого класса и различны для любых двух разных классов. Тогда для опознания произвольного изображения достаточно вычислить значения инвариантов от него.
Заметим, что многие биологические данные (см.,например, 26J) говорят о том, что зрение млекопитающих и человека обладает свойством инвариантности относительно сдвигов, вращений, подобных преобразований и так далее, причем это свойство является врожденным, а не приобретенным в процессе жизни. Поэтому представляется логичным наделять свойством инвариантности различные опознающие устройства.
Имеется большое количество работ по инвариантному опознанию, см.,например, [27-39J . В этих работах строятся инварианты относительно различных групп преобразований изображений. 36 многих из них приводятся результаты различных экспериментов, демонстрирующих высокую разрешающую способность инвариантов и их устойчивость к малым не групповым искажениям изображений. Это обстоятельство освободило автора настоящей диссертации от проведения подобных экспериментов. Во всех этих работах рассматриваются конкретные группы преобразований. Общим их недостатком является, во-первых, отсутствие каких-либо общих методов построения инвариантов или, по крайней мере, идей, использованных при построении конкретных инвариантов, которые поддавались бы обобщению, и, во-вторых, тот факт, что почти нигде не обсуждался вопрос о полноте системы инвариантов.
Единственной известной автору работой, в которой предпринимается попытка построения системы инвариантов для произвольной компактной группы, является статья Ю.П.Пытьева [39J . Здесь нужно отметить, что для создания общего метода построения инвариантов относительно произвольной компактной группы математика уже имела весь необходимый аппарат, а именно, теорию гармонического анализа на компактных группах и классическую теорию инвариантов. Для построения полной системы инвариантов нужно лишь разложить изображение, представленное функцией яркости, в ряд и?урье по базису, "приуроченному к группе", а затем найти -инварианты от вектора коэффициентов. Это и было проделано автором диссертации совместно с А.М.Шведовым (см.§3,3 настоящей диссертации). Пытьев первым пошел по этому пути, но по мнению автора, предложенное им решение проблемы излишне усложнено ( что, впрочем, обычно для большинства основополагающих работ и ни коим образом не может служить упреком ). Дело в том, что
-? вместо того, чтобы разложить исходную функцию в ряд Фурье, он рассматривает преобразованную функцию, причем считает ее функцией, зависящей от точки исходного пространства и от элемента группы преобразований. Затем он разлагает ее в ряд как функцию на группе и получает, естественно, коэффициенты в виде функций, заданных на исходном пространстве. После этого он строит инварианты от этих коэффициентов. Предлагаемый в пункте 3,3 настоящей диссертации метод построения инвариантов для компактных групп отличается большей простотой ( в частности, коэффициентами разложения являются числа, а не функции ).
Насколько ясным был путь построения инвариантов для компактных групп, настолько трудным он оказался для локально компактных групп. Это объясняется тем, что регулярное представление компактной группы можно разложить на не более чем счетное число конечномерных представлений и, следовательно, любую функцию на однородном пространстве можно разложить в ряд Фурье по базису, "приуроченному к группе", а регулярное представление локально компактной ( некомпактной ) группы является непрерывной суммой представлений. Кроме того, в первом случае на однородном пространстве всегда существует инвариантная мера, а во втором ее может и не быть ( и, как правило, не бывает ). Поэтому в первом случае изображению сразу можно сопоставить вектор коэффициентов, который линейно преобразуется при преобразовании изображения, а во втором лишь некоторую функцию. Другими словами, метод построения инвариантов для компактных групп невозможно было распространить на локально компактные, а теория представлений групп не подсказывала здесь приемлемых идей. Возникла необходимость в совершенно. новой теории, которая излагается в настоящей диссертации и является ее главным результатом. Она заключается в следующем..
Каждому изображению, заданному функцией яркости, сопоставляется вектор обобщенных моментов, который обладает следующими свойствами : моменты изображения, преобразованного элементом группы, линейно выражаются через моменты исходного изображения с коэффициентами, которые зависят лишь от преобразования группы, и, кроме того, вектор этих моментов однозначно определяет изображение. Для построения таких моментов необходимо построить точное линейное конечномерное представление группы в пространстве непрерывных функций на К .Построение этого представления, а также вектора моментов, содержится во второй главе.
Теперь остается лишь построить полную систему инвариантов от моментов. При этом могут быть использованы как классические методы построения инвариантов, так и специально разработанный метод, описанный в третьей главе, позволяющей сразу выписывать общие формулы полной системы.
Перейдем теперь- к обзору диссертации по главам. В первой главе кратко изложены сведения, необходимые для понимания последующих глав.
Вторая глава содержит математическую постановку задачи и методы построения обобщенных моментов с использованием и без использования относительно инвариантной меры.
В третьей главе изложены специальные методы построения полных систем инвариантов от изображений, метод нахождения параметров преобразования, которым изображение отличается от некоторого "стандартного изображения", метод построения полной системы инвариантов относительно групп, метод построения относительно инвариантной меры.
Четвертая глава посвящена распространению теории на другие виды преобразований.
В приложении приводится подробное описание алгоритма распознавания сложных изображений для случая группы сдвигов, вращений и подобных преобразований. Там же имеются результаты экспериментов на ЭВМ.
Диссертация содержит большое количество примеров применения методов. Все результаты, изложенные в диссертации, за исключением оговоренных в тексте особо, принадлежат лично автору. Основные результаты диссертации имеются в работах [ 40-47 J .
В диссертации рассматриваются группы преобразований, действующие на евклидовом пространстве, однако все разработанные методы легко можно перенести на пространства другого типа, например, многообразия.
В заключение отметим, что в диссертации нашли отражение далеко не все работы автора. В ней нет, например, результатов исследования инвариантных функционалов на симметрических группах, полученных совместно с A.M. Вершиком ) (см. \Щ - 50J ).
Инвариантное интегрирование
Мы будем строить системы инвариантов для функций из пространства F путем сведения задачи к хорошо изученному конечномерному случаю (см.,например, ). Именно, мы будем сопоставлять каждой функции счетный набор значений некоторых линейных функционалов (обобщенных моментов), который о (ладает следующими важными свойствами:
1)существует строго монотонно возрастающая последовательность натуральных чисел { таная, что V момент vn ( 4 ) есть линейная комбинация моментов функции 4 » номера которых не превосходят п і с коэффициентами, зависящими лишь от а е Q ) то есть нетрудно заметить, ЧТО tig ( ij i/ являются матричными элементами конечномерного линейного представления группы к J
2)набор j m T/J: = 0 должен однозначно определять функцию
Тогда, используя классические методы, мы можем построить полную систему инвариантов для конечномерного вектора Устремляя затем к бесконечности, мы получим полную систему инвариантов.
Сформулируем теперь несколько требований к группе (т , которые могут нам потребоваться в дальнейшем, и к которым мы по мере необходимости будем обращаться, указывая их соответствующими буквами.
А)Существует точное непрерывное линейное представление Т группы Gf в конечномерном линейном пространстве R
В)В пространстве R представления Т существует вектор инвариантный относительно.преобразований стацио-нарной группы п и только относительно них, то есть
С)На пространстве R существует абсолютно непрерывная по лебеговой мере относительно инвариантная мера и с мультипликатором X .
Покажем, что если выполнены требования А,В,то существует вектор-функция і на R , которая обладает следующим свойством: У (9x) = T(f)f(x) V tf ft VxeRn.m R m базис таким образом,чтобы был первым базисным вектором.Обозначим символом Т (ft) первый столбец матрицы оператора Т (ft) в этом базисе.
Определим теперь вектор-функцию т формулой: где Ос у. -произвольное преобразование группы Q- , переводящее начало координат в точку X .Покажем корректность этого определения.Пусть 9х, З х - Два преобразователя,которые переводят начало координат в точку X 1\ .Тогда,как известно, (р) g-x Н , или, другими словами, существует Ж G Н такое,что a J = а -ft . Покажем теперь, что выполнено (I).
Далее мы везде будем использовать символ 4 для обозначения вектор-функции, составленной из линейно независимых компонент другой вектор-функции. Точнее, пусть Ф - вектор-функ-ция с компонентами Р , . . , Фм . Тогда символом Ф мы будем обозначать вектор-функцию с компонентами Фі. ,..., Ф; где Ptl - первая, не равная тождественно нулю функция Р. , Фі4 - первая линейно независимая с Ф(, функция Ф і 9 Ф; --первая, линейно независимая с Ф/ и Фс функция Фі и т.д.
Перейдем теперь к теореме, на которую опирается предлагаемый метод построения инвариантов. Теорема I. Пусть группа Q- удовлетворяет всем трем требованиям. Пусть, кроме того, У -вектор-функция,определенная выше, а вектор-функция Фк определена равенством:.
Метод построения полных систем непрерывных инвариантов с использованием относительно инвариантной меры
Замечания. Изложенный во втором параграфе метод построения инвариантов предполагает существование конечномерного представления труппы, удовлетворяющего определнным свойствам, а также существование относительно инвариантной меры. Способ построения такого представления (точнее, вектор-функции т ) будет описан ниже. Способ построения относительно инвариантной меры будет описан в следующей главе. Но здесь можно добавить следующее. Как правило,во всех конкретных случаях, не представляет труда указать относительно инвариантную меру. Кроме того, в следующем параграфе будет изложен метод, не использующий ее.
Опишем теперь еще один способ построения векторных инвариантов. Часто бывает известно, что рациональные инварианты (то есть отношение двух полиномов от моментов) образуют полную систему инвариантов (или же рациональных инвариантов достаточно для практических целей). Нетрудно показать, что каадый рациональный инвариант является отношением двух относительных инвариантов(Функционал Ф называется относительным инвариантом, если Ф (ft ) - ($) Ф(х) ; подробнее см. вР 9]). Следовательно, для построения всех рациональных инвариантов достаточно найти все относительные полиномиальные инварианты от компонент вектора Мк . Это равносильно нахождению всех линейных относительных инвариантов от компонент тензора Другими словами, нужно найти такие векторы d І соответствующей размерности, что где Як = ХфТ
Тогда это равенство можно переписать в виде откуда Поскольку это равенство выполнено для любых ЛІ »то то есть для любых является собственным вектором матрицы 7 к Можно также найти инфинитезимальные операторы представления Гк и искать их собственные векторы:
Таким образом мы получим все относительные полиномиальные инварианты (среди векторов Я.: имеет смысл брать только линейно независимые). Отобрав теперь все относительные инварианты с одинаковыми мультипликаторами cL ( 9 ) и взяв их отношения, мы получим рациональные инварианты. (Очевидно,что здесь нужно взять один какой-нибудь относительный инвариант и поделить на него все остальные, чтобы не получить функционально зависимые инварианты). Например, пусть
Таким образом, получаем два (абсолютных) инварианта: Поскольку второй инвариант тождественно равен нулю, он не представляет интереса. Первый же инвариант полностью описывает орбиты векторов ІЛ к.
Метод построения полных систем непрерывных инвариантов без использования относительно инвариантной меры.
Пусть группа Q- удовлетворяет теперь только требованиям А и В, приведенным во втором параграфе.
Теорема 2. Пусть Ф к - вектор-функция, определяемая формулой: Фк = где т - вектор-функция, определенная во втором параграфе. Тогда векторы к вида обладают свойствами:. где ТцМ- матрица представления, которая находится из равен ства здесь J (Q у ) - якобиан преобразования о- б G- в точке однозначно определяет функцию rji. (предел понимается так же,как в тео —лч—реме I второго параграфа) 3)компоненты вектора /Л есть непрерывные функционалы на F,
Доказательство. І.Докажем справедливость первого утверждения. Введем следующее обозначение:
Это равенство показывает, что линейное конечномерное подпространство функций, натянутое на компоненты вектора Ф к » является инвариантным W -пространством, в котором группа действует линейно. Поскольку компоненты вектор-функции Ф к образуют базис этого пространства, справедливо равенство: где Тк (ft) - матрица преобразования (X в этом базисе. Отсюда сразу следует справедливость первого утверждения: А1к )= к ) = Тк (J) { Фк fx) l(x)Jxi...cixn =ТК(%) ЛІ к (I) .
Примеры. В этом параграфе будет проиллюстрировано применение изложенного в предыдущем параграфе метода на ряде примеров. В каждом случае будут вычислены вектор-функции Ф к и матрицы TK(J). Инварианты строиться не будут, так как их нахождение достаточно хорошо показано в третьем параграфе. Нам нужно построить точное конечномерное представление удовлетворяющее условию В (2).
Построение полной системы инвариантов от изображений относительно произвольной компактной группы
В предыдущей главе были изложены методы построения полных систем инвариантов, сводящие проблему к хорошо изученной задаче нахождения полных систем инвариантов конечномерных тензоров. При этом, обычно, довольно легко можно найти сколь угодно большое число инвариантов, но как правило, трудно, или даже невозможно указать общую формулу для инвариантов системы. В этом параграфе предлагается метод, использующий специфику задачи и позволяющий получать общие формулы при выполнении некоторых условий, которые будут сформулированы ниже.
Идея метода не нова и состоит в приведении вектора моментов изображения к"стандартному виду". Новое заключается в том, что предлагается общий метод приведения, который можно использовать для широкого класса групп преобразований. Перейдем теперь к изложению метода.
Пусть, как обычно, Q - транзитивная группа Ли преобразований пространства R" , обладающая свойствами А и В (см. 2, глава Д). Тогда каждому изображению можно сопоставлять моменты At к (см.предыдущую главу), которые преобразуются по формуле: (Другие виды преобразований моментов легко приводятся к этому. Например, пусть Тогда, заменив АІ к на Ал к.. по формуле получим то, что нужно).
Тензор к нам будет удобно представлять далее в двух вариантах. В первом случае мы будем считать его вектором (и оставлять для него обозначение М« ) размерности w ( т -размерность Al І ) для которого справедлив закон изменения (I). Во втором случае мы его будем считать матрицей размером mm 1, при этом последний индекс каждой компоненты тензора будет означать номер строки матрицы, а мультииндекс, составленный из первых К-1 индексов, будет являться номером столбца.Эту матрицу мы будем обозначать символом !Л . Закон изменения этой матрицы, как нетрудно убедиться, имеет вид: где символом Т обозначена матрица, транспонированная к Т .
Покажем теперь, что матрица At не вырождена. (На самом деле мы покажем больше, а именно, положительную определенность этой матрицы, откуда сразу будет следовать ее невырожденность). Действительно, как M0zO}feO, Покажем теперь, что последний интеграл не может равняться нулю. Действительно, функция \ не равна тождественно нулю. Следовательно, существует множество ДсЯи такое, что ju (А) 0 , -!((х) О V х 6 А . Тогда из равенства следует, что вектор Л ортогонален вектору т (х) для почти всех Х6 Л (поскольку предполагается, что хї 0 ). Следовательно, для почти всех X А векторы Р (х) лежат в подпространстве, размерность которого меньше М .. Поскольку вектор-функция У обладает свойством а группа Q - транзитивна, то это подпространство является инвариантным для представления Т . Отсюда следует, что век тор а ортогонален вектору У(х) V х є R t а ТОгда компоненты вектор-функции т оказываются линейно зависимыми функциями. Поскольку мы всегда выбираем т таким образом,что бы ее компоненты были линейно независимы {если у , которая обладает всеми требуемыми свойствами, имеются компоненты, линей но зависящие от других компонент, то их можно без всякого ущерба выкинуть), то матрица /Л () положительно определена и, следовательно, не вырождена. Определим теперь уп - мерные векторы Я к формулой:
Найдем закон изменения векторов R « . Предположим теперь, что среди векторов n к имеется m линейно независимых. Пусть это будут векторы RK. у І І m . Обозначим символом R матрицу,столбцами которой являются векторы &к- Тогда, очевидно, R(tf) = T(tfR(f) . (з) Теперь, имея матрицу R ,мы можем привести векторы Лік к"стандартному положению". Обозначим символом 3 матрицу, обратную матрице R . Теорема 5. Система операторов Гот кШ- в кШ. л..-,(4) где S - матрица, построенная выше, К R" -n a tf - полная система инвариантов пары f М о , 3 ) относительно преобразований группы Q , действующих по формуле: мультипликатор меры и является полной системой инвариантов изображения -f относительно группы
Не транзитивные группы преобразований
В этой главе будут рассмотрены различные методы построения полных систем инвариантов, представляющие собой обобщения метода, изложенного в предыдущих главах.
Первое обобщение, которое напрашивается само собой, состоит в том, что рассматриваются группы преобразований, действующие транзитивно не на всем К , а на некотором подмножестве. Очевидно, что в этом случае можно прямо применять разработанный метод, ничего не меняя, то есть, находить вектор-функцию т , строить моменты, а затем инварианты. (Заметим, что в примерах, которые приводились в предыдущих главах, группа часто действовала не на всем пространстве).
Второе обобщение заключается в переходе от скалярных функций, которыми задаются изображения, к векторным. На практике такие функции могут, например, появляться при изучении преобразований цветных изображений, звков, содержащих различные частоты и т.п. Разумеется, в этом случае вся теория также применима, нужно лишь в формулы для моментов подставить вектор-функцию вместо скалярной, а знак умножения заменить, соответственно, на знак тензорного умножения.
Заметим, что в случае, когда изображение задано вектор--функцией, оно не обязательно должно быть финитной функцией. В этом случае область интегрирования можно выбирать,например, следующим образом. Накладываются ограничения на компоненты вектор-функции, и множество точек пространства, в которых значения вектор-функции удовлетворяют этим ограничениям, принимается за область интегрирования. (Ограничения, естественно, выбираются таким образом, чтобы эта область была компактна).
Легко видеть, что для двух функций, отличающихся лишь преобразованием группы, такие области будут отличаться тем же пре- образованием. Другие виды преобразований будут рассмотрены ниже. Пусть -f - финитная вектор-функция с кусочно-непрерывными компонентами, -\ \ R — R .Обозначим символом F мно-жество всех таких вектор-функций. Пусть на К действует транзитивная группа Ли Q преобразований, а на R группа Ли D , которая транзитивна на R \ І U J и оставляет на месте точку (О).
Тогда группа преобразований п = D х ч у являющаяся прямым произведением групп:- Сич, порождает преобразования множества г по формуле: Требуется построить полную систему инвариантов относительно преобразований группы П .
Доказательство. Вектор-функция взаимно однозначная, и, следовательно, ее значения однозначно определяют значения функции . Как уже было доказано ранее, моменты где р - скалярная финитная функция, однозначно определяют функцию р . Поэтому моменты однозначно оп ределяют illt) , а, следовательно, М It) однозначно определяют т [4) и, тем самым, функцию До сих пор мы всегда имели дело с транзитивными группами преобразований. Но иногда требуется построить систему инвариантов для нетранзитивной группы. Это могут быть,например,одно-параметрические группы преобразований. Другой пример появляется, когда рассматривается действие группы преобразований декартовой степени евклидового пространства, порожденной преобразованиями самого пространства.
В этом параграфе будет предложен способ построения полных систем инвариантов для одного класса нетразитивных групп преобразований, использующий идеи метода, описанного в предыдущих главах.
Как обычно, будем считать, что изображения задаются финитными -функциями яркости на пространстве R . Пусть на R действует нетразитивная конечная группа Ли Q непрерывных преобразований. Тогда, как известно, пространство R можно представить в виде объединения областей транзитивности (или, что то же самое, орбит) группы Q ,то есть в виде объединения множеств, на каждом из которых группа действует транзитивно. Обозначим эти множества символом
