# An Improved Surface Simplification Method for Facial Expression Animation Based on Homogeneous Coordinate Transformation Matrix and Maximum Shape Operator

Authors: Juin-Ling Tseng
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Facial animation is one of the most popular 3D animation topics researched in recent years. However, when using facial animation, a 3D facial animation model has to be stored. This 3D facial animation model requires many triangles to accurately describe and demonstrate facial expression animation because the face often presents a number of different expressions. Consequently, the costs associated with facial animation have increased rapidly. In an effort to reduce storage costs, researchers have sought to simplify 3D animation models using techniques such as Deformation Sensitive Decimation and Feature Edge Quadric. The studies conducted have examined the problems in the homogeneity of the local coordinate system between different expression models and in the retainment of simplified model characteristics. This paper proposes a method that applies Homogeneous Coordinate Transformation Matrix to solve the problem of homogeneity of the local coordinate system and Maximum Shape Operator to detect shape changes in facial animation so as to properly preserve the features of facial expressions. Further, root mean square error and perceived quality error are used to compare the errors generated by different simplification methods in experiments. Experimental results show that, compared with Deformation Sensitive Decimation and Feature Edge Quadric, our method can not only reduce the errors caused by simplification of facial animation, but also retain more facial features.


---

## Body

## 1. Introduction

Concomitant with the rapid advancements in information technology, the application of 3D animation has become increasingly popular in fields such as the movie industry [1, 2], gaming [3–5], arts [6, 7], and education [8, 9]. Among the various 3D animation technologies, facial animation is the most commonly used technique. However, because facial animation contains a variety of expressional contents, the surface relief of 3D models in facial animation undergoes considerable changes.Parke [10] was the first to propose the concept establishing facial animation. Subsequently, many related studies and techniques, including Head Pose Estimation [11], Facial 3D Shape Estimation [12], Head Shop [13], The Digital Emily Project [14], Automatic Generation [15], Kinect-Based Facial Animation [16], Real-Time Facial Animation [17–21], and 3D Facial Similarity Measure [22], emerged.However, in order to elaborate facial animation, numerous triangles are needed, which significantly increases storage costs. Thus, in order to reduce the number of triangles needed to describe the face animation, many experts and scholars have proposed simplified 3D animation methods, including Deformation Sensitive Decimation (DSD) [23, 24], Feature Edge Quadric (FEQ) [25], Facial Features Region Partition [26], and MPEG-4 Quadric-based LoD Simplification [27]. However, most of them are derived from QSlim [28], proposed by Garland and Heckbert, and DSD [23], proposed by Mohr and Gleicher.QSlim [28] is one of the most famous 3D model simplification methods [29]. This method can not only execute rapidly, but also reduce the errors caused by model simplification. Unfortunately, QSlim can only simplify 3D static models, whereas 3D animation typically contains various frame models. Consequently, in order to utilize QSlim for simplification of 3D animation, Mohr and Gleicher proposed the DSD method [23]. The method calculates and aggregates the error matrix of each vertex in different frame models to serve as a basis for simplification. However, DSD can cause destruction of the appearance characteristics of the model because it lacks complete homogeneous coordinate transformation.In order to preserve the facial expression features when simplifying face animation, Kim et al. [25] established 32 feature points and adopted FEQ to preserve facial animation features, as shown in Figure 1; Wang et al. [26] used Facial Features Region Partition to set a scope on the face, which is intended to preserve the desired facial features. Its simplification results are shown in Figure 2. However, in these methods, the feature regions must be set by the user before the shapes of the regions are preserved. In other words, these methods can only preserve general facial features, such as the eyes and nose. For nongeneral features, such as wrinkles, it is most likely that they are not in the set range and their triangles can easily be removed, resulting in damage to the features of the nonsetting regions.Figure 1
Simplification results using Feature Edge Quadric [25].Figure 2
Simplification results using Facial Features Region Partition [26].In order to overcome this limitation of feature regions having to be set by users and to preserve the facial features during the simplification process, this paper proposes a DSD-based method that uses Homogeneous Coordinate Transformation Matrix (HCTM) to solve DSD’s homogeneous coordinate transformation problems and uses Maximum Shape Operator (MSO) to estimate the changes in each vertex point in the various frame models. In this way, the intensity values of each facial characteristic are automatically quantified and the characteristics of facial animation are moderately preserved during the simplification process.


## 2. Related Works

### 2.1. Deformation Sensitive Decimation (DSD)

