An impressive variety of multirate filter banks evolved during the past twenty years. We presents an algebraic approach that subsumes many concepts developed so far (e.g. multifilters, nonseparable multidimensional filter banks, cyclic filter banks, filter banks with values in finite fields, etc.). In our approach the signals and filters are viewed as elements of a group ring. We give necessary and sufficient conditions for perfect reconstruction and derive complete parameterization in terms of ladder (or lifting) structures.

We present new quantitative results for the characterization of the L₂-error of wavelet-like expansions as a function of the scale a. This yields an extension as well as a simplification of the asymptotic error formulas that have been published previously. We use our bound determinations to compare the approximation power of various families of wavelet transforms. We present explicit formulas for the leading asymptotic constant for both splines and Daubechies wavelets. For a specified approximation error, this allows us to predict the sampling rate reduction that can obtained by using splines instead Daubechies wavelets. In particular, we prove that the gain in sampling density (splines vs. Daubechies) converges to (pi) as the order goes in infinity.

Statistical independence is one of the most desirable properties for a coordinate system for representing and modeling images. In reality, however, truly independent coordinates may not exist for a given set of images, or it may be computationally too difficult to obtain such coordinates. Therefore, it makes sense to obtain the least statistically dependent coordinate system efficiently. This basis--we call it Least Statistically-Dependent Basis (LSDB)--can be rapidly computed by minimizing the sum of the differential entropy of each coordinate in the basis library. This criterion is quite different from the Joint Best Basis (JBB) proposed by Wickerhauser. We demonstrate the use of the LSDB for image modeling and compare its performance with JBB and Karhunen-Loeve Basis.

We study the statistical behavior of TCP traffic traces through their wavelet decomposition, and show that the marginal distribution of the wavelet coefficients is a 1.5- stable law. Taking advantage of the correlation between the Haar coefficients, we then give a representation to the signal in terms of Weakly Self-Affine functions, which are a generalization of `fractal' functions, and allow a parsimonious representation of the data.

This paper deals with the analysis of time series with respect to certain known periodicities. In particular, we shall present a fast method aimed at detecting periodic behavior inherent in noise data. The method is composed of three steps: (1) Non-noisy data are analyzed through spectral and wavelet methods to extract specific periodic patterns of interest. (2) Using these patterns, we construct an optimal piecewise constant wavelet designed to detect the underlying periodicities. (3) We introduce a fast discretized version of the continuous wavelet transform, as well as waveletgram averaging techniques, to detect occurrence and period of these periodicities. The algorithm is formulated to provide real time implementation. Our procedure is generally applicable to detect locally periodic components in signals s which can be modeled as s(t) equals A(t)F(h(t)) + N(t) for t in I, where F is a periodic signal, A is a non-negative slowly varying function, and h is strictly increasing with h' slowly varying, N denotes background activity. For example, the method can be applied in the context of epileptic seizure detection. In this case, we try to detect seizure periodics in EEG and ECoG data. In the case of ECoG data, N is essentially 1/f noise. In the case of EEG data and for t in I,N includes noise due to cranial geometry and densities. In both cases N also includes standard low frequency rhythms. Periodicity detection has other applications including ocean wave prediction, cockpit motion sickness prediction, and minefield detection.

We use bivariate boxspline functions to construct nonseparable wavelets in Sobolev spaces.

We define and characterize a frame-like stable decomposition for subspaces in a separable Hilbert space. We call in pseudoframes for subspaces (PFFS). Properties of PFFS are discussed. A necessary and sufficient condition for the construction is provided. An analytical formula for the construction of PFFS is also derived. An example is studied both as a motivation of the theoretical study of such pseudoframes and as an actual construction. Potential applications of PFFS are discussed.

Traditional snakes suffer from slow convergence speed (many control points) and difficult to adjust weighting factors for internal energy terms. We propose an alternative formulation using cubic B-splines, where the knot spacing is variable and controlled by the user. A larger knot spacing allows us to reduce the number of parameters, which increases optimization speeds. It also eliminates the need for internal energies, which improves user interactivity. The optimization procedure is embedded into a multi- resolution image representation, where the number of snake points is adapted to the image grid spacing by correctly adjusting the spline knot spacing. Hence, the proposed method provides a multi-scale approach in both the image and parametric contour domain. Our technique provides fast optimization of the initial snake curve and leads to more stable algorithms in noisy imaging environments. Several biomedical examples of applications are included to illustrate the versatility of the method.

This paper presents a new method to extract, semi- automatically, quadrangular urban road network from high spatial resolution imagery. A quadrangular network is generally composed of different classes of streets in a hierarchical system. The developed method is based both on the multiresolution analysis and on the wavelet transform. The multiresolution analysis allows a multiscale analysis of images and thus the extraction of the streets in a class-by- class way. The wavelet transform enables the modeling of information at different characteristic scales. In the problem, it allows the extraction of the topography of streets. These two mathematical tools are combined in the `a trous' algorithm. The application of this algorithm to images of urban areas has been used to develop semi- automatic multiresolution processing. This method will help photo-interpreters in their cartographic works by a partial automation of tasks.

