2D Transforms

2D Wavelets and Multiscale Transforms

The Morlet-Grossmann definition (Grossman et al., 1989) of the continuous wavelet transform for a 1-dimensional signal $ f(x)\in L^2(R)$, the space of all square integrable functions, is:

$\displaystyle W(a,b)=\frac{1}{\sqrt a}\int_{-\infty}^{+\infty}f(x) \psi^* \left( \frac{x-b}{a} \right) dx$     (1)

where: Many discrete wavelet transform algorithms have been described (Starck et al., 1998). The most widely-known one is certainly the orthogonal one, proposed by Mallat (1989) and its bi-orthogonal version. By this algorithm, the transformation of an image is an image. Some of the other algorithms do not produce an image, but a pyramid, or cube. So we separate the different wavelet transform algorithms into classes, depending on the output data type. Other multiscale methods, which are nonlinear can also be categorized in this way. We distinguish between fives classes of multiscale transform: The first three, and the last, are redundant (i.e. there are more pixels in the transformation than in the input data).

  1. Cube transform For the first class, the input image $ I$ can be expressed as (Bijaoui et al., 1994, Murtagh et al., 1995a, b):
    $\displaystyle I(x,y) = c_p (x,y) + \sum_{j=1}^{p} w_j(x,y)$     (2)

    $ w_j$ (for $ j=1 \dots p$) and $ c_p$ represent the transformation of $ I$. $ c_p$ is a very smoothed version of the image $ I$, and $ w_j$ is the image which contains information at scale $ j$. The transformation is defined by $ n=p+1$ images ($ n = $ number of scales). The $ p$ images have zero mean (or approximately zero, for nonlinear transforms). Each of them corresponds to the information at a given scale, i.e. structure of a given size in the input image. Compact structures (with size of one or two pixels) will be found at the first scale ($ j=1$). For this class of transformation, which is very redundant, the amount of data is multiplied by the number of scales $ n$. Therefore this takes a lot of memory, but the multiresolution coefficients ($ w_j(x,y)$) are easy to interpret.

  2. Pyramidal transform

    The second class of transformation is less redundant. The first scale has the same size as the image, but for the other scales, the number of pixels is reduced by four at each resolution. Thus, if $ N^2$ is the number of pixels of $ I$, the number of pixels of the transformation is $ 4/3N^2$.

  3. Half-pyramidal transform This transform (Bijaoui et al., 1992) is relatively close to the previous one, but the two first scales are not decimated (i.e. they have the same size as the input image). See Appendix D for more details.

  4. Non-redundant transform

    The last class is completely non-redundant, and the number of pixels is the same as in the input image. This means that it is an image. Using the Mallat transform, at a given resolution, the image is shared between four parts. Three subimages correspond to details of the image in the horizontal, vertical, and diagonal directions, and the last part corresponds to the image at a lower resolution. The process can then be repeated on the image at the lower resolution. The Haar wavelet transform, lifting scheme transform, and the G transform (which is a nonlinear transform based on the minimum and the maximum) produce the same kind of representation.

    The Feauveau transform (Feauveau, 1990) is not redundant, but the representation is different. There is no prioritized direction, and we have an intermediate resolution (half resolution).

  5. Directional cube transform In this case, just as for the orthogonal Mallat transform, the analysis is directional, but there is no decimation. This means that the number of output bands is equal to the number of scales multiplied by the number of directions, and each band has the same number of pixels as the input image. In practice, two directions are used (vertical and horizontal).

Since the output differs following the chosen algorithm, we will define the term band as the number of subimages included in a given dyadic scale. For the cube and pyramid transforms, the number of bands is equal to the number of scales. For the Mallat algorithm, we have three bands per scale. For the Feauveau and the directional cube methods, we have two bands per scale. The table indicates for each MR/1 algorithm its class, the number of bands per scale, and if it is redundant and linear.


