| dc.description.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. | en_US |
