Wavelet for multidimensional signals analysis

Wavelets are often used to analyse piece-wise smooth signals. Wavelet coefficients can efficiently represent a signal which has led to data compression algorithms using wavelets. Wavelet analysis is extended for multidimensional signal processing as well. This article introduces a few methods for wavelet synthesis and analysis for multidimensional signals. There also occur challenges such as directivity in multidimensional case.

Multidimensional separable discrete wavelet transform (DWT)

The discrete wavelet transform is extended to the multidimensional case using the tensor product of well known 1D wavelets.

In 2D for example, the tensor product space for 2D is decomposed into four tensor product vector spaces as

(φ(x) ⨁ ψ(x)) ⊗ (φ(y) ⨁ ψ(y)) = { φ(x)φ(y), φ(x)ψ(y), ψ(x)φ(y), ψ(x)ψ(y) }

This leads to the concept of multidimensional separable DWT similar in principle to the multidimensional DFT.

φ(x)φ(y) gives the approximation coefficients and other subbands:

φ(x)ψ(y) low-high (LH) subband,

ψ(x)φ(y) high-low (HL) subband,

ψ(x)ψ(y) high-high (HH) subband,

give detail coefficients.

Implementation of multidimensional separable DWT

Wavelet coefficients can be computed by passing the signal to be decomposed though a series of filters. In the case of 1D, there are two filters at every level-one low pass for approximation and one high pass for the details. In the multidimensional case, the number of filters at each level depends on the number of tensor product vector spaces. For M-D, 2M filters are necessary at every level. Each of these is called a subband. The subband with all low pass (LLL...) gives the approximation coefficients and all the rest give the detail coefficients at that level. For example, for M=3 and a signal of size N1 × N2 × N3 , a separable DWT can be implemented as follows:

The figure depicts 3D separable DWT procedure by applying 1D DWT for each dimension and splitting the data into chunks to obtain wavelets for different subbands

Applying the 1D DWT analysis filterbank in dimension N1, it is now split into two chunks of size N1⁄2 × N2 × N3. Applying 1D DWT in N2 dimension, each of these chunks is split into two more chunks of N1⁄2 × N2⁄2 × N3. This repeated in 3D gives a total of 8 chunks of size N1⁄2 × N2⁄2 × N3⁄2.

The figure shows the 3D analysis filterbank for 3D separable DWT

Disadvantages of M-D separable DWT

The wavelets generated by the separable DWT procedure are highly shift variant. A small shift in the input signal changes the wavelet coefficients to a large extent. Also, these wavelets are almost equal in their magnitude in all directions and thus do not reflect the orientation or directivity that could be present in the multidimensional signal. For example, there could be an edge discontinuity in an image or an object moving smoothly along a straight line in the space-time 4D dimension. A separable DWT does not fully capture the same. In order to overcome these difficulties, a method of wavelet transform called Complex wavelet transform (CWT) was developed.

Multidimensional complex wavelet transform

Similar to the 1D complex wavelet transform, tensor products of complex wavelets are considered to produce complex wavelets for multidimensional signal analysis. With further analysis it is seen that these complex wavelets are oriented. This sort of orientation helps to resolve the directional ambiguity of the signal.

Implementation of multidimensional (M-D) dual tree CWT

Dual tree CWT in 1D uses 2 real DWTs, where the first one gives the real part of CWT and the second DWT gives the imaginary part of the CWT. M-D dual tree CWT is analyzed in terms of tensor products. However, it is possible to implement M-D CWTs efficiently using separable M-D DWTs and considering sum and difference of subbands obtained. Additionally, these wavelets tend to be oriented in specific directions.

Two types of oriented M-D CWTs can be implemented. Considering only the real part of the tensor product of wavelets, real coefficients are obtained. All wavelets are oriented in different directions. This is 2m times as expansive where m is the dimensions.

If both real and imaginary parts of the tensor products of complex wavelets are considered, complex oriented dual tree CWT which is 2 times more expansive than real oriented dual tree CWT is obtained. So there are two wavelets oriented in each of the directions. Although implementing complex oriented dual tree structure takes more resources, it is used in order to ensure an approximate shift invariance property that a complex analytical wavelet can provide in 1D. In the 1D case, it is required that the real part of the wavelet and the imaginary part are Hilbert transform pairs for the wavelet to be analytical and to exhibit shift invariance. Similarly in the M-D case, the real and imaginary parts of tensor products are made to be approximate Hilbert transform pairs in order to be analytic and shift invariant.

Consider an example for 2D dual tree real oriented CWT:

Let ψ(x) and ψ(y) be complex wavelets:

ψ(x) = ψ(x)h + j ψ(x)g and ψ(y) = ψ(y)h + j ψ(y)g.

ψ(x,y) = [ψ(x)h + j ψ(x)g][ ψ(y)h + j ψ(y)g] = ψ(x)hψ(y)h - ψ(x)gψ(x)g + j [ψ(x)hψ(y)g - ψ(x)hψ(x)g]

The support of the Fourier spectrum of the wavelet above resides in the first quadrant. When just the real part is considered, Real(ψ(x,y)) = ψ(x)hψ(y)h - ψ(x)gψ(x)g has support on opposite quadrants (see (a) in figure). Both ψ(x)hψ(y)h and ψ(x)gψ(y)g correspond to the HH subband of two different separable 2D DWTs. This wavelet is oriented at -45o.

Similarly, by considering ψ2(x,y) = ψ(x)ψ(y)*, a wavelet oriented at 45o is obtained. To obtain 4 more oriented real wavelets, φ(x)ψ(y), ψ(x)φ(y), φ(x)ψ(y)* and ψ(x)φ(y)* are considered.

