Tutorial

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

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

Сжатие изображений

Упрощённо, изображение представляют собой таблицу, в ячейках которой хранятся цвета каждого пикселя. Если мы работаем с чёрно-белым (или, точнее, серым) изображением, то вместо цвета в ячейки помещают значения яркости из отрезка . При этом 0 соответствует чёрному цвету, 1 - белому. Но с дробями работать неудобно, поэтому часто значения яркости берут целыми из диапазона от 0 до 255. Тогда каждое значение будет занимать ровно 1 байт.

Даже небольшие изображения требуют много памяти для хранения. Так, если мы кодируем яркость каждого пикселя одним байтом, то изображение одного кадра формата FullHD (1920×1080) займёт почти два мегабайта. Представьте, сколько памяти потребуется для хранения полуторачасового фильма!

Поэтому изображения стремятся сжать. То есть закодировать таким образом, чтобы памяти для хранения требовалось меньше. А во время просмотра мы декодируем записанные в память данные и получаем исходный кадр. Но это лишь в идеале.

Существует много алгоритмов сжатия данных. О их количестве можно судить по форматам, поддерживаемым современными архиваторами: ZIP, 7Z, RAR, ACE, GZIP, HA, BZ2 и так далее. Неудивительно, что благодаря активной работе учёных и программистов в настоящее время степень сжатия данных вплотную подошла к теоретическому пределу.

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

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

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

Однако если в нашей последовательности в середине вдруг окажется единица, то одним числом 100 ограничится не удастся.

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

Преобразование Хаара

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

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

Рассмотрим фрагмент первой строки яркостей из известного изображения «Lenna» (на рисунке).

154, 155, 156, 157, 157, 157, 158, 156

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

Получаем:

154, 1, 1, 1, 0, 0, 1, -2.

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

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

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

(154, 155), (156, 157), (157, 157), (158, 156)
(154.5, 0.5), (156.5, 0.5), (157, 0.0), (157, -1.0)

Почему именно полусуммы и полуразности? А всё очень просто! Полусумма - это среднее значение яркости пары пикселей. А полуразность несёт в себе информацию об отличиях между значениями в паре. Очевидно, зная полусумму a и полуразность d можно найти и сами значения:
первое значение в паре = a - d,
второе значение в паре = a + d.

Это преобразование было предложено в 1909 году Альфредом Хааром и носит его имя.

А где же сжатие?

Полученные числа можно перегруппировать по принципу «мухи отдельно, котлеты отдельно», разделив полусуммы и полуразности:

154.5, 156.5, 157, 157; 0.5, 0.5, 0.0, -1.0.

Числа во второй половине последовательности как правило будут небольшими (то, что они не целые, пусть пока не смущает). Почему так?

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

В самом деле, рассмотрим первые 2000 пар соседних пикселей и каждую пару представим на графике точкой.

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

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

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

Применим математику!

Попробуем записать математические выражения, описывающие преобразование Хаара.

Итак, у нас была пара пикселей (вектор) , а мы хотим получить пару .

Такое преобразование описывается матрицей .

В самом деле , что нам и требовалось.

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

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

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

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

Получаем в итоге матрицу

А как декодировать?

Как известно, если у матрицы определитель не равен нулю, то для неё существует обратная матрица, «отменяющая» её действие. Если мы найдём обратную матрицу для H, то декодирование будет заключаться просто в умножении векторов с полусуммами и полуразностями на неё.

Вообще говоря, поиск обратной матрицы - не такая простая задача. Но, может, удастся как-то эту задачу упростить?

Рассмотрим поближе нашу матрицу. Она состоит из двух вектор-строк: и . Назовём их v 1 и v 2 .

Они обладают интересными свойствами.

Во-первых, их длины равны 1, то есть . Здесь буква T означает транспонирование. Умножение вектор-строки на транспонированный вектор-строку - это скалярное произведение.

Во-вторых, они ортогональны, то есть .

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

В справедливости этого выражения можно убедиться умножив H обратную матрицу. На диагонали мы получим скалярные произведения вектор-строк на самих себя, то есть 1. А вне диагоналей - скалярные произведения вектор-строк друг на друга, то есть 0. В итоге произведение будет равно единичной матрице.

Мы любим ортогональные матрицы!

Увеличиваем число точек

Всё сказанное хорошо работает для двух точек. Но что делать, если точек больше?

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

