Optimally Localized Wavelets and Smoothing Kernels

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.

Fast Space-Variant Elliptical Filtering Using Box Splines

Kunal Narayan Chaudhury, Michaël Unser

The efficient realization of linear space-variant (non-convolution) filters is a challenging computational problem in image processing. In this paper, we demonstrate that it is possible to filter an image with a Gaussian-like elliptic window of varying size, elongation and orientation using a fixed number of computations per pixel. The associated algorithm, which is based upon a family of smooth compactly supported piecewise polynomials, the radially-uniform box splines, is realized using preintegration and local finite-differences. The radially-uniform box splines are constructed through the repeated convolution of a fixed number of box distributions, which have been suitably scaled and distributed radially in an uniform fashion. The attractive features of these box splines are their asymptotic behavior, their simple covariance structure, and their quasi-separability. They converge to Gaussians with the increase of their order, and are used to approximate anisotropic Gaussians of varying covariance simply by controlling the scales of the constituent box distributions. Based upon the second feature, we develop a technique for continuously controlling the size, elongation and orientation of these Gaussian-like functions. Finally, the quasi-separable structure, along with a certain scaling property of box distributions, is used to efficiently realize the associated space-variant elliptical filtering, which requires O(1) computations per pixel irrespective of the shape and size of the filter.

IEEE2010

Image security and processing in the JPEG 2000 compressed domain

Raphaël Grosbois

