Pith. sign in

REVIEW 2 major objections 4 minor 14 references

Fast Isotropic Median Filtering

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read An immutable 2D histogram called the omnigram makes exact circular median filtering fast for arbitrary bit depths, kernel sizes, and convex kernel shapes.

desk verdict A genuine extension of compound histograms to 2D enables exact circular-kernel median filtering at competitive speeds; the main caveats are an overbroad abstract and a data-dependent runtime that deserves a sharper worst-case discussion. read the letter →

arxiv 2505.22938 v1 pith:EKAXUBED submitted 2025-05-28 cs.CV cs.DS

Ben Weiss This is my paper
classification cs.CVcs.DS
keywords medianfilteringisotropicfiltercircularkernelomnigramordinaltransformrank-orderGPUimageprocessingarbitrarybitdepth
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 the usual trade-off in median filtering — square kernels are fast but leave streaky cross-hatching artifacts, while circular kernels look right but are slow — no longer needs to be made. It introduces the omnigram, an immutable two-dimensional histogram that records where every pixel's ordinal value sits in the image, so the count of values inside any circular window can be read in constant time without maintaining any mutable per-thread histograms. On top of this structure it runs a circular adaptation of the classic sliding-window pivot-and-count method, sliding many adjacent windows at once so the work vectorizes on both CPU and GPU. The result, according to the paper, is the first method that is simultaneously exact, efficient, arbitrary in bit depth and kernel size, and able to handle arbitrary convex kernel shapes including circles. If true, circular median filtering becomes practical for quality-sensitive uses such as photo editing and medical imaging, where square-kernel artifacts were previously accepted as normal.

What carries the argument

The omnigram, $\Omega_I$, is the central object: an array indexed by ordinal value whose entries are the (row, column) locations of that value in the ordinal-transformed image. Because ordinal values are unique, the histogram count of a value in any region is a single membership test, reducing circular-window histogram queries to point-in-circle tests. The algorithm's operation is a circular adaptation of the classic sliding-window pivot-and-count procedure, with pivots quantized to multiples of 64 so that 64-entry blocks of the omnigram can be reduced to 64-bit masks whose popcounts give coarse histogram bins; this keeps the median search vectorizable and branch-light.

What would settle it

Run the published implementation on an input tile that is a high-frequency black-and-white checkerboard surrounded by a thick solid gray border, as the paper's limitations section suggests, and compare wall-clock time per pixel against a natural-image tile at the same radius and bit depth; if the adversarial tile's runtime is not substantially worse, the coherence assumption is not the bottleneck the paper claims, while if it is substantially worse, the fast-for-all-inputs framing fails for that input class.

Watch

Extended reading notes

Core claim

The central discovery is that the earlier one-dimensional compound histogram idea can be lifted to two dimensions. In the ordinal-transformed image, every pixel value is unique, so a histogram entry for any region $R$ is just an indicator of whether the omnigram entry $\Omega_I[v]$ lies inside $R$; for a circular window centered at $P$ with radius $r$, that indicator is $\|\Omega_I[v]-P\|\le r$. This makes the omnigram a universal, immutable histogram from which any shaped window's counts can be obtained in constant time. The paper's algorithm then applies the classic pivot-and-count sliding-window scheme to circles, using quantized pivots (multiples of 64) and bitmask popcounts to scan the omnigram for exact medians, and slides many windows in parallel to keep memory access vectorized. The claim is that this yields exact isotropic median filtering that is faster than state-of-the-art square-kernel implementations for medium and large radii, on both CPU and GPU architectures.

Load-bearing premise

The speed claim rests on the assumption that neighboring median-filtered windows have nearly the same median, so the pivot saved for one window is a good starting point for the next; if that coherence fails, as the paper's own adversarial checkerboard-with-gray-border example shows, the omnigram scan becomes long and the runtime advantage disappears.

Editorial extensions

If this is right

  • Square-kernel cross-hatching artifacts disappear for exact median filtering, since the circular kernel is rotationally invariant.
  • Median filtering becomes practical on arbitrary bit-depth data, including 16-bit integers and floating-point HDR images, not just 8-bit images.
  • The method closes the gap between approximate isotropic median filters and exact ones, so exact isotropic output is available at speeds previously reserved for approximations.
  • Because the omnigram is immutable and shared across all windows, the same ordinal transform supports rank statistics beyond the median, including percentiles that vary continuously across the image.

