Непрерывное wavelet преобразование

    Здравствуйте, уважаемое хабрасообщество.
    В последнее время на хабре стали появляться статьи, так или иначе связанные с анализом и обработкой сигналов и изображений (например Обнаружение устойчивых признаков изображения: метод SURF, Интегральное представление изображений от BigObfuscator), в связи с чем я хотел бы вкратце осветить такой инструмент для анализа сигналов, как wavelet-преобразование.

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

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

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

    Главной математической основой спектрального анализа является преобразование Фурье, которое связывает пространственный или временной сигнал (либо некоторую модель этого сигнала) с его представлением в частотной области.
    Преобразование Фурье функции f является интегральным представлением и задается следующей формулой:
    image
    Но преобразование Фурье дает информацию только про частоту, которая присутствует в сигнале и не дает никакой информации про то, в какой промежуток времени эта частота присутствует в сигнале.
    Таким образом для следующего стационарного сигнала:
    image
    image
    преобразование Фурье будет иметь вид:
    image

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

    Оконное преобразование Фурье

    Другим инструментом спектрального анализа является оконное преобразование Фурье (Short-time Fourier transform), которое является разновидностью преобразования Фурье и определяется следующим образом:
    image
    где W(Tau-t) — некоторая оконная функция.
    Обычно в качестве оконной функции используется гауссиан, окно Хемминга, окно Ханна или окно Кайзера.

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

    Рассмотрим следующий не стационарный сигнал:
    image
    Этот сигнал является стационарный каждые 250мс (на первом отрезке длинной 250мс он имеет частоту 300Гц, на втором — 200Гц, на третьем — 100Гц и на четвертом — 50Гц).
    Трехмерный (время, частота и амплитуда) график оконного преобразования Фурье будет иметь следующий вид:
    image
    (симметричность графика объясняется тем, что преобразования Фурье (в том числе и оконное преобразования Фурье) являются симметричными для любого сигнала)
    На этом графике мы можем увидеть четыре ярко выраженных максимума, которые соответствуют частотам, присутствующим в сигнале. Самым важным является то, что в отличии от обычного преобразования Фурье мы получаем значения частот относительно оси времени, то есть получаем частотно-временную характеристику сигнала.
    Но главной проблемой в использовании оконного преобразования Фурье для получения частотно-временной характеристики сигнала является так называемый принцип неопределенности Гейзенберга, который возникает для параметров времени и частоты сигнала.
    В основе принципа неопределенности лежит тот факт, что невозможно сказать точно какая частота присутствует в сигнале в данный момент времени (можно говорить только про диапазон частот) и не возможно сказать в какой точно момент времени частота присутствует в сигнале (можно говорить лишь про период времени).
    В связи с этим возникает проблема разрешающей способности. Разрешающую способность оконного преобразования Фурье можно регулировать с помощью ширины окна.
    Оконное преобразования Фурье с узким окном в форме Гауссиана с масштабом (обратная величина к ширине окна) 0.01 будет иметь следующий вид:
    image
    Как видно, полученное преобразование Фурье имеет хорошую точность относительно времени и плохую точностью относительно частоты (каждый максимум занимает некоторый диапазон частот).

    При использовании более широкого окна в форме Гаусианна с масштабом 0.00001 оконное преобразование будет иметь вид:
    image
    Видно, что в данном случае мы получаем высокую точность относительно частоты, но при этом очень низкую точность относительно времени.

    Можно считать, что обычное преобразование Фурье является оконным преобразованием Фурье с окном шириной в бесконечность.
    Таким образом при увеличении ширины окна (уменьшении его разрешающей способности) мы увеличиваем точность относительно частоты и уменьшаем точность относительно времени.
    Какое тогда подобрать значение ширины окна, чтобы добиться оптимального соотношения точностей? На этот вопрос отвечает вейвлет-преобразование.

    Wavelet-преобразование

    Вейвлет преобразование было создано как инструмент, который решает проблему неопределенности Гейзенберга для построение частотно-временных характеристик сигнала.
    Вейвлет преобразование сигнала f(t) имеет вид:
    image
    где Tau — сдвиг по времени, S — масштаб, а Psi* — материнский вейвлет.

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

    Опишем процесс вейвлет преобразования (в качестве материнского вейвлета используется гауиссиан) некоторого непрерывного сигнала, который действовал на протяжении некоторого промежутка времени (0-200мс) с нормализованной амплитудой (0-1):
    1. Рассчитывается интеграл при начальных условиях Tau=0 и S=1;
    а) увеличивается параметр Tau(i) =Tau(i-1)+e на некоторое достаточно малое число e и рассчитывается интеграл. Выполняется пока Tau(i) не станет равным 200мс (концу сигнала).
    image
    2. Изменяется параметр S=5, значение Tau опять устанавливается в начальную точку сигнала (Tau=0);
    а) увеличивается параметр Tau(i)=Tau(i-1)+e на некоторое достаточно малое число е и рассчитывается интеграл. Выполняется пока Tau(i) не станет равным 200мс (концу сигнала).
    image
    Аналогично рассчитываются интегралы для значений параметра S=20, S=50 и т.д.
    В результате описанного процесса мы получаем рассчитанные значения интегралов функции для каждого масштаба в каждый момент времени.
    Таким образом мы получаем трехмерное представление сигнала с компонентами: масштаб, время и амплитуда (значения рассчитанных интегралов).

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

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

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

    Использованная литература: Wavelet-tutorial
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 55

      +7
      Как-то вы сразу с места в карьер. Можно было бы объяснить, зачем вообще нужно спектральное оценивание, где применяется вейвлет-анализ, и т. д. и т. п. А самое главное, что же такое этот стационарный сигнал, о котором вы столько говорите? =)
        +2
        Вот ровно те же мысли возникли при чтении — интересно, но не понятно ничего.

        И главный вопрос, который меня мучает — а где это все применяется-то вообще и как связано с тематикой Хабра?

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

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

          В дальнейшем я собираюсь написать топик про дискретное вейвлет преобразование, где применимость станет более понятной. А сейчас же — это ответ на вопрос «что же такое вейвлет преобразование с математической точки зрения».
            0
            А на JS готовых библиотек нет?
            Вообще, каким классом софта (сервисов, фреймворков, шаблонов, библиотек скриптов) это может описываться?
            Было бы здорово, если рядом были бы фрагменты реализации (или ссылки на наиболее удачные примеры).

            Спасибо.
        0
        Стационарным сигналом называют сигнал, который не изменяется во времени. А все это в целом автор скорее всего применял для задач по сжатию информации, которой присуще наличие сигналов. К примеру, фото-, видео- и аудио- контент.
          +1
          Сигнал, который не изменяется во времени называют постоянным. Стационарный, если я не ничего путаю, не меняет закона распределения. Вообще, стационарность есть в узком и широком смысле, но это не важно.
            0
            *неважно
            +1
            Не нужно путать распределения и сигналы.

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

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

            «Плюс, представления ни о частоте, ни о времени вейвлетный спектр дать не может, он вообще, формально, не имеет физической интерпретации. „
            Это Вы с чего взяли?
              0
              Амплитуда ладно, просто перекликается с амплитудой _сигнала_, которую дает FFT/WFFT.
              Потому что там именно сдвиг и масштаб, частоты и времени там нет. Понятно, что чем ниже масштаб, тем выше частота, но численно одно в другое не переводится. Про интерепретацию — прямым текстом написано во вступительной главе в справке к Wavelet toolbox.
            +1
            У преобразования Фурье есть два свойства — оно дает фазу сигнала, и оно обратимо.
            А как с этим у вейвлет-преобразований?

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

            Ну и хотелось бы ссылки на дальнейшее чтение — где применяются вейвлеты и что они дают по сравнению с Фурье.
              0
              Обратимо.
              С Фурье не соотносится никак.
              Сильно применяется в lossy сжатии, главным образом из-за того, что может разделять информативные компоненты и высокочастотный шум.
              Чтение можно начинать с википедии, потом — любые книги по обработке сигналов. Можно поставить на пробу MatLab, лучше его Wavelet Toolbox для обучения нет.
                +1
                С Фурье соотносится так, что оба они--это разложение объекта гильбертова пространства по векторам гильбертова пространства. Как-то так.
                  +1
                  Даже более того. Поскольку вейвлет-преобразование обратимо, то система функций этого пробразования полная. А в общем случае преобразование Фурье--это разложение произвольного объекта гильбертова пространства на полную систему функций этого пространства через скалярное произведение на этом пространстве (в нашем случае скалярное произведение--это интегрирование; например, по функциям Бесселя можно раскладывать так же--через интеграл). Так что вейвлет-преобразование можно считать частным случаем общего преобразования Фурье.
                    0
                    Преобразование Фурье — это вейвлет преобразование с шириной вейвлета в бесконечность (как и в случае оконного преобразования Фурье).
                +1
                Для продолжения рекомендую Чуи — Введение в вэйвлеты, а так же есть можно сказать библия С.Малла Вэйвлеты в обработке сигналов.
                Я вейвлетами уже давно занимался, но насколько помню в отличие от Фурье, там локализация лучше на временном пространстве.
                0
                у меня есть задача — установить/распознать наличие ультразвука.

                мне для этого нужны вейвлеты или подходит фурье?
                  +1
                  если не нужно устанавливать в какой именно временной отрезок они присутствовали в сигнале — то справится Фурье
                    0
                    фурье будет полностью достаточно.
                      0
                      Достаточно линейного hipass фильтра — несколько сложений и умножений.
                      Вопрос в том, чем вы будете этот звук снимать, у звуковухи, например, должна быть соответствующая двойной частоте ультразвука частота дискретизации (хотя не обязательно — за счет алиасинга можно верить и высокие частоты)и отсутствие фильтра на 24000 кГц на АЦП. Вот со вторым проблемы, на всех стоят фильтры, чтобы не было пресловутого алиасинга…
                        0
                        а если усложнить задачу — снимать нужно не на компе, а с телефона. конкретно — iPhone :)
                        На западе есть работающий аналог. Точнее, 99%, что там программа работает через ультразвук. Но 100% гарантии нет, и я не знаю на какой частоте это происходит :)

                        Если интересно, могу в личку подробнее информации скинуть
                          +2
                          При частоте дискретизации 44100 кГц максимальная частота, которую можно оцифровать — 22050. Это как раз предел слышимости уха, дети могут и 24000 слышать, а какие-нибудь горняки — не выше 14000, но средний человек считается, что слышит в районе двадцати двух.
                          Некоторые аудиокарты могут оцифровывать с частотой 96 кГц или даже 192 кГц. Эти карты, теоретически, могут записывать и ультразвук. Но на айфоне, насколько я знаю, такие частоты дискретизации не доступны.
                          Если в прграмме называют ультразвуком писк в райное 18000-24000 кГц, то, записать можно. Для проверки нужно взять какое-нибудь средство записи для айфона, и посмотреть записанный wav-файл спектроанализатором на компьютере (тем же adobe audition, или чем-то бесплатным) Если нужный писк на нем видно, то можно писать несложную программу, реализующую соответствующий фильтр. Главное знать параметры звука.
                            0
                            Если в прграмме называют ультразвуком писк в райное 18000-24000 кГц,

                            «эксперты» писк не наблюдали

                            Для проверки нужно взять какое-нибудь средство записи для айфона, и посмотреть записанный wav-файл спектроанализатором на компьютере (тем же adobe audition, или чем-то бесплатным)

                            генератора ещё нет :)

                            я вот в том же cooledit pro генерировал звуки на 14000, 15000, у меня мозг чуть не взорвался :)
                              0
                              Я думал у вас есть западный аналог. Пишите в личку, чем смогу, помогу. DSP мое хобби на пересечении программирования и музыкописания.
                          0
                          а зачем в звуковуху такие фильтра ставят?
                            0
                            по тому что это мусор, человек его не слышит, а информации обрабатывать над больше
                              0
                              Что самое интересно — хоть человек их и не слышит, но это не означает, что он их не ощущает (как и инфразвук). Потому профессионалы работают с 96кГц и выше, так как все эти «неслышимые частоты» очень даже нужны и важны в музыке.
                                0
                                вот именно, жаль, что их и воспросизводит только специальное оборудование.
                                  0
                                  Не стоит забывать про концертные залы ;)
                                  Видимо именно поэтому живая музыка до сих пор в цене!
                                  0
                                  Профессионалы работают в 96 кГц по той же причине, по которой в расчетах используют double вместо float. И по той же, по которой в фотошопе сначала рисуют на большом разрешении, даже если итоговая картинка будет 640х480.
                                  Алгоритмы работают точнее с оверсемплингом.
                                  А не слышит не только человек, микрофоны тоже имеют завал АЧХ на высоких частотах, как и акустика.
                                +1
                                Есть общая проблема всех дискретных сигналов (видео, изображения, звука) — алиасинг. Т.е. появление в нем таких частот, которых в нем изначально не было.
                                Для видео — это, например, низкочастотное мерцание ЭЛТ монитора при съемке его на видекамеру. (монитор мерцает 60 Гц, камера снимает 25 кадров в секунду) Или медленное вращение пропеллера вертолета, причем часто в обратную сторону.
                                Для изображения — это муар. Или, например, если взять изображение черно-белого диска а-ля поле чудес и уменьшить его в паинте, получится, что там, где частота смены черное-белое высокая, с картинка может измениться вплоть до негатива.
                                Для звука наглядно не расскажешь, но можно показать, см. картинку в статье ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B8%D0%B0%D1%81%D0%B8%D0%BD%D0%B3_(%D0%BE%D0%B1%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B0_%D1%81%D0%B8%D0%B3%D0%BD%D0%B0%D0%BB%D0%BE%D0%B2)
                                Имея ультразвук 39560 Гц, который услышит не каждая собака, и оцифровывая частотой 40000 мы получим набор чисел, который будет в точности соответствовать звуку в 40000-39560 = 440 Гц, который мы отлично воспримем при цифровой обработке и услышим в колонках при обратном преобразовании. 440 Гц — это частота гудка в трубке телефона, т.е. вещь, которую не услышать невозможно.
                                Чтобы оцифровывать только то, что оцифровать в принципе возможно, частоты выше половины частоты дискретизации нужно отфильтровать аналоговым фильтром до оцифровки. По теореме Найквиста (Котельникова у нас) нужно отфильтровать все, что выше половины частоты дискретизации.
                                В случае с изображениями, перед изменением масштаба изображения, нужно так же отфильтровать высокие частоты, иначе появятся разные штуки типа муара.
                                  +2
                                  куда пиво высылать? :)

                                  завтра в личку напишу :)
                            +2
                            В формуле оконного преобразования Фурье опечатки: должно быть везде тау вместо x, раз уж интегрирование идет по тау, т.е. f(x) -> f(tau) и exp(-i*x*w) -> exp(-i*tau*w).
                              +1
                              Да, Вы правы. Большое спасибо — исправил.
                              +2
                              через вейвлет, работает алгоритм JPEG2000, если я правильно помню.
                              а все таки принцип неопределенность Гейзенберга корректно упоминать только в предметной области квантовой физики
                                +2
                                Про принцип неопределенности вы не правы. В общей форме (то есть не в популистской) этот принцип относится к любым двум самосопряженным линейным операторам гильбертова пространства. Оператор импульса пропорционален производной по соответствующей координате (x, например), и его собственные функции --это exp[ixk] (i--мнимая единица, k--волновой вектор). Переход к импульсному представлению поэтому совпадает с преобразованием Фурье. Поэтому принцип неопределенности все-таки непосредственно относится (чисто математически) к преобразованию Фурье. Притом даже при разложении по любому полному набору функций (не только экспонент), просто тогда вместо оператора импульса в выводе нужно использовать какой-то другой.
                                  0
                                  <<Существует точная, количественная аналогия между соотношениями неопределённости Гейзенберга и свойствами волн или сигналов. Рассмотрим переменный во времени сигнал, например звуковую волну. Бессмысленно говорить о частотном спектре сигнала в какой-либо момент времени. Для точного определения частоты необходимо наблюдать за сигналом в течение некоторого времени, таким образом теряя точность определения времени. Другими словами, звук не может иметь и точного значения времени, как например короткий импульс, и точного значения частоты, как, например, в непрерывном чистом тоне. Временно́е положение и частота волны во времени походят на координату и импульс частицы в пространстве.>>

                                  насколько я понял это тоже самое что написал автор в посте:

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

                                  Т.е. это всего навсего аналогия (как аналогия между спином и вращением)

                                  а то что Вы привели в пример, насколько я смог понять, справедливо лишь в том, что данные линейные операторы используются исключительно в квантовых вычислениях.
                                  Я не холивора ради, если можете, дайте ссылку или название книги, где можно просветиться насчет общей формы неопределенности Гейзенберга
                                    +2
                                    Не совсем понял, что вы хотели сказать, к сожалению.
                                    <<Т.е. это всего навсего аналогия (как аналогия между спином и вращением)>>

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

                                    Вкратце написано о принципе неопределенности в ссылке из моего предыдущего поста (на википедию). Более подробно--например, вот в этой книге Давыдов, Квантовая механика, страница 53 (так что вам недолго разбираться:-)
                                      0
                                      спасибо, понятно
                                +1
                                Спасибо, интересно. Было бы очень интересно почитать про реальные задачи анализа сигналов (помимо сжатия информации) и как в них используются этот и другие методы.
                                  0
                                  Ну вот, например, мы использовали вейвлет преобразование (правда мы его очень сильно модифицировали и упростили, так что даже не знаю как это теперь назвать:)) для задачи поиска и сравнения изображений.
                                    –1
                                    Выше уже писали, что в JPEG2000 используется вейвлет-преобразование. В обычном JPEG--дискретное косинунсое преобразование (одна из вариаций Фурье-преобразования).
                                      0
                                      В т.ч. поэтому я и написал «помимо сжатия информации».
                                        +1
                                        Виноват) Когда нам читали вейвлеты в универе, рассказывали, что ФБР использует их для хранения и поиска отпечатков пальцев. То есть здесь и сжатие информации), и задачи классификации. Вообще вейвлеты хорошо подходят под задачи классификации сигналов: удобно сравнивать низкочастотные образы сигналов.
                                    0
                                    Вопрос: какова скорость наиболее быстрых дискретных алгоритмов вейвлет-преобразования?
                                    FFT себе представляю (очень красивый алгоритм), а вот описания дискретного вейвлет-преобразования ни разу не встречал.
                                      +3
                                      Я в 2004-м писал диплом на тему вейвлет-преобразований. В качестве демонстрации применения на практике разработал обучаемую программу, распознающую речевые команды. Целью, конечно была лишь демонстрация, поэтому программа ничем конкретно не управляет, а лишь показывает какая команда произнесена, отображает в виде топографических карт полученный сигнал. Распознавание основано на сравнении карт, нормализованных по амплитуде и времени.

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

                                        Вы грубо выкинули информацию о фазе
                                          0
                                          1. Рассчитывается интеграл при начальных условиях Tau=0 и S=1;

                                          Здесь можно по подробнее… интеграл чего?
                                          0
                                          Может мне кто-нибудь тут объяснить — 1. Как же все таки получаются вейвлет базисы, как они масштабируются, по какому закону.
                                          2. Сдвиг это временная метка сигнала? Он берется в заивисимости от момента времени, в котором существует сигнал?
                                          3. Если я беру свдиг равный едине, то максимальное значение базиса в момент времени 1?
                                          4. А что если я хочу применить свои фильтры. а не те базисы, которые существуют?

                                          Only users with full accounts can post comments. Log in, please.