Cross Correlating Road Grade information

>
>martini skrev:
>> Ok, so I will be more specific.
>OK, another numerical detail to keep track of. How do you interpolate
>the measurements? How many interpolated points between each
>measurement? Those kinds of things. No need to answer them
>now, but at some point one might get back to these questions.


interpolation is kept to a minimum...sampling at 50hz, driving at like
25mph...3 cm is about the average distance between samples anyway.


>Wearing my "devil's advocate" robe: What would happen if you
>made several reference passes around the track? How consistent
>would the refernce data be between lapses?


the system is a military grade GPS/INS sytem...if i were able to drive
exactly around the same path...it would tell me that

this sensor suite can be considered a 'truth sensor' for all intensive
purposes




>OK. My only comment hee is that you ought to make sure this
>correlation coefficient is normalized to the [-1 1] range, or
>possibly absolute value to the [0,1] range.


for the non-fft routine, the correlation is from -1,1

my problem with the FFT on could be the fact htat it is not
normalized...however Im not exactly sure how to do that



>
>As a general rule, getting things right is usually more important
>than getting things fast.

if this is going to be of any use, it has to work real-time...but for now,
post processing I can do it however i want





>
>Well, I would suggest you spend a little bit of time getting to know
>the computational routines. I don't know how much time you have
>left for this project, but spending a day or two with the FFT and
>XCORR functions now might save you lots of time later.
>
>What I would do in your situation, was to focus on one of the
>examples that work, and use it as the referennce data set.
>Test the various techniques on that data set, see the differences
>between the estimators, get some code up that runs fast.
>
>Only after all that is done do you get back to the other random
>samples. Then you can set up a processing loop that computes
>the correlation coefficients and match them to the reference.
>
>It seems there are two main questions that would decide
>how to proceed:
>

I have about a 2 week period to nail this out


I will keep workin on it

martini wrote:
> 
> just as a follow up:
> 
> Sample data is   5447  data points
> track data is   56366  data points
> 
> so the question is...where in the 56366 data points does my 5447 data
> points match the best...and how can i calculated this in the most
> efficient way

How about classifying the sections of the track. Like fingerprint
identification. For instance if you have 3 classifications Then for each
5447 window on the track it will be classified as generally going
up-hill, Generally going down-hill or generally flat.  Then determine
which classification a sample matches. This might reduce the
calculations by 1/3. 
	That may not be the best system of classification. The data itself may
reveal better features. Things like potholes in a road come to mind.

-jim

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

it has to eventually be used on any road, not just the track.

i think once i get this fft stuff ironed out i will be in buisness

ok i have included some plots this time.  what you will see are the
following:

http://www.personal.psu.edu/rdm186/random_images/roadgradeplots.jpg

the first is a plot of the road grade measurements...exactly where I am
starting.  You will see the track in red, and the sample in blue.  Just
from visual inspection, you can see where they are supposed to line up -
The point circled was verified with my 'working' algorithm which I posted
a link to before.

I apologize if the plot is not crystal clear...so I will try to clafify. 
Using the FFT method (xcorr in matlab) the comes back with a maximum
correlation which corresponds to the starting point circled in blue
(towards the left)  which is no the same as the 'correct start' point i
have circled in black.  just from looking at it, you can see it is wrong.

Here i have the actual plot of the correlation:

http://www.personal.psu.edu/rdm186/random_images/xcorr_method.jpg

you can see that it is actually extracting th emaximum value of the
correlation, however this 'maximum' seems to be a false maximum, as the
true 'max' is what I have circled in blue.

NOW THE INTERESTING PART.

if BEFORE I do the FFT, i take the sample set, and subtract out its
mean...and take the template and subtract out its mean...and re-do the
correlation, everything works out....this is picture below...

http://www.personal.psu.edu/rdm186/random_images/xcorr_method_meanout.jpg

note the difference in the correlation curve.


whats the real pain is that this subtracting out the mean thing doenst
work for all the data sets (only 2 of the 6 I have)


any clues?

is there a way i can subtract out 'local means' or something?

martini wrote:

   ...

> is there a way i can subtract out 'local means' or something?

Given any set of numbers, what is the difficulty computing the mean of 
the set?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"martini" <rdm186@psu.edu> wrote in message 
news:OcKdnSw_88nLj9XZRVn-uw@giganews.com...

> is there a way i can subtract out 'local means' or something?
>

You don't need to.  See my other post ...

Fred 

martini skrev:
> >
> >martini skrev:
> >> Ok, so I will be more specific.
> >OK, another numerical detail to keep track of. How do you interpolate
> >the measurements? How many interpolated points between each
> >measurement? Those kinds of things. No need to answer them
> >now, but at some point one might get back to these questions.
>
>
> interpolation is kept to a minimum...sampling at 50hz, driving at like
> 25mph...3 cm is about the average distance between samples anyway.
>
>
> >Wearing my "devil's advocate" robe: What would happen if you
> >made several reference passes around the track? How consistent
> >would the refernce data be between lapses?
>
>
> the system is a military grade GPS/INS sytem...if i were able to drive
> exactly around the same path...it would tell me that

