3.3. Теория сегментации для временных образов

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

Определение 3.3.1. Фиксированному линейному дифференциальному оператору порядка с постоянными коэффициентами и целым числам и поставлен в соответствие класс функций на [0, 1], такой, что для каждой функции существует ряд различных точек удовлетворяет следующим условиям:

(i) функция является решением в пространстве уравнения на каждом открытом подынтервале

(ii) функция принадлежит в окрестности всех

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

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

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

Рис. 3.3.1.

хорошо можно аппроксимировать функциями класса Ф заданную функцию времени

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

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

Определение 3.3.2. Фиксированному линейному дифференциальному оператору порядка с постоянными коэффициентами и целым числам и поставлен в соответствие класс функций на [0, 1], такой, что для каждой функции существует ряд различных точек и соответствующие кратные целые где удовлетворяет следующим условиям:

(i) функция является решением в пространстве уравнения на каждом открытом подынтервале

(ii) функция принадлежит в окрестности всех

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

Функция не должна быть, однако, однозначной. Доказательство этого факта см. в работе Маклура (1975), с. 13.

Задача отыскания минимума является нелинейной из-за влияния узлов и на первый взгляд решить ее практически невозможно, особенно при больших Воспользовавшись, однако, идеей, которая была высказана Далениусом и Ходжесом при изучении оптимальной стратификации (1957, 1959), можно получить удобные асимптотические результаты.

Рассмотрим для заданной функции на [0, 1] и разбиения функционал вида

Отдельные члены (3.3.2) будут соответствовать ошибке аппроксимации на интервале однако сейчас мы не будем останавливаться на этом. Вместо этого введем более общие допущения.

(А1) Для любых удовлетворяющих условию а, Кроме того, субаддитивна на смежных

подынтервалах [0, 1]; это означает, что если то

(А2) Существуют некоторая соответствующая функция , заданная на [0, 1], и постоянная , такие, что

(i) функция неотрицательна и кусочно-непрерывна на [0,1] и имеет в худшем случае конечное число точек разрыва с конечным скачком;

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

Допущение предполагает, что неотрицательна. Допущение о субаддитивности эквивалентно предположению о том, что более мелкие разбиения [0,1] уменьшают .

Применяя эти общие результаты, чем мы займемся ниже, обычно нетрудно проверить выполнение допущений (А1) и (A3).

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

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

Лемма 3.3.1. Если для выполняются допущения то

Доказательство. Зафиксируем и пусть представляет ее изображение в (множество неотрицательных кусочно-непрерывных функций на [0,1]).

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

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

Докажем в первую очередь, что имеет порядок ограничив его сверху определенным значением этого порядка. Пусть фиксированные точки разрыва Пусть также обозначает равномерное разбиение [0,1] с внутренними точками при Разбиение содержит не более внутренних точек [0,1]. Следовательно, благодаря оптимальности

Непосредственное вычисление, основанное на допущении доказывает, что

и, таким образом,

Учитывая такой характер сходимости, можно считать, что некоторые подынтервалы разбиения становятся произвольно малыми по мере роста Введем обозначения

и

Пусть длина интервала содержащего Если то Другими словами, существует некоторая положительная величина такая, что для некоторого непрерывна и положительна на и для последовательности разбиений имеет место

Но из следует, что

Это в свою очередь означает, что

Правая часть этого неравенства расходится при увеличении , что противоречит (3.3.10).

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

По определению множества асимптотическое выражение допущения можно использовать на подынтервалах Г, содержащих На определим теперь -аппроксимацию ступенчатой функцией в виде

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

Кроме того, из допущения о равномерной сходимости в следует, что функции равномерно ограничены на [0, 1].

Выделим теперь те члены суммы для которых выполняется Пусть символ суммирования 2 обозначает сумму, взятую по тем значениям для которых справедливо . Согласно

Применив допущение можно получить следующее:

здесь Используя неравенство Гельдера, получаем

Таким образом,

По теореоме о сходимости и учитывая (3.3.17), получаем, что

Доказательство леммы закончено.

Мы действительно можем считать, что

Один из способов прийти к этому заключению основан на построении -точечного разбиения при котором сходится к некоторому пределу, сколь угодно близкому к нижней грани. Подобные разбиения можно описать плотностями распределений на [0, 1].

Пусть строго положительная ограниченная кусочно-непрерывная функция на [0, 1], нормированная так, что Обозначим через интеграл Определим для произвольного

целого числа некоторое -точечное разбиение отрезка [0, 1] как

Точки разбиения однозначно определены обращением функции распределения

Лемма 3.3.2. Предположим, что допущения выполняются для Пусть -точки разрыва в интервале . Пусть -положительная ограниченная кусочно-непрерывная плотность распределения на отрезке [0, 1], соответствующая распределению Для разбиений определенных согласно (3.3.25), имеет место