QSlim [28] is a Quadric Error Metrics- (QEMs-) based 3D model simplification method. This method first calculates the K
f matrix of the adjacent triangular piece of each vertex: f
:
a
x
+
b
y
+
c
z
+
d = 0. In this formula, a
2
+
b
2
+
c
2
=
1 and the matrix is based on the calculation of the distance of any point v from the f plane, f
T
v
2
=
v
T
f
f
T
v
=
v
T
K
f
v. The sum of distances of any point to its adjacent triangle is computed by adding all the K
f matrices of all adjacent triangular patches. This sum of distances, which can be obtained using formula (1), is the error matrix values resulting from the simplification of vertex pairs. In the QSlim process, the simplification is performed in an orderly manner from the vertex pair of the lowest error to the highest, as shown in Figure 3. Consequently, this method can efficiently generate a simplified low error model as follows:(1)
E
r
r
o
r
v
=
v
T
·
Q
·
v
.Figure 3
Surface simplification using Quadric Error Metrics [28].In this formula,(2)
Q
=
∑
f
∈
f
a
c
e
s
v
K
f
K
f
=
f
·
f
T
=
a
2
a
b
a
b
b
2
a
c
a
d
b
c
b
d
a
c
b
c
a
d
b
d
c
2
c
d
c
d
d
2
.QSlim is utilized to simplify 3D animation models by DSD [23]. This method mainly calculates the matrix Q
v
,
q of each vertex in different frame models of animation, as shown in formula (3), to estimate the errors each vertex pair (v
1
,
v
2) produces during the simplification process and then to decide which vertex pair should be simplified first, as shown in formula (4). This method inherits the speedy execution of QSlim but lacks complete homogeneous coordinate transformation [30]. Consequently, it cannot generate the best vertex point after the simplification of vertex pairs, as illustrated in Figures 4 and 5. Consider (3)
E
r
r
o
r
v
=
∑
q
=
1
k
v
T
·
Q
v
,
q
·
v
=
v
T
·
∑
q
=
1
k
Q
v
,
q
·
v
,
(4)
∑
q
=
1
k
v
~
q
T
·
Q
v
1
,
q
+
Q
v
2
,
q
·
v
~
q
,where k is the number of frame models in 3D animation; v
q refers to the new vertices, v
1 and v
2, generated in the qth frame model after simplification; and Q
v
1
,
q and Q
v
2
,
q are the respective error matrices of v
1 and v
2 in the overall 3D animation model.Figure 4
The shape of horse hoof is destroyed gradually when simplifying by the DSD [30].
(a)
Original model (16842 triangles)
(b)
Simplifying by the DSD (2000 triangles)Figure 5
DSD cannot generate the best vertex point after the simplification of vertex pairs. (a) Original model (57835 triangles); (b) simplifying by the DSD (5000 triangles).
(a)
(b)In addition, the DSD simplification method is not aimed at analyzing the surface of the 3D animation model. Consequently, it is relatively easy for the important features of the face to be damaged during the facial animation simplification process. To solve this problem, Kim et al. proposed Feature Edge Quadric method with the aim of defining the important feature regions of the face and further preserving the main facial animation features during the simplification process.


### 2.2. Feature Edge Quadric (FEQ)

FEQ was proposed by Kim et al. for preservation of facial features. In the proposed method, the feature points of 10 parts in the face, including tip of the nose, top of the head, left/right side of the face, top/bottom of the nose, left/right eye socket, bottom left/right of the nose, lip contact line, top/bottom of the lip, chin, and throat, are set as shown in Figure1. For error estimation, this method contains basic quadric error and Feature Edge Quadric. The former is based on QSlim and calculates the error matrix generated by each vertex pair (v
1
,
v
2) during the simplification process, as shown in the following formula: (5)
Q
p
=
∑
f
∈
n
g
h
b
v
1
a
r
e
a
f
·
Q
f
+
∑
f
∈
n
g
h
b
v
2
a
r
e
a
f
·
Q
f
,where n
g
h
b
(
v
1
) is the set of triangles adjacent to v
1, n
g
h
b
v
2 is the set of triangles adjacent to v
2, a
r
e
a
(
f
) is the area of triangle f, and Q
f is the error matrix of triangle f.In the latter, the error matrix of the adjacent feature edges of each feature point is calculated to properly preserve feature edges during the facial animation simplification process.To calculate the error matrix of feature edgee
i, FEQ first computes the planes m
e, which are orthogonal to the edge and can be calculated by e
i and the average normal vector of its two adjacent triangles, e
i
n, as shown in the following formula:(6)
m
e
=
e
i
×
e
i
n
,where e
i
n
=
(
n
1
f
+
n
2
f
)
/
2, where n
1
f and n
2
f are the normal vectors of two triangles adjacent to e
i.Through the integration of basic quadric error and Feature Edge Quadric, the formula of the error matrix can be deduced, as shown in(7)
Q
v
v
=
1
-
α
·
Q
p
+
α
·
Q
F
,where Q
F
=
∑
e
∈
f
e
(
v
)
(
m
e
)
·
(
m
e
)
T, where f
e
(
v
) is the set formed by the adjacent feature edge of vertex point v, and α is the weight value (0-1) customized by users (0.5 by default).Although the FEQ simplification method aims to preserve important features of the eyes, nose, mouth, and so forth, there are many more facial features than these organ features. The forehead, cheeks, and other areas also change significantly with changes in facial expressions. However, FEQ easily ignores the expression features and causes a rapid increase in the simplified errors during the process of simplification. Therefore, our paper proposes a novel simplification method that integrates MSO and HCTM and properly takes into account the overall facial features, thereby reducing errors generated during the simplification of facial animation.


## 2.1. Deformation Sensitive Decimation (DSD)

