X-radiography (X-ray imaging) is a widely used imaging technique in art investigation. It can provide information about the condition of a painting as well as insights into an artist's techniques and working methods, often revealing hidden information invisible to the naked eye. X-radiograpy of double-sided paintings results in a mixed X-ray image and this paper deals with the problem of separating this mixed image. Using the visible color images (RGB images) from each side of the painting, we propose a new Neural Network architecture, based upon 'connected' auto-encoders, designed to separate the mixed X-ray image into two simulated X-ray images corresponding to each side. This connected auto-encoders architecture is such that the encoders are based on convolutional learned iterative shrinkage thresholding algorithms (CLISTA) designed using algorithm unrolling techniques, whereas the decoders consist of simple linear convolutional layers; the encoders extract sparse codes from the visible image of the front and rear paintings and mixed X-ray image, whereas the decoders reproduce both the original RGB images and the mixed X-ray image. The learning algorithm operates in a totally self-supervised fashion without requiring a sample set that contains both the mixed X-ray images and the separated ones. The methodology was tested on images from the double-sided wing panels of the Ghent Altarpiece, painted in 1432 by the brothers Hubert and Jan van Eyck. These tests show that the proposed approach outperforms other state-of-the-art X-ray image separation methods for art investigation applications.

In the desire to quantify the success of neural networks in deep learning and other applications, there is a great interest in understanding which functions are efficiently approximated by the outputs of neural networks. By now, there exists a variety of results which show that a wide range of functions can be approximated with sometimes surprising accuracy by these outputs. For example, it is known that the set of functions that can be approximated with exponential accuracy (in terms of the number of parameters used) includes, on one hand, very smooth functions such as polynomials and analytic functions and, on the other hand, very rough functions such as the Weierstrass function, which is nowhere differentiable. In this paper, we add to the latter class of rough functions by showing that it also includes refinable functions. Namely, we show that refinable functions are approximated by the outputs of deep ReLU neural networks with a fixed width and increasing depth with accuracy exponential in terms of their number of parameters. Our results apply to functions used in the standard construction of wavelets as well as to functions constructed via subdivision algorithms in Computer Aided Geometric Design.

In this paper, we focus on X-ray images (X-radiographs) of paintings with concealed sub-surface designs (e.g., deriving from reuse of the painting support or revision of a composition by the artist), which therefore include contributions from both the surface painting and the concealed features. In particular, we propose a self-supervised deep learning-based image separation approach that can be applied to the X-ray images from such paintings to separate them into two hypothetical X-ray images. One of these reconstructed images is related to the X-ray image of the concealed painting, while the second one contains only information related to the X-ray image of the visible painting. The proposed separation network consists of two components: the analysis and the synthesis sub-networks. The analysis sub-network is based on learned coupled iterative shrinkage thresholding algorithms (LCISTA) designed using algorithm unrolling techniques, and the synthesis sub-network consists of several linear mappings. The learning algorithm operates in a totally self-supervised fashion without requiring a sample set that contains both the mixed X-ray images and the separated ones. The proposed method is demonstrated on a real painting with concealed content, Do na Isabel de Porcel by Francisco de Goya, to show its effectiveness.

X-radiography is a widely used imaging technique in art investigation, whether to investigate the condition of a painting or provide insights into artists' techniques and working methods. In this paper, we propose a new architecture based on the use of `connected' auto-encoders in order to separate mixed X-ray images acquired from double-sided paintings, where in addition to the mixed X-ray image one can also exploit the two RGB images associated with the front and back of the painting. This proposed architecture uses convolutional auto-encoders that extract features from the RGB images that can be employed to (1) reproduce both of the original RGB images, (2) reconstruct the associated separated X-ray images, and (3) regenerate the mixed X-ray image. It operates in a totally self-supervised fashion without the need for examples containing both the mixed X-ray images and the separated ones. Based on images from the double-sided wing panels from the famous Ghent Altarpiece, painted in 1432 by the brothers Hubert and Jan Van Eyck, the proposed algorithm has been experimentally verified to outperform state-of-the-art X-ray separation methods in art investigation applications.

