1
$\begingroup$

I have 2 signals S1 and S2 that contain the same information, but S2 is shifted and scaled compared to S1 by an unknown amount (but small; eg shift would be of the order of 1-10 samples).

What is the best (=most effective yet simple) way to calculate (or estimate) the shift and scaling factor to apply to S2 in order to 'match' with S1.

I have read a few papers referring to using the phase information in FFT, but those were working on signals where scaling was not really an issue (and i must admit not to have understood them completely anyway). I am a bit lost on how to put this in practice when developing that in Matlab (actually I use Octave).

I would love to have an explanation using Matlab/Octave code if possible.

Thanks for any help.

Steve

PS: I add the tag 'image processing' because I suspect that such techniques would be used in automatic stitching of images (in panoramas for example)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

In case you specifically want to find a shift and scale you can use the cross correlation function of Matlab. Some additional options for the Matlab xcorr function are the following: 

x = xcorr(s1, s2, M, 'unbiased');

Here M is the maximum number of lags for calculating the cross correlation function. The input argument unbiased takes care of finite lenght effects of the signals. The biased estimator calculates $$r[k] = \frac{1}{N}\sum_{n=1}^N s_1[n]s_2[n-k]$$ and the unbiased estimator calculates $$r[k] = \frac{1}{N-k}\sum_{n=1}^N s_1[n]s_2[n-k]$$

Another technique that you can in case the relation between $s_1$ and $s_2$ is more complex than an integer delay and a gain is to calculate a Wiener filter wikipedia. If the relation changes over time, then an adaptive filter can be useful, e.g., using the lms algorithm.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I thought that phase information in Fourier transform would be the cleanest way of doing it. For my education, are you able to comment on that? Whatever the case, cross correlation is adequate for my needs. I will continue down that route, discovering to what extent delay is constant in my signals. If a dynamic delay is needed, I'll explore adaptive filters as suggested. I mark this as my solution thanks to the precision on biased vs unbiased. $\endgroup$
    – Stevo
    Commented Aug 12, 2015 at 8:41
  • $\begingroup$ Can you provide links to " papers referring to using the phase information in FFT" and what do you mean with scaling in the time-axis? Do you have the following relation between your two signals: $s_2[n] = s_1[ \alpha n + \beta]$ or: $s_2[n] = \alpha s_1[n + \beta]$ where $\alpha$ is the scale and $\beta$ the shift? $\endgroup$
    – Brian
    Commented Aug 12, 2015 at 13:43
  • $\begingroup$ In general I refer to the Fourier Shift Theorem, which I thought would help me with this problem (but it's a long time since I covered this in my studies, hence my apparent potential ignorance). For paper: A NEW SHIFT ESTIMATION ALGORITHM FOR BARCODE SUPER RESOLUTION; not sure if this specific signal type (barcode scan lines) is applicable elsewhere however. As for relation between signals, s2[n]=s1[αn+β] $\endgroup$
    – Stevo
    Commented Aug 12, 2015 at 15:28
  • $\begingroup$ In the paper they also use the correlation function (see eq3) to estimate shifts between lines. Subsequently, the resolution is increased (estimating a shift of less than one pixel) by using the FFT. For your signal model, time scaling leads to a scaled frequency response, related to the inverse of the scale factor. For example, if $\alpha>1$ then every sine wave will be of lower frequency. Probably you can identify the scale factor by matching the power spectra of your signals. These spectra do not contain phase information. Once you have corrected for the scale, you can estimate the shift. $\endgroup$
    – Brian
    Commented Aug 13, 2015 at 6:52
  • $\begingroup$ I'm sorry! It was the wrong paper i posted (shame). This is the one I should have posted: Super-resolution of bar codes(section 2.1) $\endgroup$
    – Stevo
    Commented Aug 13, 2015 at 8:18
1
$\begingroup$

Matlab has a function called xcorr() that computes the cross correlation between two vectors. The cross correlation will be highest when the two signals overlap. The following code will compute the shift in units of samples:

x = xcorr(s1,s2)

[val,idx] = max(x);

shift = length(s1) - idx

The scaling factor should be given by:

scale = max(s1)/max(s2)

Improve this answer
$\endgroup$
2
  • $\begingroup$ This assumes that s1 and s2 are the same length. $\endgroup$
    – CMDoolittle
    Commented Aug 10, 2015 at 16:23
  • $\begingroup$ Thanks for the answer. As mentioned in my other comment, i think it is indeed the way forward, though am curious to know (for my education) whether Fourier phase information can give good approximation and why. When I said scaled, i wasn't clear. I meant in fact in the time axis, ie that my signals are indeed not the same length. However, thanks to the fact that there is little additional information before/after the signals, I think that the ratio of lengths of the signals should be a good-enough approximation of the 'stretching factor'. $\endgroup$
    – Stevo
    Commented Aug 12, 2015 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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