Cross Correlation Study Notes SP2010

Cross Correlation Methods

If we test every pair of (method, location), that gives us eight possible combinations:

	Naive	FFT
FPGA	.	.
sbRIO Processor	.	.
PC LabVIEW	.	.
PC Matlab	.	.

Naive Cross Correlation

Iterate over each sample in array X and multiply by each sample in array Y. O(n^2) operations.

FFT Cross Correlation

Reverse one array, pad both to 'length(X) + length(Y) - 1' with zeros, take the FFT of both, multiply, and take the inverse FFT. Seems much more complex than the naive algorithm, but has a lower order overall:

FFT of each sample is O(N log N) Multiplying the two FFTs is O(N) The inverse FFT is O(N log N)

So the resulting algorithm is O(N log N), and presumably becomes more efficient than the naive algorithm at some sufficiently large N.

On the sbRIO

Has the advantage that data can be analyzed immediately.

On the FPGA

Executes with the speed of dedicated hardware, but may require a lot of chip space (possibly too much).

On the Processor

We have to transfer the data via DMA, but then a conventional iterative algorithm can be used to compute the cross-correlation.

On the PC

Has to deal with network latency before analyzing the data.

LabVIEW

We're already receiving some sort of communications from the robot, so it shouldn't be too hard to add more and do the processing on the computer. Depending on the sample rate, the data throughput might be acceptably fast. The big issue is probably going to be latency.

Matlab Integration

Similar to the LabVIEW method, but we use LabVIEW's Matlab integration to offload the cross-correlation work. Has all the disadvantages of the LabVIEW method, but it may be faster on the computations if Matlab's algorithms are more heavily optimized.