Глава 6. ЛИФТИНГОВАЯ СХЕМА

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

Основная идея лифтинговой схемы весьма проста. Как показано на рис. 6.1, преобразование включает в себя три этапа: разбиение (S), предсказание (P) и обновление (U).

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

Рис. 6.1. Лифтинговая схема: разбиение, предсказание и обновление

6.1. Этап разбиения

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

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

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

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

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

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

6.2. Этап предсказания

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

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

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

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

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

Для поиска хорошего оператора предсказания предположим, что соседние отсчеты сигнала сильно коррелированны. Тогда для предсказания нечетных отсчетов можно просто взять среднее их (четных) соседей:

Вейвлет-коэффициенты тогда находятся, как

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

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

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

6.3. Различные операторы предсказания

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

Обозначим через N порядок схемы подразделения (интерполяции). Например, для кусочно-линейной аппроксимации N = 2, для кубической аппроксимации N = 4 и т.д. N показывает степень гладкости интерполяционной функции, применяемой для вычисления вейвлет-коэффициентов. Будем называть эту функцию дуальный вейвлет, и N - число дуальных нулевых моментов.

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

Новое значение (с нечетным индексом) будет равно значению, принимаемому этим полиномом на середине интервала. Нечетные отсчеты с четным индексом остаются без изменения:

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

Рис. 6.2. Примеры интерполяционного подразделения.

Линейная и кубическая интерполяции

пределе воспроизводя его. Таким образом, используя N отсчетов (N - четное), можно строить полином степени N - 1. Будем говорить, что схема подразделения имеет порядок N.

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

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

Данная интерполяционная схема позволяет легко решить проблему границы для сигналов конечной длины. Например, для кубического полинома у левой границы сигнала можно взять один отсчет слева и три справа. Аналогично и у правой границы. При вычислении новых значений у около правой границы берется меньше коэффициентов справа и больше слева. Если коэффициент у находится на правой границе, то коэффициентов справа не берется вообще. Представим все возможные случаи для N = 4.

Случай 1. Возле левой границы: 1 коэффициент слева и справа.

Случай 2. Вдали от границ: слева и справа.

Случай 3. Возле правой границы: слева и справа либо слева и справа.

На рис. 6.3 показан случай, когда коэффициент у вычисляется возле левой границы для кубического интерполяционного подразделения (N = 4).

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

Используя данную интерполяционную схему и алгоритм Невилля, вычисляются коэффициенты, с помощью которых находится аппроксимация функции порядка N -1. Например, если N = 2, необходимо два коэффициента для каждого из двух возможных случаев (по одному коэффициенту слева и справа либо 2 слева и 0 справа). Если N = 4, требуется четыре коэффициента для каждого из четырех вышеперечисленных случаев. Эти коэффициенты называются коэффициентами фильтра.

Рис. 6.3. Поведение схемы кубического интерполяционного подразделения (а) вдали от границы; (б) вдали от границы; (в)вблизи границы

Коэффициенты фильтра, вычисляемые для левой границы, равны коэффициентам для правой границы, но записываются в обратном порядке. Так что всего существует N/2 + 1 различных случаев (один для середины и N/2 для границ интервала).

Пример вычисления коэффициентов кубической интерполяции показан на рис. 6.4.

Основная идея вычисления коэффициентов заключается в следующем: N = 4, поэтому имеется четыре коэффициента в любом случае. Если мы хотим вычислить, например, приравниваем его к единице, а три остальных - к нулю. Получается полином (в данном случае, кубический). Далее вычисляется функция в интересующих нас точках. Для случая, представленного на рис.6.4(а) это будет «два слева и два справа», а для случая на рис.6.4(б) - «один слева и три справа». В табл. 6.1 приведен список коэффициентов фильтров, требующихся для интерполяции при N = 2,4 . Одним из свойств коэффициентов фильтров является то, что их сумма равна 1 для любого N.

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

Рис. 6.4. Вычисление коэффициентов для N = 4 : (а)- в середине интервала; (б) - вблизи границы

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

Таблица 6.1. Коэффициенты фильтра при N = 2

Таблица 6.2. Коэффициенты фильтра при N = 4

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

среднее значение пикселов. Эта проблема решается на третьем этапе - обновления.

6.4. Этап обновления

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

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

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

Основными свойствами, которые мы хотим сохранить на каждом уровне, являются моменты вейвлет-функции Из свойств вейвлет-функций

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

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

После инициализации моментов выполняются следующие шаги.

1. Проверяется вклад в предсказание каждого у. (На основе коэффициентов фильтра, найденных на предыдущем этапе).

2. Для каждого на текущем уровне обновляются моменты согласно следующему выражению:

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

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

а) текущий у приравнивается к 1, остальные у - к нулю;

б) выполняется один шаг обратного преобразования для определения вклада данного у в который обновляет его. Получается следующая система уравнений:

где искомые коэффициенты лифтинга, индекс коэффициента X на текущем уровне; длина сигнала) - индекс коэффициента , приравненного к единице;

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

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

Далее переходим к следующему у, и процесс повторяется.

Рассмотрим этапы разбиения, предсказания и обновления на примере одномерного сигнала длиной Вначале рассмотрим разбиение и предсказание:

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

Коэффициент Я использует а от для обновления. Аналогично использует от и а от и т.д.

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

Обновление происходит следующим образом:

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

Объединение трех этапов лифтинга, представленных на диаграмме рис.

6.1, дает нам алгоритм одномерного быстрого лифтингового вейвлет-преобразования:

Теперь можно показать одно замечательное свойство лифтинга: для реализации обратного преобразования достаточно в алгоритме прямого преобразования поменять местами знаки Таким образом, алгоритм обратного преобразования можно записать в виде

Объединить

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

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

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

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

Варьируя все три этапа лифтинга, можно получить семейство биортогональных вейвлетов:

1. Разбиение. В качестве начального разбиения возможен другой выбор, чем вейвлет Лэйзи. Классическим примером является вейвлет Хаара.

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

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

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

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

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

Рис. 6.5. Лифтинговая схема Разбиение, вычисление вейвлет-коэффициентов как степени отклонения сигнала от линейного и использование их для обновления