Deep neural networks have proved very successful on archetypal tasks for which large training sets are available, but when the training data are scarce, their performance suffers from overfitting. Many existing methods of reducing overfitting are data-independent. Data-dependent regularizations are mostly motivated by the observation that data of interest lie close to a manifold, which is typically hard to parametrize explicitly. These methods usually only focus on the geometry of the input data, and do not necessarily encourage the networks to produce geometrically meaningful features. To resolve this, we propose the Low-Dimensional-Manifold-regularized neural Network (LDMNet), which incorporates a feature regularization method that focuses on the geometry of both the input data and the output features. In LDMNet, we regularize the network by encouraging the combination of the input data and the output features to sample a collection of low dimensional manifolds, which are searched efficiently without explicit parametrization. To achieve this, we directly use the manifold dimension as a regularization term in a variational functional. The resulting Euler-Lagrange equation is a Laplace-Beltrami equation over a point cloud, which is solved by the point integral method without increasing the computational complexity. In the experiments, we show that LDMNet significantly outperforms widely-used regularizers. Moreover, LDMNet can extract common features of an object imaged via different modalities, which is very useful in real-world applications such as cross-spectral face recognition.

We propose an image representation scheme combining the local and nonlocal characterization of patches in an image. Our representation scheme can be shown to be equivalent to a tight frame constructed from convolving local bases (e.g., wavelet frames, discrete cosine transforms, etc.) with nonlocal bases (e.g., spectral basis induced by nonlinear dimension reduction on patches), and we call the resulting frame elements convolution framelets. Insight gained from analyzing the proposed representation leads to a novel interpretation of a recent high-performance patch-based image processing algorithm using the point integral method (PIM) and the low dimensional manifold model (LDMM) [S. Osher, Z. Shi, and W. Zhu, Low Dimensional Manifold Model for Image Processing, Tech. Rep., CAM report 16-04, UCLA, Los Angeles, CA, 2016]. In particular, we show that LDMM is a weighted $\ell_2$-regularization on the coefficients obtained by decomposing images into linear combinations of convolution framelets; based on this understanding, we extend the original LDMM to a reweighted version that yields further improved results. In addition, we establish the energy concentration property of convolution framelet coefficients for the setting where the local basis is constructed from a given nonlocal basis via a linear reconstruction framework; a generalization of this framework to unions of local embeddings can provide a natural setting for interpreting BM3D, one of the state-of-the-art image denoising algorithms.

We address the removal of canvas artifacts from high-resolution digital photographs and X-ray images of paintings on canvas. Both imaging modalities are common investigative tools in art history and art conservation. Canvas artifacts manifest themselves very differently according to the acquisition modality; they can hamper the visual reading of the painting by art experts, for instance, in preparing a restoration campaign. Computer-aided canvas removal is desirable for restorers when the painting on canvas they are preparing to restore has acquired over the years a much more salient texture. We propose a new algorithm that combines a cartoon-texture decomposition method with adaptive multiscale thresholding in the frequency domain to isolate and suppress the canvas components. To illustrate the strength of the proposed method, we provide various examples, for acquisitions in both imaging modalities, for paintings with different types of canvas and from different periods. The proposed algorithm outperforms previous methods proposed for visual photographs such as morphological component analysis and Wiener filtering and it also works for the digital removal of canvas artifacts in X-ray images.

In support of art investigation, we propose a new source separation method that unmixes a single X-ray scan acquired from double-sided paintings. In this problem, the X-ray signals to be separated have similar morphological characteristics, which brings previous source separation methods to their limits. Our solution is to use photographs taken from the front-and back-side of the panel to drive the separation process. The crux of our approach relies on the coupling of the two imaging modalities (photographs and X-rays) using a novel coupled dictionary learning framework able to capture both common and disparate features across the modalities using parsimonious representations; the common component captures features shared by the multi-modal images, whereas the innovation component captures modality-specific information. As such, our model enables the formulation of appropriately regularized convex optimization procedures that lead to the accurate separation of the X-rays. Our dictionary learning framework can be tailored both to a single- and a multi-scale framework, with the latter leading to a significant performance improvement. Moreover, to improve further on the visual quality of the separated images, we propose to train coupled dictionaries that ignore certain parts of the painting corresponding to craquelure. Experimentation on synthetic and real data - taken from digital acquisition of the Ghent Altarpiece (1432) - confirms the superiority of our method against the state-of-the-art morphological component analysis technique that uses either fixed or trained dictionaries to perform image separation.

