Repository navigation
Use a sliding histogram for 8-bit rank filters - #10404
cneuralnetwork wants to merge 2 commits into
Conversation
Median, min, max and other rank filters on 8-bit images copied the whole size x size window for every output pixel and ran a quickselect on it, costing O(size^2) per pixel. Keep a 256-bin histogram per row instead and update it as the window slides right: one column out, one column in, O(size) per pixel. The output value is tracked with a running count of samples below it, which moves only slightly between neighbouring pixels. Output is byte-identical. On a 1024x1024 L image (Apple M5): MedianFilter(3) 0.102s -> 0.031s MedianFilter(7) 0.724s -> 0.030s MedianFilter(15) 2.868s -> 0.036s MedianFilter(31) 11.434s -> 0.045s INT32 and FLOAT32 images keep the quickselect path. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Break RankUINT8 (cyclomatic complexity 10) into FillHistogram, SlideHistogram, SeekRank and RankRowUINT8, each with a complexity of 3 or less. Move the brute-force reference in the new test into a helper, read pixels with tobytes() so it type-checks, and use get_flattened_data() instead of the deprecated getdata(). Add a release note for the faster rank filters. Output and timings are unchanged. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
|
Measuring on random noise, especially for statistical filters like this, is not a great idea. 😅 We hit that with benchmarks and fixed it in #9831. We'll see what more representative numbers are when the CI benchmark finishes. I measured locally, and the histogram approach from here is a clear win for the general rank case. However, by my local numbers #10045 looks to be up to 60x faster for min/max, so "For 8-bit images this PR makes the min/max special case unnecessary" is not true. IOW, I'd say a combination of both my #10045 and this would be the best solution. As @cneuralnetwork here noted, they're happy to rebase this if it gets merged. As an aside, #10403 seems to have had momentarily implemented the exact same code as here 🤖 😄 |
Merging this PR will improve performance by ×4.12 warnings
Performance Changes
Tip Curious why performance improved? Comment Comparing 
Footnotes
|
|
Yes, I agree! Combining the best of both approaches seems like the way to go, especially given the performance difference for the min/max case. Also, just to clarify the duplicate PRs: I accidentally opened the original PR from my work account, so I had to close it and resubmit it from my personal account. That's why there are two PRs covering the same changes. This is the one that should be considered going forward. |
|
Btw, the non-split commit 1795abb reads better to me than the split one. |
|
You can actually use that as well. I actually split it because I prefer writing code with less cyclomatic complexity. That's why I had split it but the earlier one works as well. |
|
I think cyclomatic complexity doesn't matter that much for an "do a single thing" function like this -- the split version is +61 lines on top of the +55 lines of the first edition, and needs more cycles from the reviewer/reader to understand how pointers and arrays are being tossed around, don't you think? 😄 I suspect compilers will be able to better optimize the function in the non-split form anyway. |
|
Fair point! |
Median, min, max and other rank filters on 8-bit images currently copy the whole
size × sizewindow for every output pixel and run a quickselect on it, so the cost per pixel grows withsize².This PR keeps a 256-bin histogram per row and updates it as the window slides right: one column out, one column in, so the cost per pixel grows with
sizeinstead (Huang, 1979). The output value is tracked with a running count of samples below it, which moves only slightly between neighbouring pixels. INT32 and FLOAT32 images keep the quickselect path.Output is byte-identical to Pillow 11.3.0, and
RankFilter.chasn't changed onmainsince then.Benchmark
1024×1024 random noise, Apple M5, best of 3 runs (1 run for sizes 15 and 31):
Tests
Adds
test_rankfilter_l_matches_reference, which checks the 8-bit path against a brute-force rank on edge-padded windows for sizes 1–25 and the lowest, middle and highest ranks. The full test suite,selftest.py, black, ruff, clang-format and mypy pass locally.A release note is added under 13.1.0, "Other changes".
Relation to #10045
#10045 also touches
RankFilter.c. It hoists row lookups and special-cases min/max, but doesn't change the algorithm. The two will conflict. For 8-bit images this PR makes the min/max special case unnecessary, while #10045's changes still help INT32/FLOAT32. I'm happy to rebase onto it or adapt to whichever lands first.🤖 Generated with Claude Code