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 Gaus...
详细信息
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.
It is well known that spatial averaging can be realized (in space or frequency domain) using algorithms whose complexity does not scale with the size or shape of the filter. These fast algorithms are generally referre...
详细信息
It is well known that spatial averaging can be realized (in space or frequency domain) using algorithms whose complexity does not scale with the size or shape of the filter. These fast algorithms are generally referred to as constant-time or O(1) algorithms in the image-processing literature. Along with the spatial filter, the edge-preserving bilateral filter involves an additional range kernel. This is used to restrict the averaging to those neighborhood pixels whose intensity are similar or close to that of the pixel of interest. The range kernel operates by acting on the pixel intensities. This makes the averaging process nonlinear and computationally intensive, particularly when the spatial filter is large. In this paper, we show how the O(1) averaging algorithms can be leveraged for realizing the bilateral filter in constanttime, by using trigonometric range kernels. This is done by generalizing the idea presented by Porikli, i.e., using polynomial kernels. The class of trigonometric kernels turns out to be sufficiently rich, allowing for the approximation of the standard Gaussian bilateral filter. The attractive feature of our approach is that, for a fixed number of terms, the quality of approximation achieved using trigonometric kernels is much superior to that obtained by Porikli using polynomials.
The Euclidean distance transform (EDT) is an operation to convert a binary image consisting of black and white pixels to a representation where each pixel has the Euclidean distance of the nearest black pixel. The EDT...
详细信息
The Euclidean distance transform (EDT) is an operation to convert a binary image consisting of black and white pixels to a representation where each pixel has the Euclidean distance of the nearest black pixel. The EDT has many applications in computer vision and image processing. In this paper, we present a constant-time algorithm for computing the EDT of an N x N image on a reconfigurable mesh. Our algorithm. has two variants. (i) If the image is initially given in an Xx N mesh, one pixel per processor, our algorithm requires an N x N x N mesh for computing the EDT. (ii) If the image is given in an N x N-2 mesh, each row of the image in the First row of a separate N x X mesh, we can compute the EDT in the same N x N-2 mesh. The AT(2) bounds for these two variants are O(N-4) and O(N-3) respectively. The best previously known algorithm (Y. Pan and K. Li, Inform. Sci. 120 (1999), 209-221) for this problem assumes input similar to the second variant of our algorithm and runs in constant-time on an N-2 x N-2 reconfigurable mesh with an AT(2) bound of O(N-4). Hence both variants of our algorithm improve upon the processor complexity of the algorithm in Pan and Li (1999) by a factor of N and the second variant improves upon the AT(2) complexity by a factor of N. (C) 2001 Academic Press.
The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its distance to the nearest foreground pixel. Two parallel algorithms for EDT on linear array with reconfig...
详细信息
The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its distance to the nearest foreground pixel. Two parallel algorithms for EDT on linear array with reconfigurable pipeline bus system (LARPBS) are presented. For an image with n x n pixels, the first algorithm can complete EDT in O[(log n log log n)/(log log log n)] time using n(2) processors. The second algorithm can computethe EDT in O(log n log log n) time using n(2)/(log log n) processors.
暂无评论