3
$\begingroup$

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: figure 1

cross correlation between sigA and sigB

figure 2

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:

figure 2 - With fake offset 5

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: figure 1 - sigA long

cross correlation between sigA long and sigB

figure 2 - sigA long aligned

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):

Signal A is a real signal from my sensor, signal B is a subset of signal A Wrongly aligned signals

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?

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I added the correlation graphs to my question. Matlab max() seems to return the first appearing maximum (i.e. the most left one). So if i get you right, there is nothing i can do about this alignment error offset in cases like these? Or is there another way to align signals with higher reliability. Because it has to be possible in theory, right? $\endgroup$ – seraph Mar 27 '15 at 8:10
  • $\begingroup$ I also added some real sensor data $\endgroup$ – seraph Mar 27 '15 at 8:57
1
$\begingroup$

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): enter image description here

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

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer and your illustrations. I will give it a try asap! $\endgroup$ – seraph Apr 21 '15 at 9:38
  • $\begingroup$ What does Figure1 show exactly? The shifted signals? $\endgroup$ – seraph Apr 21 '15 at 9:44
  • $\begingroup$ @seraph, actual signals for which you calculate correlation with different shift (lag) in your first code example. See citation - "where data not provided (for example x(-1), y(N+1)) is ZERO" $\endgroup$ – SergV Apr 21 '15 at 10:01
  • $\begingroup$ @seraph, Yes it is shifted (aligned) signals. (Sorry for misleading numbers of figures). I will modify slightly my answer. $\endgroup$ – SergV Apr 21 '15 at 10:39
  • $\begingroup$ 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? Sorry for bothering you! $\endgroup$ – seraph Apr 21 '15 at 12:24
1
$\begingroup$

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"

enter image description here

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.

$\endgroup$
  • $\begingroup$ Thank you for your answer. This is as far as i got in my original question. So the answer is that a PERFECT alignment of non periodic signals is not possible with just applying cross correlation, ok. Even after applying a high pass filter to my sensor data, my calculated lag value is +/-100 samples from optimum. Doesn't matter if zero padded or not. $\endgroup$ – seraph Apr 28 '15 at 10:55

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.