An Application of a Parallel Algorithm on an Image Recognition

A group of random vectors that the value is below will be distributed by given condition.

Also we consider the step to figure out from x-y coordinates to polar coordinates transformations of the distribution of the given set of the vectors (Fig. 2 and Fig. 3).

In this work, we need to compute the eigenvalues of a covariance matrix to know the principal components of the images. Furthermore, we use the eigenvectors from the eigenvalues to get the information of Principle components.

There are several methods to solve the eigen problem, but there are sequential processes to get all eigenvalues. Also, the structure of the given matrix is broken to do for it. In our work, we want to keep the structure of the given matrix and develop the parallel algorithm. We compare the complexity to compute all eigenvalues of the given matrix between existing algorithm and our algorithm.

Consider the usual Newton iteration (2):

Choose a parameter t > 0 so that the method takes the form

Then

and

Then the parameterized Newton method takes a form:

and

Now, suppose $\left[\begin{array}{c}X\\ \alpha \end{array}\right]\in \text{D}$ and let $\text{L}=\{\left[\begin{array}{c}{U}_k\\ {\lambda }_k\end{array}\right]| U_k \in$$R^n, \parallel U_k{\parallel }_2=1$

and ${\lambda }_k\in R\}$ be the set of all eigenpairs of A. Define a distance measure from a point $\left[\begin{array}{c}X\\ \alpha \end{array}\right]$ to L by

Clearly, $d_L\left(\left[\begin{array}{c}X\\ \alpha \end{array}\right]\right) \ge 0$, $d_L\left(\left[\begin{array}{c}X\\ \alpha \end{array}\right]\right)=0$ implies $\left[\begin{array}{c}X\\ \alpha \end{array}\right]\in$L, and d_L: $\text{D}\to {\text{R}}^{+}$ is continuous (since D is compact, d_L is actually uniformly continuous).

We have the following.

Lemma 1[4]: Let A∈ M_n be Symmetric. Consider the parameterized Newton’s method $X^{\prime }= \frac{1}{\check{\beta }}{\left(aI-A\right)}^{-1}X$, and ${\alpha }^{\prime }= \alpha -\frac{t}{\beta }$, where $\text{β}=X^T(\alpha I-A){ }^{-1}X$, and

Then $d_L\left(\left[\begin{array}{c}X\prime \\ \alpha \prime \end{array}\right]\right)$ is minimized at $t={\left(\frac{\beta }{\check{\beta }}\right)}^2$ with

Therefore, we have the following modification of the Newton’s method:

In this 2.3, we discuss it about an application of eigenfaces from 25 different expressions of a face.

There are 5 steps to construct for face images.

Step 1: An input of the origin images

The size of face image is N × N and the number of the face images that are recognized as candidates are M such that each is N² × 1 column vector. Denote the set of face vectors that are recognized as candidates by S (Fig 4).

Step 2: Normalization of the image

We normalize the image on the basis of setting average and variance to reduce errors caused by the light and background (Figure 5).

Step 3: Computation of the average Face’s vector

We compute the average face vector from the face set S of recognition candidates (Figure 6).

In the computation for eigenpairs we develop the parallel algorithm with modified Newton method each eigenpair. Even though, the given matrix is ill conditioned, we can get all eigenpairs. This is an ill-conditioned matrix case:

Example1: Let $\text{H}=\left[\begin{array}{ccccc}1& 1/2& 1/3& \cdots & 1/n\\ 1/2& 1/3& \ddots & \ddots & ⋮\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ 1/n& \cdots & \cdots & \cdots & \frac{1}{2n-1}\end{array}\right]$ be a n by n Hilbert matrix H. The Hilbert matrix is a well-known example of an ill-conditioned positive. Because the smallest eigenvalue λ₁₂ of H∈M₁₂ is so near zero, many conventional algorithms produce λ₁₂ = 0. Our method gives the following experimental results:

Set the convergence criterion, ε=2 × 10⁻¹⁶, i.e., .

Suppose $D=\left\{\left[\begin{array}{c}X\\ \alpha \end{array}\right]| X \in \left\{e_1,e_2, \dots ,e_n\right\}, and \alpha \in \{ h_{1,1},h_{2,2}, \dots ,h_{12,12}\right\}$ is the initial set of points where ei is the ith column of the identity matrix and hi,i is the ith diagonal entry of H.

If we have some clustering case on the target matrix, we can also overcome all eigenpairs[Figure 7].

To overcome the lost eigenpairs from MNM by the Gram-Schmidt orthogonalization process.

Suppose both [x₁, α₁]^T and [x₂, α₂] ^T converge to [U₁,λ₁]^T.

It is shown the MNM in (10), (11) and this is algorithm as below:

Modified Newton’s Algorithm

Set ${\text{α}}_k{}^{\left(1\right)}$ and ${\text{x}}_k{}^{\left(1\right)}$.

$\left({\text{α}}_k{}^{\left(1\right)},{\text{x}}_k{}^{\left(1\right)}\right)$ is an initial eigenpairs where ${\text{α}}_k{}^{\left(1\right)}$ and ${\text{x}}_k{}^{\left(1\right)}$, k = 1, …, n are the diagonal entries of the given matrix and $\left\{e_1,e_2, \dots , e_n \right\}$.

For k = 1, …, n do (in parallel)

For j = 1, … do until convergence

End

End

We apply the MNM(Modified Newton Method) to generate eigen-imgages at each step for image recognition problems.

In this case, we work to find the all eigenpairs of a covariance matrix which is generated by the characteristic vectors.

Step 4: Solving of the eigen problem of a Covariance Matrix C

We compute the eigenvalue λ_i and the corresponding eigenvectors μ_i of the covariance matrix C. It is based on our algorithm. The eigenvalue present an average face of the given image and it produce a eigen-face(Fig. 8).