5
$\begingroup$

What is the definition of Generalized Cross Correlation?

I need it for estimating the delay (time offset) between two audio signals. The time offset between the two signals might be as large as 500ms.

$\endgroup$
  • $\begingroup$ I know this is not the place to ask about that but this is an old topic ... I wonder how is the d array defined ? (it is a array of time) Because if xi and xj signals have a length Li and Lj, the simple cross correlation is given by R(tau) where R and tau are arrays of length (Li+Lj)-1 But here, for the generalized cross correlation, Rgcc has a length Li (or Lj, it works only if they have the same length). Does someone has the answer ? Thanks in advance (I add references : xavieranguera.com/phdthesis/node92.html and xavieranguera.com/phdthesis/node $\endgroup$ – Hobgobelin Jan 8 '14 at 23:05
6
$\begingroup$

Cross-correlation implies that you have 2 signals, and there is a delay between them. A 'basic' frequency domain cross-correlator does an FFT on each signal, conjugates one of them, multiplies one versus the other, then inverse transforms. A peak in the result indicates a time delay.

There are a lot of problems with this simple approach. For instance: you want a linear cross-correlation instead of a circular one; you may have strong sinusoidal interference which will generates multiple peaks; you may have very low SNR; the noise may not be what you expect it to be, etc.

A 'generalized' cross-correlation adds a windowing (or filtering) function prior to the inverse transform. It's purpose is to improve the estimation of the time delay, depending on the specific characteristics of the signals and noise (broadband/narrowband/interference signals, Gaussian noise, etc.). Since there are many different types of signals and noise, there are many different window functions (eg.: SCOT, Ekhart, etc.) Each one is designed for specific problems. Understanding these differences is not trivial, nor is proper calculation of the window function. They are typically dealt with in graduate-level time delay estimation or sonar/radar courses.

Some references for generalized cross-correlation are:

J. C. Hassab, R. E. Boucher, “Optimum Estimation of Time Delay by a Generalized Correlator,” IEEE T-ASSP, vol. 27, no. 4, Aug. 1979, pp. 373-380 (discusses various window types).

J. C. Hassab, R. E. Boucher, “Performance of the Generalized Cross Correlator in the Presence of a Strong Spectral Peak in the Signal,” IEEE T-ASSP, vol. 29, no. 3, June 1981, pp. 549-555.

J. C. Hassab, R. E. Boucher, “An Experimental Comparison of Optimum and Sub-Optimum Filters’ Effectiveness in the Generalized Correlator,” J. Sound and Vibration, 1981, pp. 4+ (12 pages total)(Fig. 1 contains a block diagram of a generalized cross-correlator).

There are many others.

$\endgroup$
6
$\begingroup$

EDIT The OP mentions below Deve's answer that this was not the "Generalized Cross Correlation" algorithm referred to. The real one seems to be this one:

enter image description here

This paper seems to give equations about how to implement it in the time domain.

The equation they give is basically what Deve reports below. The key point they make is that the "input" to the cross-correlation is not the bare signals, but the residuals of an LMS algorithm applied to the bare signals.

This as the effect of pre-whitening the input signals.

enter image description here


The method seems to be from this paper:

Azaria, M.; Hertz, D., "Time delay estimation by generalized cross correlation methods," Acoustics, Speech and Signal Processing, IEEE Transactions on , vol.32, no.2, pp.280,285, Apr 1984

doi: 10.1109/TASSP.1984.1164314

Abstract: The problem of estimating time delay by cross correlation methods is reexamined for the whole class of stationary signals. Expressions are derived for the estimation mean square error (MSE) by the cross correlation method, and are shown to be identical to previously published results for Gaussian signals. The generalized cross correlation method is also analyzed, and the optimal weight function for this method is derived. It is shown to be identical to that derived for Gaussian signals by the maximum likelihood method. For the cross correlation method a simplified MSE expression is derived, which is to be used instead of a previously published result.

keywords: {Autocorrelation;Bandwidth;Correlation;Delay effects;Delay estimation;Error analysis;Estimation error;Maximum likelihood estimation;Mean square error methods;Signal to noise ratio}

From which the key formula appears to be:

enter image description here

where

enter image description here

$\endgroup$
  • $\begingroup$ It's cross correlation but I don't know why it's called "generalized" $\endgroup$ – Lee Jan 30 '17 at 16:49
  • $\begingroup$ @Lee The "generalized' piece is because the usual cross-correlation is normalized. In 5.10 above, that means the denominator for the usual cross-correlation is 1. $\endgroup$ – Peter K. Jan 30 '17 at 17:51
2
$\begingroup$

I'm not sure what the "generalized" exactly refers to. But to calculate the time offset between two (discrete time) audio signals $r(n)$ and $s(n)$ I would use the following cross correlation function: $$ R(m) = \sum_{n=0}^{N-1}r(n)s^*(n-m) $$ Here, $()^*$ denotes the conjugate complex and $N$ is the length of the audio signals assuming they have the same length. The position of the maximum of $R(m)$ is expected to be the time offset.

$\endgroup$
  • $\begingroup$ The method is called GCC PHAT. But I'm not sure how the algorithm is supposed to be implemented in a real-time environment where audio is processed in blocks of 10ms. $\endgroup$ – james3849 Apr 19 '13 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.