Перейти к содержанию
    

Суммирование с перекрытием и алиасинг

Здравствуйте ! Занимаясь шумоподавлением для звукового сигнала и применяя покадровую обработку понял что не достаточно хорошо понимаю метод суммирования с перекрытием при восстановлении очищенного от шума сигнала. Хотел бы проконсультироваться, но предварительно опишу то что сам понимаю и надеюсь что выплывут ошибки и недочеты моего понимания. Для шумоподавления я применяю метод спектрального вычитания, что аналогично применению фильтра в спектральной области с некоторой передаточной функцией. То есть очередной кадр с помощью кратковременного преобразования Фурье(с применением взвешивающего окна) преобразуется в спектральную область а дальше производится вычитание усредненного спектра шума и обратное преобразование во временную область. Кадры берутся с некоторым перекрытием. Затем полученный временной кадр очищенного сигнала суммируется с перекрытием с уже ранее очищенным участком сигнала.

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

1. Алгоритм перекрытия с суммированием.

2. Алгоритм перекрытия с накоплением.

В первом алгоритме входная последовательность разбивается на смежные (а не перекрывающиеся) блоки и свертка с ИХ фильтра производится при помощи циклического алгоритма свертки при этом последовательности дополняются нулями до некоторого размера N >= N1 + N2 - 1. N1 - длина последовательности, представляющей импульсную характеристику, N2 - длина кадра входной последовательности. Таким образом получаем результат циклической свертки который перекрывается со следующим блоком в N - N2 отсчетах. При суммировании перекрытий получаем результирующую последовательность.

Во втором алгоритме блоки изначально берутся перкрывающимися и над каждым блоком выполняется циклическая свертка. Затем первые N - N1 членов циклической свертки отбрасываются а остаются только N - N1 + 1 членов. Здесь никакого суммирования вообще не происходит. То есть последовательность выходная строится из смежных блоков правильных отсчетов. Более того в книге утверждается что этот вариант алгоритма предпочтительнее чем первый.

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

Теперь об оконном преобразовании Фурье и алиасинге. Алиасинг сколько я понимаю - это перетекание высокочастотных компонентов спектра в низкочастотные с отражением от середины при недостаточной частоте дискретизации. (поправьте если не прав) Оконное преобразование применяется для того чтобы в спектр попали частоты из среднего участка кадра и спектр не был бы искажен из за разрыва сигнала на границах блоков ? Я правильно понимаю ? При этом перекрытие как утверждается определяет уровень алиасинга. Вот тут я совершенно плохо понимаю как это взаимосвязано. Буду рад любой информации и подсказке где почитать о подобной обработке блоков с перекрытием.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

...Более того в книге утверждается что этот вариант алгоритма предпочтительнее чем первый.

 

Overlap-save ничем не лучше overlap-add с точки зрения теории. В смысле - и в том и в другом случае получится одинаковая последовательность на выходе.

 

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

 

Количество отсчетов в ЧХ полученного фильтра равно длине используемого преобразования Фурье. После обратного преобразования Фурье в общем случае получится столько же отсчетов и в ИХ. А перекрытие у Вас по длине меньше, т.е. условия использования алгоритмов overlap-add/save не выполняются.

 

Капитан очевидность подсказывает, что можно обеспечить требуемую длину ИХ просто сделав c ЧХ следующее преобразование IFFT ->обнуляем все, что вылазит за N1 -> FFT. Если N1 кратно N2 (N2 = k*N1, k - целое) то можно просто занулить каждый k-ый отсчет ЧХ фильтра начиная с k и получим ИХ длины N2.(Это я ступил и погорячился :))

 

Но в этом случае фильтр станет "не совсем винеровским" и на выходе останется недодавленная помеха, которую могли бы додавить.

 

В результате имеем баланс - искажения вызванные усечением ИХ фильтра vs искажения вызванные наложением при использовании циклической свертки вместо линейной. Что победит - зависит от конкретной ИХ фильтра.

 

Поэтому еще в той теме писал, что все эти алгоритмы шумоподавления отдают "черной магией"

 

Впрочем, вот есть статья о том как хорошо делать подобные свертки

_doi_10.1109_2Ficassp.2010.5495161_.pdf

Изменено пользователем andyp

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Алиасинг сколько я понимаю - это перетекание высокочастотных компонентов спектра в низкочастотные с отражением от середины при недостаточной частоте дискретизации. (поправьте если не прав) Оконное преобразование применяется для того чтобы в спектр попали частоты из среднего участка кадра и спектр не был бы искажен из за разрыва сигнала на границах блоков ? Я правильно понимаю ? При этом перекрытие как утверждается определяет уровень алиасинга. Вот тут я совершенно плохо понимаю как это взаимосвязано.

 