Reading between the lines

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

  • The coherence assumption implies a hidden performance cliff: users with synthetic, periodic, or textural images should benchmark worst-case tiles, not just natural photos; a fallback that detects unusually long omnigram scans and switches to a direct histogram build could bound the worst case without changing results.
  • The omnigram's constant-time region query is not limited to circles; the same structure could support per-pixel adaptive regions or local rank statistics where the window shape changes across the image, which would otherwise be prohibitively expensive.
  • The 64-element bitmask scan suggests a natural hierarchy: storing coarse location summaries for blocks of 64 ordinal values would let the scan skip empty blocks, which could mitigate the adversarial case the paper identifies while preserving exactness.
  • For large radii and floating-point data, overlapping tiles currently re-sort the same pixels multiple times; pre-sorting the overlap regions, which the paper lists as future work, could yield near-linear scaling for very large 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

2 major / 4 minor

Summary. The paper presents a new exact median filtering algorithm based on an "omnigram," a per-tile, immutable data structure that maps each ordinal-transformed pixel value to its 2D location, thereby enabling constant-time histogram queries for arbitrary image regions. The algorithm slides circular kernel windows, using quantized pivots and targeted omnigram scans to find exact medians, and is implemented for both CPU and GPU. The paper claims state-of-the-art performance and quality, with benchmarks against several baselines and released source code.

Significance. The omnigram construction (Eqs. 2-3) is an elegant 2D extension of the author's prior compound-histogram idea, and the paper provides a working implementation with reproducible code. The correctness argument is self-contained and parameter-free, and the empirical comparison against external baselines (2DWM, CTMF, sorting networks) is a strength. If the performance claims hold, this would be a valuable contribution to practical isotropic median filtering. However, the advertised "arbitrary convex kernel shapes" and the unqualified "fast/state-of-the-art" claims are broader than what the main text actually demonstrates, and the data-dependent runtime is disclosed but not analyzed.

major comments (2)
  1. [Abstract and §6.1.3] The abstract claims the method "operates efficiently on arbitrary bit-depth data, arbitrary kernel sizes, and arbitrary convex kernel shapes, including circular shapes," and §1 lists circular-kernel processing as a primary contribution, but the main text only implements and benchmarks circular kernels; §6.1.3 defers other convex shapes to supplemental material. Since this advertised capability is load-bearing for the novelty claim, the paper should either include a concrete description and benchmark for at least one non-circular convex shape (e.g., a hexagon) or revise the abstract and contributions to claim circular kernels only.
  2. [§5, §6, §6.1.1] The per-pixel cost of the refinement phase is proportional to the ordinal distance between the previous quantized pivot (a multiple of 64) and the exact median of the current window; this distance is not bounded by kernel radius, tile size, or bit depth, and the algorithm has no fallback. Section 6 concedes an adversarial checkerboard-with-gray-perimeter input that can cause slow runtimes, and §6.1.1 states that no systematic coherence analysis exists. The benchmarks in §5 are on a single 37-megapixel natural image. Consequently, the unqualified "fast" and "state-of-the-art" claims in the abstract and §5 are not established for arbitrary input; please add a coherence bound, a fallback path for adversarial tiles, or an explicit qualification that the speedups hold for typical natural images.
minor comments (4)
  1. [§5, footnote 2] The claim that the method "strongly outperforms SOTA octagonal or 12-sided methods" is based on published performance estimates from Perreault and Moroto rather than direct measurements on the authors' own hardware; consider adding a direct baseline or changing the wording to "is estimated to strongly outperform."
  2. [§4, Eq. (5)] The notation around the ordinal image I and the cardinal input tile I_c is easy to confuse; please explicitly distinguish the input cardinal tile from the ordinal image in the pseudocode and surrounding text.
  3. [Acknowledgments] There is a typo in the acknowledgments: "and and assistance" should be "and assistance."
  4. [§2.2] In the sentence beginning "In our previous work ( [Weiss 2006]) we had improved...," the parentheses around the citation are awkward; also ensure consistent spelling of "Perreault" (the paper uses "Perrault" in §5, footnote 2).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the omnigram is defined directly from the input, the median scan follows Huang's pivot/count principle, benchmarks are external, and the Section 6 coherence caveat is a robustness limitation rather than a logical loop.