Image Registration, one of the scene encoding approaches, is a very active research topic in computer vision and computer graphics community. This paper presents a robust image registration scheme that employs complex wavelet pyramid and the human visual perceptive thresholding techniques. Complex wavelet transform guarantees not only a global optimal solution, but also the scale and translation invariance for the image alignment. Applying the Human Visual System thresholding for wavelet coefficients shows that image can be compressed significantly (30-100:1 ratio) while the detail of the structured information can be retained so that the transformation obtained from the thresholded wavelet images is sufficiently accurate when applying on the original images. The transformation can be progressively refined on the multiresolution decomposition. This guarantees the robustness of the scheme with a better performance than the traditional registration techniques. Moreover, the scheme registers images taken directly by hand-held digital camera without knowing camera motion and any intrinsic parameters of camera.

The main contribution of this work is a new paradigm for image compression. We describe a new multi-layered representation technique for images. An image is encoded as the superposition of one main approximation, and a sequence of residuals. The strength of the multi-layered method comes from the fact that we use different bases to encode the main approximation and the residuals. For instance, we can use: a wavelet basis to encode a coarse main approximation of the image, wavelet packet bases to encode textured patterns, brushlet bases to encode localized oriented textured features, etc.

We propose a conceptually simple method for lossless compression of medical image and volume data. The method can be divided into three steps: the input data is decomposed into several subbands with the help of nonlinear lifting filters, the resulting subbands are block-sorted according to a method suggested by Burrows and Wheeler, and the redundancy is removed with the help of an adaptive arithmetic coder. Moreover, we suggest a new method to implement (non-linear) lifting filters. We describe these filters with the help of a small filter description language, which is compiled into a shared object file and dynamically loaded at run time. The source code of the program is freely available for testing purposes.