Посмотрите как вычисляется один бин ДПФ, это же просто полосовой КИХ фильтр, окно - огибающая этого КИХ фильтра, т. е. ФНЧ-прототип перенесённый на центральную частоту бина. ДПФ - гребёнка(банк) таких фильтров. Если блоки при вычисленнии банка КИХ фильтров берутся со смещением в 1 отсчёт, то децимации нет, алиасинга нет, если со смещением в половину блока N, то получается децимация N/2. Собственно от FFT можно абстрагироваться, обычные эффекты алиасинга при фильтрации и децимации-интерполяции. FFT+полифазные фильтры - всего лишь быстрый алгоритм вычисления банка фильтров, происходящий от того факта, что гребёнка фильтров имеет общий ФНЧ прототип и вычисляется над одними и теми же данными. Кстати, окно(ФНЧ-прототип) вовсе не обязано равнятся длине блока FFT.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Overlap-save ничем не лучше overlap-add с точки зрения теории. В смысле - и в том и в другом случае получится одинаковая последовательность на выходе.

Переоткрыл для себя overlap-save, за что автору спасибо. Последовательность он, конечно, даст ту же самую, но манипуляции с пямятью существенно упростятся. Пойду применять.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Переоткрыл для себя overlap-save, за что автору спасибо. Последовательность он, конечно, даст ту же самую, но манипуляции с пямятью существенно упростятся. Пойду применять.

 

Ну да, имхо там все удобством менеджмента памяти и определяется. Ну и еще, если есть возможность FFT ядру сказать, что у него на входе часть данных нулевые, то overlap-add может быть тоже чутка предпочтительнее.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Количество отсчетов в ЧХ полученного фильтра равно длине используемого преобразования Фурье. После обратного преобразования Фурье в общем случае получится столько же отсчетов и в ИХ. А перекрытие у Вас по длине меньше, т.е. условия использования алгоритмов overlap-add/save не выполняются.

