Введение

Трансформация в численном гармоническом анализе

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

Волновые волоски

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

Даубечи

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

Комплексная волновая трансформация двойного дерева (DCWT)

Двойной деревосложный волновой трансформатор (WT) — относительно недавнее усовершенствование дискретного волнового трансформатора (DWT), обладающее важными дополнительными свойствами: он почти нечувствителен к сдвигу и обладает направленной избирательностью в двух и более измерениях. Это достигается при коэффициенте избыточности, равном лишь , что существенно ниже, чем у недецимированного DWT. Многомерный (M D) двойной деревосложный WT является неразделимым, но основан на вычислительно эффективном разделимом фильтровом банке (FB).

Другие

Другие формы дискретного вейвлет-преобразования включают вейвлет Le Gall–Tabatabai (LGT) 5/3, разработанный Дидье Ле Галлом и Али Дж. Табатабай в 1988 году (используется в JPEG 2000 или JPEG XS), биномиальный QMF, разработанный Али Начи Акансу в 1990 году, алгоритм SPIHT (set partitioning in hierarchical trees), разработанный Амиром Саидом и Уильямом А. Перлманом в 1996 году, не- или недецимированное вейвлет-преобразование (где исключается понижающая дискретизация), и преобразование Ньюленда (где ортонормальный базис вейвлетов формируется из специально сконструированных фильтров "верхней шляпы" в частотной области). Вейвлет-пакетные преобразования также связаны с дискретным вейвлет-преобразованием. Комплексное вейвлет-преобразование является еще одной формой.

Свойства

Haar DWT иллюстрирует желаемые свойства вейвлетов в целом. Во-первых, она может быть выполнена за конечное число операций; во-вторых, она позволяет оценить не только частотный состав входных данных, анализируя их в различных масштабах, но и временной состав, то есть моменты времени, когда эти частоты возникают. Сочетание этих двух свойств делает быстрое вейвлет-преобразование (FWT) альтернативой традиционному быстрому преобразованию Фурье (FFT).

Проблемы времени

Благодаря изменению скорости работы операторов в фильтр-банке, дискретное вейвлет-преобразование (WT) не является инвариантным ко времени, но при этом очень чувствительно к временному выравниванию сигнала. Для решения проблемы изменчивости вейвлет-преобразований во времени, Маллат и Чжун предложили новый алгоритм вейвлет-представления сигнала, инвариантный к сдвигам во времени. В соответствии с этим алгоритмом, который называется TI DWT, дискретизация производится только по параметру масштаба вдоль диадической последовательности 2^j (j∈Z), а вейвлет-преобразование вычисляется для каждой точки времени.

Приложения

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

Отношение к материнской волной

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

Временная сложность

Реализация фильтра банка дискретной волновой трансформации требует лишь O(N) в определенных случаях, по сравнению с O(N log N) для быстрого преобразования Фурье. Следует отметить, что если и являются фильтрами постоянной длины (то есть их длина не зависит от N), то каждый из них требует O(N) времени. Фильтр банк волновых фильтров выполняет каждую из этих двух сверток со сложностью O(N), затем разделяет сигнал на две ветви размером N/2. Однако он рекурсивно разделяет только верхнюю ветвь, свернутую с (в отличие от FFT, которая рекурсивно разделяет как верхнюю, так и нижнюю ветви). Это приводит к следующему соотношению рекуррентности:

которое приводит к временной сложности O(N) для всей операции, что можно показать, разложив данное соотношение в геометрическую прогрессию. Например, дискретное преобразование Хаара является линейным, поскольку в этом случае и имеют постоянную длину 2. Локальность вейвлетов в сочетании со сложностью O(N) гарантирует, что преобразование может быть вычислено в режиме реального времени (потоковым способом). Это свойство резко контрастирует с FFT, для которой требуется доступ ко всему сигналу сразу. Оно также применимо к многомасштабному преобразованию и к многомерным преобразованиям (например, 2D DWT).

Другие преобразования

Алгоритм Adam7, используемый для чередования строк в формате Portable Network Graphics (PNG), представляет собой многомасштабную модель данных, аналогичную DWT с вейвлетами Хаара. В отличие от DWT, он имеет фиксированный масштаб – он начинается с блока 8×8 и уменьшает разрешение изображения, а не выполняет понижающую дискретизацию (фильтрацию нижних частот с последующим уменьшением разрешения). Это приводит к ухудшению частотных характеристик, проявляющемуся в артефактах (пикселизации) на ранних этапах, но упрощает реализацию. Мультипликативная (или геометрическая) дискретная вейвлет-трансформация – это вариант, применяемый к модели наблюдения, включающей взаимодействие положительной регулярной функции и мультипликативного независимого положительного шума, обозначим вейвлет-трансформацию как . Поскольку , то стандартная (аддитивная) дискретная вейвлет-трансформация имеет вид , где коэффициенты деталей, как правило, нельзя считать разреженными из-за вклада в последнее выражение. В мультипликативной модели вейвлет-трансформация имеет вид . Такое "встраивание" вейвлетов в мультипликативную алгебру включает обобщенные мультипликативные аппроксимации и операторы деталей: например, в случае вейвлетов Хаара, то до коэффициента нормализации, стандартные аппроксимации (арифметическое среднее) и детали (арифметические разности) становятся, соответственно, геометрическими средними аппроксимациями и геометрическими разностями (деталями) при использовании .

Пример вышеуказанного кода

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

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