Вейвлет преобразование для чайников. Статистический дискретный вейвлет-анализ

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

, (18)

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

,

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

.

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

.

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

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

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

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

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

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

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

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

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

(20)

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

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

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

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

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

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

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

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

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

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

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

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

,

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

.

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

,

.

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

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

,

.

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

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

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

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

.

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

и , при .

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

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

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

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

, .

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

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

Некоторые идеи теории вейвлетов появились очень давно. Например, уже в 1910 году А.Хаар опубликовал полную ортонормальную систему базисных функций с локальной областью определения (теперь они называются вейвлетами Хаара). Первое упоминание о вейвлетах появилось в литературе по цифровой обработке и анализу сейсмических сигналов (работы А.Гроссмана и Ж.Морле).

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

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

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

Вейвлеты и многомасштабный анализ

Рассмотрим задачу, которая очень часто встречается на практике: у нас есть сигнал (а сигналом может быть все, что угодно, начиная от записи показаний датчика и кончая оцифрованной речью или изображением). Идея многомасштабного анализа (multiscale analysis, multiresolutional analysis) заключается в том, чтобы взглянуть на сигнал сначала вплотную – под микроскопом, затем через лупу, потом отойти на пару шагов, потом посмотреть издалека (рис.1).

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

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

Идея применения вейвлетов для многомасштабного анализа заключается в том, что разложение сигнала производится по базису, образованному сдвигами и разномасштабными копиями функции-прототипа (то есть вейвлет-преобразование по своей сути является фрактальным). Такие базисные функции называются вейвлетами (wavelet ), если они определены на пространстве L 2 (R) (пространство комплекснозначных функций f(t) на прямой с ограниченной энергией), колеблются вокруг оси абсцисс и быстро сходятся к нулю по мере увеличения абсолютного значения аргумента (рис.2).

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

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

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

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

Ортогональное вейвлет-преобразование

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

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

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

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

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

Дискретное вейвлет-преобразование и другие направления вейвлет-анализа

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

К счастью, И.Добеши удалось найти метод, позволяющий построить (бесконечную) серию ортогональных вейвлетов, каждый из которых определяется конечным числом коэффициентов. Стало возможным построить алгоритм, реализующий быстрое вейвлет-преобразование на дискретных данных (алгоритм Малла). Достоинство этого алгоритма, помимо всего вышесказанного, заключается в его простоте и высокой скорости: и на разложение, и на восстановление требуется порядка cN операций, где с – число коэффициентов, а N – длина выборки.

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

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

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

1. Обработка экспериментальных данных. Поскольку вейвлеты появились именно как механизм обработки экспериментальных данных, их применение для решения подобных задач представляется весьма привлекательным до сих пор. Вейвлет-преобразование дает наиболее наглядную и информативную картину результатов эксперимента, позволяет очистить исходные данные от шумов и случайных искажений, и даже "на глаз" подметить некоторые особенности данных и направление их дальнейшей обработки и анализа. Кроме того, вейвлеты хорошо подходят для анализа нестационарных сигналов, возникающих в медицине, анализе фондовых рынков и других областях.
2. Обработка изображений. Наше зрение устроено так, что мы сосредотачиваем свое внимание на существенных деталях изображения, отсекая ненужное. Используя вейвлет-преобразование, мы можем сгладить или выделить некоторые детали изображения, увеличить или уменьшить его, выделить важные детали и даже повысить его качество!
3. Сжатие данных. Особенностью ортогонального многомасштабного анализа является то, что для достаточно гладких данных полученные в результате преобразования детали в основном близки по величине к нулю и, следовательно, очень хорошо сжимаются обычными статистическими методами. Огромным достоинством вейвлет-преобразования является то, что оно не вносит дополнительной избыточности в исходные данные, и сигнал может быть полностью восстановлен с использованием тех же самых фильтров. Кроме того, отделение в результате преобразования деталей от основного сигнала позволяет очень просто реализовать сжатие с потерями – достаточно просто отбросить детали на тех масштабах, где они несущественны! Достаточно сказать, что изображение, обработанное вейвлетами, можно сжать в 3-10 раз без существенных потерь информации (а с допустимыми потерями – до 300 раз!). В качестве примера отметим, что вейвлет-преобразование положено в основу стандарта сжатия данных MPEG4.
4. Нейросети и другие механизмы анализа данных. Большие трудности при обучении нейросетей (или настройке других механизмов анализа данных) создает сильная зашумленность данных или наличие большого числа "особых случаев" (случайные выбросы, пропуски, нелинейные искажения и т.п.). Такие помехи способны скрывать характерные особенности данных или выдавать себя за них и могут сильно ухудшить результаты обучения. Поэтому рекомендуется очистить данные, прежде чем анализировать их. По уже приведенным выше соображениям, а также благодаря наличию быстрых и эффективных алгоритмов реализации, вейвлеты представляются весьма удобным и перспективным механизмом очистки и предварительной обработки данных для использования их в статистических и бизнес-приложениях, системах искусственного интеллекта и т.п.
5. Системы передачи данных и цифровой обработки сигналов. Благодаря высокой эффективности алгоритмов и устойчивости к воздействию помех, вейвлет-преобразование является мощным инструментом в тех областях, где традиционно использовались другие методы анализа данных, например, преобразование Фурье. Возможность применения уже существующих методов обработки результатов преобразования, а также характерные особенности поведения вейвлет-преобразования в частотно-временной области позволяют существенно расширить и дополнить возможности подобных систем.