Вот здесь я немножко начинаю путаться( То есть если внимательно читать про перекрытие с накоплением то нужны блоки длиной N, при этом N >= N2 и N >= N1. Таким образом блок перекрывается с предыдущим в N - N2 отсчетах.

Выход цифрового фильтра представляет собой последовательные циклические N-точечные свертки блоков входного сигнала с блоками длины N, получившимися путем добавления N-N1 нулей к импульсной характеристике.

Далее часть отсчетов ошибочных отбрасывается а остальные накапливаются в соответствующем интервале выходного сигнала. Это я упрощенно цитирую Нуссбаумера. В нашем же случае длина блока равна длине

импульсной характеристики. И чем это плохо для применения алгоритма перекрытия с накоплением. Почему именно длина перекрытия должна быть не менее длины импульсной характеристики фильтра? Это не совсем укладывается в

голову(

andyp я прилагаю книжку Нуссбаумера в zip архиве в формате djvu. Если интересно пробегите раздел по цифровой фильтрации, использующей циклическюу свертку начиная со страницы 34. Там немножко.

Я наверняка что то упускаю что Вы сразу обнаружите...

 

Капитан очевидность подсказывает, что можно обеспечить требуемую длину ИХ просто сделав c ЧХ следующее преобразование IFFT ->обнуляем все, что вылазит за N1 -> FFT.

 

Но в этом случае фильтр станет "не совсем винеровским" и на выходе останется недодавленная помеха, которую могли бы додавить.

 

В результате имеем баланс - искажения вызванные усечением ИХ фильтра vs искажения вызванные наложением при использовании циклической свертки вместо линейной. Что победит - зависит от конкретной ИХ фильтра.

 

Поэтому еще в той теме писал, что все эти алгоритмы шумоподавления отдают "черной магией"

 

Впрочем, вот есть статья о том как хорошо делать подобные свертки

 

Огромное спасибо за статью! Прочитаю обязательно и внимательно.

 

 

Если блоки при вычисленнии банка КИХ фильтров берутся со смещением в 1 отсчёт, то децимации нет, алиасинга нет, если со смещением в половину блока N, то получается децимация N/2.

Собственно от FFT можно абстрагироваться, обычные эффекты алиасинга при фильтрации и децимации-интерполяции.

FFT+полифазные фильтры - всего лишь быстрый алгоритм вычисления банка фильтров, происходящий от того факта, что гребёнка фильтров имеет общий ФНЧ прототип и вычисляется над одними и теми же данными.

Кстати, окно(ФНЧ-прототип) вовсе не обязано равнятся длине блока FFT.

Спасибо Вам большое! В общих чертах что то проясняется, но к сожалению еще не достаточно хорошо знаю теоретические основы. То есть смещение более чем на один отсчет от начала блока это прореживание по частоте ?

Насколько я помню децимация вынуждает нас применять ФНЧ. К сожалению с полифазными фильтрами не имел дела поэтому трудно что то ответить.

Еще раз спасибо!

NFFTC.zip

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

То есть смещение более чем на один отсчет от начала блока это прореживание по частоте ?

 

Например, если выход КИХ фильтра децимируем в 2 раза, то мы можем не вычислять отбрасываемые отсчёты, т. е. брать блоки входных отсчётов со смещением в 2 отсчёта.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Вот здесь я немножко начинаю путаться( То есть если внимательно читать про перекрытие с накоплением то нужны блоки длиной N, при этом N >= N2 и N >= N1. Таким образом блок перекрывается с предыдущим в N - N2 отсчетах.

Выход цифрового фильтра представляет собой последовательные циклические N-точечные свертки блоков входного сигнала с блоками длины N, получившимися путем добавления N-N1 нулей к импульсной характеристике.

Далее часть отсчетов ошибочных отбрасывается а остальные накапливаются в соответствующем интервале выходного сигнала. Это я упрощенно цитирую Нуссбаумера. В нашем же случае длина блока равна длине

импульсной характеристики. И чем это плохо для применения алгоритма перекрытия с накоплением. Почему именно длина перекрытия должна быть не менее длины импульсной характеристики фильтра?

 

Пусть длина ИХ фильтра IRLen, длина Фурье - Nfft.

 

Вне зависимости от overlap-add/save у Вас в каждой свертке за счет цикличности получается ровно длина IRLen - 1 "плохих" отсчетов, потому что первые отсчеты циклической свертки используют хвост текущего блока вместо хвоста предыдущего. Если длина Фурье равна длине ИХ то получится только один хороший отсчет на блок - последний.

 

В случае overlap-save когда мы считаем циклическую свертку первые IRLen -1 результатов используют последние отсчеты блока и поэтому являются "плохими" и их требуется отбросить на выходе, т.е. каждый раз из Nfft получается Nfft - IRLen+1 полезных отсчетов. Поэтому перекрытие блоков должно быть равно IRLen-1, а длина входного блока - Nfft.

 

В случае overlap-add входные блоки не перекрываются, а дополняются IRlen - 1 отсчетами до длины Фурье. В этом случае в вычислении первых IRLen-1 результатов свертки участвуют 0 и отсчеты блока. Поэтому уже на выходе требуется суммирование и перекрытие. Длина входного блока равна Nfft - IRlen + 1

 

 

Собственно оба алгоритма сносно описаны в википедии

https://en.wikipedia.org/wiki/Overlap%E2%80%93save_method

https://en.wikipedia.org/wiki/Overlap%E2%80%93add_method

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

http://electronix.ru/redirect.php?https://...t&p=1180490

 

Утомительно цитировать самого себя.

 

Поиск на электрониксе кривоногий, но вполне рабочий.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

http://electronix.ru/redirect.php?https://...t&p=1180490

 

Утомительно цитировать самого себя.

Спасибо Вам за пример. Я правильно понимаю что в методе перекрытия с накоплением overlap-save первые N отсчетов вообще теряются для выходной последовательности ?

 

Пусть длина ИХ фильтра IRLen, длина Фурье - Nfft.

 

Вне зависимости от overlap-add/save у Вас в каждой свертке за счет цикличности получается ровно длина IRLen - 1 "плохих" отсчетов, потому что первые отсчеты циклической свертки используют хвост текущего блока вместо хвоста предыдущего. Если длина Фурье равна длине ИХ то получится только один хороший отсчет на блок - последний.

 

В случае overlap-save когда мы считаем циклическую свертку первые IRLen -1 результатов используют последние отсчеты блока и поэтому являются "плохими" и их требуется отбросить на выходе, т.е. каждый раз из Nfft получается Nfft - IRLen+1 полезных отсчетов. Поэтому перекрытие блоков должно быть равно IRLen-1, а длина входного блока - Nfft.

 

В случае overlap-add входные блоки не перекрываются, а дополняются IRlen - 1 отсчетами до длины Фурье. В этом случае в вычислении первых IRLen-1 результатов свертки участвуют 0 и отсчеты блока. Поэтому уже на выходе требуется суммирование и перекрытие. Длина входного блока равна Nfft - IRlen + 1

 

 

Собственно оба алгоритма сносно описаны в википедии

https://en.wikipedia.org/wiki/Overlap%E2%80%93save_method

https://en.wikipedia.org/wiki/Overlap%E2%80%93add_method

Спасибо! Я посмотрел и Википедию и некоторые другие материалы. Вопрос возник следующий, я прошу прощения за возможную навязчивость, А если все же разбивать на блоки длины Nfft входную последовательность, затем каждый блок дополнять нулями до длины IRLen + Nfft - 1, дополнять нулями импульсную характеристику фильтра до той же суммарной длины,

делать свертку через FFT и накапливать правильные отсчеты а неправильные отбрасывать, то есть применять overlap-save? В чем проблема здесь ? Мне не совсем понятно почему таки применяют разные перекрытия и сложение, а не overlap-save с перекрытием IRLen - 1?

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Мне не совсем понятно почему таки применяют разные перекрытия и сложение, а не overlap-save с перекрытием IRLen - 1?

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Даже если при этом будут определенные искажения? И неточности при воспроизведении сигнала ?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Даже если при этом будут определенные искажения? И неточности при воспроизведении сигнала ?

 

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

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

В принципе в моем эксперименте с набором синусоид на фоне белого шума все звучит хорошо. Я сейчас в большей степени хочу теоретически понять всею эту систему с перекрытием. Поэтому и пытаюсь с разных сторон заходить так сказать) У меня есть книжка Гоулд и Рабинер по цифровой обработке сигналов. Там может быть описана вся эта система с перекрытиями и ее применимость ?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...