We consider the problem of recognizing objects in collections of art works, in view of automatically labeling, searching and organizing databases of art works. To avoid manually labelling objects, we introduce a framework for transferring a convolutional neural network (CNN), trained on available large collections of labelled natural images, to the context of drawings. We retrain both the top and the bottom layer of the network, responsible for the high-level classification output and the low-level features detection respectively, by transforming natural images into drawings. We apply this procedure to the drawings in the Jan Brueghel Wiki, and show the transferred CNN learns a discriminative metric on drawings and achieves good recognition accuracy. We also discuss why standard descriptor-based methods is problematic in the context of drawings.

In support of art investigation, we propose a new source separation method that unmixes a single X-ray scan acquired from double-sided paintings. Unlike prior source separation methods, which are based on statistical or structural incoherence of the sources, we use visual images taken from the front- and back-side of the panel to drive the separation process. The coupling of the two imaging modalities is achieved via a new multi-scale dictionary learning method. Experimental results demonstrate that our method succeeds in the discrimination of the sources, while state-of-the-art methods fail to do so.

We propose an algorithm that removes the visually unpleasant effects of cradling in X-ray images of panel paintings, with the goal of improving the X-ray image readability by art experts. The algorithm consists of three stages. In the first stage the location of the cradle is detected automatically and the grayscale inconsistency, caused by the thickness of the cradle, is corrected. In a second stage we use a method called morphological component analysis to separate the X-ray image into a so-called cartoon part and a texture part, where the latter contains mostly the wood grain from both the panel and the cradling. The algorithm next learns a Bayesian factor model that distinguishes between the texture patterns that originate from the cradle and those from other components such as the panel and/or the painting on the panel surface, and finally uses this to remove the textures associated with the cradle. We apply the algorithm to a number of historically important paintings on panel. We also show how it can be used to digitally remove stretcher artifacts from X-rays of paintings on canvas. We compare our results with those obtained manually by best current practices in art conservation as well as on a ground truth dataset, consisting of X-ray images of a painting before and after removal of the physically attached cradle.

Super-resolution methods form high-resolution images from low-resolution images. In this paper, we develop a new Bayesian nonparametric model for super-resolution. Our method uses a beta-Bernoulli process to learn a set of recurring visual patterns, called dictionary elements, from the data. Because it is nonparametric, the number of elements found is also determined from the data. We test the results on both benchmark and natural images, comparing with several other models from the research literature. We perform large-scale human evaluation experiments to assess the visual quality of the results. In a first implementation, we use Gibbs sampling to approximate the posterior. However, this algorithm is not feasible for large-scale data. To circumvent this, we then develop an online variational Bayes (VB) algorithm. This algorithm finds high quality dictionaries in a fraction of the time needed by the Gibbs sampler.

We study Sigma-Delta ($\Sigma\Delta$) quantization of oversampled bandlimited functions. We prove that digitally integrating blocks of bits and then down-sampling, a process known as decimation, can efficiently encode the associated $\Sigma\Delta$ bit-stream. It allows a large reduction in the bit-rate while still permitting good approximation of the underlying bandlimited function via an appropriate reconstruction kernel. Specifically, in the case of stable $r$th order $\Sigma\Delta$ schemes we show that the reconstruction error decays exponentially in the bit-rate. For example, this result applies to the 1-bit, greedy, first-order $\Sigma\Delta$ scheme.

We introduce an algorithm that removes the deleterious effect of cradling on X-ray images of paintings on wooden panels. The algorithm consists of a three stage procedure. Firstly, the cradled regions are located automatically. The second step consists of separating the X-ray image into a textural and image component. In the last step the algorithm learns to distinguish between the texture caused by the wooden cradle and the texture belonging to the original painted wooden panel. The results obtained with our method are compared with those obtained manually by best current practice.

In this paper, computer-based techniques for stylistic analysis of paintings are applied to the five panels of the 14th century Peruzzi Altarpiece by Giotto di Bondone. Features are extracted by combining a dual-tree complex wavelet transform with a hidden Markov tree (HMT) model. Hierarchical clustering is used to identify stylistic keywords in image patches, and keyword frequencies are calculated for sub-images that each contains many patches. A generative hierarchical Bayesian model learns stylistic patterns of keywords; these patterns are then used to characterize the styles of the sub-images; this in turn, permits to discriminate between paintings. Results suggest that such unsupervised probabilistic topic models can be useful to distill characteristic elements of style.

