# Arduino Cross Correlation?

How can I write lightweight cross correlation code for arduino? I couldnt find any solution. The measurement system contains an ultrasonic sensor and a servo that turns from 45 to 135 degree and measures distance from 4-300 cm. Than i collect data in an array which contains distances with respect to angle. System makes several measurement like this and program finds cross correlation between new and old arrays.

http://www.instructables.com/id/How-To-Make-an-Obstacle-Avoiding-Arduino-Robot/

• Do you want to correlate two real-time signals or a real-time signal with a predefined pattern? How large (in number of samples) is the window over which you want to integrate? May 12, 2015 at 10:18
• signal collected and than cross corr will work. length of signal is 90.
– acs
May 12, 2015 at 11:17
• Could not understand your sentence. Could you please update the question with information about the two signals you want to correlate? Are they known at compile time? Have they to be processed sample by sample during acquisition? May 12, 2015 at 11:49
• I wrote a sparse cross correlator that works with a digital signal sampled on timer values. It was running on a very small microcontroller. If you give us more information about what signal you are correlating I would be happy to post it here May 12, 2015 at 11:52
• There is an ultrasonic sensor.and a servo that turns from 45 to 135 degree and measures distance from 4-300 cm. now i collect data in an array which contains distances with respect to angle.system makes several measurement like this and than program finds corelation between new and old arrays.
– acs
May 12, 2015 at 15:21

Given the time scale of the measurements, performance is not an issue. And since you are not computing in real-time, as the samples are being measured, you can apply the definition of cross-correlation as is, and compute it in a double loop. The only difficulty is figuring out that cross-correlation may not be the proper tool for the job... and finding the right one! My assumption is that you want to estimate a rotation angle between the two measurements.

The mathematical definition of cross-correlation assumes infinite arrays. In practice, cross-correlation is often used to locate a short pattern inside a long signal. In this case, the computation is done only for shifts where the pattern completely overlaps the signal. Then the length of the result is

``````length(result) = length(signal) − length(pattern) + 1
``````

In your case, since your pattern is a previously measured signal, this would give a single-sample result, which is useless.

You could instead compute the integral for all shifts where there is any overlap between the pattern and the signal. This is equivalent to zero-padding the signal. This has the drawback of biasing the result: if your signal and pattern are both featureless (positive constants), you will find a very nice peak at zero shift!

You can remove this bias by subtracting the average from both the signal and the pattern, and correlating (signal − avg(signal)) with (pattern − avg(pattern)). This still carries a bias for “big” features. Imagine for example that, after removing the averages, you have

``````pattern = [  0,   0, −20, +20,   0,   0];
signal  = [−50, +50,   0,   0, −20, +20];
``````

You would expect your correlator to find a good match between the [−20, +20] of the pattern and the [−20, +20] of the signal. The correlation is, however, much better with the [−50, +50] of the signal. You may try to alleviate this by computing a normalized cross-correlation instead, but you will at best make both matches equally good.

My suggestion is that you completely forget about correlations and instead think in terms of “goodness of fit”. Correlations are good for finding scaled and shifted copies of a pattern inside a signal. You are looking for shifted only copies, with no scaling. Your question should be: if you shift the pattern by some amount, how well does it fit the signal? What amount of shift gives the better fit? The canonical answer to all “goodness of fit” questions is to minimize the RMS difference between the two: you compute the sum

``````S = Σ(signal − shifted(pattern))²
``````

Then the RMS difference is

``````RMS(difference) = √(S/N)
``````

where N is the number of samples involved in the sum. The most likely shift is the one that minimizes this error. In practice, you do not need the square root, you just minimize

``````RMS(difference)² = Σ(signal − shifted(pattern))² / N
``````

You can implement this formula as-is, it's completely straightforward. Just beware that N depends on the shift, as it's the length of the overlap. And avoid going to very small overlaps (i.e. large shifts).

Now, if you expand the square inside the sum, you may find that, after all, this is not so far from a cross-correlation... And BTW, all this has nothing to do with Arduino.

• I need both to delay and correlation informations. delay information will be used to estimate displacement and relation will be used to decide importance of estimated displacement (is it realy meaningfull or not). The system will work like ultrasonic radar based dead reckoning. Also I'm trying to implement this link
– acs
May 13, 2015 at 15:30
• You have both informations: 1) the amount of shift that gives the better fit, 2) the RMS difference at this particular shift. May 13, 2015 at 15:48