Multidimensional signal processing

Last updated August 16, 2020

In signal processing, multidimensional signal processing covers all signal processing done using multidimensional signals and systems. While multidimensional signal processing is a subset of signal processing, it is unique in the sense that it deals specifically with data that can only be adequately detailed using more than one dimension. In m-D digital signal processing, useful data is sampled in more than one dimension. Examples of this are image processing and multi-sensor radar detection. Both of these examples use multiple sensors to sample signals and form images based on the manipulation of these multiple signals. Processing in multi-dimension (m-D) requires more complex algorithms, compared to the 1-D case, to handle calculations such as the fast Fourier transform due to more degrees of freedom.^[1] In some cases, m-D signals and systems can be simplified into single dimension signal processing methods, if the considered systems are separable.

Typically, multidimensional signal processing is directly associated with digital signal processing because its complexity warrants the use of computer modelling and computation.^[1] A multidimensional signal is similar to a single dimensional signal as far as manipulations that can be performed, such as sampling, Fourier analysis, and filtering. The actual computations of these manipulations grow with the number of dimensions.

Sampling

Multidimensional sampling requires different analysis than typical 1-D sampling. Single dimension sampling is executed by selecting points along a continuous line and storing the values of this data stream. In the case of multidimensional sampling, the data is selected utilizing a lattice, which is a "pattern" based on the sampling vectors of the m-D data set.^[2] These vectors can be single dimensional or multidimensional depending on the data and the application.^[2]

Multidimensional sampling is similar to classical sampling as it must adhere to the Nyquist–Shannon sampling theorem. It is affected by aliasing and considerations must be made for eventual Multidimensional Signal Reconstruction.

Fourier Analysis

A multidimensional signal can be represented in terms of sinusoidal components. This is typically done with a type of Fourier transform. The m-D Fourier transform transforms a signal from a signal domain representation to a frequency domain representation of the signal. In the case of digital processing, a discrete Fourier Transform (DFT) is utilized to transform a sampled signal domain representation into a frequency domain representation:

X(k_{1},k_{2},\dots ,k_{m})=\sum _{n_{1}=-\infty }^{\infty }\sum _{n_{2}=-\infty }^{\infty }\cdots \sum _{n_{m}=-\infty }^{\infty }x(n_{1},n_{2},\dots ,n_{m})e^{-j2\pi k_{1}n_{1}}e^{-j2\pi k_{2}n_{2}}\cdots e^{-j2\pi k_{m}n_{m}}

where X stands for the multidimensional discrete Fourier transform, x stands for the sampled time/space domain signal, m stands for the number of dimensions in the system, n are sample indices and k are frequency samples.^[3] Computational complexity is usually the main concern when implementing any Fourier transform. For multidimensional signals, the complexity can be reduced by a number of different methods. The computation may be simplified if there is independence between variables of the multidimensional signal.^[3] In general, fast Fourier transforms (FFTs), reduce the number of computations by a substantial factor. While there are a number of different implementations of this algorithm for m-D signals, two often used variations are the vector-radix FFT and the row-column FFT.

Filtering

A 2-D filter (left) defined by its 1-D prototype function (right) and a McClellan transformation. 2-D filter frequency response and 1-D filter prototype frequency response.gif — A 2-D filter (left) defined by its 1-D prototype function (right) and a McClellan transformation.

Filtering is an important part of any signal processing application. Similar to typical single dimension signal processing applications, there are varying degrees of complexity within filter design for a given system. M-D systems utilize digital filters in many different applications. The actual implementation of these m-D filters can pose a design problem depending on whether the multidimensional polynomial is factorable.^[3] Typically, a prototype filter is designed in a single dimension and that filter is extrapolated to m-D using a mapping function.^[3] One of the original mapping functions from 1-D to 2-D was the McClellan Transform.^[4] Both FIR and IIR filters can be transformed to m-D, depending on the application and the mapping function.

Applicable Fields

Related Research Articles

Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations. The digital signals processed in this manner are a sequence of numbers that represent samples of a continuous variable in a domain such as time, space, or frequency. In digital electronics, a digital signal is represented as a pulse train, which is typically generated by the switching of a transistor.

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 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.

Fast Fourier transform O(N logN) divide and conquer algorithm to calculate the discrete Fourier transforms

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 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.$

In mathematics, Fourier analysis is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph Fourier, who showed that representing a function as a sum of trigonometric functions greatly simplifies the study of heat transfer.

A wavelet is a wave-like oscillation with an amplitude that begins at zero, increases, and then decreases back to zero. It can typically be visualized as a "brief oscillation" like one recorded by a seismograph or heart monitor. Generally, wavelets are intentionally crafted to have specific properties that make them useful for signal processing. Using convolution, wavelets can be combined with known portions of a damaged signal to extract information from the unknown portions.

A discrete cosine transform (DCT) expresses a finite sequence of data points in terms of a sum of cosine functions oscillating at different frequencies. The DCT, first proposed by Nasir Ahmed in 1972, is a widely used transformation technique in signal processing and data compression. It is used in most digital media, including digital images, digital video, digital audio, digital television, digital radio, and speech coding. DCTs are also important to numerous other applications in science and engineering, such as digital signal processing, communications devices, reducing network bandwidth usage, and spectral methods for the numerical solution of partial differential equations.

In signal processing, a periodogram is an estimate of the spectral density of a signal. The term was coined by Arthur Schuster in 1898. Today, the periodogram is a component of more sophisticated methods. It is the most common tool for examining the amplitude vs frequency characteristics of FIR filters and window functions. FFT spectrum analyzers are also implemented as a time-sequence of periodograms.