This paper relates the style of 16th century Flemish paintings by Goossen van der Weyden (GvdW) to the style of preliminary sketches or underpaintings made prior to executing the painting. Van der Weyden made underpaintings in markedly different styles for reasons as yet not understood by art historians. The analysis presented here starts from a classification of the underpaintings into four distinct styles by experts in art history. Analysis of the painted surfaces by a combination of wavelet analysis, hidden Markov trees and boosting algorithms can distinguish the four underpainting styles with greater than 90% cross-validation accuracy. On a subsequent blind test this classifier provided insight into the hypothesis by art historians that different patches of the finished painting were executed by different hands.

Objective characterization of jewels in paintings, especially pearls, has been a long lasting challenge for art historians. The way an artist painted pearls reflects his ability to observing nature and his knowledge of contemporary optical theory. Moreover, the painterly execution may also be considered as an individual characteristic useful in distinguishing hands. In this work, we propose a set of image analysis techniques to analyze and measure spatial characteristics of the digital images of pearls, all relying on the so called spatiogram image representation. Our experimental results demonstrate good correlation between the new metrics and the visually observed image features, and also capture the degree of realism of the visual appearance in the painting. In that sense, these results set the basis in creating a practical tool for art historical attribution and give strong motivation for further investigations in this direction.

This paper proposes a novel Nyquist-rate analog-to-digital (A/D) conversion algorithm which achieves exponential accuracy in the bit-rate despite using imperfect components. The proposed algorithm is based on a robust implementation of a beta-encoder with β = φ = (1 + √5)/2, the golden ratio. It was previously shown that beta-encoders can be implemented in such a way that their exponential accuracy is robust against threshold offsets in the quantizer element. This paper extends this result by allowing for imperfect analog multipliers with imprecise gain values as well. Furthermore, a formal computational model for algorithmic encoders and a general test bed for evaluating their robustness is proposed.

We introduce the Symmetry Factored Embedding (SFE) and the Symmetry Factored Distance (SFD) as new tools to analyze and represent symmetries in a point set. The SFE provides new coordinates in which symmetry is "factored out," and the SFD is the Euclidean distance in that space. These constructions characterize the space of symmetric correspondences between points -- i.e., orbits. A key observation is that a set of points in the same orbit appears as a clique in a correspondence graph induced by pairwise similarities. As a result, the problem of finding approximate and partial symmetries in a point set reduces to the problem of measuring connectedness in the correspondence graph, a well-studied problem for which spectral methods provide a robust solution. We provide methods for computing the SFE and SFD for extrinsic global symmetries and then extend them to consider partial extrinsic and intrinsic cases. During experiments with difficult examples, we find that the proposed methods can characterize symmetries in inputs with noise, missing data, non-rigid deformations, and complex symmetries, without a priori knowledge of the symmetry group. As such, we believe that it provides a useful tool for automatic shape analysis in applications such as segmentation and stationary point detection.

This paper examines whether machine learning and image analysis tools can be used to assist art experts in the authentication of unknown or disputed paintings. Recent work on this topic has presented some promising initial results. Our reexamination of some of these recently successful experiments shows that variations in image clarity in the experimental datasets were correlated with authenticity, and may have acted as a confounding factor, artificially improving the results. To determine the extent of this factor's influence on previous results, we provide a new ¿ground truth¿ data set in which originals and copies are known and image acquisition conditions are uniform. Multiple previously-successful methods are found ineffective on this new confounding-factor-free dataset, but we demonstrate that supervised machine learning on features derived from hidden-Markov-tree-modeling of the paintings' wavelet coefficients has the potential to distinguish copies from originals in the new dataset.

A scheme for simple oversampled analog-to-digital (A/D) conversion using single-bit quantization is presented. The scheme is based on recording positions of zero-crossings of the input signal added to a deterministic dither function. This information can be represented in a manner such that the bit rate increases only logarithmically with the oversampling factor$r$. The input band-limited signal can be reconstructed from this information locally with$O(1/r)$pointwise error, resulting in an exponentially decaying distortion-rate characteristic.

