We investigate the use of integrate-and-fire systems to efficiently sample classes of non-bandlimited signals such as bursts of spikes. The sampling in this case is based on storing some timing information about the signal, and no information about its amplitude. We demonstrate that perfect reconstruction of these signals is possible when using proper prefiltering strategies before using a multi-channel integrate-and-fire system. We show that the probability of perfect reconstruction of the bursts of Diracs is high, even when the sufficient conditions for perfect reconstruction are not satisfied.

Because a ΣΔ modulator is a nonlinear feedback system, its rigorous signal analysis escapes from the standard theories used in signal processing and communications. We introduce mathematical tools that are new to these two areas and that lead to systematic and high-level methods for the spectral error analysis of ΣΔ modulators. They include the use of dynamical system techniques, of the roots of ergodic theory and the spectral properties of unitary operators in a Hubert space. In this paper, we show their application to the case of ideal ΣΔ modulation, thus providing a formal and concise theory for the extensive derivations performed by Gray et al. and He et al. in this special case some 15 years ago. We finally point to the potential extension of these new methods to a substantially larger class of ΣΔ modulators.

The quantization operation has been traditionally analyzed in signal processing and data conversion as a source of white noise although it is of deterministic nature. This model has become particularly inaccurate in ΣΔ modulation where the quantization resolution can be as low as 1-bit. For an important class of ΣΔ modulators with constant inputs, we build rigorous foundations to the quantization error analysis based on the spectral theory of unitary operators.

