Геометрическая интерпретация энтропии Комеч Сергей Александрович

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Комеч Сергей Александрович. Геометрическая интерпретация энтропии: диссертация ... кандидата Физико-математических наук: 01.01.02 / Комеч Сергей Александрович;[Место защиты: Институт проблем передачи информации им. А. А. Харкевича Российской академии наук].- Москва, 2016

Содержание к диссертации

Введение

Глава 1. Искажение границы в символических системах 16

1.1. Введение 16

1.2. Основные определения и формулировка результатов 16

1.3. Доказательство теоремы 1.1 22

1.4. Доказательство теоремы 1.2 30

Глава 2. Скорость искажения границы в гладких динамических системах

2.1. Введение и формулировка основных результатов 35

2.2. Доказательства 36

Глава 3. Дескриптор формы изображения 43

3.1. Введение 43

3.2. Формулировка и доказательства основных результатов 43

3.3. Компьютерная обработка и численные результаты 52

Литература

Основные определения и формулировка результатов
Доказательство теоремы 1.2
Доказательства
Компьютерная обработка и численные результаты

Введение к работе

Актуальность работы

Роль шенноновской энтропии в теории информации всесторонне описана в литературе. Хорошо известно также, что А.Н. Колмогоров ],] использовал это понятие при определении нового метрического инварианта сохраняющих меру преобразований вероятностных пространств, играющего фундаментальную роль в эргодической теории. Это определение было усовершенствовано Я.Г. Синаем ].

Для символических динамических систем, т.е. сдвигов в пространствах последовательностей с конечным алфавитом, энтропия Колмогорова-Синая — это не что иное, как средняя условная энтропия настоящего при условии прошлого для стационарного случайного процесса (в другой терминологии — скорость создания информации источником).

В настоящей работе энтропия Колмогорова-Синая рассматривается с геометрической точки зрения как скорость роста объема границы множества в фазовом пространстве под действием динамики. Такая интерпретация возникла в физической литературе, а именно в книге Г.М. Заславского ], где выдвинута гипотеза о том, что объем границы множества в фазовом пространстве растет экспоненциально по времени с показателем, равным энтропии. Однако в буквальной интерпретации эта гипотеза неверна и нуждается в серьезном уточнении. Подобная корреляция энтропии с объемом, точнее с площадью поверхности, обсуждается также в недавней (2012 г.) научно-популярной книге Яу и Надис ].

Впервые строгий математический результат был получен в работе Б.М. Гу-ревича [] для случая символических марковских систем. Однако аналогичный результат справедлив для гораздо более широкого класса динамических систем, включающего в себя как символические системы (синхронизованные,

в частности, софические), так и гладкие (системы Аносова). Именно такое распространение упомянутой выше гипотезы и составляет основное содержание глав I и II данной диссертации.

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

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

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

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

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

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

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

Цель диссертационной работы

Главной целью главы I является установление равенства энтропии Колмогорова-Синая и локальной скорости деформации границы (ЛСДГ) для

синхронизованных символических систем, если деформация границы измеряется в терминах инвариантной меры и число итераций растет не быстрее некоторого порога. При этом локальная скорость понимается как предел в L\ по фиксированной инвариантной мере. В данной главе мы развиваем соответствующую математическую теорию для синхронизованных систем, которые включают в себя, в частности, все марковские сдвиги. Однако класс синхронизованных систем значительно шире и включает в себя все непрерывные образы марковских сдвигов, так называемые софические системы (sofic systems) Вейсса ], которые, как можно считать, не ограничивая общности, получаются из марковских сдвигов при помощи побуквенного кодирования. Синхронизованные системы были введены в работе [10].

Главной целью главы II является исследование ЛСДГ для гладких систем на римановых многообразиях. Для таких систем, в которых имеется риманова структура, естественно измерять ЛСДГ в терминах меры Лебега, которая в общей ситуации не инвариантна. Мы отдельно изучаем динамику внутри неустойчивого слоя с целью установления связи между объемом окрестности образа множества и якобианом вдоль неустойчивого слоя, который, в свою очередь, связан с показателями Ляпунова и энтропией.

