Machine learning for protein modeling faces significant challenges due to proteins' inherently dynamic nature, yet most graph-based machine learning methods rely solely on static structural information. Recently, the growing availability of molecular dynamics trajectories provides new opportunities for understanding the dynamic behavior of proteins; however, computational methods for utilizing this dynamic information remain limited. We propose a novel graph representation that integrates both static structural information and dynamic correlations from molecular dynamics trajectories, enabling more comprehensive modeling of proteins. By applying relational graph neural networks (RGNNs) to process this heterogeneous representation, we demonstrate significant improvements over structure-based approaches across three distinct tasks: atomic adaptability prediction, binding site detection, and binding affinity prediction. Our results validate that combining static and dynamic information provides complementary signals for understanding protein-ligand interactions, offering new possibilities for drug design and structural biology applications.

Graph Neural Networks (GNNs) are models that leverage the graph structure to transmit information between nodes, typically through the message-passing operation. While widely successful, this approach is well-known to suffer from representational collapse as the number of layers increases and insensitivity to the information contained at distant and poorly connected nodes. In this paper, we present a unified view of on the appearance of these issues through the lens of vanishing gradients, using ideas from linear control theory for our analysis. We propose an interpretation of GNNs as recurrent models and empirically demonstrate that a simple state-space formulation of an GNN effectively alleviates these issues at no extra trainable parameter cost. Further, we show theoretically and empirically that (i) Traditional GNNs are by design prone to extreme gradient vanishing even after few layers; (ii) Feature collapse is directly related to the mechanism causing vanishing gradients; (iii) Long-range modeling is most easily achieved by a combination of graph rewiring and vanishing gradient mitigation. We believe our work will help bridge the gap between the recurrent and graph neural network literature and will unlock the design of new deep and performant GNNs.

ChebNet, one of the earliest spectral GNNs, has largely been overshadowed by Message Passing Neural Networks (MPNNs), which gained popularity for their simplicity and effectiveness in capturing local graph structure. Despite their success, MPNNs are limited in their ability to capture long-range dependencies between nodes. This has led researchers to adapt MPNNs through *rewiring* or make use of *Graph Transformers*, which compromise the computational efficiency that characterized early spatial message passing architectures, and typically disregard the graph structure. Almost a decade after its original introduction, we revisit ChebNet to shed light on its ability to model distant node interactions. We find that out-of-box, ChebNet already shows competitive advantages relative to classical MPNNs and GTs on long-range benchmarks, while maintaining good scalability properties for high-order polynomials. However, we uncover that this polynomial expansion leads ChebNet to an unstable regime during training. To address this limitation, we cast ChebNet as a stable and non-dissipative dynamical system, which we coin Stable-ChebNet. Our Stable-ChebNet model allows for stable information propagation, and has controllable dynamics which do not require the use of eigendecompositions, positional encodings, or graph rewiring. Across several benchmarks, Stable-ChebNet achieves near state-of-the-art performance.

Generating diverse, all‐atom conformational ensembles of dynamic proteins such as G‐protein‐coupled receptors (GPCRs) is critical for understanding their function, yet most generative models simplify atomic detail or ignore conformational diversity altogether. We present latent diffusion for full protein generation (LD-FPG), a framework that constructs complete all‐atom protein structures, including every side‐chain heavy atom, directly from molecular dynamics (MD) trajectories. LD-FPG employs a Chebyshev graph neural network (ChebNet) to obtain low‐dimensional latent embeddings of protein conformations, which are processed using three pooling strategies: blind, sequential and residue‐based. A diffusion model trained on these latent representations generates new samples that a decoder, optionally regularized by dihedral‐angle losses, maps back to Cartesian coordinates. Using D2R-MD, a $2\mu\text{s}$ MD trajectory (12 000 frames) of the human dopamine D$2$ receptor in a membrane environment, the sequential and residue-based pooling strategies reproduce the reference ensemble with high structural fidelity (all‐atom lDDT \~ $0.7$; $C\alpha$-lDDT \~ $0.8$) and recovers backbone and side‐chain dihedral‐angle distributions with a Jensen–Shannon divergence $<0.03$ compared to the MD data. LD-FPG thereby offers a practical route to system‐specific, all‐atom ensemble generation for large proteins, providing a promising tool for structure‐based therapeutic design on complex, dynamic targets. The D2R-MD dataset and our implementation are freely available to facilitate further research.

Gaussian processes (GPs) are popular nonparametric statistical models for learning unknown functions and quantifying the spatiotemporal uncertainty in data. Recent works have extended GPs to model scalar and vector quantities distributed over non-Euclidean domains, including smooth manifolds, appearing in numerous fields such as computer vision, dynamical systems, and neuroscience. However, these approaches assume that the manifold underlying the data is known, limiting their practical utility. We introduce RVGP, a generalisation of GPs for learning vector signals over latent Riemannian manifolds. Our method uses positional encoding with eigenfunctions of the connection Laplacian, associated with the tangent bundle, readily derived from common graph-based approximation of data. We demonstrate that RVGP possesses global regularity over the manifold, which allows it to super-resolve and inpaint vector fields while preserving singularities. Furthermore, we use RVGP to reconstruct high-density neural dynamics derived from low-density EEG recordings in healthy individuals and Alzheimer's patients. We show that vector field singularities are important disease markers and that their reconstruction leads to a comparable classification accuracy of disease states to high-density recordings. Thus, our method overcomes a significant practical limitation in experimental and clinical applications.

We consider the problem of learning implicit neural representations (INRs) for signals on non-Euclidean domains. In the Euclidean case, INRs are trained on a discrete sampling of a signal over a regular lattice. Here, we assume that the continuous signal exists on some unknown topological space from which we sample a discrete graph.In the absence of a coordinate system to identify the sampled nodes, we propose approximating their location with a spectral embedding of the graph. This allows us to train INRs without knowing the underlying continuous domain, which is the case for most graph signals in nature, while also making the INRs independent of any choice of coordinate system. We show experiments with our method on various real-world signals on non-Euclidean domains.

Proteins are typically represented by discrete atomic coordinates providing an accessible framework to describe different conformations. However, in some fields proteins are more accurately represented as near-continuous surfaces, as these are imprinted with geometric (shape) and chemical (electrostatics) features of the underlying protein structure. Protein surfaces are dependent on their chemical composition and, ultimately determine protein function, acting as the interface that engages in interactions with other molecules. In the past, such representations were utilized to compare protein structures on global and local scales and have shed light on functional properties of proteins. Here we describe RosettaSurf, a surface-centric computational design protocol, that focuses on the molecular surface shape and electrostatic properties as means for protein engineering, offering a unique approach for the design of proteins and their functions. The RosettaSurf protocol combines the explicit optimization of molecular surface features with a global scoring function during the sequence design process, diverging from the typical design approaches that rely solely on an energy scoring function. With this computational approach, we attempt to address a fundamental problem in protein design related to the design of functional sites in proteins, even when structurally similar templates are absent in the characterized structural repertoire. Surface-centric design exploits the premise that molecular surfaces are, to a certain extent, independent of the underlying sequence and backbone configuration, meaning that different sequences in different proteins may present similar surfaces. We benchmarked RosettaSurf on various sequence recovery datasets and showcased its design capabilities by generating epitope mimics that were biochemically validated. Overall, our results indicate that the explicit optimization of surface features may lead to new routes for the design of functional proteins.

We propose a graph signal processing framework to overcome the computational burden of Tensor Robust PCA (TRPCA). Our framework also serves as a convex alternative to graph regularized tensor factorization methods. Our method is based on projecting a tensor onto a lower-dimensional graph basis and benefits from significantly smaller SVDs as compared to TRPCA. Qualitative and computational experiments on several 2D and 3D tensors reveal that for the same reconstruction quality, our method attains up to 100 times speed-up on a low-rank and sparse decomposition application.

In this work, we propose a new, fast and scalable method for anomaly detection in large time-evolving graphs. It may be a static graph with dynamic node attributes (e.g. time-series), or a graph evolving in time, such as a temporal network. We define an anomaly as a localized increase in temporal activity in a cluster of nodes. The algorithm is unsupervised. It is able to detect and track anomalous activity in a dynamic network despite the noise from multiple interfering sources.

Acoustical behavior of a room for a given position of microphone and sound source is usually described using the room impulse response. If we rely on the standard uniform sampling, the estimation of room impulse response for arbitrary positions in the room requires a large number of measurements. In order to lower the required sampling rate, some solutions have emerged that exploit the sparse representation of the room wavefield in the terms of plane waves in the low-frequency domain. The plane wave representation has a simple form in rectangular rooms. In our solution, we observe the basic axial modes of the wave vector grid for extraction of the room geometry and then we propagate the knowledge to higher order modes out of the low-pass version of the measurements. Estimation of the approximate structure of the k-space should lead to the reduction in the terms of number of required measurements and in the increase of the speed of the reconstruction without great losses of quality.

How does coarsening affect the spectrum of a general graph? We provide conditions such that the principal eigenvalues and eigenspaces of a coarsened and original graph Laplacian matrices are close. The achieved approximation is shown to depend on standard graph-theoretic properties, such as the degree and eigenvalue distributions, as well as on the ratio between the coarsened and actual graph sizes. Our results carry implications for learning methods that utilize coarsening. For the particular case of spectral clustering, they imply that coarse eigenvectors can be used to derive good quality assignments even without refinement{—}this phenomenon was previously observed, but lacked formal justification.

Spectral clustering is a widely studied problem, yet its complexity is prohibitive for dynamic graphs of even modest size. We claim that it is possible to reuse information of past cluster assignments to expedite computation. Our approach builds on a recent idea of sidestepping the main bottleneck of spectral clustering, i.e., computing the graph eigenvectors, by a polynomial-based randomized sketching technique. We show that the proposed algorithm achieves clustering assignments with quality approximating that of spectral clustering and that it can yield significant complexity benefits when the graph dynamics are appropriately bounded. In our experiments, our method clusters 30k node graphs 3.9$\times$ faster in average and deviates from the correct assignment by less than 0.1%.

