Printer Friendly

The 2D Spectral Intrinsic Decomposition Method Applied to Image Analysis.

1. Introduction

The need of components extraction and reconstruction in signal and image processing in time frequency analysis is very strong for many fields of application. Notorious methods that have been proposed include Fourier technics, wavelet decomposition, and Empirical Mode Decomposition. While Fourier transform is localized in frequency, wavelets are localized in both time and frequency; EMD is autoadaptive. EMD decomposes a signal in AM-FM components called Intrinsic Mode Functions (IMF) and a residue. This nonlinear and nonstationary decomposition works on 1D signals [1] and 2D signals such as images [2, 3]. The EMD algorithm is based on a procedure called sifting process which iteratively uses the upper and lower envelopes to extract IMFs. To create a mathematical model to compute envelopes directly, an envelope operator has been proposed in [4] and from this operator a new decomposition method called Spectral Intrinsic Decomposition, SID, was proposed in [5].

The SID method allows decomposing any signal into a superposition of Spectral Proper Mode Functions (SPMFs) [5]. This method has been presented in a 1D version and depends on an operator interpolating the characteristics points of the signal to be decomposed. In this paper, the two-dimensional version of the Spectral Intrinsic Decomposition for images analysis is introduced. An algorithm for a faster spectral decomposition is proposed and illustrated with some images. We first recall the SID principle in one dimension and propose a faster method to determine the signal characteristics points in Section 2. Than an algorithm of the two-dimensional SID is presented in Section 3. Applications on grayscale images are depicted in Section 3.1.

2. The Spectral Intrinsic Decomposition Method

The Spectral Intrinsic Decomposition Method decomposes any signal into a combination of eigenvectors of a Partial Differential Equation (PDE) interpolation operator as presented in [5, 6].

2.1. The PDEs System Interpolator. For a given signal [s.sub.0], the upper ([s.sup.+]) and lower ([s.sup.-]) envelope are the asymptotic solution of the following PDEs system:

[mathematical expression not reproducible]. (1)

[alpha] is the tension parameter which ranges from 0 to 1. [g.sup.+] and [g.sup.-] are diffusivity functions for upper and lower envelope which are equal to zero at characteristic points of [s.sub.0] and range from zero to one. [g.sup.[+ or -]] based on Maximum Curvature Points (MCP) can be computed as follows:

[mathematical expression not reproducible], (2)

where sgn denotes the sign function.

Equation (1) is resolved numerically in its discrete implicit unconditionally stable scheme as follows:

[S.sup.k+1] = [S.sup.k] + [DELTA]tA[S.sup.k+1], [S.sup.0] = [S.sub.0], (3)

where [DELTA]t is the time step, [S.sup.k+1] = s(x, k[DELTA]t) is signal value at step k + 1, and A is a matrix formed with finite difference approximation coefficients of second- and fourth-order differential operators (resp., [D.sub.2] and [D.sub.4]), as A = G([alpha][D.sub.2] - (1 - [alpha])[D.sub.4]), with G being the diagonal matrix constructed with discrete version of stopping function values g(x), exactly, G(I, i) = g(i).

So the explicit form leads to the following numerical resolution:

[S.sup.k+1] = [(I - [DELTA]tA).sup.-1] [S.sup.k], [S.sup.0] = [s.sub.0], k [greater than or equal to] 0 (4)

with I being the identity matrix. Finally (1) can be decomposed into a linear system from implicit numerical scheme (4) by

[S.sup.(k+1)] = [L.sup.-1][S.sup.k], [S.sup.0] = [s.sub.0], k [greater than or equal to] 0. (5)

L is given by L = I - [DELTA]tA.

The operator matrix, L, has real-valued eigenvalues that are always greater than or equal to 1. Then, eigenvalues, [[lambda].sub.n], of [L.sup.-1] are always smaller than or equal to 1 (0 < [[lambda].sub.n] [less than or equal to] 1); see [4].

2.2. On the Asymptotic Solution. Iterative scheme (5) can be rewritten in terms of initial solution [s.sub.0] as

[S.sup.k] = [([L.sup.-1]).sup.k] [s.sub.0], k [greater than or equal to] 1. (6)

After convergence (see [7]), the asymptotic solution, [S.sup.[infinity]], is given by

[S.sup.[infinity]] = [([L.sup.-1]).sup.[infinity]] [s.sub.0]. (7)

Let V be a matrix of [L.sup.-1]'s sequence of eigenvectors ([V.sub.n]) and D a diagonal matrix having [L.sup.-1]'s sequence of eigenvalues ([[lambda].sub.n]), at the diagonal. So we have the following decomposition [L.sup.-1] = VD[V.sup.-1]. It is easy to see that