Главной целью главы III является применение идей, на которых основаны главы I и II, для построения дескриптора формы изображения (ДФИ), который является аналогом ЛСДГ, характеризующим сложность границы изображения. Построенный ДФИ даёт нам возможность определить расстояние между разными формами и находить ближайших соседей ("похожие"по форме изображения). Мы используем семейство деформирующих отображений, главной целью которых является выявление особенностей границы формы изображения и соответствующих им направлений. Наша цель заключается в том, чтобы сопоставить изображению функцию, а форме — класс функций.

На полученном пространстве, элементами которого являются классы функций, мы вводим естественную метрику, которая и позволит нам вычислять расстояния между формами изображений, точнее, между классами функций, которые им соответствуют. Для установления связи между пространством форм и пространством значений ДФИ доказывается теорема о непрерывности отображения метрического пространства форм в метрическое пространство значений дескриптора. Следует также отметить, что мы предлагаем математическую модель с низкой вычислительной сложностью.

Научная новизна

Сначала опишем новизну полученных результатов по главам. Новизна результатов главы I состоит в распространении геометрической интерпретации энтропии марковских систем ] на более широкий класс символических систем.

В главе II впервые геометрическая интерпретация энтропии в терминах ЛСДГ дана для гладких динамических систем, а именно для равномерно гиперболических (систем Аносова, см. Теорема 2.1, Следствие 2.5).

В главе III мы предлагаем новый подход к построению ДФИ, идейно близкий к методам глав I и П.

В более подробном изложении новизна результатов диссертации заключается в следующем. Ранее связь энтропии с ЛСДГ была обнаружена ] лишь для марковских систем, и одним из основных инструментом при доказательстве было использование классической теоремы Шеннона-Макмиллана-Бреймана. Мы также используем эту теорему для анализа границы подмножества фазового пространства. Однако в случае синхронизованных систем, изучаемых в главе І, в отличие от марковских, оценка снизу для основного выражения, характеризующего искажение границы, выполняется не на множестве полной меры. В этом одна из трудностей рассматриваемого случая. Другая состоит в том, что для покрытия образа шара приходится использо-

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

Одной из важных особенностей предлагаемого подхода является согласование размеров подмножества и числа итераций. В главе II мы впервые применяем это условие согласования для гладких динамических систем и устанавливаем равенство суммы положительных показателей Ляпунова и ЛСДГ, при условии, что число итераций растет не быстрее некоторого порога. Это равенство имеет место почти всюду по фиксированной инвариантной мере.

В главе II мы вычисляем ЛСДГ для гладких систем. Новизна нашего подхода состоит в том, что деформация границы измеряется в терминах меры Лебега, которая, вообще говоря, не инвариантна. Для автоморфизмов n-мерного тора мера Лебега является инвариантной, и в этом случае в ] была установлена сходимость допредельной ЛСДГ к энтропии во всех точках многообразия. Однако в общей ситуации мера Лебега не инвариантна, но оказывается, по крайней мере для диффеоморфизмов Аносова, что ЛСДГ, как функция от точки, равняется сумме положительных показателей Ляпунова, соответствующих инвариантной эргодической мере, почти всюду по этой мере (Теорема 2.1). Согласно результатам Песина ] и более общим результатам Ледрапье и Янг ],] эта сумма показателей Ляпунова, в свою очередь, совпадает с энтропией Колмогорова-Синая, если инвариантная мера является мерой Синая-Рюэля-Боуэна.

В главе III данной диссертации вводится новый ДФИ, изучаются его свойства и естественные метрики на пространстве форм изображений и на пространстве значений дескриптора. На пространстве форм мы вводим метрику и доказываем, что она корректно определена. Новизна нашего подхода состоит в том, что изображению ставится в соответствие функция, связанная с деформацией изображения под действием семейства линейных преобразова-