Research in graph signal processing (GSP) aims to develop tools for processing data defined on irregular graph domains. In this paper, we first provide an overview of core ideas in GSP and their connection to conventional digital signal processing, along with a brief historical perspective to highlight how concepts recently developed in GSP build on top of prior research in other areas. We then summarize recent advances in developing basic GSP tools, including methods for sampling, filtering, or graph learning. Next, we review progress in several application areas using GSP, including processing and analysis of sensor network data, biological data, and applications to image processing and machine learning.

Sparsity exploiting image reconstruction (SER) methods have been extensively used with total variation (TV) regularization for tomographic reconstructions. Local TV methods fail to preserve texture details and often create additional artifacts due to over-smoothing. Nonlocal TV (NLTV) methods have been proposed as a solution to this but they either lack continuous updates due to computational constraints or limit the locality to a small region. In this letter, we propose adaptive graph-based TV. The proposed method goes beyond spatial similarity between different regions of an image being reconstructed by establishing a connection between similar regions in the entire image regardless of spatial distance. As compared to NLTV, the proposed method is computationally efficient and involves updating the graph prior during every iteration making the connection between similar regions stronger. Moreover, it promotes sparsity in the wavelet and graph gradient domains. Since TV is a special case of graph TV, the proposed method can also be seen as a generalization of SER and TV methods.

Graph-based methods for signal processing have shown promise for the analysis of data exhibiting irregular structure, such as those found in social, transportation, and sensor networks. Yet, though these systems are often dynamic, state-of-the-art methods for graph signal processing ignore the time dimension. To address this shortcoming, this paper considers the statistical analysis of time-varying graph signals. We introduce a novel definition of joint (time-vertex) stationarity, which generalizes the classical definition of time stationarity and the recent definition appropriate for graphs. This gives rise to a scalable Wiener optimization framework for denoising, semi-supervised learning, or more generally inverting a linear operator, that is provably optimal. Experimental results on real weather data demonstrate that taking into account graph and time dimensions jointly can yield significant accuracy improvements in the reconstruction effort.

This work formulates a novel song recommender system as a matrix completion problem that benefits from collaborative filtering through Non-negative Matrix Factorization (NMF) and content-based filtering via total variation (TV) on graphs. The graphs encode both playlist proximity information and song similarity, using a rich combination of audio, meta-data and social features. As we demonstrate, our hybrid recommendation system is very versatile and incorporates several well-known methods while outperforming them. Particularly, we show on real-world data that our model overcomes w.r.t. two evaluation metrics the recommendation of models solely based on low-rank information, graph-based information or a combination of both.

Mining useful clusters from high dimensional data has received significant attention of the signal processing and machine learning community in the recent years. Linear and non-linear dimensionality reduction has played an important role to overcome the curse of dimensionality. However, often such methods are accompanied with problems such as high computational complexity (usually associated with the nuclear norm minimization), non-convexity (for matrix factorization methods) or susceptibility to gross corruptions in the data. In this paper we propose a convex, robust, scalable and efficient Principal Component Analysis (PCA) based method to approximate the low-rank representation of high dimensional datasets via a two-way graph regularization scheme. Compared to the exact recovery methods, our method is approximate, in that it enforces a piecewise constant assumption on the samples using a graph total variation and a piecewise smoothness assumption on the features using a graph Tikhonov regularization. Futhermore, it retrieves the low-rank representation in a time that is linear in the number of data samples. Clustering experiments on 3 benchmark datasets with different types of corruptions show that our proposed model outperforms 7 state-of-the-art dimensionality reduction models.

We build upon recent advances in graph signal processing to propose a faster spectral clustering algorithm. Indeed, classical spectral clustering is based on the computation of the first k eigenvectors of the similarity matrix' Laplacian, whose computation cost, even for sparse matrices, becomes prohibitive for large datasets. We show that we can estimate the spectral clustering distance matrix without computing these eigenvectors: by graph filtering random signals. Also, we take advantage of the stochasticity of these random vectors to estimate the number of clusters k. We compare our method to classical spectral clustering on synthetic data, and show that it reaches equal performance while being faster by a factor at least two for large datasets.

Spectral clustering has become a popular technique due to its high performance in many contexts. It comprises three main steps: create a similarity graph between N objects to cluster, compute the first k eigenvectors of its Laplacian matrix to define a feature vector for each object, and run k-means on these features to separate objects into k classes. Each of these three steps becomes computationally intensive for large N and/or k. We propose to speed up the last two steps based on recent results in the emerging field of graph signal processing: graph filtering of random signals, and random sampling of bandlimited graph signals. We prove that our method, with a gain in computation time that can reach several orders of magnitude, is in fact an approximation of spectral clustering, for which we are able to control the error. We test the performance of our method on artificial and real-world network data.

In this work, we are interested in generalizing convolutional neural networks (CNNs) from low-dimensional regular grids, where image, video and speech are represented, to high-dimensional irregular domains, such as social networks, brain connectomes or words’ embedding, represented by graphs. We present a formulation of CNNs in the context of spectral graph theory, which provides the necessary mathematical background and efficient numerical schemes to design fast localized convolutional filters on graphs. Importantly, the proposed technique offers the same linear computational complexity and constant learning complexity as classical CNNs, while being universal to any graph structure. Experiments on MNIST and 20NEWS demonstrate the ability of this novel deep learning system to learn local, stationary, and compositional features on graphs.

In this paper, we consider the problem of finding dense intrinsic correspondence between manifolds using the recently introduced functional framework. We pose the functional correspondence problem as matrix completion with manifold geometric structure and inducing functional localization with the L1norm. We discuss efficient numerical procedures for the solution of our problem. Our method compares favorably to the accuracy of state-of-the-art correspondence algorithms on non-rigid shape matching benchmarks, and is especially advantageous in settings when only scarce data is available.

The construction of a meaningful graph plays a crucial role in the emerging field of signal processing on graphs. In this paper, we address the problem of learning graph Laplacians, which is similar to learning graph topologies, such that the input data form graph signals with smooth variations on the resulting topology. We adopt a factor analysis model for the graph signals and impose a Gaussian probabilistic prior on the latent variables that control these graph signals. We show that the Gaussian prior leads to an efficient representation that favours the smoothness property of the graph signals, and propose an algorithm for learning graphs that enforce such property. Experiments demonstrate that the proposed framework can efficiently infer meaningful graph topologies from only the signal observations.

Principal Component Analysis (PCA) is the most widely used tool for linear dimensionality reduction and clustering. Still it is highly sensitive to outliers and does not scale well with respect to the number of data samples. Robust PCA solves the first issue with a sparse penalty term. The second issue can be handled with the matrix factorization model, which is however non-convex. Besides, PCA based clustering can also be enhanced by using a graph of data similarity. In this article, we introduce a new model called 'Robust PCA on Graphs' which incorporates spectral graph regularization into the Robust PCA framework. Our proposed model benefits from 1) the robustness of principal components to occlusions and missing values, 2) enhanced low-rank recovery, 3) improved clustering property due to the graph smoothness assumption on the low-rank matrix, and 4) convexity of the resulting optimization problem. Extensive experiments on 8 benchmark, 3 video and 2 artificial datasets with corruptions clearly reveal that our model outperforms 10 other state-of-the-art models in its clustering and low-rank recovery tasks.

Abstract In this paper, we propose a generalization of convolutional neural networks (CNN) to non‐Euclidean domains for the analysis of deformable shapes. Our construction is based on localized frequency analysis (a generalization of the windowed Fourier transform to manifolds) that is used to extract the local behavior of some dense intrinsic descriptor, roughly acting as an analogy to patches in images. The resulting local frequency representations are then passed through a bank of filters whose coefficient are determined by a learning procedure minimizing a task‐specific cost. Our approach generalizes several previous methods such as HKS, WKS, spectral CNN, and GPS embeddings. Experimental results show that the proposed approach allows learning class‐specific shape descriptors significantly outperforming recent state‐of‐the‐art methods on standard benchmarks.

Inspired by the recently proposed Magnetic Resonance Fingerprinting technique, we develop a principled compressed sensing framework for quantitative MRI. The three key components are: a random pulse excitation sequence following the MRF technique; a random EPI subsampling strategy and an iterative projection algorithm that imposes consistency with the Bloch equations. We show that, as long as the excitation sequence possesses an appropriate form of persistent excitation, we are able to achieve accurate recovery of the proton density, T1, T2and off-resonance maps simultaneously from a limited number of samples.

Compressed Sensing (CS) is a new acquisition-compression paradigm for low-complexity energy-aware sensing and compression. By merging both sampling and compression, CS is very promising to develop practical ultra-low power readout systems for wireless bio-signal monitoring devices, where large amounts of sensor data need to be transferred through power-hungry wireless links. Lately CS has been successfully applied for real-time energy-aware single-lead ECG compression on resource-constrained Wireless Body Sensor Network (WBSN) motes [1]. Building on our previous work, in this paper we propose a new and promising approach for joint compression of multi-lead ECG signals, where strong correlations exist between them. This situation that exhibit strong correlations, can be exploited to reduce even further amount of data to be transmitted wirelessly, thus addressing the important challenge of ultra-low-power embedded monitoring of multi-lead ECG signals.

In this work we combing two novelty in the area of Analog Information Converter based on Compressed Sensing. A new architecture, the Spread Spectrum Random Modulation PreIntegration and a new design flow, the rakeness based design of a Compressed Sensing system. We demonstrate that combining these approaches produces a strong reduction of the internal chipping frequency in the sensing coupled with a high compression ratio with respect to standard Analog to Digital Converter.

