0
$\begingroup$

Let's say I have a signal which consists several pulses of approximately equal height, and I have to correlate it with the expected positions of the peaks to find the shift of this signal w.r.t. a reference signal, which may consist of impulses only.

Probably I would do something like computing the cross-correlation between the two, maybe after some normalization, and read off the shift as the maximum.

Now suppose that the signal is pre-processed already, and I only have access to the locations of the detected local maxima. Due to noise some peaks may go undetected, and others may be detected where there really was no pulse. Even more common would be that, apart from a global shift, the detected maxima also have an independent further error in the position.

What I could always do, is take this list of locations, turn it into a sequence of pulses of size 1 (say) with 0's in between in one large array, convolve it with some kernel, large enough to accomodate the individual uncertainly in position, but small enough to keep consecutive pulses mostly separated, and take the cross-correlation with the expected positions, turned into an array, of the reference signal.

Is there however a good algorithm to do this without turning it into a signal, i.e. by just comparing the two lists, one with the local maxima, the other with the reference positions? This could be useful e.g. when the signal has a very high resolution, so that a very sparse signal would have to be changed into a very large array.

EDIT As a concrete example, let's say the reference says that we have maxima around

$$100, 200, 400, 1000, 1200, 1600, 2000,\ldots$$

The measured values are

$$181.7, 366.6, 480.0, 971.5, 1559.1, 1821.4, 1981.4,\ldots$$

I could for example take a long array of zeros to interpolate the domain, with a 1 at the reference position corresponding to 100, 200, etc, another one with a 1 at the positions corresponding to 181.7, 366.6, etc, convolve one of them (or both) with some point spread function, e.g. a Gaussian of standard deviation up to around 100 or so. Then I could try to take the cross-correlation between the two, to find the global relative shift, if the noise is not too bad.

Is there a way I could achieve the same without expanding the locations into some kind of a dense array?

Alternatively, what would be a good algorithm that identifies the optimal matching between specific reference points and detected maxima, taking into account that there might be false positives and negatives?

In the example, the matching could be

 100   -  not detected
 200   -  181.7
 400   -  366.6
          480.0 false local maximum 
1000   -  971.5
1600   - 1559.1
       - 1821.4 false local maximum
2000   - 1981.4
$\endgroup$
1
$\begingroup$

If I understand you correctly, you have a periodic reference signal with pulses, and a list of the local maxima. From every local max, search for the nearest reference signal pulse and measure the distance (shift). If the frequency of your reference signal and the measured one is the same, than this shift should always point in the same direction.

If you have all the local shifts, you can average them to find a good estimate of the overall shift of the two signals.

I think, cross-correlation,possibly with smoothing, is the way to go. You loop over all possible offsets $s_i$ between your two datasets $x_i$ , $y_i$.

$C_j = \sum_{i=1}^{N} x_{i} y_{i-s_j}$

Here $C_j$ should be a measure for how well the two datasets match for a given shift $s_j$. For a perfekt dataset you would get only one large C_j, with all others being zero. Since you have some noise in your data, you may have to smooth the peaks beforehand, or use the original dataset and not only the list of peaks.

The more you smooth the two signals, the more robust the above method should be.

$\endgroup$
  • $\begingroup$ Thanks! However, my reference is not necessarily periodic. Moreover, on top of the global shift, there is an uncertainty in the position, and there may be points missing and new points added (false positives and negatives). I'll edit to given an example of the kind of data I have. $\endgroup$ – doetoe Jun 25 at 10:34

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.