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

Глава 3. Анализ некоторых временных образов

3.1. Изображение на временной оси

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

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

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

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

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

Физическая интерпретация «времени» может варьироваться. Очевидно, во-первых, что удобнее, если время принимает дискретные значения, скажем целые числа, а не континуум значений на действительной оси. Иногда к тому же мы будем придавать «времени» смысл, отличающийся, строго говоря, от «физического» времени. Так, в частности, в разд. 3.4 «время» будет представлять собой число выполненных команд в процессе выполнения программы ЭВМ. Если машина работает с постоянной интенсивностью выполнения команд без прерываний, то «время» пропорционально но это справедливо только в указанных условиях, разд. 3.2 временной параметр представляет собой просто счетчик, показание которого изменяется на единицу при выполнении арифметической операции, так что связь с физическим временем становится еще более условной.

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

Сформулирована. В таком случае входная связь образующей в интервале задается как и выходная связь — как .

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

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

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

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

В конечном счете регулярные конфигурации будут идентифицироваться как функции (см. разд. 3.1, т. 1). Полученные в результате изображения относятся к классу режимов. Изображение соответствует некоторому интервалу временной оси. Конфигурация соответствует разбиению а образующие представляют функции, заданные на связанные отношением согласования Естественно, не должны однозначно определяться и потому задача сегментации (см. т. 1, разд. 3.1) может иметь несколько решений.

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

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

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

Схема конфигурации тогда может иметь, например, такой

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

Рис. 3.1.1.

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

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

компонентами

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

В случае непрерывного времени аналогично получаем идеальное изображение на некотором интервале , причем и

Идеальное изображение режима необязательно однозначно определяет соответствующие режимы — его образующие не обладают единственностью. Если образующие соединены стрелкой, направленной от первой ко второй, и если им соответствует одно и то же Т, то и сливаются в новую образующую соответствующий режим распространяется на объединение интервалов, которые служат опорными множествами для (см. т. 1, разд. 3.1). Этот факт можно использовать для приведения конфигурации, см. теорему 3.1.2, т. 1.

Рассмотрим изображение определенное на дискретном интервале , который состоит из целых чисел рассмотрим это изображение с точки зрения анализа изображений (см. разд. 1.1). Каждому переходу поставлен в соответствие некоторый оператор Т из множества которое для простоты предполагается конечным. Число переходов равно а, так что изображение можно представить с помощью регулярной конфигурации, содержащей образующих. Если бы можно было слить пары образующих, то численная сложность была бы снижена, и, следовательно, существует наименьшее число соответствующее :

Для того чтобы выяснить, как вычисляется рассмотрим

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

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

Пусть селекторная функция, Число режимов для соответствующей конфигурации тогда равно

Воспользуемся теперь методом динамического программирования для определения Применим следующий алгоритм приведения. Пусть

где минимум берется по всем селекторным функциям с элементами из Имеет место рекурсия

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

Может, конечно, оказаться, что всегда однозначно определяет Т посредством некоторого значения а из и тогда алгоритм приведения не требуется. Можно говорить и в более общем случае, когда знание где

определяет Т. Отметим, что во всех выписанных выше уравнениях используется один и тот же оператор Т. Насколько же большим следует выбирать для того, чтобы сформулированное утверждение выполнялось?

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

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

Доказательство. Введем для произвольного характеристический многочлен

Тогда

Первое утверждение в (3.1.10) является классическим (см., например, монографию Мак-Даффи (1946), с. 18). Второе утверждение (3.1.10) справедливо, поскольку собственные значения

Записав характеристические многочлены в виде

устанавливаем, что линейная комбинация

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

В качестве примера укажем, что если операторы Т имеют описанный выше вид, когда представляет значения функции в моменты времени то матрица для

всякого Т является сопутствующей:

и ее характеристическое уравнение — просто:

Остается, следовательно, вычислить значение линейной комбинации

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

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

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

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

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

Пример 1. Рассмотрим цепь из сопротивлений и емкостей, схема конфигурации которой приведена на рис. 3.1.2, а. Две

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

следовательно, и

Рис. 3.1.2.

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

Пример 2 (рост при ограниченных ресурсах). Пусть размер популяции, а темп относительного прироста равен при Уравнение системы в таком случае имеет вид