full rationale

The central derivation is self-contained. The omnigram (Eq. 2 and Eq. 3) is defined as the location of each ordinal value in the input tile, so a histogram element for any window is computed by a direct point-in-region test; it is not fitted, and the median output is not fed back into its construction. The median extraction follows Huang et al.'s [1979] pivot/count sliding-window principle, with the pivot chosen as a quantized value (multiple of 64) near the previous window's median; no parameter is fitted to a subset of data and then reported as a prediction. The self-citation to Weiss [2006] supplies the ordinal transform and its invariance under median filtering; that invariance is a standard order-statistic fact (any monotone rank-preserving relabeling commutes with the median), it is stated with its assumptions in Section 3.2 and illustrated in Fig. 4, and it is externally verifiable, so per the review rules it is real evidence rather than a circular loop. The paper's own Section 6 concedes that runtime is data-dependent and can degrade on adversarial inputs ('a high-frequency black-and-white checkerboard, with a thick solid gray perimeter'), which qualifies the abstract's unqualified 'efficiently' claim; however, this is a robustness/correctness caveat about an empirical performance statement, not a circular derivation, because the reported speedups are measured against independent external published code (Moroto and Umetani's 2DWM, Adams' Separable Sorting Networks, Perreault and Hebert's CTMF) rather than predicted from the method's own coherence assumption. No uniqueness theorem is imported from the authors' prior work, no ansatz is smuggled in via citation, and the omnigram is not a renamed known result: it is an inverted index (value-to-location) with its own correctness argument that enables arbitrary convex kernel shapes, distinct from Porikli's integral histogram and Moroto's wavelet matrix. No step in the derivation reduces by construction to its own input, so the circularity score is 0.

Assumptions & free parameters 4 free parameters · 5 assumptions · 1 invented entities

The central algorithm depends on standard properties of the ordinal transform and a few hand-chosen engineering constants (pivot quantization step, tile sizes, rightshift, seed counts). No physical entities or fitted scientific parameters are introduced; the omnigram is a data structure with independent code support.

free parameters (4)
  • Pivot quantization step = 64 or 128
    Chosen by hand to align vector scans and enable 8-bit storage of the ordinal image; affects speed and memory, not correctness. Introduced in Sec. 4.
  • Input/output tile sizes = 256x256 input (CPU); 32x32 or 64x64 output (GPU)
    Chosen to bound omnigram bit width (8 or 16 bits per element) and fit shared memory on GPU; affects working set and parallelism. Sec. 4.
  • GPU ordinal rightshift = 6 bits (r <= 48), 7 bits (r <= 96)
    Chosen to quantize the ordinal image into 8-bit shared memory for a given radius range; impacts precision of stored ordinal values but not correctness. Sec. 4.1.
  • GPU seed count = 32 or 64 per tile
    Chosen to saturate 32-way warp parallelism; affects the parallel solving strategy, not correctness. Sec. 4.1.
assumptions (5)
  • standard math The ordinal transform preserves the rank order of values in any subregion, so median filtering is invariant under it.
    Restated from Weiss (2006) in Sec. 3.2 and used to justify the single-bit histogram representation.
  • standard math For a unique-valued ordinal image, H_R[v] = 1 iff the location stored in the omnigram for value v lies inside region R.
    Given as Eq. 2 and Eq. 3; the correctness of histogram extraction rests on this equivalence.
  • standard math When a sliding window moves, the count of values below a fixed pivot changes only by the entering and leaving pixels.
    Huang et al.'s pivot/count principle, adopted in Sec. 3.3 and used for the horizontal and vertical sweeps.
  • standard math Quantizing pivots to multiples of 64 and discarding the low 6 bits of the ordinal image does not change comparisons with the pivot.
    Stated in Sec. 4; since pivots are multiples of 64, the low bits do not affect the outcome of comparisons.
  • domain assumption The key-value sort is stable when solutions are forwarded between overlapping tiles, preserving relative coordinate order.
    Required in Sec. 4 for the forwarding optimization; stability is a property of the chosen sort implementation.
invented entities (1)
  • Omnigram, denoted Omega_I independent evidence
    purpose: A 2D array encoding the spatial location of every ordinal value in an image tile, enabling constant-time membership tests of any value against any image region.
    The omnigram is a data structure, not a physical postulate. Independent evidence is the public GitHub implementation and the benchmark claims, which a third party can verify.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Isotropic Median Filtering." pith.science (2026). https://pith.science/paper/EKAXUBED

@misc{pith2026250522938,
  author       = {Pith},
  title        = {Pith review of: Fast Isotropic Median Filtering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EKAXUBED}},
  note         = {Machine review of arXiv:2505.22938}
}
read the original abstract

