“Constant Time Median Filter Using 2D Wavelet Matrix” by Moroto and Umetani
Conference:
Type(s):
Title:
- Constant Time Median Filter Using 2D Wavelet Matrix
Session/Category Title: Material and Rendering
Presenter(s)/Author(s):
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(r2) 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.
References:
1. Andrew Adams. 2021. Fast median filters using separable sorting networks. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–11.
2. Jérémy Barbay, Francisco Claude, and Gonzalo Navarro. 2010. Compact rich-functional binary relation representations. In Latin American Symposium on Theoretical Informatics. Springer, 170–183.
3. Kenneth E Batcher. 1968. Sorting networks and their applications. In Proceedings of the April 30–May 2, 1968, spring joint computer conference. 307–314.
4. Timo Beller, Simon Gog, Enno Ohlebusch, and Thomas Schnattinger. 2013. Computing the longest common prefix array based on the Burrows-Wheeler transform. Journal of Discrete Algorithms 18 (2013), 22–31.
5. Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan, et al. 1973. Time bounds for selection. J. Comput. Syst. Sci. 7, 4 (1973), 448–461.
6. Prosenjit Bose, Meng He, Anil Maheshwari, and Pat Morin. 2009. Succinct orthogonal range search structures on a grid with applications to text indexing. In Workshop on Algorithms and Data Structures. Springer, 98–109.
7. Gary Bradski. 2000. The openCV library. Dr. Dobb’s Journal: Software Tools for the Professional Programmer 25, 11 (2000), 120–123. https://github.com/opencv/opencv/
8. Tao Chen, Kai-Kuang Ma, and Li-Hui Chen. 1999. Tri-state median filter for image denoising. IEEE Transactions on Image processing 8, 12 (1999), 1834–1838.
9. Yu-Feng Chien, Wing-Kai Hon, Rahul Shah, and Jeffrey Scott Vitter. 2008. Geometric Burrows-Wheeler transform: Linking range searching and text indexing. In Data Compression Conference (dcc 2008). IEEE, 252–261.
10. Francisco Claude and Gonzalo Navarro. 2011. Self-indexed grammar-based compression. Fundamenta Informaticae 111, 3 (2011), 313–337.
11. Francisco Claude, Gonzalo Navarro, and Alberto Ordónez. 2015. The wavelet matrix: An efficient wavelet tree for large alphabets. Information Systems 47 (2015), 15–32.
12. Paolo Ferragina and Giovanni Manzini. 2005. Indexing compressed text. Journal of the ACM (JACM) 52, 4 (2005), 552–581.
13. JP Fitch, E Coyle, and Neal Gallagher. 1984. Median filtering by threshold decomposition. IEEE Transactions on Acoustics, Speech, and Signal Processing 32, 6 (1984), 1183–1188.
14. Oded Green. 2017. Efficient scalable median filtering using histogram-based operations. IEEE Transactions on Image Processing 27, 5 (2017), 2217–2228.
15. Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. 2003. High-order entropy-compressed text indexes. (2003).
16. Mark Harris, Shubhabrata Sengupta, and John D Owens. 2007. Parallel prefix sum (scan) with CUDA. GPU gems 3, 39 (2007), 851–876.
17. Charles Antony Richard Hoare. 1961a. Algorithm 64: quicksort. Commun. ACM 4, 7 (1961), 321.
18. Charles Antony Richard Hoare. 1961b. Algorithm 65: Find. Commun. ACM 4, 7 (jul 1961), 321–322.
19. Thomas Huang, GJTGY Yang, and Greory Tang. 1979. A fast two-dimensional median filtering algorithm. IEEE transactions on acoustics, speech, and signal processing 27, 1 (1979), 13–18.
20. Institute of Electrical and Electronics Engineers. 1985. IEEE Standard for Binary Floating-Point Arithmetic. IEEE Std 754-1985.
21. Kazufumi Ito and Kaiqi Xiong. 2000. Gaussian filters for nonlinear filtering problems. IEEE transactions on automatic control 45, 5 (2000), 910–927.
22. G. Jacobson. 1989. Space-efficient static trees and graphs. In 30th Annual Symposium on Foundations of Computer Science. 549–554.
23. Michael Kass and Justin Solomon. 2010. Smoothed local histogram filters. In ACM SIGGRAPH 2010 papers. 1–10.
24. Minsik Kim, Deokho Kim, Minyong Sung, and Won Woo Ro. 2015. An accelerated separable median filter with sorting networks. In 2015 IEEE International Conference on Image Processing (ICIP). IEEE, 803–807.
25. Sebastian Kreft and Gonzalo Navarro. 2013. On compressing and indexing repetitive sequences. Theoretical Computer Science 483 (2013), 115–133. Special Issue Combinatorial Pattern Matching 2011.
26. James Malcolm, Pavan Yalamanchili, Chris McClanahan, Vishwanath Venugopalakrishnan, Krunal Patel, and John Melonakos. 2012. ArrayFire: a GPU acceleration platform. In Modeling and simulation for defense systems and applications VII, Vol. 8403. International Society for Optics and Photonics, 84030A.
27. Morgan McGuire. 2008. A fast, small-radius GPU median filter. ShaderX6, February (2008).
28. Duane Merrill. 2015. Cub. NVIDIA Research (2015).
29. Yuji Moroto, Toshiya Hachisuka, and Nobuyuki Umetani. 2021. Fast Polygonal Splatting using Directional Kernel Difference. In Eurographics Symposium on Rendering – DL-only Track, Adrien Bousseau and Morgan McGuire (Eds.). The Eurographics Association.
30. Veli Mäkinen and Gonzalo Navarro. 2007. Rank and select revisited and extended. Theoretical Computer Science 387, 3 (2007), 332–347. The Burrows-Wheeler Transform.
31. Gonzalo Navarro. 2004. Indexing text using the Ziv-Lempel trie. Journal of Discrete Algorithms 2, 1 (2004), 87–114.
32. Gonzalo Navarro and Yakov Nekrich. 2012. Top-k document retrieval in optimal time and linear space. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1066–1077.
33. Simon Perreault and Patrick Hébert. 2007. Median filtering in constant time. IEEE transactions on image processing 16, 9 (2007), 2389–2394.
34. Gilles Perrot, Stéphane Domas, and Raphaël Couturier. 2014. Fine-tuned high-speed implementation of a GPU-based median filter. Journal of Signal Processing Systems 75, 3 (2014), 185–190.
35. Gilles Perrot, Stéphane Domas, and Raphaël Couturier. 2022. How Separable Median Filters Can Get Better Results than Full 2D Versions: Theoretical Approach, Experimental Study and GPU-Optimized Implementation. J. Supercomput. 78, 7 (may 2022), 10118–10148.
36. Jonathan Ragan-Kelley, Connelly Barnes, Andrew Adams, Sylvain Paris, Frédo Durand, and Saman Amarasinghe. 2013. Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. Acm Sigplan Notices 48, 6 (2013), 519–530.
37. Thomas Schnattinger, Enno Ohlebusch, and Simon Gog. 2010. Bidirectional search in a string with wavelet trees. In Annual Symposium on Combinatorial Pattern Matching. Springer, 40–50.
38. S Cheung Sen-Ching and Chandrika Kamath. 2004. Robust techniques for background subtraction in urban traffic video. In Visual Communications and Image Processing 2004, Vol. 5308. SPIE, 881–892.
39. JW Tukey. 1974. Nonlinear (nonsuperposable) methods for smoothing data. Proc. Cong. Rec. EASCOM’74 (1974), 673–681.
40. Ben Weiss. 2006. Fast median and bilateral filtering. In ACM SIGGRAPH 2006 Papers. 519–526.
