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

3.4. Гомоморфизмы конфигураций

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

томе (гл. 2). В остальных случаях требуется более общее определение.

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

Если аналогичным образом — кольца с операторами, записываемыми как сложение и умножение, то пусть гомоморфизм, такой, что

для любых

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

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

а это определяет им различные роли — они находятся в неравных условиях. Следовательно, определение (3.4.3) неприемлемо, и мы не будем им пользоваться.

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

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

следовательно,

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

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

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

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

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

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

Таким образом, условие (I) определения 3.4.1 выполняется и, следовательно, а регулярна, поскольку отображение просто заменило образующие.

Этот гомоморфизм — заменяемые прототипы — можно проиллюстрировать на примере автоматных языков, где ветви заменены прототипами

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

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

Если конфигурация с содержит образующие то

так что условие (I) определения 3.4.1 выполняется. Кроме того.

так что условие (11) определения 3.4.1 выполняется.

Этот гомоморфизм — исключение образующих — естественно возникает в связи с «описаниями», делая их более грубыми.

Пример 3.4.3. Как и в предыдущем примере, — «дискретный) и Пусть образующие составляют множества в некотором опорном пространстве X, и пусть замкнуто относительно пересечения. Пусть образующая является -инвариантной, и определим через ее состав:

состав Легко убедиться в том, что условия определения 3.4.1 выполняются.

Пример 3.4.3 можно непосредственно распространить на другие теоретико-множественные операции более чем с единственным фиксированным множеством однако здесь мы этого делать не будем.

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

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

Применение преобразований подобия означает перенос носителя на некоторое целое число, так что условие (I) определения 3.4.1 выполняется. Выполнение условия (II) в определении 3.4.1 очевидно: оба носителя сокращаются одинаковым образом.

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

Пример 3.4.5. Пусть «квадратная решетка», такое же, как и в примере 3.4.2. — группа переносов на Определим как сужения всех на четыре угловые точки, остов тот же, однако в данном случае с показателями связи, представленными двумерными векторами для связи («восток») и для связи и т. д. Если определить при помощи отображения, сужающего на угловые точки, то можно показать точно так же, как и в предыдущем случае, что некоторый гомоморфизм.

Пример 3.4.6. То же самое, что в примере 3.4.5, но с использованием триангуляции, как в примере 3.1.8. Гомоморфизм осуществляет ограничение на вершины треугольников.

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

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

Пример 3.4.8. Пусть заданы образующие-соответствия, , и пусть разбиение сопоставленного пространства У (не опорного пространства!), причем в каждом подмножестве выделен некоторый элемент Все образующие характеризуются все показатели связей заданы носителем образующих отношение связи и Преобразования подобия, входящие в должны представлять биективные отображения , сохраняющие разбиение и соответствующие значения так что преобразование подобия где является перестановкой целых чисел. Как и выше, мы считаем, что

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

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

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

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

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

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

Пример 3.4.10. Воспользуемся образующими из примера 3.1.11; все являются подмножествами одного пространства «частично упорядоченное множество», (см. т. 1, разд. 2.7). Пусть является таким подмножеством X, что любой суженный на принимает значения в .

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

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

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

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

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

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

связи показатели которых удовлетворяют отношению Определим отображение конфигурации как

В таком случае есть некоторый гомоморфизм.

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

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

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

Поскольку, однако, ковариантно, то выражение (3.4.14) можно записать в следующем виде:

Если положить то последнее выражение превращается в условие (I) определения 3.4.1.

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

что доказывает справедливость условия (II).

Для проверки обратной части утверждения заметим, что поскольку -монотонный, то это автоматически одноатомный тип соединения, и, следовательно, А индуцирует отображение посредством (напомним, что и, следовательно, должно быть одноатомными представлять отдельную

образующую, входящую в . Эта новая образующая должна иметь ту же структуру связей, что и прежняя (см. Примечания Б). Нам также потребуется условие (I) определения 3.4.1, так что причем вместо мы записываем . В таком случае для произвольных входящих в 5, и входящей в справедливо следующее:

и поскольку (напомним о нашем допущении сюръективости h), то отображение гомоморфно. Следовательно, некоторое ковариантное отображение образующих.

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

Многократно применяя условие (II) из определения гомоморфизма, получаем в конечном счете, что

отсюда нетрудно получить утверждение (3.4.13), что и требовалось доказать.

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

Пример 3.4.12. Пусть «линейный», число вершин четное, причем (вход, выход). Определим и

(см. рис. 3.4.1).

Очевидно, что удовлетворяет условиям определения 3.4.1, - это гомоморфизм. Поскольку это отображение включает «две образующие одновременно», оно не является продолжением отображения образующей. Отметим, что этот тип соединения 2 не является монотонным, а гомоморфизм h не является сюръективным.

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

предыдущих работ автора (Grenander 1969, разд. 3 и 4). В этой связи мы докажем следующую теорему.

Рис. 3.4.1

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

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

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

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

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

Если положить то условие (II) сводится к условию и, следовательно, идемпотентно.

Определим отображение на как на и как тождественное отображение на и пусть является подмножеством соединений структуры , не включающим ни одной связи, у которой (см. разд. 3.3). Для того чтобы убедиться в том, что - некоторый гомоморфизм, отметим, что если конфигурация с регулярна при соединениях о, то у конфигурации такие же о. Следовательно, конфигурации и имеют одинаковые соединения. Их состав также одинаков, поскольку индекс класса образующих -инвариантен. Таким образом, условие (I) определения 3.4.1 выполняется.

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

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

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

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