Главная > Распознавание образов > Лекции по теории образов. Синтез образов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.4. Деформации опорного пространства

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

Определение 4.4.1. Рассмотрим полугруппу отображений и определим деформированные изображения

Назовем это деформацией опорного пространства.

Рис. 4.3.5. (продолжение) (см. скан)

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

Отметим, что (4.4.1) определяет деформации независимо от идеального изображения в том смысле, что собственно опорное пространство изменяется совершенно независимо от

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

Этот случай возникает, в частности, если деформация образующих, отвечающая следующим условиям:

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

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

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

В случае, когда — группа переносов, распределение для должно быть таким же, как для Другими словами, стационарный случайный процесс.

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

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

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

относительно не внося каких-либо систематических отклонений на протяжении долгого времени.

Если часы идут с постоянной скоростью, за исключением внезапных изменений, происходящих в дискретные моменты времени то можно по-прежнему представлять в виде (4.4.3), однако в данном случае является уже кусочно-постоянной. Точнее, пусть образует пуассонов процесс с интенсивностью X и пусть положительная случайная переменная со средним значением 1; пусть также значения на различных -интервалах распределены независимо. В таком случае так что ни в одном из направлений не наблюдается систематических временных изменений. Этот случай является менее регулярным, чем первый пример.

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

Объединение этих моделей приводит к следующему случаю;

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

Сохраняя условие но не интерпретируя обязательно как время, допустим, что для совместное распределение задается плотностью распределения почти наверное не убывает как функция от

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

где обратная функция

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

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

Число членов может быть меньше величины (4.4.7), что зависит от значений у. Отметим, что в исключительных точках (мера ноль) производные могут не существовать.

Сказанное выше, естественно, не относится исключительно к чебышевским образам: для заданного I соотношение (4.4 6) продолжает выполняться при соответствующих условиях регулярности. Соответствующее соотношение, однако, в зависимости от глобальных свойств изображений-соответствий может включать суммы мощностей, которые не должны быть обязательно ограничены на

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

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

Если содержит точки, не принадлежащие деформированное изображение не определено на всем носителе

Возвратимся к рассмотрению действительной оси и допустим, что отображает [0,1] в самое себя. Деформации опорного пространства частично описываются функциями, представляющими среднее значение и дисперсию:

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

Введем ядро деформаций в виде Допустим, что:

Лемма 4.4.1. Для того чтобы механизм деформации обладал свойствами (4.4.9), необходимо и достаточно выполнения следующих условий:

Доказательство. Если соответствует допущениям (4.4.9), то почти наверное при откуда следует Условие определяется граничными условиями,

налагаемыми на , а условие следует из двух условий непрерывности, содержащихся в (4.4.9).

Обратно, если К удовлетворяет сформулированным условиям, определим с помощью уравнения

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

и поскольку вторая подинтегральная функция неотрицательна, то действительно непрерывны по вероятности.

Для некоторого заданного К можно сформировать целый ряд . Множество, определяемое (4.4.10), представляет ограниченный интерес: для практического использования оно чересчур детерминированно — заданная для одного значения определяет полностью.

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

где неотрицательны, не возрастают и абсолютно непрерывны для всех , причем

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

Случай 4.4.2 (последовательные максимумы). Рассмотрим точки и определим как независимую случайную переменную с функцией распределения

Положим

так что

Эхо выражение разумно определяет все конечномерные распределения в чем можно убедиться, обратив вниманиена то, что — марковское, и вероятность перехода от заданной при определяется как

где Реализации являются ступенчатыми функциями, и длина интервала, на котором остается равной представлена экспонентой (первый член в (4.4.16)) со средним Другими словами, представляет плотность условного распределения скачка.

Рис. 4.4.1.

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

Случай 4.4.3 (упругие деформации). Введем где смещение и определяется дифференциальным уравнением

и почти наверное.

Поскольку функция Грина для (4.4.17) определяется как

деформации принимают следующую форму: 1

Если силовое поле непрерывно по среднему значению, определяется среднеквадратичная производная

На рис. 4.4.2 приведены результаты моделирования двумерного варианта этого случая: на рис. 4.4.2, а представлен а на и деформированные изображения. В данном, случае в качестве поля использовался белый шум, и поэтому неравенство 1 не выполняется. В результате, как видна из рис. 4.4.2, изображение оказывается обернутым вокруг самого себя.

Если из (4.4.19) следует, что представляет чистые деформации, причем

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

Для систематических деформаций на интервале [0, 1] ответ выглядит следующим образом.

Теорема 4.4.1. Если непрерывная функция на [0,1] и левосистематическое, то для любого предел существует и равен 0 или 1.

Доказательство. Во-первых, очевидно, что для фиксированного последовательности образуют

мартингал и сходятся почти наверное к пределу у. Если функ распределения у обозначена через то должно иметь место условие

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

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

Рис. 4.4.2.