In numerical analysis and functional analysis, a discrete wavelet transform (DWT) is any wavelet transform for which the wavelets are discretely sampled. As with other wavelet transforms, a key advantage it has over Fourier transforms is temporal resolution: it captures both frequency and location information.

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

In signal processing, a filter bank is an array of band-pass filters that separates the input signal into multiple components, each one carrying a single frequency sub-band of the original signal. One application of a filter bank is a graphic equalizer, which can attenuate the components differently and recombine them into a modified version of the original signal. The process of decomposition performed by the filter bank is called analysis ; the output of analysis is referred to as a subband signal with as many subbands as there are filters in the filter bank. The reconstruction process is called synthesis, meaning reconstitution of a complete signal resulting from the filtering process.

Geophysical survey is the systematic collection of geophysical data for spatial studies. Detection and analysis of the geophysical signals forms the core of Geophysical signal processing. The magnetic and gravitational fields emanating from the Earth's interior hold essential information concerning seismic activities and the internal structure. Hence, detection and analysis of the electric and Magnetic fields is very crucial. As the Electromagnetic and gravitational waves are multi-dimensional signals, all the 1-D transformation techniques can be extended for the analysis of these signals as well. Hence this article also discusses multi-dimensional signal processing techniques.

A multidimensional signal is a function of M independent variables where $. Real world signals, which are generally continuous time signals, have to be discretized (sampled) in order to ensure that digital systems can be used to process the signals. It is during this process of discretization where sampling comes into picture. Although there are many ways of obtaining a discrete representation of a continuous time signal, periodic sampling is by far the simplest scheme. Theoretically, sampling can be performed with respect to any set of points. But practically, sampling is carried out with respect to a set of points that have a certain algebraic structure. Such structures are called lattices. Mathematically, the process of sampling an N-dimensional signal can be written as:$

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

Many concepts in one–dimensional signal processing are similar to concepts in multidimensional signal processing. However, many familiar one–dimensional procedures do not readily generalize to the multidimensional case and some important issues associated with multidimensional signals and systems do not appear in the one–dimensional special case.

Power spectral estimation forms the basis for distinguishing and tracking signals in the presence of noise and extracting information from available data. One dimensional signals are expressed in terms of a single domain while multidimensional signals are represented in wave vector and frequency spectrum. Therefore, spectral estimation in the case of multidimensional signals gets a bit tricky.

Digital signal processing (DSP) is a ubiquitous methodology in scientific and engineering computations. However, practically, DSP problems are often not only 1-D. For instance, image data are 2-D signals and radar signals are 3-D signals. While the number of dimension increases, the time and/or storage complexity of processing digital signals grow dramatically. Therefore, solving DSP problems in real-time is extremely difficult in reality.

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.

Multidimensional modulation is modifying or multiplying an MD signal with another signal that carries some information or message. In the frequency domain, the signal is moved from one frequency to another.

Multidimensional seismic data processing forms a major component of seismic profiling, a technique used in geophysical exploration. The technique itself has various applications, including mapping ocean floors, determining the structure of sediments, mapping subsurface currents and hydrocarbon exploration. Since geophysical data obtained in such techniques is a function of both space and time, multidimensional signal processing techniques may be better suited for processing such data.

Parallelmultidimensionaldigitalsignal processing (mD-DSP) is defined as the application of parallel programming and multiprocessing to digital signal processing techniques to process digital signals that have more than a single dimension. The use of mD-DSP is fundamental to many application areas such as digital image and video processing, medical imaging, geophysical signal analysis, sonar, radar, lidar, array processing, computer vision, computational photography, and augmented and virtual reality. However, as the number of dimensions of a signal increases the computational complexity to operate on the signal increases rapidly. This relationship between the number of dimensions and the amount of complexity, related to both time and space, as studied in the field of algorithm analysis, is analogues to the concept of the curse of dimensionality. This large complexity generally results in an extremely long execution run-time of a given mD-DSP application rendering its usage to become impractical for many applications; especially for real-time applications. This long run-time is the primary motivation of applying parallel algorithmic techniques to mD-DSP problems.

References

1 2 D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 2, 1983.
1 2 Mersereau, R.; Speake, T., "The processing of periodically sampled multidimensional signals," Acoustics, IEEE Transactions on Speech and Signal Processing, vol.31, no.1, pp.188-194, Feb 1983.
1 2 3 4 D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 61,112, 1983.
↑ Mersereau, R.M.; Mecklenbrauker, W.; Quatieri, T., Jr., "McClellan transformations for two-dimensional digital filtering-Part I: Design," IEEE Transactions on Circuits and Systems, vol.23, no.7, pp.405-414, Jul 1976.

External links

Media related to Multidimensional signal processing at Wikimedia Commons

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[dudmer83-1] 1 2 D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 2, 1983.

[mer83-2] 1 2 Mersereau, R.; Speake, T., "The processing of periodically sampled multidimensional signals," Acoustics, IEEE Transactions on Speech and Signal Processing, vol.31, no.1, pp.188-194, Feb 1983.

[dudmer83_2-3] 1 2 3 4 D. Dudgeon and R. Mersereau, Multidimensional Digital Signal Processing, Prentice-Hall, First Edition, pp. 61,112, 1983.

[mer78-4] Mersereau, R.M.; Mecklenbrauker, W.; Quatieri, T., Jr., "McClellan transformations for two-dimensional digital filtering-Part I: Design," IEEE Transactions on Circuits and Systems, vol.23, no.7, pp.405-414, Jul 1976.