Technology scaling enables the design of low cost biosignal processing chips suited for emerging wireless body-area sensing applications. Energy consumption severely limits such applications and memories are becoming the energy bottleneck to achieve ultra-low-power operation. When aggressive voltage scaling is used, memory operation becomes unreliable due to the lack of sufficient Static Noise Margin. This paper introduces an approximate biosignal Compressed Sensing approach. We propose a digital architecture featuring a hybrid memory (6T-SRAM/SCMEM cells) designed to control perturbations on specific data structures. Combined with a statistically robust reconstruction algorithm, the system tolerates memory errors and achieves significant energy savings with low area overhead.

Local Binary Descriptors are becoming more and more popular for image matching tasks, especially when going mobile. While they are extensively studied in this context, their ability to carry enough information in order to infer the original image is seldom addressed. In this work, we leverage an inverse problem approach to show that it is possible to directly reconstruct the image content from Local Binary Descriptors. This process relies on very broad assumptions besides the knowledge of the pattern of the descriptor at hand. This generalizes previous results that required either a prior learning database or non-binarized features. Furthermore, our reconstruction scheme reveals differences in the way different Local Binary Descriptors capture and encode image information. Hence, the potential applications of our work are multiple, ranging from privacy issues caused by eavesdropping image keypoints streamed by mobile devices to the design of better descriptors through the visualization and the analysis of their geometric content.

Inspired by the recently proposed magnetic resonance fingerprinting (MRF) technique, we develop a principled compressed sensing framework for quantitative MRI. The three key components are a random pulse excitation sequence following the MRF technique, a random EPI subsampling strategy, and an iterative projection algorithm that imposes consistency with the Bloch equations. We show that, theoretically, as long as the excitation sequence possesses an appropriate form of persistent excitation, we are able to accurately recover the proton density, T1, T2, and off-resonance maps simultaneously from a limited number of samples. These results are further supported through extensive simulations using a brain phantom.

We propose a novel method to accurately reconstruct a set of images representing a single scene from a few linear multiview measurements. Each observed image is modeled as the sum of a background image and a foreground one. The background image is common to all observed images but undergoes geometric transformations, as the scene is observed from different viewpoints. In this paper, we assume that these geometric transformations are represented by a few parameters, e.g., translation, rotation, affine transformation, etc.. The foreground images differ from one observed image to another, and are used to model possible occlusions of the scene. The proposed reconstruction algorithm estimates jointly the images and the transformation parameters from the available multiview measurements. The ideal solution of this multiview imaging problem minimizes a nonconvex functional, and the reconstruction technique is an alternating descent method built to minimize this functional. The convergence of the proposed algorithm is studied, and conditions under which the sequence of estimated images and parameters converges to a critical point of the nonconvex functional are provided. Finally, the efficiency of the algorithm is demonstrated using numerical simulations for applications such as compressed sensing or superresolution.

The performance of audio source separation from underdetermined convolutive mixture assuming known mixing filters can be significantly improved by using an analysis sparse prior optimized by a reweighting ℓ1scheme and a wideband data-fidelity term, as demonstrated by a recent article. In this letter, we show that the performance can be improved even more significantly by exploiting a low-rank prior on the source spectrograms. We present a new algorithm to estimate the sources based on i) an analysis sparse prior, ii) a reweighting scheme so as to increase the sparsity, iii) a wideband data-fidelity term in a constrained form, and iv) a low-rank constraint on the source spectrograms. Evaluation on reverberant music mixtures shows that the resulting algorithm improves state-of-the-art methods by more than 2 dB of signal-to-distortion ratio.

A novel compressive sampling scheme suitable for highly scalable hardware implementation is presented. The prototype design is implemented in a 0.18μm standard CMOS technology and utilizes compressed acquisition to achieve high frame rates and maintain low power consumption. Specialized pixels, convenient for Comparator-Based Switched Capacitor readout are developed for this purpose. A custom measurement matrix generation algorithm is implemented which reduces in-pixel hardware complexity and performs measurement matrix generation in a single clock cycle. Per-column Differential Cyclic-ADCs based on the Zero-Crossing Detection (ZCD) technique are used to convert the analog image measurements. Physical IC design issues such as the required dynamic range, device noise, mismatch and non-linearity, are analyzed and their effects on compressed image acquisition are presented and discussed. The final simulation results show that the proposed 256x256 pixels architecture consumes 1.45mW at 250fps and 26.2mW at 8000fps. The proposed architecture can easily be scaled towards newer technology nodes and higher image resolutions.

Modern data processing tasks frequently involve structured data, for example signals defined on the vertex set of a weighted graph. In this paper, we address the problem of inference of mobility patterns from data defined on geographical graphs based on spatially localized events. Specifically, we propose a model-based approach where we build a signal model for each of the expected mobility patterns. We then analyze the characteristics of the signal models by studying their spectral representations using wavelets defined on graphs, which enables us to build efficient classifier in the spectral domain. Experiments on data gathered from photo-taking events in Flickr show that we can efficiently infer mobility patterns using only coarse aggregated information, which is certainly interesting in terms of privacy protection.

This paper presents a novel approach to acquire multichannel wireless intracranial neural data based on a compressive sensing scheme. The designed circuits are extremely compact and low-power which confirms the relevance of the proposed approach for multichannel high-density neural interfaces. The proposed compression model enables the acquisition system to record from a large number of channels by reducing the transmission power per channel. Our main contributions are the twofold. First, a CMOS compressive sensing system to realize multichannel intracranial neural recording is described. Second, we explain a joint sparse decoding algorithm to recover the multichannel neural data. The idea has been implemented at system as well as circuit levels. The simulation results reveal that the multichannel intracranial neural data can be acquired by compression ratios as high as four.

The effective representation of the structures in the multiview images is an important problem that arises in visual sensor networks. This paper presents a novel recovery scheme from compressive samples which exploit local and non-local correlated structures in dense multiview images. The recovery model casts into convex minimization framework which penalizes the sparse and low-rank constraints on the data. The sparsity constraint models the correlations among pixels in a single image whereas the global correlations across images are modelled with the low-rank prior. Simulation results demonstrate that our approach achieves better reconstruct quality in comparison with the state-of-the-art reconstruction schemes.

We propose a novel algorithm for source signals estimation from an underdetermined convolutive mixture assuming known mixing filters. Most of the state-of-the-art methods are dealing with anechoic or short reverberant mixture, assuming a synthesis sparse prior in the time-frequency domain and a narrowband approximation of the convolutive mixing process. In this paper, we address the source estimation of convolutive mixtures with a new algorithm based on i) an analysis sparse prior, ii) a reweighting scheme so as to increase the sparsity, iii) a wideband data-fidelity term in a constrained form. We show, through theoretical discussions and simulations, that this algorithm is particularly well suited for source separation of realistic reverberation mixtures. Particularly, the proposed algorithm outperforms state-of-the-art methods on reverberant mixtures of audio sources by more than 2 dB of signal-to-distortion ratio on the BSS Oracle dataset.

We propose and analyze a new model for hyperspectral images (HSIs) based on the assumption that the whole signal is composed of a linear combination of few sources, each of which has a specific spectral signature, and that the spatial abundance maps of these sources are themselves piecewise smooth and therefore efficiently encoded via typical sparse models. We derive new sampling schemes exploiting this assumption and give theoretical lower bounds on the number of measurements required to reconstruct HSI data and recover their source model parameters. This allows us to segment HSIs into their source abundance maps directly from compressed measurements. We also propose efficient optimization algorithms and perform extensive experimentation on synthetic and real datasets, which reveals that our approach can be used to encode HSI with far less measurements and computational effort than traditional compressive sensing methods.

We study the impact of sampling theorems on the fidelity of sparse image reconstruction on the sphere. We discuss how a reduction in the number of samples required to represent all information content of a band-limited signal acts to improve the fidelity of sparse image reconstruction, through both the dimensionality and sparsity of signals. To demonstrate this result, we consider a simple inpainting problem on the sphere and consider images sparse in the magnitude of their gradient. We develop a framework for total variation inpainting on the sphere, including fast methods to render the inpainting problem computationally feasible at high resolution. Recently a new sampling theorem on the sphere was developed, reducing the required number of samples by a factor of two for equiangular sampling schemes. Through numerical simulations, we verify the enhanced fidelity of sparse image reconstruction due to the more efficient sampling of the sphere provided by the new sampling theorem.

A large number of vision applications rely on matching keypoints across images. The last decade featured an arms-race towards faster and more robust keypoints and association algorithms: Scale Invariant Feature Transform (SIFT)[17], Speed-up Robust Feature (SURF)[4], and more recently Binary Robust Invariant Scalable Keypoints (BRISK)[I6] to name a few. These days, the deployment of vision algorithms on smart phones and embedded devices with low memory and computation complexity has even upped the ante: the goal is to make descriptors faster to compute, more compact while remaining robust to scale, rotation and noise. To best address the current requirements, we propose a novel keypoint descriptor inspired by the human visual system and more precisely the retina, coined Fast Retina Keypoint (FREAK). A cascade of binary strings is computed by efficiently comparing image intensities over a retinal sampling pattern. Our experiments show that FREAKs are in general faster to compute with lower memory load and also more robust than SIFT, SURF or BRISK. They are thus competitive alternatives to existing keypoints in particular for embedded applications.

We propose a novel approach to reconstruct Hyperspectral images from very few number of noisy compressive measurements. Our reconstruction approach is based on a convex minimization which penalizes both the nuclear norm and the ℓ2,1mixed-norm of the data matrix. Thus, the solution tends to have a simultaneous low-rank and joint-sparse structure. We explain how these two assumptions fit Hyperspectral data, and by severals simulations we show that our proposed reconstruction scheme significantly enhances the state-of-the-art tradeoffs between the reconstruction error and the required number of CS measurements.