QSlim [28] is a Quadric Error Metrics- (QEMs-) based 3D model simplification method. This method first calculates the K
f matrix of the adjacent triangular piece of each vertex: f
:
a
x
+
b
y
+
c
z
+
d = 0. In this formula, a
2
+
b
2
+
c
2
=
1 and the matrix is based on the calculation of the distance of any point v from the f plane, f
T
v
2
=
v
T
f
f
T
v
=
v
T
K
f
v. The sum of distances of any point to its adjacent triangle is computed by adding all the K
f matrices of all adjacent triangular patches. This sum of distances, which can be obtained using formula (1), is the error matrix values resulting from the simplification of vertex pairs. In the QSlim process, the simplification is performed in an orderly manner from the vertex pair of the lowest error to the highest, as shown in Figure 3. Consequently, this method can efficiently generate a simplified low error model as follows:(1)
E
r
r
o
r
v
=
v
T
·
Q
·
v
.Figure 3
Surface simplification using Quadric Error Metrics [28].In this formula,(2)
Q
=
∑
f
∈
f
a
c
e
s
v
K
f
K
f
=
f
·
f
T
=
a
2
a
b
a
b
b
2
a
c
a
d
b
c
b
d
a
c
b
c
a
d
b
d
c
2
c
d
c
d
d
2
.QSlim is utilized to simplify 3D animation models by DSD [23]. This method mainly calculates the matrix Q
v
,
q of each vertex in different frame models of animation, as shown in formula (3), to estimate the errors each vertex pair (v
1
,
v
2) produces during the simplification process and then to decide which vertex pair should be simplified first, as shown in formula (4). This method inherits the speedy execution of QSlim but lacks complete homogeneous coordinate transformation [30]. Consequently, it cannot generate the best vertex point after the simplification of vertex pairs, as illustrated in Figures 4 and 5. Consider (3)
E
r
r
o
r
v
=
∑
q
=
1
k
v
T
·
Q
v
,
q
·
v
=
v
T
·
∑
q
=
1
k
Q
v
,
q
·
v
,
(4)
∑
q
=
1
k
v
~
q
T
·
Q
v
1
,
q
+
Q
v
2
,
q
·
v
~
q
,where k is the number of frame models in 3D animation; v
q refers to the new vertices, v
1 and v
2, generated in the qth frame model after simplification; and Q
v
1
,
q and Q
v
2
,
q are the respective error matrices of v
1 and v
2 in the overall 3D animation model.Figure 4
The shape of horse hoof is destroyed gradually when simplifying by the DSD [30].
(a)
Original model (16842 triangles)
(b)
Simplifying by the DSD (2000 triangles)Figure 5
DSD cannot generate the best vertex point after the simplification of vertex pairs. (a) Original model (57835 triangles); (b) simplifying by the DSD (5000 triangles).
(a)
(b)In addition, the DSD simplification method is not aimed at analyzing the surface of the 3D animation model. Consequently, it is relatively easy for the important features of the face to be damaged during the facial animation simplification process. To solve this problem, Kim et al. proposed Feature Edge Quadric method with the aim of defining the important feature regions of the face and further preserving the main facial animation features during the simplification process.


## 2.2. Feature Edge Quadric (FEQ)

FEQ was proposed by Kim et al. for preservation of facial features. In the proposed method, the feature points of 10 parts in the face, including tip of the nose, top of the head, left/right side of the face, top/bottom of the nose, left/right eye socket, bottom left/right of the nose, lip contact line, top/bottom of the lip, chin, and throat, are set as shown in Figure1. For error estimation, this method contains basic quadric error and Feature Edge Quadric. The former is based on QSlim and calculates the error matrix generated by each vertex pair (v
1
,
v
2) during the simplification process, as shown in the following formula: (5)
Q
p
=
∑
f
∈
n
g
h
b
v
1
a
r
e
a
f
·
Q
f
+
∑
f
∈
n
g
h
b
v
2
a
r
e
a
f
·
Q
f
,where n
g
h
b
(
v
1
) is the set of triangles adjacent to v
1, n
g
h
b
v
2 is the set of triangles adjacent to v
2, a
r
e
a
(
f
) is the area of triangle f, and Q
f is the error matrix of triangle f.In the latter, the error matrix of the adjacent feature edges of each feature point is calculated to properly preserve feature edges during the facial animation simplification process.To calculate the error matrix of feature edgee
i, FEQ first computes the planes m
e, which are orthogonal to the edge and can be calculated by e
i and the average normal vector of its two adjacent triangles, e
i
n, as shown in the following formula:(6)
m
e
=
e
i
×
e
i
n
,where e
i
n
=
(
n
1
f
+
n
2
f
)
/
2, where n
1
f and n
2
f are the normal vectors of two triangles adjacent to e
i.Through the integration of basic quadric error and Feature Edge Quadric, the formula of the error matrix can be deduced, as shown in(7)
Q
v
v
=
1
-
α
·
Q
p
+
α
·
Q
F
,where Q
F
=
∑
e
∈
f
e
(
v
)
(
m
e
)
·
(
m
e
)
T, where f
e
(
v
) is the set formed by the adjacent feature edge of vertex point v, and α is the weight value (0-1) customized by users (0.5 by default).Although the FEQ simplification method aims to preserve important features of the eyes, nose, mouth, and so forth, there are many more facial features than these organ features. The forehead, cheeks, and other areas also change significantly with changes in facial expressions. However, FEQ easily ignores the expression features and causes a rapid increase in the simplified errors during the process of simplification. Therefore, our paper proposes a novel simplification method that integrates MSO and HCTM and properly takes into account the overall facial features, thereby reducing errors generated during the simplification of facial animation.


## 3. Homogeneous Coordinate Transformation Matrix (HCTM)

