Kernel-Based Image Filtering: Fast Algorithms and Applications

Abstract

Image filtering is a fundamental preprocessing task in computer vision and image processing. Various linear and nonlinear filters are routinely used for enhancement, upsampling, sharpening, reconstruction, etc. The focus of this thesis is on kernel-based filtering that has received significant attention in recent years. The basic idea of kernel filtering is quite straightforward, namely, each pixel p in the image is replaced by a weighted average of its neighboring pixels q. The weighting is performed using a kernel k(p;q), which is nonnegative and symmetric. The weight assigned to a pair (p;q) is typically given by d(p;q)g( f (p) ð€€€ f (q)), where f (p) and f (q) are some representative features at p and q, g is a kernel acting on the feature space, and d(p;q) is a measure of spatial proximity. A concrete example in this regard is the bilateral filter, where g is a univariate Gaussian and f (p) is simply the intensity at p. A more robust choice is to use the intensities of the spatial neighbors of p as f (p), which is adopted in nonlocal means. While the dominant applications of kernel filtering are enhancement and denoising, it can also be used as a powerful regularizer for image reconstruction. In general, the brute-force implementation of kernel filtering is prohibitively expensive. Unlike convolution filters, they cannot (directly) be implemented efficiently using recursion or the fast Fourier transform. In fact, their brute-force implementation is often too slow for realtime applications. To address this issue, researchers have come up with various approximation algorithms that can significantly speedup the implementation without sacrificing visual quality. Apart from their excellent filtering capacity, it would be fair to say that the popularity of kernel filtering is due to the availability of these fast algorithms. In the first part of the thesis, we propose some fast algorithms for bilateral filtering (BLF) and nonlocal means (NLM), which are by far the most popular forms of kernel filtering. In particular, we demonstrate that by using the Fourier approximation of the underlying kernel, we can obtain state-of-the-art fast algorithms for BLF of grayscale images. The core idea is that by expressing the kernel in terms of sinusoids, we can approximate the brute-force implementation using fast convolutions; the convolutions are performed on images that are derived from the input image via simple pointwise transforms. An attractive aspect of our algorithm is that the complexity does not scale with the size of the neighborhood over which the aggregation is performed. Just to give an idea, we are able to achieve 50 speedup while ensuring that the PSNR (between the brute-force and fast implementations) is above 60dB. In fact, it is often difficult to visually distinguish the outputs of the brute-force and the fast implementations. A distinct aspect of our method is that we are able to analyze and bound the filtering error incurred by the approximation. We extend our fast approximation in a couple of directions: (i) for a variant of BLF called bright-pass BLF in which only those neighboring pixels whose intensities are at least as large as the center pixel are aggregated, and (ii) for a scale-adaptive variant of BLF that can be used for suppressing ne textures in images. In the latter case, we cannot use convolutions any more (since the spatial window is varying), but we can still use fast recursions. We next consider the filtering of color images, which involves the approximation of a three-dimensional kernel. The challenge in this regard is that while an accurate Fourier approximation of a one-dimensional kernel (for grayscale filtering) can be obtained using N 10 terms, a comparable approximation in three dimensions (for color filtering) requires N3 Fourier terms and proportionate number of convolutions. We show how this can be overcome using Monte-Carlo sampling, where the Fourier terms are sampled from the distribution induced by the coefficients. Furthermore, we show that the variance of Monte-Carlo sampling can be reduced by conditionally sampling the low and high frequency Fourier terms. This allows us to cut down the pixelwise fluctuation of the filtered output as a result (at some additional cost). In a different direction, we next propose a fast algorithm called PatchLift for exact NLM of one-dimensional signals. NLM uses the collection of neighboring pixel intensities (called patch) as the feature f (p), and where k(p;q) = g( f (p)ð€€€ f (q)) with g being a multidimensional Gaussian. PatchLift is based on the observation that all possible kernel values k(p;q) can be read off from a matrix that is derived from the one-dimensional signal using lifting and a single convolution. In particular, the number of operations required to compute the patch distances does not scale with the patch dimension. We demonstrate how Patch Lift can be used for NLM of grayscale images using a separable formulation of NLM. Our implementation is few orders faster than the brute-force implementation and is competitive with existing fast implementations. Finally, we consider a symmetrized variant of NLM that can be used as a regularizer within the plug-and-play framework for image restoration and develop a fast implementation for the same. In the second part, we propose some novel applications of kernel filtering: (i) We apply the scale-adaptive variant of BLF for suppressing fine textures in images. The rationale is that by adapting the window over which the aggregation is performed, we can smooth out fine textures and simultaneously preserve coarse structures. (ii) The fast bright-pass BLF is used to estimate illumination for the retinex model. The resulting algorithm offers significant speedups for low-light image enhancement. (iii)We use the fast symmetrized NLM as a regularizer with the plug-and-play framework for model based image restoration/reconstruction. This offers significant speedup over the brute force implementation.