Optimal segmentation techniques for piecewise stationary signals

The concept of stationarity is central to signal processing; it indeed guarantees that the deterministic spectral properties of linear time-invariant systems are also applicable to realizations of stationary random processes. In almost all practical settings, however, the signal at hand is just a finite-size vector whose underlying generating process, if we are willing to admit one, is unknown; In this case, invoking stationarity is tantamount to stating that a single linear system (however complex) suffices to model the data effectively, be it for analysis, processing, or compression purposes. It is intuitively clear that if the complexity of the model can grow unchecked, its accuracy can increase arbitrarily (short of computational limitations); this defines a tradeoff in which, for a given data vector, a set of complexity/accuracy pairs are defined for each possible model. In general one is interested in parsimonious modeling; by identifying complexity with "rate" and model misadjustment with "distortion", the situation becomes akin to an operational rate-distortion (R/D) problem in which, for each possible "rate", the goal is to find the model yielding t lie minimum distortion. In practice, however, only a finite palette of models is available, the complexity of which is limited by computational reasons: therefore, the entire data vector often proves too "non-stationary" for any single model. If the process is just slowly drifting, adaptive systems are probably the best choice; on the other hand, a wide class of signals exhibits a series of rather abrupt transition between locally regular portions (e.g. speech, images). In this case a common solution is to partition the data uniformly so that the resulting pieces are small enough to appear stationary with respect to the available models. However, if the goal is again to obtain an overall modeling which is optimal in the above R/D sense, it is necessary that the segmentation be a free variable in the modelization process; this is however not the case if a fixed-size time windowing is used. Note that now the reachable points in the R/D plane are in fact indexed not just by a model but by a segmentation/model-sequence pair; their number therefore grows exponentially with the size of the data vector. This thesis is concerned with the development of efficient techniques to explore this R/D set and to determine its operational lower bound for specific signal processing problems. It will be shown that, under very mild hypotheses, many practical applications dealing with nonstationary data sets can be cast as a R/D optimization problem involving segmentation, which can in turn be solved using polynomial-time dynamic programming techniques. The flexibility of the approach will be demonstrated by a very diverse set of examples: after a general overview of the various facets of the dynamic segmentation problem in Chapter 2, Chapter 3 will use the framework to determine an operational R/D bound for the approximation of piecewise polynomial function with respect to wavelet-based approximation; Chapter 4 will show its relevant to compression problems, and in particular to speech coding based on linear prediction and to arithmetic coding for binary sources; finally, in Chapter 5, an efficient data hiding scheme for PCM audio signals will be described, in which the optimal power allocation for the hidden data is determined with respect to the time-varying characteristics of the host signal.

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

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.

EPFL2002

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