Wavelet for multidimensional signals analysis: Difference between revisions

Revision as of 22:35, 11 November 2015

Latest revision as of 06:29, 10 November 2024

(75 intermediate revisions by 15 users not shown)

Line 1:

[[Wavelet]]s are often used to analyse piece-wise smooth signals.<ref>{{cite book|last1=Mallat|first1=Stéphane|title=A Wavelet Tour of Signal Processing|date=2008|publisher=Academic Press}}</ref> Wavelet coefficients can efficiently represent a signal which has led to data compression algorithms such as using wavelets.<ref>{{cite webbook |last1doi=DeVORE10.1109/DCC.1991.213386|first1isbn=RONALD978-0-8186-9202-4|last2chapter=JAWERTH|first2=BJORN|last3=LUCIER|first3=BRADLEY|title=DATAData COMPRESSIONcompression USINGusing WAVELETSwavelets: ERRORError, SMOOTHNESS,smoothness ANDand QUANTIZATIONquantization|urltitle=https://www&#91;1991&#93; Proceedings.math Data Compression Conference|pages=186–195|year=1991|last1=Devore|first1=R.purdueA.edu/~lucier/692/data-compression|last2=Jawerth|first2=B.pdf|last3=Lucier|first3=B.J.|s2cid=11964668 }}</ref> 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 Discretediscrete Waveletwavelet Transformtransform (DWT) ===

{{Orphan|date=November 2015}}

The [[Discretediscrete wavelet transform]] is extended to the multidimensional case is using the [[tensor product]] of well known 1-D wavelets.

In 2-D for example, the tensor product space for 2-D is decomposed into four tensor product vector spaces<ref name=Tensor_products>{{cite journal|last1=Kugarajah|first1=Tharmarajah|last2=Zhang|first2=Qinghua|title=Multidimensional wavelet frames|journal=IEEE Transactions on Neural Networks|date=November 1995|volume=6|issue=6|pages=1552–1556|doi=10.1109/72.471353|pmid=18263450|hdl=1903/5619|hdl-access=free}}</ref> as

{{math| ( &phi;φ(x) ⨁ &psi;ψ(x) ) ⊗ ( &phi;φ(y) ⨁ &psi;ψ(y) ) {{=}} { &phi;φ(x)&phi;φ(y), &phi;φ(x)&psi;ψ(y), &psi;ψ(x)&phi;φ(y), &psi;ψ(x)&psi;ψ(y) }}}

{{Userspace draft|source=ArticleWizard|date=November 2015}}

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

'''Wavelets for multidimensional signal analysis'''

{{math|&phi;φ(x)&phi;φ(y)}} gives the approximation coefficients and other subbands:

== Wavelets for multidimensional signal analysis ==

{{math|&phi;φ(x)&psi;ψ(y)}} low-high (LH) subband,

[[Wavelet]]s are often used to analyse piece-wise smooth signals.<ref>{{cite book|last1=Mallat|first1=Stéphane|title=A Wavelet Tour of Signal Processing|date=2008|publisher=Academic Press}}</ref> Wavelet coefficients can efficiently represent a signal which has led to data compression algorithms such as using wavelets.<ref>{{cite web|last1=DeVORE|first1=RONALD|last2=JAWERTH|first2=BJORN|last3=LUCIER|first3=BRADLEY|title=DATA COMPRESSION USING WAVELETS: ERROR, SMOOTHNESS, AND QUANTIZATION|url=https://www.math.purdue.edu/~lucier/692/data-compression.pdf}}</ref> 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.

{{math|&psi;ψ(x)&phi;φ(y)}} high-low (HL) subband,

=== Multidimensional separable Discrete Wavelet Transform (DWT) ===

[[Discrete wavelet transform]] is extended to the multidimensional case is using the [[tensor product]] of well known 1-D wavelets.

In 2-D for example, the tensor product space for 2-D is decomposed into four tensor product vector spaces as [http://www.uio.no/studier/emner/matnat/math/MAT-INF2360/v12/tensorwavelet.pdf<ref>{{cite web|title=Tensor products in a wavelet setting|url=http://www.uio.no/studier/emner/matnat/math/MAT-INF2360/v12/tensorwavelet.pdf|website=University of Oslo}}</ref>]

{{math|&psi;ψ(x)&psi;ψ(y)}} high-high (HH) subband,

{{math| ( &phi;(x) ⨁ &psi;(x) ) ⊗ ( &phi;(y) ⨁ &psi;(y) ) {{=}} { &phi;(x)&phi;(y), &phi;(x)&psi;(y), &psi;(x)&phi;(y), &psi;(x)&psi;(y) }}}

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

give detail coefficients.

{{math|&phi;(x)&phi;(y)}} gives the approximation coefficients and other subbands:

====DisadvantagesImplementation of M-Dmultidimensional separable DWT= ===

{{math|&phi;(x)&psi;(y)}} low-high (LH) subband,

Wavelet coefficients can be computed by passing the signal to be decomposed though a series of filters.<ref>{{cite web|title=Discrete wavelet transform|url=https://en.wikipedia.org/wiki/Discrete_wavelet_transform|website=Wikipedia|publisher=Wikipedia}}</ref> In the case of 1-D, there are two filters inat every level-one low pass for approximation and one high pass for the details. In the multidimensional case, the number of filters inat each level depends on the number of tensor product vector spaces. For M-D, {{math|2^M}} 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.

{{math|&psi;(x)&phi;(y)}} high-low (HL) subband,

For example, for {{math|M{{=}}3}} and a signal of size {{math| N1 × N2 × N3}} , a separable DWT can be implemented as follows:

[[FileImage:Wiki figures1figures mod.001.pdfpng|thumbnailframed|centernone|The figure depicts 3-D separable DWT procedure by applying 1-D DWT for each dimension and splitting the data into chunks to obtain wavelets for different subbands]]

Applying the 1-D DWT analysis filterbank in dimension {{math|N1}}, it is now split into two chunks of size {{math| {{frac|N1|2}} &times;× N2 &times;× N3}}. Applying 1-D DWT in {{math|N2}} dimension, each of these chunks is split into two more chunks of {{math|{{frac|N1|2}} &times;× {{frac|N2|2}} &times;× N3}}. This repeated in 3-D gives a total of 8 chunks of size {{math| {{frac|N1|2}} &times;× {{frac|N2|2}} &times;× {{frac|N3|2}}}}.<ref>{{cite Thejournal|last1=Cheng-Wu|first1=Po|last2=Gee-Chen|first2=Liang|title=An firstefficient chunkarchitecture isfor passedtwo-dimensional viadiscrete awavelet lowtransform|journal=IEEE passTransactions filteron in each of these dimensionsCircuits and theSystems secondfor oneVideo viaTechnology|date=7 high-pass.August 2002|volume=11|issue=4|pages=536–545|doi=10.1109/76.915359}}</ref>

{{math|&psi;(x)&psi;(y)}} high-high (HH) subband,

[[FileImage:Filterbank mod try 2.pdf001.png|framed|thumbnailnone|The figure shows the 3-D analysis filterbank for 3-D separable DWT]]

give detail coefficients

====ImplementationDisadvantages of multidimensionalM-D separable DWT ====

Wavelet coefficients can be computed by passing the signal to be decomposed though a series of filters.<ref>{{cite web|title=Discrete wavelet transform|url=https://en.wikipedia.org/wiki/Discrete_wavelet_transform|website=Wikipedia|publisher=Wikipedia}}</ref> In the case of 1-D, there are two filters in every level-one low pass for approximation and one high pass for the details. In the multidimensional case, the number of filters in each level depends on the number of tensor product vector spaces. For M-D, {{math|2^M}} 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 {{math|M{{=}}3}} and a signal of size {{math| N1 &times; N2 &times; N3}} , a separable DWT can be implemented as follows:<ref name=WavPoly>{{cite web|last1=Cai|first1=Shihua|last2=Li|first2=Keyong|title=Matlab implementation of wavelet transforms|url=http://eeweb.poly.edu/iselesni/WaveletSoftware/index.html}}</ref>

[[File:Wiki figures1.pdf|thumbnail|center|The figure depicts 3-D separable DWT procedure by applying 1-D DWT for each dimension and splitting the data into chunks to obtain wavelets for different subbands]]

Applying the 1-D DWT analysis filterbank in dimension {{math|N1}}, it is now split into two chunks of size {{math| {{frac|N1|2}} &times; N2 &times; N3}}. Applying 1-D DWT in {{math|N2}} dimension, each of these chunks is split into two more chunks of {{math|{{frac|N1|2}} &times; {{frac|N2|2}} &times; N3}}. This repeated in 3-D gives a total of 8 chunks of size {{math| {{frac|N1|2}} &times; {{frac|N2|2}} &times; {{frac|N3|2}}}}. The first chunk is passed via a low pass filter in each of these dimensions and the second one via high-pass.

[[File:Filterbank.pdf|thumbnail|The figure shows the 3-D analysis filterbank for 3-D 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 Complexcomplex Waveletwavelet Transform=transform==

Similar to the 1-D complex wavelet transform,<ref name=kingsbury>{{cite journal|last1=Kingsbury|first1=Nick|title=Complex Wavelets for Shift Invariant Analysis and Filtering of Signals|journal= Applied and Computational Harmonic Analysis|date=2001|volume=10|issue=3|pages=234–253|doi=10.1006/acha.2000.0343|url=http://www.idealibrary.com|doi-access=free}}</ref> 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.<ref name=IEEEmag>{{cite journal|last1=Selesnick|first1=Ivan|last2=Baraniuk|first2=Richard|last3=Kingsbury|first3=Nick|title=The Dual-Tree Complex Wavelet Transform|journal=IEEE SIGNALSignal PROCESSINGProcessing MAGAZINEMagazine|volume=22|issue=6|date=2005|pages=123–151|urldoi=http:/10.1109/ieeexploreMSP.ieee2005.org/xpls/abs_all1550194|bibcode=2005ISPM.jsp?arnumber..22..123S|hdl=1550194&tag1911/20355|s2cid=1833630 |hdl-access=free}}</ref> 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 1-D 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.

Line 50 ⟶ 42:

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 1-D. In the 1-D 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.<ref name=IEEEmag /><ref>{{cite journal|last1=Selesnick|first1=I.W.|title=Hilbert transform pairs of wavelet bases|journal=IEEE Signal Processing Letters|date=June 2001|volume=8|issue=6|pages=170–173|doi=10.1109/97.923042|citeseerx=10.1.1.139.5369|bibcode=2001ISPL....8..170S|s2cid=5994808 }}</ref>

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

Let {{math| &psi;(x)}} and {{math| &psi;(y)}} be complex wavelets:

Let {{math| &psi;ψ(x) {{=}} &psi;(x)_h + j &psi;(x)_g}} and {{math| &psi;ψ(y) {{=}} &psi;(y)_hbe +complex j &psi;(y)_g}}.wavelets:

{{math| &psi;ψ(x,y) {{=}} [&psi;ψ(x)_h + j &psi;ψ(x)_g][}} and {{math| &psi;ψ(y) {{=}} ψ(y)_h + j &psi;ψ(y)_g]}}.

{{=}} &psi;(x)_h&psi;(y)_h - &psi;(x)_g&psi;(x)_g + j [&psi;(x)_h&psi;(y)_g - &psi;(x)_h&psi;(x)_g]}}

{{math| ψ(x,y) {{=}} [ψ(x)_h + j ψ(x)_g][ ψ(y)_h + j ψ(y)_g]

The support of the Fourier spectrum of the wavelet above resides in first quadrant as in the diagram. When just the real part is considered, {{math|Real(&psi;(x,y)) {{=}} &psi;(x)_h&psi;(y)_h - &psi;(x)_g&psi;(x)_g}} has support on opposite quadrants. Both {{math|&psi;(x)_h&psi;(y)_h}} and {{math|&psi;(x)_g&psi;(y)_g}} correspond to HH subband of two different separable 2-D DWTs. This wavelet is oriented at {{math|-45^o}}.

{{=}} &psi;ψ(x)_h&psi;ψ(y)_h - &psi;ψ(x)_g&psi;ψ(x)_g + j [&psi;ψ(x)_h&psi;ψ(y)_g - &psi;ψ(x)_h&psi;ψ(x)_g]}}

The support of the Fourier spectrum of the wavelet above resides in the first quadrant as in the diagram. When just the real part is considered, {{math|Real(&psi;ψ(x,y)) {{=}} &psi;ψ(x)_h&psi;ψ(y)_h - &psi;ψ(x)_g&psi;ψ(x)_g}} has support on opposite quadrants (see (a) in figure). Both {{math|&psi;ψ(x)_h&psi;ψ(y)_h}} and {{math|&psi;ψ(x)_g&psi;ψ(y)_g}} correspond to the HH subband of two different separable 2-D DWTs. This wavelet is oriented at {{math|-45^o}}.

Similarly, by considering {{math| &psi;₂(x,y) {{=}} &psi;(x)&psi;(y)^*}}, wavelet oriented at {{math|45^o}} is obtained. To obtain 4 more oriented real wavelets, {{math|&phi;(x)&psi;(y)}}, {{math|&psi;(x)&phi;(y)}}, {{math|&phi;(x)&psi;(y)^*}} and {{math|&psi;(x)&phi;(y)^*}} are considered.

Similarly, by considering {{math| &psi;ψ₂(x,y) {{=}} &psi;ψ(x)&psi;ψ(y)^*}}, a wavelet oriented at {{math|45^o}} is obtained. To obtain 4 more oriented real wavelets, {{math|&phi;φ(x)&psi;ψ(y)}}, {{math|&psi;ψ(x)&phi;φ(y)}}, {{math|&phi;φ(x)&psi;ψ(y)^*}} and {{math|&psi;ψ(x)&phi;φ(y)^*}} are considered.

For implementation of this 2 separable 2-D DWTs in parallel are needed. Then, the appropriate sum and difference of different subbands give oriented wavelets, a total of 6 in all.

[[File:Wavelet orientation.jpg|thumbnail|center|The figure shows the Fourier support of all 6 oriented wavelets obtained by a 2-D real oriented dual tree CWT]]

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

[[FileImage:Wavelet orientation.jpg|thumbnailframed|centernone|The figure shows the Fourier support of all 6 oriented wavelets obtained by a 2-D real oriented dual tree CWT]]

Similarly, in 3-D, 4 separable 3-D 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 {{math|the (m-1}})^th dimension of a signal with {{math|m}} dimensions. When singularities in [[Manifolds|manifold]]<ref>{{cite book|last1=Boothby|first1=W|title=An Introduction to Differentiable Manifolds and Riemannian Geometry|date=2003|publisher=Academic|___location=San Diego}}</ref> of lower dimensions are considered, such as a bee moving in a straight line in the 4-D space-time, we need 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 Waveletwavelet Transform=transform==

The dual tree '''Hypercomplexhypercomplex wavelet Wavelet Transformtransform (HWT)''' developed in <ref name=DHWT>{{citeCite book journal|last1doi =Lam Chan10.1109/ICASSP.2004.1326715|first1chapter =Wai Directional hypercomplex wavelets for multidimensional signal analysis and processing|last2title =Choi 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing|first2volume =Hyeokho 3|last3pages =Baraniuk iii–996–9|first3year =Richard 2004|titlelast1 =DIRECTIONAL HYPERCOMPLEXWai WAVELETSLam FORChan|last2 MULTIDIMENSIONAL= SIGNALHyeokho ANALYSISChoi|last3 AND= PROCESSINGBaraniuk|journalfirst3 =ICASSP R.G.|dateisbn =2004 0-7803-8484-9|volumehdl =3 1911/19796|pages s2cid=996–999􀀓􀀐􀀚􀀛􀀓􀀖􀀐􀀛􀀗􀀛􀀗􀀐􀀜􀀒􀀓􀀗􀀓􀀐􀀚􀀛􀀓􀀖􀀐􀀛􀀗􀀛􀀗􀀐􀀜􀀒􀀓􀀗􀀓􀀐􀀚􀀛􀀓􀀖􀀐􀀛􀀗􀀛􀀗􀀐􀀜􀀒􀀓􀀗􀀓􀀐􀀚􀀛􀀓􀀖􀀐􀀛􀀗􀀛􀀗􀀐􀀜􀀒􀀓􀀗|url=http://citeseerx.ist.psu.edu/viewdoc/download?8287497 }}</ref> consists of a standard DWT tensor and {{math|2^{m -1}}} wavelets obtained from combining the 1-D Hilbert transform of these wavelets along the n-coordinates. In particular a 2-D HWT consists of the standard 2-D separable DWT tensor as described and three additional components:

{{math| H_x {&psi;ψ(x)_h&psi;ψ(y)_h} {{=}} &psi;ψ(x)_g&psi;ψ(y)_h }}

{{math| H_y {&psi;ψ(x)_h&psi;ψ(y)_h} {{=}} &psi;ψ(x)_h&psi;ψ(y)_g }}

{{math| H_x H_y {&psi;ψ(x)_h&psi;ψ(y)_h} {{=}} &psi;ψ(x)_g&psi;ψ(y)_g }}

For the 2-D case, this is named dual tree '''[[quaternion]] Waveletwavelet Transformtransform (QWT)'''.<ref>{{cite journal|last1=Lam Chan|first1=Wai|last2=Choi|first2=Hyeokho|last3=Baraniuk|first3=Richard|title=Coherent Multiscale Image Processing Using Dual-Tree Quaternion Wavelets|journal=IEEE Transactions on Image Processing|volume=17|issue=7|pages=1069–1082|date=2008|doi=10.1109/TIP.2008.924282|urlpmid=http://ieeexplore18586616|bibcode=2008ITIP.ieee.org/stamp/stamp.jsp?arnumber17.1069C|s2cid=452669916789586 }}</ref>

The total redundancy in M-D is {{math|2^m}} tight frame.

===Directional Hypercomplexhypercomplex Waveletwavelet Transform=transform==

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

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

In,<ref name=DHWT /> this was used to detect line singularities in 3-D 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 ==

<!--- See http://en.wikipedia.org/wiki/Wikipedia:Footnotes on how to create references using <ref></ref> tags, these references will then appear here automatically -->

{{Reflist}}

== External links ==

*[http://www.uio.no/studier/emner/matnat/math/MAT-INF2360/v12/tensorwavelet.pdf Tensor products in wavelet settings]

*[http://eeweb.poly.edu/iselesni/WaveletSoftware/index.html Matlab implementation of wavelet transforms]

*[https://arxiv.org/abs/1101.5320 A Panorama on Multiscale Geometric Representations, Intertwining Spatial, Directional and Frequency Selectivity], a review on 2D (two-dimensional) wavelet representations

[[Category: Multidimensional signal processing]]

[[Category: Wavelets]]

{{Uncategorized|date=November 2015}}

<!--- Categories --->

[[Category:Articles created via the Article Wizard]]

[[Category: Multidimensional signal processing]]

[[Category: Wavelets]]