基于链表的滑动中值滤波器实现思路

总之，先假设底层的链表已经实现好了，反正很简单。

原理

基本上，中值滤波，或者说滑动中值滤波，需要做三件事：

1. 在新数据添加到窗口的同时，将最旧的数据删除；
2. 对窗口中的数据排序；
3. 找出中位数；

排序

每个新数据将被加入一个双向链表LinkedList中，并且在加入链表时就把它按从小到大的顺序放在合适的位置。添加新数据并排序，最多只需要把整个链表遍历一次。如果不在添加时立即排序，后续只能整体排序，那就指不定要来回几次了。换个视角看，如果用这种方法添加N 个数据，最多可能要遍历N 次，其实不算快，但是用在滤波器这种场合，需要考虑的主要是添加单个数据时排序的性能，那这种方法就很方便了。

中位数

保存当前的中位数$M$，添加新数据$N$ 时，若$N<M$ ，那么$N$ 肯定会被排在$M$ 之前，链表的前半部分变长了，中点自然应该向前移动，所以新的中位数就对应$M$ 的前一个节点。反之，若$N\ge M$，中点就向后移动。

删除旧数据也会导致链表中点发生变化，和添加新数据同理：如果前面短了，就让中点向后，否则让中点向前。为了避免重复移动中点，可以一次性比较新数据$N$、旧数据$D$、当前中点$M$，如果中点前面删了一个数据，但是又加了个数据，那么中点就不用移动，其他情况同理。虽说，双向链表的优点就在于移动和增删的高效，中点重复挪几下或许比多几个分支判断要更高效呢。

当然，这么做的前提是，滤波器初始化时就要让$M$ 指向链表中间。这应该没什么难的，如果窗口大小是$W$，初始化时就给链表中添加$W$ 个节点，每个节点的值是某个初始值，比如就是0，然后让$M$ 对应$\frac{W}{2}$对应的那个节点就好了。这个步骤只需要在初始化时做一次，不用担心会浪费性能，直接随便找个地方当中值点好像也完全OK。

删除旧数据

首先要找到最旧的数据，这个地方就稍微有点麻烦了，双向链表里的数据是按大小排序的，无法直接判断数据加入的先后顺序。我的思路是：另外再加一个单向链表，也可以说是队列，就起名叫ForwardLinkedList；每个数据将被同时加入双向链表和这个队列中，队列自然就有先进先出的功能，可以高效的找出最旧的数据。

具体来说，存放数据的链表节点应该含有三个指针域，即next、prev 和forward，next 和prev 用来指向双向链表中的前一节点和后一节点，forward 用来在单向链表中指向后一节点。这些指针的类型都是一样的，指向存放数据的链表节点类型，可以取名叫DoubleLinkedNode。要删除旧数据，只需从队列中弹出最旧的节点，然后从双向链表中将该节点删除。

优点

1. 运行可能比较快：这里用链表本身就是拿空间换时间，数据增删和挪动都只要一步完成。每次添加新数据时，排序最多只用遍历一次，理论上耗时也比较短；

缺点

1. 比较费空间：如果滤波器接收的数据是float 类型，塞进链表节点里之后，加上三个指针，存储每个数据要耗费三倍的额外空间；
2. 管理链表要操作一堆指针：尤其这还是两个链表交织到一起，写代码要小心点儿；

伪代码实现

还是假设底层链表已经实现好了，拿伪代码把思路细化：

struct DoubleLinkedNode {
	// 用于单向链表
	DoubleLinkedNode *forward;
	
	// 用于双向链表
	DoubleLinkedNode *next;
	DoubleLinkedNode *prev;

	float data;
};

// 双向链表
class LinkedList {
	// 假设已经实现好了
};

// 单向链表
class ForwardLinkedList {
	// 假设已经实现好了
};

// 滑动中值滤波器
class MovindMedianFilter {
	private:
	LinkedList _ordered_list;  // 用于排序的双向链表
	ForwardLinkedList _queue;  // 先进先出队列
	
	DoubleLinkedNode *_median_node;  // 指向中值
	
	public:
	MovindMedianFilter() {
	
	}
	
	// 初始化，创建并给链表中添加windows_size 个节点，值为init_value
	void init(size_t window_size, float init_value) {
        for (int i = 0; i < window_size; ++i) {
            auto * node = new DoubleLinkedNode{};
            node->data = init_value;
            
            if(i == window_size / 2) {  // 初始化中值节点
                _median_node = node;
            }
            
            _queue.push_back(node);
            _ordered_list.push_back(node);   // 所有节点的值相同，不用排序，
                                             // 直接添加就能保证初始中值节点位于链表中间
        }
	}
	
	// 传入一个新数据，返回经过滤波的中值
	float feed(float new_value) {
        float median_value = _median_node->data;  // 当前中值
        
        auto *old_node = _queue.pop_front();      // 弹出旧数据
        _ordered_list.remove(old_node);
        float old_value = old_node->data;
        
        // 重用旧节点，添加新数据。所以初始化以后，只要窗口大小不变，滤波器就不需要释放或获取更多内存
        old_node->data = new_value;
        _queue.push_back(old_node);
        _ordered_list.insert_sorted(old_node);
        
        // 如果新数据和旧数据都大于或小于当前中值，当前中值就不需要移动
        if(new_value < median_value && old_value >= median_value) {
            // 前面加一个，后面减一个，中点前移
            _median_node = _median_node->prev;
        }
        else if(new_value >= median_value && old_value < median_value) {
            // 后面加一个，前面减一个，中点后移
            _median_node = _median_node->next;
        }
        
        return _median_node->data;
	}

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79