This paper presents a novel approach to capture light field in camera arrays based on the compressive sensing framework. Light fields are captured by a linear array of cameras with overlapping field of view. In this work, we design a redundant dictionary to exploit cross-cameras correlated structures to sparsely represent cameras image. Our main contributions are threefold. First, we exploit the correlations between the set of views by making use of a specially designed redundant dictionary. We show experimentally that the projection of complex scenes onto this dictionary yields very sparse coefficients. Second, we propose an efficient compressive encoding scheme based on the random convolution framework [1]. Finally, we develop a joint sparse recovery algorithm for decoding the compressed measurements and show a marked improvement over independent decoding of CS measurements.

Vision-based background subtraction algorithms model the intensity variation across time to classify a pixel as foreground. Unfortunately, such algorithms are sensitive to appearance changes of the background such as sudden changes of illumination or when videos are projected in the background. In this work, we propose an algorithm to extract foreground silhouettes without modeling the intensity variation across time. Using a camera pair, the stereo mismatch is processed to produce a dense disparity based on a Total Variation (TV) framework. Experimental results show that with sudden changes of background appearance, our proposed TV disparity-based extraction outperforms intensity-based algorithms and existing stereo-based approaches based on temporal depth variation and stereo mismatch.

We present a novel plenoptic sampling scheme that permits an efficient representation of the full light ray field in a space limited by a convex closed surface. We show that a convenient way to sample the light ray field around an observer consists in using a discrete set of perspective imagers with overlapping field-of-views that are distributed on a closed convex surface and looking along the normal to the surface. Taking inspiration from the vision system of flying insects, we choose to constrain the cameras on a sphere of finite radius. Building on spectral analysis we propose a sampling scheme that permits to reconstruct the spherical light field without aliasing. We validate our framework through experiments in a synthetic environment and we show that our constructive sampling scheme permits to effectively reconstruct the light field without artifacts.

In this paper we propose a novel and efficient model for compressed sensing of hyperspectral images. A large-size hyperspectral image can be subsampled by retaining only 3% of its original size, yet robustly recovered using the new approach we present here. Our reconstruction approach is based on minimizing a convex functional which penalizes both the trace norm and the TV norm of the data matrix. Thus, the solution tends to have a simultaneous low-rank and piecewise smooth structure: the two important priors explaining the underlying correlation structure of such data. Through simulations we will show our approach significantly enhances the conventional compression rate-distortion tradeoffs. In particular, in the strong undersampling regimes our method outperforms the standard TV denoising image recovery scheme by more than 17dB in the reconstruction MSE.

This paper introduces a novel algorithm for sparse approximation in redundant dictionaries called the M-term pursuit (MTP). This algorithm decomposes a signal into a linear combination of atoms that are selected in order to represent the main signal components. The MTP algorithm provides an adaptive representation for signals in any complete dictionary. The basic idea behind the MTP is to partition the dictionary into L quasi-disjoint subdictionaries. A k-term signal approximation is then iteratively computed, where each iteration leads to the selection of M ≤ L atoms based on thresholding. The MTP algorithm is shown to achieve competitive performance with the matching pursuit (MP) algorithm that greedily selects atoms one by one. This is due to efficient partitioning of the dictionary. At the same time, the computational complexity is dramatically reduced compared to MP due to the batch selection of atoms. We finally illustrate the performance of MTP in image and video compression applications, where we show that the suboptimal atom selection of MTP is largely compensated by the reduction in complexity compared with MP.

We propose a novel compressed sensing technique to accelerate the magnetic resonance imaging (MRI) acquisition process. The method, coined spread spectrum MRI or simply s(2)MRI, consists of premodulating the signal of interest by a linear chirp before random k-space under-sampling, and then reconstructing the signal with nonlinear algorithms that promote sparsity. The effectiveness of the procedure is theoretically underpinned by the optimization of the coherence between the sparsity and sensing bases. The proposed technique is thoroughly studied by means of numerical simulations, as well as phantom and in vivo experiments on a 7T scanner. Our results suggest that s(2)MRI performs better than state-of-the-art variable density k-space under-sampling approaches.

We propose a novel method to automatically detect and extract the video modality of the sound sources that are present in a scene. For this purpose, we first assess the synchrony between the moving objects captured with a video camera and the sounds recorded by a microphone. Next, video regions presenting a high coherence with the soundtrack are automatically labelled as being part of the source. This represents the starting point for an innovative video segmentation approach, whose objective is to extract the complete audiovisual object. The proposed graph-cut segmentation procedure includes an audio-visual term that links together pixels in regions with high audio-video coherence. Our approach is demonstrated on challenging sequences presenting non-stationary sound sources and distracting moving objects.

Mobile phone data provides rich dynamic information on human activities in social network analysis. In this paper, we represent data from two different modalities as a graph and functions defined on the vertex set of the graph. We propose a regularization framework for the joint utilization of these two modalities of data, which enables us to model evolution of social network information and efficiently classify relationships among mobile phone users. Simulations based on real world data demonstrate the potential application of our model in dynamic scenarios, and present competitive results to baseline methods for combining multimodal data in the learning and clustering communities.

Super-resolution is the task of creating an high resolution image from a low resolution input sequence. To overcome the difficulties of fine image registration, several methods have been proposed exploiting the non-local intuition, i.e. any datapoint can contribute to the final result if it is relevant. These algorithms however limit in practice the search region for relevant points in order to lower the corresponding computational cost. Furthermore, they define the non-local relations in the high resolution space, where the true images are unknown. In this work, we introduce the use of spectral hashing to efficiently compute fully non-local neighbors. We also restate the superresolution functional using fixed weights in the low resolution space, allowing us to use resolution schemes that avoid many artifacts.

Vision is a natural tool for human-computer interaction, since it provides visual feedback to the user and mimics some human behaviors. It requires however the fast and robust computation of motion primitives, which remains a difficult problem. In this work, we propose to apply some recent mathematical results about convex optimization to the TV-L1optical flow problem. At the cost of a small smoothing of the Total Variation (TV), the convergence speed of the numerical scheme is improved, leading to earlier termination. Furthermore, we successfully implement our algorithm on GPU for realtime performance using the OpenCL framework. We demonstrate the potential of our optical flow by using it as primary sensor in a remotely controlled image browsing software.

Wireless body sensor networks (WBSN) hold the promise to enable next-generation patient-centric tele-cardiology systems. A WBSN-enabled electrocardiogram (ECG) monitor consists of wearable, miniaturized and wireless sensors able to measure and wirelessly report cardiac signals to a WBSN coordinator, which is responsible for reporting them to the tele-health provider. However, state-of-the-art WBSN-enabled ECG monitors still fall short of the required functionality, miniaturization and energy efficiency. Among others, energy efficiency can be significantly improved through embedded ECG compression, which reduces airtime over energy-hungry wireless links. In this paper, we quantify the potential of the emerging compressed sensing (CS) signal acquisition/compression paradigm for low complexity energy-aware ECG compression on the state-of-the-art Shimmer™ WBSN mote. Interestingly, our results show that CS represents a competitive alternative to state-of-the-art digital wavelet transform (DWT)-based ECG compression solutions in terms of overall energy efficiency and Shimmer™ node lifetime extension.

Incoherence between sparsity basis and sensing basis is an essential concept for compressive sampling. In this context, we advocate a coherence-driven optimization procedure for variable density sampling. The associated minimization problem is solved by use of convex optimization algorithms. We also propose a refinement of our technique when prior information is available on the signal support in the sparsity basis. The effectiveness of the method is confirmed by numerical experiments. Our results also provide a theoretical underpinning to state-of-the-art variable density Fourier sampling procedures used in MRI.

In this paper, we address the issues of analyzing and classifying JPEG 2000 code-streams. An original representation, called integral volume, is first proposed to compute local image features progressively from the compressed code-stream, on any spatial image area, regardless of the code-blocks borders. Then, a JPEG 2000 classifier is presented that uses integral volumes to learn an ensemble of randomized trees. Several classification tasks are performed on various JPEG 2000 image databases and results are in the same range as the ones obtained in the literature with noncompressed versions of these databases. Finally, a cascade of such classifiers is considered, in order to specifically address the image retrieval issue, i.e., bi-class problems characterized by a highly skewed distribution. An efficient way to learn and optimize such cascade is proposed. We show that staying in a JPEG 2000 framework, initially seen as a constraint to avoid heavy decoding operations, is actually an advantage as it can benefit from the multiresolution and multilayer paradigms inherently present in this compression standard. In particular, unlike other existing cascaded retrieval systems, the features used along our cascade are increasingly discriminant and lead therefore to a better tradeoff of complexity versus performance.

We propose a novel non-linear video diffusion approach which is able to focus on parts of a video sequence that are relevant for applications in audio-visual analysis. The diffusion process is controlled by a diffusion coefficient based on an estimate of the synchrony between video motion and audio energy at each point of the video volume. Thus, regions whose motion is not coherent with the soundtrack are iteratively smoothed. The discretization of the proposed continuous diffusion formulation is carefully studied and its stability demonstrated. Our approach is tested in challenging situations involving sequence degradation and distracting video motion. Results show that in all cases our method is able to keep the focus of attention on the sound sources.

We consider images probed through incomplete and noisy Fourier coverages, both in the context of radio interferometry (RI) and of magnetic resonance imaging (MRI). We show that the quality of signal reconstruction can be significantly enhanced by the introduction of a linear chirp modulation, which induces a spread spectrum phenomenon.