[([L.sup.-1]).sup.k] = [(VD[V.sup.-1]).sup.k] = V[D.sup.k][V.sup.-1]. (8)

So, the asymptotic solution in (7) is given by

[S.sup.[infinity]] = (V[D.sup.[infinity]][V.sup.-1])[S.sub.0]. (9)

The asymptotic eigenvalue matrix [D.sup.[infinity]] is a diagonal matrix with eigenvalues [[lambda].sup.[infinity].sub.n] = 1 only at loci where matrix G is zeroed, and [[lambda].sup.[infinity].sub.n] = 0, where g[n] > 0. Finally, the asymptotic solution of the PDE interpolator system is a linear combination of fixed vector point of upper and lower envelope operators.

2.3. A Faster Stopping Function for Discrete Signal. For image processing we will consider region boundaries as characteristic points. The characteristic points of the upper envelope will be the local maximums and the limits of the regions where the value of the gray level of the pixel is equal to or greater than the gray level of all the pixels in their neighborhood represented, for example, by a rectangular window.

We define the diffusion function [g.sup.-.sub.M] for lower envelope to be equal to 1 everywhere except in characteristic points of the lower envelope where it will be equal to 0.

Similarly the characteristic points of the lower envelope are local minimums and region boundaries where the pixel value is equal to or less than the gray level of all pixels in their neighbors. We define the diffusion function [g.sup.+.sub.M] for upper envelope to be equal to 1 everywhere except in characteristics points of the upper envelope where it will be equal to 0.

The diffusivity function called stopping function [g.sup.+.sub.M] is calculated by using morphological dilation and erosion operations [8].

Let h = [-1, 0, 1] be a structured element; the grayscale dilation of s by h at x is given by

[mathematical expression not reproducible]. (10)

The grayscale erosion of s by b at x is given by

[mathematical expression not reproducible]. (11)

s [cross product] b is equal to s at local maxima and when s is locally constant; s [??] b is equal to s at local minima and when s is locally constant.

[g.sup.+.sub.M] is zeroed at points which are invariant to morphological dilation and variant to morphological erosion; [g.sup.+.sub.M] is equal to 1 for any other point.

Similarly, [g.sup.-.sub.M] is zeroed at points which are invariant to morphological erosion and variant to morphological dilation; [g.sup.-.sub.M] is equal to 1 for any other point.

Let

[mathematical expression not reproducible]. (12)

We have

[mathematical expression not reproducible] (13)

[g.sub.M] functions are faster than g to compute and give satisfying results for the computation of envelope operators for real images (Table 1).

Figure 1 shows an example of calculating the envelope using [g.sub.M], [g.sup.+.sub.M] for upper envelope and [g.sup.-.sub.M] for lower envelope.

2.4. The Spectral Intrinsic Decomposition. In the following, E denotes either the upper or lower envelope operator. The upper and lower envelope of the signal are calculated with the eigenvectors associated with eigenvalue [lambda] = 1. Hence, [S.sup.[infinity]] in formula (9) is a linear combination of all 1-eigenvectors of the envelope operator E weighted by the signal amplitude. Instead of focusing only on the envelope calculus, we now consider all the set of eigenvalues of the envelope operator E.

The Spectral Intrinsic Decomposition procedure is defined as the calculus of all the SPMFs for a given signal. E = [L.sup.-1]. The same procedure can be performed with the lower envelope. The eigendecomposition of E gives [[V.sub.E], [L.sub.E]] = eig(E), where [V.sub.E] = [[V.sub.1], ..., [V.sub.size(s0)]] and [L.sub.E] = [[L.sub.1], ..., [E.sub.size(s0)]] (with the possibility of zeros to complete the size of the vector) are, respectively, the set of eigenvectors and the set of eigenvalues of E. The coefficient reconstruction of [s.sub.0] is given by C = [L.sub.E][V.sup.-1.sub.E][s.sup.[perpendicular to].sub.0], with [s.sup.[perpendicular to].sub.0] being the transpose of [s.sub.0].
Algorithm 1: Pseudocode for decomposition and recomposition.

(1) M [left arrow] transforme image to data
(2) NL [left arrow] number of lines of M
(3) NC [left arrow] number of columns of M
(4) [M.sub.R] [left arrow] NL by NC zeroed matrix
(5) for i [left arrow] 1, NL do
(6)     [s.sub.i] [left arrow] line i of M
(7)     compute [g.sup.+.sub.i] from [s.sub.i]
(8)     compute [E.sub.i]
(9)     decompose [mathematical expression not reproducible]
(10)    compute [mathematical expression not reproducible]
(11)    for j [left arrow] 1, NC do
(12)        [M.sub.R] (i, j) [left arrow] [V.sub.i](j) * [C.sub.i](j)
(13)    end for
(14) end for
(15) recompose image from [M.sub.R]


