Constant-Time Filtering Using Shiftable Kernels
Constant-Time Filtering Using Shiftable Kernels
复制标题
DOI：
10.1109/lsp.2011.2167967
复制
发表时间：
2011-11-01
影响因子：
3.9
通讯作者：
Chaudhury, Kunal Narayan
中科院分区：
文献类型：
--
作者：
Chaudhury, Kunal Narayan
最近在[1]中证明了非线性双边滤波器[2]可以使用恒定时间或O（1）算法有效地实现。该算法的核心思想是使用三角函数近似双边滤波器的高斯范围核。在这封信中，我们解释了如何在[1]中的想法可以扩展到其他几个线性和非线性滤波器[2]-[4]。虽然这些过滤器中的一些近年来受到了很多关注，但它们被认为是计算密集型的。为了扩展[1]中的思想，我们确定了三角函数的一个中心属性，称为移位性，它允许我们利用滤波操作中固有的冗余。特别是，使用可移位内核，我们展示了如何某些复杂的过滤可以减少到简单的计算移动和堆栈的图像。通过输入图像的基本逐点变换获得堆栈中的每个图像。这有双重优势。首先，我们可以使用快速递归算法来计算移动和[5]，[6]，其次，我们可以使用并行计算来进一步加速计算。我们还展示了如何移位内核也可以用来近似（nonlinearshiftable）高斯内核，这是无处不在的图像滤波。
It was recently demonstrated in [1] that the nonlinear bilateral filter [2] can be efficiently implemented using a constant-time or O(1) algorithm. At the heart of this algorithm was the idea of approximating the Gaussian range kernel of the bilateral filter using trigonometric functions. In this letter, we explain how the idea in [1] can be extended to few other linear and nonlinear filters [2]-[4]. While some of these filters have received a lot of attention in recent years, they are known to be computationally intensive. To extend the idea in [1], we identify a central property of trigonometric functions, called shiftability, that allows us to exploit the redundancy inherent in the filtering operations. In particular, using shiftable kernels, we show how certain complex filtering can be reduced to simply that of computing the moving sum of a stack of images. Each image in the stack is obtained through an elementary pointwise transform of the input image. This has a two-fold advantage. First, we can use fast recursive algorithms for computing the moving sum [5], [6], and, secondly, we can use parallel computation to further speed up the computation. We also show how shiftable kernels can also be used to approximate the (nonlinearshiftable) Gaussian kernel that is ubiquitously used in image filtering.