We present a new and computationally efficient scheme for classifying signals into a fixed number of known classes. We model classes as subspaces in which the corresponding data is well represented by a dictionary of features. In order to ensure low misclassification, the subspaces should be incoherent so that features of a given class cannot represent efficiently signals from another. We propose a simple iterative strategy to learn dictionaries which are are the same time good for approximating within a class and also discriminant. Preliminary tests on a standard face images database show competitive results.

This paper addresses the reconstruction of high resolution omnidirectional images from a low resolution video acquired by an omnidirectional camera moving in a static scene. In order to exploit the additional information provided by the side images in the video sequence, the ego-motion of the camera must be accurately estimated in a first step. The reconstruction can then be modeled as a plenoptic sampling problem that has to encompass the change of viewpoint between each position of the omnidirectional sensor and the specific discretization of the real scene observed from each position. We formulate this problem as an ill-posed inverse problem that incorporates a regularization term based on a Total Variation (TV) prior. A graph variational formulation is used in order to ease the representation of omnidirectional data and to adapt the discretization of differential operators to the omnidirectional geometry. Experimental results on synthetic images demonstrate the relevance of this approach and its superiority compared to standard super-resolution using a single image.

We propose a new content-aware image resizing scheme, Stream Carving, which is based on the well-known seam carving method. Our algorithm may introduce larger seams in the retargeted image, i.e. seams with a width larger than one pixel, that we call “streams”. The resulting holes are then recovered using an inpainting method. Our retargeting algorithm is also more related to human perception by exploiting an adaptive importance map that merges several features like gradient magnitude, saliency, face, edge and straight line detection. Our approach induces an increase in the quality of the retargeted image when compared to the original seam carving method and provides similar or better results than other actual image retargeting techniques.

A novel framework for image inpainting is proposed, relying on graph-based diffusion processes. Depending on the construction of the graph, both flow-based and exemplar-based inpainting methods can be implemented by the same equations, hence providing a unique framework for geometry and texture-based approaches to inpainting. Furthermore, the use of a variational framework allows to overcome the usual sensitivity of exemplar-based methods to the heuristic issues by providing an evolution criterion. The use of graphs also makes our framework more flexible than former nonlocal variational formulations, allowing for example to mix spatial and non-local constraints and to use a data term to provide smoother blending between the initial image and the result.

A CMOS imager is presented which has the ability to perform localized compressive sensing on-chip. In-pixel convolutions of the sensed image with measurement matrices are computed in real time, and a proposed programmable two-dimensional scrambling technique guarantees the randomness of the coefficients used in successive observation. A power and area-efficient implementation architecture is presented making use of a single ADC. A 256×256 imager has been developed as a test vehicle in a 0.18μm CIS technology. Using an 11-bit ADC, a SNR of 18.6dB with a compression factor of 3.3 is achieved after reconstruction. The total power consumption of the imager is simulated at 76.7mW from a 1.8V supply voltage.

In this paper, we propose a novel method which is able to detect and separate audiovisual sources present in a scene. Our method exploits the correlation between the video signal captured with a camera and a synchronously recorded one-microphone audio track. In a first stage, audio and video modalities are decomposed into relevant basic structures using redundant representations. Next, synchrony between relevant events in audio and video modalities is quantified. Based on this co-occurrence measure, audiovisual sources are counted and located in the image using a robust clustering algorithm that groups video structures exhibiting strong correlations with the audio. Next periods where each source is active alone are determined and used to buildspectralGaussian mixture models (GMMs) characterizing the sources acoustic behavior. Finally, these models are used to separate the audio signal in periods during which several sources are mixed. The proposed approach has been extensively tested on synthetic and natural sequences composed of speakers and music instruments. Results show that the proposed method is able to successfully detect, localize, separate, and reconstruct present audiovisual sources.

We present a CMOS imager with built-in capability to perform Compressed Sensing coding by Random Convolution. It is achieved by a shift register set in a pseudo-random configuration. It acts as a convolutive filter on the imager focal plane, the current issued from each CMOS pixel undergoing a pseudo-random redirection controlled by each component of the filter sequence. A pseudo-random triggering of the ADC reading is finally applied to complete the acquisition model. The feasibility of the imager and its robustness under noise and non-linearities have been confirmed by computer simulations, as well as the reconstruction tools supporting the Compressed Sensing theory.

We propose a new method for ventricular cancellation and atrial modelling in the ECG of patients suffering from atrial fibrillation. Our method is based on dictionary learning. It extends both the average beat subtraction and the sparse source separation approaches. Experiments on synthetic data show that this method can almost completely suppress the ventricular activity, but it generates some artifacts. Contrary to other ventricular cancellations methods, our approach also learns a model for the atrial activity.

We propose a variant of orthogonal matching pursuit (OMP), called LoCOMP, for scalable sparse signal approximation. The algorithm is designed for shift-invariant signal dictionaries with localized atoms, such as time-frequency dictionaries, and achieves approximation performance comparable to OMP at a computational cost similar to matching pursuit. Numerical experiments with a large audio signal show that, compared to OMP and gradient pursuit, the proposed algorithm runs in over 500 less time while leaving the approximation error almost unchanged.

In this paper we consider the problem of sampling far below the Nyquist rate signals that are sparse linear superpositions of shifts of a known, potentially wide-band, pulse. This signal model is key for applications such as Ultra Wide Band (UWB) communications or neural signal processing. Following the recently proposed Compressed Sensing methodology, we study several acquisition strategies and show that the approximations recovered via lscr1minimization are greatly enhanced if one uses Spread Spectrum modulation prior to applying random Fourier measurements. We complement our experiments with a discussion of possible hardware implementation of our technique.

This paper deals with the problem of efficiently computing the optical flow of image sequences acquired by omnidirectional (nearly full field of view) cameras. We formulate the problem in the natural spherical geometry associated with these devices and extend a recent TV-L1 variational formulation for computing the optical flow. The discretization of differential operators occurring in this formulation turns out to be an extremely sensitive point, in particular for the TV part of our algorithm. We show that these difficulties can be very efficiently overcome using a graph-based formulation of TV denoising, which we solve by introducing a graph version of Chambolle's algorithm. A slight modification of the original framework allows us to solve the depth from motion problem using the same techniques. In both cases, our graph-based algorithms provide computationally efficient solutions and significantly outperform naive implementations based on direct discretization of the operators, or on neglecting the influence of geometry.

This paper addresses the problem of mapping images between different vision sensors. Such a mapping could be modeled as a sampling problem that has to encompass the change of geometry between the two sensors and the specific discretization of the real scene observed by the two different imaging systems. We formulate the problem in a general framework that can be cast as a minimization regularized problem with a linear operator, that applies to any image geometry. We then focus on the particular problem of the generation of planar images from omnidirectional images, in any viewing direction and for any size and resolution. In this regularized approach, the fidelity term is expressed in the original omnicam geometry and the regularization is based on Total Variation (TV) solved here with proximal methods. Experimental results demonstrate the superiority of this approach with respect to alternative schemes based on linear interpolation or TV in-painting.

In recent years, works on geometric multidimensional signal representations have established a close relation with signal expansions on redundant dictionaries. For this purpose, matching pursuits (MP) have shown to be an interesting tool. Recently, most important limitations of MP have been underlined, and alternative algorithms like weighted-MP have been proposed. This work explores the use of weighted-MP as a new framework for motion-adaptive geometric video approximations. We study a novel algorithm to decompose video sequences in terms of few, salient video components that jointly represent the geometric and motion content of a scene. Experimental coding results on highly geometric content reflect how the proposed paradigm exploits spatio-temporal video geometry. Two-dimensional weighted-MP improves the representation compared to those based on 2-D MP. Furthermore, the extracted video components represent relevant visual structures with high saliency. In an example application, such components are effectively used as video descriptors for the joint audio-video analysis of multimedia sequences.

A novel model is presented to learn bimodally informative structures from audio-visual signals. The signal is represented as a sparse sum of audio-visual kernels. Each kernel is a bimodal function consisting of synchronous snippets of an audio waveform and a spatio-temporal visual basis function. To represent an audio-visual signal, the kernels can be positioned independently and arbitrarily in space and time. The proposed algorithm uses unsupervised learning to form dictionaries of bimodal kernels from audio-visual material. The basis functions that emerge during learning capture salient audio-visual data structures. In addition, it is demonstrated that the learned dictionary can be used to locate sources of sound in the movie frame. Specifically, in sequences containing two speakers, the algorithm can robustly localize a speaker even in the presence of severe acoustic and visual distracters.

In this work we present a method to perform a complete audiovisual source separation without need of previous information. This method is based on the assumption that sounds are caused by moving structures. Thus, an efficient representation of audio and video sequences allows to build relationships between synchronous structures on both modalities. A robust clustering algorithm groups video structures exhibiting strong correlations with the audio so that sources are counted and located in the image. Using such information and exploiting audio-video correlation, the audio sources activity is determined. Next, spectral Gaussian Mixture Models (GMMs) are learnt in time slots with only one source active so that it is possible to separate them in case of an audio mixture. Audio source separation performances are rigorously evaluated, clearly showing that the proposed algorithm performs efficiently and robustly.

This paper analyzes the performance of the simple thresholding algorithm for sparse signal representations. In particular, in order to be more realistic we introduce a new probabilistic signal model which assumes randomness for both the amplitude and also the location of nonzero entries. Based on this model we show that thresholding in average can correctly recover signals for much higher sparsity levels than was previously reported. The bounds we obtain in this paper are based on a new concept of average dictionary coherence and are shown to be much sharper than in former works [1,2].

In this paper, we focus on the use of random projections as a dimensionality reduction tool for sampled manifolds in high- dimensional Euclidean spaces. We show that geodesic paths approximations from nearest neighbors Euclidean distances are well-preserved by Gaussian projections and we characterize the distribution of geodesic lengths in the reduced dimensional point cloud. A stylized application to a real-world data set of human faces is presented to validate our theoretical findings.

