Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1576246.1531327 | ACM Trans. Graph. |
Keywords | Field | DocType |
kd tree,vector space,non local means,space complexity,bilateral filtering,time complexity,monte carlo | Linear combination,Mathematical optimization,Non-local means,Gaussian blur,Filter (signal processing),Gaussian,Bilateral filter,Time complexity,Gaussian function,Mathematics | Journal |
Volume | Issue | ISSN |
28 | 3 | 0730-0301 |
Citations | PageRank | References |
100 | 4.21 | 32 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Adams | 1 | 936 | 53.55 |
| Natasha Gelfand | 2 | 1236 | 67.99 |
| Jennifer Dolson | 3 | 271 | 14.03 |
| Marc Levoy | 4 | 10273 | 1073.33 |