Hence [s.sub.0] is computed by the formula s0 = VC (Algorithm 2). The Spectral Intrinsic Decomposition of [s.sub.0] is given as follows:

[s.sub.0] = [N.summation over (k=1)] [V.sub.k][C.sub.k], N = size ([s.sub.0]). (14)

This decomposition is intrinsic and depends only on the position of the characteristic points of [s.sub.0] that define the diffusivity function in the interpolation operator. We notice that the SID with lower envelope works like the SID with the upper envelope and has the same reconstruction ability.

2.5. Advantage and Disadvantage of SID. The SID is adaptive and depends on the position of the characteristics points of the signal. It is autoadaptive and works for nonlinear and nonstationary signal. SID can decompose an IMF and can be used to separate mixing mode [9] in EMD.

However, the main disadvantage of the proposed SID algorithm is the computation time when the size of signal is a large. This is due to matrix inversion in the algorithm. Thus a faster algorithm is proposed in the next section.

3. The 2D Spectral Intrinsic Decomposition Algorithm

In this section we present, in Algorithm 1, the 2D SID procedure and implement it for images decomposition-recomposition.

3.1. The Algorithm of Image Decomposition and Recomposition by SID. Let us consider an image as represented by a matrix M (Line (1)). Each row i of the matrix M (Line (5)) can be seen as a one-dimensional signal [s.sub.i]. Thus, we can apply the spectral decomposition of [s.sub.i] (Lines (6) to (10)) as described in [4].

Each line can be recomposed to build a matrix [M.sub.R] (Lines (11) to (13)) and finally reconstruct the image from [M.sub.R] (Line (15)). Image decomposition and recomposition are described in Algorithm 1. We can also make decomposition along columns and catch more properties of the image to be analyzed.
Algorithm 2: Pseudocode to extract SPMFs between two eigenvalues.

(1) [[[lambda].sub.min], [[lambda].sub.max]] [left arrow] eigenvalues
    interval to extract
(2) M [left arrow] transforms image to data
(3) NL [left arrow] number of lines of M
(4) NC [left arrow] number of columns of M
(5) [M.sub.R] [left arrow] NL by NC zeroed matrix
(6) for i [left arrow] 1, NL do
(7)     [S.sub.i] [left arrow] line i of M
(8)     compute [g.sup.+.sub.i] from [s.sub.i]
(9)     compute [E.sub.i]
(10)    decompose [mathematical expression not reproducible]
(11)    [mathematical expression not reproducible]
(12)    for j [left arrow] 1, NC do
(13)        if [mathematical expression not reproducible] then
(14)           [mathematical expression not reproducible]
(15)        end if
(16)    end for
(17)    compute [mathematical expression not reproducible]
(18)    for j [left arrow] 1, NC do
(19)        [mathematical expression not reproducible]
(20)    end for
(21) end for


The elementary components of a spectral decomposition are the modulation of eigenvectors by their coefficients as can be seen in (14). It is clear that these components depend on eigenvalues of the envelope operator.

The range of smallest eigenvalues catches higher frequencies contents of the reconstructed signal with the smallest modulated amplitude.

So we can associate components which have similar frequency and amplitude by summing the components that have same eigenvalues; this method works well for signal in one dimension. For images, it is possible numerically to have missing eigenvalues in many lines. Hence, to avoid this drawback, elementary components which have the same eigenvalues will be associated with the same belonging to a specific range of eigenvalues.

3.2. Application to Image Components Extraction. In the following, 2D SID is applied to very known images test to demonstrate the ability of this pectoral intrinsic decomposition for images analysis, particularly in components extraction. In Figures 4(a), 3(a), and 2(a), we have a representation of high frequency components on Figures 4(b), 3(b), and 2(b); we note that they are more sensitive to small variations of the intensity of the image than low frequencies components in Figures 4(c), 3(c), and 2(c).

4. Conclusion

In this paper, we have presented a new method for autoadaptive image representation called two-dimensional version of the Spectral Intrinsic Decomposition. A new faster diffusivity function in the computation of the mean envelope operator is also provided. In future works, we will investigate how to use the Spectral Proper Mode Functions (SPMFs) to do signals classification or to treat other aspects of image processing, like edge detection, segmentation, and so on.

https://doi.org/10.1155/2017/7948571

Conflicts of Interest