ний. Цель таких преобразований — смоделировать наблюдение плоского изображения под разными углами и выявить характерные особенности границы, такой подход ранее не применялся. Форма изображения есть класс изображений, эквивалентных с точностью до изометрий и масштабирований. Таким образом, форме изображения ставится в соответствие класс функций, эквивалентных по соответствующему отношению. Полученные классы функций и представляют собой пространство значений ДФИ.

Практическая значимость

Результаты глав I и II носят в основном теоретический характер.

Результаты главы III могут найти важное практическое применение при численном моделировании в задачах, связанных с распознаванием изображений. Предложенный нами дескриптор формы показал высокую эффективность в применении к задачам распознавания форм на стандартных базах изображений КІМІА, MPEG7 ].

На защиту выносятся следующие основные результаты и положения:

Для синхронизованных символических систем с произвольной эргоди-ческой инвариантной мерой установлено равенство локальной скорости деформации границы (ЛСДГ) и энтропии Колмогорова-Синая, если деформация границы измеряется в терминах инвариантной меры и число итераций растет не быстрее некоторого порога.
Рассмотрены гладкие равномерно гиперболические системы, системы Аносова, на компактных римановых многообразиях. Для таких систем с произвольной эргодической инвариантной мерой установлено равенство ЛСДГ и суммы положительных показателей Ляпунова (с кратностями), соответствующих инвариантной мере, если деформация границы измеряется в терминах меры Лебега и число итераций растет не быстрее некоторого порога. Это равенство имеет место почти всюду по фиксированной инвариантной мере. В

качестве следствия получено равенство между ЛСДГ и энтропией Колмогорова-Синая, если инвариантная мера является мерой Синая-Рюэлля-Боуэна.

3. На пространстве форм введена метрика и предложен новый дескриптор формы изображения. Доказана теорема о непрерывности отображения метрического пространства форм в метрическое пространство значений дескриптора. Приведены результаты численного моделирования на классической базе изображений.

Апробация работы

Основные результаты диссертации докладывались на следующих конференциях: Конференция молодых ученых МГУ "Ломоносов 2005" (Москва, 2005); Dynamical Systems: Geometric Structures and Rigidity (Бедлево, Польша, июль 7 - 26, 2008); «Информационные технологии и системы» конференция молодых ученых и специалистов ИППИ РАН (ИТиС 2008, 2010, 2011 Геленджик, 2013 Калининград); XVI International Congress on Mathematical Physics (3-8 августа, 2009, Прага, Чехия); Topology, Geometry, and Dynamics: Rokhlin Memorial (11-16 января, 2010, Санкт-Петербург); European Conference on Iteration Theory (12-17 сентября, 2010, Нант, Франция); Partial Differential Equations in Mathematical Physics (ИППИ, Москва, май 2011); Международная конференция «Дифференциальные уравнения и смежные вопросы», посвященная 110-летию со дня рождения И.Г. Петровского (МГУ им. М.В. Ломоносова, Мат. ин-т им. В.А. Стеклова, 29 мая-4 июня , Москва, 2011); 4th International Conference on Pattern Recognition and Machine Intelligence PReMI'll (27 июня -1 июля, ВШЭ, Москва, 2011); XVII International Congress on Mathematical Physics ICMP12 (6-11 августа, Ольберг, Дания, 2012); Erdos Centennial (1-5 июля, Будапешт, Венгрия, 2013); Geometrie et systemes dynamiques (CIRM, с 31/03/2014 no 04/04/2014, Марсель, Франция).

Основные результаты диссертации докладывались на следующих научно-

исследовательских семинарах:

«Эргодическая теория и статистическая физика», механико-математический факультет МГУ (неоднократно).

Семинар Добрушинской математической лаборатории, Институт проблем передачи информации РАН, 2010, 2015 г.

