相互相関関数の計算方法の違いによる処理速度の差

はじめに

相互相関関数を計算するときに，時間領域で直接計算（直接法）する方法とフーリエ変換を利用して周波数領域で計算する方法（FFT法）があります．計算時間はFFT法のほうが速いと聞きましたが，Numpyのcorrelate関数は直接法でしか計算できません．そこで，勉強を兼ねてFFT法を実装して試してみようと思います．
作り終わってから気が付きましたが，Scipyのcorrelate関数はFFT法が使えます．

参考

こちらの資料を参考にさせていただきました．
コンボリューション関数（conv）と相関関数(xcorr)と離散フーリエ変換関数（fft）の関係

プログラム

ここからプログラム本体です．Juputer notebookで作成しました．

1. import

#coding:utf-8
%matplotlib notebook
import matplotlib.pyplot as plt
import numpy as np
import scipy.signal as sg

2. 試験信号

ランダムな信号を作成します．

N = 512
x, y = np.random.randn(2, N)
#正規化
x -= np.average(x)
x /= np.std(x)
y -= np.average(y)
y /= np.std(y)

3. 直接法

corr = np.correlate(x, y, mode="full") / N

4. FFT法 巡回問題対策済み

def xcorr(x, y):
    N = len(x) if len(x) > len(y) else len(y)
    #xとyの長さが同じになるように0を加える
    xz = np.append(x, np.zeros(len(y)-1))
    yz = np.append(np.zeros(len(x)-1), y)
    
    XY = np.fft.fft(xz) * np.conj(np.fft.fft(yz))
    xy = np.real(np.fft.ifft(XY)) / N
    return xy

5. 直接法とFFT法の計算結果の比較

FFT法では巡回問題を解決するために0を加えたため，インデックスが1つずれます．
1つずらして差分を取ると，両者の値は一致します．

diff = np.real(xy)[1:N*2-1]-np.append(0.0,corr)[1:N*2-1]

処理速度の比較

直接法とFFT法の処理速度を比較します．処理対象のデータ点数が少ないときはNumpyの関数が速いですが，点数が増えてくるとFFT法の利点が顕著に見れます．

まとめ

FFT法は直接法に比べて処理速度が速かったです．ただ，遅れ時間がそれほど大きくないことがわかっているときは，直接法で計算範囲を絞ったほうが速いと思います．