C/C++ 中用于“UINT16”二维数组的快速中值滤波器
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10338888/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fast Median Filter in C / C++ for `UINT16` 2D Array
提问by user1359341
Does anyone know a fast median filter algorithm for 16-bit (unsigned short) arrays in c++?
有谁知道 C++ 中 16 位（无符号短）数组的快速中值滤波器算法？
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?
这个看起来很有前途，但它似乎只适用于字节数组。有谁知道如何修改它以使用短裤或替代算法？
回答by Mark Ransom
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.
论文中的技术依赖于为 8 位像素通道创建具有 256 个 bin 的直方图。转换为每通道 16 位将需要一个包含 65536 个 bin 的直方图，并且图像的每一列都需要一个直方图。将内存需求增加 256 使这成为一种整体效率较低的算法，但仍然可能适用于今天的硬件。
Using their proposed optimization of breaking the histogram into coarse and fine sections should further reduce the runtime hit to only 16x.
使用他们提出的将直方图分解为粗细部分的优化方法，应该可以进一步将运行时命中率降低至仅 16 倍。
For small radius values I think you'll find traditional methods of median filtering will be more performant.
对于小半径值，我认为您会发现传统的中值滤波方法性能更高。
回答by Sebastian Dressler
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.
快速中值搜索 - ANSI C 实现(PDF) 是 C 的东西，它是一篇标题为“快速中值搜索：ANSI C 实现”的论文。作者声称它是 O(log(n))，他还提供了一些代码，也许它会帮助你。它并不比您建议的代码好，但也许值得一看。
回答by HelloGoodbye
This article describes a method for median filtering of images that runs in O(log r) time per pixel, where ris the filter radius, and works for any data type (be it 8 bit integers or doubles):
本文描述了一种对图像进行中值滤波的方法，该方法在每个像素的O(log r) 时间内运行，其中r是滤波器半径，适用于任何数据类型（无论是 8 位整数还是双精度数）：
回答by RawMean
See equations 4 and 5 in the following paper. The complexity is O(N*W) where W is the width of the filter and N is the number of samples.
请参阅以下论文中的等式 4 和 5。复杂度为 O(N*W)，其中 W 是滤波器的宽度，N 是样本数。
See Noise Reduction by Vector Median Filtering.
请参阅矢量中值滤波降噪。
回答by Nick
I know this question is somewhat old but I also got interested in median filtering. If one is working with signals or images, then there will be a large overlap of data for the processing window. This can be taken advantage of.
我知道这个问题有点老了，但我也对中值滤波感兴趣。如果正在处理信号或图像，那么处理窗口的数据将有很大的重叠。可以利用这一点。
I've posted some benchmark code here: 1D moving median filtering in C++
我在这里发布了一些基准代码：C++ 中的一维移动中值滤波
It's template based so it should work with most POD data types.
它是基于模板的，因此它应该适用于大多数 POD 数据类型。
According to my results std::nth_elementhas poor performance for a moving median, as it must sort the window of values each time.
根据我的结果std::nth_element，移动中位数的性能很差，因为它每次都必须对值窗口进行排序。
However, using a pool of values that is kept sorted, one can perform the median with 3 operation.
但是，使用保持排序的值池，可以使用 3 操作执行中值。
- Remove oldest value out of the pool (calls std::lower_bound)
- Insert new value into pool (calls std::lower_bound)
- Store new value in history buffer
- 从池中移除最旧的值（调用 std::lower_bound）
- 将新值插入池中（调用 std::lower_bound）
- 在历史缓冲区中存储新值
The median is now the middle value in the pool.
中位数现在是池中的中间值。
I hope someone finds this interesting and contributes their ideas!
我希望有人觉得这很有趣并贡献他们的想法！
