Fast Isotropic Median Filtering Conference: Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers ; August 10–14, 2025; Vancouver, BC, Canada Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers (SIGGRAPH Co
Ben Weiss · 2025
Read Fast Isotropic Median Filtering Conference: Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers ; August 10–14, 2025; Vancouver, BC, Canada Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers (SIGGRAPH Co by Ben Weiss (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22938.txt.
Introduction
Ben Weiss presents a faster way to run median filters on images with round kernels. Median filtering smooths images while keeping edges sharp, and it shrugs off noise and outliers. Past fast methods forced trade-offs in bit depth, kernel size, or kernel shape, and square kernels leave streaky cross-hatch marks. His 2025 paper, written for a computer graphics venue, claims a method free of all three limits.
The algorithm handles data of any bit depth and kernels of any size. It also allows any convex kernel shape, circles included, which square-only methods cannot do cleanly. Graphics and image processing readers get a filter that keeps the round look without the usual cost.
Catalog record
| CREATOR | Ben Weiss |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-22938
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast Isotropic Median Filtering Conference: Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers ; August 10–14, 2025; Vancouver, BC, Canada Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers (SIGGRAPH Conference Papers ’25), August 10–14, 2025, Vancouver, BC, Canada DOI: 10.1145/3721238.3730763 ISBN: 979-8-4007-1540-2/2025/08 Conference: Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers; August 10–14, 2025; Vancouver, BC, Canada Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers (SIGGRAPH Conference Papers ’25), August 10–14, 2025, Vancouver, BC, Canada CCS: Computing methodologies Image processing Ben Weiss 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. 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. Bottom row: square vs. circular filtered image quality for binary noise, as well as for two swatches from the image, unsharp-masked 200% to emphasize the high-frequency artifacts. Across a wide range of parameters, our circular median filter is dramatically faster and higher quality than the state of the art. Side-by-side photo comparison illustrating our method’s quality improvement. Side-by-side illustration of an original photo of a bongo (African antelope) standing in front of some trees; the same photo median-filtered with square kernel; and then median-filtered with circular kernel, illustrating the image quality improvement obtained by using a circular kernel instead of square. Across the bottom of the figure are smaller swatches illustrating square-versus-circular-kernel image quality differences: first for pure binary noise, and then for two zoomed-in representative samples from the photo. † † authorsaddresses: Authors’ address: Ben Weiss , Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA, 94043, USA 1. Introduction The median filter ( Tukey 1974 ) is a foundational element of classical signal processing. Extended to two dimensions ( Huang et al. 1979 ) , it allows removal of image noise and smoothing of edges, without the softening that is characteristic of e.g., Gaussian blur. Historically it has been fairly inefficient and artifact-prone; the nonlinear nature of the filter has resisted optimization attempts through vectorization techniques, and the ubiquitous square-kernel implementation produces distinct cross-hatching visual artifacts that reduce the filter’s usefulness for quality-sensitive applications. In this paper, we present an algorithm that performs efficient median filtering using a circular kernel, substantially improving image quality while attaining state-of-the-art performance for medium and large kernel sizes. Our primary contributions are as follows: • Extension of the 1D compound histogram technique from Weiss ( Weiss 2006 ) to a more general and powerful 2D "omnigram" data structure, from which histogram elements of any ordinal image region of any shape can be obtained in constant time. • A rank-order-filtering algorithm capable of processing circular kernel shapes, eliminating the visual artifacts characteristic of square-kernel filtering, while achieving state-of-the-art performance, even compared to the best existing square-kernel implementations. After reviewing related work in section 2 , we give an overview of our method in section 3 . We then describe our implementation in detail in section 4 and provide results and comparative studies in section 5 . Code and data for this paper are at: https://github.com/google/fast-isotropic-median-filter . 2. Related Work Figure 2 . Median-filtering binary noise with increasingly isotropic kernel shapes. By observing the cross-hatching artifacts introduced by filtering noise with low-order polygonal kernels, the importance of using near-isotropic kernels (ideally 12-sided or circular) to obtain optimal image quality is strikingly evident. Comparison of median filter artifacts for various polygonal and circular kernels. Six images are shown side-by-side, illustrating the results of median-filtering pure binary noise with 4-, 6-, 8-, 10-, 12-sided polygonal kernels and a circular kernel, respectively. The visual cross-hatching artifacts are very strong in the square-kernel case and become less and less noticeable as the polygons gain more sides, until the artifacts are barely perceptible in the 12-sided-kernel case, and imperceptible in the circular-kernel case. Approach Runtime Implementations Sorting Networks \hbox to0.0pt{\hss$\sim$\hskip 2.0pt}O(r^{2}) McGuire ( McGuire 2008 ) Adams ( Adams 2021 ) Sliding-Window Histograms O(r) , O(\log^{k}(r)) , O(1) , \hbox to0.0pt{\hss$\sim$\hskip 2.0pt}O(r) Huang et al. ( Huang et al. 1979 ) Weiss ( Weiss 2006 ) Perreault and Hébert ( Perreault and Hébert 2007 ) Our method Integral Queries O(1) Moroto and Umetani ( Moroto and Umetani 2022 ) Isotropic Approximations O(1) Kass and Solomon ( Kass and Solomon 2010 ) Yang et al. ( Yang et al. 2015 ) 2.1. Sorting Networks Sorting networks were introduced by Batcher ( Batcher 1968 ) , where inputs are sorted directly using a fixed sequence of min-max swaps to obtain the median. McGuire ( McGuire 2008 ) pioneered this approach for 3x3 and 5x5 kernels, and Adams ( Adams 2021 ) extended it to larger kernels using separable sorting networks. For square kernels of fairly small size, this is the most efficient known technique. However, it becomes impractically slow for large kernels. 2.2. Sliding-Window Histograms Other methods involve explicit histograms that are maintained and updated using sliding windows. Originated by Huang et al. ( Huang et al. 1979 ) , this provides a canonical baseline O(r) algorithm for 8-bit images. In our previous work ( ( Weiss 2006 ) ) we had improved on the sliding-window technique for 8-bit images by constructing hierarchical trees of histograms, improving the runtime from O(r) to O(log(r)) , and also extended the method to higher bit-depths in O(log^{2}(r)) time. Perreault and Hébert ( Perreault and Hébert 2007 ) employed a sliding-window technique over single-column histograms, yielding a constant-time median filtering algorithm for 8-bit data. 2.3. Integral Queries Porikli ( Porikli 2005 ) first recognized that small (e.g. 8-bit) histograms could be spatially integrated, yielding summed-area-table-like structures from which histogram components of any rectangular region could be extracted in constant time. More recently, Moroto and Umetani ( Moroto and Umetani 2022 ) extended the 1D wavelet matrix technique of Claude et al. ( Claude et al. 2015 ) to process arbitrary-depth 2D images, allowing efficient and arbitrary 2D rectangular rank-order queries and median filtering in constant time. 2.4. Isotropic Approximations The characteristic cross-hatching artifacts [Fig. 2 (a)] of square-kernel median filters have long been recognized, but the algorithmic costs of avoiding these artifacts have been difficult to overcome, particularly for exact filters. Thus, most current implementations (e.g. OpenCV, Adobe Photoshop) support only square-kernel median filtering. Mishra et al. ( Mishra et al. 2020 ) described the qualitative advantages of using an approximately circular kernel to median-filter medical MRI images, although they were limited to very small kernels. Perreault and Hébert ( Perreault and Hébert 2007 )