Mutual information (MI) based methods for image registration enjoy great experimental success and are becoming widely used. However, they impose a large computational burden that limits their use; many applications would benefit from a reduction of the computational load. Although the theoretical justification for these methods draws upon the stochastic concept of mutual information, in practice, such methods actually seek the best alignment by maximizing a number that is (deterministically) computed from the two images. These methods thus optimize a fixed function, the "similarity metric," over different candidate alignments of the two images. Accordingly, we study the important features of the computationally complex MI similarity metric with the goal of distilling them into simpler surrogate functions that are easier to compute. More precisely, we show that maximizing the MI similarity metric is equivalent to minimizing a certain distance metric between equivalence classes of images, where images f and g are said to be equivalent if there exists a bijection φ such that f(x)=φ(g(x)) for all x. We then show how to design new similarity metrics for image alignment with this property. Although we preserve only this aspect of MI, our new metrics show equal alignment accuracy and similar robustness to noise, while significantly decreasing computation time. We conclude that even the few properties of MI preserved by our method suffice for accurate registration and may in fact be responsible for MI's success.

This paper analyzes mathematically the effect of quantizer threshold imperfection commonly encountered in the circuit implementation of analog-to-digital (A/D) converters such as pulse code modulation (PCM) and sigma-delta (SigmaDelta) modulation. SigmaDelta modulation, which is based on coarse quantization of oversampled (redundant) samples of a signal, enjoys a type of self-correction property for quantizer threshold errors (bias) that is not shared by PCM. Although "classical" SigmaDelta modulation is inferior to PCM in the rate-distortion sense, this robustness feature is believed to be one of the reasons why SigmaDelta modulation is preferred over PCM in A/D converters with imperfect quantizers. Motivated by these facts, other encoders are constructed in this paper that use redundancy to obtain a similar self-correction property, but that achieve higher order accuracy relative to bit rate compared to classical SigmaDelta. More precisely, two different types of encoders are introduced that exhibit exponential accuracy in the bit rate (in contrast to the polynomial-type accuracy of classical SigmaDelta) while possessing the self-correction property

Beta-encoders with error correction were introduced by Daubechies, DeVore, Guumlntuumlrk and Vaishampayan as an alternative to pulse-code modulation (PCM) for analog-to-digital conversion. An N-bit beta-encoder quantizes a real number by computing one of its N-bit truncated beta-expansions where betaisin(1,2) determines the base of expansion. These encoders have (almost) optimal rate-distortion properties like PCM; furthermore, they exploit the redundancy of beta-expansions and thus they are robust with respect to quantizer imperfections. However, these encoders have the shortcoming that the decoder needs to know the value of the base of expansion beta, a gain factor in the circuit used by the encoder, which is an impractical constraint. We present a method to implement beta-encoders so that they are also robust with respect to uncertainties of the value of beta. The method relies upon embedding the value of beta in the encoded bitstream. We show that this can be done without a priori knowledge of beta by the transmitting party. Moreover the algorithm still works if the value of beta changes (slowly) during the implementation

In order to understand AdaBoost’s dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases. We find stable cycles for these cases, which can explicitly be used to solve for Ada- Boost’s output. By considering AdaBoost as a dynamical system, we are able to prove R¨atsch and Warmuth’s conjecture that AdaBoost may fail to converge to a maximal-margin combined classifier when given a ‘non- optimal’ weak learning algorithm. AdaBoost is known to be a coordinate descent method, but other known algorithms that explicitly aim to max- imize the margin (such as AdaBoost⁄ and arc-gv) are not. We consider a differentiable function for which coordinate ascent will yield a maxi- mum margin solution. We then make a simple approximation to derive a new boosting algorithm whose updates are slightly more aggressive than those of arc-gv.

The problem of reconstructing a /spl pi/-bandlimited signal f from its quantized samples taken at an irregular sequence of points (t/sub k/)/sub k/spl isin//spl Zopf// arises in oversampled analog-to-digital conversion. The input signal can be reconstructed from the quantized samples (f(t/sub k/))/sub k/spl isin//spl Zopf// by estimating samples (f(n//spl lambda/))/sub n/spl isin//spl Zopf//, where /spl lambda/ is the average uniform density of the sequence (tk)/sub k/spl isin//spl Zopf//, assumed here to be greater than one, followed by linear low-pass filtering. We study three techniques for estimating samples (f(n//spl lambda/))/sub n/spl isin//spl Zopf// from quantized irregular samples (f(t/sub k/))/sub k/spl isin//spl Zopf//, including Lagrangian interpolation, and two other techniques which result in a better overall accuracy of oversampled A/D conversion.

