Optimally Localized Wavelets and Smoothing Kernels
K.N. Chaudhury
École polytechnique fédérale de Lausanne, EPFL Thesis no. 4968 (2011), 239 p., February 16, 2011.
It is well-known that the Gaussian functions and, more generally, their modulations-translations (the Gabor functions) have the unique property of being optimally localized in space and frequency in the sense of Heisenberg's uncertainty principle. In this thesis, we address the construction of complex wavelets modeled on the Gabor function, and smoothing kernels based on the Gaussian. We proceed by relaxing the exact form of the Gaussian and Gabor function, and by approximating them using spline functions. In particular, we construct a family of spline wavelets, termed Gabor-like wavelets, which provide arbitrary close approximations of the Gabor function. On the other hand, we introduce a family of compactly supported box splines to approximate the Gaussian, both isotropic and anisotropic. The attractive feature of these spline wavelets and kernels is that we are able to develop fast and efficient algorithms for implementing the associated transforms.
The Gabor-like wavelet is obtained within the framework of multiresolution analysis by combining Hilbert transform pairs of B-spline wavelets. To begin with, we provide a rigorous understanding of why the Hilbert transform goes well with wavelets. We show that at the heart of this is the characteristic vanishing-moment property of wavelets and certain fundamental invariances of the Hilbert transform. The former allows us to ensure that the Hilbert transform (which is non-local) of a localized wavelet is again well-localized provided that it has sufficient number of vanishing moments, while the latter allows us to seamlessly integrate it into the multiresolution framework of wavelets. Guided by these facts, we formulate a general recipe for constructing a pair of wavelet bases that form a Hilbert transform pair. Using this recipe, we are able to identify a pair of B-spline wavelets that are related through the Hilbert transform. We show that the complex wavelet derived from this pair converges to a Gabor function as its order gets large. We next extend the construction to higher dimensions using the directional Hilbert transform and tensor-products wavelets. This results in a system of complex wavelets that closely resemble the directional Gabor functions. We develop an efficient numerical algorithm for implementing the associated complex wavelet transforms on finite periodic data.
We next identify the complete family of transforms which share the fundamental invariances of the Hilbert transform. Based on this family of transforms and its particular properties, we are able to provide an amplitude-phase interpretation of the signal representation associated with the Gabor-like wavelet transform. This allows us to understand the significance of the amplitude and phase information associated with the transform.
As an application, we develop a coarse-to-fine stereo-matching algorithm that does dynamic programming on the sub-sampled Gabor-like wavelet pyramid instead of the raw pixel intensities. The crucial feature of our pyramid was that it provides near translation-invariance at the cost of moderate redundancy. The translation-invariance is absolutely essential for encoding the local spatial translations between the stereo pair. Based on the particular Gabor-like form of our wavelets, we also provided a mathematical explanation of the near translation-invariance of our pyramid. From a computational standpoint, we show that a significant reduction of the run time is achieved in comparison with the standard dynamic programming algorithm.
In the second half of the thesis, we introduce a particular bivariate box spline termed the radially-uniform box spline. As an application of the Central Limit Theorem, we show that it converges to a Gaussian as its order gets large. For a fixed order, we show how the parameters of the box spline can be tuned to approximate a fixed anisotropic Gaussian. In particular, we develop a simple root-finding algorithm for controlling the anisotropy of the elliptical box splines.
We next investigate the efficient realization of space-variant (or non-convolution) Gaussian filters using these box splines. The realization of even the simple convolution Gaussian filter is known to be computationally challenging, particularly when the size of Gaussian is large. The number of computations required per pixel for a direct implementation of the filter scales linearly with the size of the filter. We demonstrated that it is possible to filter an image with Gaussian-like box splines of varying size, elongation and orientation using a fixed number of computations per pixel (constant-time implementation). The associated algorithm is easy to implement and uses simple pre-integrations and local finite-differences.
As an application of the Gaussian-like box splines and the associated filtering algorithm, we develop two algorithms for space-variant filtering. The first of these is inspired by anisotropic Gaussian diffusion. The space-variance in this case is in terms of the size, elongation, and orientation of the box splines, which are controlled using the local image features. The other scheme is based on a space-variant form of the Gaussian bilateral filter. The spatial adaptability in this case was in terms of the size of the spatial Gaussian filter. The highlight is that we are able to develop a constant-time algorithm for implementing the bilateral filter by approximating the variable spatial filter using isotropic box splines, and by approximating the fixed range filter (locally) using a class of shiftable kernels. We demonstrate their usage by developing smoothing algorithms for signal-adaptive denoising of images. As an application in a different direction, we develop box spline filters resembling the Laplacian-of-Gaussian. Using this particular detector, and by appropriately modifying the basic filtering algorithm, we develop a fast template-matching algorithm for the detection of bright cells and nuclei in fluorescence images.
@PHDTHESIS(http://bigwww.epfl.ch/publications/chaudhury1101.html,
AUTHOR="Chaudhury, K.N.",
TITLE="Optimally Localized Wavelets and Smoothing Kernels",
SCHOOL="{\'{E}}cole polytechnique f{\'{e}}d{\'{e}}rale de {L}ausanne
({EPFL})",
YEAR="2011",
type="{EPFL} Thesis no.\ 4968 (2011), 239 p.",
address="",
month="February 16,",
note="")