This paper extends the concept of compressed sensing to signals that are not sparse in an orthonormal basis but rather in a redundant dictionary. It is shown that a matrix, which is a composition of a random matrix of certain type and a deterministic dictionary, has small restricted isometry constants. Thus, signals that are sparse with respect to the dictionary can be recovered via basis pursuit (BP) from a small number of random measurements. Further, thresholding is investigated as recovery algorithm for compressed sensing, and conditions are provided that guarantee reconstruction with high probability. The different schemes are compared by numerical experiments.

This paper introduces p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latter results in much weaker conditions on the dictionary. Numerical simulations confirm our theoretical findings and show that p-thresholding is an interesting low complexity alternative to simultaneous greedy or convex relaxation algorithms for processing sparse multichannel signals with balanced coefficients.

We present a general framework and an efficient algorithm for tracking relevant video structures. The structures to be tracked are implicitly defined by a matching pursuit procedure that extracts and ranks the most important image contours. Based on the ranking, the contours are automatically selected to initialize a particle filtering tracker. The proposed algorithm deals with salient video entities whose behavior has an intuitive meaning, related to the physics of the signal. Moreover, as the interactions between such structures are easily defined, the inference of higher level signal configurations can be made intuitive. The proposed algorithm improves the performance of existing video structures trackers, while reducing the computational complexity. The algorithm is demonstrated on audio-visual source localization.

In this work we present a method to jointly separate active audio and visual structures on a given mixture. Blind audiovisual source separation is achieved exploiting the coherence between a video signal and a one-microphone audio track. The efficient representation of audio and video sequences allows to build relationships between correlated structures on both modalities. Video structures exhibiting strong correlations with the audio signal and that are spatially close are grouped using a robust clustering algorithm that can count and localize audiovisual sources. Using such information and exploiting audio-video correlation, audio sources are also localized and separated. To the best of our knowledge this is the first blind audiovisual source separation algorithm conceived to deal with a video sequence and the correspondingmonoaudio signal.

In this letter, we show that with high probability, the thresholding algorithm can recover signals that are sparse in a redundant dictionary as long as the 2-Babel function is growing slowly. This implies that it can succeed for sparsity levels up to the order of the ambient dimension. The theoretical bounds are illustrated with numerical simulations. As an application of the theory, sensing dictionaries for optimal average performance are characterized, and their performance is tested numerically.

A new generation of optical devices that generate images covering a larger part of the field of view than conventional cameras, namely catadioptric cameras, is slowly emerging. These omnidirectional images will most probably deeply impact computer vision in the forthcoming years, provided that the necessary algorithmic background stands strong. In this paper, we propose a general framework that helps define various computer vision primitives. We show that geometry, which plays a central role in the formation of omnidirectional images, must be carefully taken into account while performing such simple tasks as smoothing or edge detection. Partial differential equations (PDEs) offer a very versatile tool that is well suited to cope with geometrical constraints. We derive new energy functionals and PDEs for segmenting images obtained from catadioptric cameras and show that they can be implemented robustly using classical finite difference schemes. Various experimental results illustrate the potential of these new methods on both synthetic and natural images.

Real-world phenomena involve complex interactions between multiple signal modalities. As a consequence, humans are used to integrate at each instant perceptions from all their senses in order to enrich their understanding of the surrounding world. This paradigm can be also extremely useful in many signal processing and computer vision problems involving mutually related signals. The simultaneous processing of multimodal data can, in fact, reveal information that is otherwise hidden when considering the signals independently. However, in natural multimodal signals, the statistical dependencies between modalities are in general not obvious. Learning fundamental multimodal patterns could offer deep insight into the structure of such signals. In this paper, we present a novel model of multimodal signals based on their sparse decomposition over a dictionary of multimodal structures. An algorithm for iteratively learning multimodal generating functions that can be shifted at all positions in the signal is proposed, as well. The learning is defined in such a way that it can be accomplished by iteratively solving a generalized eigenvector problem, which makes the algorithm fast, flexible, and free of user-defined parameters. The proposed algorithm is applied to audiovisual sequences and it is able to discover underlying structures in the data. The detection of such audio-video patterns in audiovisual clips allows to effectively localize the sound source on the video in presence of substantial acoustic and visual distractors, outperforming state-of-the-art audiovisual localization algorithms.

This paper explores a novel approach for ventricular and atrial activities estimation in electrocardiogram (ECG) signals, based on sparse source separation. Sparse decompositions of ECG over signal-adapted multi-component dictionaries can lead to natural separation of its components. In this work, dictionaries of functions adapted to ventricular and atrial activities are respectively defined. Then, the weighted orthogonal matching pursuit algorithm is used to unmix the two components of ECG signals. Despite the simplicity of the approach, results are very promising, showing the capacity of the algorithm to generate realistic estimations of atrial and ventricular activities.

The performance of approximation using redundant expansions rely on having dictionaries adapted to the signals. In natural high-dimensional data, the statistical dependencies are, most of the time, not obvious. Learning fundamental patterns is an alternative to analytical design of bases and is nowadays a popular problem in the field of approximation theory. In many situations, the basis elements are shift invariant, thus the learning should try to find the best matching filters. We present a new algorithm for iteratively learning generating functions that can be shifted at all positions in the signal to generate a highly redundant dictionary

This paper addresses the problem of sensing or recovering a signal s, captured by distributed low-complexity sensors. Each sensor observes a noisy version of the signal of interest, and independently forms an approximant of its observation. This approximant is sent to a central decoder that tries to recover the input signal by combining the multiple sensor outputs. We propose to use redundant dictionaries, and thresholding in the sensor nodes, in order to form sparse approximants of the noisy observations, with low computational complexity. We first show that the noise can actually be beneficial in the recovery of the correct components of the signal s, since it can advantageously perturb the naive thresholding scheme. Then we illustrate the benefit of multiple observations with uncorrelated noise. By careful reconstruction with a projection onto convex sets (POCS) strategy, each additional measurement actually helps to recover more and more components of the original signal, since it tends to isolate the common part in all observations. Experimental results demonstrate the interesting recovery performance of our distributed sensing system. They show that a few observations, represented by a small number of components, are able to provide a good approximation of the signal, even in very noisy conditions

This paper presents a highly flexible video coding scheme, based on the use of a redundant dictionary of spatio-temporal three-dimensional (3-D) functions. Directionality and anisotropic scaling are key ingredients to the spatial components, which form a rich collection of two-dimensional (2-D) visual primitives. The temporal component is tuned to capture most of the energy in the temporal signal evolution, along motion trajectories in the video sequence. The video coding scheme (MP3D) first computes motion trajectories that are eventually entropy coded and sent as side information to the decoder. It then applies a spatio-temporal decomposition along motion trajectories, using an adaptive approximation algorithm based on matching pursuit (MP). Quantized coefficients and basis function parameters are entropy-coded in a embedded stream that is constructed to respect multiple rate constraints. The geometric properties of the 2-D primitive dictionary allow for flexible spatial resolution adaptation, so that the flexible MP3D stream enables decoding at different spatio-temporal resolutions, and multiple rates. The MP3D scheme is shown to provide rate-distortion performance that are comparable with state-of-the-art schemes, such as H.264, MPEG-4, at low and medium bit rate. However, the use of a redundant dictionary is penalizing at high coding rate, which makes the MP3D algorithm mostly interesting for low rate applications, or as a flexible base layer in hierarchical coding schemes.

This paper presents a progressive coding scheme for 3-D objects, based on overcomplete signal expansions on the 2-D sphere. Due to increased freedom in the basis construction, redundant expansions have shown interesting approximation properties in the decomposition of signals with multidimensional singularities organized along embedded submanifolds. We propose to map simple 3-D models on 2-D spheres and then to decompose the signal over a redundant dictionary of oriented and anisotropic atoms living on the sphere. The signal expansion is computed iteratively with a matching pursuit algorithm, which greedily selects the most prominent components of the 3-D model. The decomposition therefore inherently represents a progressive stream of atoms, which is advantageously used in the design of scalable representations. An encoder is proposed that compresses the stream of atoms by adaptive coefficient quantization and entropy coding of atom indexes. Experimental results show that the novel coding strategy outperforms state-of-the-art progressive coders in terms of distortion, mostly at low bit rates. Furthermore, since the dictionary is built on structured atoms, the proposed representation simultaneously offers an increased flexibility for easy stream manipulations. We finally illustrate that advantage in the design of a view-dependent transmission scheme

New breakthroughs in image coding possibly lie in signal decomposition through nonseparable basis functions that can efficiently capture edge characteristics, present in natural images. The work proposed in this paper provides an adaptive way of representing images as a sum of two-dimensional features. It presents a low bit-rate image coding method based on a matching pursuit (MP) expansion, over a dictionary built on anisotropic refinement and rotation of contour-like atoms. This method is shown to provide, at low bit rates, results comparable to the state of the art in image compression, represented here by JPEG2000 and SPIHT, with generally a better visual quality in the MP scheme. The coding artifacts are less annoying than the ringing introduced by wavelets at very low bit rate, due to the smoothing performed by the basis functions used in the MP algorithm. In addition to good compression performances at low bit rates, the new coder has the advantage of producing highly flexible streams. They can easily be decoded at any spatial resolution, different from the original image, and the bitstream can be truncated at any point to match diverse bandwidth requirements. The spatial adaptivity is shown to be more flexible and less complex than transcoding operations generally applied to state of the art codec bitstreams. Due to both its ability for capturing the most important parts of multidimensional signals, and a flexible stream structure, the image coder proposed in this paper represents an interesting solution for low to medium rate image coding in visual communication applications.

