The median filter is a simple yet powerful noise reduction technique that is extensively applied in image, signal, and speech processing. It can effectively remove impulsive noise while preserving the content of the image by taking the median of neighboring pixels; thus, it has various applications, such as restoration of a damaged image and facial beautification. The median filter is typically implemented in one of two major approaches: the histogram-based method, which requires O(1) computation time per pixel when focusing on the kernel radius r, and the sorting-based method, which requires approximately O(r^2) computation time per pixel but has a light constant factor. These are used differently depending on the kernel radius and the number of bits in the image. However, the computation time is still slow, particularly when the kernel radius is in the mid to large range. This paper introduces novel and efficient median filter with constant complexity O(1) for kernel size using the wavelet matrix data structure, which has been applied to query-based searches on one-dimensional data. We extended the original wavelet matrix to two-dimensional data for application to computer graphics problems. The objective of this study was to achieve high-speed median filter computation in parallel computing environment with many threads (i.e., GPUs). Our implementation for the GPU is an order of magnitude faster than the histogram method for 8-bit images. Unlike traditional histogram methods, which suffer from significant computational overhead, the proposed method can handle images with high pixel depth (e.g., 16- and 32-bit high dynamic range images). When the kernel radius is greater than 12 for 8-bit images, the proposed method outperforms the other median filter computation methods.
This paper got the SIGGRAPH Asia 2022 Best Paper Award.
We are currently preparing an implementation of a median filter using wavelet matrix for release on GitHub. Until the GitHub repository is ready for publication, we are publishing the supplementary materials code for the paper submission. This code is based on the Supplemental Material Code for “Fast median filters using separable sorting networks” [Adams 2021], with the addition of our methods. This supplementary materials includes code for CPUs, where readability is more important than speed, and code for CUDAs, where speed is the highest priority.
The GitHub version, to be released in November, will include the following updates