嵌入式中值滤波器：零动态内存的滑动窗口实现

1. 项目概述

MedianFilter 是一个专为嵌入式系统设计的滑动窗口中值滤波器实现，其核心目标是在资源受限的裸机或实时操作系统（RTOS）环境中，以零动态内存分配为前提，高效、鲁棒地消除模拟信号中的脉冲噪声（impulse noise），即“椒盐噪声”（salt-and-pepper spikes）。该库不依赖malloc、free或任何堆管理机制，所有数据结构均通过静态数组或栈上变量完成分配，确保在中断上下文、硬实时任务及内存碎片敏感场景下的绝对确定性与安全性。

与通用 DSP 库中常见的基于排序或std::nth_element的中值计算方案不同，MedianFilter 采用了一种创新的双向链表+中位指针跟踪（median pointer tracking）混合架构。它将时间序列的“年龄顺序”（age order）与数值大小的“有序链”（value chain）解耦：前者通过环形缓冲区索引隐式维护，后者则由显式的双向链表动态组织。这种设计使得每次插入新样本时，无需对整个窗口进行重排序，也无需重新遍历查找中位数，而是仅需从当前中位节点出发，沿链表向上或向下搜索至插入位置，并最多移动中位指针一步。其平均时间复杂度稳定在 O(n/2)，最坏情况为 O(n)，且在典型窗口尺寸（7–101）下，指令数显著优于插入排序、std::nth_element及朴素全排序等竞品方案。

该库提供 C 和 C++ 两种接口形态，均严格遵循嵌入式开发最佳实践：C 接口为纯函数式、无状态、caller-allocated 缓冲区模型；C++ 接口为 header-only 模板，支持编译期类型安全检查与窗口尺寸约束。二者可共存于同一工程，互不干扰。整个实现仅依赖<stdint.h>（C）或<cstdint>与<type_traits>（C++），无第三方依赖，代码体积精简，RAM 占用恒定可控——在 64 位平台为每样本 24 字节，在主流 32 位 ARM Cortex-M 系统（如 STM32F4/F7/H7）上仅为 12 字节/样本。

2. 核心原理与数据结构设计

2.1 双链表+中位指针的协同机制

MedianFilter 的核心创新在于其对滑动窗口数据结构的抽象方式。传统中值滤波器通常将窗口视为一个线性数组，每次插入后执行一次完整排序（O(n log n)）或部分排序（O(n²) 插入排序），代价高昂。MedianFilter 则引入两个正交维度：

• 年龄链（Age Chain）：逻辑上是一个长度为 N 的环形缓冲区，按采样时间顺序循环覆盖。buffer[0]是最新样本，buffer[N-1]是最老样本，下一次插入将覆盖buffer[(0 + N) % N] = buffer[0]。该链完全隐式，不存储任何指针字段，仅通过filter.ageHead（指向最老节点的索引）与模运算实现。此举节省了每个节点一个指针（8 字节），在 64 位系统上降低 25% RAM 开销。

• 值链（Value Chain）：一个双向链表，节点按数值升序排列：smallest <══> ... <══> largest。每个节点包含prev和next指针，以及value字段。该链显式维护数据的有序性，是快速定位插入点与中位数的基础。

• 中位指针（Median Pointer）：一个始终指向当前窗口中位节点的指针（filter.medianNode）。由于窗口大小 N 为奇数，中位数唯一确定为第(N+1)/2小的元素。该指针永不重算，仅在每次插入后根据新值与当前中位值的相对关系，决定向上（prev）或向下（next）移动一步。此增量更新保证了 O(1) 的中位获取开销。

三者协同工作流程如下（以插入新样本x为例）：

1. 驱逐最老节点：通过ageHead定位待驱逐节点old，将其从值链中解链（old->prev->next = old->next; old->next->prev = old->prev;），并更新ageHead = (ageHead + 1) % N。
2. 双向搜索插入点：比较x与medianNode->value：
   • 若x <= medianNode->value，则从medianNode开始沿prev链向上搜索，直至找到首个node->value <= x的位置；
   • 若x > medianNode->value，则从medianNode开始沿next链向下搜索，直至找到首个node->value >= x的位置。
   • 此策略使平均搜索步数降至 ~n/4，远优于从头遍历的 n/2。
