Directional multiresolution image representations

Efficient representation of visual information lies at the foundation of many image processing tasks, including compression, filtering, and feature extraction. Efficiency of a representation refers to the ability to capture significant information of an object of interest in a small description. For practical applications, this representation has to be realized by structured transforms and fast algorithms. Recently, it has become evident that commonly used separable transforms (such as wavelets) are not necessarily best suited for images. Thus, there is a strong motivation to search for more powerful schemes that can capture the intrinsic geometrical structure of pictorial information. This thesis focuses on the development of new "true" two-dimensional representations for images. The emphasis is on the discrete framework that can lead to algorithmic implementations. The first method constructs multiresolution, local and directional image expansions by using non-separable filter banks. This discrete transform is developed in connection with the continuous-space curvelet construction in harmonic analysis. As a result, the proposed transform provides an efficient representation for two-dimensional piecewise smooth signals that resemble images. The link between the developed filter banks and the continuous-space constructions is set up in a newly defined directional multiresolution analysis. The second method constructs a new family of block directional and orthonormal transforms based on the ridgelet idea, and thus offers an efficient representation for images that are smooth away from straight edges. Finally, directional multiresolution image representations are employed together with statistical modeling, leading to powerful texture models and successful image retrieval systems.

Directionlets

Vladan Velisavljevic

Efficient representation of geometrical information in images is very important in many image processing areas, including compression, denoising and feature extraction. However, the design of transforms that can capture these geometrical features and represent them with a sparse description is very challenging. Recently, the separable wavelet transform achieved a great success providing a computationally simple tool and allowing for a sparse representation of images. However, in spite of the success, the efficiency of the representation is limited by the spatial isotropy of the wavelet basis functions built in the horizontal and vertical directions as well as the lack of directionality. One-dimensional discontinuities in images (edges and contours), which are very important elements in visual perception, intersect with too many wavelet basis functions leading to a non-sparse representation. To capture efficiently these anisotropic geometrical structures characterized by many more than the horizontal and vertical directions, more flexible multi-directional and anisotropic transforms are required. We present a new lattice-based perfect reconstruction and critically sampled anisotropic multi-directional wavelet transform. The transform retains the separable filtering, subsampling and simplicity of computations and filter design from the standard two-dimensional wavelet transform, unlike in the case of some other existing directional transform constructions (e.g. curvelets, contourlets or edgelets). The corresponding anisotropic basis functions, which we call directionlets, have directional vanishing moments along any two directions with rational slopes. Furthermore, we show that this novel transform provides an efficient tool for non-linear approximation of images, achieving the decay of mean-square error O(N-1.55), which, while slower than the optimal rate O(N-2), is much better than O(N-1) achieved with wavelets, but at similar complexity. Owing to critical sampling, directionlets can easily be applied to image compression since it is possible to use Lagrange optimization as opposed to the case of overcomplete expansions. The compression algorithms based on directionlets outperform the methods based on the standard wavelet transform achieving better numerical results and visual quality of the reconstructed images. Moreover, we have adapted image denoising algorithms to be used in conjunction with an undecimated version of directionlets obtaining results that are competitive with the current state-of-the-art image denoising methods while having lower computational complexity.

EPFL2005

Discrete Ridgelet Transforms for Image Representation

Minh Do, Martin Vetterli

The ridgelet transform (Candes and Donoho, 1999) was introduced as a new multiscale representation for functions on continuous spaces that are smooth away from discontinuities along lines. In this paper, we present several discrete versions of the ridgelet transform that lead to algorithmic implementations. The resulting transforms are invertible, non-redundant and computed via fast algorithms. Furthermore, this construction leads to a family of directional orthonormal bases for digital images. Numerical results show that the new transforms are more effective than the wavelet transform in approximating and denoising images with straight edges. Keywords: wavelets, ridgelets, Radon transform, directional bases, discrete transforms, non-linear approximation, image denoising.

2001

Wavelet footprints and frames for signal processing and communication

Pier Luigi Dragotti

Linear transforms and expansions are fundamental mathematical tools of signal processing. In particular, the wavelet transform has played an important role in several signal processing tasks, compression being a prime example. A signal can be represented in a basis or a frame. Frames, which are an extension of bases to overcomplete sets of vectors, are sometimes preferred to bases because of their greater design freedom and recently they have had an important impact in signal processing. This thesis focuses on the design of new bases and frames for signal processing and communications. The first contribution of the thesis is the exploration of the use of oversampled filter banks, which represent a possible way to implement frames, to robust communications. Normally, transforms are used as a pure source coding method and a reliable communication is obtained with a channel coder which follows the source coder. In this case, we use frames to achieve efficient source compression and robustness to transmission errors at the same time. In the context of pure source transform coding, we investigate the performance of the wavelet transform and study the dependency of the wavelet coefficients across scales. This analysis leads to the design of a new expansion which provides an efficient representation of piecewise smooth signals. We call footprints the elements of this expansion. The main property of footprints is that they efficiently characterize the singular structures of the signal, which usually carry the main information. We show that algorithms based on footprints outperform wavelet methods in different applications such as denoising, compression and deconvolution. Finally, we study a particular source coding technique called multiple description coding. This technique is used for data transmission over unreliable networks. In multiple description coding, the coder generates several different descriptions of the same signal and the decoder can produce a useful reconstruction of the source with any received subset of these descriptions. We study the problem of multiple description coding of stationary Gaussian sources with memory. First, we compute the multiple description rate distortion region for these sources. Then, we develop an algorithm for the design of optimal critically sampled filter banks for multiple description coding of Gaussian sources.