We introduce the concept of "democracy," in which the individual bits in a coarsely quantized representation of a signal are all given "equal weight" in the approximation to the original signal. We prove that such democratic representations cannot achieve the same accuracy as optimal nondemocratic schemes.

This paper provides a mathematical analysis of transform compression in its relationship to linear and nonlinear approximation theory. Contrasting linear and nonlinear approximation spaces, we show that there are interesting classes of functions/random processes which are much more compactly represented by wavelet-based nonlinear approximation. These classes include locally smooth signals that have singularities, and provide a model for many signals encountered in practice, in particular for images. However, we also show that nonlinear approximation results do not always translate to efficient compress on strategies in a rate-distortion sense. Based on this observation, we construct compression techniques and formulate the family of functions/stochastic processes for which they provide efficient descriptions in a rate-distortion sense. We show that this family invariably leads to Besov spaces, yielding a natural relationship among Besov smoothness, linear/nonlinear approximation order, and compression performance in a rate-distortion sense. The designed compression techniques show similarities to modern high-performance transform codecs, allowing us to establish relevant rate-distortion estimates and identify performance limits.

We present a scheme for simple oversampled analog-to-digital conversion with single bit quantization and exponential error decay in the bit rate. The scheme is based on recording positions of zero-crossings of the input signal added to a deterministic dither function. This information can be represented in a manner which requires only logarithmic increase of the bit rate with the oversampling factor, r. The input-bandlimited signal can be reconstructed from this information locally, and with a mean squared error which is inversely proportional to the square of the oversampling factor, MSE=O(1/r/sup 2/). Consequently the mean squared error of this scheme exhibits exponential decay in the bit rate.

In this paper the windowed Fourier encoding-decoding scheme applied to the multiple description compression problem is analyzed. In the general case, four window functions are needed to define the encoder and decoder, although this number can be reduced to three or two by using time-shift or frequency-shift division schemes. The encoding coefficients are next divided into two groups according to the eveness of either the modulation or translation index. The distortion on each channel is analyzed using the Zak transform. For the optimal windows, explicit representation formulas are obtained and nonlocalization results are proved. Asymptotic formulas of the total distortion and transmission rate are established and the redundancy is shown to trade off between these two.

In this paper we review some recent interactions between harmonic analysis and data compression. The story goes back of course to Shannon's R(D) theory in the case of Gaussian stationary processes, which says that transforming into a Fourier basis followed by block coding gives an optimal lossy compression technique; practical developments like transform-based image compression have been inspired by this result. In this paper we also discuss connections perhaps less familiar to the information theory community, growing out of the field of harmonic analysis. Recent harmonic analysis constructions, such as wavelet transforms and Gabor transforms, are essentially optimal transforms for transform coding in certain settings. Some of these transforms are under consideration for future compression standards. We discuss some of the lessons of harmonic analysis in this century. Typically, the problems and achievements of this field have involved goals that were not obviously related to practical data compression, and have used a language not immediately accessible to outsiders. Nevertheless, through an extensive generalization of what Shannon called the "sampling theorem", harmonic analysis has succeeded in developing new forms of functional representation which turn out to have significant data compression interpretations. We explain why harmonic analysis has interacted with data compression, and we describe some interesting recent ideas in the field that may affect data compression in the future.

Invertible wavelet transforms that map integers to integers are important for lossless representations. We present an approach to build integer to integer wavelet transforms based upon the idea of factoring wavelet transforms into lifting steps. This allows the construction of an integer version of every wavelet transform. We demonstrate the use of these transforms in lossless image compression.

A geometrical description is given for reassignment vector fields of spectrograms. These vector fields are shown to be connected with both an intrinsic phase characterization and a scalar potential. This allows for the generalization of the original reassignment process to a differential version based on a dynamical evolution of time-frequency particles.

The development of wavelets is an example where ideas from many different fields combined to merge into a whole that is more than the sum of its parts. The subject area of wavelets, developed mostly over the last 15 years, is connected to older ideas in many other fields, including pure and applied mathematics, physics, computer science, and engineering. The history of wavelets can therefore be represented as a tree with roots reaching deeply and in many directions. In this picture, the trunk would correspond to the rapid development of "wavelet tools" in the second half of the 1980's, with shared efforts by researchers from many different fields; the crown of the tree, with its many branches, would correspond to different directions and applications in which wavelets are now becoming a standard part of the mathematical tool kit, alongside other more established techniques. The author gives here a highly personal version of the development of wavelets.

