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

3.3. Соединители

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

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

и

Это отображение сохраняет старые соединения в конфигурациях и вводит новые:

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

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

Хотя основной сферой действия соединителей служат пространства конфигураций (а далее — алгебры изображений), естественно ввести их также как операции на остовах конфигураций.

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

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

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

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

Рассмотрим несколько примеров.

Пример 3.3.1. Выберем таким же, как в примере «линейный», «равенство» и определим как

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

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

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

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

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

Еще один соединитель работает с , при в этом случае а обеспечивает соединение разомкнутых связей без нарушения X или

Для всякой регулярной конфигурации с, кроме того, существует тривиальное соотношение

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

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

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

состав .

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

рассматривать как базисное множество некоторой частичной универсальной алгебры (см. кннгу Гретцера (Gratzer 1968, гл. 2). Если рассмотреть также правило идентификации обсуждаемое более подробно в разд. 3.8, то мы получим некоторую алгебраическую систему в смысле Мальцева (1970), где выполняет роль некоторого отношения конгруэнтности, так как все основные операции устойчивы относительно Действительно, для любого имеем

Аналогично для любого соединителя , если все принадлежат то

(см. т. 1, разд. 3.1). При таком подходе алгебру изображений можно рассматривать как факторалгебру по модулю (см. монографию Гретцера (Gratzer (1968), с. 35).

Можно пойти дальше и сформировать многочлены над скажем

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

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