Median filtering is a cornerstone of computational image processing. It provides an effective means of image smoothing, with minimal blurring or softening of edges, invariance to monotonic transformations such as gamma adjustment, and robustness to noise and outliers. However, known algorithms have all suffered from practical limitations: the bit depth of the image data, the size of the filter kernel, or the kernel shape itself. Square-kernel implementations tend to produce streaky cross-hatching artifacts, and nearly all known efficient algorithms are in practice limited to square kernels. We present for the first time a method that overcomes all of these limitations. Our method operates efficiently on arbitrary bit-depth data, arbitrary kernel sizes, and arbitrary convex kernel shapes, including circular shapes.

Figures

Figures reproduced from arXiv: 2505.22938 by the authors.

Figure 1
Figure 1. Top row: Original photo, median-filtered with a radius-48 square kernel (with hand-applied matte), and with an equivalent-area circular kernel. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Median-filtering binary noise with increasingly isotropic kernel shapes. By observing the cross-hatching artifacts introduced by filtering noise with [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Sliding-window method of Huang et al. [1979]. (a) As the top left 5x5 window slides one pixel to the right, blue-shaded pixels are added to a running histogram, and yellow-shaded pixels removed. (b) The method as adapted to a 21-tap circular kernel [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: Ordinal transform of Weiss [2006]. Cardinal brightness values (left) map to their respective ordinal ranks (right), creating an "ordinal image." Duplicate cardinal values (yellow) map to consecutive ordinal values. Note that the median values in e.g. the blue squares (…
Figure 6
Figure 6. Figure 6: Ordinal image and omnigram. Binary histogram elements (right) of [PITH_FULL_IMAGE:figures/full_fig_p004_6.png]
Figure 7
Figure 7. Figure 7: Processing the first row. For sliding the circular kernel window hori [PITH_FULL_IMAGE:figures/full_fig_p004_7.png]
Figure 8
Figure 8. Figure 8: Sliding vertically. (a) When a single non-rectangular window is slid [PITH_FULL_IMAGE:figures/full_fig_p004_8.png]
Figure 9
Figure 9. Figure 9: CPU vs. GPU implementations. (a) On CPU, for the top tile in a column, we begin by solving the top left pixel (red), then step across the top row (blue), [PITH_FULL_IMAGE:figures/full_fig_p005_9.png]
Figure 10
Figure 10. Figure 10: Tile geometry on GPU. For the radius-48 case, each output tile is [PITH_FULL_IMAGE:figures/full_fig_p006_10.png]
Figure 11
Figure 11. Figure 11: Performance results on CPU and GPU. As our focus is on isotropic filtering, square-kernel implementations are shown with dashed lines. [PITH_FULL_IMAGE:figures/full_fig_p007_11.png]
Figure 12
Figure 12. Figure 12: Rank-order "bracketing", for a range of percentiles. Our circular-kernel implementation is shown across the top; an equivalent square-kernel [PITH_FULL_IMAGE:figures/full_fig_p009_12.png]
Figure 13
Figure 13. Figure 13: Rotational invariance. The 16-bit input (left) is rotated 22.5 [PITH_FULL_IMAGE:figures/full_fig_p009_13.png]
Figure 14
Figure 14. Figure 14: Varying percentiles reveals different image characteristics. Here the input, and 10th, 30th, 50th, 70th, and 90th percentiles, with our radius-48 filter. [PITH_FULL_IMAGE:figures/full_fig_p010_14.png]
Figure 15
Figure 15. Figure 15: The requested percentile does not need to be constant. Input (left), output (right). Our method can be modified to allow the percentile to vary [PITH_FULL_IMAGE:figures/full_fig_p010_15.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

14 extracted references · 7 canonical work pages

  1. [1]

    https://doi.org/10.1109/CVPR.2005.188 John W. Tukey

    work page doi:10.1109/cvpr.2005.188 2005

  2. [13]

    Constant Time Median and Bilateral Filtering. Int. J. Comput. Vision 112, 3 (May 2015), 307–318. https: //doi.org/10.1007/s11263-014-0764-y 8 Fast Isotropic Median Filtering SIGGRAPH Conference Papers ’25, August 10–14, 2025, Vancouver, BC, Canada Fig

    work page doi:10.1007/s11263-014-0764-y 2015

  3. [14]

    The 16-bit input (left) is rotated 22.5 ° in either direction with bicubic resampling, filtered with equivalent-area square and circular median filters, then rotated back

    Rotational invariance. The 16-bit input (left) is rotated 22.5 ° in either direction with bicubic resampling, filtered with equivalent-area square and circular median filters, then rotated back. Our circular-filtered results match each other ~35x more precisely under rotation than standard square-filtered results. (Standard deviation 0.06 levels versus 2....

    work page 2025

  4. [1968]

    In Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference

    Sorting networks and their applications. In Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference . ACM, ACM, New York, NY, USA, 307–314. https://doi.org/10.1145/1468075.1468121 CCCL Development Team

    arXiv 1968

  5. [1974]

    In In 1974 EASCON convention record

    Nonlinear (nonsuperposable) methods for smoothing data. In In 1974 EASCON convention record . IEEE, IEEE, New York, New York, NY,

    work page 1974

  6. [1979]

    IEEE Transactions on Acoustics, Speech, and Signal Processing ASSP-27, 1 (jan 1979), 13–18

    A Fast Two-Dimensional Median Filtering Algorithm. IEEE Transactions on Acoustics, Speech, and Signal Processing ASSP-27, 1 (jan 1979), 13–18. https://doi.org/10.1109/TASSP.1979.1163188 Michael Kass and Justin Solomon

    arXiv 1979

  7. [2006]

    ACM Trans

    Fast Median and Bilateral Filtering. ACM Trans. Graph. 25, 3 (jul 2006), 519–526. https://doi.org/10.1145/1141911.1141918 Qingxiong Yang, Narendra Ahuja, and Kar-Han Tan

    arXiv 2006

  8. [2007]

    IEEE Transactions on Image Processing 16, 9 (sep 2007), 2389–2394

    Median Filtering in Constant Time. IEEE Transactions on Image Processing 16, 9 (sep 2007), 2389–2394. https://doi.org/10. 1109/TIP.2007.902329 Fatih Porikli

    arXiv 2007

Show all 14 references
  1. [2008]

    https://doi.org/10.2312/HPG/HPG08/059-066 Deepa Mishra, Sangeeta Sharma, and V.K

    Eurographics Association, Eurographics Association, Aire-la-Ville, Switzerland, 59–66. https://doi.org/10.2312/HPG/HPG08/059-066 Deepa Mishra, Sangeeta Sharma, and V.K. Shandilya

    doi

  2. [2010]

    ACM Trans

    Smoothed local histogram filters. ACM Trans. Graph. 29, 4, Article 100 (jul 2010), 10 pages. https://doi.org/10.1145/1778765.1778837 Morgan McGuire

    2010

  3. [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 T.S. Huang, G.J. Yang, and G.Y. Tang

    2015 doi

  4. [2020]

    International Journal of Biomedical Engineering and Technology 36, 4 (2020), 364–382

    A Circular Adaptive Median Filter for Salt and Pepper Noise Suppression from MRI Images. International Journal of Biomedical Engineering and Technology 36, 4 (2020), 364–382. Yuji Moroto and Nobuyuki Umetani

    2020

  5. [2021]

    ACM Trans

    Fast Median Filters using Separable Sorting Networks. ACM Trans. Graph. 40, 4 (aug 2021), 1–11. https://doi.org/10.1145/3450626.3459773 Kenneth E. Batcher

    2021

  6. [2022]

    ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–13

    Fast median filters using 2D wavelet matrix. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–13. https://doi.org/10.1145/ 3550454.3555512 Simon Perreault and Patrick Hébert

    2022

Pith tools

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