“Fast median filters using separable sorting networks” by Adams

Median filters are a widely-used tool in graphics, imaging, machine learning, visual effects, and even audio processing. Currently, very-small-support median filters are performed using sorting networks, and large-support median filters are handled by O(1) histogram-based methods. However, the constant factor on these O(1) algorithms is large, and they scale poorly to data types above 8-bit integers. On the other hand, good sorting networks have not been described above the 7 X 7 case, leaving us with no fast way to compute integer median filters of modest size, and no fast way to compute floating point median filters for any size above 7 X 7.This paper describes new sorting networks that efficiently compute median filters of arbitrary size. The key idea is that these networks can be factored to exploit the separability of the sorting problem – they share common work across scanlines, and within small tiles of output. We also describe new ways to run sorting networks efficiently, using a sorting-specific instruction set, compiler, and interpreter.The speed-up over prior work is more than an order of magnitude for a wide range of data types and filter sizes. For 8-bit integers, we describe the fastest median filters for all sizes up to 25 X 25 on CPU, and up to 33 X 33 on GPU. For higher-precision types, we describe the fastest median filters at all sizes tested on both CPU and GPU.

1. Kenneth E Batcher. 1968. Sorting networks and their applications. In Proceedings of the April 30–May 2, 1968, spring joint computer conference. 307–314.Google ScholarDigital Library
2. G. Bradski. 2000. The OpenCV Library. Dr. Dobb’s Journal of Software Tools (2000). Michael Codish and Moshe Zazon-Ivry. 2010. Pairwise cardinality networks. In International Conference on Logic for Programming Artificial Intelligence and Reasoning. Springer, 154–172.Google Scholar
3. Derry Fitzgerald. 2010. Harmonic/percussive separation using median filtering. In Proceedings of the International Conference on Digital Audio Effects (DAFx), Vol. 13.Google Scholar
4. William T Freeman. 1988. Median filter for reconstructing missing color samples. US Patent 4,724,395.Google Scholar
5. Oded Green. 2017. Efficient scalable median filtering using histogram-based operations. IEEE Transactions on Image Processing 27, 5 (2017), 2217–2228.Google ScholarCross Ref
6. Wenzel Jakob. 2019. Enoki: structured vectorization and differentiation on modern processor architectures. https://github.com/mitsuba-renderer/enoki.Google Scholar
7. Michał Karpiński and Marek Piotrów. 2019. Encoding cardinality constraints using multiway merge selection networks. Constraints 24, 3–4 (2019), 234–251.Google ScholarDigital Library
8. Michael Kass and Justin Solomon. 2010. Smoothed local histogram filters. In ACM SIGGRAPH 2010 papers. 1–10.Google ScholarDigital Library
9. 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.Google ScholarDigital Library
10. Donald E. Knuth. 1998. The Art of Computer Programming (3rd ed.). Fundamental Algorithms, Vol. 1. Addison Wesley Longman Publishing Co., Inc. (book).Google ScholarDigital Library
11. Morgan McGuire. 2008. A Fast, Small-Radius GPU Median Filter. In Published in ShaderX6. https://casual-effects.com/research/McGuire2008Median/index.html ShaderX6.Google Scholar
12. NVIDIA. 2020. NVIDIA Performance Primitives. https://developer.nvidia.com/NPP.Google Scholar
13. Ian Parberry. 1992. The pairwise sorting network. Parallel Processing Letters 2, 02n03 (1992), 205–211.Google ScholarCross Ref
14. Grégoire Pau, Florian Fuchs, Oleg Sklyar, Michael Boutros, and Wolfgang Huber. 2010. EBImage—an R package for image processing with applications to cellular phenotypes. Bioinformatics 26, 7 (03 2010), 979–981. arXiv:https://academic.oup.com/bioinformatics/article-pdf/26/7/979/559050/btq046.pdf Google ScholarDigital Library
15. Simon Perreault and Patrick Hébert. 2007. Median filtering in constant time. IEEE transactions on image processing 16, 9 (2007), 2389–2394.Google ScholarDigital Library
16. 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.Google ScholarDigital Library
17. Fatih Porikli. 2005. Integral histogram: A fast way to extract histograms in cartesian spaces. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), Vol. 1. IEEE, 829–836.Google ScholarDigital Library
18. Jonathan Ragan-Kelley, Andrew Adams, Sylvain Paris, Marc Levoy, Saman Amarasinghe, and Frédo Durand. 2012. Decoupling algorithms from schedules for easy optimization of image processing pipelines. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–12.Google ScholarDigital Library
19. Gabriel Salvador, Juan M Chau, Jorge Quesada, and Cesar Carranza. 2018. Efficient GPU-based implementation of the median filter based on a multi-pixel-per-thread framework. In 2018 IEEE Southwest Symposium on Image Analysis and Interpretation (SSIAI). IEEE, 121–124.Google ScholarCross Ref
20. Ricardo M Sánchez and Paul A Rodríguez. 2013. Highly parallelable bidimensional median filter for modern parallel programming models. Journal of Signal Processing Systems 71, 3 (2013),221–235.Google ScholarDigital Library
21. E. Stewart. 2004. Intel Integrated Performance Primitives: How to Optimize Software Applications Using Intel IPP. Intel Press.Google Scholar
22. Deqing Sun, Stefan Roth, and Michael J Black. 2010. Secrets of optical flow estimation and their principles. In 2010 IEEE computer society conference on computer vision and pattern recognition. IEEE, 2432–2439.Google Scholar
23. JW Tukey. 1974. Nonlinear (nonsuperposable) methods for smoothing data. Proc. Cong. Rec. EASCOM’74 (1974), 673–681.Google Scholar
24. Vaibhav Vavilala. 2019. Lightpruning on Toy Story 4. In ACM SIGGRAPH 2019 Talks. 1–2.Google ScholarDigital Library
25. Frederick M Waltz. 1989. Fast implementation of ranked filters on general-purpose image processing hardware. In Automated Inspection and High-Speed Vision Architectures II, Vol. 1004. International Society for Optics and Photonics, 25–32.Google ScholarCross Ref
26. Frederick M Waltz, Ralf Hack, and Bruce G Batchelor. 1998. Fast efficient algorithms for 3×3 ranked filters using finite-state machines. In Machine Vision Systems for Inspection and Metrology VII, Vol. 3521. International Society for Optics and Photonics, 278–287.Google ScholarCross Ref
27. Ben Weiss. 2006. Fast median and bilateral filtering. In ACM SIGGRAPH 2006 Papers. 519–526.Google ScholarDigital Library
28. Pavan Yalamanchili, Umar Arshad, Zakiuddin Mohammed, Pradeep Garigipati, Peter Entschev, Brian Kloppenborg, James Malcolm, and John Melonakos. 2015. ArrayFire – A high performance software library for parallel computing with an easy-to-use API. https://github.com/arrayfire/arrayfireGoogle Scholar
29. Qingxiong Yang, Narendra Ahuja, and Kar-Han Tan. 2015. Constant time median and bilateral filtering. International Journal of Computer Vision 112, 3 (2015), 307–318.Google ScholarDigital Library
30. Jure Žbontar and Yann LeCun. 2016. Stereo matching by training a convolutional neural network to compare image patches. The journal of machine learning research 17, 1 (2016), 2287–2318.Google Scholar