An implementation of an efficient O(n) median filter in Rust.
The median filter is a nonlinear digital filtering technique, often used to remove noise from an image or signal. Such noise reduction is a typical pre-processing step to improve the results of later processing […]. Median filtering is very widely used […] because, under certain conditions, it preserves edges while removing noise, also having applications in signal processing. (Wikipedia)
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
}The algorithm makes use of a ring buffer of the same size as its filter window. Inserting values into the ring buffer appends them to a linked list that is embedded inside said ring buffer.
The classical implementation of a median filter uses an internal buffer that is re-sorted for each input to find the median, leading to inferior performance compared to the use of a linked list embedded in a ring buffer, as used in this crate.
(lower is better)
Given a sequence of values [3, 2, 4, 6, 5, 1] and a buffer of size 5,
the buffer would be filled like this:
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]←┘
- Remove node at current cursor (
▶︎) from linked list, if it exists. (by re-wiring its predecessor to its successor). - Initialize
currentandmedianindex to first node of linked list (▷). - Walk through linked list, searching for insertion point.
- Shift median index on every other hop (thus ending up in the list's median).
- Insert value into ring buffer and linked list respectively.
- Update index to linked list's first node, if necessary.
- Update ring buffer's cursor.
- Return median value.
Please read CONTRIBUTING.md for details on our code of conduct,
and the process for submitting pull requests to us.
This project is licensed under the MPL-2.0 – see the LICENSE.md file for details.
