Pillow 中值滤波提速 233 倍：直方图滑动窗口替代 2003 年遗留 quickselect

cneuralnetwork · x · 2026-11-03

一位开发者分享优化 Pillow 性能 bug 的一手过程：

问题：Pillow 的 MedianFilter/MinFilter/MaxFilter 都走 RankFilter.c，代码自 2003 年起几乎未变——每个输出像素都要 memcpy 整个 k×k 窗口再跑 Wirth quickselect，平均 O(k²)、最坏 O(k⁴)。
思路：8-bit 像素只有 256 个取值，改用直方图法（Huang, 1979）：窗口滑动一格时只对离开/进入的列各 k 个 bin 做增减，窗口从不复制或重扫；用 below 变量追踪小于当前输出值的样本数，每步只需按 (added < v) - (removed < v) 微调，再让 v 在 256 个 bin 里走几步定位 rank 值。
结果：每像素 O(k)，内存固定 256 个 int。1024² RGB 中值滤波实测：3×3 提速 2.7 倍，7×7 23 倍，15×15 74 倍，31×31 达 233 倍（34.5s → 0.15s），输出逐字节一致。

「研究」频道最新