То есть. исходный вектор просто обрабатывается независимо по парам.

Фильтры

Итак, когда мы знаем, как выполнять преобразование Хаара, попробуем разобраться с тем, что же оно нам даёт.

Полученные «полусуммы» (из-за того, что делим не на 2, приходится использовать кавычки) - это, как мы уже выяснили, средние значения в парах пикселей. То есть, фактически, значения полусумм - это уменьшенная копия исходного изображения! Уменьшенная потому, что полусумм в два раза меньше, чем исходных пикселей.

Но что такое разности?

Полусуммы усредняют значения яркостей, то есть «отфильтровывают» случайные всплески значений. Можно считать, что это некоторый частотный фильтр.

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

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

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

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

Степень сжатия можно увеличить, применяя преобразование Хаара многократно. В самом деле, высокочастотная составляющая - это всего лишь половина от всего набора чисел. Но что мешает применить нашу процедуру ещё раз к низкочастотным данным? После повторного применения, высокачастотная информация будет занимать уже 75%.

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

После многократного применения к, например, фотографии замка Лихтенштейн, получим следующий рисунок.

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

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

Конечно, если обнулить слишком много, то искажения станут видны на глаз. Во всём нужна мера!

После всех этих действий у нас останется матрица, содержащая много нулей. Её можно записать построчно в файл и сжать каким-то архиватором. Например, тем же 7Z. Результат будет неплох.

Декодирование производится в обратном порядке: распаковывем архив, применяем обратное преобразование Хаара и записываем декодированную картинку в файл. Вуаля!

Где эффективно преобразование Хаара?

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

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

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

Эту задачу и более сложные (устранение моментов более высоких порядков) решила Ингрид Добеши - один из создателей теории вейвлетов.

Преобразование Добеши

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

То есть, если исходная последовательность - 1, 2, 3, 4, 5, 6,…, N-1, N, то будем брать четвёрки (1, 2, 3, 4), (3, 4, 5, 6) и т. д. Последняя четвёрка «кусает последовательность за хвост»: (N-1, N, 1, 2).

Точно так же попробуем построить два фильтра: высокочастотный и низкочастотный. Каждую четвёрку будем заменять на два числа. Так как четвёрки перекрываются, то количество значений после преобразования не изменится.

Пусть значения яркостей в четвёрке равны x, y, z, t. Тогда первый фильтр запишем в виде

Четыре коэффициента, образующих вектор-строку матрицы преобразования, пока нам неизвестны.

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

Матрица преобразования будет иметь вид.

Требование ортогональности выполняется для первой и второй строк автоматически. Потребуем, чтобы строки 1 и 3 тоже были ортогональны:

Векторы должны иметь единичную длину (иначе определитель будет не единичным):

Преобразование должно обнулять цепочку одинаковых значений (например, (1, 1, 1, 1)):

Преобразование должно обнулять цепочку линейно растущих значений (например, (1, 2, 3, 4)):

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

Получили 4 уравнения, связывающие коэффициенты. Решая их, получаем:

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

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

Это преобразование получило название вейвлета D4 (читателю предлагается самостоятельно разгадать тайну этого буквенно-цифрового названия).

Другие вейвлеты

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

Чтобы не считать всё вручную, коэффициенты можно посмотреть в википедии .

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

Домашнее задание

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

Попробуйте выполнить обратное преобразование. Как вы объясните характер артефактов на изображении?

Заключение

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

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

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

Для обработки дискретных сигналов используется дискретное вейвлет-преобразование (ДВП, DWT).

Первое ДВП было предложно венгерским математиком Альфредом Хааром. Для входного сигнала, представленного массивом 2 n чисел, вейвлет преобразование Хаара просто группирует элементы по 2 и образует от них суммы и разности. Группировка сумм проводится рекурсивно для образования следующего уровня разложения. В итоге получается 2 n −1 разность и 1 общая сумма. Мы начнем с одномерного массива данных, состоящего из N элементов. В принципе, этими элементами могут быть соседние пикселы изображения или последовательные звуковые фрагменты. Примером будет служить массив чисел (2,9,12,10,9,8, 8,7). Сначала вычислим четыре средние величины (Рис. 40)

Ясно, что знания этих четырех полусумм не достаточно для восстановления всего массива, поэтому мы еще вычислим четыре полуразности

