Энергетический спектр непрерывного вейвлет преобразования. Основы теории вейвлет-преобразования

Вейвлеты (от англ. 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.

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

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

Требования к вейвлетам

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

1. Вейвлет должен обладать конечной энергией:

2. Если фурье-преобразование для, то есть

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

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

3. Дополнительный критерий предъявляется для комплексных вейвлетов, а именно, что для них Фурье-преобразование должно быть одновременно вещественным и должно убывать для отрицательных частот.

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

1. Линейность

2. Инвариантность относительно сдвига

Сдвиг сигнала во времени на t0 приводит к сдвигу вейвлет-спектра также на t0.

3. Инвариантность относительно масштабирования

Растяжение (сжатие) сигнала приводит к сжатию (растяжению) вейвлет-спектра сигнала.

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

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

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

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

Весовая функция.

Мы можем определить нормированную функцию следующим образом

что означает временной сдвиг на b и масштабирование по времени на a. Тогда формула вейлет-преобразования изменится на

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

В дискретном случае, параметры масштабирования a и сдвига b представлены дискретными величинами:

Тогда анализирующий вейвлет имеет следующий вид:

где m и n - целые числа.

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

Величины также известны как вейвлет-коэффициенты.

есть постоянная нормировки.

Некоторые идеи теории вейвлетов появились очень давно. Например, уже в 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.

12.3 Алгоритм дискретного вейвлет-преобразования

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

,

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

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

Иначе говоря, рекурсивно данный алгоритм выглядит следующим образом:

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

Отметим, рекурсии (12.12), (12.13) могут см успехом применяться к расчету коэффициентов аппроксимации и детализации также для случаев : дело в том, что дополненные последовательности являются периодическими, причем

,

.

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

,

и продолжается до восстановления вектора , пока не станет . Рекурсивное выражение для восстановления данных в этом случае имеет вид:

12.4 Статистический дискретный вейвлет-анализ

Разбиение данных

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

Процедуры деления данных на интервалы для оценивания плотности и регрессионного анализа введены в параграфах 10.2, 10.8 соответственно. В данном месте обсуждается эффект, вносимый подобным разбиением на качество синтезируемых оценок. Примеры, используемые для обсуждения эффекта, взяты из гл. 10, рис. 10.1 - 10.11.

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

Таблица 12.1

Интегральные среднеквадратические ошибки

для интервалов разбиения различной длины

Как видно из таблицы, интегральная СКО достигает своего минимума при . График данной ошибки показан на рис. 12.1.

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

Приближенное построение вейвлет-оценок

Алгоритм реализации дискретного вейвлет-преобразования для целей построения статистических оценок (12.6) - (12.8) выглядит следующим образом:

Интегральная СКО, построенная для симмлета S8

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

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

.

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

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

Пусть оператор обозначает процедуру трешолдинга вектора :

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

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

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

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

.

(12.18)

Известно, что рекурсии (12.9), (12.10) позволяют рассчитать оценки коэффициентов , тогда как выражения рекурсии (12.12), (12.13) - примерно те же коэффициенты в предположении, что исходные данные для рекурсии абсолютно те же. Однако в том случае, если требование (12.18) выполняется, исходные данные для (12.12), (12.13) в действии 3 алгоритма становятся отличными от аналогичных им данных обратной рекурсии (12.9), (12.10) на некоторый множитель . Следовательно, линейность алгоритма влечет за собой необходимость введения в прямое преобразование поправку:

,

.

Более того, поправке подвергается основное выражение для прямого преобразования:

причем оператор приобретает вид:

Объединяя выражения (12.17) и (12.19), можно записать, что теперь

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

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

Визуальная информация в компьютере представляется в виде чисел. Говоря простым языком, фото, сделанное цифровым аппаратом, представляет собой таблицу, в ячейки которой вписаны значения цвета каждого из его пикселей. Если речь идет о монохромном изображении, то их заменяют значениями яркости из отрезка , где 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.

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