“Parallel recursive filtering of infinite input extensions”
Conference:
Type(s):
Title:
- Parallel recursive filtering of infinite input extensions
Session/Category Title: Filtering Images
Presenter(s)/Author(s):
Abstract:
Filters with slowly decaying impulse responses have many uses in computer graphics. Recursive filters are often the fastest option for such cases. In this paper, we derive closed-form formulas for computing the exact initial feedbacks needed for recursive filtering infinite input extensions. We provide formulas for the constant-padding (e.g. clamp-to-edge), periodic (repeat) and even-periodic (mirror or reflect) extensions. These formulas were designed for easy integration into modern block-parallel recursive filtering algorithms. Our new modified algorithms are state-of-the-art, filtering images faster even than previous methods that ignore boundary conditions.
References:
1. Appleton, B. and Talbot, H. 2003. Efficient and consistent recursive filtering of images with reflective extension. In Scale Space’03, Springer-Verlag, LNCS 2695, 699–712.
2. Blelloch, G. E. 1990. Prefix sums and their applications. Technical Report CMU-CS-90-190, Carnegie Mellon University.
3. Blu, T., Thévenaz, P., and Unser, M. 2001. MOMS: Maximalorder interpolation of minimal support. IEEE Transactions on Image Processing, 10(7):1069–1080.
4. Catmull, E. and Rom, R. 1974. A class of local interpolating splines. In Computer Aided Geometric Design, 317–326.
5. Chaurasia, G., Ragan-Kelley, J., Paris, S., Drettakis, G., and Durand, F. 2015. Compiling high performance recursive filters. In High Performance Graphics, 85–94.
6. Condat, L., Blu, T., and Unser, M. 2005. Beyond interpolation: optimal reconstruction by quasi-interpolation. In IEEE International Conference on Image Processing, volume 1, 33–36.
7. Condat, L. and Möller, T. 2011. Quantitative error analysis for the reconstruction of derivatives. IEEE Transactions on Image Processing, 59(6):2965–2969.
8. cuFFT library. 2007. URL http://developer.nvidia.com/cuda-toolkit. NVIDIA Corporation.
9. Dotsenko, Y., Govindaraju, N. K., Sloan, P.-P., Boyd, C., and Manferdelli, J. 2008. Fast scan algorithms on graphics processors. In Proceedings of the International Conference on Supercomputing, 205–213.
10. Duchon, C. E. 1979. Lanczos filtering in one and two dimensions. Journal of Applied Meteorology, 18(8):1016–1022. Cross Ref
11. Gastal, E. S. L. and Oliveira, M. M. 2011. Domain transform for edge-aware image and video processing. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2011), 30(4):69.
12. Gastal, E. S. L. and Oliveira, M. M. 2015. High-order recursive filtering of non-uniformly sampled signals for image and video processing. Computer Graphics Forum, 34(2):81–93.
13. Govindaraju, N. K., Lloyd, B., Dotsenko, Y., Smith, B., and Manferdelli, J. 2008. High performance discrete fourier transforms on graphics processors. In Proceedings of the IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis, IEEE.
14. Hummel, R. 1983. Sampling for spline reconstruction. SIAM Journal on Applied Mathematics, 43(2):278–288. Cross Ref
15. Iverson, K. E. 1962. A Programming Language. Wiley.
16. Kajiya, J. and Ullner, M. 1981. Filtering high quality text for display on raster scan devices. Computer Graphics (Proceedings of ACM SIGGRAPH 1981), 15(3):7–15.
17. Kooge, P. M. and Stone, H. S. 1973. A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Transactions on Computers, C-22(8):786–793.
18. Malcolm, M. A. and Palmer, J. 1974. A fast method for solving a class of tridiagonal linear systems. Communications of the ACM, 17(1):14–17.
19. Martucci, S. A. 1994. Symmetric convolution and the discrete sine and cosine transforms. IEEE Transactions on Signal Processing, 42(5):1038–1051.
20. Maximo, A. 2015. Efficient finite impulse response filters in massively-parallel recursive systems. Journal of Real-Time Image Processing, 1–9.
21. McCool, M. D. 1995. Analytic antialiasing with prism splines. In Proceedings of ACM SIGGRAPH 1995, 429–436.
22. Merrill, D. and Grimshaw, A. 2009. Parallel scan for stream architectures. Technical Report CS2009-14, University of Virginia.
23. Meyer, C. D. 2000. Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia, PA, USA.
24. Mitchell, D. P. and Netravali, A. N. 1988. Reconstruction filters in computer graphics. Computer Graphics (Proceedings of ACM SIGGRAPH 1988), 22(4):221–228.
25. Nehab, D. and Hoppe, H. 2014. A fresh look at generalized sampling. Foundations and Trends in Computer Graphics and Vision, 8(1):1–84.
26. Nehab, D., Maximo, A., Lima, R. S., and Hoppe, H. 2011. GPU-efficient recursive filtering and summed-area tables. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH Asia 2011), 30(6):176.
27. Oppenheim, A. V. and Schafer, R. W. 2010. Discrete-Time Signal Processing. Prentice Hall, 3rd edition.
28. Podlozhnyuk, V. 2007. Image convolution with CUDA. NVIDIA whitepaper.
29. Sacht, L. and Nehab, D. 2015. Optimized quasi-interpolators for image reconstruction. IEEE Transactions on Image Processing, 24(12):5249–5259. Cross Ref
30. Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Proceedings of Graphics Hardware, 97–106.
31. Stone, H. S. 1971. Parallel processing with the perfect shuffle. IEEE Transactions on Computers, C-20(2):153–161.
32. Stone, H. S. 1973. An efficient parallel algorithm for the solution of a tridiagonal linear system of equations. Journal of the ACM, 20(1):27–38.
33. Sun, X., Mei, X., Jiao, S., Zhou, M., Liu, Z., and Wang, H. 2014. Real-time local stereo via edge-aware disparity propagation. Pattern Recognition Letters, 49:201–206.
34. Sung, W. and Mitra, S. 1986. Efficient multi-processor implementation of recursive digital filters. In IEEE International Conference on Acoustics, Speech and Signal Processing, 257–260.
35. Sung, W. and Mitra, S. 1992. Multiprocessor implementation of digital filtering algorithms using a parallel block processing method. IEEE Transactions on Parallel and Distributed Systems, 3(1):110–120.
36. Triggs, B. and Sdika, M. 2006. Boundary conditions for Young-van Vliet recursive filtering. IEEE Transactions on Signal Processing, 54(5):2365–2367. Cross Ref
37. Unser, M. and Aldroubi, A. 1994. A general sampling theory for nonideal acquisition devices. IEEE Transactions on Signal Processing, 42(11):2915–2925.
38. Unser, M., Aldroubi, A., and Eden, M. 1991. Fast B-spline transforms for continuous image representation and interpolation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(3):277–285.
39. Unser, M., Aldroubi, A., and Eden, M. 1993. The L2-polynomial spline pyramid. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(4):364–379.
40. Unser, M., Aldroubi, A., and Eden, M. 1995. Enlargement or reduction of digital images with minimum loss of information. IEEE Transactions on Image Processing, 4(3):247–258.
41. Unser, M., Thénevaz, P., and Yaroslavsky, L. 1995. Convolution-based interpolation for fast, high-quality rotation of images. IEEE Transactions on Image Processing, 4(10):1371–1381.
42. van Vliet, L. J., Young, I. T., and Verbeek, P. W. 1998. Recursive Gaussian derivative filters. In Proceedings of the 14th International Conference on Pattern Recognition, 509–514 (v. 1).
43. Weickert, J., ter Haar Romeny, B. M., and Viergever, M. A. 1998. Efficient and reliable schemes for nonlinear diffusion filtering. IEEE Transactions on Image Processing, 7(3):398–410.
44. Zhou, M., Liu, Z., Hong, T., Wang, X., Wang, H., and Sun, X. 2015. Efficient O(1) edge-aware filter. In IEEE International Conference on Image Processing, 1295–1299.
