4.2. Автоморфные деформации

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

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

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

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

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

и пульсирующие деформации как

Иногда мы будем пользоваться этими терминами «смещение» и «пульсация» даже в тех случаях, когда -преобразования в (4.2.1) и (4.2.2) не являются обязательно преобразованиями подобия, но могут оказаться преобразованиями образующих более общего вида.

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

Рассмотрим несколько примеров, иллюстрирующих возможности использования этого определения.

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

Если интерпретировать как алфавит, то данная деформация представляет собой обычный шифр.

Случай 4.2.2 (смещенные евклидовы образы). Пусть задана так же, как и в случае 2.3.3, R идентифицирует объединение множеств, деформации определяются соотношением (4.2.1).

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

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

Случай 4 2.3 (пульсирующий кристалл). Рассмотрим изображения, использованные в случае 3.5.1, и пусть группа переносов, действующих в соответствии с (4.2.2). Это означает, что

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

где все двумерные случайные векторы, имеющие одинаковое распределение и независимые друг от друга. Здесь возникает осложнение, которое с первого взгляда может остаться незамеченным. Обратите внимание на то, что мы наблюдаем множество а не точки, снабженные индексами . Это означает, что различные точки будут появляться в на равных основаниях (но не с одинаковыми обозначениями), что затруднит проведение анализа (см. гл. 10, т. 2).

Случай 4.2.4 (искажение терминальных символов). Множество отображений задано на множестве терминальных символов . Для изображения с терминальной цепочкой деформированное изображение определяем как

где

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

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

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

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

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

Здесь образующие, соединенные посредством в точке а.

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

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

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

Случай 4 27 (переупорядочение). Пусть имеет структуру «линейный», однако «истина». Пусть включает группу подстановок, так что отображает где с является просто результатом переупорядочения с.

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

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

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

Новые конфигурации остаются регулярными, так что отображают в и, следовательно, деформации — автоморфные. Эти деформации сохраняют также число образующих в с. Иная ситуация возникает в следующем случае:

Случай 4.2.9 (исчезающие образующие). Рассмотрим образующие с и одинаковыми показателями входной и выходной связей, соединенные с помощью — «линейный».

Рассмотрим конфигурацию в которой отношение полного порядка. отображает с в — упорядоченное подмножество множества

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

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

В таком случае можно непосредственно распространить с на алгебру изображений.

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

Случай 4.2.10 (обобщенный аддитивный шум). Если полугруппа относительно своей бинарной операции то определим деформации как

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

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

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

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

Итак, замкнутое подпространство и еслн Р — вероятностная мера на обозначает соответствующий случайный элемент, то вводится следующее определение:

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

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

Гауссовский шум является одной из важнейших разновидностей аддитивного шума; в этом случае все распределены нормально с параметрами:

Элемент играет роль среднего для гауссовского распределения, а линейный оператор должен быть эрмитовым,

неотрицательным, ограниченным, типа Гильберта — Шмидта с конечным следом.

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

Теорема 4.2.1. Рассмотрим механизм деформации (4.2.11) в сепарабельном гильбертовом пространстве и заданный гауссовским распределением с параметрами (4.2.12). В этом случае является автоморфным в том и только том случае, если

и

Доказательство. Можно записать, имея в виду сильную сходимость почти наверное, что

где собственные значения нормированные собственные векторы, соответствующие независимые нормально распределенные случайные переменные с нулевым средним значением и единичным средним квадратичным отклонением (см., например, монографию Гренандера (1963), стр. 172). Это, однако, с вероятностью единица означает, что случайный элемент пробегает линейное подпространство

Для того чтобы гарантировать следует обеспечить принадлежность всех векторов и этого также должно быть достаточно. Утверждать, однако, что все это то же самое, что требовать выполнения (4.2.14), на чем доказательство завершается.

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

которое, естественно, инвариантно относительно 5.

Деформации, связанные с аддитивным шумом, являются тривиально ковариантными, поскольку сложение коммутативно.

Мы получаем семейство деформаций, порожденных аддитивным гауссовским шумом (см. (4.2.19)), если

определяется параметрами

где фиксированы и обладают теми же, что и выше, свойствами.

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

Рассмотрим компонент изображения

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

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

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

деформацию по Минковскому, где суммирование осуществляется по Минковскому, случайное множество, соответствующее опорной функции Записав это уравнение через соответствующие опорные функции, получаем

Рис. 4.2.1.

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

где расстояние Хаусдорфа, а математическое ожидание увеличения периметра (см. (3.5.69)) равно

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

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

Теорема 4.2.2. (закон больших чисел для выпуклых множеств: (Р. Вайтал). Рассмотрим идеальное изображение (как и выше) и применим к нему последовательность деформаций в соответствии с (4.2.21):

пусть деформированные изображения нормируются с помощью изменения масштаба:

В таком случае

с вероятностью единица; здесь С — выпуклое множество с опорной функцией

Доказательство. Опорная функция деформированного изображения имеет вид

где последних членов распределены независимо и идентично как Здесь можно считать, что опорная функция принадлежит банахову пространству С -нормой. В таком случае, однако, применение усиленного закона больших чисел (см. монографию Гренандера (1963), стр. 177) к среднему значению показывает, что с вероятностью единица оно сходится к среднему, определяемому (4.2.27), по -норме. Топология же -нормы для опорной функции есть то же самое, что топология расстояния Хаусдорфа для выпуклых множеств, на чем доказательство завершается.

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

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

Случай 4.2.11 (отсекающие деформации). Пусть совокупность вероятностных деформаций удовлетворяет следующим условиям:

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

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

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

По мере усечения сети каналов число уменьшается как функция параметра деформации. Можно легко получить точное описание этого процесса.

Теорема 4.2.3. Распределение вероятностей показателя для изображений I величины является биномиальным, причем

Доказательство. Теорема доказывается посредством обычного использования процесса гибели. Положим и введем вероятности

Исходя из условий случая 4.2.11, получаем для

и

что приводит к системе дифференциальных уравнений

Рис. 4.2.2.

Можно убедиться в том, что эти уравнения относятся к типичному процессу гибели. Их можно решить непосредственно, начав с k - m, затем положив и так далее, получив в конце концов

Это выражение, однако, представляет биномиальное распределение где

Так как в результате получаем вероятность

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

Рис. 4.2.3. (см. скан)

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

Случай 4.2.12 (выборка соединений). В этом случае деформированный вариант заданного изображения,

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

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

т. е. в среднем будет иметь меньше соединений.

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

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