Fast media filter in C ++

Question

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

http://nomis80.org/ctmf.html

This seems pretty promising, but it looks like it works with byte arrays. Does anyone know how to change it to work with shorts or an alternative algorithm?

Answer 1

The technique in the article is based on creating a histogram with 256 cells for an 8-bit pixel channel. To convert 16 bits per channel, a histogram with 65536 cells is required, and a histogram is required for each image column. Increasing the memory requirements by 256 makes this a less efficient algorithm in general, but is probably possible with today's hardware.

Using his optimization of dividing the histogram into coarse and small sections, it is necessary to further reduce the execution time by 16 times.

For small radius values, I think you will find that traditional methods of median filtering will be more efficient.

Answer 2

Here (PDF) is something for C, it's a document called "Fast Median Search: Implementing ANSI C". The author claims that O (log (n)), he also provides some code, maybe this will help you. This is not better than your suggested code, but maybe worth a look.

Answer 3

This article describes a median image filtering method that works in O (log r) time per pixel, where r is the radius of the filter, and works for any type of data (whether it is 8-bit integers or doubles):

Fast median and two-way filtering

Answer 4

See equations 4 and 5 in the next article. The complexity is O (N * W), where W is the filter width and N is the number of samples.

http://www.cas.cn/ky/kyjz/201305/W020130504687068232825.pdf

Answer 5

I know this question is somewhat old, but I was also interested in median filtering. If you work with signals or images, then for the processing window there will be a lot of data overlap. It can be used.

I posted a few benchmarks here: 1D moving median filtering in C ++

This template is based on the fact that it should work with most POD data types.

According to my results, std::nth_element has poor performance for a moving median, since it must sort the value window every time.

However, using a pool of values ​​that are sorted, you can perform a median with 3 operations.

• Delete the old value from the pool (calls to std :: lower_bound)
• Paste the new value into the pool (calls to std :: lower_bound)
• Save new value in history buffer

The median is now the average value in the pool.

I hope someone finds this interesting and brings in their ideas!