We address the problem of improving the performance of wavelet based fractal image compression by applying efficient triangulation methods. We construct iterative function systems (IFS) in the tradition of Barnsley and Jacquin, using non-uniform triangular range and domain blocks instead of uniform rectangular ones. We search for matching domain blocks in the manner of Zhang and Chen, performing a fast wavelet transform on the blocks and eliminating low resolution mismatches to gain speed. We obtain further improvements by the efficiencies of binary triangulations (including the elimination of affine and symmetry calculations and reduced parameter storage), and by pruning the binary tree before construction of the IFS. Our wavelets are triangular Haar wavelets and `second generation' interpolation wavelets as suggested by Sweldens' recent work.

In highly computationally intensive fields such as signal processing, image processing, computer graphics and visualization, much of the CPU time is spent in computing various transforms on the typically large data sets which may also contain noise. Though extensive work has been reported on the de-noising and subsequent compression of the data, little of it has been reported on the de-noising and subsequent compression of the operators. Moreover, in the work reported so far, thresholding, which is essential for achieving denoising, has not been based on a specific criterion. In the present work, we propose modifications to this approach which result in significant savings in the computational cost of the associated transformations. We present wavelet based approaches to compress different operators. We present two methods to accomplish this. In the first method, we first apply a non-standard wavelet transform on the operator represented in its matrix form. This step is followed by an adaptive thresholding scheme of Donohoe and Johnstone, which results in the de-noised form of the operator. In the second method, the original matrix representation of the operator is split into two sparse diagonal dominant matrices, one in the spatial domain and the other in the wavelet domain. Although, there is a need to use the original signal in the spatial domain, the resulting decomposition actually requires only a portion of the operators. More importantly, the decomposition results in representations with very little total error. We find that the computational complexity of the transformation, using these methods, reduces to O(N²) (where N is the size of the data vector) observed with using the original, denser representation of the operator. In particular, Method 2 allows even more expedient processing of signals with greater accuracy. Hence, many transformations with operators can be represented in a diagonally dominant matrix form resulting in significant savings.

A wavelet-based image matching method was developed for removal of normal anatomic structures in chest radiographs for reduction of false positives reported by our computer- aided diagnosis (CAD) scheme for detection of lung nodules. In our approach, two regions of interest (ROIs) are extracted, one from the position where a candidate of a nodule is located, and the other from the position located at a point symmetric to the first position relative to the spine. The second ROI contains normal anatomic structures similar to those of the first ROI. A non-linear functional representing the squared differences between the two images is formulated, and is minimized by a coarse-to-fine approach to yield a planar mapping that matches the two similar images. A smoothing term is added to the non-linear functional, which penalizes discontinuous and irregular mappings. If no structure remains in the difference between these matched images, then the first ROI is identified to be a false detection (i.e., it contains only normal structures); otherwise, it is regarded as a nodule (i.e., it contains an abnormal structure). A preliminary result shows that our method is effective in removing normal anatomic structures and thus is useful for substantially reducing the number of false detections in our CAD scheme.

In this paper, a new feature extraction technique, which is based on multiwavelet frame, is introduced and its application to MRI feature extraction is investigated. Energy calculation is used as the nonlinearity of the feature extraction procedure. An optimal linear transformation is applied to the resulting features to map them onto a 3D subspace in which normal tissues are orthonormal. For brain images, this subspace corresponds to three images which illustrate projections (similarities) of abnormal tissues to each of the normal tissues of the human brain (white matter, gray matter, CSF). The three images, referred to as eigenimages, are useful in diagnosis and treatment of patients with brain abnormalities. We show that the proposed feature extraction method extracts certain brain tumor texture features, which are otherwise invisible. The method is therefore expected to enhance image analysis of MRI studies of brain tumor patients.

We describe experiments that we have performed that address the issue of the relation between the same enunciations by different speakers. Our previous work indicated that frequencies are approximately scaled uniformity. In this paper we report results addressing possible corrections to uniform scaling. Our results show that the scaling is non uniform, that is the format frequencies of different speakers scale differently at different frequencies. We discuss how this leads to the mathematical issue of separating the spectrum into a speaker dependent and speaker independent parts. We introduce the concept of a universal scaling function that is aimed at achieving this separation. The fundamental idea is to find a frequency axis transformation (warping function) which transforms the energy density spectrum (the squared absolute value of the Fourier transform of the enunciation) in such a way that a further Fourier transform of the resulting function achieves this separation. We discuss this procedure and relate it to the scale transform. Using real speech data we obtain such a transformation function. The resulting function is very similar to the Mel scale, which has been previously obtained only from psychoacoustic (hearing based) experiments. That similar scales are obtained from both hearing and speech production (as reported here) is fundamental to the understanding of speech and hearing.

The purpose of this paper is to present a method of pattern recognition applied to detect discrimination in objects manufactured in plastic, metal, glass... This discrimination is needed to avoid problems during the recycling process. Nowadays, the controls are realized by an operator who checks visually these objects. As in texture segmentation, a way to limit the data which much be analyzed, is to use orthogonal transformations. In an industrial background, one of the most interesting transformations is the orthogonal wavelet decomposition. Remaining in the image vector space, this decomposition allows a multi resolution analysis and keeps quite all the original information in the subimages. Applied to industrial objects presenting a complex textured aspect, all the wavelets (Haar, bi-orthogonal...) need post- processing to display the defects. As these defects are seen like texture breakdowns, they can be located in high frequency spatial domain. This has led us to choose Daubechies wavelets that concentrate correctly the useful information in the detail subimages. We show that the defect is more clearly apparent at a given resolution level than in the original image. We give criteria that allow the determination of this optimal resolution level. We present a method that allows the reconstruction of the defect, using the subimages. The defect, appearing on a black background, is then discriminated by an adapted classical pattern recognition method.

Fast algorithms performing time-scale analysis of multivariate functions are discussed. The algorithms employ univariate wavelets and involve a directional parameter, namely the angle of rotation. Both the rotation steps and the wavelet analysis/synthesis steps in the algorithms require a number of computations proportional to the number of data involved. The rotation and wavelet techniques are used for the segregation of wanted and unwanted components in a seismic signal. As an illustration, the rotation and wavelet methods are applied to a synthetic shot record.

We explore the filtering properties of wavelets functions in order to develop accurate and efficient numerical algorithms for Image Restoration problems. We propose a parallel implementation for MIMD distributed memory environments. The key insight of our approach is the use of distributed versions of Level 3 Basic Linear Algebra Subprograms as computational building blocks and the use of Basic Linear Algebra Communication Subprograms as communication building blocks for advanced architecture computers. The use of these low-level mathematical software libraries guarantees the development of efficient, portable and scalable high-level algorithms and hides many details of the parallelism from the user's point of view. Numerical experiments on a simulated image restoration applications are shown. The parallel software has been tested on a 12 nodes IBM SP2 available at the Center for Research on Parallel Computing and Supercomputers in Naples (Italy).

Kirchhoff migration operator is a highly oscillatory integral operator. In our previous work (see `Seismic Imaging in Wavelet Domain', Wu and Yang, 1997), we have shown that the matrix representation of Kirchhoff migration operator for homogeneous background in space-frequency domain is a dense matrix, while the compressed beamlet- operator, which is the wavelet decomposition of the Kirchhoff migration operator in beamlet-frequency (space- scale-frequency) domain, is a highly sparse matrix. Using the compressed matrix for imaging, we can obtain high quality images with high efficiency. We found that the compression ratio of the migration operator is very different for different wavelet basis. In the present work, we study the decomposition and compression of Kirchhoff migration operator by adapted wavelet packet transform, and compare with the standard discrete wavelet transform (DWT). We propose a new maximum sparsity adapted wavelet packet transform (MSAWPT), which differs from the well-known Coifman-Wickerhauser's best basis algorithm, to implement the decomposition of Kirchhoff operator to achieve the maximum possible sparsity. From the numerical tests, it is found that the MSAWPT can generate a more efficient matrix representation of Kirchhoff migration operator than DWT and the compression capability of MSAWPT is much greater than that of DWT.

