MedianFilter

KO | EN

gitlite — search

#javascript #python #hacktoberfest #typescript #golang #android #rust #deep-learning #nodejs #cli #pytorch #mcp #openai #open-source

(★ 73)

Heap-free sliding window median filter for embedded C/C++ — O(n/2) insert, zero allocations, ideal for ADC noise removal on bare-metal and RTOS targets

MedianFilter Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# MedianFilter

[![CI](https://github.com/accabog/MedianFilter/actions/workflows/ci.yml/badge.svg)](https://github.com/accabog/MedianFilter/actions/workflows/ci.yml)
[![License: MIT](https://img.shields.io/badge/License-MIT-blue.svg)](https://raw.githubusercontent.com/accabog/MedianFilter/master/LICENSE)
[![Language: C/C++](https://img.shields.io/badge/Language-C%2FC%2B%2B-brightgreen.svg)]()
[![Platform: Bare-metal / RTOS / Desktop](https://img.shields.io/badge/Platform-Bare--metal%20%2F%20RTOS%20%2F%20Desktop-orange.svg)]()
[![No dynamic allocation](https://img.shields.io/badge/Heap-None-critical.svg)]()
[![PlatformIO](https://badges.registry.platformio.org/packages/accabog/library/MedianFilter.svg)](https://registry.platformio.org/libraries/accabog/MedianFilter)

**Heap-free, O(n/2)-worst-case sliding-window median filter for embedded systems. Drop two files into your project and go.**

Removes impulse noise (salt-and-pepper spikes) from analog signals in real time — ideal for ADC readings, sensor fusion, and any DSP pipeline where you need a robust filter with zero malloc.

## Features

- **Zero heap allocation** — stack or static buffers only, safe for bare-metal and RTOS
- **O(n/2) worst-case insert (~n/4 average)** — bidirectional search from the median pointer
- **O(1) median tracking** — the median pointer adjusts by at most one step per insert, never recomputed
- **Stable duplicate handling** — address-based tiebreaker eliminates ambiguity for equal-valued samples
- **C API** — caller-allocated buffers, two functions, done
- **C++ header-only template** — type-safe, compile-time `static_assert` on window size and type
- **No dependencies** — only `<stdint.h>` (C) or `<type_traits>` / `<cstdint>` (C++)
- **24 bytes per sample** — constant, predictable RAM footprint (64-bit); 12 bytes on 32-bit ARM

## Quick Start

### C

```c
#include "MedianFilter.h"

#define WINDOW_SIZE 7

static MedianFilter_t     filter;
static MedianFilterNode_t buffer[WINDOW_SIZE];

void setup(void)
{
    filter.numNodes     = WINDOW_SIZE;
    filter.medianBuffer = buffer;
    MEDIANFILTER_Init(&filter);
}

int process(int sample)
{
    return MEDIANFILTER_Insert(&filter, sample);
}
```

### C++

```cpp
#include "MedianFilter.hpp"

MedianFilter<int, 7> filter;

int process(int sample)
{
    return filter.Insert(sample);
}
```

The C++ template accepts any arithmetic type (`int`, `float`, `double`, `int16_t`, ...) and enforces an odd window size >= 3 at compile time.

## Examples

The [`examples/`](examples/) folder contains runnable demos and platform-specific reference code:

| Example | Description |
|---------|-------------|
| [Basic Usage](examples/01_basic_usage.c) | Minimal C API — init, insert, print |
| [ADC Noise Filter](examples/02_adc_noise_filter.c) | Spike removal from a simulated 12-bit ADC signal |
| [Multichannel Sensors](examples/03_multichannel_sensors.c) | Independent filters on temperature, humidity, and pressure |
| [Window Size Comparison](examples/04_window_size_comparison.c) | Noise removal vs. signal lag tradeoff |
| [C++ Template](examples/05_cpp_template.cpp) | `float`, `int16_t`, `double` type flexibility |
| [STM32 HAL](examples/platform/stm32_hal_adc.c) | ADC interrupt callback (reference) |
| [Arduino](examples/platform/arduino_analog_filter/arduino_analog_filter.ino) | `analogRead()` filter |
| [ESP-IDF](examples/platform/esp_idf_adc_filter.c) | FreeRTOS ADC task (reference) |

Build and run all desktop demos:

make examples

## How It Works

Each sample lives in a node with two link chains:

```
Age order:     buffer[0] → [1] → ... → [N-1] → [0]   (implicit, round-robin)

Value chain:   smallest <══> ... <══> largest          (doubly-linked, sorted)

Median ptr:         ──────────> M                      (always the middle node)
```

Age order is implicit — nodes are recycled in buffer order via pointer arithmetic, so no explicit age pointer is stored. This saves one pointer per node (25% RAM reduction).

On every insert:

1. **Evict** the oldest node (age head, advanced by `ptr + 1` with wraparound) and unlink it from the value chain
2. **Search** from the median pointer — up or down depending on the new sample's value
3. **Insert** the recycled node at the correct sorted position
4. **Adjust** the median pointer by one step if needed

The bidirectional search means average traversal is ~n/4 rather than n/2. The median pointer never needs to be recomputed from scratch — it tracks incrementally.

## Performance

Consistently among the fastest across all window sizes — and the clear winner at larger windows where it matters most.

Instructions per insert (lower is better), measured with [Valgrind/Callgrind](https://valgrind.org/docs/manual/cl-manual.html) (`gcc -O2`, averaged over 5 random seeds). Results are **deterministic and hardware-independent** — reproducible on any machine:

| Window | **Ours (C)** | **Ours (C++)** | Insertion-sort ring | [vpetrigo](https://github.com/vpetrigo/median-filter) | std::nth_element | Naive sort |
|:------:|:------------:|:--------------:|:-------------------:|:------------------------------------------------------:|:----------------:|:----------:|
| 3      | **124**      | **131**        | 112                 | 159                                                    | 179              | 194        |
| 7      | **128**      | **137**        | 149                 | 190                                                    | 310              | 300        |
| 11     | **134**      | **143**        | 173                 | 218                                                    | 390              | 444        |
| 31     | **162**      | **172**        | 288                 | 359                                                    | 751              | 1446       |
| 51     | **189**      | **200**        | 395                 | 499                                                    | 1078             | 2504       |
| 101    | **259**      | **270**        | 669                 | 847                                                    | 1880             | 5452       |

"Ours (C)" uses the opt-in `MEDIANFILTER_INLINE_API` inline Insert. At small windows (3), insertion-sort ring wins thanks to cache locality on tiny arrays. From window 7+, our linked-list approach takes the lead — and at window 101, it uses **2.6× fewer instructions** than insertion-sort and **3.3× fewer** than vpetrigo.

RAM = `window_size * 24 + 40` bytes (64-bit). On 32-bit targets, nodes are 12 bytes each and the filter struct is 20 bytes, so RAM = `window_size * 12 + 20` bytes. See [`benchmarks/`](benchmarks/) for full results, throughput benchmarks, and methodology.

## API Reference

### C

| Function | Signature | Returns |
|:---------|:----------|:--------|
| **Init** | `int MEDIANFILTER_Init(MedianFilter_t *filter)` | `0` on success, `-1` on invalid config |
| **Insert** | `int MEDIANFILTER_Insert(MedianFilter_t *restrict filter, int sample)` | Current median value |

The caller must allocate `MedianFilter_t` and a `MedianFilterNode_t[N]` buffer, set `numNodes = N` and `medianBuffer = buffer`, then call Init. Window size must be **odd** and **> 1**.

> The type names were previously `sMedianFilter_t` / `sMedianNode_t`; those still work as deprecated aliases, so existing code needs no changes.

**Inline variant:** For tight-loop callers (e.g. processing an ADC buffer), define `MEDIANFILTER_INLINE_API` before including the header to get a `static inline` Insert that eliminates function-call overhead.

### C++

| Method | Signature | Returns |
|:-------|:----------|:--------|
| **Constructor** | `MedianFilter<type, N>()` | — |
| **Insert** | `type Insert(type value)` | Current median value |

Template parameters: `type` must be arithmetic, `N` must be odd and >= 3. Enforced via `static_assert`.

## Integration

**Just copy the files — no build system required.**

For C: add `MedianFilter.h` and `MedianFilter.c` to your project.
For C++: add `MedianFilter.hpp` (header-only, nothing to compile).

Both APIs are compatible in the same translation unit — the C header includes `extern "C"` guards.

## License

[MIT](LICENSE) — free for commercial and personal use.

MedianFilter

MedianFilter Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

MedianFilter

MedianFilter Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README