It is shown that there is a tradeoff between the smoothness and decay properties of the dual functions, occurring in the lattice expansion problem. More precisely, it is shown that if g and g are dual, then (1) at least one of H/sup 1/2/ g and H/sup 1/2/ g is n in L/sup 2/(R), and (2) at least one of Hg and g is not in L/sup 2/(R). Here, H is the operator -1/(4 pi /sup 2/)d/sup 2//(dt/sup 2/)+t/sup 2/. The first result is a generalization of a theorem first stated by R.C. Balian (1987). The second result is new and relies heavily on the fact that, when G in W/sup 2,2/(S) with S=(-1/2, 1/2)*(-1/2, 1/2) and G(0), than 1/G not in L/sup 2/(S).>

A combination of trellis coded quantization (TCQ) and its vector alphabet generalization TCVQ is used to code the coefficients resulting from a biorthogonal wavelet transform in an image. TCVQ is a vector trellis coder with fixed rate, very good rate-distortion performance, and yet reasonable implementation complexity. The experimental results show that the Lena image can be coded by this coding system at the rate of 0.265 bpp to yield a peak signal-to-noise ratio (PSNR) of about 29 dB. This PSNR is about 3 dB larger than that obtained by a coding system of the same rate that uses VQ to obtain the wavelet transform coefficients. Naturally, the performance of the TCQ/TCVQ wavelet transform coder can be improved if entropy-coded TCQ and TCVQ coders are employed.>

A scheme for image compression that takes into account psychovisual features both in the space and frequency domains is proposed. This method involves two steps. First, a wavelet transform used in order to obtain a set of biorthogonal subclasses of images: the original image is decomposed at different scales using a pyramidal algorithm architecture. The decomposition is along the vertical and horizontal directions and maintains constant the number of pixels required to describe the image. Second, according to Shannon's rate distortion theory, the wavelet coefficients are vector quantized using a multiresolution codebook. To encode the wavelet coefficients, a noise shaping bit allocation procedure which assumes that details at high resolution are less visible to the human eye is proposed. In order to allow the receiver to recognize a picture as quickly as possible at minimum cost, a progressive transmission scheme is presented. It is shown that the wavelet transform is particularly well adapted to progressive transmission.

A two-step scheme for image compression that takes into account psychovisual features in space and frequency domains is proposed. A wavelet transform is first used in order to obtain a set of orthonormal subclasses of images; the original image is decomposed at different scales using a pyramidal algorithm architecture. The decomposition is along the vertical and horizontal directions and maintains the number of pixels required to describe the image at a constant. Second, according to Shannon's rate-distortion theory, the wavelet coefficients are vector quantized using a multiresolution codebook. To encode the wavelet coefficients, a noise-shaping bit-allocation procedure which assumes that details at high resolution are less visible to the human eye is proposed. In order to allow the receiver to recognize a picture as quickly as possible at minimum cost, a progressive transmission scheme is presented. The wavelet transform is particularly well adapted to progressive transmission.>

Two different procedures for effecting a frequency analysis of a time-dependent signal locally in time are studied. The first procedure is the short-time or windowed Fourier transform; the second is the wavelet transform, in which high-frequency components are studied with sharper time resolution than low-frequency components. The similarities and the differences between these two methods are discussed. For both schemes a detailed study is made of the reconstruction method and its stability as a function of the chosen time-frequency density. Finally, the notion of time-frequency localization is made precise, within this framework, by two localization theorems.>

The author defines a set of operators which localize in both time and frequency. These operators are similar to but different from the low-pass time-limiting operator, the singular functions of which are the prolate spheroidal wave functions. The author's construction differs from the usual approach in that she treats the time-frequency plane as one geometric whole (phase space) rather than as two separate spaces. For disk-shaped or ellipse-shaped domains in time-frequency plane, the associated localization operators are remarkably simple. Their eigenfunctions are Hermite functions, and the corresponding eigenvalues are given by simple explicit formulas involving the incomplete gamma functions.>