The purpose of this correspondence is to extend results by Villemoes and Temlyakov about exponential convergence of Matching Pursuit (MP) with some structured dictionaries for "simple" functions in finite or infinite dimension. The results are based on an extension of Tropp's results about Orthogonal Matching Pursuit (OMP) in finite dimension, with the observation that it does not only work for OMP but also for MP. The main contribution is a detailed analysis of the approximation and stability properties of MP with quasi-incoherent dictionaries, and a bound on the number of steps sufficient to reach an error no larger than a penalization factor times the best m-term approximation error.

Summary form only given. The paper presents a low rate progressive 3D mesh compression scheme for simple, genus-zero 3D objects. The proposed scheme is based on signal representation using redundant expansions on the 2D-sphere. First, generic input data is re-sampled as a function on the 2D-sphere, and the signal value for each point on the regular grid is obtained by performing nearest neighbor interpolation within four points from the initial 3D model. The model representation is then constructed using a matching pursuit algorithm, with an over-complete dictionary of atoms, defined on a sphere. In order to capture the particular characteristics of the 3D models efficiently, we propose a dictionary construction based on two generating functions, a Gaussian to capture low-frequency components, and a modified combination of a Gaussian and its second derivative to capture high-frequency components of the input signal. Compared to state-of-the-art encoders, our method has been shown to offer very good compression efficiency, but the performance is limited by the resampling step that maps the input model on the 2D-sphere. Matching pursuit has, however, the advantage of providing an intrinsically progressive scheme, that is also very flexible.

We address the problem of coding video signals in the presence of correlated video side information. The correlated video signals may originate from cameras that monitor the same scene from different view points. We utilize motion-compensated temporal wavelet transforms to decorrelate the video signals in the temporal direction. One camera signal provides the side information to improve the coding of the second camera signal. The side information is utilized in the transform domain after disparity compensation in the image domain. Given the correlation of the video side information, we investigate the bit rate reduction for the video coding scheme. Interestingly, the efficiency of multi-view side information is dependent on the level of temporal decorrelation: For a given correlation-SNR of the side information, bit rate savings due to side information decrease with improved temporal decorrelation.

Approximating a signal or an image with a sparse linear expansion from an overcomplete dictionary of atoms is an extremely useful tool to solve many signal processing problems. Finding the sparsest approximation of a signal from an arbitrary dictionary is an NP-hard problem. Despite this, several algorithms have been proposed that provide sub-optimal solutions. However, it is generally difficult to know how close the computed solution is to being "optimal", and whether another algorithm could provide a better result. In this paper we provide a simple test to check whether the output of a sparse approximation algorithm is nearly optimal, in the sense that no significantly different linear expansion from the dictionary can provide both a smaller approximation error and a better sparsity. As a byproduct of our theorems, we obtain results on the identifiability of sparse overcomplete models in the presence of noise, for a fairly large class of sparse priors.

This paper discusses an improved pyramid for spatially scalable video coding. We introduce additional update steps in the analysis and the synthesis of the Laplacian pyramid. Our pyramid is able to control efficiently the quantization noise energy in the reconstruction. Hence, it provides improved coding performance when compared to the standard Laplacian pyramid. Moreover, our pyramid does not require biorthogonal filters as they should be used for the frame reconstruction of the Laplacian pyramid. Therefore, low-pass filters can be chosen that suppress aliasing in the low-resolution images efficiently and, hence, permit efficient motion compensation. The experimental results demonstrate coding gains of up to 1 dB for both images and image sequences when compared to the standard Laplacian pyramid.

In this work we explore the potentialities of a framework for the representation of audio-visual signals using decompositions on overcomplete dictionaries. Redundant decompositions may describe audio-visual sequences in a concise fashion, preserving good representation properties thanks to the use of redundant, well designed, dictionaries. We expect that this helps us overcome two typical problems of multimodal fusion algorithms. On one hand, classical representation techniques, like pixel-based measures (for the video) or Fourier-like transforms (for the audio), take into account only marginally the physics of the problem. On the other hand, the input signals have large dimensionality. The results we obtain by making use of sparse decompositions of audio-visual signals over redundant codebooks are encouraging and show the potentialities of the proposed approach to multimodal signal representation.

This paper introduces a sparse signal representation algorithm in redundant dictionaries, called the M-term pursuit (MTP), with an application to image representation and scalable coding. The MTP algorithm belongs to the framework of the matching pursuit (MP) (S. Mallat and Z. Zhang, 1993); it expands the image into a linear combination of atoms, selected from a large collection of spatial atoms. The MTP relies on the concept of dictionary partitioning, i.e., as splitting the dictionary into L disjoint sub-dictionaries, each carrying some specific information. Then, it iteratively finds a K-term approximation, by selecting M atoms at a time, where M /spl les/ L, followed by an orthogonal projection. The approximation performances of the MTP algorithm have been shown to yield comparable results with those of the matching pursuit. However, it presents the advantage of a reduced computational complexity. For progressive image compression, an embedded quantization and coding step is applied on the series of obtained atoms based on the subset approach (A. Rahomoune, et al, 2004); to generate a flexible bitstream. The performances of the MTP image coder are finally shown to compare favorably against those of the state-of-the-art JPEG-2000 scheme, in terms of rate-distortion characteristics.

This work addresses the coding of 3-dimensional scenes, as captured by distributed vision sensors with catadioptric cameras. Spherical images allow for avoiding distortion due to the common euclidian assumption in the representation of the plenoptic function. We consider here low complexity encoding of the sensor outputs, in a framework where the cameras could be placed anywhere in the scene, and where the sensors do not communicate to each other. Since multiple spherical images of the same scene most probably provide a redundant representation, we propose to have different compression ratios for different cameras, in order to reduce the overhead of information. The decoder performs a joint decoding of the multiples images, by motion estimation, and joint refinement by consistent inverse quantization. It is finally shown that, even in the absence of any information about the scene or the position of the cameras, the proposed scheme offers improved performance with respect to an independent encoding of the spherical images, especially at low coding rate

The paper describes a novel video coding scheme based on a three-dimensional matching pursuit algorithm. In addition to good compression performance at low bit rates, the proposed coder allows for flexible spatial, temporal and rate scalability thanks to its progressive coding structure. The matching pursuit algorithm generates a sparse decomposition of a video sequence in a series of spatio-temporal atoms, taken from an overcomplete dictionary of three-dimensional basis functions. The dictionary is generated by shifting, scaling and rotating two different mother atoms in order to cover the whole frequency cube. An embedded stream is then produced from the series of atoms. They are first distributed into sets through the set-partitioned position map algorithm (SPPM) to form the index-map, inspired from bit plane encoding. Scalar quantization is then applied to the coefficients which are finally arithmetic coded. A complete MP3D codec has been implemented, and performances are shown to compare favorably to other scalable coders like MPEG-4 FGS and SPIHT-3D. In addition, the MP3D streams offer an incomparable flexibility for multiresolution streaming or adaptive decoding.

The paper presents a new scalable and highly flexible color image coder based on a matching pursuit expansion. The matching pursuit algorithm provides an intrinsically progressive stream and the proposed coder allows us to reconstruct color information from the first bit received. In order to capture edges in natural images efficiently, the dictionary of atoms is built by translation, rotation and anisotropic refinement of a wavelet-like mother function. This dictionary is moreover invariant under shifts and isotropic scaling, thus leading to very simple spatial resizing operations. This flexibility and adaptivity of the MP coder makes it appropriate for asymmetric applications with heterogeneous end user terminals.

To be efficient, data protection algorithms should generally exploit the properties of the media information in the transform domain. In this paper, we will advocate the use of nonlinear image approximations using highly redundant dictionaries, for security algorithms. We show that a flexible image representation based on a multidimensional and geometry-based coding scheme, has precious attributes for security information embedding. Redundant expansions provide very good approximation properties, as well as an increased resiliency to coding noise and a simple stream structure enables easy manipulations. This paper describes simple examples of image scrambling and watermarking applications, based on a matching pursuit image coder. It illustrates the very interesting potential of redundant decompositions for data protection and security applications.

The dictionary approach to signal and image processing has been massively investigated in the last two decades, proving very attractive for a wide range of applications. The effectiveness of dictionary-based methods, however, is strongly influenced by the choice of the set of basis functions. Moreover, the structure of the dictionary is of paramount importance regarding efficient implementation and practical applications such as image coding. In this work, an over-complete code for sparse representation of natural images has been learnt from a set a real-world scenes. The functions found have been organized into a hierarchical structure. We take advantage of this representation of the dictionary, adopting a structured greedy algorithm to build sparse approximations of images. Using this procedure, no a-priori constraint is imposed on the structure of the dictionary, allowing great flexibility in its design and lower computational complexity.

In this work, we explore a framework for the sparse representation of video sequences by means of spatio-temporal functions able to exploit the 2D nature of images and the temporal smoothness associated to object trajectories. Decomposition over redundant dictionaries formed by 2D functions capable to exploit image geometry, has shown to be well adapted for efficient sparse image approximations. Video representation by means of temporally evolving sets of such 2D functions seems thus a natural extension toward video approximation techniques. In the present paper we study the deformation of a geometry oriented image expansion based on matching pursuits (MP) (P. Vandergheynst and P. Frossard, May 2001), to obtain a parametric representation of frames transformation through time. We consider a modified MP approach based on a Bayesian decision criteria to deform geometrical primitives in a predictive fashion from frame to frame. Indeed, since motion stability is not guaranteed using a pure MP, a Bayesian framework is introduced to regularize motion among expansion terms of frames representations.

