реклама на сайте
подробности

 
 
2 страниц V   1 2 >  
Reply to this topicStart new topic
> Суммирование с перекрытием и алиасинг, прошу прощения за избитость вопроса но хочу лучше понять
Сергей Ст
сообщение Jun 26 2017, 15:11
Сообщение #1


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 27-01-16
Пользователь №: 90 226



Здравствуйте ! Занимаясь шумоподавлением для звукового сигнала и применяя покадровую обработку понял что не достаточно хорошо понимаю метод суммирования с перекрытием при восстановлении очищенного от шума сигнала. Хотел бы проконсультироваться, но предварительно опишу то что сам понимаю и надеюсь что выплывут ошибки и недочеты моего понимания. Для шумоподавления я применяю метод спектрального вычитания, что аналогично применению фильтра в спектральной области с некоторой передаточной функцией. То есть очередной кадр с помощью кратковременного преобразования Фурье(с применением взвешивающего окна) преобразуется в спектральную область а дальше производится вычитание усредненного спектра шума и обратное преобразование во временную область. Кадры берутся с некоторым перекрытием. Затем полученный временной кадр очищенного сигнала суммируется с перекрытием с уже ранее очищенным участком сигнала.
Насколько я понимаю данная процедура должна быть технически аналогична ситуации когда имеется входная последовательность квазибесконечная и импульсная характеристика фильтра через который эта последовательность пропускается, достаточно короткая по сравнению с длиной входной последовательности. В этом случае принято применять так называемую секционированную свертку. Она основана на том что входная последовательность обрабатывается блоками. При этом чаще всего применяется алгоритмы свертки с использованием БПФ. То есть циклические свертки. Я нашел в литературе два предлагаемых варианта: (книжка Г. Нуссбаумер Быстрое преобразование Фурье и алгоритмы вычисления сверток)
1. Алгоритм перекрытия с суммированием.
2. Алгоритм перекрытия с накоплением.
В первом алгоритме входная последовательность разбивается на смежные (а не перекрывающиеся) блоки и свертка с ИХ фильтра производится при помощи циклического алгоритма свертки при этом последовательности дополняются нулями до некоторого размера N >= N1 + N2 - 1. N1 - длина последовательности, представляющей импульсную характеристику, N2 - длина кадра входной последовательности. Таким образом получаем результат циклической свертки который перекрывается со следующим блоком в N - N2 отсчетах. При суммировании перекрытий получаем результирующую последовательность.
Во втором алгоритме блоки изначально берутся перкрывающимися и над каждым блоком выполняется циклическая свертка. Затем первые N - N1 членов циклической свертки отбрасываются а остаются только N - N1 + 1 членов. Здесь никакого суммирования вообще не происходит. То есть последовательность выходная строится из смежных блоков правильных отсчетов. Более того в книге утверждается что этот вариант алгоритма предпочтительнее чем первый.
В случае же обработки которую рекомендуют в статьях о шумоподавлении применяется алгоритм блочной обработки который не принадлежит ни к одному из типов обработки, описанных выше. Хотя по идее любая обработка кадра входного сигнала в спектральной области - это применение фильтра с некоторой импульсной характеристикой преобразованной в частотную область (то есть передаточной функцией). И, поскольку длина кадра фиксированная, фиксированной надо полагать и эту самую импульсную характеристику. То есть можно применять один из алгоритмов описанных выше?? Но видимо не все так просто.
Теперь об оконном преобразовании Фурье и алиасинге. Алиасинг сколько я понимаю - это перетекание высокочастотных компонентов спектра в низкочастотные с отражением от середины при недостаточной частоте дискретизации. (поправьте если не прав) Оконное преобразование применяется для того чтобы в спектр попали частоты из среднего участка кадра и спектр не был бы искажен из за разрыва сигнала на границах блоков ? Я правильно понимаю ? При этом перекрытие как утверждается определяет уровень алиасинга. Вот тут я совершенно плохо понимаю как это взаимосвязано. Буду рад любой информации и подсказке где почитать о подобной обработке блоков с перекрытием.
Go to the top of the page
 
+Quote Post
andyp
сообщение Jun 26 2017, 17:38
Сообщение #2


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(Сергей Ст @ Jun 26 2017, 18:11) *
...Более того в книге утверждается что этот вариант алгоритма предпочтительнее чем первый.


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

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


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

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

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

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

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

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

Сообщение отредактировал andyp - Jun 27 2017, 12:03
Прикрепленные файлы
Прикрепленный файл  _doi_10.1109_2Ficassp.2010.5495161_.pdf ( 202.47 килобайт ) Кол-во скачиваний: 48
 
Go to the top of the page
 
+Quote Post
petrov
сообщение Jun 26 2017, 19:53
Сообщение #3


