MATLAB.Exponenta
–Û·Ë͇ Matlab&Toolboxes

Обработка сигналов и изображений\Wavelet Toolbox

Теоретические основы лифтинга (К.А.Алексеев)

Введение

Предположим, что на некотором финитном интервале времени задана последовательность отсчетов (т.н. последовательность Кронекера)

,

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

. (1)

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

. (2)

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

Рис. 1

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

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

, (3)

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

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

.

Во-вторых, скейлинг-функции удовлетворяют соотношению подобия

, (4)

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

Вейвлет-функции уровня (см. рис. 3) являются ортогональным дополнением скейлинг-функций:

,

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

. (5)

Рис. 2

Рис. 3

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

,

,

что вытекает из свойства биортогональности их фильтров:

,

.

Лифтинг

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

Рис. 4

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

, (6)

. (7)

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

. (8)

Здесь коэффициенты и фильтров , таких, что или

,

образуют матрицу , столбцы которой биортогональны строкам матрицы : , , или

.

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

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

, (9)

, (10)

, (11)

, (12)

или в матричной форме

,

.

Это означает, что, согласно выражениям (10), (11), лифтинг претерпевают лишь фильтры , тогда как фильтры , как видно из выражений (9), (12), остаются неизменными. Наряду с фильтрами лифтинг также воздействует на порождаемые ими вейвлет-функции и их дуальные аналоги , а также дуальные скейлинг-функции , поскольку

,

,

,

.

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

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

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

. (13)

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

В то же время, процедура восстановления данных, осуществляемая по формуле

,

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

,

т.е. выражением, попросту отменяющим предыдущие операции (см. рис. 5).

Рис. 5

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

вычисление последовательности масштабирующих коэффициентов посредством свертки ,

вычисление последовательности коэффициентов детализации посредством свертки ,

лифтинг масштабирующей последовательности на основании выражения (13);

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

восстановление данных как .

Дуальный лифтинг

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

, (14)

, (15)

, (16)

, (17)

приводящих к лифтингу скейлинг и вейвлет-функций:

,

, (18)

,

.

Здесь, как следует из выражений (14), (17), лифтинг претерпевают фильтры , тогда как фильтры , согласно выражениям (15), (16), остаются неизменными. Данное обстоятельство, вообще говоря, является в лифтинге основополагающим, т.к. позволяет гарантировать неизменность числа нулевых моментов дуальных скейлинг-функций , полученных с использованием (10), после приложения к ним дуального лифтинга (14) - (17). Поэтому на основании выражения (18) можно записать, что

(19)

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

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

(20)

или

, (21)

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

Умножим выражение (21) на , где , тогда после интегрирования правой и левой частей получим:

.

В силу свойства сохранения нулевых моментов дуальных скейлинг и вейвлет-функций

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

. (22)

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

Запишем результирующее выражение для дуального лифтинга функций :

.

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

вычислим последовательность масштабирующих коэффициентов посредством свертки ,

вычислим последовательность коэффициентов детализации (без лифтинга) посредством свертки ,

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

найдем коэффициенты детализации посредством лифтинга коэффициентов как .

Рис. 6

Реализация обратного дуального лифтинга представляется очевидной:

отменим последнюю операцию дуального лифтинга,

осуществим операции восстановления последовательности масштабирующих коэффициентов и последовательности данных .

Многомоментность. Лифтинг-коэффициенты

Одним из необходимых условий корректности многомасштабного анализа является, как известно, соблюдение постоянства какой-либо интегральной характеристики исследуемых данных при изменении масштаба их рассмотрения:

.

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

. (23)

Для этого в схемах (9) - (12), (14) - (17) посредством операторов и осуществляется преобразование функций , и, следовательно, изменение числа их нулевых моментов.

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

,

.

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

. (24)

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

(25)

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

Неравенство нулю моментов , вытекающее из условия (24), приводит систему (25) к неоднородной системе:

,

решение которой относительно не вызывает затруднений.

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

Литература

1. Истомина Т.В., Чувыкин Б.В., Щеголев В.Е. Применение теории wavelets в задачах обработки информации. - Пенза: Изд-во Пенз. гос. ун-та, 2000. - 188 с.

2. Новиков И.Я., Стечкин С.Б. Основы теории всплесков // Успехи математических наук, 1998, №6. - С. 53 - 128

4. Новиков Л.В. Основы вейвлет-анализа сигналов. - СПб., 1999. - 152 с.

5. Sweldens, W. The lifting scheme: A custom-design construction of biorthogonal wavelets // Appl. Comput. Harmon. Anal., 3(2): 186-200, 1996

Численное моделирование

Лифтинг и функции Хаара

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

,

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

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

,

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

Рис. 1

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

(1)

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

, (2)

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

Выражая из формулы (1) через коэффициент и оценку и подставляя в выражение (2), получим:

. (3)

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

Рис. 2

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

. (4)

Полагая в последовательности для всех и для , составим систему

. (5)

В силу предположений, высказанных относительно коэффициентов , перепишем систему (5) следующим образом:

.

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

. (6)

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

,

где

,

,

.

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

(7)

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

Так, лифтинг, осуществляемый над отсчетами исходной последовательности, в условиях (7) имеет вид:

.

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

, (8)

. (9)

Интегрирование правой и левой частей выражений (8), (9) позволяет получить систему уравнений относительно искомых , :

.

Отыскание коэффициентов , представляется очевидным; например, по правилу Крамера имеем:

,

.

Расчет лифтинга порядков

Рассмотрим иллюстративный пример расчета и моделирования лифтинг-схемы порядков .

Предположим, в нашем распоряжении имеется последовательность отсчетов некоторого сигнала, взятого с шагом дискретизации, равным 1: , где - длина данной последовательности.

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

. (10)

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

. (11)

Подобная перегруппировка отсчетов на четно и нечетно индексируемые имеет в литературе название лэйзи-преобразования (от англ. - lazy).

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

. (12)

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

Равенство средних значений отсчетов исходной последовательности и коэффициентов последовательности (23, ч. I) позволяет записать выражение для лифтинга порядка :

,

где А - некоторый лифтинг-коэффициент. Просуммируем правую и левую части данного выражения

и после подстановки в него выражения (12) с учетом (10), (11) получим:

. (13)

Из выражения (13) следует, что лифтинг-коэффициент и, таким образом,

.

Замечание

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

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

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


Поиск по сайту:

Система Orphus

Яндекс.Метрика