3.7. Операции на изображениях

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

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

Изображение и, обладающее тем свойством, что при произвольном и соединителе а имеет место а называется (частичным) единичным элементом алгебры изображений. Так, например, если рассматривается как регулярная конфигурация (см. приложение 3.7.А) и 2 «одноатомный», то единичный.

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

Если и если единичные, то также единичный. Действительно,

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

Замечание. Термин «единичный» неоднозначен, возможно, «тождественный» было бы лучше.

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

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

Понятие конгруэнтности, очевидно в случае универсальной алгебры, становится более зыбким, если некоторые из основных операций алгебры являются частичными, — этот случай представляет для нас наибольший интерес. Мы рекомендуем в этой связи читателю обратиться к монографии Гретцера (Gratzer 1968, с. 79—99). Если рассмотреть базисную операцию а, объединяющую конфигурации в некоторую регулярную конфигурацию с и конфигурации в некоторую регулярную конфигурацию с, то мы будем требовать выполнения условия Итак, наше понятие правила идентификации соответствует «конгруэнции», но не «сильной конгруэнции» (см. Примечания А). Для базисных операций нет необходимости проводить это различие, поскольку с регулярна в том и только том случае, если регулярна (преобразования подобия должны, как мы предполагали, образовывать группу).

Точно так же, как мы не можемудовлетвориться одним поня-

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

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

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

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

В самом деле, автоматически является отношением эквивалентности, и если справедливо условие то выполняется и и, следовательно, конфигурации с и имеют одинаковые внешние связи. Кроме того, при и, следовательно, И наконец, если выполняются условия и конфигурации регулярны, то выполняются и условия следовательно, и условия определения 3.1.1 из первого тома выполнены.

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

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

В таком случае, последовательно применяя соотношение (3.7.2), получаем следующее:

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

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

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

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

Пример 3.7.1. Рассмотрим конфигурации типа «соответствие», так что Пусть для простоты пространство

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

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

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

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

Сейчас мы будем пользоваться только одним определением и обратимся к другим позже. Наше определение представляет собой модификацию определения, использовавшегося в разд. 2.11 первого тома, а в более общем виде — в работе Гренандера (Grenander 1977d); там было указано, что даже приведенное определение чересчур ограничительно, и его следует обобщить таким образом, чтобы оно покрывало случаи, когда две алгебры изображений, связанные отображением, имеют различную глобальную регулярность: допускается различие их типов соединения. Сейчас мы попытаемся дать общеприменимое определение гомоморфизмов двух алгебр изображений.

Допустим, что сформировано некоторое пространство конфигураций

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

соединения , так что общая регулярность определяется как

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

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

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

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

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

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

Композиционная таблица имеет вид, подобный табл. 3.7.2. При работе не с одним, а несколькими соединителями нам требуется, естественно, несколько композиционных таблиц.

Таблица 3.7.1 (см. скан)

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

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

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

Условная ассоциативность, т. е.

(когда определена только одна часть равенства), требует более тщательного изучения.

Таблица 3.7.2 (см. скан)

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

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

Рис. 3.7.1

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

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

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

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

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

Мы допускаем переменную арность, но с учетом сказанного выше, так что со

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

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

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

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

Рассмотрим теперь три изображения обладающие такими свойствами, что

Перенумеруем -активные связи изображений, представив их векторами-столбцами:

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

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

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

и при соединении с изображением замыкаются связи .

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

и, следовательно, на чем доказательство заканчивается,

Теорема полностью доказана.

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

Пример 3.7.2. Рассмотрим регулярность типа в качестве примера выше); и очевидно, что, как и выше, две -активные (-конкатенация справа) связи индивидуально распознаваемы. Следовательно, как нам уже известно, соединение а должно быть условно ассоциативно.

Пример 3.7.3. Рассмотрим регулярность типа «дерево»), и пусть соединитель а предусматривает соединение верхней (единственной) связи изображения с крайней левой из нижних связей изображения Снова и минутное размышление показывает, что -активные связи распознаваемы. Следовательно, этот соединитель также условно ассоциативен.

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

Рис. 3.7.2

Пример 3.7.5. Пусть -активные связи ; соединение с осуществляется путем введения соединений 1—3 и 4—2, так что имеет -активные связи Г, 2, 3, 4. Комбинированное изображение для исходных изображений представлено на рис. 3.7.2. Некоторые из неактивных связей изображены пунктиром, -актив-ные связи распознаваемы, и, следовательно, соединитель о условно ассоциативен.

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

Пусть все показатели связей одинаковы и отношение связи для двух показателей связей и имеет вид

При выборе «полный» мы приходим к случаю, рассмотренному в гл. 3 первого тома.

На рис. 3.7.3 представлен типичный случай. Для этой регулярности типа «полный») условия теоремы 3.7.2 не выполняются, поскольку число -активных связей не фиксировано. В данном случае мы имеем дело не просто с единственным соединителем, но с целым семейством где — это со так что данный пример и в этом отношении отличается от остальных примеров. Тем не менее такой соединитель является условно ассоциативным.

Рис. 3.7.3

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

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

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

Замечание. В соответствии со стандартным употреблением термина миморфизм мы будем использовать его для обозначения гомоморфизма на.

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

Теорема 3.7.3. Если гомоморфизм конфигурации удовлетворяет условию для всех то индуцированное отображение Н является гомоморфизмом изображений.

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

Для того чтобы доказать, что И является гомоморфизмом, необходимо продемонстрировать выполнение двух условий, включенных в определение 3.7.1. Для проверки условия (I) допустим, что т. е.

(здесь использована -ковариантность правила идентификации

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

(здесь использовано комбинаторное свойство отношения эквивалентности). В таком случае имеем следующее:

что и требовалось доказать. Теорема полностью доказана.

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

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

снова следует, что и, следовательно, условие (II) выполняется.

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

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

Определение 3.7.2. Левое (правое) множество определения для некоторого заданного изображения I задается следующим образом:

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

Определение 3.7.3. Множество называется левым идеалом, заданным посредством а, если для любых изображений таких, что определено, имеет место .

Теорема 3.7.4. Левое множество определения ковариантно: Если соединитель обладает активными индивидуально распознаваемыми связями, то является левым (правым) идеалом.

Доказательство. Из условия определения (3.7.20) и с учетом свойства условной дистрибутивности (3.7.6) следует, что

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

замкнута относительно преобразований подобия:

и, следовательно, множество ковариантно.

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

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

и, следовательно, действительно левдей идеал. Что и требовалось доказать.

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

Теорема 7.3.5. Если — некоторый гомоморфизм, а А — левый (правый) идеал в то левый (правый) идеал.

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

Поскольку, однако, то или и в таком случае и, следовательно, А является левым идеалом (см. определение 3.7.3). Следовательно, мы показали, что прообраз идеала А является левым идеалом так же, как сам А. Естественно, не должен быть однозначным. Что и требовалось доказать.

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

Мы считаем, что соотношение (3.7.25) не всегда можно усилить до равенства.

Роль условных правых (левых) нулей аналогична роли условных единиц: является условным правым нулем, если

Множество условных правых нулей -инвариантно относительно преобразований подобия, поскольку если то

Множество , кроме того, является условным правым идеалом, так как если то