Fast Array Manipulation and Data Reorganization

I am generating a 512x512 image on data collected from a sample, and am attempting to sum together all of the datapoints into bins to generate the image. The size of the dataset per image is ~62MB, and I need to compile it into an image quickly (realtime, if achievable). Due to how my scanhead works, some pixels are sampled a lot, but most are sampled less than 20 times. Since some pixels in my image are sampled in excess of 5000 times, making a 262144x5000 matrix padded with 0's and summing along the second dimension is resource prohibitive. I looked into sparse matrices to deal with this issue, but I found that creating sparse matrices is a slow process (whether it's through the sparse command, or through instantiating a sparse matrix and filling it).

Instead of relying on sparse matrices, I group the pixels together by how many times they were sampled; I can create just a few matrices and remain efficient. Specifically, I create exactly 3 matrices and sum() all samples together into their pixel bins. I have successfully generated a script to group pixels together, perform 3 separate sum() statements, and then reconstruct the image afterwards. The algorithm is relatively simple and robust, but is lukewarm in terms of speed. I clock it at 95ms to perform the grouping and summing each time I send it a dataset. Surprisingly, the slow step is organizing the vector of data into the three temporary matrices to be summed. This simple reorganization accounts for 80ms of time!

In a previous slow step, I have cataloged all of the relevant RawDataChannel datapoints with the index vector array *SamplePixelGroupDataIndex, and where these datapoints should be sent into the *SampleImageArray temporary matrix with the index vector array *SamplePixelGroupMatrixIndex. I have to think that I'm handling the data in an incorrect manner, because this data reorganization step takes ~10x longer than it does to actually sum the data! Is there a faster or more correct way to reorganize data & matrices than how I am doing it?

Thanks!

HighSampleImageArray(HighSamplePixelGroupMatrixIndex) = RawDataChannel(HighSamplePixelGroupDataIndex);
MidSampleImageArray(MidSamplePixelGroupMatrixIndex) = RawDataChannel(MidSamplePixelGroupDataIndex);
LowSampleImageArray(LowSamplePixelGroupMatrixIndex) = RawDataChannel(LowSamplePixelGroupDataIndex);

Answer 1

[Matt J]

Sounds like you should just be using ACCUMARRAY. Make a table of the form [I,J,S] where column vectors I and J are lists of pixel coordinates and S are the sample values. Then do

 accumarray([I,J],S)

In general though, binning operations are difficult things to accelerate. 95 ms doesn't sound all that bad.

[Ryan Muir]

Thanks for your answer! I was very excited to see that there was a hardcoded function that already did what I wanted to do! I gave it a test run by feeding it some randomly generated data and indices, and found that it was taking more than 250ms to complete. Sorting my array prior to evaluation dropped it down to around 170ms. I was a bit surprised that it performed much worse than my matlab script. I suspect that my script comes out ahead because I've already figured out how to organize all of the data prior to my function.

It still feels silly to me that reorganizing the data can take 10x longer than summing it. I don't have any experience with creating mex functions, but would creating my own mex function expedite this data rearrangement?

[Matt J]

It still feels silly to me that reorganizing the data can take 10x longer than summing it.

Not sure where your intuition comes from. Moving things around in memory is always the hardest/slowest thing software does.

[Ryan Muir]

I didn't realize! Thank you!

That accumarray function is just exactly what I needed, though. I do have a jacket license, and furtunately, accumarray is implemented in jacket. It is indeed quite fast on the GPU. I tried thinking of keywords and searching around in matlab for a while, but I didn't come across accumarray.