Sorry for not being clear. I meant to ask how consistent the reference
data sets would be ebetween lapses if you don't drive in exactly
the same track. What would the cross correlation be between
diffrent passes along the same sections of track.

In Formula 1 terminology, there is an 'ideal' track around every race
cirquit, where everybody try to drive. How do your templates show up
if you do several lapses, some in the ideal track, others outside.

> this sensor suite can be considered a 'truth sensor' for all intensive
> purposes

No sensors show the 'truth'. The best one can hope for is a
sensor that gives consisten data with low variance. But the
deviations are there between experiments. Get an impression
of how your sensor suite operates, and get an idea of what
to aim for in your analysis.

> >OK. My only comment hee is that you ought to make sure this
> >correlation coefficient is normalized to the [-1 1] range, or
> >possibly absolute value to the [0,1] range.
>
>
> for the non-fft routine, the correlation is from -1,1
>
> my problem with the FFT on could be the fact htat it is not
> normalized...however Im not exactly sure how to do that

Me neither.

> >As a general rule, getting things right is usually more important
> >than getting things fast.
>
> if this is going to be of any use, it has to work real-time...but for now,
> post processing I can do it however i want

Sure. But before you try to get the thing up and running real time,
you need to know what it is supposed to do and how to do it.
It seems you are in the phase of finding out those things now.

...
> >It seems there are two main questions that would decide
> >how to proceed:
> >
>
> I have about a 2 week period to nail this out

If you had four weeks, I'd suggest you spent a couple of days sorting
out the correlation methods. Seems you don't have time to spare.

> I will keep workin on it

Rune

martini skrev:
> ok i have included some plots this time.  what you will see are the
> following:
>
> http://www.personal.psu.edu/rdm186/random_images/roadgradeplots.jpg
>
> the first is a plot of the road grade measurements...exactly where I am
> starting.  You will see the track in red, and the sample in blue.  Just
> from visual inspection, you can see where they are supposed to line up -
> The point circled was verified with my 'working' algorithm which I posted
> a link to before.

Well, I wouldn't be surprised if you need to subtract the mean from
both data in order to get this stuff to work.

> is there a way i can subtract out 'local means' or something?

Here is what I would try:

x : Sample (blue) data, N points long.
y : Template (red) data, M points long, M>>N.

1) Subtract the mean from x once and for all.
2) Extract an N-point frame from y, call it y'.
3) Compute the mean of y', and subtract it from y'.
4) Compute the 0'th lag correlation coefficient Rxy'
    between x and y', normalized to |Rxy'| = [0,1].
5) Store Rxy'
6) Advance k points in the main sequence y
7) Repeat from 2)

The algorithm above might work, but you would probably
have to abandon standard functions like XCORR.
I usually find it far easier to implement things from scratch
instead of using more or less awkward standard
functions.

The above algorithm can easily be fine-tuned to work very
fast, if it turns out to work. As I said in a different post,
there is a time for doing things right and there is
a time for doing things fast. Don't worry about real-time
performance for now. If that was a requirement in the
current part of your project, you wouldn't be using 
matlab.

Rune

Rune Allnor skrev:
> martini skrev:

> > is there a way i can subtract out 'local means' or something?
>
> Here is what I would try:
>
> x : Sample (blue) data, N points long.
> y : Template (red) data, M points long, M>>N.
>
> 1) Subtract the mean from x once and for all.
> 2) Extract an N-point frame from y, call it y'.
> 3) Compute the mean of y', and subtract it from y'.
> 4) Compute the 0'th lag correlation coefficient Rxy'
>     between x and y', normalized to |Rxy'| = [0,1].
> 5) Store Rxy'
> 6) Advance k points in the main sequence y
> 7) Repeat from 2)
>
> The algorithm above might work, but you would probably
> have to abandon standard functions like XCORR.
> I usually find it far easier to implement things from scratch
> instead of using more or less awkward standard
> functions.
>
> The above algorithm can easily be fine-tuned to work very
> fast, if it turns out to work.

Actually, I found this to be an interesting algorithm, so I
jotted down the sketch of a C++ MEX program appended
below.

Check the matlab documentation about how to compile
and link it. Do note that I have NOT tested or debugged it
and run-time error checking is absent, so you shouldn't
really regard it as more than an advanced pseudocode
to elaborate on what was said above.

If you have a go at compiling and testing this code,
it might interest you to know that I often spend lots
of time debugging index limits around loops. That is,
I often get the non-trivial index limits in loops wrong.

Have fun. I'd be very interested in seeing how things
turn ot if you get this algorithm to work, regardless
of whether you use my program or something else.

Rune

////////////////////////////////////////////////////////////////////////////////////////////////
#include "mex.h"
#include "matrix.h"

