Pith. sign in

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 →

arxiv 2507.19926 v1 pith:DWF6UONX submitted 2025-07-26 cs.DC cs.CV

classification cs.DCcs.CV
keywords medianfiltersortingnetworkGPUparallelalgorithmhierarchicaltilingselectionimageprocessingdata-oblivious
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that median filtering, long considered too expensive for large kernels and high bit depths, can be made much faster by reusing sorted intermediate results across overlapping kernels. It introduces hierarchical tiling: a tile of pixels is split recursively, and at each split the already-sorted core of each child kernel is extended with only the newly exposed rows, columns, and corners while extrema are discarded. From this, two GPU algorithms follow: a data-oblivious selection network with per-pixel complexity O(k log k), and a data-aware multi-pass version with O(k) per-pixel complexity, both computing exact medians. If correct, these are the first sorting-based median filters with these complexities, and the paper's benchmarks show them ahead of existing GPU implementations for most kernel sizes from 3x3 to 75x75 across 8-, 16-, and 32-bit data.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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)
  1. [§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.
  2. [§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.
  3. [§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)
  1. [§2.2] 'Perrot el al.' should be 'Perrot et al.'
  2. [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).
  3. [§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).
  4. [§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

0 steps flagged · score 0.0 of 10

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 2 free parameters · 4 assumptions · 0 invented entities

The central theoretical claims rest on standard sorting and merging network bounds and the forgetfulness lemma; the paper-specific free choices are the root tile heuristic and per-kernel CUDA configuration. There are no invented physical or mathematical entities.

free parameters (2)
  • Root tile size t(k) (heuristic) = 2^{floor(log2 k)-1}
    Chosen by the author to balance shared work versus final steps; used in the complexity proof rather than fitted to data.
  • Thread-block configuration (threads, tiles per block, mapping) = varies; not reported
    Section 4.3: the most efficient configuration is selected per kernel size and data type, affecting measured speedups but not complexity.
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).
    Used in Section 4.2 to bound initialization and recursion cost for the data-oblivious variant.
  • 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.
    Used throughout the recursion to discard extrema from sorted cores (Section 2.2, Figure 3).
  • domain assumption Data-oblivious networks can be compiled to register-resident min-max instruction sequences within the 255-register CUDA limit for small kernels.
    Assumed in Section 4.3; this assumption limits the data-oblivious variant to roughly 15x15 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).
    Introduced in Section 4.2 to make root tile size linear in k; not derived from prior theory.

how reviews work

0 comments
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 reproduced from arXiv: 2507.19926 by the authors.

Figure 1
Figure 1. A 17 × 17 median filter is applied to smooth a 30-megapixel photograph. The 8-bit red, green, and blue channels are filtered separately. Thanks to a computationally efficient and GPU-friendly algorithm, our method takes only 2.2 ms on an L40S GPU — 3 times faster than the current state of the art. Median filtering is a non-linear smoothing technique widely used in digital image processing to remove noise while retai… view at source ↗
Figure 2
Figure 2. A selection network that computes the median of 5 inputs. Knuth [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Illustration of the principle of forgetfulness when selecting the me [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (3 more)
Figure 5
Figure 5. Figure 5: Footprint of a 4 × 4 tile for a 9 × 9 kernel. (a) Outlines of the kernels for two pixels at opposite ends of the tile. (b) Partition of the tile’s footprint into a core (the intersection of all 16 kernels), extra columns, extra rows, and corners. At each tile subdivisi…
Figure 7
Figure 7. Figure 7: Compute graph of the multi-pass algorithm, using an [PITH_FULL_IMAGE:figures/full_fig_p006_7.png]
Figure 8
Figure 8. Figure 8: Pixel throughput (higher is better) of various median filtering methods on an NVIDIA L40S GPU. The two implementations of our algorithm combined [PITH_FULL_IMAGE:figures/full_fig_p007_8.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

28 extracted references · 19 canonical work pages

  1. [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

  2. [17]

    ACM Trans

    Constant Time Median Filter Using 2D Wavelet Matrix. ACM Trans. Graph. 41, 6, Article 267 (nov 2022), 10 pages. https: //doi.org/10.1145/3550454.3555512 Saher Odeh, Oded Green, Zahi Mwassi, Oz Shmueli, and Yitzhak Birk

  3. [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

  4. [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

  5. [24]

    InProceedings of the 2017 ACM International Conference on Man- agement of Data (Chicago, Illinois, USA) (SIGMOD ’17)

    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

  6. [27]

    ACM Trans

    Fast median and bilateral filtering. ACM Trans. Graph. 25, 3 (July 2006), 519–526. https://doi.org/10.1145/1141911.1141918 Jure Žbontar and Yann LeCun

  7. [1380]

    https: //doi.org/10.1049/el:20062357 Donald E. Knuth

  8. [1968]

    In Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference (Atlantic City, New Jersey)(AFIPS ’68 (Spring))

    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
  1. [1975]

    Semiannual Report, Univ

    Median filtering. Semiannual Report, Univ. of Southern California (1975). Gabriel Salvador, Juan M. Chau, Jorge Quesada, and Cesar Carranza

  2. [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

  3. [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

  4. [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

  5. [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

  6. [2000]

    The OpenCV Library. Dr. Dobb’s Journal of Software Tools (2000). C. Chakrabarti

  7. [2006]

    Electronics Letters 42 (02 2006), 1379 –

    High-performance 3D median filter architecture for medical image despeckling. Electronics Letters 42 (02 2006), 1379 –

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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...

  13. [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

  14. [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

  15. [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

  16. [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

  17. [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

  18. [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

  19. [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

  20. [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

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.