Fast High-Dimensional Filtering Using the Permutohedral Lattice
We describe a
method of quickly evaluating the type of Gauss transform used in
bilateral filters, joint bilateral filters, non-local means, and
related tasks. Other recent fast methods for doing this include
Grid, and the Gaussian
KD-Tree. The diagram above shows, for a wide range of filters
sizes and dimensionalities, which method of the three is the
fastest, and by how much it is faster than the second fastest
method. The permutohedral lattice described in our paper is the
best choice for a wide range of dimensionalities and filter sizes.
Many useful algorithms for processing images and geometry fall under
the general framework of high-dimensional Gaussian filtering. This
family of algorithms includes bilateral filtering and non-local
means. We propose a new way to perform such filters using the
permutohedral lattice, which tessellates high-dimensional space with
uniform simplices. Our algorithm is the first implementation of a
high-dimensional Gaussian filter that is both linear in input size and
polynomial in dimensionality. Furthermore it is parameter-free, apart
from the filter size, and achieves a consistently high accuracy
relative to ground truth (> 45 dB). We use this to demonstrate a
number of interactive-rate applications of filters in as high as eight
Tech Report: permutohedral_techreport.pdf
This supporting tech report is referenced in the paper above, and proves a variety of useful properties of the permutohedral lattice.
Here we provide a single header file implementation of the method (permutohedral.h), along with enough support code to perform bilateral filters of pngs and jpgs under linux or cygwin (assuming you have libpng and libjpg installed). It's pretty straight-forward to adapt this for joint-bilateral filters. Non-local means is a little more complex, as it involves reducing the dimensionality of the space of local patches using PCA as a preprocess (see the paper for details). Finally, joint-bilateral upsampling is possible with this method, but would require modifying our code a little, as currently it assumes you sample the high-dimensional space at the same locations as you splat. If this would be useful to you, send us an email and we'll post code that does that.
This CPU implementation is also included in ImageStack, along with operations that use it for bilateral filtering, joint bilateral filtering, and non-local means.
A CUDA implementation of the lattice tuned for a GTX460 is available here, as source and linux binary. This program uses it for color bilateral filtering.
An older CUDA implementation of the lattice is available here.