Fast Median Filter in C / C++ for `UINT16` 2D Array

Question

Does anyone know a fast median filter algorithm for 16-bit (unsigned short) arrays in c++?

http://nomis80.org/ctmf.html

This one seems quite promising, but it only seems to work with byte arrays. Does anyone know either how to modify it to work with shorts or an alternative algorithm?

Answer 1

The technique in the paper relies on creating a histogram with 256 bins for an 8 bit pixel channel. Converting to 16 bits per channel would require a histogram with 65536 bins, and a histogram is required for each column of the image. Inflating the memory requirements by 256 makes this a less efficient algorithm overall, but still probably doable with today's hardware.

Using their proposed optimization of breaking the histogram into coarse and fine sections should further reduce the runtime hit to only 16x.

For small radius values I think you'll find traditional methods of median filtering will be more performant.

Answer 2

Fast Median Search - An ANSI C implementation (PDF) is something for C, it's a paper with the title "Fast median search: an ANSI C implementation". The author claims it's O(log(n)), he also provides some code, maybe it'll help you. It's not better than your suggested code, but maybe a look worth.

Answer 3

std::vector<unsigned short> v{4, 2, 5, 1, 3};
std::vector<unsigned short> h(v.size()/2+1);
std::partial_sort_copy(v.begin(), v.end(), h.begin(), h.end());
int median = h.back();

Runs in O(N·log(N/2+1)) and does not modify your input.