Stack of 64 2D arrays - get median 2D array out of it

[noxus]

Hello all, 

I've got a sensor - you can compare it with an image sensor - that takes values into a 2D array. The dimension of this 2D array 1960*2588.

In total I need to acquire 64 of these 2D arrays, resulting in a 3D array of 64*1960*2588

I need to get the median 2D array [1960*2588] out of these 64 2D arrays. 

What would be the fastest way to do this? 

I've attached a vi with two possible implementations I've created but it takes almost 8 seconds to complete. 

One of the implementations fails with 'not enough memory to complete this operation'. 

I'm convinced there are better ways to do it, but analysis and filtering is not my strongest competence... I'm hoping so of you can help me or point me in the correct direction! 

Looking forward to some suggestions on how this can be improved. Thanks in advance for all the suggestions!

Note: I'm limited to work in LabVIEW version 2014 SP1 32 bit

[GerdW]

Hi noxus,

do you really need the Median (and not the Mean)?

To calculate the Median you need to sort each of those 1960×2588=5072480 subarrays of 64 elements and pick the center element (at index 31 or 32) - this will take a while. Calculating the mean probably is much faster and less CPU demanding…

You might parallize the outer loop to utilize more CPU cores. On a 8-core CPU the execution time decreased from ~10s to <2s…

(And/or use a faster computer.)

[noxus]

Hi GerdW, 

Thanks for your reply. Yes, unfortunately I do need the median, and not the mean value.

I have no experience with parallizing loops, but I will certainly look into it - something to learn for me 🙂

Thanks again - I will post it when I have some success with this method. 

Kind regards

[noxus]

Configuring the parallelism did indeed reduce the processing time from 7.6 to 1.3 seconds.

This helps a lot...

[alexderjuengere]

---

wrote:

Configuring the parallelism did indeed reduce the processing time from 7.6 to 1.3 seconds.

This helps a lot...

---

so, hit the Kudo Button underneath Gert's post 

[GregSands]

One other option if you happen to be using the Vision module (and IMAQ images rather than arrays) is the IMAQ Compute Median Image vi, which takes an array of images and returns the median image.

[k_tunsten]

Thanks GregS for the suggestion. 

Unfortunately this function is not available in the 2014 version which I'm using!

[altenbach]

Another problem is that you are changing representation. You definitely don't need DBL for the output. You can make an U8 median that will probably be faster than a DBL median and will reduce the size of the result 8x. (actually, you might need 9 bits, but an 8 bit approximation to the median is probably sufficient).

There are only 256 possible input values, so even faster median algorithms might be possible. Many years ago, we had a "median" coding challenge (page no longer available?) and if I remember right some were about twice as fast as the NI median.

[altenbach]

---

@GerdW wrote:

To calculate the Median you need to sort each of those

---

Not quite. Only a partial sorting is needed, e.g. as implemented in quickselect. 

[GregSands]

---

There are only 256 possible input values, so even faster median algorithms might be possible. Many years ago, we had a "median" coding challenge (page no longer available?) and if I remember right some were about twice as fast as the NI median.

---

I had the same thought, and tried using a copy of the "median coding challenge" code that I had modified for integers - perhaps because the number of values is fairly small (64), that wasn't any faster.

But your comment about the small number of values gave me an idea - the quickest median is probably to use a histogram method, and indeed that's the quickest I found (about a 2-fold further improvement).  This code would need changing slightly for stacks >256, and there may be other tweaks to get a little more speed, but this doesn't sort the inputs, and only steps through them once, so should be close to linear speed.