Cross Correlation Study Notes SP2010
Contents
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.
