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

26

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

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

Сетки, показывающие, как коэффициенты БПФ и WT соответствуют частотно-временной плоскости

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

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

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

  • Сколько коэффициентов вычисляет одна операция FWT и где они расположены на частотно-временной диаграмме выше? 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.        ])]
эндолиты
источник
2
Чтобы лучше понять, как работает эта вейвлет-декомпозиция, один полезный инструмент должен был бы быть в состоянии сделать это на реальных сигналах: например, на аудиосигнале (у меня есть вопрос в этом направлении здесь dsp.stackexchange.com/ questions / 12694 / stft-and-dwt-wavelets )
Basj
@endolith Ваш вопрос все еще запрашивается? Если так, я могу добавить другие подсказки
Лоран Дюваль
@ LaurentDuval Да, это все еще открыто, и я все еще не понимаю. Я могу быть смущен, потому что CWT использует такие вещи, как Morlet, а DWT использует только такие вещи, как Haar или Daubechies. Я не уверен, что быстрый FWT - это только Хаар, или он также может использовать другие типы вейвлетов.
эндолит
2
@ndolith Просто комментарий к этому: непрерывный CWT допускает невероятное количество потенциальных форм вейвлета. Они могут быть дискретизированы точно только с образцами выборки (по времени или шкале), которые учитывают некоторое неравенство «Гейзенберга». Эти шаблоны зависят от вейвлета. В большинстве случаев шаблоны создают дискретный CWT, который является избыточным. Некоторые хотят, чтобы это не было лишним, с диадической шкалой. Только очень немногие вейвлеты позволяют это. Если вы затем навязываете поддержку вейвлетов как конечную, то Хаар - один, почти невозможно получить w / «естественные вейвлеты», именно поэтому были построены те, что были у Добеши
Лоран Дюваль

Ответы:

13

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

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

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

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

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

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

Патрик
источник
1
«на самом деле это минимальная выборка в смещении / масштабе, а не избыточное представление». Ах! Я думаю, что вы правы, и это объясняет, почему его всегда сравнивают с БПФ, который также является минимальным представлением.
эндолит
3
FWT является критической выборкой CWT. Я все еще пытаюсь понять это лучше, но я узнал, что STFT и CWT оба являются фреймами. Теория фреймов выходит за рамки моего понимания, но одним интересным понятием является формула неопределенности: для STFT dw * dt> C (dw - разрешение по частоте, а dt - разрешение по времени). Другими словами, когда вы пытаетесь лучше разрешить частоту, вы теряете временное разрешение. CWT не имеет этого ограничения. Я буду продолжать читать и попытаюсь уточнить мой ответ выше, как только уясню его в своей голове.
1
Из того, что я понимаю, CWT имеет то же ограничение, но использует лучший компромисс.
эндолит
1
«STFT - это избыточные анализы сигнала». Я не думаю, что это правда. Если у вас есть 100-точечный сигнал, разделите его на порции по 10 точек, а затем сделайте БПФ с 10 точками для каждого, у вас останется та же информация, хранящаяся в том же количестве сэмплов.
эндолит
11

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

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

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


источник
Да, я понимаю локализацию коэффициентов. Это так же, как БПФ. Когда вы говорите «должен придерживаться», что вы имеете в виду? Это только требование, если вы пытаетесь получить минимальное / не избыточное представление сигнала? Что если вы просто пытаетесь проанализировать / визуализировать это? Я добавлю более конкретный пример к вопросу.
эндолит
1
Соблюдение критерия допустимости гарантирует, что разрешение идентичности существует, то есть что все сигналы могут быть восстановлены из их вейвлет-преобразований. Если вы не придерживаетесь его, то вы не можете восстановить сигнал из его преобразования, и в этот момент вы должны спросить, что именно вы анализируете (отражает ли это какую-либо информацию, которая была в сигнале ?!). Если вам не требуется минимальное / не избыточное представление, вы можете использовать более слабый критерий допустимости из CWT (который позволяет вам определять более «идеальные» вейвлеты).
1
Я думаю, что вы сочтете мою диссертацию действительно полезной. Я сделаю это для вас ...
Вы поместили это онлайн? :)
эндолит
2
Я уверен, что сделал: flyingfrogblog.blogspot.com/2010/02/…
3

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

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

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

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

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

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


источник
Я не понимаю этот ответ. Это отвечает на мои вопросы? Левая сторона и правая сторона чего? Какое это имеет отношение к частотно-временному представлению?
эндолит
Описание «левая сторона - правая сторона» - это предварительный просмотр страницы DWT, показывающий, что эта страница содержит простой пример, объясняющий относительные достоинства синусоидальной основы и основы вейвлетов Хаара. Вы спрашивали о природе коэффициентов в вейвлет-преобразовании. Похоже, вы искали интуицию. Я думал, что вы могли бы найти этот пример (в его первоначальном контексте) полезным.
Да, я прочитал статьи Википедии несколько раз, прежде чем опубликовать этот вопрос. Я не знаю, если / как ваш ответ связан с моим вопросом о частотно-временном представлении. Если да, не могли бы вы соединить точки? БПФ из n выборок даст n коэффициентов, которые составляют один столбец спектрограммы STFT. Есть ли соответствующая связь между коэффициентами, производимыми WT и скалограммой? Если так, то, что это? Какие из полей в нижнем правом графике заполнены одним проходом через FWT?
Эндолит
1
Почти все на страницах Википедии, связанных с вейвлетами, в настоящее время неверно.
3

O(N2)

O(N)O(Nlog(N))O()

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

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

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

O(N)

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

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

Так:

  • kkk804T2×424[ω/2,ω]42×22[ω/8,ω/4][1,1,2,4]
  • k
  • +×O(N)

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

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

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

Лоран Дюваль
источник