Image compression using an edge adapted redundant dictionary and wavelets

Low bit rate image coding is an important problem regarding applications such as storage on low memory devices or streaming data on the internet. The state of the art in image compression is to use 2-D wavelets. The advantages of wavelet bases lie in their multiscale nature and in their ability to sparsely represent functions that are piecewise smooth. Their main problem on the other hand, is that in 2-D wavelets are not able to deal with the natural geometry of images, i.e they cannot sparsely represent objects that are smooth away from regular submanifolds. In this paper we propose an approach based on building a sparse representation of the edge part of images in a redundant geometrically inspired library of functions, followed by suitable coding techniques. Best N-terms non-linear approximations in general dictionaries is, in most cases, a NP-hard problem and sub-optimal approaches have to be followed. In this work we use a greedy strategy, also known as Matching Pursuit to compute the expansion. The residual, that we suppose to be the smooth and texture part, is then coded using wavelets. A rate distortion optimization procedure choses the number of functions from the redundant dictionary and the wavelet basis.

Algorithms and methods for sparse approximation in structured dictionaries

Lorenzo Peotta

In the last decade we observed an increasing interaction between data compression and sparse signals approximations. Sparse approximations are desirable because they compact the energy of the signals in few elements and correspond to a structural simplification of the approximated signals. In the first part of this dissertation we consider the low bit rate image coding problem. The state of the art in image compression is to use two-dimensional (2-D) wavelets. The main advantage of wavelet bases lie in their multiscale nature and in their ability to sparsely represent functions that are piecewise smooth. Their main problem on the other hand, is that 2-D wavelets are not able to deal with the natural geometry of images, i.e. they cannot sparsely represent objects that are smooth away from regular submanifolds. We propose an approach based on building a sparse approximation of the edge part of images in a redundant geometrically inspired library of functions, followed by suitable coding techniques. The edge-oriented dictionary is built by anisotropically scaling, orienting and bending a generating function. The new bending transform generates elementary waveforms that efficiently approximate the edges; with few waveforms we are able to approximate long edges. The sparse approximations over the redundant dictionary are computed using a sub-optimal greedy strategy, as indeed finding the best m-terms non-linear approximations in general dictionaries is a NP-hard problem. Recently there has been an intense activity in the field of sparse approximations with redundant dictionaries, largely motivated by the practical performances of algorithms such as Matching Pursuit and Basis Pursuit. However, most of the theoretical results obtained so far are valid only for the restricted class of incoherent dictionaries. The second part of the dissertation investigates a new class of overcomplete dictionaries, called block incoherent dictionaries, where coherence can be arbitrarily large. We show that a simple greedy algorithm can correctly identify stable subdictionaries (called blocks) and demonstrate how one can use the extra coherence freedom for approximation purposes. With the aim of improving the sparse approximations over redundant dictionaries obtained with greedy algorithms, in the last part we develop a new decomposition algorithm characterized by the computational cost of MP and global optimization properties typical of the re-weighted minimum norm algorithms such as FOCUSS. We introduce the concept of sub-dictionary, a subset of the redundant dictionary which depends on the signal to be approximated, and we propose a sub-dictionary selection algorithm based on greedy techniques. The low computational cost greedy algorithm selects a sub-dictionary that contains the solution of more complex algorithms, which are utilized to obtain the approximation over the sub-dictionary. In the first part we studied image and video sparse approximation, however the concepts we present in the second part of the dissertation are general and can be applied to any kind of structured signal.

EPFL2007

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

Algorithms and methods for sparse approximation in structured dictionaries

Lorenzo Peotta

EPFL2007

Directionlets

Vladan Velisavljevic

EPFL2005