Перекрытие-Добавить против перекрытия-Сохранить

24

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

hotpaw2
источник

Ответы:

27

По сути, ОС немного более эффективна, поскольку не требует добавления перекрывающихся переходных процессов. Тем не менее, вы можете использовать OA, если вам нужно повторно использовать FFT с заполнением нулями, а не с повторными выборками.

Вот краткий обзор статьи, которую я написал недавно

Быстрая свертка относится к блочному использованию круговой свертки для достижения линейной свертки. Быстрая свертка может быть достигнута методами OA или OS. ОС также известна как «перекрытие». При OA-фильтрации каждый блок данных сигнала содержит только столько отсчетов, сколько позволяет круговой свертке быть эквивалентной линейной свертке. Блок данных сигнала заполняется нулями перед БПФ, чтобы предотвратить «обтекание» конца последовательности импульсной характеристики фильтра. OA-фильтрация добавляет входной переходный процесс из одного блока с входным отключенным переходом из предыдущего блока. При фильтрации ОС, показанной на рисунке 1, заполнение нулями для входных данных не выполняется, поэтому круговая свертка не эквивалентна линейной свертке. Части, которые «оборачиваются», бесполезны и выбрасываются. Чтобы компенсировать это, последняя часть предыдущего входного блока используется в качестве начала следующего блока. ОС не требует добавления переходных процессов, что делает его быстрее, чем OA.

Марк Боргердинг
источник
Отличная статья! =)
Фонон
Может быть некоторая оптимизация в способе вычисления DFT по заполненной нулями части буфера OA, что дает преимущество для метода OA. Это будет зависеть от вашего процессора и пакета FFT. Кроме того, вы могли бы написать свой собственный алгоритм БПФ специально для ОА, который учитывает нулевую точку.
Ордбен
@orodbhen, вы знаете какой-нибудь такой пакет FFT?
Марк Боргердинг
@MarkBorgerding В OpenCV вы можете указать количество нулевых строк, но это специфично для 2D. Что касается того, какие неявные оптимизации присутствуют в том или ином пакете FFT, я не знаю. Я могу вспомнить множество случаев, когда было бы полезно использовать пользовательское БПФ для использования разреженности, но я сам не пошел по этому пути. Еще нет.
Ордбен
1
Хорошо, что вы процитировали, потому что ссылка не работает :(
Mehrdad