Случай чистых деформаций подобен только что рассмотренным, однако требует использования другого метода. Для того чтобы лучше в нем разобраться, мы начали с моделирования чистых деформаций; на рис. 4.4.3 представлены последовательные деформации для

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

Пусть реализуется в виде одной из функций, каждая из которых характеризуется вероятностью 0,5:

и

Если связать с выбором в последовательной деформации выбором то можно записать

где

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

Рис. 4.4.3.

Теорема 4.4.2. Если I — непрерывное и чистые деформации с непрерывной обращающейся в нуль только при

х = 0 или 1, то существует случайная переменная такая, что

по вероятности.

Доказательство. Рассмотрим вторые моменты для

и отметим, что, поскольку — чистые деформации,

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

причем не убывает. Чистота деформаций, однако, предполагает, что и поэтому предел — единственный. Неубывающий характер означает существование переменной со сформулированными свойствами.

Из условий теоремы 4.4.2 с тем исключением, что в данном случае обращается в нуль в точках очевидно, что обеспечивает и в связи со свойством неубывания Следовательно вышеприведенное рассуждение можно применить к каждому интервалу, доказав в результате существование случайных переменных причем

Следовательно, несколько ординат идеального изображения появятся в пределе для

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

Случай 4.4.4 (инфинитезимальные деформации). Для введем

где обращается в нуль при , непрерывна по и равномерно ограничена некоторой случайной переменной Знак в (4.4.33) выбирается с равной вероятностью.

Пусть -предел по вероятности где таком случае инфинитезимальная скорость (см. монографию Феллера (1957)) определяется

а инфинитезимальная дисперсия — как

где функция распределения Следовательно, переменная имеет плотность распределения удовлетворяющую уравнению

начальными условиями для которого являются -функция в при

Отметим, однако, что это не просто (одномерный) диффузионный процесс. Как раз наоборот, мы должны учитывать все значения одновременно, так что возникает случайное поле на [0, 1], изменяющееся во времени в соответствии с непрерывной полугруппой деформаций

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

Непосредственное вычисление дает

это уравнение известно в связи с популяционной генетикой; его решение можно записать в виде ряда при помощи многочленов Гегенбауэра (см. монографию Баруча-Рид (I960)).

Аналоги теоремы 4.4.2 и деформаций (4.4.33) более высоких размерностей не исследовались. Многообещающим представляется случай, когда X — единичный квадрат. Очевидно, внутренние точки будут перемещаться в сторону границы, и имеет смысл обратиться к теореме потенциала. Следует, однако, заметить, что в данном случае этого будет недостаточно, так как, деформирующий механизм воздействует на все точки X

одновременно, а не только на их безусловное (двумерное) распределение.

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

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

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

В самом деле, этот объем будет повернут относительно оси вектора

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

или, более подробно, как

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

объемного элемента определяется дивергенцией

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

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

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

Рис. 4.4.4.

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

где F - сила, F = -V. Начальными условиями системы являются и некоторые заданные значения

Следующий случай будет рассмотрен для идеального изображения-соответствия на при фиксированном значении параметра деформации

Случай 4.4.5 (линейные деформации решетки).

для тех k, для которых представление задано. Таким образом, деформированное изображение является вектором, быть может, с недостающими компонентами.

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

Во-вторых, может оказаться, что некоторые меньше 0 или больше 1. В этом случае соответствующий компонент вектора не определен.

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

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

с начальными условиями или, в матричной форме,

где

В таком случае решением (4.4.48) является линейная комбинация где собственные значения М,

Приведя матрицу к диагональному виду в качестве элементов главной диагонали можно записать решение через ортогональную матрицу О:

где .

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

где положительный коэффициент трения.

Устойчивое решение (4.4.53) можно записать в спектральном представлении:

где ортогональный векторно-значный процесс. Решая уравнение (4.4.53) относительно получаем

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

и с помощью (4.4.56) и (4.4.6) можно вычислить вероятностную меру для деформированного изображения Этот результат будет полезен нам при анализе образов, рассматриваемом в части III. Деформации опорного пространства возникают и в других контекстах, например, когда X — конечно. Если деформации относятся к типу то осуществляется просто перестановка точек X, так что работает на симметрической

группе, определенной на объектах. Рассмотрим более общий случай, когда задана компактная группа Г с элементами у и механизм деформаций определен следующим образом.

Случай 5.4.6 (деформации компактной группы). При определяется

где П — вероятностная мера на Г. Введем множество несводимых и неэквивалентных унитарных представлений Г, где тождественный оператор. Обозначив распределение вероятностей на Г, порожденное через и введя преобразование Фурье

получаем следующее соотношение:

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

с решением вида

так что, использовав в качестве начального условия единичный элемент получаем

откуда можно получить воспользовавшись соотношениями ортогональности для элементов матриц представлений (см., например, монографию Понтрягина (1973), гл. 5, § 32).

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление