Multidimensional transform: Difference between revisions

Revision as of 12:17, 24 May 2017

Latest revision as of 04:59, 25 March 2025

(29 intermediate revisions by 25 users not shown)

Line 1:

{{Short description|Mathematical analysis of frequency content of signals}}

In [[mathematical analysis]] and applications, '''multidimensional transforms''' are used to analyze the frequency content of signals in a ___domain of two or more dimensions.

== Multidimensional Fourier transform ==

One of the more popular multidimensional transforms is the [[Fourier transform]], which converts a signal from a time/space ___domain representation to a frequency ___domain representation.<ref name="Smith">Smith, W. Handbook of Real-Time Fast Fourier Transforms:Algorithms to Product Testing, Wiley_IEEE Press, edition 1, pages 73–80, 1995</ref> The discrete-___domain multidimensional Fourier transform (FT) can be computed as follows:

:<math> F(w_1,w_2,\dots,w_m) = \sum_{n_1=-\infty}^\infty \sum_{n_2=-\infty}^\infty \cdots \sum_{n_m=-\infty}^\infty f(n_1,n_2,\dots,n_m) e^{-i w_1 n_1 -i w_2 n_2 \cdots -i w_m n_m}</math>

Line 17 ⟶ 18:

=== Properties of Fourier transform ===

Similar properties of the 1-D FT transform apply, but instead of the input parameter being just a single entry, it's a Multi-dimensional (MD) array or vector. Hence, it's x(n1n₁,…,nMn_M) instead of x(n).

====Linearity====

Line 28 ⟶ 29:

if <math>x(n_1,...,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} X(\omega_1,...,\omega_M)</math>, then<br />

<math>x(n_1 - a_1,...,n_M - a_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} e^{-ji(\omega_1 a_1 +,...,+ \omega_M a_M)} X(\omega_1,...,\omega_M)</math>

====[[Multidimensional modulation|Modulation]]====

Line 34 ⟶ 35:

if <math>x(n_1,\ldots,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} X(\omega_1,\ldots,\omega_M)</math>, then

: <math>e^{ji(\theta_1 n_1 +\cdots+ \theta_M n_M)} x(n_1 - a_1,\ldots,n_M - a_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} X(\omega_1 - \theta_1,\ldots,\omega_M - \theta_M)</math>

====Multiplication====

Line 42 ⟶ 43:

then,

: {{NumBlk|::|<math> x_1(n_1,\ldots,n_M) x_2(n_1,\ldots,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} \frac{1}{(2\pi)^M} \int \limits_{-\pi}^\pi \cdots \int\limits_{-\pi}^\pi X_1(\omega_1 - \theta_1,\ldots,\omega_M - \theta_M) X_2 (\theta_1, \ldots, \theta_M) \, d\theta_1 \cdots d\theta_M</math>|{{EquationRef|MD Convolution in Frequency Domain}}}}

or,

: {{NumBlk|::|<math> x_1(n_1,\ldots,n_M) x_2(n_1,\ldots,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} \frac{1}{(2\pi)^M} \int\limits_{-\pi}^\pi \cdots \int\limits_{-\pi}^\pi X_1(\theta_1,\ldots,\theta_M) X_2(\omega_1 - \theta_1,\ldots,\omega_M - \theta_M) \, d\theta_1\cdots d\theta_M</math>|{{EquationRef|MD Convolution in Frequency Domain}}}}

====Differentiation====

Line 51 ⟶ 52:

If <math>x(n_1,\ldots,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} X(\omega_1,\ldots,\omega_M)</math>, then

: <math>-jn_1xin_1x(n_1,\ldots,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} \frac{\partial}{(\partial\omega_1)} X(\omega_1,\ldots,\omega_M), </math>

: <math>-jn_2xin_2x(n_1,\ldots,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} \frac{\partial}{(\partial\omega_2)} X(\omega_1,\ldots,\omega_M), </math>

: <math>(-ji)^M(n_1n_2\cdots n_M)x(n_1,\ldots,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} \frac{(\partial)^M}{(\partial\omega_1\partial\omega_2\cdots\partial\omega_M)} X(\omega_1,\ldots,\omega_M),</math>

====Transposition====

Line 71 ⟶ 72:

If <math>x(n_1,\ldots,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} X(\omega_1,\ldots,\omega_M)</math>, then

: <math>x^{*}(\pm n_1,\ldots,\pm n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} X^{*}(-\mp \omega_1,\ldots,-\mp \omega_M)</math>

