8.3.1. Формальный имитационный метод Блока, Нильсона и Дуды

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

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

Векторное представление креста на этой сетке имеет вид

а представление в виде множества —

Определим маску как подмножество целых чисел от 1 до . Если маска присутствует в объекте то

Рис. 8.2. Представление объекта на сетке: а — сетка; — объект на сетке.

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

Заметим, что для заданного множества масок множества Ф и могут быть неединственными.

Для нахождения наименьшего множества масок Ф желательно найти те маски, которые содержатся в большом числе описаний. Блок и др. определяют процедуру, позволяющую это делать даже для случая, когда первоначально отдельные маски неизвестны. Пусть — множество описаний объектов, содержащих маску . Блок и др. считают, что а будет определяться как пересечение таких описаний:

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

Займемся сначала задачей определения в точности одной маски. Пусть выборка как-то упорядочена: Маска будет определяться в результате последовательного рассмотрения каждого описания из Пусть будет определением маски построенным после рассмотрения описания из так что Алгоритм имеет вид

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

Чтобы ограничить рассмотрение масок масками размера не меньше 3, положим Последовательность шагов для определения первой маски такова:

Рис. 8.3. (см. скан) Фигуры в примере формирования маски.

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

которая в действительности была одним из признаков, использованных при построении объектов рис. 8.3.

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

Определим как множество целых чисел для которых

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

Тогда обсуждаемый алгоритм можно записать в виде

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

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

алгоритм построит соответствующие маски.