(2 - 9)/2 = - 4,5,

(12 - 10)/2 = 1,

(9 – 8)/2 = 0,5,

(8 – 7)/2 = 0,5,

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

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

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

Рисунок 3.18. Илллюстрация работы одномерного вейвлет-преобразования.

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

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

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

Рисунок 3.19. Стандартное двумерное вейвлет-преобразование

Рисунок 3.20. Пирамидальное двумерное вейвлет-преобразование

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

Рисунок 3.21. Составляющие двумерного вейвлет-преобразования

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

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

Рисунок 3.22 . Пример вейвлет-преобразования изображения.

Вейвлет-преобразование используется в стандарте сжатия изображений JPEG2000, а также предусмотрено в качестве инструмента в формате MPEG-4.

Дискретные вейвлет-преобразования.

6.3.3.1. Общие сведения о вейвлет-преобразованиях.

Вейвлетное преобразование сигналов является обобщением спектрального анализа, типичный представитель которого – классическое преобразование Фурье.

Вейвлет-преобразования (WT) подразделяют на дискретное (DWT) и непрерывное (CWT). DWT используется для преобразований и кодирования сигналов, CWT – для анализа сигналов.

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

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

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

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

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

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

Рисунок

Рисунок 3.1 – вейвлет-преобразование сигнала

6.3.3.2. Базисные функции вейвлет-преобразований.

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

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

, (3.1)

где b – сдвиг;

а – масштаб.

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

Следующая функция

не зависит от параметров и . Вектор, заданный функцией , имеет постоянную длину в пространстве:

На практике, в качестве базовой функции часто используют функцию

называемую мексиканской шляпой.

6.3.3.3. Непрерывное вейвлет-преобразование.

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

. (3.2)

Если базисная функция описывается выражением:

то в результате имеется обычное преобразование Фурье (в этом случае параметр не используется).

Для перекрытия функцией вейвлета всей временной оси пространства используется операция сдвига (смещения по временной оси): , где значение b для НВП является величиной непрерывной. Для перекрытия всего частотного диапазона используется операция временного масштабирования вейвлета с непрерывным изменением независимой переменной: . Таким образом, путем сдвига по независимой переменной (t-b) вейвлет имеет возможность перемещаться по всей числовой оси произвольного сигнала, а путем изменения масштабной переменной "а" (в фиксированной точке (t-b) оси) «просматривать» частотный спектр сигнала по определенному интервалу окрестностей этой точки.

Таким образом, непрерывное вейвлет-преобразование представляет собой разложение сигнала по всем возможным сдвигам и сжатиям/растяжениям некоторой локализованной финитной функции – вейвлета. При этом переменная "a" определяет масштаб вейвлета и эквивалентна частоте в преобразованиях Фурье, а переменная "b" – сдвиг вейвлета по сигналу от начальной точки в области его определения, шкала которого повторяет временную шкалу анализируемого сигнала.

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

6.3.3.4. Дискретное вейвлет-преобразование.

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

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

где ;

Целые числа;

Параметр масштаба;

Параметр сдвига.

Базис пространства в дискретном представлении:

Вейвлет-коэффициенты прямого преобразования:

. (3.5)

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

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

. (3.6)

Число использованных вейвлетов по масштабному коэффициенту m задает уровень декомпозиции сигнала, при этом за нулевой уровень (m = 0) обычно принимается уровень максимального временного разрешения сигнала, т.е. сам сигнал, а последующие уровни (m < 0) образуют ниспадающее вейвлет-дерево . В программном обеспечении вычислений для исключения использования отрицательной нумерации по m знак "минус" обычно переносится непосредственно в следующее представление базисных функций:

6.3.3.5. Частотно-временная локализация вейвлет-анализа.

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

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

. (3.8)

Если считать, что каждый вейвлет имеет определенную «ширину» своего временного окна, которому соответствует определенная «средняя» частота спектрального образа вейвлета, обратная его масштабному коэффициенту а , то семейства масштабных коэффициентов вейвлет-преобразования можно считать аналогичными семействам частотных спектров оконного преобразования Фурье, но с одним принципиальным отличием. Масштабные коэффициенты изменяют «ширину» вейвлетов и, соответственно, «среднюю» частоту их фурье-образов, а, следовательно, каждой частоте соответствует своя длительность временного окна анализа, и наоборот. Так малые значения параметра а , характеризующие быстрые составляющие в сигналах, соответствуют высоким частотам, а большие значения – низким частотам. За счёт изменения масштаба вейвлеты способны выявлять различия на разных частотах, а за счёт сдвига (параметр b ) проанализировать свойства сигнала в разных точках на всём исследуемом временном интервале. Многоразмерное временное окно вейвлет-преобразования адаптировано для оптимального выявления и низкочастотных, и высокочастотных характеристики сигналов.

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

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

