Fast High-Dimensional Filtering Using the Permutohedral Lattice

Eurographics 2010
Runner up for Best Paper

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 the Bilateral 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.

Abstract

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 dimensions.

Paper: permutohedral.pdf

Video: permutohedral.mov

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.

Implementation: permutohedral.zip

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.