Multidimensional transform

Last updated

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

Contents

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. [1] The discrete-domain multidimensional Fourier transform (FT) can be computed as follows:

where F stands for the multidimensional Fourier transform, m stands for multidimensional dimension. Define f as a multidimensional discrete-domain signal. The inverse multidimensional Fourier transform is given by

The multidimensional Fourier transform for continuous-domain signals is defined as follows: [1]

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(n1,…,nM) instead of x(n).

Linearity

if , and then,

Shift

if , then

Modulation

if , then

Multiplication

if , and

then,

 

 

 

 

(MD Convolution in Frequency Domain)

or,

 

 

 

 

(MD Convolution in Frequency Domain)

Differentiation

If , then

Transposition

If , then

Reflection

If , then

Complex conjugation

If , then

Parseval's theorem (MD)

if , and then,

if , then

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

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 , , ... , and if , then

, so

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 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. [2] The N1 × N2 × ... Nm DFT is given by:

for 0 ≤ KiNi 1, i = 1, 2, ..., m.

The inverse multidimensional DFT equation is

for 0 ≤ n1, n2, ... , nmN(1, 2, ... , m) – 1.

Multidimensional discrete cosine transform

The discrete cosine transform (DCT) is used in a wide range of applications such as data compression, feature extraction, Image reconstruction, multi-frame detection and so on. The multidimensional DCT is given by:

for ki = 0, 1, ..., Ni 1, i = 1, 2, ..., r.

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. [3] The Laplace transform for an M-dimensional case is defined [3] as

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 [4] as

is called the image of and is known as the original of .[ citation needed ] This special case can be used to solve the Telegrapher's equations.[ citation needed ]}

Multidimensional Z transform [5]

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

Figure 1.1a Figure 1.1a depicting region of support.png
Figure 1.1a

where F stands for the z-domain representation of the signal f(n).

A special case of the multidimensional Z transform is the 2D Z transform which is given as

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

where z and w are vectors.

Region of convergence

Figure 1.1b Region of Convergence for figure 1.1a.png
Figure 1.1b

Points (z1,z2) for which are located in the ROC.

An example:

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(z1,z2)| < .

lies in the ROC, then all pointsthat satisfy |z1|≥|z01| and |z2|≥|z02 lie in the ROC.

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

where L is the slope.

The 2D Z-transform, similar to the Z-transform, is used in multidimensional signal processing to relate a two-dimensional discrete-time signal to the complex frequency domain in which the 2D surface in 4D space that the Fourier transform lies on is known as the unit surface or unit bicircle.

Applications

The DCT and DFT are often used in signal processing [6] and image processing, and they are also used to efficiently solve partial differential equations by spectral methods. The DFT can also be used to perform other operations such as convolutions or multiplying large integers. The DFT and DCT have seen wide usage across a large number of fields, we only sketch a few examples below.

Image processing

Two-dimensional DCT frequencies from the JPEG DCT Dctjpeg.png
Two-dimensional DCT frequencies from the JPEG DCT

The DCT is used in JPEG image compression, MJPEG, MPEG, DV, Daala, and Theora video compression. There, the two-dimensional DCT-II of NxN blocks are computed and the results are quantized and 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, [7] and According to different orientations, the 2-D directional DCT-DWT hybrid transform can be applied in denoising ultrasound images. [8] 3-D DCT can also be used to transform video data or 3-D image data in watermark embedding schemes in transform domain. [9] [10]

Spectral analysis

When the DFT is used for spectral analysis, the {xn} 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 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 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 § Sampling the DTFT.

Partial differential equations

Discrete Fourier transforms are often used to solve partial differential equations, where again the DFT is used as an approximation for the Fourier series (which is recovered in the limit of infinite N). The advantage of this approach is that it expands the signal in complex exponentials einx, which are eigenfunctions of differentiation: d/dxeinx = ineinx. Thus, in the Fourier representation, differentiation is simple—we just multiply by i n. (Note, however, that the choice of n is not unique due to aliasing; for the method to be convergent, a choice similar to that in the trigonometric interpolation section above should be used.) A linear differential equation with constant coefficients is transformed into an easily solvable algebraic equation. One then uses the inverse DFT to transform the result back into the ordinary spatial representation. Such an approach is called a spectral method.

DCTs are also widely employed in solving partial differential equations by spectral methods, where the different variants of the DCT correspond to slightly different even/odd boundary conditions at the two ends of the array.

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. [3]

The multidimensional Z transform can also be used to solve partial differential equations. [11]

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: [12]

where N is the image dimension and x, y are the coordinates from the center of image spans from 0 to N/2. The author wanted to compute an equal value for spatial frequency such as: [12]

