Autocorrelation is a measure of a signal’s similarity to itself at lagged points. By shifting a copy of the source signal over itself we can see the measure of similarity at periodic points. Autocorrelation can be used as a pitch detection algorithm (PDA). Pitch is another term for the frequency of a sound wave. A significant peak in the Autocorrelation result can indicate the fundamental frequency/pitch, but watch out for harmonics.
%matplotlib agg
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from IPython.display import HTML
$$ r[k] = \frac{1}{N} \sum_{j=1}^{N-k} x[j]x[j+k] $$ ACF can be implemented as:
def acf(x):
r = np.zeros(len(x))
N = len(x)
for k in range(N):
for j in range(1,N-k):
r[k] += (x[j]*x[j+k])
r[k] = r[k]/(N)
return r
Adding some signal data. e2 (below) is 256 samples of an E2 note (82.4 hz) at a sampling rate of 3874 hz. Signals from fixed point instruments tend to look somewhat messy. It’s not a pure fundamental 82.4 hz sine wave, but a combination of it’s fundamental and harmonic signals.
From the sample length and sampling frequency, build the time axis t
e2 = [187,173,105,-84,-184,-172,-180,-193,-160,-241,-347,-166,-87,66,190,146,160,235,134,109,164,61,-73,-35,-167,-117,-56,-75,34,229,-6,12,82,-5,61,109,-86,-300,-407,-373,-137,55,37,77,120,52,328,451,386,239,-42,-182,-149,-124,-189,-220,-296,-397,-300,-87,91,176,223,204,104,8,40,141,45,19,-107,-241,-170,-192,-79,257,225,12,45,82,76,210,129,-54,-399,-407,-291,5,122,98,82,-35,24,320,362,316,103,-144,-251,-145,-201,-163,-181,-284,-339,-177,-37,136,199,245,188,39,-42,61,74,50,58,-157,-168,-146,-183,67,335,161,-23,24,-44,40,112,67,-306,-407,-407,-194,53,74,147,53,-40,174,348,345,208,29,-204,-189,-173,-217,-164,-197,-296,-252,-70,58,163,226,204,85,-39,-29,61,13,35,-51,-150,-172,-203,-151,223,274,68,48,50,18,79,153,-69,-407,-407,-317,-19,66,108,126,4,-4,251,365,283,133,-87,-214,-163,-231,-222,-152,-269,-308,-151,-28,82,189,191,158,59,-29,75,90,48,53,-61,-141,-174,-207,44,298,170,25,38,38,-9,130,126,-260,-408,-365,-166,44,95,109,-3,-53,87,329,284,194,42,-170,-157,-125,-185,-109,-122,-278,-233,-56,27,90,195,153,70,-16,-6,68,58,65]
fs= 3874
l = len(e2)/fs
t = np.arange(0,l,1.0/fs)
res = acf(e2)
def step_acf(x):
fig.clear()
plt.subplot(1,2,1)
plt.title("Source Signal and copy at lag=%i" %(x))
plt.plot(t+t[x],e2)
plt.plot(t,e2)
plt.xlim(0,t[len(e2)-1])
plt.subplot(1,2,2)
plt.plot(t[:x+1],res[:x+1])
plt.title("Autocorrelation result")
plt.xlim(0,t[len(e2)-1])
fig = plt.figure(figsize = (9, 3))
frames=np.arange(2,100,5)
anim = FuncAnimation(fig, step_acf, frames,interval=500 )
#HTML(anim.to_jshtml())
HTML(anim.to_html5_video())
Lag points with significant overlap in the source signal and copy are points of interest; in an autocorrelation result these show up as high peaks. There is a lot of overlap of the signal and lagged signal at lag=47, and repeats periodically about every +47 lags for this source signal at this sample frequency. Normalizing the Lagged point with the sample frequency gives us the frequency at this point. The source is a 82.4 hz signal and the result does agree. \(f = fs/47\)
print("3874/47 =",fs/47)
3874/47 = 82.42553191489361
There are some lesser peaks, the first peak is around lag=16 which is the influence of the third harmonic \(f_3\) and will repeat about every +16 lags. The second harmonic \(f_2\) is around lag=23 but isn’t a peak in this case. Harmonics can show up as a change in slope or a trough or a peak and sometimes be a problem when doing simple peak detection in Autocorrelation techniques. The Harmonic problem is something the watch out for.
This sampling frequency worked out nicely to land on 82.4 hz but consider if this note was out of tune at 79.9 hz. The nearest discrete point would be lag=48 or (80.7083 hz). Or if the note was just a little out of tune at 82.0 hz. At this sample frequency, it would always find the result of 82.4 hz. This isn’t quite good enough to work as a guitar tuner at this sample frequency.
A higher sampling frequency would increase accuracy, there’s also techniques to figure out the peak of a curve between discrete points like parabolic interpolation.