Gaussian KD-Trees for Fast High-Dimensional Filtering

Andrew Adams Natasha Gelfand Jennifer Dolson Marc Levoy


We use a Monte-Carlo sampled kd-tree we call the Gaussian kd-tree for various filtering tasks. Our method applies to bilateral filtering of image (left), non-local means of bursts of images (middle), and denoising geometry (right).


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.


Adobe Acrobat PDF (8.4 MB)


H.264 (61.3 MB)

Supplemental Material

Zip (350 MB)


Here is the GPU implementation of the paper, which runs on linux with NVIDIA's cuda installed. There's a readme.txt inside the package to get you started: Linux Binary and Source

Here is the CPU implementation of the paper, including example code for computing bilateral filters: Cygwin Binary and Cross-Platform Source.

The CPU implementation is also included in ImageStack, including operations that use it for bilateral filtering, joint bilateral filtering, and non-local means.