A Fast Parallel Median Filtering Algorithm Using Hierarchical Tiling
作者: Louis Sugy
分类: cs.DC, cs.CV
发布日期: 2025-07-26
备注: 8 pages, 8 figures
期刊: SIGGRAPH Conference Papers '25, August 10-14, 2025, Vancouver, BC, Canada
💡 一句话要点
提出基于分层平铺的快速并行中值滤波算法，显著提升GPU上的滤波速度。
🎯 匹配领域: 支柱八：物理动画 (Physics-based Animation)
关键词: 中值滤波 图像处理 并行算法 CUDA 分层平铺
📋 核心要点
- 传统中值滤波计算量大，基于排序的算法在核较大时效率低，难以满足实时性要求。
- 论文提出分层平铺策略，将排序问题分解为可分离的子问题，减少冗余计算，提升效率。
- CUDA实现表明，该方法在现代GPU上比现有技术快5倍，是8-32位数据类型下最快的中值滤波器。
📝 摘要（中文）
中值滤波是一种非线性平滑技术，广泛应用于数字图像处理中，能够在去除噪声的同时保留图像的锐利边缘。它尤其擅长去除离群值（脉冲噪声）或颗粒状伪影（散斑噪声）。然而，中值滤波的高计算成本可能令人望而却步。基于排序的算法在小核上表现出色，但随着核直径的增加，其性能会迅速下降。相比之下，基于直方图或二维小波矩阵等常数时间方法虽然具有较高的常数因子，但具有更好的可扩展性。本文提出了一种新颖的算法，利用分层平铺实现排序问题的可分离性，从而最大限度地减少冗余计算。我们提出了两种变体：一种可以在寄存器内完全运行的数据无关选择网络，以及一种利用随机存取存储器的数据感知版本。对于 k × k 核，这些变体分别实现了 O(k log(k)) 和 O(k) 的每像素复杂度，这对于基于排序的方法来说是前所未有的。我们的 CUDA 实现比当前最先进的 GPU 实现快 5 倍，并且在大多数情况下，对于 8 位、16 位和 32 位数据类型以及 3 × 3 到 75 × 75 的核，它是最快的中值滤波器。
🔬 方法详解
问题定义：论文旨在解决中值滤波计算复杂度高的问题，尤其是在大尺寸滤波核的情况下。现有基于排序的算法虽然在小核上表现良好，但随着核尺寸增大，排序操作的计算量急剧增加，成为性能瓶颈。传统的直方图方法虽然复杂度较低，但常数因子较高，实际性能提升有限。
核心思路：论文的核心思路是利用分层平铺（Hierarchical Tiling）策略，将二维中值滤波问题分解为多个一维排序子问题。通过这种方式，可以有效地利用图像数据的局部相关性，避免重复计算，从而降低整体计算复杂度。
技术框架：该算法主要包含以下几个阶段：1. 分层平铺：将输入图像划分为多个小的重叠瓦片（tiles）。2. 局部排序：在每个瓦片内部进行局部排序，得到局部中值。3. 合并排序：将相邻瓦片的局部中值进行合并排序，得到全局中值。论文提出了两种变体：数据无关选择网络（Data-Oblivious Selection Network）和数据感知版本（Data-Aware Version）。前者完全在寄存器中操作，后者利用随机存取存储器。
关键创新：该算法的关键创新在于将二维中值滤波问题转化为可分离的一维排序问题，并通过分层平铺策略最大限度地减少了冗余计算。数据无关选择网络和数据感知版本分别针对不同的硬件架构进行了优化，实现了更高的并行度和效率。
关键设计：数据无关选择网络的设计目标是在寄存器中完成所有计算，避免访存开销。数据感知版本则利用随机存取存储器来存储中间结果，从而可以处理更大的滤波核。具体的参数设置包括瓦片的大小、排序算法的选择等。论文中没有提及损失函数或网络结构，因为该算法并非基于深度学习。
🖼️ 关键图片
📊 实验亮点
实验结果表明，该算法在现代GPU上比当前最先进的中值滤波算法快5倍。对于8位、16位和32位数据类型，以及3x3到75x75的滤波核尺寸，该算法在大多数情况下都是最快的。这表明该算法具有很高的实用价值和竞争力。
🎯 应用场景
该算法可广泛应用于图像处理、计算机视觉、医学影像分析等领域，尤其是在需要实时性或处理大规模图像数据的场景下。例如，在自动驾驶系统中，可以使用该算法对摄像头采集的图像进行去噪处理，提高目标检测和识别的准确性。在医学影像领域，可以用于去除CT或MRI图像中的噪声，提高诊断的准确性。
📄 摘要（原文）
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$.