Гуру
******

Группа: Свой
Сообщений: 2 062
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(Сергей Ст @ Jun 26 2017, 18:11) *
Алиасинг сколько я понимаю - это перетекание высокочастотных компонентов спектра в низкочастотные с отражением от середины при недостаточной частоте дискретизации. (поправьте если не прав) Оконное преобразование применяется для того чтобы в спектр попали частоты из среднего участка кадра и спектр не был бы искажен из за разрыва сигнала на границах блоков ? Я правильно понимаю ? При этом перекрытие как утверждается определяет уровень алиасинга. Вот тут я совершенно плохо понимаю как это взаимосвязано.


Посмотрите как вычисляется один бин ДПФ, это же просто полосовой КИХ фильтр, окно - огибающая этого КИХ фильтра, т. е. ФНЧ-прототип перенесённый на центральную частоту бина. ДПФ - гребёнка(банк) таких фильтров. Если блоки при вычисленнии банка КИХ фильтров берутся со смещением в 1 отсчёт, то децимации нет, алиасинга нет, если со смещением в половину блока N, то получается децимация N/2. Собственно от FFT можно абстрагироваться, обычные эффекты алиасинга при фильтрации и децимации-интерполяции. FFT+полифазные фильтры - всего лишь быстрый алгоритм вычисления банка фильтров, происходящий от того факта, что гребёнка фильтров имеет общий ФНЧ прототип и вычисляется над одними и теми же данными. Кстати, окно(ФНЧ-прототип) вовсе не обязано равнятся длине блока FFT.
Go to the top of the page
 
+Quote Post
KalashKS
сообщение Jun 27 2017, 10:35
Сообщение #4


Местный
***

Группа: Участник
Сообщений: 208
Регистрация: 7-02-11
Пользователь №: 62 755



Цитата(andyp @ Jun 26 2017, 20:38) *
Overlap-save ничем не лучше overlap-add с точки зрения теории. В смысле - и в том и в другом случае получится одинаковая последовательность на выходе.

Переоткрыл для себя overlap-save, за что автору спасибо. Последовательность он, конечно, даст ту же самую, но манипуляции с пямятью существенно упростятся. Пойду применять.
Go to the top of the page
 
+Quote Post
andyp
сообщение Jun 27 2017, 12:24
Сообщение #5


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(KalashKS @ Jun 27 2017, 13:35) *
Переоткрыл для себя overlap-save, за что автору спасибо. Последовательность он, конечно, даст ту же самую, но манипуляции с пямятью существенно упростятся. Пойду применять.


Ну да, имхо там все удобством менеджмента памяти и определяется. Ну и еще, если есть возможность FFT ядру сказать, что у него на входе часть данных нулевые, то overlap-add может быть тоже чутка предпочтительнее.
Go to the top of the page
 
+Quote Post
Сергей Ст
сообщение Jun 27 2017, 15:51
Сообщение #6


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 27-01-16
Пользователь №: 90 226



Цитата(andyp @ Jun 26 2017, 21:38) *
Количество отсчетов в ЧХ полученного фильтра равно длине используемого преобразования Фурье. После обратного преобразования Фурье в общем случае получится столько же отсчетов и в ИХ. А перекрытие у Вас по длине меньше, т.е. условия использования алгоритмов overlap-add/save не выполняются.

