Обработка сигналов в Python. Найти сдвиг в данных серии

Question

У меня есть данные: [1,3,3,....1] ~ 500 номеров.

Каждые 1 мс у меня есть новый, но с некоторой сменой (5-10 баллов) + небольшой шум.

E.g: 
[1 2 3 4 3 21 4 5...] 
[0 4 3 1 2 3 4 19 7 5 ...] 

В этом случае сдвига 3.

Я хочу знать, этот сдвиг. Как я могу его получить?

Путь Фурье должен замедляться .. Потому что у меня много линий в секунду. find time shift between two similar waveforms

Может быть, есть некоторые быстрые пути? Или Может быть, я должен использовать Фурье только для части моих данных (потому что они смещаются примерно как целые). Большое спасибо.

Answer 1

Если вы знаете, что отставание составляет всего несколько образцов 5-10, то вы можете использовать автокорреляцию, чтобы найти его. Он должен быть быстрым, если вы только вычислите его для этого ограниченного небольшого диапазона лагов. Если вы вычислите его для всех возможных задержек, то это, вероятно, будет очень медленным.

Вот пример, в котором используется алгоритм модифицированного AMDF:

import numpy as np 

def modified_amdf(x1, x2, steps): 
    N = min(len(x1), len(x2)) 
    res = [] 
    for step in steps: 
     sm = 0 
     for n in range(0, N - step): 
      sm += np.abs(x1[n] - x2[n + step]) 
     sm = sm * (1.0/(N - step - 1)) 
     res.append(sm) 
    return res 

#x1 = [1, 2, 3, 4, 3, 21, 4, 5] 
#x2 = [0, 4, 3, 1, 2, 3, 4, 19, 7, 5] 
x1 = np.sin(np.linspace(0, 10*np.pi, 500)) 
x2 = np.r_[[0,0], x1] # add two lag entries 
penalties = modified_amdf(x1, x2, range(5)) 
print "Found lag:", np.argmin(penalties) 

Вы можете улучшить скорость немного, если вы меняете расчеты использовали только NumPy, но это займет много времени только 500 образцов за несколько лагов.