2

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/

5
  • 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? – Edgar Bonet May 12 '15 at 10:18
  • signal collected and than cross corr will work. length of signal is 90. – acs May 12 '15 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? – Edgar Bonet May 12 '15 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 – benathon May 12 '15 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 '15 at 15:21
5

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.

2
  • 1
    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 '15 at 15:30
  • 1
    You have both informations: 1) the amount of shift that gives the better fit, 2) the RMS difference at this particular shift. – Edgar Bonet May 13 '15 at 15:48
2

This will work. No Arrays or difficult stuff about cross blabla. The code is in within 4-5 micros

int mic1 = 2;// using leonardo for external interrupts on theese pins.
int mic2 = 3;
int mic3 = 7;

volatile unsigned long tid1 = 0; //Var to store time-stamp in micros in.
volatile unsigned long tid2 = 0;
volatile unsigned long tid3 = 0;
volatile int stop1 = 0;//Flags in interrupts to not trigger again. 
volatile int stop2 = 0;
volatile int stop3 = 0;


void setup() {
  
  
  pinMode(mic1, INPUT);
  pinMode(mic2, INPUT);
  pinMode(mic3, INPUT);
  pinMode(11, OUTPUT);//Eg Buzzer to beep when all triggs ar OK!

  Serial.begin(9600);
  attachInterrupt(digitalPinToInterrupt(mic1), trig1, RISING);
  
  attachInterrupt(digitalPinToInterrupt(mic2), trig2, RISING);
  attachInterrupt(digitalPinToInterrupt(mic3), trig3, RISING);

}


void loop() {


  if (stop1 == 1 && stop2 == 1 && stop3 == 1) {
  

    stop1 = 20;
    stop2 = 20;
    stop3 = 20;

    


    delay(250); //ECHO-Delay.

    tid1 = 0;
    tid2 = 0;
    tid3 = 0;

    stop1 = 0;
    stop2 = 0;
    stop3 = 0;


  }
}

void trig1() {

  if (stop1 == 0);
  tid1=micros();// How to write this the hardcore way adressing timer1 to get the value based om clockcycles i dont know. Jus
  tid1=tid1;
  
  stop1 = 1;


}

void trig2() {

  if ( stop2 == 0);
  tid2=micros();
  tid2=tid2;
  
  stop2 = 1;

}


void trig3() {

  if ( stop3 == 0);
  tid3=micros();
  tid3=tid3;
  
  stop3 = 1;

}
2
  • You've got something odd going on with if (stop1 == 0); and similar lines. Note the semicolon. – timemage May 30 at 20:32
  • 1
    I don't see how this is even remotely related to the question, even ignoring the unusual code. – Dave Newton May 30 at 20:59

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.