Digital images are becoming increasingly successful thanks to the development and the facilitated access to systems permitting their generation (i.e. camera, scanner, imaging software, etc). A digital image basically corresponds to a 2D discrete set of regularly spaced samples, called pixels, where each pixel contains the light intensity information (e.g., luminance, chrominance) of a very localized spatial region of the image. In the case of natural images, pixel values are acquired through one or several arrays of MOS semiconductors (Charge Couple Devices, CCDs), each generating an electrical information proportional to the incoming light intensity. The initial finalities of digital images were the storage on a dedicated medium (e.g., camera's memory, computer's hard drive, CDROM), eventual transmissions, and final display on a screen or printing. With such a narrow scope, the principal goal of image processing and coding tools was to face storage and transmission bandwidth limitations thanks to efficient compression algorithms reducing the image representation size. However, with recent developments in computing, algorithmic and telecommunication domains, many new applications (i.e. web-publishing, remote browsing etc.) have arisen. They generally require additional and enhanced features (i.e. progressive decoding, random-access, region of interest support, robustness to transmission errors, etc.) and have motivated the creation of a new generation of coding algorithms which, besides their good compression performance, present many other useful features. Hence, digital images are almost never represented as a simple set of pixel values (i.e. raw representation) but, instead, under a specific compact way (i.e. compressed or coded representation), chosen according to features it brings to the considered application. A compressed version of an image is obtained by removing as much spatial, visual and statistical redundancies as possible, thanks to appropriate coding methods, while keeping an acceptable visual quality. Noting that natural images have most of their energy concentrated in low frequency components, recent coding algorithms generally first decompose the image into a specific frequency domain DCT, DWT, etc). The goal is to obtain a representation, where few coefficients are sufficient for reconstructing the image with a good quality. The precision of transformed coefficients is then generally reduced by quantization in order to make them more compressible by an entropy coder, aiming at removing statistical redundancies of quantization indexes. The ultimate compressed representation, called codestream, is usually obtained by a rate-allocation process that tries to achieve the best trade-off between the compression ratio and the reconstructed image quality. JPEG 2000, the new still image coding standard developed by the Joint Photographic Experts Group JPEG), is based on these state-of-the-art compression techniques, but is also designed to fulfill many requirements of recent applications. It only normalizes the decoding algorithm and consequently let some liberty for designing encoders optimized for some specific features or for building extensions that take profit from its compressed domain specifics. The success of the JPEG 2000 standard will not only depend on its intrinsic performance, but also on its ability to comply with specific demands of actual and future imaging applications. Thus, among the major concerns of image content providers are the security of the transmission over networks and of the image itself: with current facilities to instantly access on-line digital libraries from anywhere in the world, to perfectly copy and to easily modify the content of an image, solutions must be found in order to permit, at one hand, Intellectual Property Right (IPR) protection and image integrity verification and, at the other hand, the development of dedicated tools favoring exchange and purchase of images over communication networks. It is worth pointing out that some cryptographic-based solutions to these problems already exist. However, they need to be adapted to the digital image and its compressed domain representation in order to take full advantage from their specifics and to avoid restraining fields of applications. The JPEG 2000 coding algorithm is mainly based on Discrete Wavelet Transform (DWT), embedded scalar quantization and adaptive arithmetic coding. From a terminology point of view, this means that compressed domain representation can indifferently refer to either wavelet coefficients, or quantized wavelet coefficients, or bit streams (i.e. entropy coded group of quantization indexes) or the codestream (i.e. aggregation of bit streams and headers containing necessary decoding information). The choice of the appropriate compressed domain actually depends on the considered application. The quality of a JPEG 2000 image, at a given compression ratio, mainly depends on the rate-allocation procedure used at the encoder side. Such a procedure applies on entropy coded quantization indexes and favors groups of quantization indexes (i.e. code-blocks) offering the best rate-distortion trade-offs. However, this does not necessary correspond to the most interesting part of the image, from an end-observer point of view. Hence, the standard provides with ways to define Regions Of Interest (ROI) which are prioritized during the encoding process in order to exhibit a higher quality than the rest (i.e. background) at any decoding time. This feature applies either in the quantized wavelet domain or at the bit stream level, but its parameters are generally not very explicit for a standard end-user and only provide with a rough control of the decoded ROI quality. Consequently, the first objective of this thesis is to create and also extend compressed domain tools for controlling the quality of a JPEG 2000 ROI. In the meantime, several image processing techniques, such as watermarking, are applied directly in the spatial domain or in a specific transform space defined from the spatial domain. However, since digital images are preferably available under a compressed/encoded format, which we assume to be JPEG 2000 in this thesis, their implementation first imply decompressing the image, then apply the considered processing task and finally re-encode the resulting image. Such a scheme has two main drawbacks: First, it generally implies time and complexity overheads compared to equivalent methods (if they exist) in the JPEG 2000 compressed domain. Such effects become important when the scheme is repeatedly applied on multiple images. Second, since encoding and decoding operations are generally lossy, the introduced distortion can become non negligible whenever several processing tasks are repeated on a same image. These observations lead to the second objective of this thesis, which is to adapt or create a watermarking algorithm dedicated to the JPEG 2000 compressed domain. Finally, there are imaging algorithms, such as authentication and access control, that already exist and could be directly applied to JPEG 2000 images but, because they do not take into account the coding algorithm specifics, they either decrease compression performance or remove useful features of the encoded representation (scalability, random access, etc). This leads to the third objective of this thesis, which is to adapt, create and combine authentication and access control algorithms with JPEG 2000 coding and decoding. Thus, the common goal of the three objectives described above is the deep integration of selected processing and security algorithms into a JPEG 2000 codec in order to provide with minimum complexity, JPEG 2000 compliant codestreams and an unified framework for many imaging applications.

EPFL2003

Improvements on "Fast Space-Variant Elliptical Filtering Using Box Splines"

Kunal Narayan Chaudhury, Sebanti Sanyal

It is well-known that box filters can be efficiently computed using pre-integration and local finite-differences. By generalizing this idea and by combining it with a nonstandard variant of the central limit theorem, we had earlier proposed a constant-time or O(1) algorithm that allowed one to perform space-variant filtering using Gaussian-like kernels. The algorithm was based on the observation that both isotropic and anisotropic Gaussians could be approximated using certain bivariate splines called box splines. The attractive feature of the algorithm was that it allowed one to continuously control the shape and size (covariance) of the filter, and that it had a fixed computational cost per pixel, irrespective of the size of the filter. The algorithm, however, offered a limited control on the covariance and accuracy of the Gaussian approximation. In this paper, we propose some improvements of our previous algorithm.

Ieee-Inst Electrical Electronics Engineers Inc2012

Image security and processing in the JPEG 2000 compressed domain

Raphaël Grosbois

EPFL2003