Sparse is compact and in press (special issue)

Szeged University Memorial plaque in honor of Haar and Riesz

All papers in press for the Special Issue of Signal Processing on "Multirate Filter Bank Structures and Multiscale Representations" (announced here at Nuit Blanche)  are now available online and published in Volume 91, Issue 12, December 2011. 100 years after Alfred Haar seed, with the help of about 100 reviewers. While waiting for the paperback versions in the solid world, have a look at the following contributions in digital form, gathered on a dedicated page Signal Processing: Special issue on Advances in Multirate Filter Bank Structures and Multiscale Representations. They deal with 1-D signals to 2-D images, from image coding to compressive sensing, from fixed to adaptive representations, with a common bias toward sparsity. Forthcoming "call for papers" in 2011, related to sparsity, were gathered in a previous post: Sparse is abundant.

A century after the first outbreak of wavelets in Alfred Haar's thesis in 1909, filter banks and wavelet transforms lie at the heart of many digital signal processing and communication systems. During the last thirty years, they have been the focus of tremendous theoretical advances and practical applications in a growing digital world. They are for instance present, as local linear expansions, at the core of many existing or forthcoming audio, image or video compression algorithms.

Beyond standards, many exciting developments have emerged in filter banks and wavelets from the confrontation between scientists from different fields (including signal and image processing, computer science, harmonic analysis, approximation theory, statistics, bioengineering, physics,\ldots). At their confluence, multiscale representations of data, associated with their efficient processing in a multirate manner, have unveiled tools or refreshed methods impacting the whole data management process, from acquisition to interpretation, through communications, recovery and visualization. Multirate structures naturally shelter key concepts such as the duality between redundancy and sparsity, as well as means for extracting low dimensional structures from higher ones. In image processing in particular, various extensions of wavelets provide smart linear tools for building insightful geometrical representations of natural images.
The purpose of this special issue is to report on recent progresses performed, and emerging trends, in the domain of multirate filter banks and multiscale representations of signals and images. Topics addressed faithfully reflect the active research pertaining to this field, including sparse representations of (1-D) signals to (2-D) images, multiscale models and processing, shrinkage and denoising, compressive sensing, oversampled discrete frames, geometrical multiscale transforms, hybrid and adaptive representations and non-separable lifting for image compression.

Fast orthogonal sparse approximation algorithms over local dictionaries (DOI:10.1016/j.sigpro.2011.01.004)

Boris Mailhé and Rémi Gribonval and Pierre Vandergheynst and Frédéric Bimbot

Abstract:

In this work we present a new greedy algorithm for sparse approximation called LocOMP.
LocOMP is meant to be run on local dictionaries made of atoms with much shorter supports than the signal length.
This notably encompasses shift-invariant dictionaries and time-frequency dictionaries, be they monoscale or multiscale.
In this case, very fast implementations of Matching Pursuit are already available.
LocOMP is almost as fast as Matching Pursuit while approaching the signal almost as well as the much slower Orthogonal Matching Pursuit.

Keywords:

Sparse approximation; Greedy algorithms; Shift invariance; Orthogonal Matching Pursuit

Recursive Nearest Neighbor Search in a Sparse and Multiscale Domain for Comparing Audio Signals (DOI:10.1016/j.sigpro.2011.03.002)

Bob Sturm and Laurent Daudet

Abstract:

We investigate recursive nearest neighbor search in a sparse domain
at the scale of audio signals.
Essentially, to approximate the cosine distance between the signals
we make pairwise comparisons between
the elements of localized sparse models built from
large and redundant multiscale dictionaries of time-frequency atoms.
Theoretically, error bounds on these approximations provide
efficient means for quickly reducing the search space to
the nearest neighborhood of a given data;
but we demonstrate here that the tightest bound
involving a probabilistic assumption does not provide a practical approach
for comparing audio signals with respect to this distance measure.
Our experiments show, however, that regardless of these non-discriminative bounds,
we only need to make a few atom pair comparisons
to reveal, e.g., the position of origin of an excerpted signal,
or melodies with similar time-frequency structures.

Keywords:

Multiscale decomposition; Sparse approximation; Time—frequency dictionary; Audio similarity

Symmetric Tight Frame Wavelets With Dilation Factor M=4 (DOI:10.1016/j.sigpro.2011.05.005)

Farras Abdelnour

Abstract:

In this paper we discuss a new set of symmetric tight frame wavelets with the associated filterbank outputs downsampled by four at each stage. The frames consist of seven generators obtained from the lowpass filter using spectral factorization, with the lowpass filter obtained via Groebner basis method. The filters are simple to construct, and offer smooth scaling functions and wavelets. Additionally, the filterbanks presented in this paper have limited redundancy while maintaining the smoothness of underlying limit functions. The filters are linear phase (symmetric), FIR, and the resulting wavelets possess vanishing moments.

