Three Dimensional Face Surfaces Analysis using Geodesic Distance

Veiw figure View Figure

2.1. Reference Point Detection

The reference point (nose tip) is detected manually or automatically. There are several automatic approaches: L. Ballihi et al are developed an automatic algorithm nose end detection of a 3D face in ^[13]. This algorithm is based on two cuts of facial surface. The first is the transverse face of the mass center. The second cut is based on the minimum depth point of the horizontal curve obtained by the first cut. The output of the last cut is a vertical curve and the minimum depth of this curve is the end of 3D face nose. In ^[14] S. Bahanbin et al use Gabor filters to automatically detect the nose tip. Another method has been used by C. Xu et al in ^[15], this method computes the effective energy of each neighbor pixel, then be determined the mean and variance of each neighbor pixel and uses the SVM to specify point end of the nose. L.H. Anuar et al ^[16] use a local geometry curvature and point signature to detect a nose tip region in 3D face model. In this work we have detected the point of reference p₀ (nose tip) manually. The following figure (Figure 2) summarizes the steps to detect the nose tip of a 3D face of an image of the database SHREC2008.

Figure 2. 3D face nose end detection steps: (a) 3D face image; (b) Manual nose tip selection; (c) Reference point detection

Download as

Veiw figure View Figure

2.2. Geodesic Distance

The geodesic distance between two points’ p₀ and p of 3D face surface is the shortest path between the two points while remaining on the facial surface. In the context of calculating the geodesic distance R. Kimmel and J.A. Sethian ^[17] propose the method of Fast Marching as a solution of the Eikonal equation.

Eikonal equation is of the form:

(1)

With:

is an open set in Rⁿ housebroken limit.

denote the gradient.

is the Euclidean norm.

The Fast Marching method is a numerical method for solving boundary value problems of the Eikonal equation ^{[17, 18, 19]}. The algorithm is similar to the Dijkstra's algorithm ^[20] and uses that information flows only to the outside from the planting area.

Figure 3. 3D facial surface discretized on triangular mesh of N vertices

Download as

Veiw figure View Figure

We consider a 3D face surface discretized using a triangular mesh with N vertices. Figure 3 shows a 3D face image of the Shape REtrieval Contest 2008 (SHREC2008) database whose obverse surface is discretized into a triangular mesh.

The geodesic distance between two points on a surface is calculated as the length of the shortest path connecting the two points. Using the Fast Marching algorithm on the triangulated surface 3D face, we can compute the geodesic distance between the reference point P₀ and the other point’s p constructing the facial surface.

The geodesic distance between p0 and p is approximated by the following expression:

(2)

With:

• is the path between p₀ and according to the surface S of the 3D face.

• is the path length.

The following figure (Figure 4) shows the steps for determining the geodesic distance using a 3D face image of SHREC2008 database.

Figure 4. 3D face geodesic distance computes Steps: (a) 3D face image; (b) Reference point detection; (c) Discretization by triangular mesh; (d) Geodesic distance computing

Download as

Veiw figure View Figure

Repeating this computation (geodesic distance ) between the reference point p₀ and each point p of the surface S of the 3D face, then we compute a geodesic distance matrix Ψ:

With, δ_ij = .

To realize our 3D face recognition system, we use the Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) for writing space of the geodesic distance matrix [Ψ].

2.3. Principal Component Analysis (PCA)

The Principal Component Analysis (PCA) is to express a set of variables into a set of linear combinations of uncorrelated factors together, these factors account for a fraction of increasingly lower variability of the data. This method is used to represent the original data in a space of dimension less than the original space while minimizing the loss of information.

The recognition is performed by comparing the projection coefficients of a test image with those in the electronic driving components. The performance of the PCA will be illustrated by the following stages:

• We load the data to be compared in a matrix Ψ.

• We thus determine the size of the data set:

(3)

- To summarize the data, we compute the sample mean vector and the sample standard deviation vector:

(4)

• Normalize the data. Here, the calibration means subtracting the average sample of each observation, and dividing by their standard deviation. This center and measure the data. Sometimes there are good reasons to change or do not perform this step, but we recommend you normalizes unless you have a good reason. It is easy to run this step as follows:

