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) and#1048576; 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...