Because 3D facial animation is composed of various different expression models, the tangent plane and normal vector of the same vertex point also vary with changes in expressions, as shown in Figure6. In other words, the local coordinate system for the same vertex point varies in different frame models. Therefore, if the coordinate transformation system is not accurate, errors can be easily caused by the simplification of the facial animation models. For this reason, the DSD cannot accurately calculate the optimal vertex position after the simplification of vertex pairs. This paper adopts Theorems 1 and 2 and proposes HCTM to solve this problem.Figure 6
The local coordinate system for the same vertex point varies in different expression models.Theorem 1.
The Homogeneous Coordinate Transformation MatrixT
(
d
) that corresponds to a translation by d
=
(
d
x
,
d
y
,
d
z
) is given by the following formula [31]:(8)
T
d
=
1
0
0
d
x
0
1
0
d
y
0
0
1
d
z
0
0
0
1
.Theorem 2.
The Homogeneous Coordinate Transformation MatrixR
(
a
,
θ
) that corresponds to a rotation of θ about the axis in the direction of the unit vector a
=
(
a
x
,
a
y
,
a
z
) is given by the following formula [31]:(9)
R
a
,
θ
=
a
x
2
+
c
θ
1
-
a
x
2
a
x
a
y
1
-
c
θ
-
a
z
s
θ
a
x
a
z
1
-
c
θ
+
a
y
s
θ
0
a
x
a
y
1
-
c
θ
+
a
z
s
θ
a
y
2
+
c
θ
1
-
a
y
2
a
y
a
z
1
-
c
θ
-
a
x
s
θ
0
a
x
a
z
1
-
c
θ
-
a
y
s
θ
a
y
a
z
1
-
c
θ
+
a
x
s
θ
a
z
2
+
c
θ
1
-
a
z
2
0
0
0
0
1
,where c
θ
=
cos
⁡
θ and s
θ
=
sin
⁡
θ.In this paper, HCTM sets the local coordinate space for each vertex point in the first expression model of the facial animation as the main coordinate space. Then, the vertex points in all other expression models are transformed into the corresponding local coordinate space in the first expression model.Suppose thatv
p
,
q is the vertex point of v
p in frame q; M
p
,
q is the Mesh formed by the adjacent vertex points of v
p
,
q; and t
p
,
q and n
p
,
q are the tangent plane and normal vector in v
p
,
q. HCTM must convert M
p
,
q from its original local coordinate system to the local coordinate system in the first expression model. This process contains two steps: translation of M
p
,
q to the coordinate system that takes v
p
,
1 as the origin and t
p
,
1 and n
p
,
1 as the tangent plane and normal vector and rotation of the tangent plane t
p
,
q and normal vector n
p
,
q to overlap with t
p
,
1 and n
p
,
1. The transformation matrix in step one can be defined by Theorem 1 as follows:(10)
T
Δ
v
=
1
0
0
Δ
v
x
0
1
0
Δ
v
y
0
0
1
Δ
v
z
0
0
0
1
.In this formula,(11)
Δ
v
=
v
p
,
1
-
v
p
,
q
=
Δ
v
x
Δ
v
y
Δ
v
z
1
T
.The transformation matrix in step two can be defined by Theorem 2 as in formula (12). In this formula, n
=
n
p
,
q
×
n
p
,
1
=
n
x
n
y
n
z
1
T and θ is the angle included between n
p
,
q and n
p
,
1. Consider(12)
R
n
,
θ
=
n
x
2
+
c
θ
1
-
n
x
2
n
x
n
y
1
-
c
θ
-
n
z
s
θ
n
x
n
z
1
-
c
θ
+
n
y
s
θ
0
n
x
n
y
1
-
c
θ
+
n
z
s
θ
n
y
2
+
c
θ
1
-
n
y
2
n
y
n
z
1
-
c
θ
-
n
x
s
θ
0
n
x
n
z
1
-
c
θ
-
n
y
s
θ
n
y
n
z
1
-
c
θ
+
n
x
s
θ
n
z
2
+
c
θ
1
-
n
z
2
0
0
0
0
1
.Integrating formulas (10) and (12), HCTM can be defined, as is shown in (13). Mesh M
p
,
q and the error matrix Q
v
p
,
q can be converted from one to the other with (13), as is shown in formulas (14) and (15) as follows:(13)
H
n
,
θ
,
Δ
v
=
R
n
,
θ
×
T
Δ
v
=
n
x
2
+
c
θ
1
-
n
x
2
n
x
n
y
1
-
c
θ
-
n
z
s
θ
n
x
n
z
1
-
c
θ
+
n
y
s
θ
0
n
x
n
y
1
-
c
θ
+
n
z
s
θ
n
y
2
+
c
θ
1
-
n
y
2
n
y
n
z
1
-
c
θ
-
n
x
s
θ
0
n
x
n
z
1
-
c
θ
-
n
y
s
θ
n
y
n
z
1
-
c
θ
+
n
x
s
θ
n
z
2
+
c
θ
1
-
n
z
2
0
0
0
0
1
×
1
0
0
Δ
v
x
0
1
0
Δ
v
y
0
0
1
Δ
v
z
0
0
0
1
=
n
x
2
+
c
θ
1
-
n
x
2
n
x
n
y
1
-
c
θ
-
n
z
s
θ
n
x
n
z
1
-
c
θ
+
n
y
s
θ
Δ
v
x
n
x
2
+
Δ
v
x
c
θ
1
-
n
x
2
+
Δ
v
y
n
x
n
y
1
-
c
θ
-
Δ
v
y
n
z
s
θ
+
Δ
v
z
n
x
n
z
1
-
c
θ
+
Δ
v
z
n
y
s
θ
n
x
n
y
1
-
c
θ
+
n
z
s
θ
n
y
2
+
c
θ
1
-
n
y
2
n
y
n
z
1
-
c
θ
-
n
x
s
θ
Δ
v
x
n
x
n
y
1
-
c
θ
+
Δ
v
x
n
z
s
θ
+
Δ
v
y
n
y
2
+
Δ
v
y
c
θ
1
-
n
y
2
+
Δ
v
z
n
y
n
z
1
-
c
θ
-
Δ
v
z
n
x
s
θ
n
x
n
z
1
-
c
θ
-
n
y
s
θ
n
y
n
z
1
-
c
θ
+
n
x
s
θ
n
z
2
+
c
θ
1
-
n
z
2
Δ
v
x
n
x
n
z
1
-
c
θ
-
Δ
v
x
n
y
s
θ
+
Δ
v
y
n
y
n
z
1
-
c
θ
+
Δ
v
y
n
x
s
θ
+
Δ
v
z
n
z
2
+
Δ
v
z
c
θ
1
-
n
z
2
0
0
0
1
,
(14)
M
p
,
q
′
=
H
n
,
θ
,
Δ
v
×
M
p
,
q
,
(15)
Q
v
p
,
q
′
=
H
n
,
θ
,
Δ
v
×
Q
v
p
,
q
.With HCTM, the same MeshM
p in different expression models can be converted to the local coordinate system in the first expression model, and its error calculation can be revised using formula (3) defined by DSD, as shown in formula (16). This method can solve the error value increase problem resulting from incomplete homogeneous coordinate transformation in DSD as follows:(16)
E
r
r
o
r
v
=
v
T
·
∑
q
=
1
k
H
n
,
θ
,
Δ
v
·
Q
v
,
q
·
v
.