6.3.3.6. Достоинства и недостатки вейвлет-анализа.

К достоинствам вейвлет-анализа можно отнести:

Вейвлетные преобразования обладают всеми достоинствами преобразований Фурье;

Вейвлетные базисы могут быть хорошо локализованными как по частоте, так и по времени;

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

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

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

6.3.3.7. Свойства вейвлет-анализа.

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

Линейность .

TW[α·x 1 (t)+β·x 2 (t)] = α·TW+β·TW.

Инвариантность относительно сдвига . Сдвиг сигнала во времени на t 0 приводит к сдвигу вейвлет-спектра также на t 0:

TW = X(a, b-t o).

Инвариантность относительно масштабирования . Растяжение (сжатие) сигнала приводит к сжатию (растяжению) вейвлет-спектра сигнала:

TW = (1/а о)·X(a/а о,b/а o).

Дифференцирование .

D n {TW}/dt n = TW.

TW = (-1) n x(t) dt.

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

Аналог теоремы Парсеваля для ортогональных и биортогональных вейвлетов.

X 1 (t)·x 2 *(t) = X ψ -1 a -2 X(a,b) X*(a,b) da db.

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

Основы цифровой обработки сигналов: учебное пособие / Ю.А. Брюханов, А.А. Приоров, В.И. Джиган, В.В. Хрящев; Яросл. Гос. ун-т им. П.Г. Демидова. – Ярославль: ЯрГУ, 2013. – 344 с. (с. 270)

Тема Вейвлет-преобразования.

Лекции 6-8

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

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

Многомасштабное представление поверхностей для вейвлет-анализа. Вейвлет-сжатие сигналов, изображений, видеоизображений.

Вейвлетное преобразование сигналов является обобщением спектрального анализа, типичный представитель которого – классическое преобразование Фурье. Термин "вейвлет" (wavelet) в переводе с английского означает "маленькая (короткая) волна". Вейвлеты - это обобщенное название семейств математических функций определенной формы, которые локальны во времени и по частоте, и в которых все функции получаются из одной базовой (порождающей) посредством ее сдвигов и растяжений по оси времени. Вейвлет-преобразования рассматривают анализируемые временные функции в терминах колебаний, локализованных по времени и частоте. Как правило, вейвлет-преобразования (WT) подразделяют на дискретное (DWT) и непрерывное (CWT).

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

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

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

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

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

История спектрального анализа восходит к И. Бернулли, Эйлеру и Фурье, который впервые построил теорию разложения функций в тригонометрические ряды. Однако это разложение долгое время применялось как математический прием и не связывалось с какими-либо физическими понятиями. Спектральные представления применялись и развивались сравнительно узким кругом физиков–теоретиков. Однако, начиная с 20-х годов прошлого века, в связи с бурным развитием радиотехники и акустики, спектральные разложения приобрели физический смысл и практическое применение. Основным средством анализа реальных физических процессов стал гармонический анализ, а математической основой анализа - преобразование Фурье. Преобразование Фурье разлагает произвольный процесс на элементарные гармонические колебания с различными частотами, а все необходимые свойства и формулы выражаются с помощью одной базисной функции exp(jt) или двух действительных функций sin(t) и cos(t). Гармонические колебания имеют широкое распространение в природе, и поэтому смысл преобразования Фурье интуитивно понятен независимо от математической аналитики.

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

Было также установлено, что функции можно разложить не только по синусам и косинусам, но и по другим ортогональным базисным системам, например, полиномам Лежандра и Чебышева, функциям Лагерра и Эрмита. Однако практическое применение они получили только в последние десятилетия ХХ века благодаря развитию вычислительной техники и методов синтеза цифровых линейных систем обработки данных. Непосредственно для целей спектрального анализа подобные ортогональные функции не нашли широкого применения из-за трудностей интерпретации получаемых результатов. По тем же причинам не получили развития в спектральном анализе функции типа "прямоугольной волны" Уолша, Радемахера, и пр.

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

