9.3.2. ЛИНЕЙНЫЕ СВОЙСТВА

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

Предположим тогда, что имеет место ситуация, показанная на рис. 9.12. Мы начнем с бинарного дискретного изображения, на котором элементы, равные «1», представляют точки объекта. Мы полагаем, что у нас есть семейство функций-предикатов , которые воспринимают значения некоторых элементов изображения в качестве входных величин и дают на выходе либо нуль (ложь), либо

единицу (истина). Функции можно считать признаками объекта — объект либо обладает признаком, либо нет. Признаки поступают на вход линейной схемы, которая формирует линейные комбинации и сравнивает их с порогом t. В конечном итоге мы говорим, что объект обладает свойством Р, если линейная комбинация превосходит порог t, и не обладает свойством Р в противном случае. Вопрос заключается в следующем: какой класс свойств объекта может вычислять такое устройство?

Рис. 9.12. Схема для вычисления линейных свойств.

Сразу же ясно, что на этот вопрос не может быть дано представляющего интерес ответа до тех пор, пока мы не наложили ограничения на функции-предикаты Если мы примем, что единственный предикат может вычислять любое желаемое свойство объекта (т. е. указывать, обладает объект этим свойством или нет), то используем этот единственный предикат и отбросим остальную часть схемы. В соответствии с этим мы наложим ограничения на способ, посредством которого функция-предикат получает информацию о точках изображения на сетчатке. Двумя видами ограничений, представляющих интерес, являются ограничение по диаметру и ограничение по порядку. Мы будем говорить, что предикат ограничен по диаметру величиной d, если множество элементов изображения, от которых он зависит, целиком лежит внутри круга диаметра d. Аналогично предикат ограничен по порядку величиной , если он зависит не более чем от элементов изображения 1). Подобно этому, ограниченная по диаметру (или порядку) линейная схема — это такая схема, в которой все предикаты ограничены по диаметру (или порядку). Заметим, что мы не ограничиваем ни число предикатов, ни их логические формы — ограничиваем лишь выбор входных элементов для одного произвольного предиката. Будем называть линейным свойством объекта свойство, которое можно вычислить с помощью линейной схемы (с объявленными заранее ограничениями относительно предикатов).

Пользуясь этими определениями, мы можем изложить несколько замечательных результатов, относящихся к линейным свойствам объектов. В некоторых случаях мы будем доказывать результат, в других будем просто формулировать его. Читателя, заинтересовавшегося дальнейшим изложением этих вопросов, мы отсылаем к превосходной книге основоположников этой теории Минского и Пейперта (1969). Начнем с некоторого свойства ограниченных по диаметру линейных схем, которое легко доказывается.

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

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

Рис. 9.13. Примеры к результату относительно связности.

Нужные нам объекты изображены на рис. 9.13, а - 9.13, г, где для наглядности сетка квантования не показана. Примем, что во всех случаях ограничение по диаметру d меньше, чем ширина объекта, и поэтому ни один из предикатов не может «видеть» оба конца. Для удобства мы сгруппировали предикаты, как показано на рис. 9.13, а. Предикаты группы 1 связаны с левым концом объекта, группы 2 — с правым, а предикаты группы 3 связаны с остальной частью сетчатки. Без какой-либо потери общности предположим, что линейная сумма Т превосходит порог t для связных объектов. Поскольку

объект рис. 9.13, а несвязный, мы получим сумму, например Та, меньшую порога t. Поскольку объект рис. 9.13, б связный, найдем, что и, кроме того, что этот прирост должен полностью определяться вкладом предикатов группы 2. Точно так же для объекта рис. 9.13, в мы получим, что и что прирост должен определяться только предикатами группы 1. Наконец, для объекта рис. 9.13, г должен возрасти вклад в сумму от обеих групп предикатов, поскольку каждая группа «видит» те же изменения, что она видела и раньше. Таким образом, сумма, Те для последнего изображения будет даже больше, чем каждая из сумм поэтому порог будет превышен и линейная схема ошибочно определит, что объект рис. 9.13, г связный.

Подобного рода утверждение для ограниченных по порядку линейных схем выступает как

Результат 2: Порядок линейной схемы, способной вычислять связность, неограниченно растет по мере того, как число элементов сетчатки стремится к бесконечности.

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

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

Результат 3: Свойство «число Эйлера для объекта больше чем k» может быть вычислено посредством линейной схемы порядка 4 и диаметра 2.

Корнем этого утверждения является тот факт, что число Эйлера для объекта может быть вычислено посредством линейной суммы, каждый член которой зависит только от нескольких элементов. А именно пусть U — число элементов объекта, Р — число пар элементов, смежных по горизонтали или вертикали, и Q — число «квадратов» объекта размером элемента. Нетрудно показать, что тогда число Эйлера определяется формулой

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

объекта на один элемент. В качестве примера такого анализа предположим, что мы увеличиваем объект, добавляя один элемент таким образом, чтобы он касался только одного из имевшихся ранее элементов объекта. (Напомним, что подразумевается «касание» по правилу 4-связки.) Такого рода добавление элемента не может изменить ни числа связных компонент, ни числа дыр, поэтому число Эйлера для данного объекта не изменяется. Как следствие, число элементов U увеличивается на единицу, число пар Р увеличивается на единицу, а число квадратов Q не изменяется, поэтому величина также остается неизменной и переход по индукции для этого случая подтверждается. Одна из причин интереса к результату 3 заключается в том, что он показывает, как можно определить число Эйлера другим способом, связав его с такими свойствами объекта, которые вычислимы посредством линейных схем.

Результат 4: Все возможные топологические свойства конечного порядка являются функциями числа Эйлера.

Под «конечным порядком» мы подразумеваем, что порядок не возрастает неограниченно при неограниченном возрастании числа элементов сетчатки. Интересно отметить, что, хотя линейная схема конечного порядка может вычислить для объекта число Эйлера, она не может определить, является ли он связным.

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

Результат 5: Выпуклость может быть вычислена линейной схемой порядка 3.

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