Computing the cross-correlation function is useful for finding the time-delay offset between two time series. Python has the numpy.correlate function. But there is a much faster FFT-based implementation. Check out the following paper for an application of this function:

[bibtex file=lanes.bib key=fridman2015sync]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
import numpy as np from numpy.fft import fft, ifft, fft2, ifft2, fftshift def cross_correlation_using_fft(x, y): f1 = fft(x) f2 = fft(np.flipud(y)) cc = np.real(ifft(f1 * f2)) return fftshift(cc) # shift < 0 means that y starts 'shift' time steps before x # shift > 0 means that y starts 'shift' time steps after x def compute_shift(x, y): assert len(x) == len(y) c = cross_correlation_using_fft(x, y) assert len(c) == len(x) zero_index = int(len(x) / 2) - 1 shift = zero_index - np.argmax(c) return shift |

We can test the above function by shifting the second series manually and seeing if the shift is accurately computed:

1 2 3 4 5 6 7 8 9 10 11 12 |
for n in range(1000, 1050, 7): for s in range(-5, 5): a = [random.random() for _ in xrange(n)] # big random sequence of values b = a if s >= 1: a = a[s:] b = b[:-s] elif s <= -1: a = a[:s] b = b[-s:] assert s_optimal == s |