EigenMoments

From Wikipedia, the free encyclopedia
Jump to: navigation, search
concept chart of EigenMoment algorithm
Signal space is transformed into moment space, i.e. Geometric Moments, then it is transformed into noise space in which axes with lowest rate of noise are retained and finally transformed into feature space

EigenMoments[1] is a set of orthogonal, noise robust, invariant to rotation, scaling and translation and distribution sensitive moments. Their application can be found in signal processing and computer vision as descriptors of the signal or image. The descriptors can later be used for classification purposes.

It is obtained by performing orthogonalization, via eigen analysis on geometric moments.[2]

Framework summary[edit]

EigenMoments are computed by performing eigen analysis on the moment space of an image by maximizing Signal to Noise Ratio in the feature space in form of Rayleigh quotient.

This approach has several benefits in Image processing applications:

  1. Dependency of moments in the moment space on the distribution of the images being transformed, ensures decorrelation of the final feature space after eigen analysis on the moment space.
  2. The ability of EigenMoments to take into account distribution of the image makes it more versatile and adaptable for different genres.
  3. Generated moment kernels are orthogonal and therefore analysis on the moment space becomes easier. Transformation with orthogonal moment kernels into moment space is analogous to projection of the image onto a number of orthogonal axes.
  4. Nosiy components can be removed. This makes EigenMoments robust for classification applications.
  5. Optimal information compaction can be obtained and therefore a few number of moments are needed to characterize the images.

Problem formulation[edit]

Assume that a signal vector  s \in \mathcal{R}^n is taken from a certain distribution having coorelation  C \in \mathcal{R}^{n \times n} ,i.e. C=E[ss^T] where E[.] denotes expected value.

Dimension of signal space, n, is often too large to be useful for practical application such as pattern classification, we need to transform the signal space into a space with lower dimensionality.

This is performed by a two-step linear transformation:

q=W^T X^T s,

where q=[q_1,...,q_n]^T \in \mathcal{R}^k is the transformed signal, X=[x_1,...,x_n]^T \in \mathcal{R}^{n \times m} a fixed transformation matrix which transforms the signal into the moment space, and W=[w_1,...,w_n]^T \in \mathcal{R}^{m \times k} the transformation matrix which we are going to determine by maximizing the SNR of the feature space resided by q. For the case of Geometric Moments, X would be the monomials. If m=k=n, a full rank transformation would result, however usually we have m \leq n and k \leq m. This is specially the case when n is of high dimensions.

Finding W that maximizes the SNR of the feature space:

 SNR_{transform} = \frac{w^TX^TCXw}{w^TX^TNXw},

where N is the correlation matrix of the noise signal. The problem can thus be formulated as

{w_1,...,w_k}=argmax_w \frac{w^TX^TCXw}{w^TX^TNXw}

subject to constraints:

w_i^T X^T NX w_j=\delta_{ij}, where \delta_{ij} is the Kronecker delta.

It can be observed that this maximization is Rayleigh quotient by letting A=X^TCX and B=X^TNX and therefore can be written as:

{w_1,...,w_k}=\underset{x}{\operatorname{arg\,max}} \frac{w^TAw}{w^TBw}, w_i^TBw_j=\delta_{ij}

Rayleigh quotient[edit]

Optimization of Rayleigh quotient[3][4] has the form:

 \max_w R(w)= \max_w \frac{w^{T}Aw}{w^{T}Bw}

and A and B, both are symmetric and B is positive definite and therefore invertibale. scaling w does not change the value of the object function and hence and additional scalar constraint w^{T}Bw=1 can be imposed on w and no solution would be lost when the objective function is optimized.

This constraint optimization problem can be solved using Lagrangian multiplier:

 \max_w {w^{T}Aw} subject to {w^{T}Bw}=1

 \max_w \mathcal{L}(w) = \max_w (w{T}Aw-\lambda w^{T}Bw)

equating first derivative to zero and we will have:

Aw=\lambda Bw

which is an instance of Generelized Eigenvalue Problem(GEP). The GEP has the form:

 Aw=\lambda Bw

for any pair (w,\lambda) that is a solution to above equation, w is called a generalized eigenvector and  \lambda is called a generalized eigenvalue.

Finding w and \lambda that satisfies this equations would produce the result which optimizes Rayleigh quotient.