И это еще далеко не все!

Заключение

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

Литература

1. Добеши И. Десять лекций по вейвлетам. Москва, "РХД", 2001 г.
2. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. С.-Петербург, ВУС, 1999 г.
3. Mallat S. A theory for multiresolutional signal decomposition: the wavelet representation. IEEE Trans. Pattern Analysis and Machine Intelligence, 1989, N7, p.674-693.

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

Что такое цифровое изображение

Визуальная информация в компьютере представляется в виде чисел. Говоря простым языком, фото, сделанное цифровым аппаратом, представляет собой таблицу, в ячейки которой вписаны значения цвета каждого из его пикселей. Если речь идет о монохромном изображении, то их заменяют значениями яркости из отрезка , где 0 используют для обозначения черного цвета, а 1 — белого. Остальные оттенки задаются дробными числами, но с ними неудобно работать, поэтому диапазон расширяют и значения выбирают из отрезка между 0 и 255. Почему именно из этого? Все просто! При таком выборе в двоичном представлении для кодирования яркости каждого пикселя требуется ровно 1 байт. Очевидно, что для хранения даже небольшого изображения требуется довольно много памяти. Например, фотография размером 256 х 256 пикселей займет 8 кБайт.

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

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

К с потерями относятся:

• JPEG. На данный момент это один из наиболее популярных алгоритмов. Он основан на применении дискретного косинусного преобразования. Справедливости ради нужно отметить, что существуют варианты JPEG, осуществляющие сжатие без потерь. К ним относятся Lossless JPEG и JPEG-LS.
• JPEG 2000. Алгоритм используется на мобильных платформах и основан на применении дискретного вейвлет-преобразования.
• Алгоритм фрактального сжатия. В некоторых случаях он позволяет получать изображения превосходного качества даже при сильном сжатии. Однако из-за проблем с патентованием этот метод продолжает оставаться экзотикой.

Без потерь сжатие осуществляют посредством алгоритмов:

• RLE (используется в качестве основного метода в форматах TIFF, BMP, TGA).
• LZW (применяется в формате GIF).
• LZ-Huffman (используется для формата PNG).

Преобразование Фурье

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

Оно выглядит так:

Формула обращения записывается следующим образом:

Что такое вейвлет

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

Спектрограммы Wavelet отличаются от обычных спектров Фурье, так как связывают спектр различных особенностей сигналов с их временной компонентой.

Вейвлет-преобразование

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

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

• Если для некой функции ψ (t) Фурье-преобразование имеет вид

то должно выполняться условие:

Кроме того:

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

Виды

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

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

Вайвлет Хаара

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

Сначала нужно вспомнить, что у фотографий яркость соседних пикселей, как правило, отличается на небольшую величину. Если даже на реальных изображениях присутствуют участки с резкими, контрастными перепадами яркости, то они занимают только малую часть изображения. В качестве примера возьмем всем известное тестовое изображение Lenna в градациях серого. Если взять матрицу яркости его пикселей, то часть первой строки будет выглядеть как последовательность чисел 154, 155, 156, 157, 157, 157, 158, 156.

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

В результате получится последовательность: 154,1,1,1,0,0,1,-2.

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

