Median filter 233x faster: replacing Pillow's 2003-era quickselect with sliding histograms
cneuralnetwork · x · 2026-11-03
A developer walks through a first-hand perf fix in Pillow:
- Problem: MedianFilter/MinFilter/MaxFilter all route through RankFilter.c, essentially unchanged since 2003 — every output pixel memcpy'd its k×k window and ran Wirth's quickselect, O(k²) average, O(k⁴) worst case.
- Fix: Since 8-bit pixels have only 256 values, use a histogram (Huang, 1979). Sliding one pixel right only decrements k bins for the leaving column and increments k for the arriving one — the window is never copied or re-scanned. A below counter tracks samples less than the current output value, adjusted by (added < v) - (removed < v), then v walks a few bins to find the rank.
- Result: O(k) per pixel, fixed 256-int memory. On 1024² RGB median: 2.7x at 3×3, 23x at 7×7, 74x at 15×15, and 233x at 31×31 (34.5s → 0.15s), byte-identical output.
More from Research
- NorthCUA: open-source computer-use agent family claims SOTA on OSWorld and WebArena — Powerful_Evening5495 · 2026-11-03
- Unitree G1 learns self-rescue via ROOF RL strategy using geometric rewards, no maps — Scobleizer · 2026-11-03
- ACM double-blind rollout clarified: TOSEM stays single-anonymous for now — mboehme_ · 2026-11-03
- DeepMind RCT with 992 participants: repeated LLM use, not personalization, drives perceived closeness — Dr_Atoosa · 2026-11-03
- Qwen model edited via Weight-Space Programming, weights and demo on HF — kalyan_kpl · 2026-11-03
- AI practitioner argues frontier labs are overlooking chemistry as the richest RL sandbox — gabepgomes · 2026-11-03