提出分层分块加速中值滤波，速度比现有方法快5倍。
A Fast Parallel Median Filtering Algorithm Using Hierarchical Tiling
- 用分层分块思想减少重复计算，分解排序问题。
- 实现每像素复杂度O(k log k)和O(k)，打破排序法瓶颈。
- 支持8~32位数据与3×3至75×75核，适配现代GPU加速。
中值滤波是数字图像处理中广泛使用的非线性平滑技术，能有效去除脉冲噪声或散斑噪声，同时保留边缘细节。但其高计算成本常成瓶颈。基于排序的算法在小核时表现优异，但随核尺寸增大而急剧下降；而常数时间方法虽具更好可扩展性，却有较高常数开销。本文提出一种新算法，利用排序问题的可分离性，通过分层分块策略最小化冗余计算。设计两种变体：完全在寄存器内运行的数据无关选择网络，以及利用随机访问内存的数据感知版本。二者对k×k核分别达到每像素O(k log k)和O(k)的复杂度，为排序类方法迄今最优。基于CUDA的实现，在现代GPU上速度达当前最先进水平的5倍，对8、16、32位数据及3×3至75×75核的多数情况均为最快。
原文摘要 · Abstract (English)
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$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。