Для преодоления этого недостатка числа делят на пары и для каждой находят полусумму (об. a) и полуразность (об. d), т. е. для (154,155),(156,157),(157,157),(158,156) имеем (154.5,0.5),(156.5,0.5),(157,0.0),(157,-1.0). В таком случае в любой момент можно найти значение обоих чисел в паре.

В общем случае для дискретного вейвлет-преобразования сигнала S имеем:

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

Сжатие

Как уже было сказано, одной из сфер применения вейвлет-преобразования является алгоритм JPEG 2000. Сжатие с использованием метода Хаара основано на переводе вектора из двух пикселей X и Y в вектор (X + Y)/2 и (X - Y)/2. Для этого достаточно умножить исходный вектор на матрицу, представленную ниже.

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

Фильтры

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

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

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

Пример

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

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

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

Применение к двумерным массивам

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

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

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

Декодирование

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

• архив распаковывается;
• применяется обратное преобразование Хаара;
• декодированная матрица преобразуется в изображение.

Преимущества по сравнению с JPEG

При рассмотрении алгоритма Joint Photographic Experts Group было сказано, что он основан на ДКП. Такое преобразование осуществляется поблочно (8 х 8 пикселей). В результате, если сжатие сильное, то на восстановленном изображении становится заметной блочная структура. При сжатии с использованием вейвлетов такая проблема отсутствует. Однако могут появиться искажения другого типа, которые имеют вид ряби около резких границ. Считается, что подобные артефакты в среднем менее заметны, чем «квадратики», которые создаются при применении алгоритма JPEG.

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

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

Вначале опишем DWT в матричном виде, а затем – на основе банков фильтров, что наиболее часто используется при обработке сигналов.

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

1. Матричное описание dwt

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

. (2.52)

Обратное преобразование есть умножение
на обратную матрицу
:

. (2.53)

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

В четвертой и восьмой строках матрицы (2.51) последовательность циркулярно сдвинута: коэффициенты, выходящие за пределы матрицы справа, помещены в ту же строку слева. Это означает, чтоDWT есть точно один период длины N DTWS сигнала , получаемого путем бесконечного периодического продолжения. Так чтоDWT, будучи определенным таким образом, использует периодичность сигнала, как и в случае с DFT.

Матричное описание DWT кратко и ясно. Однако при обработке сигналов DWT чаще всего описывается посредством блок-диаграммы, аналогичной диаграмме системы анализа-синтеза (см. рис.1.1).

1. Описание dwt посредством блоков фильтров

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

Фильтры F и E означают фильтрацию фильтрами и
, соответственно. В нижней ветви схемы выполняется низкочастотная фильтрация. В результате получается некоторая аппроксимация сигнала, лишенная деталей низкочастотная (НЧ) субполоса. В верхней части схемы выделяется высокочастотная (ВЧ) субполоса. Отметим, что при обработке сигналов константа
всегда выносится из банка фильтров и сигнал домножается на 2 (см. рис.3.2, глава 3).

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

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

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

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

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

Как видно, вейвлет-преобразование на самом деле является бесконечным множеством различных преобразований в зависимости от оценочной функции, использованной для его расчёта. Это является основной причиной, почему термин «вейвлет-преобразование » используется в весьма различных ситуациях и для различных применений. Также существует множество типов классификации вариантов вейвлет-преобразования. Здесь мы покажем только деление, основанное на ортогональности вейвлетов. Можно использовать ортогональные вейвлеты для дискретного вейвлет-преобразования и неортогональные вейвлеты для непрерывного. Эти два вида преобразования обладают следующими свойствами:

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

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

В библиотеке обработки данных Gwyddion реализованы оба этих преобразования и использующие вейвлет-преобразование модули доступны в меню Обработка данных → Интегральные преобразования .

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

Дискретное вейвлет-преобразование (DWT) - реализация вейвлет-преобразования с использованием дискретного набора масштабов и переносов вейвлета, подчиняющихся некоторым определённым правилам. Другими словами, это преобразование раскладывает сигнал на взаимно ортогональный набор вейвлетов, что является основным отличием от непрерывного вейвлет-преобразования (CWT), или его реализации для дискретных временных рядов, иногда называемой непрерывным вейвлет-преобразованием дискретного времени (DT-CWT).

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

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

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

