median

概要

Rust 中 O(n) 中值滤波器的实现。

动机

中值滤波器是一种 非线性数字滤波技术，通常 用于从图像或信号中去除噪声。这种噪声减少是典型的预处理步骤，以 提高后续处理的结果 […]. 中值滤波器非常广泛地使用 […] 因为，在 某些条件下，它可以在去除噪声的同时保留边缘，同时也有 信号处理中的应用。（维基百科）

中值与平均值

用法

extern crate rand;
use rand::{Rng, XorShiftRng};

extern crate median;
use median::Filter;

let mut rng = XorShiftRng::new_unseeded();
let mut filter = Filter::new(FILTER_WIDTH);
for i in 0..INPUT_LENGTH {
    let signal = (i as f32).sin();
    let noise = rng.gen::<f32>();
    let value = signal + (noise * 0.2);
    let filtered = filter.consume(value);
    // use filtered
}

实现

该算法使用了一个与滤波窗口大小相同的 环形缓冲区。将值插入环形缓冲区会将它们附加到环形缓冲区内部嵌入的 链表。

性能

中值滤波器的经典实现使用一个内部缓冲区，它为每个输入重新排序以找到中值，与使用环形缓冲区嵌入的链表相比，性能较差，如本软件包中所用。

（越低越好）

示例

给定一个值序列 [3, 2, 4, 6, 5, 1] 和一个大小为 5 的缓冲区，
缓冲区将填充如下

new(5)  consume(3)  consume(2)  consume(4)  consume(6)  consume(5)  consume(1)
▶︎[ ]      ▷[3]       ┌→[3]       ┌→[3]─┐     ┌→[3]─┐    ▶︎┌→[3]─┐      ▷[1]─┐
 [ ]      ▶︎[ ]      ▷└─[2]      ▷└─[2] │    ▷└─[2] │    ▷└─[2] │    ▶︎┌─[2]←┘
 [ ]       [ ]        ▶︎[ ]         [4]←┘     ┌─[4]←┘     ┌─[4]←┘     └→[4]─┐
 [ ]       [ ]         [ ]        ▶︎[ ]       └→[6]       │ [6]←┐     ┌→[6] │
 [ ]       [ ]         [ ]         [ ]        ▶︎[ ]       └→[5]─┘     └─[5]←┘

算法

1. 移除当前光标（▶︎）处的节点，如果存在。（通过重新连接其前驱到其后继）。
2. 初始化 current 和 median 指针到链表的第一个节点（▷）。
3. 遍历 链表，搜索 插入点。
4. 每跳一步移动 中值索引（因此最终到达链表的中值位置）。
5. 将值 插入环形缓冲区和链表。
6. 如果需要，将索引更新到链表的第一个节点。
7. 更新 环形缓冲区的游标。
8. 返回中值值.

贡献

请阅读 CONTRIBUTING.md 了解我们的 行为准则，
以及向我们提交拉取请求的过程。

许可证

本项目采用 MPL-2.0 许可证 – 请参阅 LICENSE.md 文件以获取详细信息。