Arduino Stack Exchange is a question and answer site for developers of open-source hardware and software that is compatible with Arduino. It only takes a minute to sign up.
Sign up to join this community
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/
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.
