We specialize to two simple cases the algorithm for singularity detection in images from eigenvalues of the dual local autocovariance matrix. The eigenvalue difference, or "edginess" at a point, then reduces to a simple nonlinear function. We discuss the derivation of these functions, which provide low-complexity nonlinear edge filters with parameters for customization, and obtain formulas in the two simplest special cases. We also provide an implementation and exhibit its output on six sample images.
Wavelet and wavelet packet transforms are presently used for image compression and denoising. There has been recent progress on three fronts: implementing multiplication operations in wavelet bases, estimating compressibility by wavelet packet transform coding, and designing wavelet packets to control frequency spreading and pointwise convergence. Some open problems are mentioned.
Wavelet transform coding image compression is applied to two raw seismic data sets. The parameters of filter length, depth of decomposition, and quantization method are varied through 36 parameter settings and the rate-distortion relation is plotted and fitted with a line. The lines are compared to judge which parameter setting produces the highest quality for a given compression ratio on the sample data. It is found that long filters, moderate decomposition depths, and frequency-weighted, variance-adjusted quantization yield the best results.
We briefly survey how to use libraries of (orthonormal) bases of well-behaved waveforms, including wavelets and lapped orthogonal transforms, so as to obtain fast numerical algorithms for the expansion of functions and operators in these bases. The most important applications are fast approximate matrix multiplication, and application of matrices to vectors.
We consider the following pair of problems related to orthonormal compactly supported wavelet expansions: (1) Given a wavelet coefficient with its nominal scale and position indices, find the precise location of the transient signal feature which produced it; (2) Given two collections of wavelet coefficients, determine whether they arise from a periodic signal and its translate, and if so find the translation which maps one into the other. Both problems may be solved by traditional means after inverting the wavelet transform, but we propose two alternative algorithms which rely solely on the wavelet coefficients themselves.
We use large libraries of template waveforms with remarkable orthogonality properties to recast the relatively complex principal orthogonal decomposition (POD) into an optimization problem with a fast solution algorithm. Then it becomes practical to use POD to solve two related problems: recognizing or classifying images, and inverting a complicated map from a low-dimensional configuration space to a highdimensional measurement space. In the case where the number N of pixels or measurements is more than 1000 or so, the classical O(N3) POD algorithm becomes very costly, but it can be replaced with an approximate best-basis method that has complexity O(N2 logN). A variation of POD can also be used to compute an approximate Jacobian for the complicated map.
We describe the development of adapted waveform analysis (AWA) as a tool for fast processing of the various identification tasks involved in medical diagnostics and automatic target recognition. Such tasks consist of steps: representing the signal as a superposition of component functions, choosing to retain some of the components and discard the others, then reconstructing a new, approximate signal from what was kept. AWA provides tools for each of these steps, accelerating the decomposition and reconstruction computations, providing new functions for analysis and modeling, and extracting new features for recognition and classification. AWA extends Fourier analysis by providing new libraries of standard waveforms with properties akin to windowed sines and cosines, and it extends principal component analysis and eigen-function expansions by adapting the standard functions to individual operators. The cost of representing a function can be measured by how many components must be superposed to obtain a desired degree of approximation, and this cost can be minimized by a fast search through the library of representations. The analysis can be iterated to sift coherent signals from noise. We consider applications to signal and image compression, feature detection, and medical image denoising.
Principal orthogonal decomposition can be used to solve two related problems: distinguishing elements from a collection by making d measurements, and inverting a complicated map from a p- parameter configuration space to a d-dimensional measurement space. In the case where d is more than 1000 or so, the classical O(d3) singular value decomposition algorithm becomes very costly, but it can be replaced with an approximate best-basis method that has complexity O(d2 log d). This can be used to compute an approximate Jacobian for a complicated map from Rp to Rd in the case where p is much less than d.
The principal orthogonal factor analysis or Karhunen-Loeve algorithm may be sped up by a low-complexity preprocessing step. A fast transform is selected from a large library of wavelet-like orthonormal bases, so as to maximize transform coding gain for an ensemble of vectors. Only the top few coefficients in the new basis, in order of variance across the ensemble, are then decorrelated by diagonalizing the autocovariance matrix. The method has computational complexity O(d2 log d + d'3) and O(d log d + d'2) respectively for training and classifying a d-dimensional system, where d' << d. One application is described, the reduction of an ensemble of 16,384 pixel face images to a 10 parameter space using a desktop computer, retaining 90% of the variance of the ensemble.
SC475: Survey of Wavelet Algorithms and Applications
This course will include a brief description of wavelets and wavelet packets, followed by a moderately detailed survey of fast discrete wavelet transform algorithms and implementations. Emphasis will be placed on the "lifting" implementation, treatment of boundaries, and wavelet and basis selection, keyed to the transforms used in the WSQ and JPEG2000 image compression algorithms. The related lapped orthogonal transforms will be discussed as well.