Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
Глава 3. Алгебра регулярных структур3.1. Координаты образующихВ первом томе были введены объекты теории образов: образующие, конфигурации и изображения, а также и отношения образов: преобразования подобия, комбинаторные отношения и деформации. Теперь мы займемся углублением нашего понимания этих объектов, обращая особое внимание на их алгебраические свойства. Пространства конфигураций и алгебры изображений обладают комбинаторными свойствами, так же как и другие, более привычные для нас математические структуры, такие, как группы, векторные пространства, алгебры и поля. К таким комбинаторным свойствам относятся алгебраические свойства, характеризующие возможности соединения отдельных объектов друг с другом, связи, устанавливаемые между объектами с помощью преобразований подобия, и особенности восприятия этих объектов идеальным наблюдателем. Алгебраизация теории образов проходит младенческий период развития, однако с момента ее зарождения в середине шестидесятых годов было очевидно, что общеалгебраические понятия могут способствовать упрощению теоретического анализа. Именно поэтому автор и ввел термин «алгебра изображений». В данной главе будет показано, каким образом понятия теории классов образов можно представить с помощью языка универсальной алгебры. Комбинации конфигураций или изображений являются допустимыми только в том случае, если получаемый результат удовлетворяет условиям регулярности. Очевидно, что основные операции определены не для всех значений аргументов, а лишь частично. Это обстоятельство осложняет изучение гомоморфизмов, соотношений конгруэнтности и т. п., поскольку для таких понятий существует более чем одно естественное определение; эта трудность не возникает в связи с полугруппами, группами, векторными пространствами и т. д. Поэтому мы будем иметь дело с частичными универсальными алгебрами. Какому-то читателю часть нижеследующего анализа может показаться слишком абстрактной или просто казуистикой, как, например, обсуждение роли пустой конфигурации и изображения или разметка системы координат для связей и образующих. Эти детали не удается, однако, обойти при строгом рассмотрении синтеза образов, и они необходимы для того, чтобы иметь возможность справиться с колоссальным разнообразием и изменчивостью регулярных структур. Как и во всех алгебраических теориях, в нашем случае роль гомоморфизма очень существенна и мы будем изучать их применительно ко многим регулярным структурам и на уровне конфигурации, и для индуцированных отображений изображений. Это приведет нас к представлению о пространствах конфигураций и алгебрах изображений как категориях и рассмотрению нескольких соответствующих функторов. Хотя это, несомненно, шаг в правильном направлении, совершенно очевидно, что мы лишь слегка прошлись по поверхности, под которой лежит богатый пласт алгебраической структуры, еще ожидающий разработки. Все рассматриваемые нами регулярные структуры построены из неделимых элементов — образующих, соединенных в определенном порядке таким образом, что наблюдатель воспринимает регулярность. Эта регулярность может иметь как глобальный, так и локальный характер; тип соединения определяет регулярность глобального типа, а отношение связей — регулярность локального типа. Задание глобальной регулярности будет весьма подробно обсуждаться в следующем разделе, и мы не будем сейчас предвосхищать это обсуждение. А пока тщательно рассмотрим локальную регулярность, опираясь на показатели связи, и поставим ряд вопросов, ответы на которые следует получить прежде, чем мы перейдем к определению конфигураций на глобальном уровне. Напомним некоторые сведения из гл. 1 и 2 первого тома. Образующая представляет собой непроизводный информационный элемент. Образующая Выделим некоторые особенно важные из этих признаков. Индекс класса образующих Образующая может быть снабжена также и некоторым идентификатором, предназначенным для того, чтобы помечать образующие, входящие в конфигурацию с. Если все образующие конфигурации с различны, то никаких проблем не возникает и можно воспользоваться любой системой меток, например обозначать образующие с помощью нижнего индекса большую осторожность. При этом необходимо установить, располагают ли эти образующие каким-либо идентификатором, и последующий синтез образов зависит от этого решения. В следующем разделе мы вернемся к этой проблеме в связи с системами координат для конфигураций. Сейчас мы займемся признаками, определяющими локальную регулярность, а именно связями. Связи любой образующей определяются как
где В соотношении Множество Мы будем изучать регулярности двух типов, причем соответствующая терминология несколько отличается от использовавшейся в томе «Синтез образов». Определение 3.1.1.
В случае Рассмотрим несколько примеров, иллюстрирующих смысл Определения 3.1.1, начав при этом с простейших. Пример 3.1.1. Образующая сформирована из некоторого дискретного «интервала» содержащего Пример 3.1.2. Пример 3.1.3. Образующая представляет собой некоторый (обычный) интервал Пример 3.1.4. Пример 3.1.5. Образующая представляет собой некоторый прямоугольник со сторонами единичной длины и углами, расположенными в узлах целочисленной решетки Пример 3.1.6. То же самое, что и в предыдущем случае, за исключением того, что
Рис. 3.1.1 Отметим, что элементами множества Пример 3.1.7. То же самое, что в примерах 3.1.5 и 3.1.6, за исключением того, что прямоугольники заменены треугольниками (см. рис. 3.1.1) с индексом класса образующих, принимающим значения «верхний» или «нижний». Образующая представляет собой либо верхний треугольник с углами
Пример 3.1.8. То же самое, что в предыдущем случае, за исключением того, что Пример 3.1.9. Пусть Пример 3.1.10. Пусть
и выходные связи упорядочены указанным способом. Кроме того,
порядок в данном случае также указывается. Здесь Пример 3.1.11. Пусть
Соответствующие показатели связей представляют собой области определения и значений Мы уже отмечали, что образующие, объединенные в регулярную конфигурацию, не всегда снабжены метками, позволяющими различать эти образующие. Точно таким же образом может оказаться, что связи какой-то определенной образующей не будут различаться. Чтобы пояснить, рассмотрим схемы образующих, приведенные на рис. 3.1.2. Рис. 3.1.2(a) иллюстрирует пример 3.1.4: рассматривается функция
Рис. 3.1.2 На рис. 1.3.2(б) образующая является правилом подстановки бесконтекстной грамматики, преобразующим группу существительного На рис. 3.1.2(в) ситуация, однако, меняется. В данном случае образующая представляет арифметический модуль, вычисляющий сумму двух функций действительного переменного, область значений которых, так же как и области определения, представляют собой ось действительных чисел. Две входные связи не поддаются различению: показатели связей одинаковы и перестановка двух аргументов не изменяет результата. Если задана образующая со связями В, то в общем случае мы будем обозначать через группу, а именно группу связей образующей Очевидно, что в случае, представленном на рис. Пусть образующая Маркировка связей однозначна по модулю Если речь идет о локальной регулярности, то возможность присоединения образующей к некоторой конфигурации полностью определяется множеством Определение 3.1.2. Две образующие Совершенно очевидно, что речь здесь идет об отношении эквивалентности и, следовательно, оно разбивает множество образующих Напомним в этой связи, что все преобразования подобия сохраняют структуру связей и индекс класса образующих и осуществляют биективное отображение подобия. Всякая регулярная конфигурация сохраняет регулярность при «пульсациях», возникающих в результате воздействия конгруэнтных преобразований подобия Продолжим наше обсуждение и рассмотрим следующие два примера. Пример 3.1.12. Каждая образующая снабжена четырьмя связями, помеченными координатами, например Поскольку все четыре показателя связей различны,
Эти образующие можно использовать для формирования конфигураций, топологически эквивалентных подмножествам квадратной решетки на плоскости; для этого необходимо воспользоваться дополнительным условием глобальной регулярности, которое будет введено позже. Особенность данного примера по сравнению с примером 3.1.5 заключается в том, что в последнем показатели связей более информативны: они содержат информацию о местоположении. Таким образом, соответствующие образующие можно интерпретировать как единичные квадраты с заданным местоположением, в примере же 3.1.12 образующие — это просто единичные квадраты. Подобные внешне безобидные различия будут встречаться нам во многих случаях. Пример 3.1.13. Образующие представляют собой замкнутые полуплоскости в пространстве Мы приводим здесь пример 3.1.13, поскольку он показывает, каким образом использовать локальную регулярность (например,
В качестве подготовки к подробному обсуждению глобальной регулярности рассмотрим некоторую заданную образующую
представляет глобальную связность образующей Глобальная связность абстрагирована от всех признаков, за исключением структуры связей и индекса класса образующих. Поскольку вся остальная информация исключена, мы представим схематически остов Для схем, изображенных на этом рисунке, выбор координат связей осуществляется по-разному. На схемах
Рис. 3.1.3 Точно так же как связи образующей не всегда однозначно определяются структурой и показателями связей, связи остова могут оказаться неразличимыми подобно тому, как это имеет место на рис. 3.1.3(в) для входных связей. Представлена группа перестановок, фактически не изменяющая связи, за исключением изменения маркировки при помощи Если заданы два семейства образующих
а соответствующие показатели связей—объединением
что обеспечивает естественную связь между новыми координатами связей и новыми показателями связей. Кроме того,
|
1 |
Оглавление
|