(5)

• The data matrix Ψ is multiplied by its transpose to obtain a covariance matrix L as shown in equation (5):

(6)

• In this step the values is computed using Matlab languages and the corresponding eigenvectors in the covariance matrix by the equation (6):

(7)

Where V is an orthogonal matrix of specific vectors and D is a diagonal matrix of eigenvalues.

We classify the eigenvectors according to decreasing values

The eigenvectors matrix V represents the projection eigenspace.

• In this step we project the images vectors centered in eigenspace. For this, we must compute the scalar product of these pictures vectors along with the eigenvector matrix by:

(8)

2.4. Equations Fisher Linear Discriminant Analysis (LDA)

The Linear Discriminant Analysis (LDA) of Fisher method proceeds according to the following steps:

2.4.1. Computing of within-class Scatter Matrix S_w

The within-class scatters matrix measure the amount of the dispersion between the images in the same class. For the i-th class, the dispersion matrix Si is calculated as the sum of the covariance matrices of the images centered in this category:

(9)

Where μ_j is the mean of images in the class and x_j is vector image. The matrix of the within-class dispersion S_w is the sum of all the dispersion matrices.

(10)

Where c is the class’s number.

2.4.2. Computing of between-class Scatter Matrix S_b

As with tables and equations, figures should be set in one column if possible unless two-column display is essential. The resolution of graphics and image should be adequate to reveal the important detail in the figure.

S_b between-class scatter matrix measures the amount of dispersion between classes. It computes the sum of the difference between the total average and the average of each class.

(11)

Where μ_i is the mean of images in class i and μ is the mean of all images.

2.4.3. Solve the Generalized Eigenvalue Problem

We calculate the eigenvalues and corresponding eigenvectors for the two dispersion matrices within-class and between-class by the following equation:

(12)

Where U_k is a matrix of eigenvectors and λ_k is a matrix of eigenvalues.

The eigenvectors (each vector has the size of 1x100) are ordered in descending order of their eigenvalues. Finally we keep only the first C-1 eigenvectors. These C-1 eigenvectors form the Fischer projection base.

2.5. Classification

Let us consider the 3D human face images. First, we compute the geodesic distances matrix [Ψ] = δ_ij as described in subsection (2.2). Then, we apply the reduce space algorithms (ACP or ALD) to geodesic distances matrix [Ψ], we obtain a low size matrix [A] = A_ij. In the end, we determine the input vectors ν_i of classification algorithms using the linearization of the matrix [A]. Figure 5 illustrates the steps of extracting the input vectors of the classifier algorithms used in our face recognition system.

Figure 5. Steps of extracting input vectors of the classifier algorithms

Download as

Veiw figure View Figure

To realize our 3D face recognition system, we use three types of classification algorithms: the Neural Networks (NN), k-Nearest Neighbor (KNN) and Support Vector Machines (SVM).

3. Simulation Results

In this section we make a series of simulation to evaluate the effectiveness of the proposed approach. These results were performed based on SHREC 2008 database. This database contain 427 scans of 61 subjects, for each of these 61 subjects 7 different scans namely: two “frontal”, one “look-up”, one “look-down”, one “smile”, one “laugh” and one “random expression” ^{[21, 22]}.

The following table summarizes the results obtained from simulation:

Table 1. Resultants of Recognition rate and Error rate of our automatic 3D face recognition system

Download as

View current table in a new window

Tables index

Veiw figure View Table

View next table

Table 1 summarizes the simulation results obtained by the presented approach. This results shows the recognition rate and the error rate found by methods used in our 3D face recognition system: (Geodesic Distance + PCA) and (Geodesic Distance + LDA) for characters extraction, with three algorithms used in classification such as: Neural Networks (NN), k-Nearest Neighbor (KNN) and Support Vector Machines (SVM).

The results obtained by our 3D face recognition system shows that our method present the best recognition rate (95,30%) using (Geodesic Distance + PCA) for images of SHREC 2008 database.

In conclusion of this series of results, a summary table (Table 2) compares the performance of our face authentication with respect to the performance obtained in other 3D face recognition systems.

Table 2. Comparison of Our Approach with Other Methods

Download as