Fast array indexing

[bpmccall]

Hi LabVIEW forums!

I've got an application that builds a 3D 'datacube' of size ~360x360x30 by indexing a continuously acquired 8MP image. After optimizing as far as I know how, I can only create my data cube once every ~200ms. I need to be much faster, so what are my options for further optimization? I'm wondering if I need to investigate the use of GPUs or FPGAs...

The large arrays take a lot of memory and the forum doesn't allow me to post - so I've included a link to my VI.  Any help would be much appreciated. 

https://docs.google.com/leaf?id=0B6On7iVFSmqqYTUwZjkyN2MtYzE4Zi00MzllLTgwZjItNTIwMWFlZjdlNmE2&hl=en

Noah

[GregSands]

One simple way to speed it up a lot is to only index the 2D image that you want to view, something like this:

If you do need the whole 3D array, of course that won't work.  It might help to know a little more about the mapping between the 2D image and the 3D output.

[LVNoah]

(posting for bpmccall)

Thank you for your response. Unfortunately, the entire datacube must be created in order to allow for real-time analysis later in the application. Also, the mapping between the 2D and 3D data has no simple pattern, so blocks or chunks can't be indexed. Any more ideas??

Noah

[GregSands]

There must be some sort of mapping, which is what's in the array at the top saying which values to index out.  But this array is written for the 1D "reshaped" data array, and I was essentially wondering how that mapping was constructed?  Without knowing that, I'm not sure there is much of a way to speed things up faster.

[BruceAmmons]

I agree with GregS.  Without an explanation of how the mapping works, we can't really help much.  If you need the entire 3D cube mapped for every image, there may not be an easier or faster way to do it.

How fast are you trying to go?  On my computer, it averages about 130 msec per iteration.  If you had a high speed quad, it would probably be under 50 msec per iteration.

I could see running this through an FPGA card and getting really fast iterations.  Since the lookup indices are fixed, they could be hard coded.  You could probably stream the image to the FPGA as it streamed the converted 3D cube back to you.  You could get a PCI-7811R for $1500 and really fly!  It would be interesting to program this one.

Bruce

[LVNoah]

Hi guys, Thanks for your responses. I'll describe the project a little more (http://www.opticsinfobase.org/abstract.cfm?URI=oe-17-15-12293). Briefly, an image of a sample is projected onto ~1000 long thin mirrors. Each mirror sends that image information through a prism and onto a different area on the CCD, depending on the angle of that facet. After some calibration, for a given spatial element in our sample, we can determine where on the CCD any wavelength will fall. 

Our goal is a datacube containing several image pages - one for each wavelength we collect. Currently just reconstructing the data is only at around 5 FPS, and I'd also like to analyze this 'hyperspectral' image data in real-time. 

Each pixel in the mapping array represent a pixel location (index) in the raw data vector (4872*X + Y). The first pixel of the mapping represents the first pixel in page one of the datacube (page one = image for wavelength one). Because the tiny mirror facets and the camera are stationary, you are correct that the mapping vector is fixed.

I'm open to any suggestions. I've never used an FPGA. Bruce, could you explain your response a little further?

Noah

[BruceAmmons]

Okay, now it makes a lot more sense.  A lot more interesting, too!

I was looking at FPGA options, and I am not sure how well it would work.  The main problem is that FPGA programs can only access limited amounts of memory at one time.  I think the limit is around 80k bytes, perhaps up to 200k.  That wouldn't be enough to store your lookup table or the source image.  There would have to be some method for paging sections of the image in and out of the FPGA memory, which is beyond my experience.  If there was a somewhat predictable pattern to the lookup table, you might be able to match a section of image to a section of lookup table somehow.

Bruce

[GregSands]

I had a quick look at this again.  By reshaping the lookup table to 3D, and then by reconstructing row/column indices rather than 1D lookups, it's more obvious that there are a few patterns in your lookup table which make it fairly easy to speed up the indexing.  For example, each page is a single pixel shift from the previous, so it's possible to pull all of the "pages" out at once, taking values from 29 consecutive columns.  Also, the lookup table is usually taking consecutive pixels, so we can look for where those pixels come from the same column, but that changes every so often.

The attached code takes things, on my oldish 2-core machine, from ~140ms to ~35ms.  The 3D reassembly is highly parallel, so an 8-core machine would probably get to less than 10ms.  Basically, the speedup is a result of taking 2D blocks out of the input array, rather than assembling it point-by-point.  The 3D array is assembled in a different rotation to what you originally had, such that the "page" is now the last index, but that's easy to cope with.

It appears to me that there is a slight rotation in your optics, which causes the appropriate pixel to keep shifting column.  It looks as though correcting that would enable you to directly reassemble the image chunks into the 3D array.  As far as I can tell, that would probably be the only way to get any significant further speedup.

Note, I've pulled your data and lookup table out of the VI to make it small enough to post.  Of course you can save the new Lookup Table rather than compute every time it is run.

[LVNoah]

WOW!

Really great answer Greg!

Because of distortion in our image (from our optics) I didn't think it was possible to pull out chunks of data like that. It might take me a while to actually understand the algorithm.

Also, I had never heard of OpenG. What a great resource; thanks for drawing my attention to that!