“Adaptive manifolds for real-time high-dimensional filtering” by Gastal and Oliveira

We present a technique for performing high-dimensional filtering of images and videos in real time. Our approach produces high-quality results and accelerates filtering by computing the filter’s response at a reduced set of sampling points, and using these for interpolation at all N input pixels. We show that for a proper choice of these sampling points, the total cost of the filtering operation is linear both in N and in the dimension d of the space in which the filter operates. As such, ours is the first high-dimensional filter with such a complexity. We present formal derivations for the equations that define our filter, as well as for an algorithm to compute the sampling points. This provides a sound theoretical justification for our method and for its properties. The resulting filter is quite flexible, being capable of producing responses that approximate either standard Gaussian, bilateral, or non-local-means filters. Such flexibility also allows us to demonstrate the first hybrid Euclidean-geodesic filter that runs in a single pass. Our filter is faster and requires less memory than previous approaches, being able to process a 10-Megapixel full-color image at 50 fps on modern GPUs. We illustrate the effectiveness of our approach by performing a variety of tasks ranging from edge-aware color filtering in 5-D, noise reduction (using up to 147 dimensions), single-pass hybrid Euclidean-geodesic filtering, and detail enhancement, among others.

1. Adams, A., Gelfand, N., Dolson, J., and Levoy, M. 2009. Gaussian kd-trees for fast high-dimensional filtering. In SIGGRAPH. Google ScholarDigital Library
2. Adams, A., Baek, J., and Davis, M. A. 2010. Fast high-dimensional filtering using the permutohedral lattice. CGF 29, 2, 753–762.Google ScholarCross Ref
3. Adams, A. B. 2011. High-dimensional gaussian filtering for computational photography. PhD thesis, Stanford University.Google Scholar
4. Arasaratnam, I., Haykin, S., and Elliott, R. 2007. Discrete-time nonlinear filtering algorithms using gauss–hermite quadrature. Proc. of the IEEE 95, 5, 953–977.Google ScholarCross Ref
5. Aurich, V., and Weule, J. 1995. Non-linear gaussian filters performing edge preserving diffusion. In Mustererkennung 1995, 17. DAGM-Symposium, 538–545. Google ScholarDigital Library
6. Bae, S., Paris, S., and Durand, F. 2006. Two-scale tone management for photographic look. ACM TOG 25, 3, 637–645. Google ScholarDigital Library
7. Barash, D. 2002. A fundamental relationship between bilateral filtering, adaptive smoothing, and the nonlinear diffusion equation. IEEE TPAMI 24, 844–847. Google ScholarDigital Library
8. Bauszat, P., Eisemann, M., and Magnor, M. 2011. Guided image filtering for interactive high-quality global illumination. Computer Graphics Forum 30, 4, 1361–1368. Google ScholarDigital Library
9. Bennett, E. P., and McMillan, L. 2005. Video enhancement using per-pixel virtual exposures. ACM TOG 24, 845–852. Google ScholarDigital Library
10. Bhavsar, A. V., and Rajagopalan, A. N. 2010. Depth estimation and inpainting with an unconstrained camera. In Proceedings of the British Machine Vision Conference, 84.1–12.Google Scholar
11. Buades, A., Coll, B., and Morel, J. 2005. A non-local algorithm for image denoising. In IEEE CVPR, vol. 2, 60–65. Google ScholarDigital Library
12. Chen, J., Paris, S., and Durand, F. 2007. Real-time edge-aware image processing with the bilateral grid. ACM TOG 26, 3, 103. Google ScholarDigital Library
13. Criminisi, A., Sharp, T., Rother, C., and P’erez, P. 2010. Geodesic image and video editing. ACM TOG 29, 5, 134. Google ScholarDigital Library
14. Dabov, K., Foi, A., Katkovnik, V., and Egiazarian, K. 2007. Image denoising by sparse 3-d transform-domain collaborative filtering. IEEE TIP 16, 8, 2080–2095. Google ScholarDigital Library
15. Deriche, R., 1993. Recursively implementating the gaussian and its derivatives.Google Scholar
16. Durand, F., and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. In SIGGRAPH ’02, 257–266. Google ScholarDigital Library
17. Eisemann, E., and Durand, F. 2004. Flash photography enhancement via intrinsic relighting. In ACM TOG, vol. 23, ACM, 673–678. Google ScholarDigital Library
18. Farbman, Z., Fattal, R., Lischinski, D., and Szeliski, R. 2008. Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM TOG 27, 3, 67. Google ScholarDigital Library
19. Fattal, R., Agrawala, M., and Rusinkiewicz, S. 2007. Multiscale shape and detail enhancement from multi-light image collections. ACM TOG 26, 51:1–51:9. Google ScholarDigital Library
20. Fattal, R. 2009. Edge-avoiding wavelets and their applications. ACM TOG 28, 3, 22. Google ScholarDigital Library
21. Gastal, E. S. L., and Oliveira, M. M. 2010. Shared sampling for real-time alpha matting. CGF 29, 2, 575–584.Google ScholarCross Ref
22. Gastal, E. S. L., and Oliveira, M. M. 2011. Domain transform for edge-aware image and video processing. ACM TOG 30, 4, 69:1–69:12. Proceedings of SIGGRAPH 2011. Google ScholarDigital Library
23. He, K., Sun, J., and Tang, X. 2010. Guided image filtering. In ECCV. Springer Berlin/Heidelberg, 1–14. Google ScholarDigital Library
24. He, K., Rhemann, C., Rother, C., Tang, X., and Sun, J. 2011. A global sampling method for alpha matting. In CVPR, IEEE, 2049–2056. Google ScholarDigital Library
25. Heckbert, P. S. 1986. Filtering by repeated integration. SIGGRAPH Comput. Graph. 20, 4, 315–321. Google ScholarDigital Library
26. Knutsson, H., and Westin, C.-F. 1993. Normalized and differential convolution: Methods for interpolation and filtering of incomplete and uncertain data. In CVPR, 515–523.Google Scholar
27. Kopf, J., Cohen, M. F., Lischinski, D., and Uyttendaele, M. 2007. Joint bilateral upsampling. ACM TOG 26, 96:1–96:5. Google ScholarDigital Library
28. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM TOG 23, 689–694. Google ScholarDigital Library
29. Lischinski, D., Farbman, Z., Uyttendaele, M., and Szeliski, R. 2006. Interactive local adjustment of tonal values. ACM TOG 25, 3, 646–653. Google ScholarDigital Library
30. Nehab, D., Maximo, A., Lima, R. S., and Hoppe, H. 2011. Gpu-efficient recursive filtering and summed-area tables. ACM TOG 30, 176:1–176:12. Google ScholarDigital Library
31. NIST, 2011. National Institute of Standards and Technology: Digital library of mathematical functions, August.Google Scholar
32. Paris, S., and Durand, F. 2009. A fast approximation of the bilateral filter using a signal processing approach. IJCV 81, 1, 24–52. Google ScholarDigital Library
33. Petschnigg, G., Szeliski, R., Agrawala, M., Cohen, M., Hoppe, H., and Toyama, K. 2004. Digital photography with flash and no-flash image pairs. ACM TOG 23, 3, 664–672. Google ScholarDigital Library
34. Pham, T., and van Vliet, L. 2005. Separable bilateral filtering for fast video preprocessing. IEEE Intl. Conf. on Multimedia and Expo 0, 4 pp.Google ScholarCross Ref
35. Porikli, F. 2008. Constant time O(1) bilateral filtering. In CVPR, 1–8.Google Scholar
36. Richardt, C., Orr, D., Davies, I., Criminisi, A., and Dodgson, N. 2010. Real-time spatiotemporal stereo matching using the dual-cross-bilateral grid. In ECCV. Springer Berlin/Heidelberg, 510–523. Google ScholarDigital Library
37. Smith, S. M., and Brady, J. M. 1997. Susan — a new approach to low level image processing. International journal of computer vision 23, 1, 45–78. Google ScholarDigital Library
38. Sochen, N., Kimmel, R., and Bruckstein, A. 2001. Diffusions and confusions in signal and image processing. Journal of Mathematical Imaging and Vision 14, 3, 195–209. Google ScholarDigital Library
39. Tasdizen, T. 2008. Principal components for non-local means image denoising. In ICIP, IEEE, 1728–1731.Google Scholar
40. Tomasi, C., and Manduchi, R. 1998. Bilateral filtering for gray and color images. In ICCV, 839–846. Google ScholarDigital Library
41. Weber, M., Milch, M., Myszkowski, K., Dmitriev, K., Rokita, P., and Seidel, H. 2004. Spatio-temporal photon density estimation using bilateral filtering. In CGI, IEEE, 120–127. Google ScholarDigital Library
42. Winnemöller, H., Olsen, S. C., and Gooch, B. 2006. Real-time video abstraction. ACM TOG 25, 3, 1226. Google ScholarDigital Library
43. Yang, C., Duraiswami, R., Gumerov, N., and Davis, L. 2003. Improved fast gauss transform and efficient kernel density estimation. In ICCV, IEEE, 664–671. Google ScholarDigital Library
44. Yang, Q., Tan, K. H., and Ahuja, N. 2009. Real-time O(1) bilateral filtering. In CVPR, 557–564.Google Scholar
45. Yang, L., Sander, P. V., Lawrence, J., and Hoppe, H. 2011. Antialiasing recovery. ACM TOG 30, 22:1–22:9. Google ScholarDigital Library
46. Zhuo, S., Zhang, X., Miao, X., and Sim, T. 2010. Enhancing low light images using near infrared flash images. In IEEE ICIP, IEEE, 2537–2540.Google Scholar