«Дифференциальные уравнения и динамические системы», механико-математический факультет МГУ, 2015 г.

«Петербургский семинар по теории представлений и динамическим системам», Санкт-Петербургское отделение Математического института им. В.А. Стеклова Российской академии наук 2015 г.

Публикации

Материалы диссертации опубликованы в 12 печатных работах, из них 5 статей в рецензируемых журналах , -] (4 из которых опубликованы в журналах, рекомендованных ВАК -]), 5 статей в сборниках трудов конференций [19-] и 2 в сборниках тезисов докладов , ].

Личный вклад автора

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

Структура и объем диссертации

Основные определения и формулировка результатов

Всевозможные конечные последовательности w = abc... h символов из А будем называть словами (в алфавите А). Слову w длины \w\ и паре /с, / Є Z, где / = к + \w\ — 1, отвечает цилиндрическое множество Cj if] с носителем [к,1], состоящее из всех таких х Є X, что Xk ... xi = w.

Определение 1.1. Подмножество Y С X называется марковским множеством порядка т 1, если существует такое множество слов F С Am+l, что у = (уі, і Є Z) Є Y тогда и только тогда, когда yj ... yj+m Є F Vj Є Z. Ограничение динамики сдвига S на множество У определяет систему (Y,S), которая называется марковским сдвигом (subshift of finite type) порядка т. Очевидно, всякое марковское множество замкнуто и -инвариантно. Пусть Y — произвольное замкнутое -инвариантное подмножество множества X. Слово и будем называть допустимым (Y-допустимым) или просто У-словом, если оно встречается в некоторой бесконечной последовательности из У, т.е. если С\ [и] П Y т 0 при некотором к Є Z. Определение 1.2. Система (Y,S) называется транзитивным подсдвигом (сдвига S на X), если для любых Y-слов и} v существует такое Y-слово и, что uuv — Y-слово. Транзитивный подсдвиг называется синхронизованной системой, если существует такое Y-слово w (волшебное слово), что для любой пары Y-слов и} v допустимость слов uw и wv влечет допустимость слова uwv.

Пример 1.1. Покажем, что неприводимый марковский сдвиг произвольного порядка т является синхронизованной системой и каждое допустимое слово длины не меньше т + 1 является волшебным. Пусть w — произвольное допустимое слово длины к т + 1. Рассмотрим допустимые слова u v, такие что uw и wv допустимы. Докажем, что слово uwv допустима. Для этого, так как сдвиг марковский порядка т, нам достаточно проверить, что любое подслово из uwv длины т + 1 допустимо. Очевидно, что подслово длины т + 1 целиком лежит либо в uw, либо в wv, так как \w\ т + 1. Из допустимости слов uw и wv следует допустимость любого их подслова, что и завершает доказательство.

Несложно показать, что всякое слово, содержащее волшебное слово, тоже является волшебным. Пусть w — волшебное слово и u=vwv . Пусть допустимы слова zu и uz . Докажем, что это влечет допустимость слова zuz . Заменяя и на vwv получаем, что слова zvwv и vwv z допустимы. Следовательно допустимы слова zvw и wv V (как подслова допустимых слов), и значит, так как w — волшебное слово, слово zvwv z = zuz допустимо.

Напомним определения маркированного графа и софической системы.

