 Astronomy
 Biomedical Optics & Medical Imaging
 Defense & Security
 Electronic Imaging & Signal Processing
 Illumination & Displays
 Lasers & Sources
 Micro/Nano Lithography
 Nanotechnology
 Optical Design & Engineering
 Optoelectronics & Communications
 Remote Sensing
 Sensing & Measurement
 Solar & Alternative Energy
 Sign up for Newsroom EAlerts
 Information for:
Advertisers




Electronic Imaging & Signal Processing
Improved signal representations using rational dilation factors
İlker Bayram and Ivan Selesnick
Enhancing wavelettransform performance by allowing for rational dilation factors is much easier if the generalized transforms are also overcomplete.
14 July 2008, SPIE Newsroom. DOI: 10.1117/2.1200806.1198
Wavelet transforms (WTs) are used in numerous signal and imageprocessing applications including compression, denoising, deblurring, sharpening, dequantization, interpolation, demosaicking, and waveform classification. WTs are based on signal analysis at several levels of resolution. In most applications, particularly those requiring that the transform is invertible, the resolution is doubled from one level to the next: the dilation factor is two and the WT is ‘dyadic.’ We have recently developed^{1,2} a new approach based on rational dilation factors of between one and two, where the resolution increases more gradually from one level to the next. Figure 1. Analysis functions for the first few levels of (a) a dyadic orthonormal wavelet transform (WT) and (b) a rational wavelet frame (with a dilation factor of 4/3), where the duration and frequency change more gradually from one resolution level to the next. Orthonormal WTs using rational schemes have been explored and developed by a number of groups. However, several issues complicate their effective use compared with their dyadic counterparts. First, the underlying theory^{3,4,5,6} is significantly more complicated. Secondly, the design of good digital filters^{7,8} with which to implement a discrete WT is significantly more difficult. In particular, Daubechies’ celebrated construction of short filters with vanishingmoment properties^{9} cannot be extended to the rational case. In fact, only a few finitelength filters with more than one vanishing moment have been constructed for the latter, which must be done by exact arithmetic computation over several days using Gröbnertype methods.^{1} Moreover, the frequency selectivity and differentiability of the resulting analysis functions are quite poor. Thirdly, the rational WTs associated with using these filters are outperformed by the orthonormal dyadic WTs. However, for overcomplete rational WTs or ‘frames’ the situation is quite different. Frames are transforms that expand an Npoint signal to L transform coefficients, with L > N. Frames have become a wellrecognized tool^{10} in signal processing for enhancing the performance of many transformdomain algorithms, such as waveletbased denoising. Short filters with vanishingmoment properties, useful for the construction of selfinverting rational wavelet frames, can be constructed by solving a polynomialmatrix spectral factorization^{11} problem. The filters generate highlydifferentiable analysis functions (see Figure 1) which cover the frequency domain more densely (see Figure 2). The resulting frames perform well and are approximately shift invariant. They can also approximate continuous WTs (CWTs). Yet, unlike CWTs, they are easily and efficiently inverted. Figure 2. Frequency analyses provided by (a) a dyadic orthonormal WT and (b) a rational wavelet frame. Both selfinverting transforms are implemented with digital finiteimpulse response filters, although the frame provides a denser frequency coverage. Rational wavelet frames are also promising alternatives to the widelyused undecimated discrete WTs (UDWTs) or ‘stationary’ WTs. Such WTs are exactly shift invariant, easily invertible, can be implemented using filters designed for orthonormal WTs (i.e., Daubechies’ filters can be applied), and reliably improve the performance of waveletbased signalprocessing algorithms compared with orthonormal WTs. However, UDWTs can be highly redundant: a Jlevel UDWT is J+1 times overcomplete. For very long signals and large images UDWTs may require more memory and computing time than is practical. On the other hand, the rational wavelet frame has a fixed redundancy rate independent on the number of levels, so it can be used to analyze large data sets without incurring these high memory and computingtime costs. (The redundancy does not increase with the number of levels either for dualtree complex or partiallydecimated WTs.) In addition, rational frames sample the time–frequency (T–F) plane more efficiently than UDWTs. As shown in Figure 1, these frames oversample both the time and frequency axes of the T–F plane, whereas UDWTs oversample only the time axis (not shown). Figure 3. Time–frequency distribution of the analysis functions of (a) a dyadic orthonormal WT and (b) a rational wavelet frame. The frame samples the time–frequency plane more densely and thus approximates the continuous WT. Frames provide an efficient scheme for signal processing based on their T–F characteristics. Because the rational wavelet frame serves as an approximate CWT, analysis methods based on singularity detection and classification and wavelet skeletons, among others, can be employed in an analysissynthesis mode because rational WTs are easily invertible. These frames may serve as a practical link between invertible discrete WTs and CWTs. To design effective finiteimpulse response (FIR) filters for the construction of rational wavelet frames, we need vanishing moments and regularity conditions and we seek the filters having the shortest timedomain responses. For a rational frame with dilation factor p/q, the vanishingmoment and regularity conditions can be satisfied by choosing a lowpass filter with a transfer function that has both zeros at the pth and qth roots of unity and a flat response at zero frequency. To demonstrate the performance of rational wavelet frames we carried out a denoising experiment. We added unitvariance white Gaussian noise to a piecewise smooth signal of length 2000, performed soft thresholding of the coefficients using several overcomplete transforms, and computed the rootmeansquare (rms) error as a function of the threshold value. The overcomplete transforms used were the UDWT and rational wavelet frame with dilation factors of 3/2 and 4/3, respectively. The result (see Figure 4) indicates that the frame outperforms the UDWT, even though it is less redundant than the UDWT. By increasing the rational dilation factor to 4/3, and hence sampling the T–F plane more densely and making the transform more redundant (at a redundancy rate of about 4), we obtain even better performance. Although not shown, the orthonormal discrete WT performance is inferior to that of the UDWT. Figure 4. Denoising results for the rational wavelet frame (with dilation factors of 3/2 and 4/3) and the undecimated discrete WT (UDWT). The curves show the rootmeansquare (rms) error averaged over 100 realizations as a function of the threshold, T. Even though the rational wavelet frame is less redundant than the UDWT, it provides better performance. In summary, we can construct overcomplete discrete WTs based on rational dilation factors that are efficiently implemented with FIR digital filter banks, easily invertible, designed according to vanishingmoment and regularity conditions, and approximately shift invariant. Moreover, because this type of overcomplete transform provides a dense sampling of the T–F plane, it may serve as an approximate CWT which, unlike most similar implementations, is exactly invertible and not as redundant. The transform may be useful for future applications that require tracking of signal features in the T–F plane and/or finer frequency analysis than those provided by the common dyadic WTs.
İlker Bayram, Ivan W. Selesnick Department of Electrical and Computer Engineering Polytechnic University Brooklyn, NY İlker Bayram received his BSc and MSc in electrical and electronics engineering from the Middle East Technical University in Ankara, Turkey in 2002 and 2004, respectively. Following a year of graduate study at Bilkent University in Ankara, he has been a research assistant at Polytechnic University since 2005. Ivan W. Selesnick obtained his BS, MEE, and PhD in electrical and computer engineering from Rice University in Houston, TX, in 1990, 1991, and 1996, respectively. He has been at the Department of Electrical and Computer Engineering at Polytechnic University since 1997, where he is currently an associate professor. His research interests relate to signal and image processing. He is an associate editor of IEEE Signal Processing Letters.


