4
$\begingroup$

I would like to find the exact replica of signal A in time series B. I am working with the simple toy example below, in which A is located starting at the 4th position in B.

I thought that using xcorr would achieve this but I am clearly failing somewhere. xcorr doesn't seem to be the right function despite the MATLAB help notes on xcorr and comments such as:

Cross-correlation is usually the simplest way to determine the time lag between two signals. The position of peak value indicates the time offset at which the two signals are the most similar.

A = [1 2 1];
B = [0 9 8 1 2 1 7 3 1 0];  
[c, lags] = xcorr(A,B)
lags(c==max(c))
c =
Columns 1 through 12
  0.0000    1.0000    5.0000   14.0000   18.0000   11.0000    6.0000   12.0000   26.0000   26.0000    9.0000    0.0000
Columns 13 through 19
  0.0000    0.0000    0.0000   -0.0000   -0.0000   -0.0000   -0.0000
lags =
  -9    -8    -7    -6    -5    -4    -3    -2    -1     0     1     2     3     4     5     6     7     8     9
ans =
  -1     0

The max correlation values are located at lags of -1 and 0, which doesn't match the offset required to get A to match B. This leads me to ask:

  1. When is xcorr useful for finding the exact signal in another signal? 2. And what function should I be using to find the location of A in B?

Ideally I would like to test this method on more complicated signals as well as look for methods of detecting "similar" signals inside other (longer) signals.

$\endgroup$
3
$\begingroup$

It is usually useful to use normalized cross-correlation for finding position of small template on other longer signal. The value of normalized cross-correlation coefficient is invariant to change of amplitude and bias of signals.

xcorr function does not calculate normalized cross-correlation coefficient for vectors with unequal length. I prepare code snippet, which calculate normalized cross-correlation coefficient:

%prepare template Y and signal X
Y = [1 2 1];
X = [0 9 8 1 2 1 7 3 1 0];

% calculation normalized cross-correlation
lngX = length(X);
lngY = length(Y);
assert(lngX >= lngY);
lags = 0:(lngX-lngY);
for i = lags
   c(i+1) = xcorr(X(i+1:i+lngY) - mean(X(i+1:i+lngY)), Y - mean(Y),0,'coeff');
end
[m,i]=max(c);
printf('max=%f, lag=%d\n',c(i),lags(i));
plot(lags,c,'-',lags(i),c(i),'*r');
text(lags(im)+4,c(im)-0.05,'max correlation', 'color','red');
xlabel('lags'); title('normalized cross-correlation'); grid on;

Result:

 max=1.000000, lag=3

enter image description here

UPDATE 1

Matlab's xcorr does not calculate true normalized cross-correlation, so I add subtraction of mean value from signals before call to xcorr.

UPDATE 2 I modify my code to demonstrate more interesting example of template and signal. Part of code for calculation normalized cross-correlation is the same.

%prepare template Y and signal X
Y = exp(-((1:40)-20).^2/20.).*cos(((1:40)-20)*2*pi/10);
Y2 = exp(-((1:100)-50).^2/100.);
X = [zeros(1,40) 2*Y zeros(1,10) 3*Y2 zeros(1,10)];
noise=1.;
X=X+noise*(rand(1,length(X))-0.5);

% calculation normalized cross-correlation
lngX = length(X);
lngY = length(Y);
assert(lngX >= lngY);
lags = 0:(lngX-lngY);
for i = lags
   c(i+1) = xcorr(X(i+1:i+lngY) - mean(X(i+1:i+lngY)), Y -     mean(Y),0,'coeff');
end
[m,im]=max(c);
printf('max=%f, lag=%d\n',c(im),lags(im));

%plotting
subplot(2,1,2);
plot(lags(im)+1:(lngY+lags(im)),Y,'r','linewidth',2,1:lngX,X,'b');
legend('template','signal'); grid on;
subplot(2,1,1);
plot(lags,c,'-',lags(im),c(im),'*r');
text(lags(im)+4,c(im)-0.05,'max correlation', 'color','red');
xlabel('lags'); title('normalized cross-correlation'); grid on;

Result:

max=0.905503, lag=40

normalized cross-correlation

$\endgroup$
  • $\begingroup$ Nice post (+1)! I was a little confused by "scale" invariant. I tend to think of scaling $x(t)$ by $S$, as $x(t/S)$ rather than $S x(t)$... but then I've looked at wavelets for too long. :-) $\endgroup$ – Peter K. Oct 28 '15 at 10:52
  • 1
    $\begingroup$ @PeterK. Thank you. I have modified phrase. Yes, the scale is a very popular term in wavelets :-) $\endgroup$ – SergV Oct 28 '15 at 11:16
1
$\begingroup$

The function xcorr calculates the correlation of 2 signals.
The correlation is known to be a good (The MLE) for delay estimation under Gaussian Noise.

Yet, as can be seen in your data you're not using it in the cases it meant to be used.
If we assume you have a model of a known signal with Additive White Gaussian Noise (AWGN or any other Additive White Noise), than the SNR is so terrible you can not expect it perform well.

If your signal model is additive deterministic signal (The signal [0 9 8 0 0 0 7 3 1 0] in that example) then you should look for a different approach (Though xcorr can be part of it).

Any tool you use, you must be aware for the model it was designed for.

$\endgroup$
  • $\begingroup$ Thanks. Any suggestions as to what tool I should use for my task? $\endgroup$ – val Oct 28 '15 at 7:42
  • $\begingroup$ What is the model of your task? $\endgroup$ – Royi Oct 28 '15 at 7:58
  • $\begingroup$ I don't know how you would call such a model other than to say exactly what it represents: in some cases it is a categorical sequence from a geological drillhole lithology log (e.g. {sandstone = 0, granite = 9, gneiss = 8, shale =1, limestone = 2, ...., shale =1, sandstone = 0}, in other cases it might be a set of continuous values that represent some physical property measurement (e.g. density) measured down the depth of the drillhole (no example given). I interpret both of these as (geological) "time series" and wish to find specific signals within them. $\endgroup$ – val Oct 28 '15 at 16:26
  • $\begingroup$ It sounds like you are looking for specific patterns of integers in sequence (meaning no noise component). This should work for you: blogs.mathworks.com/loren/2008/09/08/finding-patterns-in-arrays $\endgroup$ – Dan Boschen Mar 6 '17 at 11:08

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.