Определение 1.3. Маркированный граф есть набор (G, L), где G — граф, состоящей из конечного числа вершин и соединяюищх их направленных ребер, a L — отображение, маркирующее каждое ребро е буквой L(e) из конечного алфавита A. YQ состоит из всех бесконечных двусторонних последовательностей ... Ь(е-іЬ(ео)Ь(еі)..., где ... Є-\Єф\... — произвольная допустимая последовательность ребер, задающая бесконечный двусторонний путь в графе G.

Определение 1.4. Подсдвиг Y С X называется софическим, если Y = YQ для некоторого маркированного графа G. Ограничение динамики сдвига S на Y определяет софическую систему (У, S).

Определение 1.5. Класс продолжений Fy(w) для Y-слова w есть совокупность всех Y-слов, которые могут идти после словаw, т.е. Fy(w) состоит из всех таких Y-слов v, что wv тоже Y-слово. Например, для сдвига Бернулли, когда все слова из {0,1} допустимы, для разных слов класс продолжений всегда один и тот же, и этот класс состоит из всех допустимых слов. Таким образом, для сдвига Бернулли есть только один класс продолжений.

Система является софической тогда и только тогда, когда количество различных классов продолжений конечно (см. [47] 3.2).

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

Пример 1.2. Рассмотрим алфавит {а, 6, с} и подсдвиг (У, S), в котором запрещены слова abmcka при т=к. Всякое допустимое слово, содержащее а, является волшебным для этой системы. Эта система не является софической, так как для слов аЪ, abb, ..., abk, ... их классы продолжений различны (слово ска входит только в один класс). Следовательно для этой системы бесконечное число классов продолжений и она не является софической.

Несложно показать, что софическая система является синхронизованной. Пример 1.3. Рассмотрим любое допустимое в софической системе (Y,S) слово w = w\.. .Wk,Wi Є Д1 і к . Пусть оно не является волшебным. Это означает, что существуют такие допустимые слова u v, что uw и wv допустимы, a uwv — нет. Из допустимости слова wv следует, что v Є Fy(wi.. .Wk) при всех 1 г к. Из недопустимости uwv следует, что v ф FY(UW) и, значит, класс продолжений слова uw не совпадает ни с одним из классов продолжений окончаний слова w (и, конечно, самого слова w). Рассмотрим слово uw. Пусть оно не волшебное. Аналогично приведенным выше рассуждениям получим, что при некотором допустимом и все классы FY(U UW)}FY(UW) и Fy(w) различны. Ясно, что процесс оста новится, так как в софической системе конечное число различных классов продолжений.

Для любых О, Є (0,1) и Є обозначим через е{,) шар в (, e) радиуса с центром в . Для любого множества С (, 6 ) обозначим через e{) его открытую окрестность. Ясно, что {,) = f ({}).

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

Для синхронизованной системы мера с таким свойством существует. Более того, существует мера, носителем которой является всё синхронизованное множество (см. [48]), а в таком случае мера любого цилиндрического множества положительна.

Вследствие эргодичности меры из условия (1.2) вытекает, что для ПОЧТИ каждого Є найдется такое {) Є N, что Теперь сформулируем основное утверждение этой главы. Теорема 1.1. Пусть (,) — синхронизованная система и — эргодическая -инвариантная вероятностная борелевская мера, сосредоточенная на . Предположим, что существует волшебное -слово , для которого выполнено условие (1.2). Тогда для любой функции : М+, удовлетворяющей условиям

Доказательство теоремы 1.2

В этой главе мы рассматриваем гладкие динамические системы на ри-мановых многообразиях. Для таких систем мы оцениваем ЛСДГ в терминах естественной меры Лебега, хотя она может и не быть инвариантной.

Рассмотрим компактное метрическое пространство (X, р) и его гомеоморфизм /. Для всякого множества А С X обозначим через Оє(А) его е-окрестность. Пусть В(х,г) С X — шар радиуса г с центром в точке х. Мы рассматриваем асимптотику отношения

В первой главе мы изучали асимптотику отношения (2.1), используя в качестве /і инвариантную меру. Для гладких систем (диффеоморфизмов ри-мановых многообразий) под /і в (2.1) естественно понимать также риманов объем vol. Для гиперболических автоморфизмов n-мерного тора (когда vol — инвариантная мера) в [11] была установлена сходимость (2.1) к сумме положительных показателей Ляпунова, которая совпадает с энтропией таких систем. Причем сходимость имеет место во всех точках тора. В общей ситуации риманов объем не инвариантен относительно /, однако оказывается, что, по крайней мере для диффеоморфизмов Аносова, выражение (2.1) сходится почти всюду к сумме положительных показателей Ляпунова.