Вейвлет-анализ является разновидностью спектрального анализа, в котором роль простых колебаний играют функции особого рода, называемые вейвлетами. Базисная функция вейвлет – это некоторое "короткое" колебание, но не только. Понятие частоты спектрального анализа здесь заменено масштабом, и, чтобы перекрыть "короткими волнами" всю временную ось, введен сдвиг функций во времени. Базис вейвлетов – это функции типа ((t-b)/a), гдеb- сдвиг, а – масштаб. Функция(t) должна иметь нулевую площадь и, еще лучше, равными нулю первый, второй и прочие моменты. Фурье-преобразование таких функций равно нулю при=0 и имеет вид полосового фильтра. При различных значениях масштабного параметра "a" это будет набор полосовых фильтров. Семейства вейвлетов во временной или частотной области используются для представления сигналов и функций в виде суперпозиций вейвлетов на разных масштабных уровнях декомпозиции (разложения) сигналов.

Первое упоминание о подобных функциях (которые вейвлетами не назывались) появилось в работах Хаара (Haar) еще в начале прошлого века. Вейвлет Хаара - это короткое прямоугольное колебание на интервале , показанное на рис. 1.1.1. Однако он интересен больше теоретически, так как не является непрерывно дифференцируемой функцией и имеет длинные "хвосты" в частотной области. В 30-е годы физик Пол Леви (Paul Levy), исследуя броуновское движение, обнаружил, что базис Хаара лучше, чем базис Фурье, подходит для изучения деталей броуновского движения.

Сам термин "вейвлет", как понятие, ввели в своей статье Дж. Морле и А. Гроссман (J. Morlet, A. Grossman), опубликованной в 1984 г. Они занимались исследованиями сейсмических сигналов с помощью базиса, который и назвали вейвлетом. Весомый вклад в теорию вейвлетов внесли Гуппилауд, Гроссман и Морле, сформулировавшие основы CWT, Ингрид Добеши, разработавшая ортогональные вейвлеты (1988), Натали Делпра, создавшая время-частотную интерпретацию CWT (1991), и многие другие. Математическая формализация вейвлетов в работах этих и других авторов привела к созданию теоретических основ вейвлет-анализа, названного мультиразрешающим (кратномасштабным) анализом.

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

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

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

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

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

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

Определение вейвлета. К вейвлетам относятся локализованные функции, которые конструируются из одного материнского вейвлета (t) (или по любой другой независимой переменной) путем операций сдвига по аргументу (b) и масштабного изменения (а):

 ab (t) = (1/) ((t-b)/a), (a, b)R, (t)L 2 (R).

где множитель (1/) обеспечивает независимость нормы функций от масштабного числа "a".

Непрерывное вейвлет-преобразование сигнала s(t)L 2 (R), которое применяется для качественного частотно-временного анализа, по смыслу соответствует преобразованию Фурье с заменой гармонического базиса exp(-jt) на вейвлетный ((t-b)/a):

С(a, b) = s(t),  ab (t) = (1/)s(t)((t-b)/a) dt, (a, b)R, a0.

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

Рис. 24.1.1. Вейвлеты Mhat и Wave.

На рис. 24.1.1 приведены примеры простейших неортогональных вейвлетов четного (Mhat) и нечетного (Wave) типов.

Для количественных методов анализа в качестве вейвлетных базисов можно использовать любые локализованные функции (t), если для них существуют функции-двойники  # (t), такие, что семейства { ab (t)} и {  ab (t)} могут образовывать парные базисы функционального пространства L 2 (R). Вейвлеты, определенные таким образом, позволяют представить любую произвольную функцию в пространстве L 2 (R) в виде ряда:

s(t) = С(a,b)  ab (t), (a, b)I,

где коэффициенты С(a,b) – проекции сигнала на вейвлетный базис пространства:

С(a,b) = s(t),  ab (t) =s(t) ab (t) dt.

Если вейвлет (t) обладает свойством ортогональности, то   (t) ≡ (t) и вейвлетный базис ортогонален. Вейвлет может быть неортогональным, однако если он имеет двойника, и пара ((t),   (t)) дает возможность сформировать семейства { mk (t)} и {  zp (t)}, удовлетворяющие условию биортогональности на целых числах I:

 mk (t),   zp (t) =  mz · kp , m,k,z,p Î I,

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