Доказательство. Допустим, во-первых, что непрерывна. Точки разбиения удовлетворяют условию . Чтобы получить их границы, введем

Таким образом, обозначив

устанавливаем, что интервалы строго положительны и стремятся к нулю при

Применив допущение получаем

Используя аналогично нижнюю грань имеем

что доказывает утверждение (3.3.26). Когда имеет конечное число разрывов на отрезке [0, 1], разбиение приводит к утверждению (3.3.26).

Учитывая это обстоятельство и применив к (3.3.26) простую вариацию, приходим к следующей теореме.

Теорема 3.3.1. Если допущения выполняются для то

Более того, если строго положительна на отрезке [0, 1], вычисление значения функции

дает асимптотически эффективные разбиения. Разбиения асимптотически эффективны,

Доказательство. Требуемый результат можно получить при помощи подстановки вместо в выражение (3.3.26).

Необходимо вычислить локальные ошибки воспользуемся теоремой Пойа о среднем значении (см. Пойа (1922)) и свойством

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

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

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

где Условие выполняется, и если заключено между

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

Исходя из этого, можно сформулировать следующий результат.

Теорема 3.3.2. Если оператор имеет на отрезке свойство и если принадлежит то ошибка наилучшей -аппроксимации на отрезке решением уравнения равна

для некоторой точки отрезка от не зависит и задается как где

Н — матрица Гильберта размера с элементами вектор-столбец с компонентами .

Можно также записать в виде

Доказательство теоремы 3.3.2 связано с установлением нескольких «вспомогательных» следствий из свойства которые имеют и самостоятельный интерес.

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

Доказательство. См. монографию Мейнардуса (1967), теорема 70, с. 88.

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

Лемма 3.3.4. Если оператор имеет на отрезке свойство и если наилучшая -аппроксимация непрерывной функции на отрезке с помощью решения уравнения при то существуют различных точек удовлетворяющих условию в которых при

Доказательство. Филипс (1970) доказал этот результат для случая аппроксимации алгебраическими многочленами. Подробное доказательство леммы 3.3.4 приведено в работе Маклура (1975); ход рассуждений аналогичен доказательству Филипса.

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

Лемма 3.3.5. Допустим, что оператор имеет свойство на отрезке принадлежит удовлетворяет уравнению на отрезке различных точках интервала Тогда для всех принадлежащих отрезку где единственное решение уравнения на отрезке удовлетворяющее условию при некоторая промежуточная точка, такая, что

Доказательство. Это известная теорема Пойа о среднем значении (см. работу Пойа (1922)).

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

Зафиксируем таким образом, чтобы оператор имел на отрезке [0, Н] свойство пусть функция принадлежит и пусть — наилучшая аппроксимация на отрезке с помощью решения уравнения Согласно лемме 3.3.4, существуют различных точек интервала в которых

Построим на отрезке следующие функции, связанные с

(i) — единственное решение уравнения обращающееся в нуль в точках

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

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

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

и

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

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

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

(см. Девис (1963)). В данном случае -норма равна

Вели возвести это выражение в квадрат, то из уравнения получаются (3.3.35) и (3.3.33). Доказательство цоремы закончено.

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

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

Теорема 3.3.3. Для любой функции наилучшая -аппроксимация в классе имеет норму ошибки такую, что

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

и использовать решения (3.3.25) в качестве узлов.

Данный результат удобен с вычислительной точки зрения. Чтобы оценить практические возможности метода, Маклур (1975) выполнил численное исследование, и ниже мы приводим некоторые из его результатов.

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

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

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

Моделируя чисто случайные импульсы, воздействующие на систему, определим

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

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

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

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

Действительная часть корня а отрицательна, следовательно, система устойчива и уравнение (3.3.42) имеет стационарное в узком смысле решение

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

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

с вычислительной точки зрения. Наконец, корень а оператора был произвольно выбран равным

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

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

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

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

Исследование модели методом Монте-Карло на отрезке [0,1] предоставляет данные для оценки качества описанного метода. Оператор порождает аппроксимирующие классы функций Каждая смоделированная функция аппроксимируется некоторым представителем класса который дает по одному узлу для аппроксимации в центре каждого импульса, поступающего на вход системы. Мы не предпринимаем дальнейших попыток оптимизировать размещение узлов; вычисленные аппроксимации просто являются наилучшими -аппроксимациями в классе с заданными узлами. Поскольку при каждом прогоне модели уравнение (3.3.42), играющее роль легко решается аналитически, то ошибки аппроксимации вычисляются с помощью простых аналитических выражений. Соответствующие вычислительные процедуры не требуют дискретизации.

Таблица 3.3.2 (см. скан) Эксперименты с моделью

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

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

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

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

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

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