На следующем рисунке показаны некоторые масштабирующие функции и вейвлеты. Наиболее известным семейством ортонормированных вейвлетов явлется семейство Добеши. Её вейвлеты обычно обозначаются числом ненулевых коэффициентов a k , таким образом, мы обычно говорим о вейвлетах Добеши 4, Добеши 6, и т.п. Грубо говоря, с увеличением числа коэффициентов вейвлета функции становятся более гладкими. Это явно видно при сравнении вейвлетов Добеши 4 и 20, представленных ниже. Другой из упомянутых вейвлетов - простейший вейвлет Хаара, который использует прямоугольный импульс как масштабирующую функцию.

Функция масштабирования Хаара и вейвлет (слева) и их частотные составляющие (справа).

Функция масштабирования Добеши 4 и вейвлет (слева) и их частотные составляющие (справа).

Функция масштабирования Добеши 20 и вейвлет (слева) и их частотные составляющие (справа).

Существует несколько видов реализации алгоритма дискретного вейвлет-преобразования. Самый старый и наиболее известный – алгоритм Малла (пирамидальный). В этом алгоритме два фильтра – сглаживающий и несглаживающий составляются из коэффициентов вейвлета и эти фильтры рекуррентно применяются для получения данных для всех доступных масштабов. Если используется полный набор данных D = 2 N и длина сигнала равна L , сначала рассчитываются данные D /2 для масштаба L /2 N - 1 , затем данные (D /2)/2 для масштаба L /2 N - 2 , … пока в конце не получится 2 элемента данных для масштаба L /2 . Результатом работы этого алгоритма будет массив той же длины, что и входной, где данные обычно сортируются от наиболее крупных масштабов к наиболее мелким.

В Gwyddion для расчёта дискретного вейвлет-преобразования используется пирамидальный алгоритм. Дискретное вейвлет-преобразование в двумерном пространстве доступно в модуле DWT.

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

где Y ij соответствует всем коэффициентам наиболее высокого поддиапазона масштаба разложения (где, как предполагается, должна присутствовать большая часть шума). Или же дисперсия шума может быть получена независимым путём, например, как дисперсия сигнала АСМ, когда сканирование не идёт. Для наиболее высокого поддиапазона частот (универсальный порог) или для каждого поддиапазона (для адаптивного по масштабу порога) или для окружения каждого пикселя в поддиапазоне (для адаптивного по масштабу и пространству порога) дисперсия рассчитывается как

Значение порога считается в конечном виде как

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

Удаление шума DWT доступно в меню Обработка данных → Интегральные преобразования → Удаление шума DWT .

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

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

В принципеЮ непрерывное вейвлет-преобразование работает используя напрямую определение вейвлет-преобразования, т.е. мы рассчитываем свёртку сигнала с масштабированным вейвлетом. Для каждого масштаба мы получаем этим способом набор той же длины N , что и входной сигнал. Используя M произвольно выбранных масштабов мы получаем поле N×M , которое напрямую представляет плоскость время-частота. Алгоритм, используемый для этого расчёта может быть основан на прямой свёртке или на свёртке посредством умножения в Фурье-пространстве (это иногда называется быстрым вейвлет-преобразованием).

Выбор вейвлета для использования в разложении на время-частоту является наиболее важной вещью. Этим выбором мы можем влиять на разрешение результата по времени и по частоте.Нельзя изменить этим путём основные характеристики вейвлет-преобразования (низкие частоты имеют хорошее разрешение по частотам и плохое по времени; высокие имеют плохое разрешение по частотам и хорошее по времени), но можно несколько увеличить общее разрешение по частотам или по времени. Это напрямую пропорционально ширине используемого вейвлета в реальном и Фурье-пространстве. Если, например, использовать вейвлет Морле (реальная часть – затухающая функция косинуса), то можно ожидать высокого разрешения по частотам, поскольку такой вейвлет очень хорошо локализован по частоте. наоборот, используя вейвлет Производная Гауссиана (DOG) мы получим хорошую локализацию по времени, но плохую по частоте.

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

Источники

A. Bultheel: Bull. Belg. Math. Soc.: (1995) 2

S. G. Chang, B. Yu, M. Vetterli: IEEE Trans. Image Processing, (2000) 9 p. 1532

S. G. Chang, B. Yu, M. Vetterli: IEEE Trans. Image Processing, (2000) 9 p. 1522