0
$\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)

$\endgroup$
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.

$\endgroup$
  • $\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 Aug 12 '15 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 Aug 12 '15 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 Aug 12 '15 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 Aug 13 '15 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 Aug 13 '15 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)

$\endgroup$
  • $\begingroup$ This assumes that s1 and s2 are the same length. $\endgroup$ – CMDoolittle Aug 10 '15 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 Aug 12 '15 at 8:56

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.