To do Cross-correlation with FFTs and Afrog:
- Padding Signals with zeros:
As per AForge documentation of fft:
The method accepts data array of 2n size only, where n may vary in the [1, 14] range.
So you would need to make sure the input size is correctly padded to a length that is a power of 2, and in the specified range:
taking into account at least half of the wave is "blank" (zeros)
ref:
https://dsp.stackexchange.com/questions/741/why-should-i-zero-pad-a-signal-before-taking-the-fourier-transform
https://dsp.stackexchange.com/questions/1919/efficiently-calculating-autocorrelation-using-ffts
- take the FFT of both signals
- multiply one with conjugate of the other (element-wise multiplication)
- do the inverse FFT
- get max value as a corellation coefficient and its index as the delay(signal lag)
Why Max value of the resultant IFFT:
from wikipedia, Cross-correlations are useful for determining the time delay between two signals, e.g. for determining time delays for the propagation of acoustic signals across a microphone array.2[3][clarification needed]
After calculating the cross-correlation between the two signals, the maximum (or minimum if the signals are negatively correlated) of the cross-correlation function indicates the point in time where the signals are best aligned, i.e. the time delay between the two signals is determined by the argument of the maximum, or arg max of the cross-correlation, as in
ref:
https://math.stackexchange.com/questions/1080709/why-is-the-maximum-value-of-cross-correlation-achieved-at-similar-section
Based on the above points, the Cross Calculation is calculated using the following code:
//same as OP
public Complex[] CrossCorrelation(Complex[] ffta, Complex[] fftb)
{
var conj = ffta.Select(i => new Complex(i.Re, -i.Im)).ToArray();
conj = conj.Zip(fftb, (v1, v2) => Complex.Multiply(v1, v2)).ToArray();
FourierTransform.FFT(conj, FourierTransform.Direction.Backward);
//get that data and plot in Excel, to show the max peak
Console.WriteLine("---------rr[i]---------");
double[] rr = new double[conj.Length];
rr = conj.Select(i => i.Magnitude).ToArray();
for (int i = 0; i < conj.Length; i++)
Console.WriteLine(rr[i]);
Console.WriteLine("----end-----");
return conj;
}
//tuble.Item1: Cor. Coefficient
//tuble.Item2: Delay of signal (Lag)
public Tuple<double, int> CorrelationCoefficient(Complex[] ffta, Complex[] fftb)
{
Tuple<double, int> tuble;
var correlation = CrossCorrelation(ffta, fftb);
var seq = correlation.Select(i => i.Magnitude);
var maxCoeff = seq.Max();
int maxIndex = seq.ToList().IndexOf(maxCoeff);
Console.WriteLine("max: {0}", maxIndex);
tuble = new Tuple<double, int>(maxCoeff, maxIndex);
return tuble;
}
// Pad signal with zeros up to 2^n and convert to complex
public List<Complex> ToComplexWithPadding(List<double> sample, int padding = 1)
{
//As per AForge documentation:
// The method accepts data array of 2n size only, where n may vary in the [1, 14] range
//So you would need to make sure the input size is correctly padded to a length that is a power of 2, and in the specified range:
double logLength = Math.Ceiling(Math.Log(sample.Count * padding, 2.0));
int paddedLength = (int)Math.Pow(2.0, Math.Min(Math.Max(1.0, logLength), 14.0));
Complex[] complex = new Complex[paddedLength];
var samples = sample.ToArray();
// copy all input samples
int i = 0;
for (; i < sample.Count; i++)
{
complex[i] = new Complex(samples[i], 0);
Console.WriteLine(complex[i].Re);
}
// pad with zeros
for (; i < paddedLength; i++)
{
complex[i] = new Complex(0, 0);
Console.WriteLine(complex[i].Re);
}
return complex.ToList();
}
// extra for signal generation for testing. You can find in the link of the life demo.
You can run life demo with sample of two signal generated with delay 11
and the result match the actual delay of the signal
Life demo with two signals generated
The output result:
correlation Coef: 0.33867796353274 | Delay: 11| actual delay: 11