where "FFT" denotes the fast Fourier transform, and f is the spatial frequency spans from 0 to N/2 – 1. The proposed FFT-based imaging approach is diagnostic technology to ensure a long life and stable to culture arts. This is a simple, cheap which can be used in 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 [13]

An example of a weakly nonlinear circuit A weakly circuit.PNG
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 Laguerre 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.

See also

Related Research Articles

<span class="mw-page-title-main">Discrete Fourier transform</span> Type of Fourier transform in discrete mathematics

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT (IDFT) is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous, and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

<span class="mw-page-title-main">Fast Fourier transform</span> O(N log N) discrete Fourier transform algorithm

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse factors. As a result, it manages to reduce the complexity of computing the DFT from , which arises if one simply applies the definition of DFT, to , where n is the data size. The difference in speed can be enormous, especially for long data sets where n may be in the thousands or millions. In the presence of round-off error, many FFT algorithms are much more accurate than evaluating the DFT definition directly or indirectly. There are many different FFT algorithms based on a wide range of published theories, from simple complex-number arithmetic to group theory and number theory.

<span class="mw-page-title-main">Fourier transform</span> Mathematical transform that expresses a function of time as a function of frequency

In physics, engineering and mathematics, the Fourier transform (FT) is an integral transform that converts a function into a form that describes the frequencies present in the original function. The output of the transform is a complex-valued function of frequency. The term Fourier transform refers to both this complex-valued function and the mathematical operation. When a distinction needs to be made the Fourier transform is sometimes called the frequency domain representation of the original function. The Fourier transform is analogous to decomposing the sound of a musical chord into the intensities of its constituent pitches.

<span class="mw-page-title-main">Short-time Fourier transform</span> Fourier-related transform suited to signals that change rather quickly in time

The short-time Fourier transform (STFT), is a Fourier-related transform used to determine the sinusoidal frequency and phase content of local sections of a signal as it changes over time. In practice, the procedure for computing STFTs is to divide a longer time signal into shorter segments of equal length and then compute the Fourier transform separately on each shorter segment. This reveals the Fourier spectrum on each shorter segment. One then usually plots the changing spectra as a function of time, known as a spectrogram or waterfall plot, such as commonly used in software defined radio (SDR) based spectrum displays. Full bandwidth displays covering the whole range of an SDR commonly use fast Fourier transforms (FFTs) with 2^24 points on desktop computers.

In signal processing, a finite impulse response (FIR) filter is a filter whose impulse response is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response (IIR) filters, which may have internal feedback and may continue to respond indefinitely.

In mathematics and signal processing, the Hilbert transform is a specific singular integral that takes a function, u(t) of a real variable and produces another function of a real variable H(u)(t). The Hilbert transform is given by the Cauchy principal value of the convolution with the function (see § Definition). The Hilbert transform has a particularly simple representation in the frequency domain: It imparts a phase shift of ±90° (π/2 radians) to every frequency component of a function, the sign of the shift depending on the sign of the frequency (see § Relationship with the Fourier transform). The Hilbert transform is important in signal processing, where it is a component of the analytic representation of a real-valued signal u(t). The Hilbert transform was first introduced by David Hilbert in this setting, to solve a special case of the Riemann–Hilbert problem for analytic functions.

In mathematics, Parseval's theorem usually refers to the result that the Fourier transform is unitary; loosely, that the sum of the square of a function is equal to the sum of the square of its transform. It originates from a 1799 theorem about series by Marc-Antoine Parseval, which was later applied to the Fourier series. It is also known as Rayleigh's energy theorem, or Rayleigh's identity, after John William Strutt, Lord Rayleigh.

In mathematics, the discrete-time Fourier transform (DTFT) is a form of Fourier analysis that is applicable to a sequence of discrete values.

<span class="mw-page-title-main">Rectangular function</span> Function whose graph is 0, then 1, then 0 again, in an almost-everywhere continuous way

The rectangular function is defined as

<span class="mw-page-title-main">Dirac comb</span> Periodic distribution ("function") of "point-mass" Dirac delta sampling

In mathematics, a Dirac comb is a periodic function with the formula

<span class="mw-page-title-main">Gabor transform</span>

The Gabor transform, named after Dennis Gabor, is a special case of the short-time Fourier transform. It is used to determine the sinusoidal frequency and phase content of local sections of a signal as it changes over time. The function to be transformed is first multiplied by a Gaussian function, which can be regarded as a window function, and the resulting function is then transformed with a Fourier transform to derive the time-frequency analysis. The window function means that the signal near the time being analyzed will have higher weight. The Gabor transform of a signal x(t) is defined by this formula:

The split-radix FFT is a fast Fourier transform (FFT) algorithm for computing the discrete Fourier transform (DFT), and was first described in an initially little-appreciated paper by R. Yavne (1968) and subsequently rediscovered simultaneously by various authors in 1984. In particular, split radix is a variant of the Cooley–Tukey FFT algorithm that uses a blend of radices 2 and 4: it recursively expresses a DFT of length N in terms of one smaller DFT of length N/2 and two smaller DFTs of length N/4.

In many-body theory, the term Green's function is sometimes used interchangeably with correlation function, but refers specifically to correlators of field operators or creation and annihilation operators.

In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring.

In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform was discovered by Don Coppersmith.

The spectrum of a chirp pulse describes its characteristics in terms of its frequency components. This frequency-domain representation is an alternative to the more familiar time-domain waveform, and the two versions are mathematically related by the Fourier transform. The spectrum is of particular interest when pulses are subject to signal processing. For example, when a chirp pulse is compressed by its matched filter, the resulting waveform contains not only a main narrow pulse but, also, a variety of unwanted artifacts many of which are directly attributable to features in the chirp's spectral characteristics.

<span class="mw-page-title-main">Phase stretch transform</span>

Phase stretch transform (PST) is a computational approach to signal and image processing. One of its utilities is for feature detection and classification. PST is related to time stretch dispersive Fourier transform. It transforms the image by emulating propagation through a diffractive medium with engineered 3D dispersive property. The operation relies on symmetry of the dispersion profile and can be understood in terms of dispersive eigenfunctions or stretch modes. PST performs similar functionality as phase-contrast microscopy, but on digital images. PST can be applied to digital images and temporal data. It is a physics-based feature engineering algorithm.

In signal processing, multidimensional discrete convolution refers to the mathematical operation between two functions f and g on an n-dimensional lattice that produces a third function, also of n-dimensions. Multidimensional discrete convolution is the discrete analog of the multidimensional convolution of functions on Euclidean space. It is also a special case of convolution on groups when the group is the group of n-tuples of integers.

The problem of reconstructing a multidimensional signal from its projection is uniquely multidimensional, having no 1-D counterpart. It has applications that range from computer-aided tomography to geophysical signal processing. It is a problem which can be explored from several points of view—as a deconvolution problem, a modeling problem, an estimation problem, or an interpolation problem.

Multiresolution Fourier Transform is an integral fourier transform that represents a specific wavelet-like transform with a fully scalable modulated window, but not all possible translations.

References

  1. 1 2 Smith, W. Handbook of Real-Time Fast Fourier Transforms:Algorithms to Product Testing, Wiley_IEEE Press, edition 1, pages 73–80, 1995
  2. Dudgeon and Mersereau, Multidimensional Digital Signal Processing,2nd edition,1995
  3. 1 2 3 Debnath, Joyati; Dahiya, R. S. (1989-01-01). "Theorems on multidimensional laplace transform for solution of boundary value problems". Computers & Mathematics with Applications. 18 (12): 1033–1056. doi: 10.1016/0898-1221(89)90031-X .
  4. Operational Calculus in two Variables and its Application (1st English edition) - translated by D.M.G. Wishart (Calcul opérationnel).
  5. "Narod Book" (PDF).
  6. Tan Xiao, Shao-hai Hu, Yang Xiao. 2-D DFT-DWT Application to Multidimensional Signal Processing. ICSP2006 Proceedings, 2006 IEEE
  7. Peter KULLAI, Pavol SABAKAI, JozefHUSKAI. Simple Possibilities of 2D DCT Application in Digital Monochrome Image Cryptography. Radioelektronika, 17th International Conference, IEEE, 2007, pp. 1–6
  8. Xin-ling Wen, Yang Xiao. The 2-D Directional DCT-DWT Hybrid Transform and Its Application in Denoising Ultrasound Image. Signal Processing. ICSP 2008. 9th International Conference, Page(s): 946–949
  9. Jinwei Wang, Shiguo Lian, Zhongxuan Liu, Zhen Ren, Yuewei Dai, Haila Wang. Image Watermarking Scheme Based on 3-D DCT.Industrial Electronics and Applications, 2006 1ST IEEE Conference, pp. 1–6
  10. Jin Li, Moncef Gabbouj, Jarmo Takala, Hexin Chen. Direct 3-D DCT-to-DCT Resizing Algorithm for Video Coding. Image and Signal Processing and Analysis, 2009. ISPA 2009. Proceedings of 6th International Symposium pp. 105–110
  11. Gregor, Jiří (1998). "Kybernetika" (PDF). Kybernetika. 24.
  12. 1 2 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
  13. Wang, Tingting (2012). "Weakly Nonlinear Circuit Analysis Based on Fast Multidimensional Inverse Laplace Transform". 17th Asia and South Pacific Design Automation Conference. pp. 547–552. doi:10.1109/ASPDAC.2012.6165013. ISBN   978-1-4673-0772-7. S2CID   15427178.