3. 插入回收节点：将驱逐出的old节点填入搜索到的位置，调整其prev/next指针，完成值链重组。
4. 更新中位指针：若新值x插入位置在原中位节点左侧（即x <= medianNode->value），且插入后中位序号左移，则medianNode = medianNode->prev；反之，若插入右侧且序号右移，则medianNode = medianNode->next。因窗口大小固定且为奇数，此调整恒为 ±1 步。

该机制彻底规避了全局重排序，将计算重心从“找中位数”转向“维护中位数”，是其实时性与低开销的根本保障。

2.2 节点结构与内存布局

MedianFilter的节点结构在 C 和 C++ 中保持一致语义，但实现细节略有差异。以 64 位平台为例，C 版本sMedianNode_t定义如下：

typedef struct sMedianNode_s { int32_t value; // 样本值（可配置为 int16_t, float 等） struct sMedianNode_s *prev; struct sMedianNode_s *next; } sMedianNode_t;

其内存布局为：value（4 字节） +prev（8 字节） +next（8 字节） =20 字节。但实际占用为24 字节，原因在于结构体对齐（alignment）：编译器为保证prev/next指针的 8 字节对齐，会在value后填充 4 字节空洞。此 24 字节为常量，与样本类型无关（int16_t仍占 4 字节value字段，以保持指针对齐）。

在 32 位 ARM 平台（如 Cortex-M3/M4），指针为 4 字节，sMedianNode_t布局为：value（4 字节） +prev（4 字节） +next（4 字节） =12 字节，无额外填充，RAM 效率更高。

C++ 模板版本通过模板参数T泛化value类型，并利用static_assert在编译期强制T为算术类型（std::is_arithmetic_v<T>），同时对value字段进行精确对齐控制，避免冗余填充，确保跨平台内存 footprint 可预测。

2.3 稳定重复值处理：地址基决胜机制

当窗口中存在多个相等值的样本时，标准中值定义可能产生歧义（例如窗口[1,2,2,2,3]，三个2均可作为中位数）。MedianFilter 通过地址基决胜（address-based tiebreaker）确保行为完全确定：

• 所有节点在物理内存中具有唯一地址。
• 当搜索插入点遇到相等值节点时，比较规则为：if (x == node->value) { use node's address as secondary key }。
• 具体实现中，若x == node->value，则根据&node的地址大小决定插入方向（例如，地址较小者视为“更小”），从而打破平局。

此机制不改变数值排序语义，仅在完全相等时提供确定性顺序，保证相同输入序列在任意平台、任意编译器下产生完全一致的输出，对传感器校准、数据回放等场景至关重要。

3. API 接口详解与工程化使用

3.1 C 接口：裸机与 RTOS 的基石

C 接口设计严格遵循嵌入式 C 编程范式：无隐藏状态、无全局变量、caller-allocated 资源、返回码驱动错误处理。主要 API 如下表所示：

sMedianFilter_t结构体关键字段：

typedef struct sMedianFilter_s { uint32_t numNodes; // 窗口大小 N（必须为奇数） sMedianNode_t *medianBuffer; // 用户分配的节点数组首地址 sMedianNode_t *medianNode; // 当前中位节点指针（内部维护） uint32_t ageHead; // 最老节点索引（0-based，隐式年龄链头） } sMedianFilter_t;

典型裸机初始化与使用示例（STM32 HAL ADC 中断）：

#include "MedianFilter.h" #define WINDOW_SIZE 7 static sMedianFilter_t adc_filter; static sMedianNode_t filter_buffer[WINDOW_SIZE]; void ADC_IRQHandler(void) { static uint32_t raw_value; // 读取 ADC DR 寄存器（假设已配置好） raw_value = ADC1->DR; // 滤波：直接调用内联 Insert，零开销 int32_t filtered = MEDIANFILTER_Insert(&adc_filter, (int32_t)raw_value); // 使用 filtered 值进行后续处理（如 PID 控制、显示） process_filtered_value(filtered); } void system_init(void) { // 配置 ADC、时钟等... // 初始化滤波器 adc_filter.numNodes = WINDOW_SIZE; adc_filter.medianBuffer = filter_buffer; if (MEDIANFILTER_Init(&adc_filter) != 0) { // 初始化失败，进入安全模式或报错 error_handler(); } }

3.2 C++ 接口：类型安全与编译期约束

C++ 接口为 header-only 模板，提供更强的类型安全与编译期检查。其核心类MedianFilter<T, N>定义如下：

template<typename T, size_t N> class MedianFilter { static_assert(std::is_arithmetic_v<T>, "T must be arithmetic"); static_assert(N >= 3 && N % 2 == 1, "N must be odd and >= 3"); public: MedianFilter(); // 构造函数，自动初始化 T Insert(T value); // 插入样本，返回当前中位数 private: std::array<sMedianNode<T>, N> m_buffer; // 内部节点数组 sMedianNode<T>* m_medianNode; size_t m_ageHead; };

Insert方法为内联实现，无函数调用开销。模板参数T支持int,int16_t,float,double等任意算术类型；N为编译期常量窗口大小，static_assert确保其合法性。

多通道传感器滤波示例（FreeRTOS 任务）：

#include "MedianFilter.hpp" #include "freertos/FreeRTOS.h" #include "freertos/task.h" // 为不同传感器创建独立滤波器实例 MedianFilter<int16_t, 5> temp_filter; // 温度，5点窗口 MedianFilter<uint16_t, 7> humi_filter; // 湿度，7点窗口 MedianFilter<int32_t, 9> pres_filter; // 压力，9点窗口 void sensor_task(void* pvParameters) { while(1) { // 读取原始传感器数据（伪代码） int16_t raw_temp = read_temperature_sensor(); uint16_t raw_humi = read_humidity_sensor(); int32_t raw_pres = read_pressure_sensor(); // 并行滤波 int16_t filtered_temp = temp_filter.Insert(raw_temp); uint16_t filtered_humi = humi_filter.Insert(raw_humi); int32_t filtered_pres = pres_filter.Insert(raw_pres); // 发布滤波后数据到队列或共享内存 publish_sensor_data(filtered_temp, filtered_humi, filtered_pres); vTaskDelay(pdMS_TO_TICKS(10)); // 10ms 采样周期 } }

3.3 RAM 占用与性能权衡分析

MedianFilter 的 RAM 占用公式为：
总 RAM = N × node_size + filter_struct_size

其中node_size为 12 字节（32 位）或 24 字节（64 位）；filter_struct_size为 40 字节（含numNodes,medianNode,ageHead等字段）。对于典型的 STM32F407（192KB SRAM），使用N=11的int16_t滤波器，RAM 占用仅为11×12 + 40 = 172字节，可轻松部署数十个独立通道。

性能方面，基准测试（gcc -O2）显示其指令数优势随窗口增大而凸显：

在N=101时，MedianFilter 比插入排序快 2.6 倍，比vpetrigo快 3.3 倍。这意味着在需要大窗口抑制强噪声（如电机驱动干扰）的场景下，它能释放更多 CPU 周期给控制算法或通信协议栈。

4. 典型应用场景与集成实践

4.1 ADC 信号去噪：从理论到硬件闭环

ADC 采样易受电源噪声、PCB 布线耦合、外部电磁干扰影响，产生随机尖峰。MedianFilter 是消除此类脉冲噪声的黄金标准。以 STM32H743 的 16 位 ADC 为例，典型配置如下：

• 硬件层：ADC 配置为连续扫描模式，采样周期 1μs，触发源为定时器 TRGO。
• 驱动层：HAL 库HAL_ADC_Start_DMA()启动 DMA 循环传输，将uint16_t数据流写入双缓冲区。
• 滤波层：在 DMA 传输完成回调HAL_ADC_ConvCpltCallback()中，对每个新样本调用MEDIANFILTER_Insert()。
• 应用层：滤波后值用于 PID 控制器输入，或经float转换后送入 FFT 分析。

此流水线完全避开了malloc，DMA 与滤波在中断上下文中完成，主循环仅处理高阶逻辑，满足硬实时要求。

4.2 多传感器融合：独立通道与资源隔离

在环境监测节点中，温度、湿度、气压传感器常共用同一 I2C 总线，但采样速率与噪声特性各异。MedianFilter 的轻量级特性允许为每个通道分配独立滤波器实例：

// 为不同传感器定制窗口 MedianFilter<int16_t, 5> temp_filter; // 温度变化慢，小窗口响应快 MedianFilter<uint16_t, 9> humi_filter; // 湿度易受结露影响，大窗口抑噪 MedianFilter<int32_t, 7> pres_filter; // 压力需兼顾精度与稳定性

各滤波器使用独立缓冲区，互不干扰，避免了单一大缓冲区带来的 cache line 冲突与内存带宽争用。

4.3 与 FreeRTOS 高级特性集成

在 FreeRTOS 环境中，可进一步利用其同步机制提升鲁棒性：

• 滤波器保护：若滤波器被多个任务共享（如一个任务采集，另一个任务读取中位数），可用SemaphoreHandle_t包裹Insert调用，防止并发访问破坏链表一致性。
• 动态窗口调整：通过消息队列接收上位机指令，运行时切换N（需预先分配最大窗口缓冲区，运行时仅更新filter.numNodes并重初始化）。
• 内存池集成：将sMedianNode_t数组置于 FreeRTOS 的StaticQueue_t或StaticSemaphore_t内存池中，实现全静态内存管理。

5. 部署与调试指南

5.1 快速集成步骤

1. 下载源码：克隆仓库，提取MedianFilter.h/MedianFilter.c（C）或MedianFilter.hpp（C++）。
2. 添加到工程：将文件加入 IDE 工程，确保头文件路径正确。
3. 配置宏（C）：在MedianFilter.h包含前定义MEDIANFILTER_INLINE_API。
4. 静态分配：在.c文件全局区或.cpp文件命名空间下声明sMedianFilter_t和sMedianNode_t[N]数组。
5. 初始化：在main()或App_Init()中调用MEDIANFILTER_Init()。
6. 调用滤波：在数据采集点插入MEDIANFILTER_Insert()。

5.2 常见问题与调试技巧

• 问题：滤波器输出恒为 0 或异常值
  排查：检查MEDIANFILTER_Init()返回值是否为-1；确认numNodes为奇数且>=3；验证medianBuffer指针非空且内存可写。

• 问题：中位数跳变剧烈，未达预期平滑效果
  排查：窗口大小N过小（如N=3对强噪声无效），增大至7或9；检查原始信号是否真为脉冲噪声，而非高频振荡（此时应结合低通滤波）。

• 问题：RAM 占用超预期
  优化：在 32 位 MCU 上，确保编译器未启用 64 位指针；检查sMedianNode_t是否被意外对齐到 16 字节边界（可通过#pragma pack(1)强制紧凑对齐，但需确保指针访问安全）。

• 调试可视化：利用printf或 Segger RTT 输出窗口内所有节点值（filter.medianBuffer[i].value）及medianNode地址，验证链表排序与中位指针位置是否符合预期。

MedianFilter 的价值不仅在于其卓越的性能指标，更在于它将一个看似复杂的 DSP 算法，提炼为嵌入式工程师可理解、可审计、可预测的底层数据结构操作。当你的 ADC 读数在电机启停瞬间依然稳定，当你的多轴 IMU 数据在振动环境下保持可信，当你的 FreeRTOS 任务在 95% CPU 占用率下仍准时交付滤波结果——你所依赖的，正是这 24 字节节点背后，对确定性与效率的极致追求。