Struct signalo_filters::median::Median

pub struct Median<T, const N: usize> { /* fields omitted */ }

A median filter of fixed width with linear complexity.

While the common naïve implementation of a median filter has a worst-case complexity of O(n^2) (due to having to sort the sliding window) the use of a combination of linked list and ring buffer allows for a worst-case complexity of O(n).

Implementation

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 (using relative integer jump offsets as links).

Example

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]←┘

Algorithm

1. Remove node at current cursor (▶︎) from linked list, if it exists. (by re-wiring its predecessor to its successor).
2. Initialize current and median index to first node of linked list (▷).
3. Walk through linked list, searching for insertion point.
4. Shift median index on every other hop (thus ending up in the list’s median).
5. Insert value into ring buffer and linked list respectively.
6. Update index to linked list’s first node, if necessary.
7. Update ring buffer’s cursor.
8. Return median value.

(Based on Phil Ekstrom, Embedded Systems Programming, November 2000.)

Implementations

impl<T, const N: usize> Median<T, N> where
    T: Clone, 

pub fn len(&self) -> usize

Returns the window size of the filter.

pub fn is_empty(&self) -> bool

Returns true if the filter’s buffer is empty, false otherwise.

pub fn median(&self) -> Option<T>

Returns the filter buffer’s current median value, panicking if empty.

pub fn min(&self) -> Option<T>

Returns the filter buffer’s current min value, panicking if empty.

pub fn max(&self) -> Option<T>

Returns the filter buffer’s current max value, panicking if empty.

Trait Implementations

impl<T: Clone, const N: usize> Clone for Median<T, N>

fn clone(&self) -> Median<T, N>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug, const N: usize> Debug for Median<T, N>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, const N: usize> Default for Median<T, N>

fn default() -> Self

Returns the “default value” for a type.

impl<T, const N: usize> Filter<T> for Median<T, N> where
    T: Clone + PartialOrd, 

type Output = T

The filter’s output type.

fn filter(&mut self, input: T) -> Self::Output

Processes the input value, returning a corresponding output.

impl<T, const N: usize> FromGuts for Median<T, N>

fn from_guts(guts: Self::Guts) -> Self

Constructs a value from its guts.

impl<T, const N: usize> Guts for Median<T, N>

type Guts = State<T, N>

The type’s guts.

impl<T, const N: usize> IntoGuts for Median<T, N>

fn into_guts(self) -> Self::Guts

Destructures a value into its guts.

impl<T, const N: usize> Reset for Median<T, N>

fn reset(self) -> Self

Returns an instance with a freshly reset internal state.

impl<T, const N: usize> State for Median<T, N>

type State = State<T, N>

The filter’s internal state.

impl<T, const N: usize> StateMut for Median<T, N>

unsafe fn state_mut(&mut self) -> &mut Self::State

Returns a mutable reference to the internal state of the filter.