Content deleted Content added
No edit summary |
→BPBEMD algorithm: move ref out of heading |
||
| (25 intermediate revisions by 15 users not shown) | |||
Line 1:
In [[signal processing]], '''multidimensional empirical mode decomposition''' ('''multidimensional EMD''') is an extension of the [[one-dimensional]] (1-D) [[Hilbert–Huang transform|EMD]] algorithm to a signal encompassing multiple dimensions. The [[Hilbert–Huang transform|Hilbert–Huang empirical mode decomposition]] (EMD) process decomposes a signal into intrinsic mode functions combined with the [[Hilbert spectral analysis]], known as the [[Hilbert–Huang transform]] (HHT). The multidimensional EMD extends the 1-D [[Hilbert–Huang transform|EMD]] algorithm into multiple-dimensional signals. This decomposition can be applied to [[image processing]], [[audio signal processing]], and various other multidimensional signals.
==Motivation==
Multidimensional empirical mode decomposition is a popular method because of its applications in many fields, such as texture analysis, financial applications, [[Digital image processing|image processing]], [[Ocean Engineering|ocean engineering]], [[Seismology|seismic]] research, etc.
==Introduction to empirical mode decomposition (EMD)==
[[File:Flow chart of EMD algorithm.jpg|thumb|400x400px|Flow chart of basic EMD algorithm<ref>{{Cite journal|url=http://www.ripublication.com/irph/ijeee_spl/ijeeev7n8_14.pdf|author=Sonam Maheshwari |author2=Ankur Kumar |title=Empirical Mode Decomposition: Theory & Applications |journal=International Journal of Electronic and Electrical Engineering |issn=0974-2174 |volume=7 |issue=8 |year=2014 |pages=873–878}}</ref>{{Predatory open access publisher}}]]
The
The EMD method was developed so that data can be examined in an adaptive time–frequency–amplitude space for nonlinear and non-stationary signals.
The EMD method decomposes the input signal into several
: <math>I(n)=\sum_{m=1}^M \operatorname{IMF}_m(n)+\operatorname{Res}_M(n)</math>
Line 21 ⟶ 17:
==Ensemble empirical mode decomposition==
In the case of only one observation, one of the multiple-observation ensembles is mimicked by adding different copies of white noise, <math>w_i(t)</math>, to that single observation as given in the equation. Although adding noise may result in a smaller signal
The EEMD consists of the following steps:
Line 34 ⟶ 30:
In these steps, EEMD uses two properties of white noise:
# The added white noise leads to a relatively even distribution of extrema distribution on all timescales.
# The [[Dyadic transformation|dyadic]] filter bank property provides a control on the periods of oscillations contained in an oscillatory component, significantly reducing the chance of scale mixing in a component. Through ensemble average, the added noise is averaged out.<ref name=":9" />
=== Pseudo-bi-dimensional empirical mode decomposition ===
Source:<ref name=":5" /> To design a pseudo-BEMD algorithm the key step is to translate the algorithm of the 1D [[Hilbert huang transform|EMD]] into a Bi-dimensional Empirical Mode Decomposition (BEMD) and further extend the algorithm to three or more dimensions which is similar to the BEMD by extending the procedure on successive dimensions. For a 3D data cube of <math>i \times j \times k</math> elements, the pseudo-BEMD will yield detailed 3D components of <math>m \times n \times q</math> where <math>m</math>, <math>n</math> and <math>q</math> are the number of the IMFs decomposed from each dimension having <math>i</math>, <math>j</math>, and <math>k</math> elements, respectively.
Line 49 ⟶ 47:
\begin{bmatrix}x(1,1) & x(1,2) & \cdots & x(1,j) \\x(2,1) & x(2,2) & \cdots & x(1,j) \\ \vdots & \vdots & & \vdots \\x(i,1) & x(i,2) & \cdots & x(i,j) \end{bmatrix}
</math><ref name=":5" />
At first we perform EMD in one direction of ''X''(''i'', ''j''), Row wise for instance, to decompose the data of each row into m components, then to collect the components of the same level of m from the result of each row decomposition to make a 2D decomposed signal at that level of m. Therefore, m set of 2D spatial data are obtained
: <math>
\begin{align}
Line 59 ⟶ 57:
</math><ref name=":5" />
where RX (1, i, j), RX (2, i, j), and RX (m, i, j) are the ''m'' sets of signal as stated (also here we use ''R'' to indicate row decomposing). The relation between these m 2D decomposed signals and the original signal is given as <math>X(i,j)=\sum_{ k \mathop =1}^mRX(k,i,j)</math>
The first row of the matrix RX (m, i, j) is the mth EMD component decomposed from the first row of the matrix X (i, j). The second row of the matrix RX (m, i, j) is the mth EMD component decomposed from the second row of the matrix X (i, j), and so on.
Line 67 ⟶ 65:
For example, the component
# RX(1,i,j) will be decomposed into CRX(1,1,i,j), CRX(1,2,i,j),
# RX(2,i,j) will be decomposed into CRX(2,1,i,j), CRX(2,2,i,j),
# RX(m,i,j) will be decomposed into CRX(m,1,i,j), CRX(m,2,i,j),
where C means column decomposing. Finally, the 2D decomposition will result into m× n matrices which are the 2D EMD components of the original data X(i,j). The matrix expression for the result of the 2D decomposition is
Line 91 ⟶ 89:
given as <math>I=f(x_1,x_2,x_3,x_4,\ldots,x_n)</math>
In which the subscription, n, indicated the number of dimensions. The procedure is identical as stated above: the decomposition starts with the first dimension, and proceeds to the second and third
For example, the matrix expression for the result of a 3D decomposition is TCRX(m,n,q,i,j,k) where T denotes the depth (or time) decomposition. Based on the comparable minimal scale combination principle as applied in the 2D case, the number of complete 3D components will be the smallest value of ''m'', ''n'', and ''q''. The general equation for deriving 3D components is
Line 105 ⟶ 103:
</math>
The pseudo-BEMD method has several advantages. For instance, the sifting procedure of the pseudo-BEMD is a combination of one dimensional sifting. It employs 1D curve fitting in the sifting process of each dimension, and has no difficulty as encountered in the 2D EMD algorithms using surface fitting, which has the problem of determining the saddle point as a local maximum or minimum. Sifting is the process which separates the IMF and repeats the process until the residue is obtained. The first step of performing sifting is to determine the upper and lower envelopes encompassing all the data by using the spline method. Sifting scheme for pseudo-BEMD is like the 1D sifting where the local mean of the standard EMD is replaced by the mean of multivariate envelope curves.
The major disadvantage of this method is that although we could extend this algorithm to any dimensional data we only use it for Two dimension applications. Because the computation time of higher dimensional data would be proportional to the number of IMF's of the succeeding dimensions. Hence, it could exceed the computation capacity for a Geo-Physical data processing system when the number of EMD in the algorithm is large. Hence, we have mentioned below faster and better techniques to tackle this disadvantage.
Source:<ref name=":7" />
▲=== Multi-dimensional ensemble empirical mode decomposition.<ref name=":7" /> ===
A Fast and efficient data analysis is very important for large sequences hence the MDEEMD focuses on two important things
Line 119:
The [[principal component analysis]]/[[Empirical orthogonal functions|empirical orthogonal function]] analysis (PCA/EOF) has been widely used in data analysis and image compression, its main objective is to reduce a data set containing a large number of variables to a data set containing fewer variables, but that still represents a large fraction of the variability contained in the original data set. In climate studies, EOF analysis is often used to study possible spatial modes (i.e., patterns) of variability and how they change with time . In statistics, EOF analysis is known as [[principal component analysis]] (PCA).
Typically, the EOFs are found by computing the eigenvalues and eigen vectors of a spatially weighted anomaly covariance matrix of a field. Most commonly, the spatial weights are the cos(latitude) or, better for EOF analysis, the sqrt(cos(latitude)). The derived eigenvalues provide a measure of the percent variance explained by each mode. Unfortunately, the eigenvalues are not necessarily distinct due to sampling issues. North et al. (Mon. Wea. Rev., 1982, eqns
Atmospheric and oceanographic processes are typically 'red' which means that most of the variance (power) is contained within the first few modes. The time series of each mode (aka, principle components) are determined by projecting the derived eigen vectors onto the spatially weighted anomalies. This will result in the amplitude of each mode over the period of record.
Line 139:
where
: <math>K'_i=\frac{\sum_{i=1}^nK_iN_i}{N}. </math>
Therefore, the compression rate of the spatial ___domain is as follows
Line 146:
The advantage of this algorithm is that an optimized division and an optimized selection of PC/EOF pairs for each region would lead to a higher rate of compression and result into significantly lower computation as compared to a Pseudo BEMD extended to higher dimensions.
=== Fast multidimensional ensemble empirical mode decomposition ===
Source:<ref name=":7" /> For a temporal signal of length ''M'', the complexity of cubic spline sifting through its local extrema is about the order of ''M,'' and so is that of the EEMD as it only repeats the spline fitting operation with a number that is not dependent on ''M''. However, as the sifting number (often selected as 10) and the ensemble number (often a few hundred) multiply to the spline sifting operations, hence the EEMD is time
The fast MEEMD includes the following steps:
Line 162 ⟶ 164:
Note that a detailed knowledge of the intrinsic mode functions of a noise corrupted signal can help in estimating the significance of that mode. It is usually assumed that the first IMF captures most of the noise and hence from this IMF we could estimate the Noise level and estimate the noise corrupted signal eliminating the effects of noise approximately. This method is known as denoising and detrending. Another advantage of using the MEEMD is that the mode mixing is reduced significantly due to the function of the EEMD.<br />The denoising and detrending strategy can be used for image processing to enhance an image and similarly it could be applied to Audio Signals to remove corrupted data in speech. The MDEEMD could be used to break down images and audio signals into IMF and based on the knowledge of the IMF perform necessary operations. The decomposition of an image is very advantageous for radar-based application the decomposition of an image could reveal land mines etc.
== Parallel implementation of multi-dimensional ensemble empirical mode decomposition.
In MEEMD, although ample parallelism potentially exists in the ensemble dimensions and/or the non-operating dimensions, several challenges still face a high performance MEEMD implementation.<ref name=":8" />
[[File:Sample_BEMD_Simulation_results_for_a_noisy_signal.jpg|thumb|Bi-Dimensional EMD corrupted with Noise]]
Line 176 ⟶ 178:
# Its implementation is like the sequential one, which makes it more straightforward.
===
The EEMDs comprising MEEMD are assigned to independent threads for parallel execution, relying on the OpenMP runtime to resolve any load imbalance issues. Stride memory accesses of high-dimensional data are eliminated by transposing these data to lower dimensions, resulting in better utilization of cache lines. The partial results of each EEMD are made thread-private for correct functionality.
=== CUDA implementation
In the GPU CUDA implementation, each EMD, is mapped to a thread. The memory layout, especially of high-dimensional data, is rearranged to meet memory coalescing requirements and fit into the 128-byte cache lines. The data is first loaded along the lowest dimension and then consumed along a higher dimension. This step is performed when the Gaussian noise is added to form the ensemble data. In the new memory layout, the ensemble dimension is added to the lowest dimension to reduce possible branch divergence. The impact of the unavoidable branch divergence from data irregularity, caused by the noise, is minimized via a regularization technique using the on-chip memory. Moreover, the cache memory is utilized to amortize unavoidable uncoalesced memory accesses.<ref name=":8" />
Line 189 ⟶ 191:
Based on the algorithm of BEMD, the implementation method of FABEMD is really similar to BEMD, but the FABEMD approach just changes the interpolation step into a direct envelope estimation method and restricts the number of iterations for every BIMF to one. As a result, two order statistics, including MAX and MIN, will be used for approximating the upper and lower envelope. The size of the filter will depend on the maxima and minima maps obtained from the input. The steps of the FABEMD algorithm are listed below.
===FABEMD algorithm===
Source:<ref name=":0" /> ;Step 1 – Determine and detect local maximum and minimum
Line 218 ⟶ 221:
: <math>\ell = n - \frac{w_{ex} - 1}{2}:n + \frac{w_{ex} - 1}{2},(\ell \ne n)</math><ref name=":0" />
;[[File:Flow chart for FABEMD algorithm.jpg|thumb|upright|Flow chart for FABEMD algorithm<ref>{{Cite book |doi=10.1109/ICASSP.2008.4517859|chapter=A novel approach of fast and adaptive bidimensional empirical mode decomposition|title=2008 IEEE International Conference on Acoustics, Speech and Signal Processing|pages=1313–1316|year=2008|last1=Bhuiyan|first1=Sharif M. A.|last2=Adhami|first2=Reza R.|last3=Khan|first3=Jesmin F.|isbn=978-1-4244-1483-3|s2cid=18226941 }}</ref>]]Step 2 – Obtain the size of window for order-statistic filter
At first, we define <math>d_{\mathrm{adj}-\max}</math> and <math>d_{\mathrm{adj}-\min}</math> to be the maximum and minimum distance in the array which is calculated from each local maximum or minimum point to the nearest nonzero element. Also, <math>d_{\mathrm{adj}-\max}</math> and <math>d_{\mathrm{adj}-\min}</math> will be sorted in descending order in the array according to the convenient selection. Otherwise, we will only consider square window. Thus, the gross window width will be as follows:
Line 257 ⟶ 260:
Here, we take 2-D PDE-based EMD as an example.
===PDE-based BEMD algorithm===
Source:<ref name=":2" /> ;Step 1 – Extend super diffusion model from 1-D to 2-D
Line 314 ⟶ 318:
===Concept===
There are some problems in BEMD and boundary extending implementation in the iterative sifting process, including time
===BPBEMD algorithm
The few core steps for BPBEMD algorithm are:<ref name=":3" />
;Step 1
Line 340 ⟶ 344:
===Advantages===
This method can process larger number of elements than traditional BEMD method. Also, it can shorten the time
===Limitations===
Because most of image inputs are non-stationary which
==Applications==
In the first part, these MEEMD techniques can be used on Geophysical data sets such as climate, magnetic, seismic data variability which takes advantage of the fast algorithm of MEEMD. The MEEMD is often used for nonlinear geophysical data filtering due to its fast algorithms and its ability to handle large amount of data sets with the use of compression without losing key information. The IMF can also be used as a signal enhancement of Ground Penetrating Radar for nonlinear data processing; it is very effective to detect geological boundaries from the analysis of field anomalies.<ref name=":6" />
In the second part, the PDE-based MEMD and FAMEMD can be implemented on audio processing, image processing and texture analysis. Because of its several properties, including stability, less time
==References==
| |||