## 4. Maximum Shape Operator (MSO)

To detect the shape features of the facial animation model, this paper presents a shape operator that estimates the changes in the 3D surface. In general, shape operator is mainly used to calculate the shape change of the specific tangent direction of the 3D object’s surface, as in Definition3. However, in this paper, the shape change of the 3D object’s surface, on which Mesh lies, is estimated by the edge of the Mesh.Definition 3.
LetM
⊂
R
3 be a regular surface, and let U be a surface normal to M defined in a neighborhood of a point v
~
∈
M. For a tangent vector t to M at v
~, we put(17)
S
t
=
-
D
t
U
.Then, S is called theshape operator [32, 33].Shape operator refers to the change degree of the normal vector field of surfaceM’s vertex point v
~ in its tangent direction t. To calculate the adjacent surface changes of the vertex points in the 3D model, in this paper, shape operator is extended to estimate and integrate the shape operator values of the vertex point v
~ and its adjacent vertex points. Suppose that the number of adjacent vertex points of vertex point v
~ is m, called v
~
1
,
v
~
2
,
v
~
3
,
…
,
v
~
m, and its tangent vector to each vertex point is, respectively, t
1
,
t
2
,
t
3
,
…, and t
m, as shown in Figure 7. Consequently, S
v
~
t
1
,
S
v
~
t
2
,
S
v
~
t
3
,
…
,
S
v
~
t
m, which signify the shape operator value of vertex v
~ in the t
1
,
t
2
,
t
3
,
…, and t
m directions can be generated according to the definition of shape operator, as shown in formula (18). After integrating the shape operator in each of these different tangent directions, the surface change of the region in which the vertex lies is shown in formula (19) as follows:(18)
S
v
~
t
i
=
U
v
~
i
-
U
v
~
v
~
i
-
v
~
,
(19)
S
v
~
=
∑
i
=
1
m
v
~
i
-
v
~
×
S
v
~
t
i
∑
i
=
1
m
v
~
i
-
v
~
=
∑
i
=
1
m
U
v
~
i
-
U
v
~
∑
i
=
1
m
v
~
i
-
v
~
.Figure 7
Shape operators of pointp using the tangent vectors to each neighboring point to estimate local surface variation.Shape operator can automatically analyze the surface changes of the facial expression model and extract the important features, such as eyes, nose, and mouth, as shown in Figure8. This method covers the drawback in FEQ of each feature region having to be defined by the user. However, facial animation is not static. As time passes, the face may produce various facial features, including nasolabial folds and forehead wrinkles. Therefore, in order to preserve facial expression features during simplification of the facial animation, this paper uses MSO to extract the facial animation feature. This method calculates the shape operator value of each vertex point v in k (the number of expression models) expression models and takes the maximum value as the eigenvalue for appearance analysis of facial animation. The MSO is defined as follows:(20)
S
v
=
max
1
≤
i
≤
k
⁡
S
v
,
i
,where S
v
,
i is the shape operator value of vertex v in frame i. Figure 9 shows the results of the surface changes of the face animation extracted by MSO. It can be seen from the result that nasolabial folds are obvious in expressions of surprise, grin, laugh, and smile, but not obvious in expressions of fury, anger, rage, and sadness. However, if the features of those expressions are ignored during the face animation simplification process, a rapid increase in simplification errors can easily occur. With MSO, the proposed method can extract the features of nasolabial folds to reduce the errors caused by the simplification of the facial animation.Figure 8
Shape operator can automatically analyze the surface changes of the facial expression model. (Red indicates the high-variation surfaces. Yellow indicates medium-variation regions. Green represents low-variation areas.)
(a)
(b)
(c)
(d)Figure 9
This method calculates the shape operator value of each vertex point in every expression model and takes the maximum value as the eigenvalue for appearance analysis of facial animation.