The authors declare that they have no conflicts of interest.

References

[1] N. E. Huang, Z. Shen, S. R. Long et al., "The empirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary time series analysis," Proceedings A, vol. 454, no. 1971, pp. 903-995, 1998.

[2] J. C. Nunes, Y. Bouaoune, E. Delechelle, O. Niang, and P. Bunel, "Image analysis by bidimensional empirical mode decomposition," Image and Vision Computing, vol. 21, no. 12, pp. 1019-1026, 2003.

[3] F. B. Arfia, A. Sabri, M. B. Messaoud, and M. Abid, "The Modified Bidimensional Empirical Mode Decomposition for Color Image Decomposition," in Proceedings of the World Congress on Engineering, vol. 2, 2011.

[4] O. Niang, E. Delechelle, and J. Lemoine, "A spectral approach for sifting process in empirical mode decomposition," Signal Processing, IEEE Transactions on, vol. 58, no. 11, pp. 5612-5623, 2010.

[5] O. Niang, A. Thioune, E. Delechelle, and J. Lemoine, "Spectral Intrinsic Decomposition Method for Adaptive Signal Representation," ISRN Signal Processing, vol. 2012, pp. 1-10, 2012.

[6] O. Niang, Decomposition Modale Empirique: Contribution a la Modelisation Mathematique et Application en Traitement du Signal et de lImage [Ph.D. thesis], Universite Paris XII Val de Marne, 2007.

[7] O. Niang, A. Thioune, E. Delechelle, M. T. Niane, and J. Lemoine, "About a Partial Differential Equation-Based Interpolator for Signal Envelope Computing: Existence Results and Applications," ISRN Signal Processing, vol. 2013, pp. 1-18, 2013.

[8] L. Vincent, "Morphological grayscale reconstruction in image analysis: applications and efficient algorithms," IEEE Transactions on Image Processing, vol. 2, no. 2, pp. 176-201, 1993.

[9] Y. Gao, G. Ge, Z. Sheng, and E. Sang, "Analysis and solution to the mode mixing phenomenon in EMD," in Proceedings of the 1st International Congress on Image and Signal Processing, CISP 2008, pp. 223-227, May 2008.

Samba Sidibe, Oumar Niang, Abdoulaye Thioune, Abdoul-Dalibou Abdou, and Ndeye Fatou Ngom

Laboratoire de Traitementde I'Information et Systemes Intelligents, Ecole Polytechnique de Thies, BPA10, Thies, Senegal

Correspondence should be addressed to Oumar Niang; oniang@ucad.sn

Received 5 July 2016; Revised 4 January 2017; Accepted 18 January 2017; Published 20 December 2017

Academic Editor: M. Jamal Deen

Caption: Figure 1: The effectiveness of envelope computation using [g.sub.M] instead of g.

Caption: Figure 2: Decomposition (a), component extraction and representation of high frequency component ([lambda] [member of] [0, 0.1]) (b), medium frequency component([lambda] [member of] [0.5, 0.7]) (c), high and medium frequency component([lambda] < 1) (d), low frequency component ([lambda] = 1) (e), and recomposition of all components (f).

Caption: Figure 3: Decomposition (a), component extraction and representation of high frequency component ([lambda] [member of] [0, 0.1]) (b), medium frequency component([lambda] [member of] [0.5, 0.7]) (c), high and medium frequency component([lambda] < 1) (d), low frequency component ([lambda] = 1) (e), and recomposition of all components (f).

Caption: Figure 4: Decomposition (a), component extraction and representation of high frequency component ([lambda] [member of] [0, 0.1]) (b), medium frequency component([lambda] [member of] [0.5, 0.7]) (c), high and medium frequency component([lambda] < 1) (d), low frequency component ([lambda] = 1) (e), and recomposition of all components (f).
Table 1

Image         Width   Height   Time for [g.sup.[+ or -]]

Figure 4(a)    300     300             0,4684466
Figure 3(a)    400     266            0,826974833
Figure 2(a)    400     272              0,807968

Image         Time for [g.sup.[+ or -].sub.M]

Figure 4(a)               0.320695
Figure 3(a)              0,2877035
Figure 2(a)               0,284108
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Sidibe, Samba; Niang, Oumar; Thioune, Abdoulaye; Abdou, Abdoul-Dalibou; Ngom, Ndeye Fatou
Publication:Journal of Electrical and Computer Engineering
Date:Jan 1, 2018
Words:2944
Previous Article:UFIR Filtering for GPS-Based Tracking over WSNs with Delayed and Missing Data.
Next Article:Improved Design of Bit Synchronization Clock Extraction in Digital Communication System.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |