3
$\begingroup$

Forgive me if this question is poorly worded, I'm not sure if centroid is the word to use here.

Say I want to interpolate the peak of a cross-correlation function in order to get sub-sample delays. I can fit a parabola with three points, or simply upsample my signal through zero-padding/sinc-interpolation. However, I haven't seen any comments (or found any literature) on using some sort of weighted average on the main peak.

In case it's unclear, i mean performing the following:

  1. Finding the maximum of the cross-correlation in order to get a coarse estimate. $$ \hat{D} = argmax(R_{12}) $$
  2. Taking the P nearest neighbors (where [-P,P] corresponds to the central peak area) and doing the following fine estimate

$$ \hat{d} = \frac{\sum_{k =-P}^P kR_{12}(k)}{\sum_{k=-P}^PR_{12}(k)} $$

I've tested it for a gaussian distributed, infinite snr signal, critically sampled (so peak is only three samples. Centroid, (yellow) versus some sinc interpolation (purple) and parabolic fitting (orange), and it seems to offer good performance.

enter image description here

It appears to have less maximum bias, despite the discontinuity. I also tested it with noise and the results were also okay. I get that this requires knowledge of the signal A.C.F. beforehand whereas fitting a parabola doesn't, but is there any other reason why this method is not seen in the literature?

Either way, I'm finding it somewhat advantageous in my application (also not sure wh), so I would like to read some more formal studies or descriptions of the technique. My background is not signal processing, so I'm afraid I'm overlooking some severe shortcoming.

NOTE: I also tested the mean-square error. It seems to perform much worse there, but as I said, for my use case it seems to perform well. enter image description here. (The black line is the cramer-rao lower bound. Not sure why the parabola goes below it, probably because it's a biased estimator...)

EDIT: Signal example of the application (this picture has quite a lot of distortion of the delayed signal, but it's what I have at hand currently).

enter image description here

Improve this question
$\endgroup$
7
  • $\begingroup$ Can you disclose what your signal is like? $\endgroup$
    – Olli Niemitalo
    Oct 31, 2017 at 19:58
  • 1
    $\begingroup$ For the examples I mentioned it's simply a random Gaussian distributed signal (for purposes of evaluating the interpolators). In the use case it's a bandlimited, exponentially distributed signal with gaussian distributed noise. I have an old picture from some poster that shows the signal, although it was meant to show the distortion of the signal for larger delays. I'll post it. (Sorry, I will only be in the office now on Thursday, so it's what I can provide) $\endgroup$
    – LDPC
    Oct 31, 2017 at 20:07
  • 1
    $\begingroup$ If you have some headroom in the sampling frequency (and I suspect that you do as you find that centroid of cross-correlation $R_{12}$ works well) centroid of $R_{12}^2$ could work even better. $\endgroup$
    – Olli Niemitalo
    Oct 31, 2017 at 20:39
  • $\begingroup$ Thanks for the tip. Any comments on why that is? I'm quite oversampled, about 3 times more than I need, currently. Also, you don't know of any place I can find some description or study of the performance of the centroid? $\endgroup$
    – LDPC
    Oct 31, 2017 at 20:48
  • $\begingroup$ I tested finding the peak position of a delayed oversampled sinc using the centroid. Squaring the sinc seemed to remove (not sure if completely) the bias of the centroid. Squaring doubles the bandwidth, and the headroom to keep the bandwidth at half the sampling frequency or less is necessary if the peak finding method is generic and not specific to the peak shape. Sometimes the square of a function can be considered as an unnormalized probability density function. $\endgroup$
    – Olli Niemitalo
    Oct 31, 2017 at 21:56

2 Answers 2

Reset to default
3
$\begingroup$

There are a lot of papers on bin interpolation and some of them have obvious connections to interpolating a parabola and others aren't' so obvious. Given what you presented, I'm sure that you can make the connection between cross correlation and spectral analysis. I suggest you look at:

M. D. Macleod, "Fast nearly ML estimation of the parameters of real or complex single tones or resolved multiple tones," in IEEE Transactions on Signal Processing, vol. 46, no. 1, pp. 141-148, Jan 1998. doi: 10.1109/78.651200 Abstract: This paper presents new computationally efficient algorithms for estimating the parameters (frequency, amplitude, and phase) of one or more real tones (sinusoids) or complex tones (cisoids) in noise from a block of N uniformly spaced samples. The first algorithm is an interpolator that uses the peak sample in the discrete Fourier spectrum (DFS) of the data and its two neighbors. We derive Cramer-Rao bounds (CRBs) for such interpolators and show that they are very close to the CRB's for the maximum likelihood (ML) estimator. The new algorithm almost reaches these bounds. A second algorithm uses the five DFS samples centered on the peak to produce estimates even closer to ML. Enhancements are presented that maintain nearly ML performance for small values of N. For multiple complex tones with frequency separations of at least 4π/N rad/sample, unbiased estimates are obtained by incorporating the new single-tone estimators into an iterative “cyclic descent” algorithm, which is a computationally cheap nonlinear optimization. Single or multiple real tones are handled in the same way. The new algorithms are immune to nonzero mean signals and (provided N is large) remain near-optimal in colored and non-Gaussian noise keywords: {Fourier analysis;Gaussian noise;amplitude estimation;frequency estimation;harmonic analysis;interpolation;iterative methods;maximum likelihood estimation;optimisation;phase estimation;signal sampling;spectral analysis;white noise;AWGN;Cramer-Rao bounds;FFT;amplitude;cisoids;colored noise;complex single tones;discrete Fourier spectrum;fast nearly ML estimation;frequency;frequency separations;interpolator;iterative cyclic descent algorithm;noise;nonGaussian noise;nonlinear optimization;nonzero mean signals;parameter estimation;peak sample;phase;real single tones;resolved multiple tones;sinusoids;unbiased estimates;uniformly spaced samples;Amplitude estimation;Computational efficiency;Frequency estimation;Iterative algorithms;Maximum likelihood estimation;Noise level;Parameter estimation;Phase estimation;Phase noise;Signal processing algorithms}, URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=651200&isnumber=14197

and if you can get into IEEE Explore, look at the papers that cite it. These are the State-OF-The-Art bin interpolation schemes, which you should be making your comparisons to.

The only comment that I have about you centroid technique, would be that the accuracy would seem to depend on there being only a single delay in your data. My experience is that where there is one delay, there are often many. Having too wide a window would seem to be more susceptible to additional delays.

Improve this answer
$\endgroup$
2
$\begingroup$

I didn't find much literature of interest on the centroid of cross-correlation. This article:

Bradley M. Peterson, Ignaz Wanders, Keith Horne, Stefan Collier, Tal Alexander, Shai Kaspi, Dan Maoz (Submitted on 9 Feb 1998) On Uncertainties in Cross-Correlation Lags and the Reality of Wavelength-Dependent Continuum Lags in Active Galactic Nuclei. https://arxiv.org/abs/astro-ph/9802103

is cited by:

W. F. Welsh (1999) On the Reliability of Cross‐Correlation Function Lag Determinations in Active Galactic Nuclei. Publications of the Astronomical Society of the Pacific, Volume 111, Number 765. http://iopscience.iop.org/article/10.1086/316457/meta

Improve this answer
$\endgroup$

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.