Вот здесь я немножко начинаю путаться( То есть если внимательно читать про перекрытие с накоплением то нужны блоки длиной N, при этом N >= N2 и N >= N1. Таким образом блок перекрывается с предыдущим в N - N2 отсчетах.
Выход цифрового фильтра представляет собой последовательные циклические N-точечные свертки блоков входного сигнала с блоками длины N, получившимися путем добавления N-N1 нулей к импульсной характеристике.
Далее часть отсчетов ошибочных отбрасывается а остальные накапливаются в соответствующем интервале выходного сигнала. Это я упрощенно цитирую Нуссбаумера. В нашем же случае длина блока равна длине
импульсной характеристики. И чем это плохо для применения алгоритма перекрытия с накоплением. Почему именно длина перекрытия должна быть не менее длины импульсной характеристики фильтра? Это не совсем укладывается в
голову(
andyp я прилагаю книжку Нуссбаумера в zip архиве в формате djvu. Если интересно пробегите раздел по цифровой фильтрации, использующей циклическюу свертку начиная со страницы 34. Там немножко.
Я наверняка что то упускаю что Вы сразу обнаружите...

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

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

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

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

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


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


Цитата(petrov @ Jun 26 2017, 23:53) *
Если блоки при вычисленнии банка КИХ фильтров берутся со смещением в 1 отсчёт, то децимации нет, алиасинга нет, если со смещением в половину блока N, то получается децимация N/2.
Собственно от FFT можно абстрагироваться, обычные эффекты алиасинга при фильтрации и децимации-интерполяции.
FFT+полифазные фильтры - всего лишь быстрый алгоритм вычисления банка фильтров, происходящий от того факта, что гребёнка фильтров имеет общий ФНЧ прототип и вычисляется над одними и теми же данными.
Кстати, окно(ФНЧ-прототип) вовсе не обязано равнятся длине блока FFT.

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

Прикрепленные файлы
Прикрепленный файл  NFFTC.zip ( 2.47 мегабайт ) Кол-во скачиваний: 21
 
Go to the top of the page
 
+Quote Post
petrov
сообщение Jun 27 2017, 16:22
Сообщение #7


Гуру
******

Группа: Свой
Сообщений: 2 062
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(Сергей Ст @ Jun 27 2017, 18:51) *
То есть смещение более чем на один отсчет от начала блока это прореживание по частоте ?


Например, если выход КИХ фильтра децимируем в 2 раза, то мы можем не вычислять отбрасываемые отсчёты, т. е. брать блоки входных отсчётов со смещением в 2 отсчёта.
Go to the top of the page
 
+Quote Post
andyp
сообщение Jun 27 2017, 21:27
Сообщение #8


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(Сергей Ст @ Jun 27 2017, 18:51) *
Вот здесь я немножко начинаю путаться( То есть если внимательно читать про перекрытие с накоплением то нужны блоки длиной 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

Go to the top of the page
 
+Quote Post
thermit
сообщение Jun 27 2017, 21:34
Сообщение #9


Знающий
****

Группа: Участник
Сообщений: 735
Регистрация: 3-08-09
Пользователь №: 51 730



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

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

Поиск на электрониксе кривоногий, но вполне рабочий.
Go to the top of the page
 
+Quote Post
andyp
сообщение Jun 27 2017, 21:46
Сообщение #10


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(thermit @ Jun 28 2017, 00:34) *
Утомительно цитировать самого себя.


Да и всех остальных, кто тут отвечал sm.gif
Go to the top of the page
 
+Quote Post
Сергей Ст
сообщение Jul 4 2017, 08:44
Сообщение #11


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 27-01-16
Пользователь №: 90 226



Цитата(thermit @ Jun 28 2017, 01:34) *
http://electronix.ru/redirect.php?https://...t&p=1180490

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

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

Цитата(andyp @ Jun 28 2017, 01:27) *
Пусть длина ИХ фильтра 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?
Go to the top of the page
 
+Quote Post
petrov
сообщение Jul 4 2017, 09:38
Сообщение #12


Гуру
******

Группа: Свой
Сообщений: 2 062
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(Сергей Ст @ Jul 4 2017, 11:44) *
Мне не совсем понятно почему таки применяют разные перекрытия и сложение, а не overlap-save с перекрытием IRLen - 1?


Потому что нужна не быстрая свёртка сама по себе, а простой способ на лету менять коэффициенты передачи гребёнки полосовых фильтров.
Go to the top of the page
 
+Quote Post
Сергей Ст
сообщение Jul 4 2017, 11:20
Сообщение #13


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 27-01-16
Пользователь №: 90 226



Цитата(petrov @ Jul 4 2017, 13:38) *
Потому что нужна не быстрая свёртка сама по себе, а простой способ на лету менять коэффициенты передачи гребёнки полосовых фильтров.

Даже если при этом будут определенные искажения? И неточности при воспроизведении сигнала ?
Go to the top of the page
 
+Quote Post
petrov
сообщение Jul 4 2017, 11:36
Сообщение #14


Гуру
******

Группа: Свой
Сообщений: 2 062
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(Сергей Ст @ Jul 4 2017, 14:20) *
Даже если при этом будут определенные искажения? И неточности при воспроизведении сигнала ?


Непревышение любого наперёд заданного уровня алиасинга может быть обеспечено. Ну и про неточности вопрос интересный, даже если алиасинга нет, слышите вы неискажённый сигнал или звон фильтров?
Go to the top of the page
 
+Quote Post
Сергей Ст
сообщение Jul 4 2017, 12:11
Сообщение #15


Участник
*

Группа: Участник
Сообщений: 15
Регистрация: 27-01-16
Пользователь №: 90 226



Цитата(petrov @ Jul 4 2017, 15:36) *
Непревышение любого наперёд заданного уровня алиасинга может быть обеспечено. Ну и про неточности вопрос интересный, даже если алиасинга нет, слышите вы неискажённый сигнал или звон фильтров?

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

2 страниц V   1 2 >
Reply to this topicStart new topic
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 20th November 2017 - 01:59
Рейтинг@Mail.ru


Страница сгенерированна за 0.01349 секунд с 7
ELECTRONIX ©2004-2016