Основную теорему этой главы мы доказываем для систем Аносова (равномерно гиперболических систем, см. [51] 6.4).

Для 6 0 обозначим через W${x) и W${x) соответственно локальное устойчивое и неустойчивое многообразие диаметра 5 в точке х. При фиксированном 5 0 будем считать, что є достаточно мало для того, чтобы при всех х,у Є М пересечение Wj-(y) П Wg(x) состояло ровно из одной точки при р(х,у) є, где р — риманова метрика (см. [51], Предложение 6.4.13). Рассмотрим множество

Множество Ри(х,є) есть "проекция" В(х,є) на W${x) вдоль устойчивых слоев wss. Для х Є М и г 0 обозначим через Ви(х} г) шар радиуса г в слое W#(x) с центром в точке х (в индуцированной метрике ри). Лемма 2.2. Найдутся С\}С2 0, такие что при всех х Є М и достаточно малых є О Ви{х,С\є) С Ри{х,є) С Ви{х,С2е).

Доказательство. Угол между Wj-(x) и Wg(x) является непрерывной функ цией от ж и отделен от нуля (см. [51], Предложение 6.4.14), поэтому расстояние от "проекции" любой точки шара В(х, є) на W {x) (вдоль устойчивых слоев Wg) до точки х не будет превосходить Се при некотором С, не зависящем от х. Таким образом, при достаточно малых є, при всех у Є Ри(х,є) С W#(x) будет выполнено р(х,у) Се. Следовательно, ри(х,у) С ІЄ при некотором С2 0. Ясно, что С\ можно положить равным 1. Следующая лемма даёт возможность получить оценки сверху и снизу на рост объема внутри неустойчивого слоя. Лемма 2.3. Пусть 7 0 и {В(х),є 0},ж Є М, — семейство подмножеств из Wf{x), таких что с1іат( "(х)) е и х Є В (х) при всех е. Если для f, к (є) и v выполнены условия теоремы 2.1, то для v-n.e. х Є М где ри — индуцированный риманов объем на соответствующем локальном неустойчивом многообразии.

Доказательство. Для упрощения записи мы будем писать к вместо к (є) и В вместо В(х). Якобиан отображения в неустойчивом направлении Ju является непрерывной функцией на М (см. [51], 19.1), и мы можем применить

Следовательно, p(xi,/гх) є[5г. Для диффеоморфизма Аносова класса С +а якобиан Ju удовлетворяет условию Гёльдера с показателем а и некоторой константой С 0 (см.[51], 19.1, Следствие 19.1.3), и мы получаем оценку сверху

Из (2.7) следует, что второе слагаемое из правой части (2.6) стремится к нулю при є — 0. Первое слагаемое zz-п.в. сходится к А+ (подробнее о якобиане в неустойчивом направлении см. [28], [51] 20.4, Теорема 20.4.1), что завершает построение оценки сверху. Несложно показать, что похожим образом получается и оценка снизу:

Доказательство. Оценки (2.9) следуют из компактности М и непрерывно сти положительно определенной формы, задающей риманову метрику. Нера венства (2.10) справедливы в силу того, что кривизна/кУє Ви(ж, є) ограничена (см. [52], Section 3, где рассматривается более общая ситуация). Параметры Ь{а) и д(с, d) могут зависеть от метрик р и ри соответственно. Вернемся к доказательству основной теоремы 2.1. Мы построим по индукции конечный набор точек уі Є fk Pu(x,e), 1 і N(e), таких что шары В(уі}є) покрывают множество / Ри(х} є), а шары с теми же центрами, но меньшего радиуса, не пересекаются. А именно,

