Вычисления свертки в Numpy / Scipy

Профилирование некоторых вычислительных работ, которые я выполняю, показало мне, что одним узким местом в моей программе была функция, которая в основном это делала (np это numpy, sp scipy):

def mix1(signal1, signal2):
    spec1 = np.fft.fft(signal1, axis=1)
    spec2 = np.fft.fft(signal2, axis=1)
    return np.fft.ifft(spec1*spec2, axis=1)

Оба сигнала имеют форму (C, N), где C - количество наборов данных (обычно меньше 20), а N - количество выборок в каждом наборе (около 5000). Вычисление для каждого набора (строки) полностью не зависит от любого другого набора.

Я решил, что это просто свертка, поэтому я попытался заменить ее на:

def mix2(signal1, signal2):
    outputs = np.empty_like(signal1)

    for idx, row in enumerate(outputs):
        outputs[idx] = sp.signal.convolve(signal1[idx], signal2[idx], mode='same')

    return outputs

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

  1. Почему нет?
  2. Есть ли лучший способ вычислить эквивалент mix1()?

(Я понимаю, что mix2, вероятно, не был бы быстрее как есть, но это могло бы стать хорошей отправной точкой для распараллеливания.)

Вот полный сценарий, который я использовал, чтобы быстро это проверить:

import numpy as np
import scipy as sp
import scipy.signal

N = 4680
C = 6

def mix1(signal1, signal2):
    spec1 = np.fft.fft(signal1, axis=1)
    spec2 = np.fft.fft(signal2, axis=1)
    return np.fft.ifft(spec1*spec2, axis=1)

def mix2(signal1, signal2):
    outputs = np.empty_like(signal1)

    for idx, row in enumerate(outputs):
        outputs[idx] = sp.signal.convolve(signal1[idx], signal2[idx], mode='same')

    return outputs

def test(num, chans):
    sig1 = np.random.randn(chans, num)
    sig2 = np.random.randn(chans, num)
    res1 = mix1(sig1, sig2)
    res2 = mix2(sig1, sig2)

    np.testing.assert_almost_equal(res1, res2)

if __name__ == "__main__":
    np.random.seed(0x1234ABCD)
    test(N, C)

person detly    schedule 28.07.2011    source источник
comment
Я не знаю наверняка, но подозреваю, что разница может быть связана с тем, что БПФ / ОБПФ являются круговыми, т.е. они компенсируют тот факт, что данные не продолжаются вечно, притворяясь, что сигнал периодический, в то время как свертка () заполняется нулями. Должен быть способ получить круговую свертку - правда, не знаю, как это сделать.   -  person Owen    schedule 28.07.2011
comment
@Owen - Должно быть, mix1 выполняет эквивалент круговой свертки. Я совершенно забыл об этом различии.   -  person detly    schedule 28.07.2011
comment
Существует также еще одно отличие из-за нормализации - FFT нормализует свой вывод путем деления на длину массива (не все реализации FFT из-за этого, но Numpy делает), тогда как convolve не из-за этого, потому что он думает, что вы действительно хотите складывать, а не усреднять. Редактировать - не уверен в этом.   -  person Owen    schedule 28.07.2011
comment
Кроме того, если вы хотите исправить свое узкое место, это очень поможет, если ваша временная ось будет иметь степень двойки.   -  person Owen    schedule 28.07.2011
comment
@Owen - да, я думал, что внутренне алгоритм БПФ дополнил его до следующей степени 2. Я это проверю. Я не уверен, что БПФ Numpy выполняет какую-либо нормализацию - я помню, что что-то проверял с помощью теоремы Парсеваля, и мне здесь нужен был коэффициент 1 / N². Тоже не уверен.   -  person detly    schedule 28.07.2011


Ответы (3)


Я проверил это и теперь могу подтвердить несколько вещей:

1) numpy.convolve не является круговым, что дает вам код fft:

2) БПФ не имеет внутреннего дополнения до степени 2. Сравните сильно различающиеся скорости следующих операций:

x1 = np.random.uniform(size=2**17-1)
x2 = np.random.uniform(size=2**17)

np.fft.fft(x1)
np.fft.fft(x2)

3) Нормализация - это не разница - если вы выполните наивную циклическую свертку, добавив a (k) * b (i-k), вы получите результат кода БПФ.

Дело в том, что дополнение до степени 2 изменит ответ. Я слышал рассказы о том, что есть способы справиться с этим, разумно используя простые множители длины (упомянутые, но не закодированные в числовых рецептах), но я никогда не видел, чтобы люди действительно так поступали.

person Owen    schedule 28.07.2011
comment
Знаете ли вы, вне головы, если в Numpy есть следующая функция степени 2 (например, nextpow2 в MATLAB)? - person detly; 28.07.2011
comment
Ха-ха, не знаю. Я тоже часто хотел такую ​​:). - person Owen; 28.07.2011
comment
Хм. Кажется, это меняет ответ до такой степени, что больше не восстанавливается сигнал с действительным знаком (с использованием ifft(..., n=original_n,...). Тем не менее, это в основном отвечает на мои вопросы :) - person detly; 28.07.2011
comment
@detly Если вы расширите оба исходных сигнала до 2 ^ n, а затем выполните свертку, вы должны получить реальный сигнал. Это также означает, что вы не делаете никаких дополнительных отступов в частотной области, потому что это нарушит симметрию. - person Owen; 28.07.2011
comment
@eryksun правда, это не изменит ответ, если вы действительно хотите линейную свертку. Но если вам нужна круговая свертка, разве добавление нулей не изменит сигнал? - person Owen; 28.07.2011
comment
@eryksun Ну, может, и лучше, но все равно это меняет. Скажем, у меня есть ABCDEF, и я хочу расширить его до 8, чтобы он стал ABCDEFAB. Но этот сигнал теперь представляет ABCDEFABABCDEFAB ... тогда как исходным был ABCDEFABCFED (повторяющийся AB отличается). - person Owen; 28.07.2011
comment
Следующую степень двойки очень легко вычислить: 2 ** ceil (log2 (x)) - person staticfloat; 30.04.2012
comment
Степени двойки легко вычислить, но смешанные размеры оснований системы счисления могут быть быстрее и использовать меньше памяти. См. gist.github.com/bhawkins/4479607. - person Brian Hawkins; 30.08.2013

scipy.signal.fftconvolve выполняет свертку с помощью БПФ, это код Python. Вы можете изучить исходный код и исправить функцию mix1.

person HYRY    schedule 29.07.2011
comment
У меня работает функция mix1. Мне нужна была mix2 функция, которая воспроизводила бы ее поведение. - person detly; 29.07.2011

Как упоминалось ранее, функция scipy.signal.convolve не выполняет циклическую свертку. Если вы хотите, чтобы круговая свертка выполнялась в реальном пространстве (в отличие от использования fft), я предлагаю использовать функцию scipy.ndimage.convolve. У него есть параметр режима, который может быть установлен на «обертку», что делает его круговой сверткой.

for idx, row in enumerate(outputs):
    outputs[idx] = sp.ndimage.convolve(signal1[idx], signal2[idx], mode='wrap')
person ABDreverhaven    schedule 20.08.2013
comment
@_ABDreverhaven Я пробовал то, что вы сказали, но все равно получаю разные результаты - person Manolete; 12.02.2014