Свойства вейвлета ,

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

Нулевое среднее значение , т.е. выполнение условия для нулевого момента:

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

Ограниченность. Необходимое и достаточное условие:

||(t)|| 2 =|(t)| 2 dt < 

Автомодельность базиса или самоподобие. Форма всех базисных вейвлетов  ab (t) должна быть подобна материнскому вейвлету (t), т.е. должна оставаться одной и той же при сдвигах и масштабировании (растяжении/сжатии), иметь одно и то же число осцилляций.

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

Спектр C(a,b) одномерного сигнала представляет собой поверхность в трехмерном пространстве. Способы визуализации спектра могут быть самыми различными. Наиболее распространенный способ – проекция на плоскость ab с изолиниями (изоуровнями), что позволяет проследить изменения коэффициентов на разных масштабах во времени, а также выявить картину локальных экстремумов этих поверхностей ("холмов" и "впадин"), так называемый "скелет" (skeleton) структуры анализируемого процесса. При широком диапазоне масштабов применяются логарифмические координаты (log a , b ). Пример вейвлетного спектра простейшего сигнала при его разложении вейвлетом Mhat приведен на рис. 24.1.2.

Рис. 24.1.2. Сигнал, вейвлетный Mhat - спектр и масштабные сечения спектра.

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

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

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

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

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

 n (x) = (-1) n +1 d n /dx n , n ≥ 1, (24.1.1)

WАVE-вейвлет вычисляется по первой производной (n=1) и приведен на рис. 24.1.3 во временной и частотной области для трех значений масштабных коэффициентов "а". Форма вейвлета относится к нечетным функциям и, соответственно, спектр вейвлета является мнимым. Уравнение вейвлета по (24.1.1) с единичной нормой:

Рис. 24.1.3. Вейвлет Wave.

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

МНАТ-вейвлет (Mexican hat – мексиканская шляпа) вычисляется по второй производной (n=2) и приведен на рис. 24.1.5. Вейвлет симметричен, спектр вейвлета представлен только действительной частью и хорошо локализован по частоте, нулевой и первый моменты вейвлета равны нулю. Применяется для анализа сложных сигналов. Уравнение вейвлета по (24.1.1):

Рис. 24.1.5. Вейвлет MHAT.

На рис. 24.1.6 приведен пример использования вейвлета для анализа сложного сигнала y(t). Модель сигнала образована суммой сигналов разной структуры. Сигналы у1-у2 представляют собой функции Гаусса разного масштабного уровня, сигнал у3 - прямоугольный импульс, сигнал у4 задан в виде тренда с постоянным значением дифференциала. На контурном графике вейвлет-коэффициентов можно видеть выделение всех трех основных структур сигнала при полном исключении тренда. Особенно четко выделяются границы скачков прямоугольной структуры. Справа на рисунке приведена полная трехмерная картина вейвлет-преобразования.

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

Рис. 24.1.7.

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

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

Свойства вейвлет-преобразования

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

Линейность .

TW[·s 1 (t)+·s 2 (t)] = ·TW+·TW. (24.2.1)

TW = C(a, b-t o). (24.2.2)

TW = (1/а о)·C(a/а о,b/а o). (24.2.3)

Дифференцирование .

d n {TW}/dt n = TW. (24.2.4)

TW = (-1) n s(t) dt. (24.2.5)

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

Аналог теоремы Парсеваля для ортогональных и биортогональных вейвлетов.

s 1 (t)·s 2 *(t) = C   a -2 С(a,b) С*(a,b) da db. (24.2.6)

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

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

24.3. Вейвлет-преобразование простых сигналов.

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

с(a,b) =s(t)(t,a,b), (24.3.1)

где суммирование выполняется в растворе угла влияния (по области достоверности) с шагом t = b = a = 1. Так как при непрерывном разложении скейлинг-функция не используется, отсчет значений "а" начинается с 1, а ряд коэффициентов c(0,b) оставляется нулевым и определяет нулевой фон контурных графиков спектра.

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

Рис. 24.3.1. Преобразование импульсов Кронекера.

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

Рис. 24.3.2. Преобразование функций Лапласа.

