Gaussian KD-Trees for Fast High-Dimensional Filtering

被引:160
作者
Adams, Andrew [1 ]
Gelfand, Natasha [2 ]
Dolson, Jennifer [1 ]
Levoy, Marc [1 ]
机构
[1] Stanford Univ, Stanford, CA 94305 USA
[2] Nokia Res, Espoo, Finland
来源
ACM TRANSACTIONS ON GRAPHICS | 2009年 / 28卷 / 03期
关键词
bilateral filter; non-local means; geometry filtering; denoising; IMAGE;
D O I
10.1145/1531326.1531327
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页数:12
相关论文
共 35 条
[11]   A non-local algorithm for image denoising [J].
Buades, A ;
Coll, B ;
Morel, JM .
2005 IEEE COMPUTER SOCIETY CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION, VOL 2, PROCEEDINGS, 2005, :60-65
[12]   Nonlocal image and movie denoising [J].
Buades, Antoni ;
Coll, Bartomeu ;
Morel, Jean-Michel .
INTERNATIONAL JOURNAL OF COMPUTER VISION, 2008, 76 (02) :123-139
[13]  
Buck I, 2007, INT SYM CODE GENER, P17
[14]  
DESBRUN M, 1999, P SIGGRAPH 99
[15]  
DURAND F, 2002, P SIGGRAPH 02
[16]  
EISEMANN E, 2004, ACM T GRAPHICS P SIG
[17]  
FLEISCHMAN S, 2005, ACM T GRAPHICS P SIG
[18]  
FLEISHMAN S, 2003, ACM T GRAPHICS P SIG
[19]  
JOHNSON A, 1999, 21 PAMI
[20]  
JONES T, 2003, ACM T GRAPHICS P SIG, V24, P3