Although the technique of sigma-delta (/spl Sigma//spl Delta/) modulation is well established in practice for performing high-resolution analog-to-digital (A/D) conversion, theoretical analysis of the error between the input signal and the reconstructed signal has remained partial. For modulators of order higher than 1, the only rigorous error analysis currently available that matches practical and numerical simulation results is only applicable to a very special configuration, namely, the standard and ideal k-bit k-loop /spl Sigma//spl Delta/ modulator. Moreover, the error measure involves averaging over time as well as possibly over the input value. At the second order, it is known in practice that the mean-squared error decays with the oversampling ratio /spl lambda/ at the rate O(/spl lambda//sup -5/). In this paper, we introduce two new fundamental results in the case of constant input signals. We first establish a framework of analysis that is applicable to all second-order modulators provided that the built-in quantizer has uniformly spaced output levels, and that the noise transfer function has its two zeros at the zero frequency. In particular, this includes the one-bit case, a rigorous and deterministic analysis of which is still not available. This generalization has been possible thanks to the discovery of the mathematical tiling property of the state variables of such modulators. The second aspect of our contribution is to perform an instantaneous error analysis that avoids infinite time averaging. Until now, only an O(/spl lambda//sup -4/) type error bound was known to hold in this setting. Under our generalized framework, we provide two types of squared-error estimates; one that is statistically averaged over the input and another that is valid for almost every input (in the sense of Lebesgue measure). In both cases, we improve the error bound to O(/spl lambda//sup -4.5/), up to a logarithmic factor, for a general class of modulators including some specific ones that are covered in this paper in detail. In the particular case of the standard and ideal two-bit double-loop configuration, our methods provide a (previously unavailable) instantaneous error bound of O(/spl lambda//sup -5/), again up to a logarithmic factor.

Although the topic of analog-to-digital (A/D) conversion should fundamentally be part of the signal processing area, paradoxically, very little signal theory has been devoted to it. One reason is that the main technique currently used in data acquisition, called /spl Sigma//spl Delta/ modulation, consists of coarse quantization with feedback. This prevents the normal resolution of the output of the system in terms of its input, contrary to the case of linear feedback systems. The paper introduces new tools to solve this problem and enable rigorous signal error analysis of /spl Sigma//spl Delta/ modulators.

We explore an image compression scheme that does not rely on the usual additive decomposition of an input image into a set of predefined spanning functions. The proposed scheme only encodes implicit properties of the image and reconstructs an estimate by constrained high pass energy minimization. This has particular advantages for very low bit rate perceptually oriented image compression. We show experimental results in a context where we mainly target the smooth areas and the edges of the image.

We show that the complete information that is available after an image has been encoded is not just an approximate quantized image version, but a whole set of consistent images that contains the original image by necessity. From this starting point, we develop a set of tools to design a new class of encoders for image compression, based on a set decomposition and recombination of the image features. As an initial validation, we show the results of an experiment where these tools are used to modify the encoding process of block discrete cosine transform (DCT) coding in order to yield less blocking artifacts.

Coefficient quantization has peculiar qualitative effects on representations of vectors in IR with respect to overcomplete sets of vectors. These effects are investigated in two settings: frame expansions (representations obtained by forming inner products with each element of the set) and matching pursuit expansions (approximations obtained by greedily forming linear combinations). In both cases, based on the concept of consistency, it is shown that traditional linear reconstruction methods are suboptimal, and better consistent reconstruction algorithms are given. The proposed consistent reconstruction algorithms were in each case implemented, and experimental results are included. For frame expansions, results are proven to bound distortion as a function of frame redundancy r and quantization step size for linear, consistent, and optimal reconstruction methods. Taken together, these suggest that optimal reconstruction methods will yield O(1/r/sup 2/) mean-squared error (MSE), and that consistency is sufficient to insure this asymptotic behavior. A result on the asymptotic tightness of random frames is also proven. Applicability of quantized matching pursuit to lossy vector compression is explored. Experiments demonstrate the likelihood that a linear reconstruction is inconsistent, the MSE reduction obtained with a nonlinear (consistent) reconstruction algorithm, and generally competitive performance at low bit rates.

We give a general method to recover a continuous-tone image from a halftone image in the situation where the halftoning algorithm is known. Using rigorous mathematical tools, the method combines what we call the visual information and the coding information of the halftone data. Although we concentrate on halftoning by error diffusion, the method is applicable to all digital halftoning techniques.

We introduce a new way to use fractal coding for image compression, based on the parallel use of a fractal encoder and a DCT encoder. The two encoders are given the complementary roles to capture the information of edge and smooth variation, and the information of detail respectively. We show the advantage of using this hybrid coding scheme over the use of a fractal encoder alone, or a DCT encoder alone. This coding scheme is also the occasion to demonstrate a new concept of coding by nonlinear feature separation based on regular and uniform algorithms, suitable for real-time VLSI implementation.

Oversampled analog-to-digital conversion is a technique which permits high conversion resolution using coarse quantization. Classically, by lowpass filtering the quantized oversampled signal, it is possible to reduce the quantization error power in proportion to the oversampling ratio R. In other words, the reconstruction mean-squared error (MSE) is in /spl Oscr/(R/sup -1/). It was recently found that this error reduction is not optimal. Under certain conditions, it was shown on periodic bandlimited signals that an upper bound on the MSE of optimal reconstruction is in /spl Oscr/(R/sup -2/) instead of /spl Oscr/(R/sup -1/). In the present paper, we prove on the same type of signals that the order /spl Oscr/(R/sup -2/) is the theoretical limit of reconstruction as an MSE lower bound. The proof is based on a vector-quantization approach with an analysis of partition cell density.

We present a method that represents a signal with respect to an overcomplete set of vectors which we call a dictionary. The use of overcomplete sets of vectors (redundant bases or frames) together with quantization is explored as an alternative to transform coding for signal compression. The goal is to retain the computational simplicity of transform coding while adding flexibility like adaptation to signal statistics. We show results using both fixed quantization in frames and greedy quantization using matching pursuit. An MSE slope of -6 dB/octave of frame redundancy is shown for a particular tight frame and is verified experimentally for another frame.

The concept of convex coding systems is presented together with an application to image coding. A convex coder gives the exact description of a convex set or a group of convex sets in which the input signal is located. The reconstruction is left to the decoder whose role is to pick an estimate in the intersection of these sets. Alternating projections can be used to obtain such estimates which geometrically lie in the intersection of the sets. Convex coding enables us to supplement a criterion of "pleasingness" to the current MSE-oriented criterion. This may be useful for very high compression ratio. An example of convex coding which utilizes the conventional DCT coder as one set is demonstrated and the result shows that the blocking artifacts are efficiently removed.>

In this paper we explore how to implement realizable orthogonal projection operators for real signals. Using some of the ideas developed in the area of multirate filter banks we find it possible to implement orthogonal projections onto spaces that are approximately bandlimited, using very efficient operators. These represent a considerable improvement over linear shift-invariant approximations, which are neither bandlimited nor exact projections. A main application is for use with the algorithm of projection on convex sets, which is used, for example in image deblurring, bandlimited extrapolation and in reconstruction in oversampled A/D conversion.>

We discuss the concept of set theoretic compression where the input signal is implicitly encoded by the specification of a set which contains it, rather than an estimate which approximates it. This approach assumes the reconstruction of an estimate from the encoded set information only at the decoder side. We explain the motivations of this approach for high signal compression and encoding simplification, and the implication of more complex decoding. We then present the tools to support the approach. We finally show a demonstration of this approach in a particular application of image coding.>

Signal reconstruction in oversampled analog-to-digital conversion is classically performed by a lowpass filtering of the quantized signal. This leads to a mean squared error (MSE) inversely proportional to R/sup 2n+1/, where R is the oversampling rate and n is the order of the converter. It is shown that this reconstruction does not necessarily lead to a signal which gives the same digital sequence as that of the original input signal. It is shown that, if this were the case, one would obtain an MSE inversely proportional to R/sup 2n+2/ instead. A way to achieve such an estimate with the same bandwidth and same digital conversion is proposed. This made it possible to perform numerical experiments which confirm the R/sup 2n+2/ behavior of the MSE.>