Аналогичный характер спектра сохраняется и для любых локальных неоднородностей на сигналах в форме пиков (рис. 24.3.2) со смещением максимумов (минимумов) коэффициентов с(a,b) со значений а=1 в область больших значений "а" (в зависимости от эффективной ширины пиков).

Рис. 24.3.3. Преобразование функций Гаусса.

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

Рис. 24.3.4. Преобразование перепада постоянного значения функций.

На рис. 24.3.4 приведены спектры двух разных по крутизне перепадов постоянных значений функции. Центры перепадов фиксируются по переходу через нуль значений коэффициентов c(a,b), а крутизна перепадов отражается, в основном, на значениях функции c(a,b) при малых значениях параметра "а".

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

Рис. 24.3.5. Преобразование изломов функций.

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

Рис. 24.3.6. Преобразование гармонических функций.

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

Рис. 24.3.7. Изменение фазы гармонического сигнала.

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

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

Рис. 24.3.8. Преобразование суммы трех сигналов.

Форма вейвлета (четность или нечетность), доминирующая частота и степень ее локализации существенно влияют на вейвлет-спектры анализируемых сигналов и на возможности выделения его локальных особенностей. На нижеследующих рисунках приведены сравнительные спектры простых сигналов при использовании вейвлетов Wave (нечетный, рис. 24.1.3), Mhat (четный, рис. 24.1.5) и вейвлета по 8-й производной Гаусса (рис. 24.3.9-24.3.16), который также является четным, и имеет в 4 раза более высокую доминирующую частоту, чем вейвлет Mhat.

Рис. 24.3.9. Импульсы Кронекера.

Рис. 24.3.10. Пики Лапласа.

Рис. 24.3.11. Функции Гаусса.

Рис. 24.3.12. Крутые скачки.

Рис. 24.3.13. Сглаженные скачки.

Рис. 24.3.14. Изломы функций

Рис. 24.3.15. Фазовые скачки гармоник.

Рис. 24.3.16. Сумма двух модулированных синусоид.

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

Принцип вейвлет-преобразования. Гармонические базисные функции преобразования Фурье предельно локализованы в частотной области (до импульсных функций Дирака при Т) и не локализованы во временной (определены во всем временном интервале от -до). Их противоположностью являются импульсные базисные функции типа импульсов Кронекера, которые предельно локализованы во временной области и "размыты" по всему частотному диапазону. Вейвлеты по локализации в этих двух представлениях можно рассматривать как функции, занимающие промежуточное положение между гармоническими и импульсными функциями. Они должны быть локализованными как во временной, так и в частотной области представления. Однако при проектировании таких функций мы неминуемо столкнемся с принципом неопределенности, связывающим эффективные значения длительности функций и ширины их спектра. Чем точнее мы будем осуществлять локализацию временного положения функции, тем шире будет становиться ее спектр, и наоборот, что наглядно видно на рис. 1.1.5.

Вейвлетный базис пространства L 2 (R), R(-,), целесообразно конструировать из финитных функций, принадлежащих этому же пространству, которые должны стремиться к нулю на бесконечности. Чем быстрее эти функции стремятся к нулю, тем удобнее использовать их в качестве базиса преобразования при анализе реальных сигналов. Допустим, что такой функцией является psi - функцияt, равная нулю за пределами некоторого конечного интервала и имеющая нулевое среднее значение по интервалу задания. Последнее необходимо для задания локализации спектра вейвлета в частотной области. На основе этой функции сконструируем базис в пространстве L 2 (R) с помощью масштабных преобразований независимой переменной.

Функция изменения частотной независимой переменной в спектральном представлении сигналов отображается во временном представлении растяжением/сжатием сигнала. Для вейвлетного базиса это можно выполнить функцией типа (t) =>(a m t), a = const, m = 0, 1, … , M, т.е. путем линейной операции растяжения/сжатия, обеспечивающей самоподобие функции на разных масштабах представления. Однако локальность функции(t) на временной оси требует дополнительной независимой переменной последовательных сдвигов функции(t) вдоль оси, типа(t) =>(t+k), для перекрытия всей числовой оси пространства R(-,). C учетом обеих условий одновременно структура базисной функции может быть принята следующей:

(t) => (a m t+k). (1.1.10)

Для упрощения дальнейших выкладок значения переменных m и kпримем целочисленными. При приведении функции (1.1.10) к единичной норме, получаем:

 mk (t) = a m/2 (a m t+k). (1.1.11)

