Какие частотно-временные коэффициенты вычисляет вейвлет-преобразование?

Быстрое преобразование Фурье принимает операций, в то время как быстрого вейвлет - преобразование принимает . Но что конкретно FWT вычисляет?O ( N $\mathcal O(N \log N)$$\mathcal O(N)$

Хотя их часто сравнивают, кажется, что FFT и FWT - это яблоки и апельсины. Насколько я понимаю, было бы более уместно сравнивать STFT (FFT небольших кусков во времени) со сложным Morlet WT , так как они являются частотно-временными представлениями, основанными на сложных синусоидах (пожалуйста, исправьте меня, если я ошибаюсь ). Это часто показано на следующей диаграмме:

( Еще один пример )

Слева показано, как STFT представляет собой набор FFT, сложенных друг на друге с течением времени (это представление является источником спектрограммы ), а справа - диадический WT, который имеет лучшее временное разрешение на высоких частотах и ​​лучшую частоту разрешение на низких частотах (это представление называется скалограммой ). В этом примере для STFT - это число вертикальных столбцов (6), и одна операция FFT вычисляет одну строку из коэффициентов из выборок. Всего 8 БПФ по 6 точек в каждом, или 48 выборок во временной области.O ( N log N ) N $N$$\mathcal O(N \log N)$$N$$N$

Что я не понимаю:

• Сколько коэффициентов вычисляет одна операция FWT и где они расположены на частотно-временной диаграмме выше? $\mathcal O(N)$

• Какие прямоугольники заполняются одним вычислением?

• Если мы вычислим блок частотно-временных коэффициентов равной площади, используя оба, получим ли мы одинаковое количество данных?

• FWT все еще более эффективен, чем FFT?

Конкретный пример с использованием PyWavelets :

In [2]: dwt([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[2]:
(array([ 0.70710678,  0.        ,  0.        ,  0.        ]),
 array([ 0.70710678,  0.        ,  0.        ,  0.        ]))

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

Обновить:

На самом деле, я, вероятно, делал это неправильно, и должен был использовать wavedec(), который выполняет многоуровневую декомпозицию DWT:

In [4]: wavedec([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[4]: 
[array([ 0.35355339]),
 array([ 0.35355339]),
 array([ 0.5,  0. ]),
 array([ 0.70710678,  0.        ,  0.        ,  0.        ])]

Вы правы в том, что FWT лучше считать «двоюродным братом» STFT, а не FT. Фактически, FWT - это просто дискретная выборка CWT (непрерывного вейвлет-преобразования), так как FFT / DFT - это дискретная выборка преобразования Фурье. Это может показаться тонким моментом, но это важно при выборе способа дискретизации преобразования.

CWT и STFT являются избыточными анализами сигнала. Другими словами, у вас больше «коэффициентов» (в дискретном случае), чем нужно для полного представления сигнала. Однако преобразование Фурье (или, скажем, вейвлет-преобразование, использующее только одну шкалу) интегрирует сигнал от -infinity до + infinity. Это не очень полезно для сигналов реального мира, поэтому мы усекаем (то есть окно) преобразования до более коротких длин. Работа с окном сигнала изменяет преобразование - вы умножаете на окно во времени / пространстве, поэтому в пространстве преобразования вы получаете свертку преобразования окна с преобразованием сигнала.

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

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

То, как вы дискретизируете CWT, зависит от вас, хотя я думаю, что есть минимальные выборки как в сдвиге, так и в масштабе, чтобы полностью представить сигнал. Как правило (по крайней мере, как я их использовал), для самой низкой шкалы (самая высокая частота) вы будете пробовать во всех местах смены (время / пространство). По мере увеличения масштаба (снижения частоты) вы можете делать выборки реже. Обоснование состоит в том, что низкие частоты не меняются так быстро (вспомните о крушении тарелки или бас-гитаре - у крена тарелки очень короткие переходные процессы, тогда как для изменения басовой гитары потребуется больше времени). На самом деле, в кратчайшем масштабе (при условии, что вы производите выборку во всех местах сдвига), у вас есть полное представление сигнала (вы можете восстановить его, используя только коэффициенты в этом масштабе). Я не уверен в обоснованности выборки из шкалы. Я' мы посчитали это предполагаемым логарифмическим, с (я думаю) более близким интервалом между более короткими шкалами. Я думаю, это потому, что вейвлеты в более длинных масштабах имеют более широкое преобразование Фурье (поэтому они «улавливают» больше частот).

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

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

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

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

Ваша ссылка имеет это:

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

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

• Вейвлеты имеют местоположение - вейвлет (1,1, –1, –1) соответствует «левой стороне» по сравнению с «правой стороной», в то время как последние два вейвлета имеют поддержку на левой или правой стороне, и один является переводом другого.
• Синусоидальные волны не имеют местоположения - они распространяются по всему пространству - но имеют фазу - вторая и третья волны являются сдвигами друг друга, что соответствует отклонению фазы на 90 °, как косинус и синус, из которых они являются дискретными версиями ,

Если вместо дискретных вейвлетов вы хотите использовать непрерывные вейвлеты или сложные вейвлеты, вы можете начать с вейвлет-серий .

Помимо Википедии, учебник и курс могут помочь вам.

$O(N^2)$

$O(N)$$O(N\log(N))$$O(\cdot)$

Начните с общего оконного STFT (непрерывная форма). Если вы подключите бесконечное окно высоты блока, вы восстановите преобразование Фурье как особый случай. Который вы можете дискретизировать (и получить ДПФ) и сделать это быстро (и получить БПФ).

Начните с CWT (непрерывная форма). Непрерывный CWT допускает невероятное количество потенциальных вейвлет-форм. Они могут быть дискретизированы точно только с образцами выборки (по времени или шкале), которые учитывают некоторое неравенство «Гейзенберга»: один образец на единицу поверхности. Эти шаблоны зависят от вейвлета. В большинстве случаев шаблоны создают дискретный CWT, который является избыточным, и дает вейвлет-кадр.

Некоторые хотели, чтобы это не было лишним, с диадической шкалой (DWT). Только очень немногие вейвлеты (все еще бесконечное число, но вы не можете найти их случайно) позволяют это. Среди первых были вейвлеты Хаара, Франклина и Мейера. Если вы затем навязываете поддержку вейвлетов как конечную, то Хаар долгое время был единственным. Практически невозможно получить ортогональный вейвлет из «естественных непрерывных вейвлетов», поэтому были построены те , что были у Добеши , а затем у Симмлета и Коифлета . Эти вейвлеты странной формы не имеют хороших и простых формул, таких как вейвлет Морле.

$O(N)$

На самом деле, FWT - это просто дискретная выборка CWT.

DWT (или FWT) является точным, как DFT / FFT. Большинство других дискретных CWT (с любым вейвлетом) примерно такие (без особого вреда, если у вас есть достаточная избыточность).

Так:

• $k$$k$$k$$8$$0$$4T$$2\times 4$$2$$4$$[\omega/2,\omega]$$4$$2\times2$$2$$[\omega/8,\omega/4]$$[1,1,2,4]$
• $k$
• $+$$\times$$O(N)$

Следующие фотографии показывают, как непрерывная версия вейвлета Хаара

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

Обратите внимание, что некоторые дискретные вейвлеты, особенно длинные (например, сплайны), иногда вычисляются с использованием БПФ :)