Gaussian KD-trees for fast high-dimensional filtering

ABSTRACT

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.

REFERENCES

• 1: Adams, A., Gelfand, N., and Pulli, K. 2008. Viewfinder alignment. Computer Graphics Forum (Proc. Eurographics) 27, 2, 597--606.
• 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.
• 3: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 4: Volker Aurich , Jörg Weule, Non-Linear Gaussian Filters Performing Edge Preserving Diffusion, Mustererkennung 1995, 17. DAGM-Symposium, p.538-545, September 13-15, 1995
• 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.
• 6: Philippe Bekaert , Mateu Sbert , Yves D. Willems, Weighted Importance Sampling Techniques for Monte Carlo Radiosity, Proceedings of the Eurographics Workshop on Rendering Techniques 2000, p.35-46, June 26-28, 2000
• 7: Eric P. Bennett , Leonard McMillan, Video enhancement using per-pixel virtual exposures, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 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.
• 9: Antoni Buades , Bartomeu Coll , Jean-Michel Morel, A Non-Local Algorithm for Image Denoising, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.60-65, June 20-26, 2005 [doi>10.1109/CVPR.2005.38]
• 10: Antoni Buades , Bartomeu Coll , Jean-Michel Morel, Nonlocal Image and Movie Denoising, International Journal of Computer Vision, v.76 n.2, p.123-139, February 2008 [doi>10.1007/s11263-007-0052-1]
• 11: Ian Buck, GPU Computing: Programming a Massively Parallel Processor, Proceedings of the International Symposium on Code Generation and Optimization, p.17, March 11-14, 2007 [doi>10.1109/CGO.2007.13]
• 12: Jiawen Chen , Sylvain Paris , Frédo Durand, Real-time edge-aware image processing with the bilateral grid, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 13: Danny Barash, A Fundamental Relationship between Bilateral Filtering, Adaptive Smoothing, and the Nonlinear Diffusion Equation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.6, p.844-847, June 2002 [doi>10.1109/TPAMI.2002.1008390]
• 14: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 15: Frédo Durand , Julie Dorsey, Fast bilateral filtering for the display of high-dynamic-range images, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 16: Elmar Eisemann , Frédo Durand, Flash photography enhancement via intrinsic relighting, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 17: Shachar Fleishman , Daniel Cohen-Or , Cláudio T. Silva, Robust moving least-squares fitting with sharp features, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 18: Shachar Fleishman , Iddo Drori , Daniel Cohen-Or, Bilateral mesh denoising, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 19: Andrew E. Johnson , Martial Hebert, Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.5, p.433-449, May 1999 [doi>10.1109/34.765655]
• 20: Thouis R. Jones , Frédo Durand , Mathieu Desbrun, Non-iterative, feature-preserving mesh smoothing, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 21: Neeraj Kumar , Li Zhang , Shree Nayar, What Is a Good Nearest Neighbors Algorithm for Finding Similar Patches in Images?, Proceedings of the 10th European Conference on Computer Vision: Part II, October 12-18, 2008, Marseille, France [doi>10.1007/978-3-540-88688-4_27]
• 22: Paris, S., and Durand, F. 2006. A fast approximation of the bilateral filter using a signal processing approach. In Proc. ECCV 06.
• 23: Sylvain Paris , Frédo Durand, A Fast Approximation of the Bilateral Filter Using a Signal Processing Approach, International Journal of Computer Vision, v.81 n.1, p.24-52, January 2009 [doi>10.1007/s11263-007-0110-8]
• 24: Sung W. Park , Lars Linsen , Oliver Kreylos , John D. Owens , Bernd Hamann, Discrete Sibson Interpolation, IEEE Transactions on Visualization and Computer Graphics, v.12 n.2, p.243-253, March 2006 [doi>10.1109/TVCG.2006.27]
• 25: Georg Petschnigg , Richard Szeliski , Maneesh Agrawala , Michael Cohen , Hugues Hoppe , Kentaro Toyama, Digital photography with flash and no-flash image pairs, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 26: Sheffer, A., Praun, E., and Rose, K. 2006. Mesh Parameterization Methods and Their Applications. Now Publishers.
• 27: Stephen M. Smith , J. Michael Brady, SUSAN—A New Approach to Low Level Image Processing, International Journal of Computer Vision, v.23 n.1, p.45-78, May 1997 [doi>10.1023/A:1007963824710]
• 28: O. Sorkine , D. Cohen-Or , Y. Lipman , M. Alexa , C. Rössl , H.-P. Seidel, Laplacian surface editing, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057456]
• 29: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 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.
• 31: C. Tomasi , R. Manduchi, Bilateral Filtering for Gray and Color Images, Proceedings of the Sixth International Conference on Computer Vision, p.839, January 04-07, 1998
• 32: Ben Weiss, Fast median and bilateral filtering, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 33: Changjiang Yang , Ramani Duraiswami , Nail A. Gumerov , Larry Davis, Improved Fast Gauss Transform and Efficient Kernel Density Estimation, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.464, October 13-16, 2003
• 34: Shin Yoshizawa , Alexander Belyaev , Hans-Peter Seidel, Smoothing by Example: Mesh Denoising by Averaging with Similarity-Based Weights, Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, p.9, June 14-16, 2006 [doi>10.1109/SMI.2006.38]
• 35: Kun Zhou , Qiming Hou , Rui Wang , Baining Guo, Real-time KD-tree construction on graphics hardware, ACM SIGGRAPH Asia 2008 papers, December 10-13, 2008, Singapore

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement
          Subjects: Filtering

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Keywords:
bilateral filter, denoising, geometry filtering, non-local means