Twin Dragon Wavelet

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

This Demonstration shows the iteration process that approximates a continuous-time, twin dragon wavelet basis from the discrete-time one. The iteration is performed on the so-called quincunx lattice. At every iteration, the resulting function tiles the space, even though it has a "fractal" boundary.

[more]

In discrete time, two filters, low pass and high pass, are needed to create a wavelet basis. When iterated on the sampling lattice, they will lead to an equivalent discrete-time scaling function (obtained by repeated upsampling and filtering by the low pass) and an equivalent discrete-time wavelet (obtained by repeated upsampling and filtering by the low pass and a final step by the high pass). In the Demonstration, the low pass and high pass filters are of Haar form (two-point average and difference). The equivalent approximated continuous-time scaling function and wavelet are shown in each iteration; the darker color denotes where the function equals , and the lighter where it is (for the wavelet). The equivalent discrete-time scaling function and wavelet are just single points in each tile (which can be seen by turning on edges). The plots are shown in the new coordinate system at each iteration (this is why they seem to rotate about the origin). The meaning of the zeroth iteration is explained in the Details.

You can observe two effects:

1. Both the scaling function and the wavelet in the current iteration are obtained from two copies of the scaling function from the previous iteration. This is called the "two-scale equation", and can most easily be seen by observing the supports of the wavelet at and ; these supports correspond to the support of the scaling function and its shift from the previous iteration.

2. At every iteration, the support of the scaling function/wavelet and its copies on the lattice (white points) tile the space; this is called a fractal tiling of the plane (check "tile" and only the eight closest tiles are shown).

[less]

Contributed by: Jelena Kovacevic (July 2012)
Open content licensed under CC BY-NC-SA


Snapshots


Details

The twin-dragon construction in this Demonstration is one instance of the generalization of the Haar basis to multiple dimensions. It is based on the work of Lawton and Resnikoff [2], and Gröchenig and Madych [1].

In the one-dimensional continuous-time Haar basis, the associated scaling function equals over the interval and otherwise. In other words, the scaling function can be viewed as the characteristic function of the set . Together with integer translates, this Haar scaling function "covers" the real line. The Haar wavelet, on the other hand, is from to , from to , and otherwise. It can be obtained from two copies of the scaling function of half the length. The idea is to construct analogous multidimensional generalized Haar bases that would have, as scaling functions, characteristic functions of appropriate sets with dilation (scaling) replaced by a suitable linear transformation.

The approach in [1] consists of finding a characteristic function of a compact set (the square in the zeroth iteration in the Demonstration) that would be the scaling function for an appropriate multiresolution analysis. Then to find the wavelets, one would use standard techniques. An interesting property of such scaling functions is that they form self-similar tilings of the plane, a not-quite-intuitive feature for some scaling functions of exotic shapes.

The algorithm for constructing a scaling function for multiresolution analysis with matrix dilation , here

,

basically states that one takes a set of points belonging to different cosets of the lattice, which here has only two elements, and forms a discrete filter equal to on these points. The filter is then iterated following the construction of wavelet bases from iterated filter banks (illustrated in the Demonstration) [4, 5]. If it converges to some compact set, it is an example of a generalized Haar wavelet. In one dimension, this is equivalent to a Haar filter converging to the indicator function of the unit interval.

References

[1] K. Gröchenig and W. R. Madych, "Multiresolution Analysis, Haar Bases, and Self-Similar Tilings of ," IEEE Transactions on Information Theory, 38(2), 1992, pp. 556-568. doi:10.1109/18.119723.

[2] W. M. Lawton and H. L. Resnikoff, Multidimensional Wavelet Bases, Technical report AD910130, AWARE, Inc., Bedford, MA, 1991.

[3] B. Mandelbrot, The Fractal Geometry of Nature, San Francisco: W.H. Freeman, 1982.

[4] M. Vetterli and J. Kovačević, Wavelets and Subband Coding, Englewood Cliffs, NJ: Prentice Hall, 1995. www.waveletsandsubbandcoding.org.

[5] J. Kovačević, V. K Goyal, and M. Vetterli, Signal Processing: Fourier and Wavelet Representations, Cambridge: Cambridge University Press, forthcoming. www.fourierandwavelets.org.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send