extern void __main();

void mexFunction(int nlhs, mxArray *plhs[],
                 int nrhs, const mxArray *prhs[])
/*
 *  [rxy] = NlCorrMex(x,y)
 *
 *   x     Data series #1. N by 1 column vector.
 *   y     Data series #2  M by 1 column vector.
 *   rxy   Correlation sequence between x and y, rxy = [-1,1].
 *         max(N,M) by 1 column vector.
 *
 *   The function computes the "nonlinear covariance"
 *   between sequences x and y. The mean is removed from
 *   the shorter sequence, and the residual is normalized
 *   so the L2 norm equals 1. Frames of equal length
 *   as the shorter sequence are extracted from the longer
 *   sequence. The frames have their means subtracted
 *   and are normalized on a frame by frame basis.
 *
 *   An effort is made to make a fast algorithm.
 */

{
   /* Check number of input arguments */
   if (nrhs~=2)
   {
      mexErrMsgTxt("Need exactly two input arguments!");
   }

   for (n=0;n<2;n++)
   {
      if((mxIsNumeric(prhs[n])==false)||(mxIsComplex(prhs[n])==true))
      {
         mexErrMsgTxt("Arguments must be real-valued numbers.");
      }
      if (mxGetN(prhs[n])~=1)
       {
         mexErrMsgTxt("Arguments must be column vectors.");
      }
   }

   int N = mxGetM(prhs[0]);
   int M = mxGetM(prhs[1]);
   int n,m;

   double *xx = mxGetPr(prhs[0]);
   double *yy = mxGetPr(prhs[1]);
   double *tp;

   if (N>M)
   {
      n = M;
      M = N;
      N = n;
      tp = xx;
      xx=yy;
      yy=tp;
   }

/*
 *    The pointer xx now points to the shorter data sequence
 *    and yy to the longer. N contains the number of samples
 *    in xx and M the number of samples in yy.
 */

/*
 *     Allocate internal work space.
 */

   double *x = new double[N];

/*
 *     Allocate return variable
 */

    plhs[0]= mxCreateDoubleMatrix(M,1,mxREAL);
    tp = mxGetPr(plhs[0]);

/*
 *     Initialize work spaces.
 *     The shorter time series.
 */

   double mean = 0;
   double variance = 0;
   double t0;

   for (n=0;n<N;n++)
   {
      mean += xx[n];
   }

   for (n=0;n<N;n++)
   {
      variance += (xx[n]-mean)*(xx[n]-mean);
   }

   t0=1/variance;

   for (n=0;n<N;n++)
   {
      x[n]=(xx[n]-mean)*t0;
   }
/*
 *   The shorter data series is now prepared.
 */

/*
 *     Initialize work spaces.
 *     The longer time series.
 */
   for (n=0;n<N-1;n++)
   {
      mean += yy[n];
   }

   for (n=0;n<N-1;n++)
   {
      variance += (yy[n]-mean)*(yy[n]-mean);
   }

   t0=1/variance;
/*
 *   The longer data series is now prepared.
 */

/*
 * The main loop. At entry, the variables 'mean' and 'variance'
 * contain data for the sequence of length N-1 ending at y[n+N-2].
 * Update the 'mean' and 'variance' variables before computing
 * the clocal covariance. Remove the contribution of y[n] before
 * exiting the loop.
 */

   t1 = 1.0/((double)N);

   for (n=0;n<M-N+1;n++)
   {
      mean = mean + t1*yy[n+N-1];
      variance = variance + t1*(yy[n+N-1]-mean)*(yy[n+N-1]-mean);

      t0 = 1/variance;
      tp[n]=0;
      for (m=0;m<N;m++)
      {
         tp[n] += t0*x[n]*(yy[n+m]-mean);
      }

      variance = variance - t1*(yy[n]-mean)*(yy[n]-mean);
      mean = mean - t1*yy[n];
   }

/*
 *  Handle trailing N-1 samples in the correlation sequence.
 */
   for (n=M-N+1;n<M;n++)
   {
      t0 = 1/variance;
      tp[n]=0;
      for (m=0;m<N-(M-N+1)-n;m++)
      {
         tp[n] += t0*x[n]*(yy[n+m]-mean);
      }

      variance = variance - t1*(yy[n]-mean)*(yy[n]-mean);
      mean = mean - t1*yy[n];
   }

/*
 *     Release allocated memory
 */
   delete [] x;

   return;
}

"martini" <rdm186@psu.edu> wrote in message 
news:teKdnfTAYtRgYdrZRVn-hg@giganews.com...

>
> I have about a 2 week period to nail this out

Then, in the interest of time, set aside the FFT methods and do the 
correlation in the time domain.  You don't need to cut up the sequences if 
you have all the data.  Just do one correlation across all the data.

You will likely run into things that need to be done anyway like removing 
the means.
With one record, that's easy.

Fred