Eduardo S. L. Gastal
Manuel M. Oliveira
Abstract
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.
Supplemental Material
Available for Download
Supplemental material.
- Adams, A., Gelfand, N., Dolson, J., and Levoy, M. 2009. Gaussian kd-trees for fast high-dimensional filtering. In SIGGRAPH. Google Scholar
Digital Library
- 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
- Adams, A. B. 2011. High-dimensional gaussian filtering for computational photography. PhD thesis, Stanford University.Google Scholar
- 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
- 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
- Bae, S., Paris, S., and Durand, F. 2006. Two-scale tone management for photographic look. ACM TOG 25, 3, 637--645. Google ScholarDigital Library
- Barash, D. 2002. A fundamental relationship between bilateral filtering, adaptive smoothing, and the nonlinear diffusion equation. IEEE TPAMI 24, 844--847. Google ScholarDigital Library
- 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
- Bennett, E. P., and McMillan, L. 2005. Video enhancement using per-pixel virtual exposures. ACM TOG 24, 845--852. Google ScholarDigital Library
- 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
- 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
- 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
- Criminisi, A., Sharp, T., Rother, C., and P'erez, P. 2010. Geodesic image and video editing. ACM TOG 29, 5, 134. Google ScholarDigital Library
- 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
- Deriche, R., 1993. Recursively implementating the gaussian and its derivatives.Google Scholar
- 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
- Eisemann, E., and Durand, F. 2004. Flash photography enhancement via intrinsic relighting. In ACM TOG, vol. 23, ACM, 673--678. Google ScholarDigital Library
- 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
- 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
- Fattal, R. 2009. Edge-avoiding wavelets and their applications. ACM TOG 28, 3, 22. Google ScholarDigital Library
- Gastal, E. S. L., and Oliveira, M. M. 2010. Shared sampling for real-time alpha matting. CGF 29, 2, 575--584.Google ScholarCross Ref
- 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
- He, K., Sun, J., and Tang, X. 2010. Guided image filtering. In ECCV. Springer Berlin/Heidelberg, 1--14. Google ScholarDigital Library
- 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
- Heckbert, P. S. 1986. Filtering by repeated integration. SIGGRAPH Comput. Graph. 20, 4, 315--321. Google ScholarDigital Library
- 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
- Kopf, J., Cohen, M. F., Lischinski, D., and Uyttendaele, M. 2007. Joint bilateral upsampling. ACM TOG 26, 96:1--96:5. Google ScholarDigital Library
- Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM TOG 23, 689--694. Google ScholarDigital Library
- 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
- 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
- NIST, 2011. National Institute of Standards and Technology: Digital library of mathematical functions, August.Google Scholar
- 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
- 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
- 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
- Porikli, F. 2008. Constant time O(1) bilateral filtering. In CVPR, 1--8.Google Scholar
- 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
- 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
- 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
- Tasdizen, T. 2008. Principal components for non-local means image denoising. In ICIP, IEEE, 1728--1731.Google Scholar
- Tomasi, C., and Manduchi, R. 1998. Bilateral filtering for gray and color images. In ICCV, 839--846. Google ScholarDigital Library
- 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
- Winnemöller, H., Olsen, S. C., and Gooch, B. 2006. Real-time video abstraction. ACM TOG 25, 3, 1226. Google ScholarDigital Library
- 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
- Yang, Q., Tan, K. H., and Ahuja, N. 2009. Real-time O(1) bilateral filtering. In CVPR, 557--564.Google Scholar
- Yang, L., Sander, P. V., Lawrence, J., and Hoppe, H. 2011. Antialiasing recovery. ACM TOG 30, 22:1--22:9. Google ScholarDigital Library
- 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
Index Terms
- Adaptive manifolds for real-time high-dimensional filtering
Recommendations
Unscented Kalman Filtering on Riemannian Manifolds
In recent years there has been a growing interest in problems, where either the observed data or hidden state variables are confined to a known Riemannian manifold. In sequential data analysis this interest has also been growing, but rather crude ...
A fast efficient restoration algorithm for high-noise image filtering with adaptive approach
The video signal is easily interfered by noise over the wireless system. The well-known ''median filter'' and its modified methods could completely remove the impulse noise when the ratio of noise/image is low. However, if the noise ratio becomes high, ...
Comments