Cross correlation with short or non periodic signals?

Question

I am a total newbe to signal processing and i have a problem which may be quite trivial to most of you guys.

I want to align two short sensor signals (speaking of max. 1000 samples recorded with 20Hz). The signals are sampled with the exact same sample rate and are not necessarily periodic. I use octave to make first experiments and i recognized some confusing behaviour of the xcorr() function in the 'signal' package. If i correlate two short signals the resulting lag value is not really correct. The longer one of the signals is, the better the lag value calculated by the xcorr() function.

Here is what i tested:

pkg load signal

clear all

%generate two short signals
x = -pi:0.05:pi;

sigA = sin(x);
sigB = cos(x);

%plot the original signals
figure 1
subplot(2,1,1);
plot((0:length(sigA)-1), sigA, 'r');
title("sin(x)");
xlabel("Sample index");
grid on;
subplot(2,1,2);
plot((0:length(sigB)-1), sigB, 'b');
title("cos(x)");
xlabel("Sample index");
grid on;

%calculate the cross correlation between signal B and signal A
[c, lag] = xcorr(sigB, sigA);
[~,i] = max(abs(c));
shift = lag(i) %the shifting offset between the two signals

%align the signals
sigA = sigA(abs(shift)+1:end);

maxLength = max(length(sigA), length(sigB)); %for sample index axis range

%plot the aligned signals
figure 2
subplot(2,1,1);
plot((0:length(sigA)-1), sigA, 'r');
title("sin(x) aligned");
xlabel("Sample index");
axis([0, maxLength, -1, 1]);
grid on;
subplot(2,1,2);
plot((0:length(sigB)-1), sigB, 'b');
title("cos(x) aligned");
xlabel("Sample index");
axis([0, maxLength, -1, 1]);
grid on;

The code produces the following figures and calculates a shift of -27 samples:

As you can clearly see, the signal A (sin(x)) is not perfectly aligned! I would have to change the alignment call to

%align the signals
sigA = sigA(abs(shift)+6:end); %where does this offset (1+5) come from?

to align them perfectly:

Now if i generate a longer signal for sigA, this offset disappears completely:

x = -100:0.1:100;
y = -pi:0.05:pi;

sigA = sin(x);
sigB = cos(y);

Then the situation looks like this:

As you can see in the image above, the two signals are perfectly aligned without shifting signal A manually as i had to with the shorter version of signal A.

Now here is an actual signal from my sensor (where signal A is a stored signal and signal B is a subset of signal A, the x axis shows the time in ms):

Same Problem appears here. I would have to shift signal A by 29 samples to the right to align them perfectly.

Why is that? Is cross correlation not the right thing to do for short or non periodic finite signals? Or is there a way to calculate the additional offset to the signal shift?

Answer 1

Given two signals with the same finite duration and number of samples $N$, we can calculate the periodic or cyclic crosscorrelation function which has $N$ values, or the aperiodic crosscorrelation function which has $2N-1$ values. For signals with $N$ and $M$ samples respectively ($N > M$), the aperiodic crosscorrelation function has $N+M-1$ values.

When the two signals are the same except that one is a cyclic shift of the other, the periodic crosscorrelation function has a maximum at perfect alignment. However, the maximum of the aperiodic crosscorrelation function is not necessarily at perfect alignment because the part that is "sticking out" and not overlapping with the other signal is missing, which lowers the peak.

When one signal is a truncated version of the other, and the longer signal is periodic, then the aperiodic crosscorrelation function will have multiple maxima all of the same height. Look at the array that xcorr gives you as th eoutput, and check how the max function works in MATLAB when there are multiple maxima. Does max report the leftmost maximum if there are multiple maxima of the same height? (I am not a MATLABi and cannot help you on this last point).

Answer 2

I want to add some illustration to good answer of Dilip Sarwate. Below is citation from help of function xcorr:

The cross-correlation estimate between vectors "x" and "y" (of
 length N) for lag "k" is given by

                 N
      R_xy(k) = sum x_{i+k} conj(y_i),
                i=1
 where data not provided (for example x(-1), y(N+1)) is ZERO.

So when xcoor calculate correlation for some lag $k$ (see formula above), some values from $x$ are not participating in the calculations. This is equivalent, this values of $x$ are multiplied by zero values in extended signal $y$. Actually you calculate correlation not for $sin(t)$ and $cos(t)$, but for this signals (I add some additional lag to both signal):

Result of your search is quite valid mathematically, but it is not result for $sin(x)$ and $cos(x)$! See shifted (aligned) signals:

About an actual signals from your sensor. I can advice to do high pass filter to this data before using cross correlation. Usually you do not need to use low frequency part of signals to find good correlation.

Answer 3

Seraph ask me:

Ok i understood so far, i guess at least. The question is, what is the
right thing to do to get the correct shift between two non periodic     
signals? Especially if they look like my sensor data (don't know 
anything about high pass filters, yet, but i will try to apply one). Is 
that kind of perfect alignment even possible within an acceptable amount 
of run time? 

I decide add new answer (due to big length of answer).

If you have 2 signals with equal length it is not possible to find correct shift (see my first answer). There is an important exception to this statement. You can find the correct shift if the signals have regions with zero values at the beginning and the end. More frequent task - to find the correct shift of a small fragment to the other more long signal.

I have prepared a step-by-step explanation of decision this task. I used your code as a starting point. Your task - find position $sigB$ on $sigA$

Ts=0.05;
x = 0:Ts:7*pi;
y = 0:Ts:2*pi;
sigA = sin(x);
sigB = cos(y);
figure 1 
plot(x,sigA,'r',y,sigB,'b');
grid on;

You have to calculate the correlation values for $sigB$ with fragment of $sigA$ for shift with range $0..(length(sigA)-length(sigB))$. You can use any suitable function (eg xcorr from Matlab) but correctly use the results of its work.

[corr,lag] = xcorr(sigA,sigB);
[peaks,l]=findpeaks(corr'+100);   %add 100, as "DoubleSided" options does not work in my version
peaks=peaks-100;     %subtract 100 to get valid values of peaks
figure 2
subplot(2,1,1);
plot(lag,corr,'b',lag(l),peaks,'*r');
grid on
title "maximum of correlation for all lag"
%find indexes of peaks with valid lag
valpeaks=(lag(l) > 0) & (lag(l) < (length(sigA) - length(sigB)));
peaks=peaks(valpeaks);
l=l(valpeaks);
subplot(2,1,2);
plot(lag,corr,'b',lag(l),peaks,'*r');
grid on
title "maximum of correlation with valid lag"

Now find maximum peak. It will be your decision.

figure 3
[~,i] = max(peaks);
shift=lag(l(i));
plot(x,sigA,'r',y+shift*Ts,sigB,'.b');
grid on
title "find good position sigB in sigA"

About real signals. Sometimes you need to use not the usual correlation coefficient, but the normalized correlation coefficient. This is particularly useful when the signals have a different scale. Sometimes you can improve results by using high-pass filtering of signals before calculation of correlation.