## 5. The Proposed Algorithm

The algorithm proposed in this paper is mainly based on DSD, with the introduction of MSO and HCTM to reduce the errors caused by the simplification of the face animation model. The main steps in this algorithm are as follows.(1)
Calculate the QEMQ
v
p
,
q of vertex v
p in each facial expression model:(21)
Q
v
p
,
q
=
∑
f
∈
f
a
c
e
s
v
p
,
q
K
f
,
wheref
a
c
e
s
(
v
p
,
q
) is the set of triangles adjacent to v
p
,
q in facial expression model q and K
f is the matrix formed in plane f, as is shown in formula (1).
(2)
Calculate HCTMH
n
,
θ
,
Δ
v and update QEM Q
v
p
,
q to obtain the following:(22)
Q
v
p
,
q
′
=
H
n
,
θ
,
Δ
v
×
Q
v
p
,
q
.
(3)
Estimate the MSOS
v
p of each vertex point v
p:(23)
S
v
p
=
max
1
≤
q
≤
k
⁡
S
v
p
,
q
,
S
v
p
,
q
=
∑
i
=
1
m
U
v
~
i
-
U
v
p
,
q
∑
i
=
1
m
v
~
i
-
v
p
,
q
,
wherem is the number of vertex points adjacent to v
p
,
q in facial expression model q, v
~
i is the vertex point adjacent to v
p
,
q in facial expression model q, and S
v
p
,
q is the shape operator of v
p
,
q.
(4)
Sum all QEMs ofv
p and import MSO into the QEM:(24)
Q
v
p
′
′
=
∑
q
=
1
k
Q
v
p
,
q
′
+
S
v
p
′
×
∑
q
=
1
k
Q
v
p
,
q
′
=
1
+
S
v
p
′
×
∑
q
=
1
k
H
n
,
θ
,
Δ
v
×
Q
v
p
,
q
,
S
v
p
′
=
0
,
S
v
p
≤
0
,
S
v
p
μ
+
3
σ
,
0
<
S
v
p
<
μ
+
3
σ
,
1
,
S
v
p
≥
μ
+
3
σ
,
whereS
v
p is the MSO value of v
p, μ is the mean value of MSO, and σ is the standard deviation of MSO. The original MSO value is between zero and 1,241.77, which is scattered and has some outliers. In order to balance the effect of QEM Q
v
p
,
q
′ and MSO, in this paper, the MSO is standardized to [
0,1
], and the outliers that are higher than S
v
p
/
μ
+
3
σ are set to the maximum value of one.
(5)
Calculate the minimum simplification error of each vertex pair with the following conditions:
(a)
v
a
,
v
b is an edge; or
(b)
v
a
,
v
b is not an edge, but its distance v
a
-
v
b is smaller than the threshold value set by users.
(6)
Choose the vertex pair with the smallest error in step (5) for simplification.
(7)
Simplify the vertex pairv
a
,
v
b into a vertex point v, and update the QEM Q
v
′
′ of v, where Q
v
′
′
=
Q
v
a
′
′
+
Q
v
b
′
′.
(8)
Update all the information adjacent to the vertex pointsv
a or v
b.
(9)
Repeat steps (5) to (8) until the number of triangles has been reduced to the designated value.


## 6. Experimental Results