====Parseval's theorem (MD)====

Line 83 ⟶ 84:

<math>\sum_{n_1=-\infty}^\infty ... \sum_{n_M =-\infty}^\infty |x_1 (n_1,...,n_M)|^2 {=} \frac{1}{(2\pi)^M} \int\limits_{-\pi}^{\pi} ... \int\limits_{-\pi}^{\pi}|X_1(\omega_1,...,\omega_M)|^2 d\omega_1...d\omega_M</math>

A special case of the [[Parseval's theorem]] is when the two multi-dimensional signals are the same. In this case, the theorem portrays the energy conservation of the signal and the term in the summation or integral is the energy-density of the signal.

====Separability====

One property is the separability property. A signal or system is said to be separable if it can be expressed as a product of 1-D functions with different independent variables. This phenomenon allows computing the FT transform as a product of 1-D FTs instead of multi-dimensional FT.

One property is the separability property. A signal or system is said to be separable if it can be expressed as a product of 1-D functions with different independent variables. This phenomenon allows computing the FT transform as a product of 1-D FTs instead of multi-dimensional FT.

if <math>x(n_1,...,n_M) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} X(\omega_1,...,\omega_M)</math>, <math>a(n_1) \overset{\underset{\mathrm{FT}}{}}{\longleftrightarrow} A(\omega_1)</math>,

Line 98:

=== MD FFT ===

A [[fast Fourier transform]] (FFT) is an algorithm to compute the discrete Fourier transform (DFT) and its inverse. An FFT computes the DFT and produces exactly the same result as evaluating the DFT definition directly; the only difference is that an FFT is much faster. (In the presence of [[round-off error]], many FFT algorithms are also much more accurate than evaluating the DFT definition directly).There are many different FFT algorithms involving a wide range of mathematics, from simple complex-number arithmetic to group theory and number theory. See more in [[Fast Fourier transform|FFT]].

=== MD DFT ===

The multidimensional [[discrete Fourier transform]] (DFT) is a sampled version of the discrete-___domain FT by evaluating it at sample frequencies that are uniformly spaced.<ref>Dudgeon and Mersereau, Multidimensional Digital Signal Processing,2nd edition,1995</ref> The {{nowrap|''N''₁ × ''N''₂ × ... ''N''_''Mm''}} DFT is given by:

:<math> Fx(K_1,K_2,\ldots,K_nK_m)= \sum_{n_1=0}^{N_1-1} \cdots \sum_{n_m=0}^{N_m-1} fx(n_1,n_2,\ldots,n_Nn_m) e^{-i \frac{2 \pi}{N_1} n_1 K_1 -i \frac{2 \pi}{N_2} n_2 K_2 \cdots -i \frac{2 \pi}{N_m} n_m K_m} </math>

for {{nowrap|0 ≤ ''K_i'' ≤ ''N_i'' &minus; 1}}, {{nowrap|''i'' {{=}} 1, 2, ..., ''m''}}.

Line 123:

== Multidimensional Laplace transform ==

The multidimensional [[Laplace transform]] is useful for the solution of boundary value problems. Boundary value problems in two or more variables characterized by partial differential equations can be solved by a direct use of the Laplace transform.<ref name=":0">{{Cite journal|title = Theorems on multidimensional laplace transform for solution of boundary value problems|url = http://www.sciencedirect.com/science/article/pii/089812218990031X|journal = Computers & Mathematics with Applications|date = 1989-01-01|pages = 1033–1056|volume = 18|issue = 12|doi = 10.1016/0898-1221(89)90031-X|firstfirst1 = Joyati|lastlast1 = Debnath|first2 = R. S.|last2 = Dahiya|doi-access = free}}</ref> The Laplace transform for an M-dimensional case is defined<ref name=":0"/> as

<math> F(s_1,s_2,\ldots,s_n) = \int_{0}^{\infty} \cdots \int_{0}^{\infty}

Line 130:

where F stands for the s-___domain representation of the signal f(t).

A special case (along 2 dimensions) of the multi-dimensional Laplace transform of function f(x,y) is defined<ref>{{Cite book|title = Operational Calculus in two Variables and its Application (1st English edition) - translated by D.M.G. Wishart (Calcul opérationnel)|last = |first = |publisher = |year = |isbn = |___location = |pages = }}</ref> as

<math display="block">F(s_1,s_2)=\textstyle \int\limits_{0}^{\infty}\int\limits_{0}^{\infty}\ f(x,y) e^{-s_1x-s_2y}\, dxdy</math>

<math> F(s_1,s_2) </math> is called the image of <math> f(x,y) </math> and <math> f(x,y) </math> is known as the original of <math> F(s_1,s_2) </math>.<ref name=":1">{{Cite journalcn|url = |title = Multi-Dimensional Laplace Transforms and Systems of Partial Differential Equations |last = Aghili and Moghaddam|first = |journal = International Mathematical Forum |volume=1 |year=2006 |issue=21 |pages=1043–1050|doi = |pmid = |access-date =November 2019}}</ref> This special case can be used to solve the [[Telegrapher's equations]].<ref name{{cn|date=":1"November />2019}}}

== Multidimensional Z transform ==

== Multidimensional Z transformSource:<ref>{{Cite web|url = http://dsp-book.narod.ru/HFTSP/8579ch08.pdf|title = Narod Book|date = |accessdate = |website = |publisher = |last = |first = }}</ref> ==

== Multidimensional Z transform<ref>{{Cite web|url = http://dsp-book.narod.ru/HFTSP/8579ch08.pdf|title = Narod Book|date = |accessdate = |website = |publisher = |last = |first = }}</ref> ==

The multidimensional Z transform is used to map the discrete time ___domain multidimensional signal to the Z ___domain. This can be used to check the stability of filters. The equation of the multidimensional Z transform is given by

[[File:Figure 1.1a depicting region of support.png|thumb|209x209px|Figure 1.1a]]

Line 147 ⟶ 149:

<math> F(z_1,z_2)= \sum_{n_1=-\infty}^{\infty} \sum_{n_2=-\infty}^{\infty} f(n_1,n_2) z_1^{-n_1} z_2^{-n_2} </math>

The Fourier transform is a special case of the Z transform evaluated along the [[unit circle]] (in 1D) and unit bi-circle (in 2D). i.e. at

<math display="inline"> z=e^{jwiw} </math> where z and w are vectors.

=== Region of convergence ===

Line 159 ⟶ 161:

If a sequence has a support as shown in Figure 1.1a, then its ROC is shown in Figure 1.1b. This follows that |''F''(''z''₁,''z''₂)| < '''∞''' .

<math>(z_{01},z_{02})</math> lies in the ROC, then all points<math>(z_1,z_2)</math>that satisfy |z1|≥|z01| and |z2|≥|z02| lie in the ROC.

Therefore, for figure 1.1a and 1.1b, the ROC would be

Line 177 ⟶ 179:

[[File:Dctjpeg.png|thumb|250px|Two-dimensional DCT frequencies from the [[JPEG#Discrete cosine transform|JPEG DCT]]]]

The DCT is used in [[JPEG]] image compression, [[MJPEG]], [[MPEG]], [[DV (video format)|DV]], [[Daala]], and [[Theora]] [[video compression]]. There, the two-dimensional DCT-II of ''N''x''N'' blocks are computed and the results are [[Quantization (signal processing)|quantized]] and [[Entropy encoding|entropy coded]]. In this case, ''N'' is typically 8 and the DCT-II formula is applied to each row and column of the block. The result is an 8x8 transform coefficient array in which the: (0,0) element (top-left) is the DC (zero-frequency) component and entries with increasing vertical and horizontal index values represent higher vertical and horizontal spatial frequencies, as shown in the picture on the right.

In image processing, one can also analyze and describe unconventional cryptographic methods based on 2D DCTs, for inserting non-visible binary watermarks into the 2D image plane,<ref>Peter KULLAI, Pavol SABAKAI, JozefHUSKAI. Simple Possibilities of 2D DCT Application in Digital

Line 187 ⟶ 189:

When the DFT is used for [[Frequency spectrum#Spectrum analysis|spectral analysis]], the {''x_n''} sequence usually represents a finite set of uniformly spaced time-samples of some signal ''x''(''t'') where ''t'' represents time. The conversion from continuous time to samples (discrete-time) changes the underlying [[continuous Fourier transform|Fourier transform]] of ''x''(''t'') into a [[discrete-time Fourier transform]] (DTFT), which generally entails a type of distortion called [[aliasing]]. Choice of an appropriate sample-rate (see ''[[Nyquist rate]]'') is the key to minimizing that distortion. Similarly, the conversion from a very long (or infinite) sequence to a manageable size entails a type of distortion called ''[[Spectral leakage|leakage]]'', which is manifested as a loss of detail (aka resolution) in the DTFT. Choice of an appropriate sub-sequence length is the primary key to minimizing that effect. When the available data (and time to process it) is more than the amount needed to attain the desired frequency resolution, a standard technique is to perform multiple DFTs, for example to create a [[spectrogram]]. If the desired result is a power spectrum and noise or randomness is present in the data, averaging the magnitude components of the multiple DFTs is a useful procedure to reduce the [[variance]] of the spectrum (also called a [[periodogram]] in this context); two examples of such techniques are the [[Welch method]] and the [[Bartlett method]]; the general subject of estimating the power spectrum of a noisy signal is called [[spectral estimation]].

A final source of distortion (or perhaps ''illusion'') is the DFT itself, because it is just a discrete sampling of the DTFT, which is a function of a continuous frequency ___domain. That can be mitigated by increasing the resolution of the DFT. That procedure is illustrated at [[{{slink|Discrete-time Fourier transform#|Sampling the DTFT|Sampling the DTFT]]nopage=y}}.

*The procedure is sometimes referred to as ''zero-padding'', which is a particular implementation used in conjunction with the [[fast Fourier transform]] (FFT) algorithm. The inefficiency of performing multiplications and additions with zero-valued "samples" is more than offset by the inherent efficiency of the FFT.

*As already noted, leakage imposes a limit on the inherent resolution of the DTFT. So there is a practical limit to the benefit that can be obtained from a fine-grained DFT.

Line 199 ⟶ 201:

Laplace transforms are used to solve partial differential equations. The general theory for obtaining solutions in this technique is developed by theorems on Laplace transform in n dimensions.<ref name=":0" />

The multidimensional Z transform can also be used to solve partial differential equations.<ref>{{Cite journal|url = http://dml.cz/bitstream/handle/10338.dmlcz/124265/Kybernetika_24-1988-7_1.pdf|title = Kybernetika|last = Gregor|first = Jiří |date= 1998 |journal= Kybernetika |volume=24 |access-date = }}</ref>

=== Image processing for arts surface analysis by FFT ===

One very important factor is that we must apply a non-destructive method to obtain those rare valuables information (from the HVS viewing point, is focused in whole colorimetric and spatial information) about works of art and zero-damage on them.

We can understand the arts by looking at a color change or by measuring the surface uniformity change. Since the whole image will be very huge, so we use a double raised cosine window to truncate the image:<ref name="Angelini et al">Angelini, E., Grassin, S. ; Piantanida, M. ; Corbellini, S. ; Ferraris, F. ; Neri, A. ; Parvis, M. FFT-based imaging processing for cultural heritage monitoring Instrumentation and Measurement Technology Conference (I2MTC), 2010 IEEE</ref>

:<math> w(x,y)=\frac{1}{4} \left(1 + \cos {\frac {x \pi} N }\right)\left(1 + \cos {\frac{y \pi} N }\right) </math>

Line 221 ⟶ 223:

museums without affecting their daily use. But this method doesn’t allow a quantitative measure of the corrosion rate.

=== Application to weakly nonlinear circuit simulation ===
Source:<ref>{{Cite journalbook|chapter-url = httphttps://ieeexplore.ieee.org/search/searchresult.jsp?newsearch=true&queryText=Weakly%20Nonlinear%20Circuit%20Analysis%20Based%20on%20Fast%20Multidimensional%20Inverse%20Laplace%20Transform|titlechapter = Weakly Nonlinear Circuit Analysis Based on Fast Multidimensional Inverse Laplace Transform|last = Wang|first = Tingting|date = 2012|journalpages = IEEE Conference Publications547–552|doi = 10.1109/ASPDAC.2012.6165013|pmidisbn = |access978-date1-4673-0772-7|title = 17th Asia and South Pacific Design Automation Conference| s2cid=15427178 }}</ref> ===

[[File:A weakly circuit.PNG|thumb|330x330px|An example of a weakly nonlinear circuit]]

The inverse multidimensional Laplace transform can be applied to simulate nonlinear circuits. This is done so by formulating a circuit as a state-space and expanding the Inverse Laplace Transform based on [[Laguerre function]] expansion.

The LagurreLaguerre method can be used to simulate a weakly nonlinear circuit and the Laguerre method can invert a multidimensional Laplace transform efficiently with a high accuracy.

It is observed that a high accuracy and significant speedup can be achieved for simulating large nonlinear circuits using multidimensional Laplace transforms.