На первом шаге выберем произвольно точку у\ Є fk Pu(x,e). Пусть точки 2/1,. .. ,ут уже выбраны и шары B(jji,s), 1 і m, удовлетворяют условию (2.12), но не покрывают fk Pu(x, є). Добавим в набор произвольную непокрытую точку ут-\-\. Очевидно, и, таким образом, условие (2.12) выполнено при 1 і j m + 1. Так как М компактно, то процесс непременно остановится после конечного числа шагов. Шары с центрами в построенном наборе точек yi мы используем для получения оценок сверху и снизу для центрального отношения из нашей теоремы.

Доказательства

Каждое изображение из нашего вспомогательного пространства можно интерпретировать как некоторый гомеоморфный образ шара U под действием преобразования Т. Основная идея, лежащая в основе предлагаемого дескриптора формы, заключается в изучении деформации границы изображения T(U) под действием семейства преобразований. Деформацию границы мы измеряем в терминах объема, так же как и ЛСДГ во второй главе. В этом прослеживается определенная аналогия с геометрической интерпретацией энтропии, которой посвящена первая и вторая главы.

Мы вводим семейство линейных преообразований {РЫ): 7Є[-,], /3 1}, каждое из которых растягивает в направлении под углом 7 в (3 раз, а в ортогональном сжимает в (3 раз и, следовательно, сохраняет площадь(см. рис. 3.1). Соответствующее семейство матриц имеет вид / в cos2 7 + \ sin2 7 (/3 - 4) sin 7 cos 7 \ \(р - 4) sin 7 cos 7 psm 7 + cos 7/

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

Рассмотрим множество единичной площади а Є S, которому соответствует некоторый гомеоморфизм Т единичного шара U, т.е. а = T(U). Дескриптор формы, который мы определяем, основан на изучении отношения

На рис. 3.2 приведены изображения квадрата и круга и соответствующие им функции при фиксированных (Зяє. Очевидно, что Pf а){а) непрерывно зависит от є,7 и (3. Ясно также, что эта функция периодическая по 7 с периодом 7Г. Можно считать, что 7 Є К, при этом функция будет периодической по 7- Например для круга при фиксированном (3 эта функция будет константой.

Пусть RQ — поворот на угол #, а а — симметрия относительно некоторой оси. Очевидны следующие свойства функций Pf о){а) Утверждение 3.2. При всех 7 Є [—,] (7,/3)№а) ((7+f+6 )mod(7r)-f,/3) (a) Р(П,Р) (СГ(2) = (-7,/3)(а) Пусть R — группа, порожденная преобразованиями функций из Утверждения 3.2. Таким образом, для формы А Є мы можем определить пространство Л4 их характеристик — значений нашего дескриптора: Другими словами форме А ставится в соответствие класс непрерывных функций, переходящих друг в друга под действием элементов группы R.

При фиксированном (3 мы будем иметь функции ("сечения" поверхности), аналогичные приведенным на рис. 3.2. Ясно также, что в "сечении" /3 = 1, когда ни в одном из направлений нет ни растяжения, ни сжатия, соответствующая функция есть константа, зависящая от изображения. На рис. 3.3 приведен приближенный вид поверхности для изображения быка. Можно заметить, что функция PV1 Q)XOL) возрастает быстрее в двух направлениях — ног

Бык (вверху слева) и часть соответствующей поверхности PL ау Изображения внизу при действии .F(7)/3) при /3 = 2 и 7 = тг/4,7г/2, — 7г/4, 0 (цвет изображения — черный, окрестности — серый). и туловища. На рис. 3.4 наибольший рост соответствует направлению размаха крыльев орла.

На пространстве Л4 мы рассматриваем следующую метрику I: где к О, а Є unit(A)1 b Є ипй(В). Интеграл в правой части сходится, так как P )( ) растет по (3 на бесконечности не быстрее, чем линейно. Заметим, что если в правой части зафиксировать а или 6, то значение нижней грани не изменится.

Мы получили отображение из пространства форм S с метрикой (3.2) в пространство характеристик Л4 с метрикой (3.15). Построенное отображение метрических пространств является непрерывным.

Мы применили разработанный нами подход к данным из базы изображений MPEG-7 СЕ Shape-1 Part-B (см. [59]), состоящей из 7 различных групп, по 20 изображений в каждой группе. Изображения в каждый группе сходны по форме, но имеют существенные отличия друг от друга (см. рис. 3.5).

Первый шаг заключался в приведении всех изображений к единому размеру площади. На втором шаге для каждого изображения вычислялось значение дескриптора, который представляет собой вектор параметров. Параметры суть значения соответствующей функции (f о) в разных точках (точка определяется набором: направление (угол ) и коэффициент растяжения ). Например, на рис. 3.1 приведено изображение руки , для которого (f () = 1.23. После применения преобразований мы получаем соответственно (L/22)() = 1.33 и (:02)() = 1.20. Как и можно было ожидать: при растяжении вдоль направления пальцев соответствующая функция возрастает, а при сжатии вдоль этого направления убывает.

На третьем шаге вычислялось расстояние между соответствующими сигнатурами. Мы использовали четыре направления, соответственно сигнатура состояла из восьми векторов, которые соответствуют четырем поворотам изображения (при фиксированном значении коэффициента растяжения получаем циклические перестановки координат векторов (см.ниже)) и их сим-метриям. Другими словами, сигнатура в данном случае есть набор векторов, которые соответствуют изображению и его поворотам на некоторый набор углов, а также соответствующим симметриям. Напомним, что сдвиги не влияют на значение функции (f о), а повороты и симметрии влияют (см. Утверждение 3.2).

Компьютерная обработка и численные результаты

Основную теорему этой главы мы доказываем для систем Аносова (равномерно гиперболических систем, см. [51] 6.4).

Теорема 2.1. Пусть f — С2 диффеоморфизм Аносова, действующий на компактном римановом многообразии М без края, и v — f -инвариантная эргодическая борелевская вероятностная мера наМ. Тогда, для всякой функции к : М+ — Z+, удовлетворяющей условиям (2.2), и и-п.в. х Є М обозначим через W${x) и W${x) соответственно локальное устойчивое и неустойчивое многообразие диаметра 5 в точке х. При фиксированном 5 0 будем считать, что є достаточно мало для того, чтобы при всех х,у Є М пересечение Wj-(y) П Wg(x) состояло ровно из одной точки при р(х,у) є, где р — риманова метрика (см. [51], Предложение 6.4.13). Рассмотрим множество

Преобразование / растягивает вдоль неустойчивых слоев. Следовательно, если его применять не к исходному шару Ви{х С2е\ а к его є-окрестности — шару Ви(х, (С2+1)є), то образ при растяжении будет шире, чемє-окрестность образа Ви(х} С2е). Отсюда получаем 0 (fk{)Bu(x, С2є)) С fk{)Bu(x, (С2 + 1)є). (2.15) Из (2.12) и (2.14)-(2.15) следует, что Так как / сжимает вдоль устойчивых слоев, множества f є В{х,є) и fk y Pu(x,e) сближаются при є — 0 (образ шара "расплющивается" вдоль своего центрального неустойчивого слоя, сжимаясь к нему). Следовательно, при достаточно малых є (и, соответственно, больших к (є))

Так же как и при оценке сверху, первое слагаемое в правой части сходится к сумме положительных показателей Ляпунова меры z/, а последние два сходятся к нулю zz-почти всюду при є — 0.

Полученные оценки завершают доказательство основного результата этой главы. Для важного класса SRB мер (мер Синая-Рюэлля-Боуэна, активно изучаемых в теории динамических систем и в статистической физике (см. [53] и [54] 13 ), установлено, что их энтропия совпадает с суммой положительных показателей Ляпунова [13], и мы получаем следующее утверждение о связи ЛСДГ с энтропией.