и, следовательно,

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

Тип II. Тенденция к повторению. Значения не сходятся, но обнаруживают точно или приближенно периодическое поведение. «Приближенную периодичность» можно интерпретировать многими способами, некоторые из которых будут затронуты ниже.

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

где интерпретируются соответственно как функция от времени и ее производная. Следовательно, функция времени удовлетворяет уравнению так что

где амплитуда А и фазовый угол произвольные, но частота и период фиксированы.

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

Рис. 3.1.3.

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

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

Применение стандартного спектрального анализа к этому уравнению приводит к следующему:

где спектральный процесс, соответствующий шумовой составляющей. Следовательно, спектральная плотность равна

Если, таким образом, мало, то пики этой плотности приходятся на Итак, функция будет вести себя как (почти) гармонический осциллятор на коротких временных интервалах. На более длинных интервалах, однако, отсутствие строгой периодичности становится очевидным.

Представляет интерес случай, когда временной образ порождается стационарным процессом восстановления на временной оси, скажем, с распределением временных промежутков между событиями (см., например, монографию Феллера (1957), т. 2, гл. 11). Форма импульса определяется функцией а изображение — суперпозицией импульсов, расположенных в точках (моментах) событий процесса восстановления, так что

Для сходимости (3.1.25) мы потребуем, чтобы распределение имело конечное среднее значение и чтобы принадлежала или на действительной оси. Результат (3.1.25) называется образом восстановления. Если, в частности, распределение

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

Пример 7 (образы Лиссажу). Движение двух гармонических осцилляторов, например

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

Рис. 3.1.4.

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

Используя формулы сложения тригонометрических функций, все еще можно записывать х и у как линейные функции от некоторых степеней где представляются как кратные частоты. Это означает, что образ — все еще алгебраическая кривая, но может представать во многих формах. Эти образы известны как фигуры Лиссажу; несколько примеров таких фигур приведено на рис. 3.1.4 (они заимствованы из справочника Тернера (1965) с. 161)). Заметим, что число вертикальных и горизонтальных контуров указывает, каково отношение частот, и, следовательно, дает возможность просто и быстро определять это отношение. Таким же образом в предыдущем случае фазовый угол можно определить, подстраивая второй фазовый угол до тех пор, пока образ не выродится в линию.

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

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

Тип III. Эргодическое поведение. Функция не устанавливается на каком-либо конкретном значении или цикле, хотя ее распределение сходится к некоторому пределу. Такие временные образы очень подробно изучены в эргодической теории (см., например, работу Хопфа (1948), в которой можно найти соответствующие детали). Конечно, здесь мы сможем привести лишь несколько примеров из этой богатой математической теории.

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

сходится почти для всех начальных значений Если предел - почти наверное постоянная, так что он совпадает со средним

значением если нормирована к 1 и это справедливо для всех то говорят, что оператор Т эргодический.

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

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

Пример 8 (генераторы случайных чисел). Пусть одномерный тор, полученный путем отождествления точек 0 и 1, периодический, с лебеговой мерой Определяем Т как

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

Асимптотическое распределение последовательности равно равномерному распределению на почти для всех начальных значений

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

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

Рис. 3.1.5 б (см. скан)


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

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

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

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

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

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

Пример 9 (движение с упругими соударениями). Материальная точка совершает равномерное движение внутри некоторой окружности, это движение нарушается лишь упругими соударениями со стенками.

Если первый угол соударения со стенкой представить величиной измеренной от нормали в точке удара (см. рис. 3.1.5а), то очевидно, что длина дуги между очередными ударами равна просто радиусу, умноженному на я — Если эта величина оказывается несоизмеримой с периметром окружности т. е. рациональное число, то можно ожидать, что точки соударения распределены равномерно. Это следует из классической теоремы Вейля о том, что последовательность а, 2а, 3а, ..., где а — иррациональное число, приведенная к [0, 1) по модулю единица, распределена равномерно.

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

Отметим, что построение последовательности а, 2а, 3а, ... Соответствует случаю аддитивного конгруэнтного генератора псевдослучайных чисел.

Тип. IV. Расходимость. Рассмотрим теперь функции, которые резко возрастают с увеличением времени. Простого примера будет достаточно для иллюстрации этого поведения.

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

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