%0 Conference Paper %1 adams_gaussian_2009 %A Adams, Andrew %A Gelfand, Natasha %A Dolson, Jennifer %A Levoy, Marc %B SIGGRAPH %D 2009 %K geometry\_filtering siggraph kd\_tree gaussian\_filter filtering data\_structure denoising importance\_sampling 2009 non\_local\_means bilateral\_filter cv %T Gaussian KD-Trees for Fast High-Dimensional Filtering %X 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.

@inproceedings{adams_gaussian_2009, 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.}, added-at = {2009-09-29T19:54:18.000+0200}, author = {Adams, Andrew and Gelfand, Natasha and Dolson, Jennifer and Levoy, Marc}, biburl = {https://www.bibsonomy.org/bibtex/295510e2c895ebcc356bbf8883064ec19/dudemeister}, booktitle = {{SIGGRAPH}}, interhash = {e58a4cc47b4e5a7b634c92fe862a4ba4}, intrahash = {95510e2c895ebcc356bbf8883064ec19}, keywords = {geometry\_filtering siggraph kd\_tree gaussian\_filter filtering data\_structure denoising importance\_sampling 2009 non\_local\_means bilateral\_filter cv}, timestamp = {2009-09-29T19:54:18.000+0200}, title = {Gaussian {KD-Trees} for Fast {High-Dimensional} Filtering}, year = 2009 }