One way of maximizing Rayleigh quotient is through solving the Generalized Eigen Problem. Dimension reduction can be performed by simply choosing the first components w_i, i=1,...,k, with the highest values for R(w) out of the m components, and discard the rest. Interpretation of this transformation is rotating and scaling the moment space, transforming it into a feature space with maximized SNR and therefore, the first k components are the components with highest k SNR values.

The other method to look at this solution is to use the concept of simultaneous diagonalization instead of Generalized Eigen Problem.

Simultaneous diagonalization[edit]

  1. Let A=X^TCX and B=X^TNX as mentioned earlier. We can write W as two separate transformation matrices:

W=W_1W_2.

  1. W_1 can be found by first diagonalize B:

P^TBP=D_B.

Where D_B is a diagonal matrix sorted in increasing order. Since B is positive definite, thus D_B>0. We can discard those eigenvalues that large and retain those close to 0, since this means the energy of the noise is close to 0 in this space, at this stage it is also possible to discard those eigenvectors that have large eigenvalues.

Let \hat P be the first k columns of P, now \hat{P^T}B\hat P=\hat{D_B} where \hat{D_B} is the k \times k principal submatrix of D_B.

  1. Let

W_1=\hat{P} \hat{D_B}^{-1/2}

and hence:

W_1^T B W_1=(\hat P \hat{D_B}^{-1/2})^TB(\hat P \hat{D_B}^{-1/2})=I.

W_1 whiten B and reduces the dimensionality from m to k. The transformed space resided by q'=W_1^TX^Ts is called the noise space.

  1. Then, we diagonalize W_1^T A W_1:

W_2^T W_1^T A W_1 W_2 = D_A,

where W_2^T W_2 =I. D_A is the matrix with eigenvalues of W_1^T A W_1 on its diagonal. We may retain all the eigenvalues and their corresponding eigenvectors since the most of the noise are already discarded in previous step.

  1. Finally the transformation is given by:

W=W_1W_2

where W diagonalizes both the numerator and denominator of the SNR,

W^TAW=D_A, W^TBW=I and the transformation of signal s is defined as q=W^TX^Ts=W_2^TW_1^TX^Ts.

Information loss[edit]

To find the information loss when we discard some of the eigenvalues and eigenvectors we can perform following analysis:

 \begin{array}{lll}
\eta &=& 1- \frac{trace(W_1^TAW_1)}{trace(D_B^{-1/2}P^TAPD_B^{-1/2})}\\
     &=& 1- \frac{trace(\hat{D_B}^{-1/2}\hat{P}^TA\hat{P}\hat{D_B}^{-1/2})}{trace(D_B^{-1/2}P^TAPD_B^{-1/2})}
     
\end{array}

Eigenmoments[edit]

Eigenmoments are derived by applying the above framework on Geometric Moments. They can be derived for both 1D and 2D signals.

1D signal[edit]

If we let X=[1,x,x^2,...,x^{m-1}], i.e. the monomials, after the transformation X^T we obtain Geometric Moments, denoted by vector M, of signal s=[s(x)],i.e. M=X^Ts.

In practice it is difficult to estimate the correlation signal due to insufficient number of samples, therefore parametric approaches are utilized.

One such model can be defined as:

r(x_1,x_2)=r(0,0)e^{-c(x_1-x_2)^2},

Model for correlation in signal
Plot of the parametric model which predicts correlations in the input signal. r(x_1,x_2)=r(0,0)e^{-c(x_1-x_2)^2}

where r(0,0)=E[tr(ss^T)]. This model of correlation can be replaced by other models however this model covers general natural images.

Since r(0,0) does not affect the maximization it can be dropped.

A=X^TCX=\int_{-1}^{1}\int_{-1}^{1}[x_1^j x_2^i e^{-c(x_1-x_2)^2}]_{i,j=0}^{i,j=m-1}dx_1dx_2

The correlation of noise can be modelled as \sigma_n^2\delta(x_1,x_2), where \sigma_n^2 is the energy of noise.Again \sigma_n^2 can be dropped because the constant does not have any effect on the maximization problem.

B=X^TNX=\int_{-1}^{1}\int_{-1}^{1}[x_1^j x_2^i\delta(x_1,x_2)]_{i,j=0}^{i,j=m-1}dx_1dx_2 B=X^TNX=\int_{-1}^{1}[x_1^{j+i}]_{i,j=0}^{i,j=m-1}dx_1=X^TX

