REVIEW 3 major objections 4 minor 28 references
A Fast Parallel Median Filtering Algorithm Using Hierarchical Tiling
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read A hierarchical-tiling algorithm computes exact median filters on GPUs with per-pixel cost O(k log k) for a register-backed variant and O(k) for a data-aware variant, and reports up to five times higher throughput than prior GPU…
desk verdict Genuinely new separable sorting-network median filter with O(k log k) and O(k) per-pixel complexity claims; plausible and well written, but the arXiv version omits the correctness proof and mixes benchmark hardware, so the strongest speedup claims are provisional. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is hierarchical tiling, a binary tree of tile subdivisions, combined with a sorted-core invariant. The core of a tile is the intersection of all kernels over that tile's pixels; at every subdivision the sorted core of the parent is merged with the newly included extra columns or rows to form the child's sorted core, and the forgetfulness principle (when m inputs remain unseen, the median lies in the middle m+1 of the seen values) justifies discarding extrema, keeping the candidate set small. The data-oblivious variant implements all merges as comparison networks compiled to register min/max instructions, while the data-aware variant uses linear-time merging algorithms and saves intermediate state to memory between passes.
What would settle it
Compute the exact median by brute-force sorting for every pixel of random 8-bit and 32-bit test images, for a range of odd kernel sizes such as 3x3 up to 31x31, and compare against both GPU variants; any mismatch, particularly on adversarial patterns designed to hit the pruning boundary, would falsify the exact-median claim and, more specifically, the forgetfulness discard invariant.
Extended reading notes
Core claim
The paper's central claim is that the overlapping kernels of adjacent pixels can be separated recursively, not just once, so that a single sorted core is reused through a hierarchy of tile subdivisions. Concretely, for a tile of pixels the algorithm sorts the core of the tile (the intersection of all kernels), the extra columns, and the extra rows once; each split of the tile then absorbs the newly exposed columns or rows into the child's sorted core with a small merge, applying the forgetfulness principle to discard values that cannot be medians. When the recursion reaches single pixels, the sorted core contains exactly the median of that pixel's kernel. This yields per-pixel complexity O(k log k) for the register-resident selection-network variant and O(k) for the data-aware multi-pass variant, and the paper reports that the GPU implementation is the fastest exact median filter for most tested kernel sizes and data types.
Load-bearing premise
The load-bearing premise is the recursive discard rule: after each split, the algorithm assumes the values it throws away from the sorted core can never be the median of any child tile's pixel, an invariant the paper asserts by reference to supplemental material rather than proves in the main text.
Editorial extensions
If this is right
- If the claimed complexities hold, median filtering cost grows only linearly (data-aware) or as k log k (register variant) with kernel diameter, so kernels of diameter 31 or larger become usable in real-time pipelines instead of being prohibitive.
- 16-bit and 32-bit channels stop being a handicap: sorting-based filters are not limited by histogram bin count, so high-precision image data can be filtered at the same speed profile as 8-bit data.
- Because the output is the exact median, not an approximation, the method can replace existing GPU median filters in any pipeline without changing downstream semantics.
- The crossover point with constant-time wavelet-matrix filters (around 61x61 for 8-bit, 75x75 for 16-bit) sets a clear regime: use hierarchical tiling for small and medium kernels and constant-time methods only for very large ones.
- Improving the parallel multi-way merge bottleneck would extend the data-aware version's dominance to even larger kernels.
Reading between the lines
- The paper does not prove the discard invariant in the main text; a formal proof or exhaustive test of that invariant would be the first thing to check, since a failure would produce silently wrong medians rather than graceful degradation.
- The hierarchical tiling recursion is generic to rectangular neighborhoods, so the same machinery could plausibly be adapted to 3D kernels, a direction the paper names as future work; if it carries over, medical-imaging denoising with large 3D kernels could see similar speedups.
- The complexity proof relies on a root-tile heuristic that keeps the root tile within a constant factor of the kernel size, so tile-size sensitivity is worth measuring; the claimed O(k) bound may hold only when that relationship is maintained.
- The data-oblivious variant's sharp performance drop after 15x15 kernels is likely register pressure, so the crossover between the two variants should shift with GPU register-file size and occupancy; on future architectures the register variant may dominate for larger kernels.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes a new exact median filtering algorithm for GPUs based on hierarchical tiling. The image is partitioned into a binary tree of tiles; at each split, sorted rows/columns and a sorted "core" are reused and pruned via a forgetfulness principle. Two variants are described: a data-oblivious selection-network variant claimed to achieve O(k log k) per-pixel complexity for a k x k kernel, and a data-aware multi-pass variant claimed to achieve O(k). CUDA implementations are presented, with benchmarks against OpenCV's histogram method, Adams' separable sorting networks, and Moroto/Umetani's 2D wavelet matrix method on an NVIDIA L40S GPU. The paper reports that the combined implementations are the fastest for most kernel sizes from 3 x 3 to 75 x 75, with speedups over prior work up to 5x. The authors explicitly defer correctness proofs, pseudocode, and implementation details to a supplemental document that is not present in the arXiv version.
Significance. If the correctness invariant and the complexity bounds are fully established, the contribution is significant: it would provide sorting-based exact median filtering with per-pixel complexity O(k log k) and O(k), which would be an improvement over the O(k^2 log^2 k) sorting-network approaches and a competitive alternative to histogram and wavelet-matrix methods across a wide kernel range. The hierarchical tiling idea is well motivated and the split between a register-resident data-oblivious variant and a multi-pass data-aware variant is sensible. The paper is also commendably candid about practical limitations such as compilation time, binary size, and memory footprint. However, the central correctness and complexity claims are currently assertions backed by an absent supplement, and the performance comparison mixes locally measured numbers with published results from other GPUs, so the headline claims are not yet independently verifiable.
major comments (3)
- [§3.4 and Fig. 6 (also §4.2/§5.2)] The exactness of the algorithm rests on a pruning invariant that is asserted but not proved in the main text. The text states that after a split the parent sorted core is merged with new extra rows/columns and that 'extrema are discarded,' but it never specifies the exact number of elements to discard or proves that the remaining sorted core still contains the median for every pixel of each child tile. The single-pixel forgetfulness argument in Fig. 3 is insufficient, because one sorted core serves multiple child pixels and the number of unseen elements decreases by different amounts for horizontal versus vertical splits. The paper explicitly defers the proof to the supplemental material, which is not included in the arXiv submission. This invariant is load-bearing for both correctness and the complexity claims, so the authors must provide a complete proof in the manuscript or in the submitted supplement.
- [§6, Fig. 8] The performance comparison is not apples-to-apples. The manuscript states that OpenCV was measured on the L40S GPU, but for Adams it uses 'the benchmark published by Adams in the ACM digital library' and for Moroto/Umetani it uses 'the benchmark published on their project page.' Those published baselines were likely measured on different hardware, so the claimed 'up to 5 times faster' and 'fastest in most cases' conclusions could reflect GPU differences rather than algorithmic advantage. The authors should rerun the baselines on the same L40S GPU, or clearly disaggregate and qualify the comparison, and should report run-to-run variance or error bars. Without this, the central performance claim is not reproducible from the submitted text.
- [§4.2 and §5.2] The per-pixel complexity results O(k log k) and O(k) are stated as theorems but the proofs are deferred entirely to the supplemental material, which is not present. The high-level outline—initialization O(k^2 log^2 k) per root tile and recursion O(t(k)^2 k log k)—does not by itself establish the claimed per-pixel bounds; a full accounting of all sorting, merging, multi-way merging, and corner-handling costs is needed, along with the justification for choosing t(k) = 2^{floor(log2 k)-1}. As written, the complexity claim cannot be checked from the manuscript alone.
minor comments (4)
- [§2.2] 'Perrot el al.' should be 'Perrot et al.'
- [Fig. 3 and surrounding text] The variables n and m in the forgetfulness illustration are not defined in the caption or the immediately preceding text; please define n as the total number of inputs and m as the number still unseen, and explain the two extreme cases shown in (a) and (b).
- [§6, Fig. 8] The legend entries are abbreviated and the provenance of each curve should be clearer: specify that 'Histogram (OpenCV)' is Green's implementation, and add a note that the Adams and Moroto/Umetani curves are taken from their published benchmarks (with the caveat noted in the major comments).
- [§7.1] The limitation statement mentions that the data-aware version's memory requirement 'exceeding the size of the input image by up to two orders of magnitude' is 'detailed in the supplemental material.' Since the supplement is absent, please include at least one concrete example or a short table in the main text so readers can judge the practical memory budget.
Circularity Check
No significant circularity: complexity and correctness arguments rest on external network bounds and prior-work principles, not on fitted targets or self-citations.
full rationale
The paper's derivation chain is self-contained rather than circular. The O(k log k) and O(k) per-pixel complexity claims are derived from published sorting and merging network bounds (Batcher 1968; Lee and Batcher 1995) plus an explicitly stated root-tile heuristic t(k) = 2^(floor(log2 k) - 1), which gives t(k) = Theta(k). The correctness argument relies on the forgetfulness principle borrowed from prior work (Perrot et al. 2013, Figure 3), and the paper's own pruning invariant is presented as a consequence of that principle, not as a fitted result. No parameter is fitted to benchmark data, and the claimed speedups are measured against external implementations (Adams' separable sorting networks, Moroto-Umetani's 2D wavelet matrix, OpenCV's histogram filter) using their published benchmark figures; even if cross-GPU comparability is a concern, that is an experimental-control issue, not circularity. The paper does defer complete proofs to supplemental material, and the arXiv version omits those proofs, pseudocode, and source code; this is a completeness and verifiability limitation, not a circular derivation. There is also no load-bearing self-citation chain: the single author cites prior work such as Adams and Perrot et al., but none of those citations are by the present author, and the central claims do not reduce to those citations by construction. Accordingly, the circularity score is 0.
Assumptions & free parameters
free parameters (2)
- Root tile size t(k) (heuristic) =
2^{floor(log2 k)-1}
- Thread-block configuration (threads, tiles per block, mapping) =
varies; not reported
assumptions (4)
- standard math Sorting and merging network complexity upper bounds: sorting n elements in O(n log^2 n), two-list merge O((p+q) log(p+q)), multiway merge O(k n log k log n).
- standard math Forgetfulness principle: when m of n inputs remain unseen, the median lies in the middle m+1 values of the seen n-m inputs.
- domain assumption Data-oblivious networks can be compiled to register-resident min-max instruction sequences within the 255-register CUDA limit for small kernels.
- ad hoc to paper Root tile size heuristic t(k)=2^{floor(log2 k)-1} with a fixed split rule (split square tiles horizontally, longer side otherwise).
Cite this review
Pith. "Pith review of A Fast Parallel Median Filtering Algorithm Using Hierarchical Tiling." pith.science (2026). https://pith.science/paper/DWF6UONX
@misc{pith2026250719926,
author = {Pith},
title = {Pith review of: A Fast Parallel Median Filtering Algorithm Using Hierarchical Tiling},
year = {2026},
howpublished = {\url{https://pith.science/paper/DWF6UONX}},
note = {Machine review of arXiv:2507.19926}
}
abstract
Median filtering is a non-linear smoothing technique widely used in digital image processing to remove noise while retaining sharp edges. It is particularly well suited to removing outliers (impulse noise) or granular artifacts (speckle noise). However, the high computational cost of median filtering can be prohibitive. Sorting-based algorithms excel with small kernels but scale poorly with increasing kernel diameter, in contrast to constant-time methods characterized by higher constant factors but better scalability, such as histogram-based approaches or the 2D wavelet matrix. This paper introduces a novel algorithm, leveraging the separability of the sorting problem through hierarchical tiling to minimize redundant computations. We propose two variants: a data-oblivious selection network that can operate entirely within registers, and a data-aware version utilizing random-access memory. These achieve per-pixel complexities of $O(k \log(k))$ and $O(k)$, respectively, for a $k \times k$ kernel - unprecedented for sorting-based methods. Our CUDA implementation is up to 5 times faster than the current state of the art on a modern GPU and is the fastest median filter in most cases for 8-, 16-, and 32-bit data types and kernels from $3 \times 3$ to $75 \times 75$.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[3]
https://doi.org/10.1109/ISCAS.1992.230295 Francisco Claude, Gonzalo Navarro, and Alberto Ordóñez
1069–1072 vol.3. https://doi.org/10.1109/ISCAS.1992.230295 Francisco Claude, Gonzalo Navarro, and Alberto Ordóñez
- [17]
-
[19]
Parallel Processing Letters 2 (09 1992), 205–211
The Pairwise Sorting Network. Parallel Processing Letters 2 (09 1992), 205–211. https://doi.org/10.1142/S0129626492000337 Simon Perreault and Patrick Hebert
-
[23]
In 2018 IEEE Southwest Symposium on Image Analysis and Interpretation (SSIAI)
Efficient GPU-based implementation of the median filter based on a multi-pixel-per-thread framework. In 2018 IEEE Southwest Symposium on Image Analysis and Interpretation (SSIAI). 121–124. https://doi.org/10.1109/SSIAI.2018.8470318 Elias Stehle and Hans-Arno Jacobsen
-
[24]
A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs. InProceedings of the 2017 ACM International Conference on Man- agement of Data (Chicago, Illinois, USA) (SIGMOD ’17). Association for Computing Machinery, New York, NY, USA, 417–432. https://doi.org/10.1145/3035918.3064043 Deqing Sun, Stefan Roth, and Michael J. Black
arXiv 2017
- [27]
-
[1380]
https: //doi.org/10.1049/el:20062357 Donald E. Knuth
-
[1968]
Sorting networks and their applications. In Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference (Atlantic City, New Jersey)(AFIPS ’68 (Spring)). Association for Computing Machinery, New York, NY, USA, 307–314. https://doi.org/10.1145/1468075.1468121 G. Bradski
Show all 28 references
-
[1975]
Semiannual Report, Univ
Median filtering. Semiannual Report, Univ. of Southern California (1975). Gabriel Salvador, Juan M. Chau, Jorge Quesada, and Cesar Carranza
1975
-
[1979]
IEEE Transactions on Acoustics, Speech, and Signal Processing 27, 1 (1979), 13–18
A fast two-dimensional median filtering algorithm. IEEE Transactions on Acoustics, Speech, and Signal Processing 27, 1 (1979), 13–18. https://doi.org/10.1109/TASSP.1979.1163188 M. Jiang and D. Crookes
1979
-
[1992]
In 1992 IEEE International Symposium on Circuits and Systems (ISCAS) , Vol
Median filter architecture based on sorting networks. In 1992 IEEE International Symposium on Circuits and Systems (ISCAS) , Vol
1992
-
[1993]
IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 40, 11 (1993), 723–727
Sorting network based architectures for median filters. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 40, 11 (1993), 723–727. https://doi.org/10.1109/82.251840 C. Chakrabarti and S. Dhanani
1993 doi
-
[1995]
https://doi.org/10.1109/71
A multiway merge sorting network.IEEE Transactions on Parallel and Distributed Systems 6, 2 (1995), 211–215. https://doi.org/10.1109/71. 342136 Morgan McGuire
1995 doi
-
[2000]
The OpenCV Library. Dr. Dobb’s Journal of Software Tools (2000). C. Chakrabarti
2000
-
[2006]
Electronics Letters 42 (02 2006), 1379 –
High-performance 3D median filter architecture for medical image despeckling. Electronics Letters 42 (02 2006), 1379 –
2006
-
[2007]
IEEE Transactions on Image Processing 16, 9 (2007), 2389–2394
Median Filtering in Constant Time. IEEE Transactions on Image Processing 16, 9 (2007), 2389–2394. https://doi.org/10.1109/ TIP.2007.902329 Gilles Perrot, Stéphane Domas, and Raphaël Couturier
2007
-
[2010]
In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
Secrets of optical flow estimation and their principles. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2432–2439. https://doi.org/10.1109/CVPR.2010.5539939 Preeti Topno and Govind Murmu
2010
-
[2012]
In 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops and PhD Forum
Merge Path - Parallel Merging Made Simple. In 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops and PhD Forum . 1611–1618. https: //doi.org/10.1109/IPDPSW.2012.202 Ian Parberry
2012 doi
-
[2013]
Journal of Signal Processing Systems 75 (06 2013), 1–6
Fine-tuned High-speed Implementation of a GPU-based Median Filter. Journal of Signal Processing Systems 75 (06 2013), 1–6. https://doi.org/10.1007/s11265-013-0799-2 William K Pratt
2013 doi
-
[2014]
In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (New York, New York) (STOC ’14)
Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (New York, New York) (STOC ’14). Association for Computing Machinery, New York, NY, USA, 684–693. htt...
-
[2015]
Information Systems 47 (2015), 15–32
The wavelet matrix: An efficient wavelet tree for large alphabets. Information Systems 47 (2015), 15–32. https://doi.org/10.1016/j.is.2014.06.002 Bert Dobbelaere
2015 doi
-
[2016]
arXiv:1510.05970 [cs.CV] 8
Stereo Matching by Training a Convolutional Neural Network to Compare Image Patches. arXiv:1510.05970 [cs.CV] 8
-
[2017]
In 2017 IEEE International Conference on Circuits and Systems (ICCS)
Efficient preprocessing filters and mass segmentation techniques for mammogram images. In 2017 IEEE International Conference on Circuits and Systems (ICCS) . 408–413. https://doi.org/10.1109/ICCS1. 2017.8326032 Michael T. Goodrich
2017
-
[2018]
IEEE Transactions on Image Processing 27, 5 (2018), 2217–2228
Efficient Scalable Median Filtering Using Histogram-Based Op- erations. IEEE Transactions on Image Processing 27, 5 (2018), 2217–2228. https: //doi.org/10.1109/TIP.2017.2781375 Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter
2018
-
[2019]
In 2019 Devices for Integrated Circuit (DevIC)
An Improved Edge Detection Method based on Median Filter. In 2019 Devices for Integrated Circuit (DevIC) . 378–381. https: //doi.org/10.1109/DEVIC.2019.8783450 John W. Tukey
2019
-
[2021]
Fast median filters using separable sorting networks.ACM Trans. Graph. 40, 4, Article 70 (jul 2021), 11 pages. https://doi.org/10.1145/3450626.3459773 Andy Adinets and Duane Merrill
2021
-
[2022]
ArXiv abs/2206.01784 (2022)
Onesweep: A Faster Least Significant Digit Radix Sort for GPUs. ArXiv abs/2206.01784 (2022). https://api.semanticscholar.org/ CorpusID:249395262 K. E. Batcher
2022 arXiv
-
[2024]
https://github.com/bertdobbelaere/ SorterHunter
SorterHunter: An evolutionary approach to find small and low latency sorting networks — github.com. https://github.com/bertdobbelaere/ SorterHunter. [Accessed 06-03-2024]. M. Jayesh George and S. Perumal Sankar
2024
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.