The implementation of complex oriented dual tree structure is done as follows: Two separable 2D DWTs are implemented in parallel using the filterbank structure as in the previous section. Then, the appropriate sum and difference of different subbands (LL, LH, HL, HH) give oriented wavelets, a total of 6 in all.

The figure shows the Fourier support of all 6 oriented wavelets obtained by a 2D real oriented dual tree CWT

Similarly, in 3D, 4 separable 3D DWTs in parallel are needed and a total of 28 oriented wavelets are obtained.

Disadvantage of M-D CWT

Although the M-D CWT provides one with oriented wavelets, these orientations are only appropriate to represent the orientation along the (m-1)th dimension of a signal with m dimensions. When singularities in manifold of lower dimensions are considered, such as a bee moving in a straight line in the 4-D space-time, oriented wavelets that are smooth in the direction of the manifold and change rapidly in the direction normal to it are needed. A new transform, Hypercomplex Wavelet transform was developed in order to address this issue.

Hypercomplex wavelet transform

The dual tree hypercomplex wavelet transform (HWT) developed in consists of a standard DWT tensor and 2m -1 wavelets obtained from combining the 1D Hilbert transform of these wavelets along the n-coordinates. In particular a 2D HWT consists of the standard 2D separable DWT tensor and three additional components:

Hx {ψ(x)hψ(y)h} = ψ(x)gψ(y)h

Hy {ψ(x)hψ(y)h} = ψ(x)hψ(y)g

Hx Hy {ψ(x)hψ(y)h} = ψ(x)gψ(y)g

For the 2D case, this is named dual tree quaternion wavelet transform (QWT). The total redundancy in M-D is 2m tight frame.

Directional hypercomplex wavelet transform

The hypercomplex transform described above serves as a building block to construct the directional hypercomplex wavelet transform (DHWT). A linear combination of the wavelets obtained using the hypercomplex transform give a wavelet oriented in a particular direction. For the 2D DHWT, it is seen that these linear combinations correspond to the exact 2D dual tree CWT case.

For 3D, the DHWT can be considered in two dimensions, one DHWT for n = 1 and another for n = 2. For n = 2, n = m-1, so, as in the 2D case, this corresponds to 3D dual tree CWT. But the case of n = 1 gives rise to a new DHWT transform. The combination of 3D HWT wavelets is done in a manner to ensure that the resultant wavelet is lowpass along 1D and bandpass along 2D. In, this was used to detect line singularities in 3D space.

Challenges ahead

The wavelet transforms for multidimensional signals are often computationally challenging which is the case with most multidimensional signals. Also, the methods of CWT and DHWT are redundant even though they offer directivity and shift invariance.

References

  1. ↑ Mallat, Stéphane (2008). A Wavelet Tour of Signal Processing. Academic Press.
  2. ↑ Devore, R.A.; Jawerth, B.; Lucier, B.J. (1991). "Data compression using wavelets: Error, smoothness and quantization". [1991] Proceedings. Data Compression Conference. pp. 186–195. doi:10.1109/DCC.1991.213386. ISBN 978-0-8186-9202-4. S2CID 11964668.
  3. ↑ Kugarajah, Tharmarajah; Zhang, Qinghua (November 1995). "Multidimensional wavelet frames". IEEE Transactions on Neural Networks. 6 (6): 1552–1556. doi:10.1109/72.471353. hdl:1903/5619. PMID 18263450.
  4. ↑ Cheng-Wu, Po; Gee-Chen, Liang (7 August 2002). "An efficient architecture for two-dimensional discrete wavelet transform". IEEE Transactions on Circuits and Systems for Video Technology. 11 (4): 536–545. doi:10.1109/76.915359.
  5. ↑ Kingsbury, Nick (2001). "Complex Wavelets for Shift Invariant Analysis and Filtering of Signals". Applied and Computational Harmonic Analysis. 10 (3): 234–253. doi:10.1006/acha.2000.0343.
  6. 1 2 Selesnick, Ivan; Baraniuk, Richard; Kingsbury, Nick (2005). "The Dual-Tree Complex Wavelet Transform". IEEE Signal Processing Magazine. 22 (6): 123–151. Bibcode:2005ISPM...22..123S. doi:10.1109/MSP.2005.1550194. hdl:1911/20355. S2CID 833630.
  7. ↑ Selesnick, I.W. (June 2001). "Hilbert transform pairs of wavelet bases". IEEE Signal Processing Letters. 8 (6): 170–173. Bibcode:2001ISPL....8..170S. doi:10.1109/97.923042. S2CID 5994808.
  8. ↑ Boothby, W (2003). An Introduction to Differentiable Manifolds and Riemannian Geometry. San Diego: Academic.
  9. 1 2 Wai Lam Chan; Hyeokho Choi; Baraniuk, R.G. (2004). "Directional hypercomplex wavelets for multidimensional signal analysis and processing". 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing. Vol. 3. pp. iii–996–9. doi:10.1109/ICASSP.2004.1326715. hdl:1911/19796. ISBN 0-7803-8484-9. S2CID 8287497.
  10. ↑ Lam Chan, Wai; Choi, Hyeokho; Baraniuk, Richard (2008). "Coherent Multiscale Image Processing Using Dual-Tree Quaternion Wavelets". IEEE Transactions on Image Processing. 17 (7): 1069–1082. Bibcode:2008ITIP...17.1069C. doi:10.1109/TIP.2008.924282. PMID 18586616. S2CID 16789586.