Constant Time Median Filter using 2D Wavelet Matrix
Abstract
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.
Award
This paper got the SIGGRAPH Asia 2022 Best Paper Award.
Errata
- In Algorithm 3 (LowFreq), lines 6 and 10 are unnecessary (they do not affect the algorithm)
Supplementary Materials Code
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
- Improved readability
- Support for multiple channels
- Reduced memory usage by about 40~50%.
Yuji Moroto
Ph.D Course
Nobuyuki Umetani
Associate Professor
My research interests include interactive smart engineering design tool using physics simulation and machine learning.