Keywords:

Wavelet transform; Frame; Symmetric filterbanks; Multiresolution analysis

Activelets: Wavelets for Sparse Representation of Hemodynamic Responses (DOI:10.1016/j.sigpro.2011.03.008)

Ildar Khalidov and Jalal Fadili and Francois Lazeyras and Dimitri Van De Ville and Michael Unser

Abstract:

We propose a new framework to extract the activity-related component in the BOLD functional Magnetic Resonance Imaging (fMRI) signal. As opposed to traditional fMRI signal analysis techniques, we do not impose any prior knowledge of the event timing. Instead, our basic assumption is that the activation pattern is a sequence of short and sparsely-distributed stimuli, as is the case in slow event-related fMRI.

We introduce new wavelet bases, termed ``activelets'', which sparsify the activity-related BOLD signal. These wavelets mimic the behavior of the differential operator underlying the hemodynamic system. To recover the sparse representation, we deploy a sparse-solution search algorithm.

The feasibility of the method is evaluated using both synthetic and experimental fMRI data. The importance of the activelet basis and the non-linear sparse recovery algorithm is demonstrated by comparison against classical B-spline wavelets and linear regularization, respectively.

Keywords:

BOLD fMRI; Hemodynamic response; Wavelet design; Sparsity; l1 minimization

Resonance-Based Signal Decomposition: A New Sparsity-Enabled Signal Analysis Method (DOI:10.1016/j.sigpro.2010.10.018)

Ivan Selesnick

Abstract:

Numerous signals arising from physiological and physical processes, in addition to being non-stationary, are moreover a mixture of sustained oscillations and non-oscillatory transients that are difficult to disentangle by linear methods. Examples of such signals include speech, biomedical, and geophysical signals. Therefore, this paper describes a new nonlinear signal analysis method based on signal resonance, rather than on frequency or scale, as provided by the Fourier and wavelet transforms. This method expresses a signal as the sum of a ‘high-resonance’ and a ‘low-resonance’ component—a high-resonance component being a signal consisting of multiple simultaneous sustained oscillations; a low-resonance component being a signal consisting of non-oscillatory transients of unspecified shape and duration. The resonance-based signal decomposition algorithm presented in this paper utilizes sparse signal representations, morphological component analysis, and constant-Q (wavelet) transforms with adjustable Q-factor.

Keywords:
Sparse signal representation; Constant-Q transform; Wavelet transform; Morphological component analysis

Multivariate empirical mode decomposition and application to multichannel filtering (DOI:10.1016/j.sigpro.2011.01.018)

Amar Kachenoura and Julien Fleureau and Laurent Albera and Jean-Claude Nunes and Lotfi Senhadji

Abstract:

Empirical Mode Decomposition (EMD) is an emerging topic in signal processing research, applied in various practical fields due in particular to its data-driven filter bank properties. In this paper, a novel EMD approach called X-EMD (eXtended-EMD) is proposed, which allows for a straightforward decomposition of mono- and multivariate signals without any change in the core of the algorithm. Qualitative results illustrate the good behavior of the proposed algorithm whatever the signal dimension is. Moreover, a comparative study of X-EMD with classical mono- and multivariate methods is presented and shows its competitiveness. Besides, we show that X-EMD extends the filter bank properties enjoyed by monovariate EMD to the case of multivariate EMD. Finally, a practical application on multi-channel sleep recording is presented.

Keywords:
Mono- and multivariate empirical mode decomposition; Filter bank structure; Electroencephalography data analysis

A Panorama on Multiscale Geometric Representations, Intertwining Spatial, Directional and Frequency Selectivity (DOI:10.1016/j.sigpro.2011.04.025)

Laurent Jacques and Laurent Duval and Caroline Chaux and Gabriel Peyré

Abstract:

The richness of natural images makes the quest for optimal representations in
image processing and computer vision challenging. The latter observation has
not prevented the design of image representations, which trade off between
efficiency and complexity, while achieving accurate rendering of smooth regions
as well as reproducing faithful contours and textures. The most recent ones,
proposed in the past decade, share an hybrid heritage highlighting the
multiscale and oriented nature of edges and patterns in images. This paper
presents a panorama of the aforementioned literature on decompositions in
multiscale, multi-orientation bases or dictionaries. They typically exhibit
redundancy to improve sparsity in the transformed domain and sometimes its
invariance with respect to simple geometric deformations (translation,
rotation). Oriented multiscale dictionaries extend traditional wavelet
processing and may offer rotation invariance. Highly redundant dictionaries
require specific algorithms to simplify the search for an efficient (sparse)
representation. We also discuss the extension of multiscale geometric
decompositions to non-Euclidean domains such as the sphere or arbitrary meshed
surfaces. The etymology of panorama suggests an overview, based on a choice of
partially overlapping "pictures". We hope that this paper will contribute to
the appreciation and apprehension of a stream of current research directions in
image understanding.