Если для семейства функций  mk (t) выполняется условие ортогональности:

 nk (t), lm (t)= nk (t)·* lm (t) dt = nl · km , (1.1.12)

то семейство  mk (t) можно использовать в качестве ортонормированного базиса пространства L 2 (R). Произвольную функцию этого пространства можно разложить в ряд по базису mk (t):

s(t) =S mk  mk (t), (1.1.13)

где коэффициенты S m k – проекции сигнала на новый ортогональный базис функций, как и в преобразовании Фурье, определяются скалярным произведением

S mk = s(t),  mk (t) =s(t) mk (t) dt, (1.1.14)

при этом ряд равномерно сходиться:

||s(t) –S mk  mk (t),|| = 0.

При выполнении этих условий базисная функция преобразования (t) называется ортогональным вейвлетом.

Простейшим примером ортогональной системы функций такого типа являются функции Хаара. Базисная функция Хаара определяется соотношением

(t) =(1.1.15)

Легко проверить, что при а = 2, m = 0, 1, 2, ..., k = 0, 1,2, … две любые функции, полученные с помощью этого базисного вейвлета путем масштабных преобразований и переносов, имеют единичную норму и ортогональны. На рис. 1.1.6 приведены примеры функций для первых трех значений m и b при различных их комбинациях, где ортогональность функций видна наглядно.

Рис. 1.1.6. Функции Хаара

Вейвлетный спектр , в отличие от преобразования Фурье, является двумерным и определяет двумерную поверхность в пространстве переменныхmиk. При графическом представлении параметр растяжения/сжатия спектра m откладывается по оси абсцисс, параметр локализации k по оси ординат – оси независимой переменной сигнала. Математику процесса вейвлетного разложения сигнала в упрощенной форме рассмотрим на примере разложения сигнала s(t) вейвлетом Хаара с тремя последовательными по масштабу m вейвлетными функциями с параметром а=2, при этом сам сигнал s(t) образуем суммированием этих же вейвлетных функций с одинаковой амплитудой с разным сдвигом от нуля, как это показано на рис. 1.1.7.

Рис. 1.1.7. Скалярные произведения сигнала с вейвлетами.

Для начального значения масштабного коэффициента сжатия m определяется функция вейвлета (1(t) на рис. 1.1.7), и вычисляется скалярное произведение сигнала с вейвлетом1(t), s(t+k)с аргументом по сдвигу k. Для наглядности результаты вычисления скалярных произведений на рис. 1.1.7 построены по центрам вейвлетных функций (т.е. по аргументу k от нуля со сдвигом на половину длины вейвлетной функции). Как и следовало ожидать, максимальные значения скалярного произведения отмечаются там, где локализована эта же вейвлетная функция.

После построения первой масштабной строки разложения, меняется масштаб вейвлетной функции (2 на рис. 1.1.7) и выполняется вычисление второй масштабной строки спектра, и т.д.

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

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

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

, (18)

коэффициенты определяются из соотношения

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

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

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

и ее преобразование Фурье (рис. 9).

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

Сложно провести анализ временного сигнала по его Фурье образу;

Приемлемая аппроксимация временного сигнала возможна при учете большого числа высокочастотных коэффициентов;

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

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

Рис. 9. Преобразование Фурье синусоидального сигнала с небольшими ступеньками при переходе через нуль

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

(20)

Графически вейвлет Хаара представляется следующим образом:

Рис. 10. Базисная функция вейвлета Хаара

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

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

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

получим следующую аппроксимацию:

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

Рис. 11. Преобразование пар случайных величин

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

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

Рис. 12. Вейвлет-коэффициенты одного периода функции (19)

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

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

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

Следует отметить, что если число отсчетов , то максимальное значение равно . Наибольшее значение для текущего равно .

Для непрерывных сигналов будут справедливы следующие интегральные выражения:

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

Рис. 13. Распределение базисных функций Хаара при анализе сигнала

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

1. Ограниченность нормы:

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

и , при .

Контрпример: дельта-функция и гармоническая функция не удовлетворяют данному условию.

3. Нулевое среднее:

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

В качестве примера приведем следующие известные вейвлет-функции:

, .

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

Запишем алгоритм быстрого вейвлет-преобразования Хаара в матричном виде. Пусть дан вектор размером 8 элементов. Матрица преобразования Хаара запишется в виде