do/undo fft shift?

[colman77]

Hi,

I just finished porting some code from Matlab to Labview.  There are a couple of 2D FFT's in the code... the matlab version computes the 0,0-centered FFT, then uses fftshift() to obtain the middle-centered FFT.  It then makes use of BOTH versions (does its own calculations with one, interfaces to some other code with the other).

Right now, I'm replicating this in Labview by doing 2 FFT's for every 1 in Matlab, one with "shift?" true and one with "shift?" false.  Obviously it is quite a bit slower!

I thought I'd ask here if anyone has replicated the shift code before I tried it myself? It will greatly speed up my program... and that's the whole reason I took on this little code-porting project in the first place!  Help would be greatly appreciated.

Thanks,

Colin

[Mellobuck]

Hey Colin,

I am a big LabVIEW fan and constant user, but I don't think anyone would claim that LV is faster than Matlab at 2D matrix operations, like the FFT - that is what Matlab was created to do. However, I am happy to be corrected.

However, could you post a screenshot or the code? Quite often the ability to speed things up in on the program architecture side, not the settings on the functions/subVIs.

Regards,

Mello

[colman77]

I agree completely, Mello.  I actually don't have Matlab available (although I've used it extensively before), so that's why I'm porting the code.  I don't think I explained my problem well enough.

In the Matlab Code:

buf1ft = fft2(buf1); % takes the 2-D FFT, DC at (1,1)
buf1ft_shifted = fftshift(buf1ft); % Puts DC in center of array

Note that fftshift() doesn't actually do a transform, it just rearranges the data so that DC is in the middle.

buf1ft and buf1ft_shifted are used in separate places in the code later on.

In labview, I've had to replicate this by doing 2 separate FFT's because there's no fftshift VI (to the best of my knowledge), although it's an option on the FFT VI:

Performing the second FFT with shift=true is a lot slower than copying and moving around the data from the first FFT so that DC is centered.

I was just hoping someone has been here, done this before.  Writing the labview code to shift around the data isn't impossible, it's just a pain because I don't know what it does when the sizes are even/odd, etc. and I would like to save myself some time.

Message Edited by colman77 on 07-23-2009 02:18 PM

[Darin.K]

I do not want to discourage the LV solution to this problem, but as a fan of open source software I am curious if you have considered Octave as a Matlab replacement?  In general I agree with the previous post, LV probably will not beat Matlab, but if you do things properly you should get reasonable performance.  Hopefully somebody knows what properly means in your case since I am curious to know myself.

[colman77]

The application I'm working on is not suitable for Matlab (nor Octave).  This code is part of a much larger solution.  I'm interfacing with a camera and running some calculations live @ about 15fps, which is why I'm concerned about execution speed.  I don't think Octave (nor Matlab) can do this (show live image, do calculations, show results, output HTML report, etc).  Even if they could, porting all the Labview code and figuring how to interface the cameras with Octave (or Matlab) would be a monumental task, far larger than doing some matrix math in Labview.

The Matlab code is "efficient subpixel image registration."  I realize this can be done by VIs in NI's vision library but we don't have $4000 to throw down for it.  2 days of my time is worth a lot less, unfortunately 🙂

Oh and I don't see how Matlab is going to compute an FFT significantly faster than Labview.  It seems likely to me that they use the same algorithms, perhaps even the same FFT libraries.  Maybe Matlab's execution system is faster, but as I said before the sophistication provided by Labview's execution system and the extra capabilities of Labview are necessary for this application. 

For the record, Labview reports that it takes me about 12ms to calculate a 512x512 FFT from a ~55x55 ROI.  Running on an Intel Core 2 6600 @2.4Ghz, 2GB ram.

Message Edited by colman77 on 07-23-2009 03:22 PM

[Mellobuck]

It looks like the example that ships with LabVIEW "2D FFT of a Pulse.vi" does the shifted and non-shifted the exact way that you are, with two FFT nodes. So, I am not sure there is a faster solution.

Does your install of LabVIEW have the MathScript node (under structures in your function pallette)? I tested your matlab code above and it executed just fine. The mathscript node itself is not very fast, so you'll have to do a compare and contrast with your code to see if it is worth it.

I'd also like to add scilab to Darin. K's Octave suggestion above, another free matlab compatible program.

-Mello

[colman77]

Thanks for investigating, Mello... too bad.  I'll probably just write a C routine that juggles around the 4 quadrants of the FFT (since it appears that's all fftshift does) and compile it into a dll.

A little more on matrix/array computation speed... I haven't done much with arrays in Matlab, Octave, etc., so I don't have a very good mental benchmark.  That being said, I was impressed by Labview's computation speed.  I'm acquiring an image, performing several element-wise calculations on a 16-bit 640x512 image, then doing fairly intense calculations on a region of interest that's around 100x200 pixels.  These include image registration via phase-shifting FIR filter and correlation (basically a guess-and-check for loop, runs 30 times), 2 2D FFT's, magnitude scaling, and a whole host of other stuff.

The advantage of Labview is that by using queues and multiple while-loops, you can separate tasks and have htem run in parallel.  The disadvantage is it doesn't seem very good at splitting up calculations on a large array and spreading it over multiple cores.

Matlab, on the other hand, is very good at breaking up large calculations and spreading htem over multiple cores.  But in my case I'm spending a lot of time waiting around for my frame grabber to get the image.  With queues, Labview will continue to do stuff while the camera is transmitting.  I don't think Matlab would do this. 

Before I knew all that, I had one giant while loop that ran at about 8fps... CPU usage was never above 65% or so.  After separating the program into 2 loops, the execution speed was limited by the camera's framerate (fastest camera I have is 30fps).   (that was before I put in image registration and some other stuff, so it's back down to 15fps now.)  CPU usage is at 100% all the time.

[Mellobuck]

I completely agree, I myself am a Matlab to LabVIEW convert. Matlab was great back in my research days (although I was still using LabVIEW for DAQ), but for my customer solutions now, LabVIEW takes the cake. LabVIEWs advantages that you mentioned are absolutely correct - being able to readily create parallel operations is huge strength, especially with the reduced development time.

Well done on implementing the parallel, queued executions, that is a big part of leveraging the power of LabVIEW

I do know that using the DLL call you mentioned will be MUCH faster than a Mathscript node (from personal experience, good luck with the project!

-Mello

[jl8987]

Hi Colman,

I'm working on the same issue with needing an FFTSHIFT operation for the exact same reason as you!  I'm also grabbing images from a camera and processing them live.  Did you ever find a workaround?  I don't want to write my own fftshift if I can avoid it, although I did write a version for GPU / CUDA programming.  I just never made own in LV.  

Please me know how things turned out.  By the way, maybe you can let me know what kind of imaging you're doing.  Maybe we can help each other out?  

-JL