6.5. Каскадный алгоритм: связь с уточняющими схемами и схемами последовательного деления

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

(кликните для просмотра скана)

(кликните для просмотра скана)

Рис. 6.5. (см. скан) Функция для и 10, соответствующая фильтрам из таблицы 6.1 или 6.3

Прежде всего, так как имеет компактный носитель и причем мы имеем

Предложение 6.5.1. Если — непрерывная функция на то для всех

Если — равномерно непрерывна, то такая поточечная сходимость является и равномерной. Если — непрерывна по Гёлъдеру с показателем

(кликните для просмотра скана)

то имеем экспоненциальную сходимость по

Доказательство.

Все утверждения следуют из факта, что является «приблизительно» -функцией при стремящимся к Более точно,

(предполагается, что . Если — непрерывна, то выражение можно сделать произвольно малым, выбрав достаточно большим. Если — равномерно непрерывна, то выбор не зависит от х, и сходимость является равномерной. Если непрерывна по Гёльдеру, то (6.5.2) получается немедленно.

Теперь предположим, что сама является непрерывной или даже непрерывной по Гёльдеру с показателем а. (В следующей главе мы рассмотрим много способов вычисления показателя для Возьмем любое диадическое рациональное Тогда предложение 6.5.1 говорит о том, что

Более того, для больших некоторого

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

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

условий для данных в теореме 6.3.5), является единственной функцией характеризующейся с помощью

Мы можем использовать это в качестве входных данных для алгоритма восстановления субполосной фильтрации, связанного с (см. § 5.6). Более детально: мы начинаем с низкочастотной последовательности и высокочастотной последовательности и «запускаем

машину», чтобы получить

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

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

Предложение 6.5.2. Если непрерывна по Гёльдеру с показателем а, то существуют такие что при

Доказательство.

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

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

Здесь С можно выбрать не зависящей от так что выполняется (6.5.8).

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

1. Начинаем с последовательности представляющей

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

значения в «нечетных точках» вычисляются в первый раз:

Формулы (6.5.9) и (6.5.10) можно рассматривать как свертку.

3. Интерполируем (кусочно-постоянным образом, если кусочно-линейным, если для получения в недиадических

В работе Добеши и Лагариса [59] этот алгоритм был назван каскадным алгоритмом, при этом они выбрали . В [53] Добеши выбрала Все графики для из § 6.4 и более поздних глав на самом деле являются графиками , где или . При данном разрешении этих рисунков разница между незаметна. Особенно привлекательным свойством каскадного алгоритма является возможность рассмотреть «в увеличительное стекло» отдельные особенности Предположим, что мы уже вычислили все но хотели бы рассмотреть с лучшим разрешением увеличенное изображение на интервале с центром в 1. Мы могли бы сделать это, вычислив все для очень большого а затем изобразив лишь на очень маленьком интересующем нас интервале, соответствующем Но нам не нужно этого делать: ввиду «локального» характера (6.5.9), (6.5.10) достаточно сделать намного меньше вычислений. Предположим для При вычислении используются лишь те для которых При их вычислении, в свою очередь, используется лишь где

или Возвращаясь назад к мы видим, что для вычисления на нам нужны лишь для 28 то 34. Таким образом, мы можем начать каскад с последовательности пройти пять шагов, выбрать семь значений , использовать лишь их в качестве входных значений нового каскада с четырьмя шагами и закончить рисунком на Для больших увеличений на даже еще меньших интервалах просто повторяем процесс. Графики в главе 7 были вычислены таким образом.

В рассуждениях, приводящих к каскадному алгоритму, неявно использовалась ортонормированность или, что то же (см. §§ 6.2, 6.3), ортонормированность Мы характеризовали как единственную функцию, удовлетворяющую (6.5.4), (6.5.5). Каскадный алгоритм можно рассматривать и по-другому, без акцента на ортонормированность, как частный случай стационарной схемы последовательного деления (subdivision scheme) или уточняющей схемы (refinement scheme).

Уточняющие схемы используются в компьютерной графике для построения кривых или поверхностей, проходящих через дискретное, часто довольно разреженное множество точек или вблизи него. Прекрасным обзором является работа Каваретты, Дамена и Мичелли [29]. В этом коротком обсуждении мы ограничимся одномерными схемами последовательного деления. Предположим, что мы хотим, чтобы кривая принимала заданные значения Можно просто построить кусочно-линейный график, проходящий через точки Для всех на этом графике выполняется соотношение

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

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

аналогичные (6.5.9), (6.5.10), содержали бы бесконечное число членов. Можно выбрать более гладкую, в сравнении с линейными сплайнами, аппроксимацию с интерполяционными формулами типа

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

Этот пример был подробно изучен Дюбуком в [70], Дин, Грегори, Левиным в [74] и обобщен, например, Делорье и Дюбуком в [67], Дин и Левиным в [73]. Он приводит к почти из (Подробнее о методах определения регулярности говорится в главе 7.) Формула (6.5.14) описывает интерполяционную уточняющую схему, в которой на каждом шаге вычисления значения, найденные ранее, не изменяются, и лишь значения в промежуточных точках подлежат вычислению. Можно также рассмотреть схемы, в которых значения, определенные на предыдущем шаге, в дальнейшем «уточняются», соответствуя более общей уточняющей схеме типа

Формула (6.5.15) на самом деле соответствует двум схемам свертки (с двумя масками, если использовать терминологию литературы об уточнении):

(уточнение уже вычисленных величин) и

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

(6.5.15) определяет лишь на дискретном множестве Точным утверждением «сходимости» к непрерывной функции является

где верхний индекс обозначает начальные данные, Говорят, что уточняющая схема сходится, если (6.5.18) выполняется для всех ; см. Каваретта, Дамен, Мичелли [29]. (Можно также переформулировать (6.5.18), вводя непрерывные функции интерполирующие см. ниже.) Если общая уточняющая схема является интерполяционной схемой, приводящей к

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

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

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

аппроксимирующие функции удовлетворяют соотношениям силу

(так как к к При этом предполагается, что похожая формула должна выполняться для всех т. е.

Индукцией показывается, что это и в самом деле выполняется:

Так как то из (6.5.22) следует, что для фундаментального решения выполняется уравнение

Теперь понятно, какое место занимают наши масштабирующие функции и каскадный алгоритм в уточняющих схемах: с одной стороны, удовлетворяет уравнению вида (6.5.23) (в основном, как следствие требования кратномасштабности а с другой стороны, каскадный алгоритм в точности соответствует (6.5.15), (6.5.20). Ортонормированность в отмеченных рамках кратномасштабности несколько облегчала нашу жизнь при доказательстве предложения 6.5.2, но похожие результаты могут быть доказаны для уточняющих схем и без привлечения ортонормированности Приведем некоторые основные результаты для уточняющих схем.

• Если уточняющая схема (6.5.15) сходится, то и соответствующее функциональное уравнение (6.5.23) допускает единственное непрерывное решение с компактным носителем (с точностью до нормировки).

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

Для доказательства этого и многих других результатов мы рекомендуем работу Каваретты, Дамена, Мичелли [29] и цитируемую там литературу. Заметим, что условие в точности соответствует требованиям

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

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

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

т.е. Тогда являются коэффициентами маски для интерполяционной уточняющей схемы, поскольку (см. . В частности, как замечено Шенсой в [162], интерполяционные уточняющие схемы, полученные выбором в (6.1.11), являются так называемыми интерполяционными схемами Лагранжа, подробно изученными Делорье и Дюбуком в примером которых является (6.5.14).

Заметим, что (за исключением случая Хаара) конечный ортонормированный вейвлет-фильтр не может быть также и интерполяционным фильтром: ортонормированность предполагает в то время как условие интерполяции эквивалентно или Если выполняются оба условия, то

или

Допустим, что для Тогда (6.5.24) уже предполагает, что либо либо Пусть

(случай аналогичен); обязательно нечетное, Возьмем в (6.5.24). Тогда

Поскольку то Аналогично приводит к

что вместе с приводит к . В конечном итоге лишь являются ненулевыми, и оба равняются так что маска является «вытянутой» маской Хаара. Тогда ортонормированность дает или т. е. базис Хаара. Если убрать ограничение, что является тригонометрическим полиномом, т. е. что могут иметь носителем всю вещественную ось, то условия то могут выполняться одновременно для нетривиального Примеры можно найти у Евангелисты в [77] или у Лемарье, Малгуйреса в [127].