The application of wavelet transform can improve discrimination capability and signal-to-noise ratio of the correlation outputs with respect to the classical one. The concept of the associative storage in a photorefractive material offers suitable methods to design multichannel correlators for fingerprint identification. An optical system that employs holographic recording in a F_e: LiNbO₃ crystal is proposed and experimentally demonstrated for the physical implementation of multichannel wavelet matched correlator. The scale of wavelet filter is optimized according to the robustness to the noise and discriminability of the filter. The photorefractive correlator is used as a ROM in the recognition. When the object beam with an input fingerprint is used for recovering, a set of correlation outputs are obtained in parallel along the directions of the reference beams, and detected by a CCD camera. Experimental results are promising for further use in the practice.

High-resolution optical mapping is an emerging technique to record the activation and propagation of transmembrane potential on the surface of cardiac tissues. Important electrodynamic information previously not available from extracellular electric recording could be extracted from these detailed optical recordings. The noise contamination in the images is a major obstacle that prohibits higher level of information extraction. Because the patterns of interest contain sharp wavefronts and structures that we wish to detect and track in a series of frames, we seek to perform denoising based on wavelet decomposition approaches. Among the wavelet denoise methods that were tested in this preliminary study, the wavelet packet produced the best results that could be extended to denoise the entire image sequence for multi-dimensional information processing.

We present planar curve descriptors that allow a hierarchical representation of curves. The descriptors are based on wavelet and multiwavelet transforms and they decompose a curve into components of different scales.