Table 1: Multiscale transform algorithms.
Multiscale algorithm Class Redund- Bands Linear
    ant per scale  
1: linear WT Cube Yes 1 Yes
2: B-spline WT Cube Yes 1 Yes
3: wavelet transform in Fourier space Cube Yes 1 Yes
4: morphological median transform (MT) Cube Yes 1 No
5: morphological minmax transform Cube Yes 1 No
6: pyramidal linear WT Pyramid Yes 1 Yes
7: pyramidal B-spline WT Pyramid Yes 1 Yes
8: pyramidal WT in Fourier space: alg. 1 Pyramid Yes 1 Yes
9: pyramidal WT in Fourier space: alg. 2 Pyramid Yes 1 Yes
10: pyramidal median transform Pyramid Yes 1 No
11: pyramidal Laplacian Pyramid Yes 1 No
12: morph. pyramidal minmax transform Pyramid Yes 1 No
13: decomposition on scaling function Pyramid Yes 1 No
14: (bi-) orthogonal wavelet transform Image No 3 Yes
14-1: Antonini 7/9 filter        
14-2: Daubechies filter        
14-3: Haar filter        
14-4: Odegard 7/9 filters        
15: Feauveau WT Image No 2 Yes
16: Feauveau WT without undersampling Cube Yes 2 Yes
17: G transform (morph. min-max alg.) Image No 3 No
18: Haar wavelet transform Image No 3 Yes
19: Half-pyramidal transform Half-Pyramid Yes 1 Yes
20: Mixed Half-pyramidal and MT Half-Pyramid Yes 1 No
21: Dyadic wavelet transform Cube Yes 2 Yes
22: Mixed WT and PMT method Pyramid Yes 1 No
23: Undecimated Haar transform Cube Yes 1 Yes
24: Wavelet transform via lifting scheme Image No 3  
24-1: CDF WT       Yes
24-2: Median prediction       No
24-3: integer Haar WT       No
24-4: integer CDF WT       No
24-5: integer (4,2) interpolating transform       No




Bibliography

1
M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies.
Image coding using wavelet transform.
IEEE Transactions on Image Processing, 1(2):205-220, 1992.

2
A. Bijaoui, F. Rué, and B. Vandame.
Multiscale vision and its application to astronomy.
In Proceedings of the Fifth Workshop in Data Analysis in Astronomy, pages 337-343. World Scientific, 1992.

3
A. Bijaoui, J.L. Starck, and F. Murtagh.
Restauration des images multi-échelles par l'algorithme à trous.
Traitement du Signal, 3:11, 1994.

4
I. Daubechies.
Orthogonal bases of compactly supported wavelets.
Communications in Pure and Applied Mathematics, 41:909-996, 1988.

5
J.C. Feauveau.
Analyse multirésolution par ondelettes non-orthogonales et bancs de filtres numériques.
PhD thesis, Université Paris Sud, 1990.

6
A. Grossmann, R. Kronland-Martinet, and J. Morlet.
Reading and understanding continuous wavelet transform.
In J.M. Combes., A. Grossmann., and Ph. Tchamitchian, editors, Wavelets: Time-Frequency Methods and Phase-Space, pages 2-20. Springer Berlin, 1989.

7
S. G. Mallat.
A theory for multiresolution signal decomposition: the wavelet representation.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(7):674-693, 1989.

8
F. Murtagh, J.L. Starck, and A. Bijaoui.
Image analysis using multiresolution: New results.
ST-ECF Newsletter, 22:6-8, 1995.

9
F. Murtagh, J.L. Starck, and A. Bijaoui.
Multiresolution in astronomical image processing: A general framework.
The International Journal of Image Systems and Technology, 6:332-338, 1995.

10
J.L. Starck, F. Murtagh, and A. Bijaoui.
Image Processing and Data Analysis: The Multiscale Approach.
Cambridge University Press, Cambridge (GB), 1998.