This paper discusses distributed coding of two correlated video signals. The video signals are captured from a dynamic scene where each signal is temporally decorrelated by a motion-compensated Haar wavelet. The two cameras operate independently, however, the central decoder is able to exploit the coded information from all cameras to achieve the best reconstruction of the correlated video signals. The coding system utilizes nested lattice codes for the transform coefficients and exploits side information at the decoder. The efficiency of the decoder is improved by disparity compensation of one video signal. When compared to decoding without side information, decoding of the quantized transform coefficients with side information reduces the bit-rate of our test sequence by up to 5%. Further, we observe bit-rate savings of up to 8% with disparity compensation at the decoder and decoding of transform coefficients with side information.

In many applications - such as compression, de-noising and source separation - a good and efficient signal representation is characterized by sparsity. This means that many coefficients are close to zero, while only few ones have a non-negligible amplitude. On the other hand, real-world signals such as audio or natural images - clearly present peculiar structures. In this paper we introduce a global optimization framework that aims at respecting the sparsity criterion while decomposing a signal over an overcomplete, multi-component dictionary. We adopt a probabilistic analysis which can lead to consider the signal internal structure. As an example that fits this framework, we propose the weighted basis pursuit algorithm, based on the solution of a convex, non-quadratic problem. Results show that this method can provide sparse signal representations and sparse m-terms approximations. Moreover, weighted basis pursuit provides a faster convergence compared to basis pursuit.

In the present paper we propose a new framework for the construction of meaningful dictionaries for sparse representation of signals. The dictionary approach to coding and compression proves very attractive since decomposing a signal over a redundant set of basis functions allows a parsimonious representation of information. This interest is witnessed by numerous research efforts that have been done in the last years to develop efficient algorithm for the decomposition of signals over redundant sets of functions. However, the effectiveness of such methods strongly depends on the dictionary and on its structure. In this work, we develop a method to learn overcomplete sets of functions from real-world signals. This technique allows the design of dictionaries that can be adapted to a specific class of signals. The found functions are stored in a tree structure. This data structure is used by a Tree-Based Pursuit algorithm to generate sparse approximations of natural signals. Finally, the proposed method is considered in the context of image compression. Results show that the learning Tree-Based approach outperforms state-of-the-art coding technique.

This paper investigates video coding with wavelet transforms applied in the temporal direction of a video sequence. The wavelets are implemented with the lifting scheme in order to permit motion compensation between successive pictures. We improve motion compensation in the lifting steps and utilize complementary motion-compensated signals. Similar to superimposed predictive coding with complementary signals, this approach improves compression efficiency. We investigate experimentally and theoretically complementary motion-compensated signals for lifted wavelet transforms. Experimental results with the complementary motion-compensated Haar wavelet and frame-adaptive motion compensation show improvements in coding efficiency of up to 3 dB. The theoretical results demonstrate that the lifted Haar wavelet scheme with complementary motion-compensated signals is able to approach the bound for bit-rate savings of 2 bits per sample and motion-accuracy step when compared to optimum intra-frame coding of the input pictures.

In this paper, we introduce a framework that merges classical ideas borrowed from scale-space and multiresolution segmentation with nonlinear partial differential equations. A non-linear scale-space stack is constructed by means of an appropriate diffusion equation. This stack is analyzed and a tree of coherent segments is constructed based on relationships between different scale layers. Pruning this tree proves to be a very efficient tool for unsupervised segmentation of different classes of images (e.g., natural, medical, etc.). This technique is light on the computational point of view and can be extended to nonscalar data in a straightforward manner.

The presented work extends the concept of sub-band video coding based on a 3D wavelet transform to a more adaptive approach. A formal comparison is presented between the performances inferred by the use of the 3D wavelet transform and the use of a 2D wavelet in the spatial domain extended by a locally adaptive transform in the temporal dimension. Some advantages are foreseen for the new scheme since it is able to deal better with certain signal models, like appearing and moving edges. An increased control of distortion spreading is expected and, consequently, a lower visual impact relevance.

The wavelet transform is a powerful instrument in catching zero-dimensional singularities. Ridgelets are a powerful instrument in catching and representing monodimensional singularities in bidimensional space. The continuous ridgelet transform, defined by E.J. Candes and D.L. Donoho (see Phil. Trans. R. Soc. Lond. A., p.2495-509, 1999), is the application of a mono-dimensional wavelet to the slices of the Radon transform. We propose a hybrid video coder scheme using the ridgelet transform for the first approximation of line-edge singularities in displaced frame difference images. We demonstrate the potential of ridgelets and results show substantial improvements when compared to a wavelet only based coder.

In this paper, we propose an energy functional to segment objects whose global shape is a priori known thanks to a statistical model. Our work aims at extending the variational approach of Chen et al. [Y. Chen, et al., 2002] by integrating the statistical shape model of Leventon et al. [M. Leventon, et al., 2000]. The proposed energy functional allows us to capture an object that exhibits high image gradients and a shape compatible with the statistical model which best fits the segmented object. The minimization of the functional provides a system of coupled equations whose steady-state solution is the solution of the segmentation problem. Results are presented on synthetic and medical images.

Today's video codecs employ motion compensated prediction in combination with block matching techniques. These techniques, although achieving some level of adaptivity in their latest versions, continue to rely on the decomposition of frames on a set of artificial primitives: blocks. This paper presents a new approach to video coding. A geometrically adaptive image decomposition scheme using an over-complete basis is used to represent the scene. Using Matching Pursuit (MP), we are able to express local features such as position, anisotropic scale and orientation in terms of a set of spatio-frequential primitives. In order to perform frame prediction, only the changes in the parameters that determine these functions from frame to frame will have to be coded. Such an approach, in addition to being able to catch displacements in images deals as well in a natural way with local scale deformations and local rotations.

Today's video codecs employ motion compensated prediction in combination with block matching techniques. These techniques, although achieving some level of adaptivity in their latest versions, continue to rely on the decomposition of frames on a set of artificial primitives: blocks. This paper presents a new approach to video coding. A geometrically adaptive image decomposition scheme using an over-complete basis is used to represent the scene. Using matching pursuit (MP), we are able to express local features such as position, anisotropic scale and orientation in terms of a set of spatio-frequential primitives. In order to perform frame prediction, only the changes in the parameters that determine these functions from frame to frame will have to be coded. Such an approach, in addition to being able to catch displacements in images deals as well in a natural way with local scale deformations and local rotations.

Wavelet transform is a powerful instrument in catching zero-dimensional singularities. Ridgelets are powerful instrument in catching and representing mono-dimensional singularities in bidimensional space. In this paper we propose a hybrid video coder scheme using ridgelet transform for the first approximation of line-edge singularities in displaced frame difference images. We demonstrate the potential of ridgelets and results show substantial improvements when compared to wavelet only based coder.

Matching pursuit decomposes a signal into a linear expansion of functions selected from a redundant dictionary, isolating the signal structures that are coherent with respect to a given dictionary. In this paper we focus on the Matching Pursuit representation of the displaced frame difference (dfd). In particular, we introduce a new dictionary for matching pursuit that efficiently exploits the signal structures of the dfd. We also propose a fast strategy to find the atoms exploiting the maximum of the absolute value of the error in the motion predicted image and the convergence of the MSE with the rotation of the atoms. Results show that the fast strategy is quite robust when compared to exhaustive search techniques and it improves the results of a suboptimal search strategy based on a genetic algorithm.

We propose a simple and efficient technique for designing translation invariant dyadic wavelet transforms (DWTs) in two dimensions. Our technique relies on an extension of the work of Duval-Destin et al. where dyadic decompositions are constructed starting from the continuous wavelet transform. The main advantage of this framework is that it allows for a lot of freedom in designing two-dimensional (2-D) dyadic wavelets. We use this property to construct directional wavelets, whose orientation filtering capabilities are very important in image processing. We address the efficient implementation of these decompositions by constructing approximate QMFs through an L(2) optimization. We also propose and study an efficient implementation in the Fourier domain for dealing with large filters.

This paper presents a new image representation method based on anisotropic refinement. It has been shown that wavelets are not optimal to code 2-D objects which need true 2-D dictionaries for efficient approximation. We propose to use rotations and anisotropic scaling to build a real bi-dimensional dictionary. Matching pursuit then stands as a natural candidate to provide an image representation with an anisotropic refinement scheme. It basically decomposes the image as a series of basis functions weighted by their respective coefficients. Even if the basis functions can a priori take any form, bi-dimensional dictionaries are almost exclusively composed of two-dimensional Gabor functions. We present here a new dictionary design by introducing orientation and anisotropic refinement of a Gaussian generating function. The new dictionary permits to efficiently code 2-D objects and more particularly oriented contours. It is shown to clearly outperform common nonoriented Gabor dictionaries.

This paper proposes an adaptive entropy-constrained matching pursuit coefficient quantization scheme. The quantization scheme takes benefit of the inherent properties of matching pursuit streams where coefficient energy decreases along with the iteration number. The decay rate can moreover be upper-bounded with an exponential curve driven by the redundancy of the dictionary. An optimal entropy-constrained quantization scheme can thus be derived once the dictionary is known. We propose to approximate this optimal quantization scheme by adaptive quantization of successive coefficients whose actual values are used to update the quantization scheme parameters. This new quantization scheme is shown to outperform classical exponential quantization in the case of both random dictionaries and practical image coding with Gabor dictionaries.

Working with contrast instead of luminance can facilitate numerous image processing and analysis tasks. Unfortunately, a common definition of contrast suitable for all situations does not exist. We review existing contrast definitions for natural images and propose a new isotropic contrast measure, which is computed from oriented filters. We investigate some of its properties and apply it to natural images.

We recall the definition and basic properties of 2-D directional wavelets. We then focus on a particular class of wavelets, namely the Cauchy wavelets introduced by Antoine et al. (1996), and give several examples of its use in detecting and handling symmetries in images. We also compare these results with those obtained using the well-known 2-D Morlet wavelet. These directional wavelets can be used to evaluate the global symmetry of an object or to measure its intrinsic orientation.