“Gaussian KD-trees for fast high-dimensional filtering” by Adams, Gelfand, Dolson and Levoy

We propose a method for accelerating a broad class of non-linear filters that includes the bilateral, non-local means, and other related filters. These filters can all be expressed in a similar way: First, assign each value to be filtered a position in some vector space. Then, replace every value with a weighted linear combination of all values, with weights determined by a Gaussian function of distance between the positions. If the values are pixel colors and the positions are (x, y) coordinates, this describes a Gaussian blur. If the positions are instead (x, y, r, g, b) coordinates in a five-dimensional space-color volume, this describes a bilateral filter. If we instead set the positions to local patches of color around the associated pixel, this describes non-local means. We describe a Monte-Carlo kd-tree sampling algorithm that efficiently computes any filter that can be expressed in this way, along with a GPU implementation of this technique. We use this algorithm to implement an accelerated bilateral filter that respects full 3D color distance; accelerated non-local means on single images, volumes, and unaligned bursts of images for denoising; and a fast adaptation of non-local means to geometry. If we have n values to filter, and each is assigned a position in a d-dimensional space, then our space complexity is O(dn) and our time complexity is O(dn log n), whereas existing methods are typically either exponential in d or quadratic in n.

1. Adams, A., Gelfand, N., and Pulli, K. 2008. Viewfinder alignment. Computer Graphics Forum (Proc. Eurographics) 27, 2, 597–606.Google ScholarCross Ref
2. Amat, F., Moussavi, F., Comolli, L., Elidan, G., Downing, K., and Horowitz, M. 2008. Markov random field based automatic image alignment for electron tomography. Journal of Structural Biology (March), 260–275.Google ScholarCross Ref
3. Arya, S., Mount, D., Netanyahu, N. S., Silverman, R., and Wu, A. 1998. An optimal algorithm for approximate nearest neighbor searching. Journal of the ACM 45, 6. Google ScholarDigital Library
4. Aurich, V., and Weule, J. 1995. Non-linear gaussian filters performing edge preserving diffusion. In Mustererkennung 1995, 17. DAGM-Symposium, Springer-Verlag, London, UK, 538–545. Google ScholarDigital Library
5. Avanaki, A. N. 2006. A spatiotemporal edge-preserving denoising method for high-quality video. Signal Processing and Information Technology, 2006 IEEE International Symposium on (Aug.), 157–161.Google ScholarCross Ref
6. Bekaert, P., Sbert, M., and Willems, Y. D. 2000. Weighted importance sampling techniques for monte carlo radiosity. In Proceedings of the Eurographics Workshop on Rendering Techniques 2000, Springer-Verlag, London, UK, 35–46. Google ScholarDigital Library
7. Bennett, E. P., and McMillan, L. 2005. Video enhancement using per-pixel virtual exposures. ACM Transactions on Graphics (Proc. SIGGRAPH 05). Google ScholarDigital Library
8. Brox, T., Kleinschmidt, O., and Cremers, D. 2008. Efficient nonlocal means for denoising of textural patterns. Image Processing, IEEE Transactions on 17, 7 (July), 1083–1092. Google ScholarDigital Library
9. Buades, A., Coll, B., and Morel, J.-M. 2005. A non-local algorithm for image denoising. In Proc. CVPR 05., vol. 2, 60–65 vol. 2. Google ScholarDigital Library
10. Buades, A., Coll, B., and Morel, J.-M. 2008. Nonlocal image and movie denoising. International Journal of Computer Vision 76, 2, 123–139. Google ScholarDigital Library
11. Buck, I. 2007. Gpu computing: Programming a massively parallel processor. In CGO ’07: Proceedings of the International Symposium on Code Generation and Optimization, IEEE Computer Society, Washington, DC, USA, 17. Google ScholarDigital Library
12. Chen, J., Paris, S., and Durand, F. 2007. Real-time edge-aware image processing with the bilateral grid. ACM Transactions on Graphics (Proc. SIGGRAPH 07). Google ScholarDigital Library
13. D. Barash. 2002. A fundamental relationship between bilateral filtering, adaptive smoothing and the nonlinear diffusion equation. IEEE Transactions on Pattern Analysis and Machine Intelligence 24, 6, 844–847. Google ScholarDigital Library
14. Desbrun, M., Meyer, M., Schroder, P., and Barr, A. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. Proc. SIGGRAPH 99. Google ScholarDigital Library
15. Durand, F., and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. Proc. SIGGRAPH 02. Google ScholarDigital Library
16. Eisemann, E., and Durand, F. 2004. Flash photography enhancement via intrinsic relighting. ACM Transactions on Graphics (Proc. SIGGRAPH 04). Google ScholarDigital Library
17. Fleischman, S., Cohen-Or, D., and Silva, C. 2005. Robust moving least-squares fitting with sharp features. ACM Transactions on Graphics (Proc. SIGGRAPH 05). Google ScholarDigital Library
18. Fleishman, S., Drori, I., and Cohen-Or, D. 2003. Bilateral mesh denoising. ACM Transactions on Graphics (Proc. SIGGRAPH 03). Google ScholarDigital Library
19. Johnson, A., and Hebert, M. 1999. Using spin images for efficient object recognition in cluttered 3D scenes. PAMI 21. Google ScholarDigital Library
20. Jones, T., Durand, F., and Desbrun, M. 2003. Nonitertive, feature-preserving mesh smoothing. ACM Transactions on Graphics (Proc. SIGGRAPH 03) 24, 3. Google ScholarDigital Library
21. Kumar, N., Zhang, L., and Nayar, S. K. 2008. What is a good nearest neighbors algorithm for finding similar patches in images? Proc. ECCV 08, 364–378. Google ScholarDigital Library
22. Paris, S., and Durand, F. 2006. A fast approximation of the bilateral filter using a signal processing approach. In Proc. ECCV 06. Google ScholarDigital Library
23. Paris, S., and Durand, F. 2009. A fast approximation of the bilateral filter using a signal processing approach. International Journal of Computer Vision 81, 24–52. Google ScholarDigital Library
24. Park, S. W., Linsen, L., Kreylos, O., Owens, J. D., and Hamann, B. 2006. Discrete sibson interpolation. IEEE Transactions on Visualization and Computer Graphics 12, 2 (Mar./Apr.), 243–253. Google ScholarDigital Library
25. Petschnigg, G., Szeliski, R., Agrawala, M., Cohen, M., Hoppe, H., and Toyama, K. 2004. Digital photography with flash and no-flash image pairs. ACM Transactions on Graphics (Proc. SIGGRAPH 04). Google ScholarDigital Library
26. Sheffer, A., Praun, E., and Rose, K. 2006. Mesh Parameterization Methods and Their Applications. Now Publishers.Google Scholar
27. Smith, S., and Brady, J. M. 1997. Susan:a new approach to low level image processing. International Journal of Computer Vision 23, 45–78. Google ScholarDigital Library
28. Sorkine, O., Cohen-Or, D., Lipman, Y., Rssl, C., Peter Seidel, H., and Alexa, M. 2004. Laplacian surface editing. Proc. SGP. Google ScholarDigital Library
29. Taubin, G. 1995. A signal processing approach to fair surface design. Proc. SIGGRAPH 95. Google ScholarDigital Library
30. Telleen, J., Sullivan, A., Yee, J., Wang, O., Gunawardane, P., Collins, I., and Davis, J. 2007. Synthetic shutter speed imaging. Computer Graphics Forum (Proc. Eurographics) 26, 3, 591–598.Google ScholarCross Ref
31. Tomasi, C., and Manduchi, R. 1998. Bilateral filtering for gray and color images. Proc. ICCV 98 0, 839. Google ScholarDigital Library
32. Weiss, B. 2006. Fast median and bilateral filtering. ACM Transactions on Graphics (Proc. SIGGRAPH 06). Google ScholarDigital Library
33. Yang, C., Duraiswami, R., Gumerov, N. A., and Davis, L. 2003. Improved fast gauss transform and efficient kernel density estimation. Proc. ICCV 03, 664–671 vol.1. Google ScholarDigital Library
34. Yoshizawa, S., Belyaev, A., and Seidel, H.-P. 2006. Smoothing by example: mesh denoising by averaging with similarity-based weights. IEEE Shape Modeling International. Google ScholarDigital Library
35. Zhou, K., Hou, Q., Wang, R., and Guo, B. 2008. Real-time kd-tree construction on graphics hardware. ACM Transactions on Graphics (Proc. SIGGRAPH Asia 08). Google ScholarDigital Library