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

9.4. Две специальные алгебры изображений

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

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

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

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

Выходные арности этих образующих изменяются в пределах от 0 до 5, объекты с соои, состоят из двух образующих и

Уровни абстракции изменяются от для двух объектов до для а и Два разбиения и показаны в табл. 9.4.3 и 9.4.4.

Показатели связей принадлежат множествам как указывалось в подразделе 3.4.6 — см. табл. 9.4.2. Нам не требуется указывать показатели входных связей образующих максимального уровня, поскольку с ними не может соединяться никакая выходная связь. Вот почему в табл. 9.4.1 ячейки для в первых двух строках пустые.

Рис. 9.4.1. (см. скан) Диаграммы конфигураций на

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

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

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

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

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

Теперь опять посмотрим на рисунок и займемся четырьмя замкнутыми связями. Рассмотрим, например, соединение между и верхней образующей Согласно табл. 9.4.1, первая выходная связь имеет показатель V, показатель входной связи также равен V, таким образом, соблюдается «равенство», т. е. отношение для этого конкретного соединения двух связей. Аналогично проверяем соединения оставшихся связей и убеждаемся, что удовлетворяется. Таким образом, — регулярная конфигурация. Она не является простейшей -конфигурацией, поскольку образующая может быть удалена без нарушения регулярности. Однако если все же удалить, то оставшаяся подконфигурация будет простейшей.

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

4.3.1. Теперь рассмотрим более интересный примере 34 образующими, перечисленными в табл. 9.4.5 вместе с их уровнями, выходными арностями и показателями связей.

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

Сначала несколько замечаний. Показатели входных связей никогда не встречаются среди показателей выходных связей. Это означает, что образующие 8—18 и 23—26 никогда не принимают выходных связей от других образующих.

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

(кликните для просмотра скана)

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

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

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

Образующая захватить, с выходной арностью 3, должна и интерпретироваться как «захватить нечто, между пальцем, и пальцем,». Образующая прижать, выходной арности 4, должна интерпретироваться как «прижать нечто, к нечто при помощи пальца, и пальца». Здесь индексы — это координаты связей. Остальные образующие не нуждаются в пояснениях.

4.3.2. Множества 33 даны в табл. 9.4.6, а разбиения, соответствующие уровню и выходной арности, — в табл, соответственно.

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

Классы образующих легко вычисляются — см. обсуждения в разд. 3.5. В табл. 9.4.9 представлены 15 классов.

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

классы образующих с табл. 9.4.8 и отношением приведенным ниже в табл. 9.4.11.

Преобразований подобия теперь намного больше, чем в первом примере. Группа преобразований подобия есть прямое произведение полных симметричных групп порядка 2, 4, 1, 1, 4, ... — см. табл. 9.4.9. Следовательно,

4.3.3. Объединив образующие большой палец, указательный палец, захватить, болт, медь, мы получаем регулярную конфигурацию, представленную на рис. Еще одна конфигурация показана на рис. Более сложная конфигурация изображена на рис. где Подконфигурация с, заключенная внутри пунктирного контура, регулярна и ее можно рассматривать как макрообразующую (см. т. I, с 33). Уровень всей конфигурации равен трем.

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

Конфигурация представленная на рис. 9.4.2(д), подобна конфигурации на рис. 9.4.2(a), т. е. .

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

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

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

Рис. 9.4.2. (см. скан) Диаграммы конфигураций на


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

Если мы захотим удалить подобные изображения из алгебры, это можно будет сделать, пометив входные связи

маркерами. Однако на данной стадии это не представляется необходимым.

Наконец, последние три конфигурации (е), (ж) и (з) подобны друг другу и принадлежат той же разновидности, тому же образу,


Рис. 9.4.2 (продолжение) (см. скан)

Рис. 9.4.2 (окончание) (см. скан)


что и (а). В этом нетрудно убедиться, глядя на табл. 9.4.10, где представлена группа преобразований подобия S.

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

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

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

Вспомнив замечание 2 из подраздела 3.7.9, мы можем убедиться в том, что порождает гомоморфизм Для этого нужно проверить, что сохраняет структуру связей, для чего воспользуемся табл. 9.4.9 совместно с табл. 9.4.5 и 9.4.1, а также, что показатели связей ведут себя так, как требуется в упомянутом замечании 2.

Применяя этот гомоморфизм, например, к на рис. 9.4.2, мы получаем -конфигурацию на рис. 9.4.1. Аналогичным образом -конфигурации на рис. 9.4.2 соответствует конфигурация на рис. 9.4.1.

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

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