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

2.2. Принцип комбинаторности

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

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

(в зависимости от того, что имеет место в конкретном случае).

Как отмечалось в разд. 1.3. нашей целью является создание единой теории, части которой естественным образом сочетаются

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

Отметим, что мы допускаем лишь «двойные» соединения связей: связи могут соединяться только попарно. Мы никогда не соединяем вместе три или большее количество связей. Это допущение представляет собой очень сильное ограничение, и на раннем этапе развития теории образов считалось, что возникнет необходимость в использовании троек связей или даже большего их числа. До сих пор, однако, среди множества изученных случаев, нам не встретился хотя бы один, где бы это имело место, так что допустимыми будут считаться только двойные связи.

В качестве примеров воспользуемся снова случаями, включенными в (2.1.1). В примере (I) входной связью является центр окружности, а выходной — сама окружность. Один из способов организации эпицикла заключается в том, что центр движется по окружности; соответствующим отношением связей является отношение «быть элементом...».

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

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

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

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

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

Рис. 2.2.1 (см. скан)

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

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

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

И наконец, в случае (V) атомы соединяются между собой, если они являются соседями по некоторой квадратной решетке. Читателю, интересующемуся тем, каким образом это можно сделать, следует обратиться к с. 134 первого тома. Мы снова встречаемся с отношением связей «равный...».

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

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

Образующие, представленные на рис. 2.2.1(б), имеют арность, равную 3. Топология в данном случае определяется тем, что по ширине соединены две образующие, а по длине — произвольное число образующих.

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

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

Топология квадратной решетки представлена на рис. 2.2.1(д), где . Конфигурация в целом располагает тремя

несоединенными входными связями и тремя несоединенными выходными связями.

Два остальных примера представляют крайние случаи, но они довольно интересны. На рис. 2.2.1(e) топология является пустой: соединения связей отсутствуют совершенно, так что на образующие, составляющие конфигурацию, никаких ограничений не налагается. В конфигурации, представленной на рис. 2.2.1(ж), все образующие имеют бесконечную арность, мы же, естественно, можем показать лишь некоторые связи. Количество несоединенных входных связей равно 4 и столько же имеется несоединенных выходных связей. Эта конфигурация представляет крайний случай, противоположный конфигурации на рис. 2.2.1(e): все образующие соединены друг с другом. И входная, и выходная арности конфигурации в целом бесконечны.

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

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

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

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