SPIE Startup Challenge 2015 Founding Partner - JENOPTIK Get updates from SPIE Newsroom
  • Newsroom Home
  • 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 E-Alerts
  • Information for:
SPIE Defense + Commercial Sensing 2017 | Register Today

OPIE 2017

OPIC 2017




Print PageEmail PageView PDF

Electronic Imaging & Signal Processing

Improved signal representations using rational dilation factors

Enhancing wavelet-transform 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 image-processing 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 developed1,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 theory3,4,5,6 is significantly more complicated. Secondly, the design of good digital filters7,8 with which to implement a discrete WT is significantly more difficult. In particular, Daubechies’ celebrated construction of short filters with vanishing-moment properties9 cannot be extended to the rational case. In fact, only a few finite-length 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öbner-type 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 N-point signal to L transform coefficients, with L > N. Frames have become a well-recognized tool10 in signal processing for enhancing the performance of many transform-domain algorithms, such as wavelet-based denoising. Short filters with vanishing-moment properties, useful for the construction of self-inverting rational wavelet frames, can be constructed by solving a polynomial-matrix spectral factorization11 problem. The filters generate highly-differentiable 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 self-inverting transforms are implemented with digital finite-impulse response filters, although the frame provides a denser frequency coverage.

Rational wavelet frames are also promising alternatives to the widely-used 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 wavelet-based signal-processing algorithms compared with orthonormal WTs. However, UDWTs can be highly redundant: a J-level 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 computing-time costs. (The redundancy does not increase with the number of levels either for dual-tree complex or partially-decimated 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 analysis-synthesis mode because rational WTs are easily invertible. These frames may serve as a practical link between invertible discrete WTs and CWTs.

To design effective finite-impulse 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 time-domain responses. For a rational frame with dilation factor p/q, the vanishing-moment and regularity conditions can be satisfied by choosing a low-pass 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 unit-variance white Gaussian noise to a piecewise smooth signal of length 2000, performed soft thresholding of the coefficients using several overcomplete transforms, and computed the root-mean-square (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 root-mean-square (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 vanishing-moment 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.