This study used an Intel Core 2.2 GHz CPU with 1 GB RAM as the main execution environment. The eight experimental facial animation models included fury, surprise, anger, grin, laugh, rage, sadness, and smile. This experiment compared the differences between this method and DSD and FEQ and used root mean square (RMS) error and perceived quality to analyze the distortion errors caused by these methods so as to verify the superiority of this method over DSD and FEQ.The eight original expression models adopted in this experiment are shown in Figure10. Each model had 29,299 vertex points and 57,836 triangles. When the number of triangles in the facial animation model is reduced to 5,000, 2,000, 1,000, and 500 through DSD, the generated RMS error values are shown in Table 1.Table 1
RMS error comparison between our method and DSD (unit: 10−2).
Triangles
The DSD
Our method
Improvement rate
Face 01 (fury)
5000
5.7313
0.8427
85.30%
2000
11.3899
1.6240
85.74%
1000
22.9495
2.6013
88.67%
500
42.7859
4.7140
88.98%
Face 02 (surprise)
5000
4.8805
1.4011
71.29%
2000
9.6882
2.7791
71.31%
1000
21.3109
4.2362
80.12%
500
37.8799
6.6230
82.52%
Face 03 (anger)
5000
4.6126
1.1371
75.35%
2000
9.1516
2.3843
73.95%
1000
19.3625
3.9031
79.84%
500
35.8760
6.6498
81.46%
Face 04 (grin)
5000
5.2081
1.3187
74.68%
2000
10.2029
2.4012
76.47%
1000
21.2078
3.8791
81.71%
500
39.2217
6.6697
82.99%
Face 05 (laugh)
5000
4.8700
1.2308
74.73%
2000
10.1936
2.4448
76.02%
1000
21.3471
3.8759
81.84%
500
39.3825
6.5277
83.42%
Face 06 (rage)
5000
5.3178
1.1113
79.10%
2000
10.2902
2.3494
77.17%
1000
21.0917
3.6617
82.64%
500
37.7458
5.6601
85.00%
Face 07 (sad)
5000
4.6088
1.4588
68.35%
2000
9.9824
2.9477
70.47%
1000
21.0213
4.4211
78.97%
500
38.0176
7.1686
81.14%
Face 08 (smile)
5000
4.6887
1.1734
74.97%
2000
9.8362
2.4347
75.25%
1000
21.4011
3.7970
82.26%
500
39.8993
5.9372
85.12%Figure 10
The original expression models.With changes in the expression model, the error caused by DSD and this method will be different. Take face 01 (fury) as an example: when the number of triangles in the facial animation model is reduced to 5,000, 2,000, 1,000, and 500 through DSD, the generated RMS error values are 5.7313 × 10−2, 11.3899 × 10−2, 22.9495 × 10−2, and 42.7859 × 10−2, respectively. However, the error can be reduced to 0.8427 × 10−2, 1.6240 × 10−2, 2.6013 × 10−2, and 4.7140 × 10−2 using this method, resulting in an improvement rate of between 85.30% and 88.98%. For other expression models, this method is better than the DSD method, with an improvement rate of more than 68.35%. In addition, with the reduction in the number of triangles, the improvement rate is increasingly better. Take face 01 (fury) as an example: when the number of triangles is reduced to 5,000, the improvement rate of this method is 85.30% compared with the DSD; and when the number is 500, the improvement rate is 88.98%. In other words, this method is better than DSD in low triangle numbers and can retain more facial shapes than DSD.The average errors generated by all the facial expressions in the facial animation are shown in Table2 and Figure 11. The table shows the errors generated from simplifying the entire 3D facial animation using DSD and this method, respectively. In Table 2, it can be seen that when the number of triangles is simplified to 5,000, 2,000, 1,000, and 500, the errors generated by DSD are 4.9897 × 10−2, 10.0919 × 10−2, 21.2115 × 10−2, and 38.8511 × 10−2, whereas those of this method are 1.2092 × 10−2, 2.4207 × 10−2, 3.7969 × 10−2, and 6.2438 × 10−2, which are improved by 75.77% to 83.93% compared with DSD.Table 2
Average RMS error comparison between our method and DSD (unit: 10−2).
Triangles
The DSD
Our method
Improvement rate
5000
4.9897
1.2092
75.77%
2000
10.0919
2.4207
76.01%
1000
21.2115
3.7969
82.10%
500
38.8511
6.2438
83.93%Figure 11
RMS error comparison between our method and DSD.In addition to the use of QEM for simplification like DSD, FEQ also estimates the simplification errors of important facial features such as the eyes, nose, mouth, and ears. Therefore, FEQ is also better than DSD in terms of simplification results. However, the features of facial animation include not only the eyes, nose, mouth, and ears, but also wrinkles on an angry forehead, protuberant cheeks, and obvious nasolabial folds on a smiling face.The data in Table3 and Figure 12 indicate that when the number of triangles is simplified to 5,000, 2,000, 1,000, and 500, the errors generated by FEQ are 1.2658 × 10−2, 2.7134 × 10−2, 5.2143 × 10−2, and 10.6767 × 10−2, which are better than DSD’s but are only limited to general facial features such as eyes, nose, mouth, and ears, having no obvious improvement in other expression features like wrinkles in forehead and nasolabial folds in cheeks.Table 3
Average RMS error comparison among our method, FEQ, and DSD (unit: 10−2).
Triangles
The DSD
The FEQ
Our method
5000
4.9897
1.2658
1.2092
2000
10.0919
2.7134
2.4207
1000
21.2115
5.2143
3.7969
500
38.8511
10.6767
6.2438Figure 12
Average RMS error comparison among our method, FEQ, and DSD.The error comparison results in Table4 indicate that when the number of triangles is simplified to 5,000, 2,000, 1,000, and 500, the respective errors generated by this method are 1.2092 × 10−2, 2.4207 × 10−2, 3.7969 × 10−2, and 6.2438 × 10−2, which are all better than EFQ’s. The improvement rate reaches 4.47% when the number of triangles is simplified to 5,000, and it even reaches 41.52% when the number is 500.Table 4
Average RMS error comparison between our method and FEQ (unit: 10−2).
Triangles
The FEQ
Our method
Improvement rate
5000
1.2658
1.2092
4.47%
2000
2.7134
2.4207
10.79%
1000
5.2143
3.7969
27.18%
500
10.6767
6.2438
41.52%In the preservation of expression features, as shown in Figure13, when the model is simplified to 5,000 triangular pieces, as shown in Figure 13(b), the FEQ method retains 129 triangles in the forehead wrinkled area; however, this method has 123 fully covered and 37 half-covered triangles in the same area. If we use 0.5 as a unit for each half-covered triangle, then our method obtains 141.5 triangles in the forehead wrinkled area. In other words, for this feature area, this method retains 10% more triangular pieces than the FEQ. Moreover, when the model is reduced to 1,000 triangles, as shown in Figure 13(c), the FEQ only has 15.5 triangles in the forehead wrinkled area (including 11 fully covered and 9 half-covered triangles), but this method has 28.5 triangles (20 fully covered and 17 half-covered triangles); 84% more triangles are retained compared with the FEQ.Figure 13
Comparison between FEQ and our method when the number of triangles in the face 03 (anger) model is simplified to 5,000 and 1,000.
(a)
Original model
(b)
The simplification results of forehead wrinkles using FEQ (left) and our method (right) when the model is simplified to 5,000
(c)
The simplification results of forehead wrinkles using FEQ (left) and our method (right) when the model is simplified to 1,000In addition, in the cheeks and the nasolabial fold areas, as shown in Figure14, when the number of triangles in the model is reduced to 1,000 using the FEQ, these areas retain 61 triangles. However, by using the proposed method to simplify the model, 113.5 triangles are retained (including 97 fully covered and 33 half-covered triangles), which is approximately 86% more triangles as compared to the FEQ.Figure 14
Comparison between FEQ and our method when the number of triangles in the face 04 (grin) model is simplified to 1,000.
(a)
FEQ
(b)
Our methodFrom the simplified results of forehead wrinkles, cheeks, and nasolabial fold areas, it can be seen that this method retains a greater number of triangles than the FEQ. It also shows that, after simplification, this method gets closer to expressing the original facial model in these feature areas than the FEQ method.To verify the effectiveness of our method, we also adopted perceived quality to further compare it with DSD and FEQ. Perceived quality is mainly used to compare visual differences. We used tensor-based perceptual distance measure (TPDM) [34], proposed by Torkhani et al., to evaluate the perceived quality values of the model before and after simplification. The perceived quality value is between zero and one. A value closer to one signifies that the appearance of the simplified model is very similar to the original, whereas a value closer to zero signifies that the appearance of the simplified model is very different from the original.In Table5, it can be seen that the perceived value generated by our method is 1.7413 × 10−1 to 3.0275 × 10−1, results that are clearly superior to DSD’s 2.4633 × 10−1 to 4.6055 × 10−1, with its improvement rate of 29.31% to 37.30%. In Table 6, it can be seen that the perceived value generated by FEQ is 1.7413 × 10−1 to 3.0275 × 10−1. Thus, this method generates a lower perceived value than FEQ and can achieve an improvement rate of 2.33% to 12.88%, as shown in Figure 15.Table 5
Perceived quality comparison between our method and DSD (unit: 10−1).
Triangles
DSD
Our method
Improvement rate
5000
2.4633
1.7413
29.31%
2000
3.2981
2.2074
33.07%
1000
4.0961
2.5682
37.30%
500
4.6055
3.0275
34.26%Table 6
Perceived quality comparison between our method and FEQ (unit: 10−1).
Triangles
FEQ
Our method
Improvement rate
5000
1.7828
1.7413
2.33%
2000
2.3440
2.2074
5.83%
1000
2.8950
2.5682
11.29%
500
3.4751
3.0275
12.88%Figure 15
Perceived quality comparison among our method, FEQ, and DSD.In addition, in terms of time cost, given that this improved method is based on DSD, it inherits benefits such as lower computation time. In order to perform the time cost analysis, this paper divided the entire implementation process into four phases, namely, the setup time, initialization time, simplification running time, and output time.In the setup time phase, the main work is to input the original facial models, including vertex coordinates and triangle information. In the initialization time phase, this method calculates relevant information needed to simplify the model, including QEM, HCTM, and MSO. In the simplification running time phase, the method mainly records the execution time needed to simplify the model until it reaches a specific required number of triangles.In the final output time phase, it records the time needed to output the simplified facial model. The average time required for each execution process is shown in Table7. As is evident from the table, the execution speed of this method is significantly fast. The overall simplification time is only about 8 seconds, in which the initialization time for HCTM and MSO is just over 2-3 seconds, accounting for about 37% of the total simplification time. Undoubtedly, this method is very efficient in model simplification.Table 7
Time analysis for each execution process in facial model simplification (unit: second).
Triangles
Setup time
Initialization time
Running time
Output time
Total time
5000
2.95
2.92
1.95
0.22
8.04
2000
2.78
3.05
2.09
0.17
8.09
1000
2.53
2.97
2.13
0.11
7.74
500
2.78
2.88
2.19
0.09
7.94
Average
2.76
2.96
2.09
0.15
7.95


## 7. Conclusions

In order to analyze the shape changes of facial animation and to reduce simplification errors, this paper proposed HCTM to modify the homogeneity of the local coordinate system for different models and adopted MSO to automatically analyze the degree of facial animation shape change, to locate the region with most expression changes and to rectify the drawback wherein feature regions such as the eyes, nose, mouth, and ears had to be defined by users. In experiments conducted, RMS and perceived quality errors were utilized to compare the simplification results of the proposed method with those of DSD and FEQ. The experimental results show that the errors caused by this method are lower than those of DSD and FEQ. Furthermore, this method can not only properly retain the facial features of fixed positions such as the eyes, nose, mouth, and ears, but also preserve more triangles than other methods in other important feature regions such as wrinkles on the forehead, cheeks, and nasolabial folds. Thus, it satisfies the requirement that the simplified facial animation should be as elaborate and natural as possible.



---

*Source: 2370919-2016-02-08.xml*