Keywords:
Review; Multiscale; Geometric representations; Oriented decompositions; Scale-space; Wavelets; Atoms; Sparsity; Redundancy; Bases; Frames; Edges; Textures; Image processing; Haar wavelet; Non-Euclidean wavelets

Bandlet Image Estimation with Model Selection (DOI:10.1016/j.sigpro.2011.01.013)

Charles Dossal and Stéphane Mallat and Erwan Le Pennec

Abstract:

To estimate geometrically regular images in the white noise model and
obtain an adaptive near asymptotic minimaxity result, we consider a model selection
based bandlet
estimator. This bandlet estimator combines the best basis selection
behaviour of the model selection and the
approximation properties of the bandlet dictionary.
We derive its near asymptotic minimaxity for geometrically regular images as an
example of model selection with general dictionary of orthogonal bases.
This paper is thus
also a self contained tutorial on model selection with orthogonal bases dictionary.

Keywords:
Model selection; White noise model; Image estimation; Geometrically regular functions; Bandlets

Augmented Lagrangian based Reconstruction of non-uniformly sub-Nyquist sampled MRI data (DOI:10.1016/j.sigpro.2011.04.033)

Jan Aelterman and Hiep Luong and Bart Goossens and Aleksandra Pizurica and Wilfried Philips

Abstract:

MRI has recently been identified as a promising application for compressed-sensing-like regularization because of its potential to speed up the acquisition while maintaining the image quality. Thereby non-uniform k-space trajectories, such as random or spiral trajectories, are becoming more and more important, because they are well suited to be used within the compressed-sensing (CS) acquisition framework. In this paper, we propose a new reconstruction technique for non-uniformly sub-Nyquist sampled k-space data. Several parts make up this technique, such as the non-uniform Fourier transform (NUFT), the discrete shearlet transform and a augmented Lagrangian based optimization algorithm. Because MRI images are real-valued, we introduce a new imaginary value suppressing prior, which attenuates imaginary components of MRI images during reconstruction, resulting in a better overall image quality. Further, a preconditioning based on the Voronoi cell size of each NUFT data point speeds up the conjugate gradient optimization used as part of the optimization algorithm. The resulting algorithm converges in a relatively small number of iterations and guarantees solutions that fully comply to the imposed constraints. The results show that the algorithm is applicable not only to sub-Nyquist sampled k-space reconstruction, but also to MR image fusion and/or resolution enhancement.

Keywords:
Augmented Lagrangian methods; MRI reconstruction; Non-uniform Fourier transform; Shearlet; Compressed sensing

Matching Pursuit Shrinkage in Hilbert Spaces (DOI:10.1016/j.sigpro.2011.04.010)

Tieyong Zeng and Francois Malgouyres

Abstract:

In this paper, we study a variant of the Matching Pursuit named Matching Pursuit Shrinkage. Similarly to the Matching Pursuit it seeks for an approximation of a datum living in a Hilbert space by a sparse linear expansion in a countable set of atoms. The difference with the usual Matching Pursuit is that, once an atom has been selected, we do not erase all the information along the direction of this atom. Doing so, we can evolve slowly along that direction. The goal is to attenuate the negative impact of bad atom selections.

We analyze the link between the shrinkage function used by the algorithm and the fact that the result belongs to $l^2$, $l^1$ and $l^0$ space. Experimental results are also reported to show the potential application of the proposed algorithm.

Keywords:
Dictionary; Matching pursuit; Shrinkage; Sparse representation

Non Separable Lifting Scheme with Adaptive Update Step for Still and Stereo Image Coding (DOI:10.1016/j.sigpro.2011.01.003)

Mounir Kaaniche and Amel Benazza-Benyahia and Béatrice Pesquet-Popescu and Jean-Christophe Pesquet

Abstract:

Many existing works related to lossy-to-lossless multiresolution image compression are based on the lifting concept. It is worth noting that a separable lifting scheme may not appear very efficient to cope with the 2D characteristics of edges which are neither horizontal nor vertical. In this paper, we propose to use 2D non-separable lifting schemes that still enable progressive reconstruction and exact decoding of images. Their relevant advantage is to yield a tractable optimization of all the involved decomposition operators. More precisely, we design the prediction operators by minimizing the variance of the detail coefficients. Concerning the update filters, we propose a new optimization criterion which aims at reducing the inherent aliasing artifacts. A theoretical analysis of the proposed method is conducted in terms of the adaptation criterion considered in the optimization of the update filter. Simulations carried out on still images and residual ones generated from stereo pairs show the benefits which can be drawn from the proposed optimization of the lifting operators.

Keywords:
Lossless compression; Progressive reconstruction; Lifting schemes; Separable transforms; Non-separable transforms; Adaptive transforms; Multiresolution analysis; Wavelets; Stereo coding