Using the computed A and B and applying the algorithm discussed in previous section we find W and set of transformed monomials \Phi=[\phi_1,...,\phi_k]=XW which produces the moment kernels of EM. The moment kernels of EM decorrelate the correlation in the image.

\Phi^TC\Phi=(XW)^TC(XW)=D_C,

and are orthogonal:

 \begin{array}{lll}\Phi^T\Phi& = & (XW)^T(XW) \\
& = & W^TX^TX\\
& = & W^TX^TNXW\\
& = & W^TBW\\
& = & I\\
\end{array}

Example computation[edit]

Taking c=0.5, the dimension of moment space as m=6 and the dimension of feature space as k=4, we will have:

W=
\left( \begin{array}{cccc}
0.0       & 0        & -0.7745 & -0.8960 \\
2.8669    & -4.4622  & 0.0     & 0.0     \\
0.0       & 0.0      & 7.9272  & 2.4523  \\
-4.0225   & 20.6505  & 0.0     & 0.0     \\
0.0       & 0.0      & -9.2789 & -0.1239 \\
-0.5092   & -18.4582 & 0.0     & 0.0      \end{array} \right)

and

 \begin{array}{lll}
\phi_1&=& 2.8669x - 4.0225x^3 - 0.5092x^5 \\
\phi_2&=&-4.4622x + 20.6505x^3 - 18.4582x^5 \\
\phi_3&=&-0.7745  + 7.9272x^2 - 9.2789x^4 \\
\phi_4&=&-0.8960  + 2.4523x^2 - 0.1239x^4 \\
\end{array}

2D signal[edit]

The derivation for 2D signal is the same as 1D signal except that conventional Geometric Moments are directly employed to obtain the set of 2D EigenMoments.

The definition of Geometric Moments of order (p+q) for 2D image signal is:

m_{pq}=\int_{-1}^1\int_{-1}^1 x^py^qf(x,y)dxdy.

which can be denoted as M=\{m_{j,i}\}_{i,j=0}^{i,j=m-1}. Then the set of 2D EigenMoments are:

\Omega=W^TMW,

where \Omega=\{\Omega_{j,i}\}_{i,j=0}^{i,j=k-1} is a matrix that contains the set of EigenMoments.

\Omega_{j,i}=\Sigma_{r=0}^{m-1}\Sigma_{s=0}^{m-1}w_{r,j}w_{s,i}m_{r,s}.

EigenMoment invariants (EMI)[edit]

In order to obtain a set of moment invariants we can use normalized Geometric Moments \hat M instead of M.

Normalized Geometric Moments are invariant to Rotation,Scaling and Transformation and defined by:

\begin{array}{lll}
\hat m_{pq} & = & \alpha^p+q+2\int_{-1}^{1}\int_{-1}^{1}[(x-x^c)cos(\theta)+(y-y^c)sin(\theta)]^p\\
            & = & \times [-(x-x^c)sin(\theta)+(y-y^c)cos(\theta)]^q\\
            & = & \times f(x,y)dxdy,\\
\end{array}

where: (x^c,y^c) = (m_{10}/m_{00},m_{01}/m_{00}) is the centroid of the image f(x,y) and

\begin{array}{lll}
\alpha&=&[m_{00}^{S}/m_{00}]^{1/2}\\
\theta&=&\frac{1}{2}tan^{-1}\frac{2m_{11}}{m_{20}-m_{02}}
\end{array}
.

m_{00}^{S} in this equation is a scaling factor depending on the image. m_{00}^{S} is usually set to 1 for binary images.

See also[edit]

References[edit]

  1. ^ Pew-Thian Yap, Raveendran Paramesran, Eigenmoments, Pattern Recognition, Volume 40, Issue 4, April 2007, Pages 1234-1244, ISSN 0031-3203, 10.1016/j.patcog.2006.07.003.
  2. ^ M. K. Hu, "Visual Pattern Recognition by Moment Invariants", IRE Trans. Info. Theory, vol. IT-8, pp.179–187, 1962
  3. ^ T. De Bie, N. Cristianini, R. Rosipal, Eigenproblems in pattern recognition, in: E. Bayro-Corrochano (Ed.), Handbook of Computational Geometry for Pattern Recognition, Computer Vision, Neurocomputing and Robotics, Springer, Heidelberg, 2004G.
  4. ^ Strang, Linear Algebra and Its Applications, second ed., Academic Press, New York, 1980.

External links[edit]