# SADRNet: Self-Aligned Dual Face Regression Networks for Robust 3D Dense Face
Alignment and Reconstruction

Zeyu Ruan, Changqing Zou, , Longhai Wu, Gangshan Wu, , Limin Wang Z. Ruan, G.
Wu, L. Wang are with the State Key Laboratory for Novel Software Technology,
Nanjing University, Nanjing, 210023, China (e-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>lmwang@nju.edu.cn).C. Zou is with
the School of Data and Computer Science, Sun Yat-sen University, Guangzhou,
510006, China (e-mail: aaronzou1125@gmail.com).L. Wu is with the Samsung
Electronics (China) R&D Centre, Nanjing, 210012, China (e-mail:
longhai.wu@samsung.com).

###### Abstract

Three-dimensional face dense alignment and reconstruction in the wild is a
challenging problem as partial facial information is commonly missing in
occluded and large pose face images. Large head pose variations also increase
the solution space and make the modeling more difficult. Our key idea is to
model occlusion and pose to decompose this challenging task into several
relatively more manageable subtasks. To this end, we propose an end-to-end
framework, termed as Self-aligned Dual face Regression Network (SADRNet),
which predicts a pose-dependent face, a pose-independent face. They are
combined by an occlusion-aware self-alignment to generate the final 3D face.
Extensive experiments on two popular benchmarks, AFLW2000-3D and Florence,
demonstrate that the proposed method achieves significant superior performance
over existing state-of-the-art methods.

###### Index Terms:

Three-dimensional deep face reconstruction, Dense face alignment, occlusion-
aware attention.

Figure 1:  Illustration of the challenges of large poses (the 1st row) and
occlusions (the 2nd row). The results of both face alignment and
reconstruction are demonstrated. Only 68 landmarks are plotted for better
view.

##  I Introduction

Monocular 3D face reconstruction recovers 3D facial geometry from a single-
view image. Dense face alignment (e.g., [1, 2]) locates all facial vertices of
a face model. They are closely related to each other, and both play important
roles in broad applications such as face recognition [3, 4], normalization
[5], tracking [6], swapping [7], and expression recognition [8] in computer
vision and graphics.

The existing methods that simultaneously address 3D dense face alignment and
face reconstruction (3D-DFAFR, for short) can be roughly grouped into two
categories: model-based category and model-free category. Model-based methods
infer the parameters of a parametric model [9, 10], such as a 3D morphable
model (3DMM [11]), by solving a nonlinear optimization problem or directly
regressing with convolutional neural networks (CNNs) [12, 13, 1, 14, 15, 16].
Recent work [17, 18, 19, 20, 18] achieves high-fidelity face shape and dense
face alignment by using nonlinear 3DMM decoders to improve its representation
power. Rather than using a parametric model, model-free methods obtain
unrestricted 3D face structure and alignment information by directly inferring
the 3D position of face vertices represented in specific forms (e.g., UV map
[2], volume [21]).

Although significant improvements have been achieved on the problem of
3D-DFAFR in a controlled setting during the past few years, 3D-DFAFR under
unconstrained conditions is still yet to be well addressed. Specifically,
under unconstrained conditions, as shown in Fig. 1, self occlusions caused by
large pose orientation and inter-object occlusion of hair and glasses could
significantly reduce the useful information in an image, making it challenging
to generate good results. Meanwhile, large pose diversity will make it hard to
distinguish the shape variations and increase the modeling difficulty.
Previous works mainly tackle these problems by increasing the data size and
diversity of training data [1, 2, 18, 22] or performing strong regularization
on the shape [23].

To addresses the challenges of 3D-DFAFR in the wild, this paper proposes an
effective solution based on the following three motivations: (1) an occluded
region in the image does not contain any face information but may negatively
affect the network prediction. (2) the occluded part of a face can only be
inferred through the global facial structure or prior knowledge. (3)
disentangling the face pose and face shape will significantly reduce the
complexity of the problem of 3D-DFAFR and thus make it more tractable. Based
on the above motivations, we believe occlusion and pose are two critical
factors in achieving a robust 3D-DFAFR. Unfortunately, there are few 3D-DFAFR
works explicitly handle with the face occlusions. The face pose estimation is
also rarely discussed deeply in existing 3D-DFAFR works. Therefore, in this
work, we propose to explicitly model these two factors to build a robust
method for 3D-DFAFR.

We propose a self-aligned dual face regression network (SADRNet) for robust 3D
dense face alignment and face reconstruction based on the above analysis. In
particular, we present a dual face regression framework to decouple face pose
estimation and face shape prediction in a low computational cost manner. These
two regression networks share the same encoder-decoder backbone. They are
equipped with its task-specific head design for predicting pose-dependent face
and pose-independent face, respectively. The pose-independent shape regression
could relieve the difficulty of directly predicting the original complex face
shape under various poses and thus improve the shape prediction accuracy.
Besides, to tackle the occlusion issue, we devise a supervised attention
mechanism to enhance the discriminative features in visible areas while
suppressing the occluded region’s influence. The attention mechanism could be
plugged into our dual face regression framework to improve prediction
accuracy. Finally, we propose an occlusion-aware self-alignment module to
combine the pose-dependent and pose-independent faces to yield the final face
reconstruction. In this alignment module, we only use the visible and sparse
face landmarks to estimate the pose parameters, which could further improve
the robustness of our SADRNet. Our solution significantly improves the
robustness toward face occlusions in the wild. It achieves a considerable
margin on both face reconstruction and dense face alignment. In summary, the
main contributions of this paper are:

  * •

We propose a self-aligned dual faces regression framework, which is robust to
face pose variation and occlusion, for the problem of 3D-DFAFR.

  * •

We propose an attention-aware mechanism for visible face region regression,
which can improve the regression accuracy and robustness under various
situations of face occlusion.

  * •

The proposed end-to-end architecture is efficient and it can run at $224\times
224/70$ FPS on a single GTX 1080 Ti GPU.

  * •

The proposed method achieves a considerable margin on the challenging
AFLW2000-3D [1] dataset and Florence 3D Faces [24] over the state-of-the-art
methods.

##  II Related Work

###  II-A 3D Face Reconstruction

Blanz and Vetter [11] proposed 3DMM to represent a face model by a linear
combination of orthogonal bases obtained by PCA. In this way, 3D face
reconstruction can be formulated as 3DMM parameters regression problems.
Later, Paysan et al. [25] extended the model by adding more scans and
decomposing the expression bases from shape bases. A lot of earlier methods
regressed the 3DMM parameters by solving a nonlinear optimization function
[26, 5, 25, 27, 28]. Thanks to the development of deep learning, some methods
[29, 1, 30, 31, 12, 16, 32, 33] started to use deep convolutional neural
network (DCNN) architectures to learn 3DMM parameters and largely replaced
traditional optimization-based methods with more accurate results and shorter
running time. The self-supervised training of DCNN-based methods was
implemented by exploiting a differentiable renderer [34, 35, 36, 37, 38, 39,
40], which alleviated the lack of 3D-supervised data and improved the
generalization of networks. However, these model-based methods’ reconstruction
geometry is constrained by the linear bases with limited representation power.

Some works proposed to break the limitation by using nonlinear models [41, 42,
17, 20, 43, 41, 44]. In [19], a DCNN was used as a nonlinear 3DMM decoder.
Ranjan et al. [45] used spectral graph convolutions to learn 3D faces. Zhou et
al. [18] presented a nonlinear 3DMM using colored mesh decoding. Guo et al.
[46] learn a more powerful nonlinear 3DMM from different data sources: scanned
3D face, RGB-D images, and RGB images.

Some other works directly obtained the full 3D geometry to avoid the
restriction of parametric models and difficulty in pose estimation [47, 2,
45]. Jackson et al. [21] proposed to use a volumetric representation of 3D
face shape instead of the previously used point cloud or mesh and directly
regressed the voxels. Feng et al. [2] mapped the mesh of a face geometry into
UV position maps and then trained a light-weighted network that obtains the 3D
facial geometry along with its correspondence information.

Some works also combine the 3DMM-based regression and direct 3D geometry
regression to improve the reconstruction performance. Chen et al. [48] used a
3DMM-based coarse model and a displacement map in UV space to represent a 3D
face, and utilize the input image as supervision to effectively learn the
facial details. Huber et al. [12] proposed to estimate an intermediate
volumetric geometry and finetune it with 3DMM parameters’ regression.

###  II-B Face Alignment

In the beginning, face alignment works aimed to locate a set of 2D facial
landmarks in the image plane. Traditional works were mainly based on Active
Appearance Models (AMM) and Active Shape Models (ASM) [49, 50, 51, 52, 53] and
considered face alignment as a model parameter optimization problem. Then
cascaded regression methods [54, 55] became popular. They iteratively refined
the predictions and reached higher accuracy. With the development of deep
learning, CNNs were wildly used to regress the landmarks’ positions directly
or predict heat maps and largely improved the performance [56, 57, 58, 59].
Since the 2D face alignment methods have limitations on detecting invisible
landmarks, the 3D face alignment problem has been widely researched in recent
years. There are two major strategies for 3D face alignment: (1) separately
detecting 2D landmarks and their depth [60, 61, Bulat2016TwoStageCP], and (2)
fitting a certain 3D face model [63, 64] to obtain the full 3D structure to
guide the 3D landmark localization.

Since the methods mentioned above can handle only a limited quantity of
landmarks, which is far from enough in some applications, 3D dense face
alignment [65] started to be researched. It requires methods to offer pixel-
wise facial region correspondence between two face images. As the prediction
target changes from a sparse set of facial landmarks to a dense set of tens of
thousands of points, it is natural to solve this problem by fitting a
registered 3D face model.

Figure 2: The framework of our proposed self-aligned dual face regression
network (SADRNet). $\mathbf{A}$ is the attention mask. $\mathbf{P}$ is the
pose-dependent face. $\mathbf{D}$ is the face shape deformation (visualized in
UV space). $\mathbf{\bar{S}}$ is the mean face template. $\mathbf{S}$ is the
pose-independent face. $\mathbf{G}$ is the output face model.

###  II-C 3D Dense Face Alignment and Face Reconstruction

Most model-based reconstruction approaches can be applied to dense face
alignment if the face model is well registered and provides a dense
correspondence [65, 17, 12]. Explicit facial pose estimation is needed in
these works. Zhu et al. proposed 3DDFA [1], which is a representative work in
this task. They used a cascaded CNN framework to regress the 3DMM parameters,
including the pose parameters. The rotation angles are represented by a 4D
unit quaternion for less difficulty in learning. However, their output faces
are sensitive to the fluctuation of every parameter and hard to reach high
precision. In [12], an ICP post-processing is incorporated to refine the
regressed pose parameters, but it takes enormous extra computation. Zhou et
al. learned a nonlinear 3DMM by directly using graph convolutions on face
meshes and reached an extremely fast decoding speed. Nevertheless, the face
pose is still obtained by direct regression like 3DDFA.

Some model-free methods that directly predict 3D coordinates of facial points
are also applicable to the task of dense face alignment with their face
representation registered with fixed semantic meaning [2, 21]. However, it is
difficult for these model-free methods to handle severe occlusions and large
poses since no prior knowledge or constraint is provided.

Our method’s final output face geometry is represented by a UV position map,
which possesses a dense correspondence between the face shape and the input
image. Unlike the methods mentioned above, we explicitly deal with object
occlusions by leveraging an attention mechanism on network features. We
predict a pose-independent face model to avoid the large variance in face
shape brought by large poses. Instead of directly regressing the pose
parameters, we perform a visibility-aware self-alignment between a pose-
dependent face model and a pose-independent face model to estimate the pose of
a nonlinear 3DMM. The alignment process is stable as the error caused by a
single outlier is apportioned by all of the landmarks. In contrast, the error
of every pose parameter is accumulated in parameter-regressing methods.
Besides, the alignment process is based on two regressed faces with similar
shapes, rather than the matching of landmarks and a fixed face template.
Therefore, the change of face shape is taken into account in pose estimation.
In this way, our method is more robust and accurate than previous works.

##  III Method

In this section, we detail the SADRNet. We first introduce the dual face
representation used in this work and the network architecture overview. We
then present the occlusion-aware attention mechanism and the face fusion
module. After that, we introduce the loss functions and implementation
details.

###  III-A Dual Face Regression Framework

Facial geometry representation. We assume the projection from the 3D face
geometry to the 2D image is a weak perspective projection:

$\mathbf{V}=\mathbf{Pr}*\mathbf{G}$ (1)

where $\mathbf{V}$ is the projected geometry on the 2D plane,
$\mathbf{Pr}=\begin{bmatrix}~{}1&~{}0&~{}0\\\ ~{}0&~{}1&~{}0\end{bmatrix}$ is
the projection matrix, $\mathbf{G}\in\mathbb{R}^{3\times n}$ is the 3D mesh of
a specific face with $n$ vertices.

We separate the 3D face geometry into pose, mean shape, and deformation as:

$\mathbf{G}=f*\mathbf{R}*\mathbf{S}+\mathbf{t},$ (2)
$\mathbf{S}=(\mathbf{\bar{S}}+\mathbf{D}),$ (3)

$\mathbf{S}\in\mathbb{R}^{3\times n}$ represents the pose-independent (i.e.,
pose-normalized) face shape, $\mathbf{\bar{S}}\in\mathbb{R}^{3\times n}$ is
the mean shape template provided by [25] and $\mathbf{D}\in\mathbb{R}^{3\times
n}$ is the deformation between $\mathbf{S}$ and $\mathbf{\bar{S}}$. The pose
parameters consist of the scale factor $f$, the 3D rotation matrix
$\mathbf{R}\in\mathbb{R}^{3\times 3}$ and the 3D translation
$\mathbf{t}\in\mathbb{R}^{3}$.

Dual face regression and analysis. We propose to jointly regress two face
models: a pose-independent face (the face shape) $\mathbf{S}$ and a pose-
dependent face $\mathbf{P}$. And then, we use a self-alignment post-process
$\phi$ to estimate face pose from $\mathbf{P}$, $\mathbf{S}$ and facial
vertices’ visibility information $\mathbf{Vis}$:

$\phi(\mathbf{P},\mathbf{S},\mathbf{Vis})=f,\mathbf{R},\mathbf{t}.$ (4)

The visibility information $\mathbf{Vis}$ is explained in Sec.III-B. Based on
the estimated face pose $\phi(\mathbf{P},\mathbf{S},\mathbf{Vis})$ and pose-
independent face $\mathbf{S}$, we could reconstruct our final face shape $G$
via transformation defined in Eq.2.

In fact, $\mathbf{G}$ and $\mathbf{P}$ have the same physical meaning, which
means the ground truth of them are the same:

$\hat{\mathbf{P}}=\hat{\mathbf{G}}.$ (5)

The difference is that $\mathbf{P}$ is obtained by direct network regression,
while $\mathbf{G}$ is obtained by applying Eq.2. To distinguish them, we term
$\mathbf{P}$ as pose-dependent face and $\mathbf{G}$ as face geometry. The
learning of pose-dependent face is easy to over-fit to pose and under-fit to
shape as the orientation variations bring much greater point-to-point
distances than the shape variations, resulting in some implausible face shape
under large pose cases. By contrast, the pose-independent face $\mathbf{S}$
does not change with the pose. Thus the network would focus on the shape
characteristics and learn more details. $\mathbf{S}$ is disentangled into the
mean face shape template $\mathbf{\bar{S}}$ and the deformation $\mathbf{D}$
between the actual shape and the mean shape. Only the zero-centered
$\mathbf{D}$ needs to be predicted. It further reduces the fitting difficulty.
The mean face shape also serves as prior knowledge to keep the invisible
facial parts plausible. By combining the shape of $\mathbf{S}$ with the pose
$\phi(\mathbf{P},\mathbf{S},\mathbf{Vis})$ estimated from $\mathbf{P}$ and
$\mathbf{S}$, we are able to get a much better $\mathbf{G}$, as demonstrated
in experiments.

UV map representation. The face geometry $\mathbf{G}$, pose-independent face
$\mathbf{S}$, mean face $\mathbf{\bar{S}}$, deformation $\mathbf{D}$, and
pose-dependent face $\mathbf{P}$ are transformed into UV space [2] as UV maps.
UV map $\mathbf{U}$ is a 2D representation of 3D vertices on the face mesh
model. It can be expressed as

$\mathbf{U}(u_{i},v_{i})=(x_{i},y_{i},z_{i}),$ (6)

where $(x_{i},y_{i},z_{i})$ is the 3D coordinate of vertex $i$ on the 3D face
mesh and $(u_{i},v_{i})$ is the corresponding 2D UV coordinate.

Figure 3: Illustration the UV map of a 3D face model. Given a textured face
model (a), we can compute the corresponding unwrapped texture in UV space (b),
and the corresponding UV position map (c).

The mapping relationship between the 3D object coordinate
$(X_{i},Y_{i},Z_{i})$ and the UV coordinate $(u_{i},v_{i})$ of a facial vertex
$i$ can be formulated as

$u_{i}\rightarrow\alpha_{1}\cdot Y_{i}+\beta_{1},$ (7)
$v_{i}\rightarrow\alpha_{2}\cdot\arctan(\frac{X_{i}}{Z_{i}})+\beta_{2},$ (8)

where $\alpha_{1}$, $\alpha_{2}$, $\beta_{2}$, $\beta_{1}$ are scaling and
translation constants. The mapping relationship is computed on the mean face
mesh from the Basel Face Model (BFM) [25] and applied to all the face meshes.
In this way, the points in the UV map are registered to the face mesh model.
Fig. 3 illustrates the mapping for a better understanding. This representation
guarantees the spatial consistency between face model and UV map, i.e.,
spatially neighboring points on the face model are neighboring in the UV map.
Since 2D UV maps can be processed by sophisticated CNNs, this ensures a great
potential of the representation in applications of unconstrained situations.
In the remainder of this paper, the face geometry, pose-independent face, mean
face, deformation, and pose-dependent face are represented as UV maps. For
clarity, the same notation is used for a thing in the two spaces (e.g.,
$\mathbf{G}$ is used to denote both the face geometry and the UV map of it).

Network architecture. Our self-aligned dual face regression network is an
encoder-decoder-based architecture that regresses the deformation $\mathbf{D}$
and infers the pose parameters $f$, $\mathbf{R}$ and $\mathbf{t}$ to
reconstruct the 3D face geometry from a single 2D face image. It consists of
three sub-networks: encoder, attention side branch, and decoder.

The encoder network contains a sequence of residual blocks that first extract
low-level features, which are then fed into the attention side branch. The
attention network generates an attention mask $\mathbf{A}$ with the visible
face region highlighted. Then encoder network further encodes the attended
features into high-level features. The decoder then decodes them into the
pose-dependent face $\mathbf{P}$ and the deformation $\mathbf{D}$. The face
shape $\mathbf{S}$ is obtained by Eq. 3. The pose parameters $f$, $\mathbf{R}$
and $\mathbf{t}$ are then obtained from $\mathbf{P}$, $\mathbf{S}$ and
$\mathbf{A}$ in the self-alignment module. The final face geometry
$\mathbf{G}$ is generated by applying Eq. 2.

###  III-B Occlusion-Aware Attention Mechanism

Figure 4: An example of the synthetic attention mask annotation. (a) is the
original face image. (b) is the ground truth face geometry projected on the
image plane. (c) is the binary image of the projected face. (d) is the face
image augmented with synthetic occlusions. (e) is the ground truth attention
mask corresponding to (d).

To deal with the occlusions, we adopt an attention mechanism to extract
features mainly from the visible face regions in the input images. This sub-
network is a side branch consisting of five convolutional layers. It outputs a
soft attention mask assigning high values to the pixels corresponding to the
visible regions and low values to the pixels in the occluded regions and
background region. The attention is applied to the low-level features to make
a trade-off between resolution and accuracy.

Considering the attention mask may be inaccurate in some cases, we do not
discard the information of the regions with low attention entirely. We instead
highlight the features of the visible face regions according to the attention
values. This operation can be formulated as

$\mathbf{F_{a}}=\mathbf{F_{l}}\odot\exp(\mathbf{A}),$ (9)

where $\mathbf{F_{a}}$ denotes the obtained weighted feature map,
$\mathbf{F_{l}}$ is the low-level feature map, and $\mathbf{A}$ is the
attention mask.

Once we get the attention mask, we are able to estimate the visibility of the
vertices in the pose-dependent face through

$\mathbf{Vis}(i)=\begin{cases}0&\mbox{if $n_{z}<0$ }\\\ \mathbf{A}(\lfloor
x_{i}\rfloor,\lfloor y_{i}\rfloor)&\mbox{if $n_{z}\geq 0$},\par\end{cases}$
(10)

where the 3D position of vertex $i$ is $(x_{i},y_{i},z_{i})$. The normal
direction of vertex $i$ that can be obtained from its adjacent vertices is
$(n_{x},n_{y},n_{z})$. The vertex visibility is employed in the self-alignment
module and is discussed detailedly in Sec. III-C.

Since no database has the ground truth for face occlusion annotation, we
simulate occlusions through data augmentation. Specifically, we project the 3D
face geometry to the image plane to generate a binary map that indicates the
full face region. Then we overlay patterns with random shapes to the input
image and use them as the occlusions as shown in Fig. 4. We use the resulting
binary image as the ground truth of the attention mask. In this way, we can
obtain the ground truth data for the training of the attention branch.
Although occlusions in the real world can be very diverse, our experiments
find the proposed method has the ability to predict real-world occlusions as
shown in Fig. 5.

Figure 5: The top row shows the input images and the bottom row shows the
attention masks predicted by our attention branch.

###  III-C Self-Alignment Module

This module aims to extract the pose information from the pose-dependent face
$\mathbf{P}$ and the shape information from the pose-independent face
$\mathbf{S}$ (see Fig. 2 for the two faces $\mathbf{P}$ and $\mathbf{S}$). It
is achieved by estimating the similarity transformation matrices between
$\mathbf{P}$ and $\mathbf{S}$ (i.e., $f$, $\mathbf{R}$, and $\mathbf{t}$ in
Eq. 2). The similarity transformation matrix is estimated using two sets of
correspondent landmarks, $\mathbf{K_{S}}$ and $\mathbf{K_{P}}$, extracted from
$\mathbf{S}$ and $\mathbf{P}$, respectively. The pixels with the same
coordinates in the UV maps of $\mathbf{S}$ and $\mathbf{P}$ are semantically
correspondent (e.g., the nose tip corresponds to two locations with the same
coordinates in the UV maps of $\mathbf{S}$ and $\mathbf{P}$). Thus, in our
method, $\mathbf{K_{S}}$ and $\mathbf{K_{P}}$ are extracted based on the same
UV coordinates set. Specifically, we extract the 68 landmarks as the same as
[1] for $\mathbf{K_{S}}$ and $\mathbf{K_{P}}$.

We do not simply use all the 68 landmarks. We propose to use more reliable
facial vertices, i.e., the visible landmarks, for the alignment. We define a
diagonal matrix $\mathbf{W}\in\mathbb{R}^{k\times k}$ that represents the
weight of each landmark with the visibility. The weight of the $i$th landmark
is formulated as

$\mathbf{W}(i,i)=\mathbf{Vis}(i)+eps,$ (11)

where $\mathbf{Vis}(i)$ denotes the visibility of the $i$th landmark as
mentioned earlier. $eps$ is set to $0.1$ in our implementation to avoid the
divide-by-zero error caused by the estimated visibility of all landmarks being
zero. The estimation of the similarity transformation goes as the following
steps: we first estimate $f$, and then estimate $\mathbf{R}$ and $\mathbf{t}$
using the singular value decomposition method. Specifically, We first compute
the two weighted centroids $\mathbf{M_{S}}$ and $\mathbf{M_{P}}$ of the two
sets of landmarks $\mathbf{K_{S}}$ and $\mathbf{K_{P}}$ by

$\mathbf{M_{S}}=\frac{\sum_{i=1}^{k}\mathbf{W}(i,i)*\mathbf{K_{S}}(i)}{|\mathbf{W}|},$
(12)
$\mathbf{M_{P}}=\frac{\sum_{i=1}^{k}\mathbf{W}(i,i)*\mathbf{K_{P}}(i)}{|\mathbf{W}|}.$
(13)

Then we obtain $f$ by

$f=\frac{\sum_{i=1}^{k}\lVert\mathbf{K_{P}}(i)-\mathbf{M_{P}}\rVert}{\sum_{i=1}^{k}\lVert\mathbf{K_{S}}(i)-\mathbf{M_{S}}\rVert}.$
(14)

After that, we normalize $\mathbf{K_{S}}$ and $\mathbf{K_{P}}$ as bellow:

$\mathbf{K_{S}^{{}^{\prime}}}=f*(\mathbf{K_{S}}-\mathbf{M_{S}}),$ (15)
$\mathbf{K_{P}^{{}^{\prime}}}=\mathbf{K_{P}}-\mathbf{M_{P}}.$ (16)

Performing SVD to
$\mathbf{H}=\mathbf{K_{S}^{{}^{\prime}}*\mathbf{W}*\mathbf{K_{P}^{{}^{\prime}\mathrm{T}}}}$,
we have $[U,\Sigma,P]=\mathrm{SVD}(\mathbf{H})$, the rotation matrix
$\mathbf{R}$ between $\mathbf{K_{S}^{{}^{\prime}}}$ and
$\mathbf{K_{P}^{{}^{\prime}}}$ can be obtained by

$\mathbf{R}=P*U^{\mathrm{T}},$ (17)

and $\mathbf{t}$ can be obtained by

$\mathbf{t}=\mathbf{M_{P}}-\mathbf{R}*\mathbf{M_{S}}.$ (18)

The pose estimation from landmarks requires only a small amount of computation
and has high accuracy because the estimation is performed on a number of
reliable landmarks on the two regressed faces.

###  III-D Loss Functions

The loss of our SADRNet consists of 6 components, the face geometry loss
$\mathcal{L}_{G}$, the deformation loss $\mathcal{L}_{D}$, the pose-dependent
face loss $\mathcal{L}_{P}$, the attention mask loss $\mathcal{L}_{A}$, the
edge length loss $\mathcal{L}_{E}$, and the normal vector loss
$\mathcal{L}_{V}$. Since the significance of the vertices in different face
regions may differ considerably, we adopt a weight mask $\mathbf{M}$ as [2] to
$\mathcal{L}_{D}$, $\mathcal{L}_{P}$, and $\mathcal{L}_{G}$. We adjust the
weight ratio of the four sub-regions for better training results. We use
16:12:3:0 for sub-region1 (the landmarks): sub-region2 (the eyes, nose, and
mouth): sub-region3 (the cheek, chin and forehead): sub-region4 (the neck).

$\mathcal{L}_{G},\mathcal{L}_{D}$, and $\mathcal{L}_{P}$ can be obtained by
the weighted average Euclidean distance between the estimated value and the
ground truth, i.e., generalized as

$\mathcal{L}_{N}=\sum_{u=1}^{h}\sum_{v=1}^{w}\lVert\mathbf{N}(u,v)-\mathbf{\hat{N}}(u,v)\rVert_{2}\cdot\mathbf{M}(u,v).$
(19)

$N$ denotes any one of the face geometry $\mathbf{G}$, the pose-dependent face
$\mathbf{P}$, and the shape deformation $\mathbf{D}$. $h$ and $w$ are the
height and width of the maps. $\mathbf{N}(u,v)$ denotes the estimated 3D
coordinates of the vertex at the UV location $(u,v)$ in the UV maps of
$\mathbf{G}$, $\mathbf{P}$, or $\mathbf{D}$. The symbol $\mathbf{\hat{~{}}}$
denotes the corresponding ground truth. $\mathbf{M}(u,v)$ denotes the weight
value at the pixel location $(u,v)$ in $\mathbf{M}$.

We use binary cross entropy (BCE) between the predicted attention mask
$\mathbf{A}$ and the ground truth $\mathbf{\hat{A}}$ to compute
$\mathcal{L}_{A}$.

The edge length loss $\mathcal{L}_{E}$ is defined based on the lengths of the
edges in the pose-independent face $\mathbf{S}$ as

$\mathbf{E}_{ij}=\mathbf{S}(u_{i},v_{i})-\mathbf{S}(u_{j},v_{j}),$ (20)
$\mathcal{L}_{E}=\sum_{(i,j)\in\mathcal{E}}|\lVert\mathbf{E}_{ij}\rVert_{2}-\lVert\mathbf{\hat{E}}_{ij}\rVert_{2}|.$
(21)

$\mathcal{E}$ is the edges set. It is composed of every pair of adjacent
vertices $(i,j)$ in the UV map. $(u_{i},v_{i})$ is the UV coordinates of
vertex $i$. $\mathbf{E}_{ij}$ is the edge vector.

The normal vector loss $\mathcal{L}_{V}$ is defined as

$\mathbf{n}_{ijk}=\frac{\mathbf{E}_{ij}\times\mathbf{E}_{jk}}{\lVert\mathbf{E}_{ij}\times\mathbf{E}_{jk}\rVert_{2}},$
(22)

$\displaystyle\mathcal{L}_{V}=\sum_{(i,j,k)\in\mathcal{T}}$
$\displaystyle\left|\left\langle\frac{\mathbf{E}_{ij}}{\lVert\mathbf{E}_{ij}\rVert_{2}},\mathbf{n}_{ijk}\right\rangle\right|$
(23) $\displaystyle+$
$\displaystyle\left|\left\langle\frac{\mathbf{E}_{jk}}{\lVert\mathbf{E}_{jk}\rVert_{2}},\mathbf{n}_{ijk}\right\rangle\right|$
$\displaystyle+$
$\displaystyle\left|\left\langle\frac{\mathbf{E}_{ki}}{\lVert\mathbf{E}_{ki}\rVert_{2}},\mathbf{n}_{ijk}\right\rangle\right|,$

where $\mathcal{T}$ is the triangle facets set, $\mathbf{n}_{i,j,k}$ is the
normal vector of the triangle facet $(i,j,k)$. The edge length loss and the
normal vector loss are used to generate better-looking face models.

The entire loss function of SADRNet is given by

$\mathcal{L}=\beta_{G}\mathcal{L}_{G}+\beta_{D}\mathcal{L}_{D}+\beta_{P}\mathcal{L}_{P}+\beta_{A}\mathcal{L}_{A}+\beta_{E}\mathcal{L}_{E}+\beta_{V}\mathcal{L}_{V},$
(24)

where $\beta_{G}$, $\beta_{D}$, $\beta_{P}$, $\beta_{A}$, $\beta_{E}$,
$\beta_{V}$ are respectively set to 0.1, 0.5, 1, 0.05, 1, 0.1 in our
implementation.

###  III-E Implementation Details

Our network takes cropped-out $256\times 256\times 3$ images as the input,
regardless of the effect of the face detector. The network starts with a
single convolution layer followed by a low-level feature extractor that
consists of 6 residual blocks [66] and outputs a $32\times 32\times 128$
feature map. The attention sub-network contains 5 convolution layers and a
sigmoid activation. The high-level feature extractor contains 4 residual
blocks and outputs a $8\times 8\times 512$ feature map. The decoder starts
with 10 transpose convolution layers that up-sample the feature map to
$64\times 64\times 64$, followed by 7 transpose convolution layers to output a
UV map of the face shape with size $256\times 256\times 3$ and another 7
layers to output a UV map of the pose-dependent face with size $256\times
256\times 3$.

We follow [1, 2, 12] and use the full 300W-LP [1] as the training set. 300W-LP
contains $122,450$ face images generated from 300W [1] by 3D rotation around
the y axis and horizontal flipping. Since there is no sample with a larger
than 90 degrees yaw angle in 300W-LP, we generate 5,000 samples with yaw
angles range from 90 to 105 degrees by 3D rotation to supplement the dataset.
Similar to [2], we augment the training data by randomly rotating the image
from -90 to 90 degrees, translating in the range of 0 to 10 percent of input
size, scaling the image size from 0.9 to 1.1, and scaling the color channel
separately from 0.6 to 1.4. We also generate synthetic occlusions as explained
in Sec. III-B. We use Adam optimizer with a gradual warm-up strategy [67]. We
start from a learning rate of 1e-5 and increase it by a constant amount at
each iteration. After 4 epochs, the learning rate reaches 1e-4. Then we use an
exponential scheduler that decays the learning rate by 0.85 every epoch. The
batch size is set to 16. We train our network for 25 epochs.

The original annotations of 300W-LP are 3DMM parameters, so the ground truth
of $\mathbf{D}$ can be generated by computing
$\mathbf{D}=\sum_{i}\alpha_{i}\mathbf{A}_{i}$, where
$(\alpha_{1},\alpha_{2},\dots)$ are the shape parameters,
$(\mathbf{A}_{1},\mathbf{A}_{2},\dots)$ are the shape basis vectors (including
the identity and expression basis vectors).

##  IV Experiments

In this section, we evaluate the performance of the proposed method in terms
of 3D face reconstruction, dense face alignment and head pose estimation. Our
SADRNet is quantitatively compared with state-of-the-art methods including CMD
(2019 [18]), SPDT (2019 [23]), PRN (2018 [2]) and 3DDFAv2 (2020 [16]). The
qualitative comparison of PRN, MGCNet [40] and our method are demonstrated in
Fig. 6.

TABLE I: Performance comparison on AFLW2000-3D on the task of sparse alignment (68 landmarks) and dense alignment (45K points). The NME (%) are reported. Images with different yaw angle ranges are also evaluated separately. “balanced” denotes the results on the subset with balanced distribution of the yaw angles. “mean” denotes the average results on the entire dataset. The best results are highlighted in bold. Method | 68 points | 45k points
---|---|---
2D | 3D | 2D | 3D
0 to 30 | 30 to 60 | 60 to 90 | Balanced | Mean | Mean | Mean | Mean
3DDFA [1] | 3.78 | 4.54 | 7.93 | 5.42 | 6.03 | 7.50 | 5.06 | 6.55
3DFAN [60] | 2.77 | 3.48 | 4.61 | 3.62 | - | - | - | -
DeFA [65] | - | - | - | 4.50 | 4.36 | 6.23 | 4.44 | 6.04
3DSTN [68] | 3.15 | 4.33 | 5.98 | 4.49 | - | - | - | -
Nonlinear 3DMM [19] | - | - | - | 4.12 | - | - | - | -
PRN [2] | 2.75 | 3.51 | 4.61 | 3.62 | 3.26 | 4.70 | 3.17 | 4.40
DAMDN [14] | 2.90 | 3.83 | 4.95 | 3.89 | - | - | - | -
CMD [18] | - | - | - | 3.90 | - | - | - | -
SPDT [23] | 3.56 | 4.06 | 4.11 | 3.88 | - | - | - | -
3DDFAv2 [16] | 2.63 | 3.42 | 4.48 | 3.51 | - | - | - | 4.18
SADRNet (ours) | 2.66 | 3.30 | 4.42 | 3.46 | 3.05 | 4.33 | 2.93 | 4.02

###  IV-A Evaluation Datasets

AFLW2000-3D [1] is an in-the-wild dataset with large variations in pose,
illumination, expression, and occlusion. There are 2,000 images annotated with
68 3D landmarks and fitted 3DMM parameters to recover the ground truth face
model. We evaluate both face alignment and 3D face reconstruction performance
on this dataset.

Florence [24] is a publicly available database of 53 subjects. The ground
truth annotations are meshes scanned by a structured-light system. Similar to
[21, 2, 12], each face mesh is rendered in 20 poses: a pitch angle of -15, 0,
20, or 25 degrees and a yaw angle of -80, -40, 0, 40, and 80 degrees to
generate the face images. We evaluate the 3D face reconstruction performance
on this dataset.

Figure 6: The qualitative comparison on AFLW2000-3D dataset. The estimated
landmarks are in blue and the ground truth landmarks are in red. NME(%) is
shown at the bottom right of each result.

###  IV-B Face Alignment

We employ normalized mean error (NME) as the evaluation metric. It is defined
as the normalized mean Euclidean distance between each pair of corresponding
points in the predicted result $\mathbf{p}$ and the ground truth
$\mathbf{\hat{p}}$:

$\mathrm{NME}=\frac{1}{N}\sum_{i=1}^{N}\frac{\lVert\mathbf{p_{i}}-\mathbf{\hat{p}_{i}}\rVert_{2}}{d}.$
(25)

For a fair comparison, the normalization factor $d$ of the compared methods is
computed in the same way. For sparse and dense alignment, the normalization
factor of NME is defined as $\sqrt{h*w}$ where $h$ and $w$ are the height and
width of the bounding box of all the evaluated points.

We evaluate the performance of 2D and 3D sparse alignment on the point set of
68 landmarks. We evaluate the performance of 2D and 3D dense alignment on the
point set of around 45K points selected from the largest common face region of
different methods as in [2]. Following the settings of previous works [2, 1,
18] on 2D sparse alignment, we also test the images with yaw angles in
$[0^{\circ},30^{\circ})$ (1,306 samples), $[30^{\circ},60^{\circ})$ (462
samples) and $[60^{\circ},90^{\circ}]$ (232 samples) separately, as well as
the balanced subsets of each angle interval.

Figure 7:  Results on AFLW2000-3D from our SADRNet. Our results are more
accurate than the ground truth. From the top row to the bottom row are the
input images, the sparse alignment results of SADRNet and the corresponding
ground truth (blue for our method and red for the ground truth), the
reconstructed face models, and the ground truth face models.

The quantitative results on AFLW2000-3D are shown in Table I. The results of
other methods are from published papers or produced by the official open-
source codes. We can see our method is superior to the other methods on most
metrics. Especially on 3D and dense alignment tasks, our method has taken a
clear lead. SPDT [23] generates rendered large pose training samples and uses
a CycleGAN [22] to transform the rendering style. The large pose samples in
our training database 300W-LP are mostly obtained by 3D image rotation with
large distortion. We argue that they outperform us for sparse alignment in-
between 60 and 90 degrees is because of the quality gap of training data.

Visualized results of challenging samples in AFLW2000-3D are demonstrated in
Fig. 6, in which various degrees of occlusion and different face orientations
are evaluated. We compare our method with two representative methods: MGCNet
[40] and PRN [2]. MGCNet is a model-based method that fits the shape and the
pose parameters of 3DMM by CNN. PRN is a model-free method that directly
infers 3D coordinates of face mesh vertices with the UV position map. Our pose
estimation method based on the alignment using visibility is more accurate and
robust than previous works.

On the samples where the faces are partially occluded, as shown in Fig. 6c and
Fig. 6d, the inaccuracy of the estimated poses of MGCNet leads to
misalignment. And under severe occlusion, e.g., Fig. 6e, MGCNet fails to
obtain a reasonable result, while our method is still able to precisely
estimate the head pose. PRN jointly obtains pose and shape and works well for
the visible facial region. However, PRN tends to give results with larger
errors for invisible regions (see the misaligned landmarks in Fig. 6b and Fig.
6g). It is worth noting that AFLW2000-3D [1] is semi-automatically annotated
and has some inaccurate annotations in some cases. In Fig. 7, we demonstrate
some examples from AFLW2000-3D that our predictions have relatively larger NME
but are apparently more accurate than the ground truth. This may narrow our
method’s superiority margin.

TABLE II: Performance comparison on 3D face reconstruction. Evaluations are conducted on the AFLW2000-3D dataset and Florence dataset. Around 45K points are used on AFLW2000-3D and 19K points are used on Florence. The NME (%) normalized by outer interocular distance are reported. The best results are highlighted in bold. Method | AFLW2000-3D | Florence
---|---|---
0 30 | 30 60 | 60 90 | Mean | Mean
3DDFA [1] | - | - | - | 5.36 | 6.38
DeFA [65] | - | - | - | 5.64 | -
VRN - Guided [21] | - | - | - | - | 5.26
PRN [2] | 3.72 | 4.04 | 4.45 | 3.96 | 3.75
SPDT [23] | - | - | - | 3.70 | 3.83
3DDFAv2 [16] | - | - | - | - | 3.56
SADRNet (ours) | 3.17 | 3.42 | 3.36 | 3.25 | 3.12

###  IV-C 3D Face Reconstruction

On this task, we use NME normalized by 3D outer interocular distance as the
evaluation metric. We follow the settings of [2] to evaluate our method on
AFLW2000-3D [1] and Florence [24]. For AFLW2000-3D, we use the same set of
points as we do for dense face alignment. The results under different yaw
angles are also reported. As for Florence, we choose the face region
containing 19K points. We use iterative closest point (ICP) to align the
results to the corresponding ground truth as in [2]. Table II gives the
quantitative comparison. Our method is robust to pose variations and achieves
around 13% improvement over the state-of-the-art method on both datasets.

As our method employs a nonlinear shape deformation decoder that is more
powerful than the linear bases based representation of MGCNet, our network can
reconstruct more shape variations. It is worth mentioning that the output
space of PRN is also nonlinear, but its large space, caused by entangled shape
and pose, increases the learning difficulty for the high-frequency details. It
is shown in Fig. 6 that eyes, lips, and noses of the face models reconstructed
by our method have more details than PRN. Our attention-aware mechanism also
contributes to the robustness toward the occlusions. In Figs. 6b-e, our
reconstructed faces maintain natural appearances while those from PRN are
distorted in occluded areas.

TABLE III: Performance comparison on head pose estimation. Evaluations are conducted on the AFLW2000-3D dataset. The MAEs of head pose parameters are reported. The best results are highlighted in bold. Method | AFLW2000-3D
---|---
yaw | pitch | roll | Mean
FSANet [69] | 4.50 | 6.08 | 4.64 | 5.07
GLDL [70] | 3.02 | 5.06 | 3.68 | 3.92
QuatNet [71] | 3.97 | 5.61 | 3.92 | 4.50
FDN [72] | 3.78 | 5.61 | 3.88 | 4.42
MNN [73] | 3.34 | 4.69 | 3.48 | 3.83
SADRNet (ours) | 2.93 | 5.00 | 3.54 | 3.82
SADRNet-fix (ours) | 2.93 | 4.43 | 2.95 | 3.44

###  IV-D Head Pose Estimation

On this task, we use MAE (mean absolute error) of the head pose parameters as
the evaluation metric:

$\mathrm{MAE}=\frac{1}{N}\sum_{i=1}^{N}\left|\mathbf{p}_{i}-\mathbf{\hat{p}}_{i}\right|,$
(26)

where $\mathbf{p}$ represents the predicted pose parameters and
$\mathbf{\hat{p}}$ represents the ground truth.

In Table III, we compare our proposed self-aligned module with the SOTA head
pose estimation methods. The actual output of our method is the transformation
matrix. So we convert the rotation matrix to Euler angles to calculate MAE
with the ground truth. However, when the yaw angle is close to 90 degrees, the
angle conversion suffers a serious gimbal lock problem. Some examples are
shown in Fig.8. Their yaw angles’ errors are low, and the faces’ orientations
seem nice, but the errors of the pitch and roll angles are extremely high. It
will make the quantitative evaluation result worse than the actual
performance. Thus, besides the initial evaluation results, we also report a
result marked as SADRNet-fix that ignores the samples with more than 20
degrees pitch or roll error and less than 5 degrees yaw error. However, the
negatively biased performance of our method (SADRNet) is still equivalent to
the best standalone head pose estimation method.

Figure 8: Some samples in AFLW2000-3D, in which our estimated pitch angle and
roll angle have an error of more than 20 degrees, while the yaw angle errors
are less than 5 degrees.

###  IV-E Ablation Study

Figure 9: Alternative frameworks of baselines in ablation study. The figures
(a)-(e) correspond to the 1st-5th result rows in Table IV, respectively.

We conduct ablation experiments on AFLW2000-3D to analyze the effectiveness of
the following three modules: 1) the attention mechanism, 2) the self-alignment
module, and 3) the regression via the shape deformation. The experiments are
conducted on three tasks: sparse alignment, dense alignment, and 3D face
reconstruction. The results are summarized in Table IV.

TABLE IV: Ablation study on AFLW2000-3D. The “AT” column indicates using the attention mechanism or not. The “SA” column indicates using the self alignment module or not. The “DF” column indicates whether 3D-DFAFR is achieved by regressing shape deformation “$\mathbf{D}$” or not. Applied approaches | Sparse | Dense | Rec.
---|---|---|---
AT | SA | DF |  2D |  3D |  2D |  3D |  3D
|  |  | 3.31 | 4.74 | 3.10 | 4.33 | 4.07
|  | $\surd$ | 3.43 | 4.94 | 3.21 | 4.50 | 3.37
| $\surd$ | $\surd$ | 3.18 | 4.51 | 3.03 | 4.17 | 3.39
$\surd$ |  |  | 3.16 | 4.53 | 3.03 | 4.21 | 4.02
$\surd$ | $\surd$ |  | 3.24 | 4.59 | 3.14 | 4.31 | 3.49
$\surd$ | $\surd$ | $\surd$ | 3.05 | 4.33 | 2.93 | 4.02 | 3.25

Attention mechanism. To study the contribution of the proposed attention
mechanism, we remove the attention side branch from the proposed SADRNet
(denoted as SADRNet-D; see Fig. 9c for the structure.) and compare it with
SADRNet. The results of the two networks are respectively summarized in the
3rd and the bottom rows in Table IV. We can see that the proposed attention
mechanism benefits all three tasks. In Fig. 10, we visualize the comparison.
SADRNet-D is more easily affected by the occlusions and has lower
reconstruction accuracy in the occlusion areas. In addition, SADRNet-D cannot
estimate a face orientation as accurately as SADRNet. We can see the evidence
from the bottom row of Fig. 10. We also investigate the attention mechanism on
the basic encoder-decoder architecture as shown in Figs. 9 a and d. The
corresponding results in Table IV confirm the conclusion we draw from the
comparison between SADRNet-D and SADRNet.

Dual face regression and self alignment. The distinguishing features of the
self-alignment module lie in two points. One is that we obtain the target 3D
face geometry through a two-stage refinement process (i.e., first pose-
dependent face $\mathbf{P}$ and then the final 3D face model $\mathbf{G}$ as
shown in Fig. 2) rather than a direct regression as shown in Fig. 9a. Another
feature is that we estimate the pose information by aligning two reconstructed
faces: the pose-dependent face $\mathbf{P}$ and the pose-independent face
$\mathbf{S}$, rather than direct regression using the image features as in [1]
(shown in Fig. 9b). By comparing the first and the third result rows in Table
IV, we can observe that the two-stage refinement process brings significant
gains for all of the three tasks. The comparison between the second and third
result rows demonstrates that the self-alignment-based face alignment is more
reliable than that based on direct pose regression from image features.
However, Fig. 9b has a slightly better 3D face reconstruction than Fig. 9c.
This may be because regressing $\mathbf{S}$ and $\mathbf{P}$ together may
slightly affect the estimation of $\mathbf{S}$.

Shape deformation. This paper regresses the pose-independent face $\mathbf{S}$
through the shape deformation, which estimates the differential 3D geometry
relative to the mean face template. An alternative solution to regress
$\mathbf{S}$ is to directly perform the estimation in UV space from scratch by
the decoder layers as shown in Fig. 9d. By comparing the results in the 5th
and bottom result rows in Table IV, it is easy to find that the shape
regression based on deformation provides more accurate results than direct
regression from scratch on all three tasks. Moreover, quantitatively comparing
the improvement provided by using deformation (i.e., the bottom row over the
5th row) and that provided by using attention mechanism (i.e., the bottom row
over the 3rd row), we can see the contribution of the deformation regression.
Its improvement is more than that made by the attention mechanism in terms of
3D face reconstruction.

Figure 10: SADRNet vs. SADRNet-D; results for sparse alignment and face
reconstruction are demonstrated. Facial regions around occlusions are zoomed
in for better visual comparison.

Mesh loss. Besides the losses that directly supervise the 3D coordinates of
$\mathbf{P}$, $\mathbf{S}$, and $\mathbf{G}$, inspired by [74], we also adopt
losses defined on the face mesh structure, i.e., the edge length loss and the
normal vector loss. They do not improve the quantitative results, but help to
reconstruct the face details for better visualization. In Fig.11, we
demonstrate some reconstruction results of the model trained with and without
the mesh loss. In the demonstrated cases, the estimated landmarks are almost
the same. However, the model with mesh loss can better reflect the difference
between identities. In the first example with the mesh loss, the mouth’s
openness is more suitable. In the second example, the curvature of the cheek
is better, and the reconstructed model is more recognizable. In the third
example, the hollow is more obvious.

Figure 11: With mesh loss vs. without mesh loss; results for sparse alignment
and face reconstruction are demonstrated.

###  IV-F Running Time and Model Size

Our method has a model size of 60MB (including the mean face template
parameters). In Table V we compare the model sizes of the proposed method and
the baseline methods. Our model is lighter than all other deep-learning-based
methods. The network inference for one face image takes 12ms on a GTX 1080 Ti
GPU. The self-alignment post process (i.e., the step generating $\mathbf{G}$
from $\mathbf{S}$ and $\mathbf{P}$) takes 4ms on GPU or 1.5ms on an Intel Xeon
E5-2690 CPU @ 2.60GHz. The fastest implementation of our method reconstructs
the 3D face model from a cropped image in up to 13.5 ms.

The backbone of our method, (i.e. the framework in Fig.9.a) has a model size
of 52MB. The extra size introduced by the attention side branch is 7MB. The
parameters of the 7-layer pose-dependent face decoder and the 7-layer pose-
independent face decoder add up to 1MB.

TABLE V: Comparison of model size. Method | Size
---|---
VRN [21] | 1.5GB
PRN [2] | 153MB
Nonlinear-3DMM [17] | 152MB
CMD [18] | 93MB
SADRNet (ours) | 60MB

###  IV-G Limitations

We note the following limitations of our work:

  * •

Our network only regresses the shape geometry and pose, but does not
reconstruct the facial texture from the input image.

  * •

The learning of the proposed SADRNet is fully supervised and depends on the
costly face mesh annotation. Designing a weakly supervised architecture that
can utilize additional data modalities (e.g., facial keypoint detection data,
silhouette data, segmentation data) may improve the application potential.

  * •

There is still much room for improvement in the reconstruction of high-
frequency facial details (i.e. the pores, blemishes, and wrinkles) in our
work. We believe the improvements can be made in two aspects. First, the
training dataset we currently use is labeled with the parameters of 3DMM. The
ground truth face models lack high-frequency details. Using datasets with
high-fidelity ground truth models may help the detail synthesis. Considering
that such training data is expensive, a self-supervised architecture that
utilizes the facial details in the input image as supervision may be another
feasible way. Second, although we have regressed the face shape deformation
separately in the framework, the high-frequency details are relatively minor
compared to the deformation and easy to ignore in learning. Further
decomposing the shape and details or iteratively updating the face shape with
cascaded regressors can more adequately supervise the learning of high-
frequency details.

We leave these limitations as our future work.

##  V Conclusions and Future Work

In this paper, we have proposed a self-aligned dual face regression network
(SADRNet) to solve the problem of 3D face reconstruction and dense alignment
under unconstrained conditions. We decouple the framework of face
reconstruction to two regression modules for pose-dependent and pose-
independent face shape estimation, respectively. Then, a novel self-alignment
module is presented to transform the detailed and more accurate face shape
into its corresponding pose view to yield the final face reconstruction. To
make our method robust to occlusion, we incorporate an attention module to
enhance the visible facial information and estimate the transformation matrix
only with visible landmarks. We evaluate our network on the AFLW2000-3D
database and the Florence database. With the power of robustness to occlusions
and large pose variation, our proposed method outperforms the state-of-the-art
methods by a notable margin on both face alignment and 3D reconstruction.

Lacking high-frequency facial details is the main drawback of our method and
we consider to improve our method in the future from two aspects. First, we
could finetune our SADRNet on a high-fidelity 3D scanned dataset or design a
self-supervised learning framework to train the network with high-frequency
details in the input images. Second, we plan to present a cascade
reconstruction pipeline to regress our face shape in a coarse-to-fine manner
and focus on more detailed face shape regression in the latter stages.

## References

  * [1] X. Zhu, Z. Lei, X. Liu, H. Shi, and S. Z. Li, “Face alignment across large poses: A 3d solution,” in _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * [2] Y. Feng, F. Wu, X. Shao, Y. Wang, and X. Zhou, “Joint 3d face reconstruction and dense alignment with position map regression network,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018\.
  * [3] Y. Taigman, M. Yang, M. Ranzato, and L. Wolf, “Deepface: Closing the gap to human-level performance in face verification,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2014\.
  * [4] F. Liu, Q. Zhao, X. Liu, and D. Zeng, “Joint face alignment and 3d face reconstruction with application to face recognition,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2020.
  * [5] X. Zhu, Z. Lei, J. Yan, D. Yi, and S. Z. Li, “High-fidelity pose and expression normalization for face recognition in the wild,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015.
  * [6] X. Xiong and F. De la Torre, “Global supervised descent method,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015.
  * [7] D. Chen, Q. Chen, J. Wu, X. Yu, and T. Jia, “Face swapping: Realistic image synthesis based on facial landmarks alignment,” _Mathematical Problems in Engineering_ , 2019.
  * [8] A. Mollahosseini, D. Chan, and M. H. Mahoor, “Going deeper in facial expression recognition using deep neural networks,” in _IEEE Winter Conference on Applications of Computer Vision (WACV)_ , 2016.
  * [9] T. Li, T. Bolkart, M. J. Black, H. Li, and J. Romero, “Learning a model of facial shape and expression from 4d scans,” _ACM Trans. Graph._ , 2017.
  * [10] M. Loper, N. Mahmood, J. Romero, G. Pons-Moll, and M. J. Black, “Smpl: A skinned multi-person linear model,” _ACM Trans. Graph._ , 2015.
  * [11] V. Blanz and T. Vetter, “A morphable model for the synthesis of 3d faces,” in _Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques_ , 1999.
  * [12] H. Yi, C. Li, Q. Cao, X. Shen, S. Li, G. Wang, and Y.-W. Tai, “Mmface: A multi-metric regression network for unconstrained face reconstruction,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [13] A. Tuan Tran, T. Hassner, I. Masi, E. Paz, Y. Nirkin, and G. Medioni, “Extreme 3d face reconstruction: Seeing through occlusions,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * [14] L. Jiang, X.-J. Wu, and J. Kittler, “Dual attention mobdensenet(damdnet) for robust 3d face alignment,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV) Workshops_ , 2019.
  * [15] J. Lin, Y. Yuan, T. Shao, and K. Zhou, “Towards high-fidelity 3d face reconstruction from in-the-wild images using graph convolutional networks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [16] J. Guo, X. Zhu, Y. Yang, F. Yang, Z. Lei, and S. Z. Li, “Towards fast, accurate and stable 3d dense face alignment,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2020.
  * [17] L. Tran and X. Liu, “Nonlinear 3d face morphable model,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018\.
  * [18] Y. Zhou, J. Deng, I. Kotsia, and S. Zafeiriou, “Dense 3d face decoding over 2500fps: Joint texture and shape convolutional mesh decoders,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [19] L. Tran and X. Liu, “On learning 3d face morphable model from in-the-wild images,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2019.
  * [20] L. Tran, F. Liu, and X. Liu, “Towards high-fidelity nonlinear 3d face morphable model,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [21] A. S. Jackson, A. Bulat, V. Argyriou, and G. Tzimiropoulos, “Large pose 3d face reconstruction from a single image via direct volumetric cnn regression,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * [22] J.-Y. Zhu, T. Park, P. Isola, and A. A. Efros, “Unpaired image-to-image translation using cycle-consistent adversarial networks,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * [23] J. Piao, C. Qian, and H. Li, “Semi-supervised monocular 3d face reconstruction with end-to-end shape-preserved domain transfer,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2019.
  * [24] A. D. Bagdanov, A. Del Bimbo, and I. Masi, “The florence 2d/3d hybrid face dataset,” in _Proceedings of the 2011 Joint ACM Workshop on Human Gesture and Behavior Understanding_ , 2011.
  * [25] P. Paysan, R. Knothe, B. Amberg, S. Romdhani, and T. Vetter, “A 3d face model for pose and illumination invariant face recognition,” in _IEEE International Conference on Advanced Video and Signal Based Surveillance_ , 2009\.
  * [26] Y. J. Lee, S. J. Lee, K. R. Park, J. Jo, and J. Kim, “Single view-based 3d face reconstruction robust to self-occlusion,” _EURASIP Journal on Advances in Signal Processing_ , 2012.
  * [27] P. Huber, Z.-H. Feng, W. Christmas, J. Kittler, and M. Rätsch, “Fitting 3d morphable face models using local features,” in _IEEE International Conference on Image Processing (ICIP)_ , 2015.
  * [28] S. Romdhani and T. Vetter, “Estimating 3d shape and texture using pixel intensity, edges, specular highlights, texture constraints and a prior,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2005.
  * [29] A. Jourabloo and X. Liu, “Large-pose face alignment via cnn-based dense 3d model fitting,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * [30] M. Sela, E. Richardson, and R. Kimmel, “Unrestricted facial geometry reconstruction using image-to-image translation,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * [31] A. Tuan Tran, T. Hassner, I. Masi, and G. Medioni, “Regressing robust and discriminative 3d morphable models with a very deep neural network,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * [32] A. Chen, Z. Chen, G. Zhang, K. Mitchell, and J. Yu, “Photo-realistic facial details synthesis from single image,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2019.
  * [33] A. Lattas, S. Moschoglou, B. Gecer, S. Ploumpis, V. Triantafyllou, A. Ghosh, and S. Zafeiriou, “Avatarme: Realistically renderable 3d facial reconstruction ”in-the-wild”,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [34] K. Genova, F. Cole, A. Maschinot, A. Sarna, D. Vlasic, and W. T. Freeman, “Unsupervised training for 3d morphable model regression,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * [35] S. Sanyal, T. Bolkart, H. Feng, and M. J. Black, “Learning to regress 3d face shape and expression from an image without 3d supervision,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [36] B. Gecer, S. Ploumpis, I. Kotsia, and S. Zafeiriou, “Ganfit: Generative adversarial network fitting for high fidelity 3d face reconstruction,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [37] F. Wu, L. Bao, Y. Chen, Y. Ling, Y. Song, S. Li, K. N. Ngan, and W. Liu, “Mvf-net: Multi-view 3d face morphable model regression,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [38] A. Tewari, F. Bernard, P. Garrido, G. Bharaj, M. Elgharib, H.-P. Seidel, P. Perez, M. Zollhofer, and C. Theobalt, “Fml: Face model learning from videos,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [39] Y. Deng, J. Yang, S. Xu, D. Chen, Y. Jia, and X. Tong, “Accurate 3d face reconstruction with weakly-supervised learning: From single image to image set,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , 2019.
  * [40] J. Shang, T. Shen, S. Li, L. Zhou, M. Zhen, T. Fang, and L. Quan, “Self-supervised monocular 3d face reconstruction by occlusion-aware multi-view geometry consistency,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2020.
  * [41] F. Liu, R. Zhu, D. Zeng, Q. Zhao, and X. Liu, “Disentangling features in 3d face shapes for joint face reconstruction and recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * [42] T. Bagautdinov, C. Wu, J. Saragih, P. Fua, and Y. Sheikh, “Modeling facial geometry using compositional vaes,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * [43] Z.-H. Jiang, Q. Wu, K. Chen, and J. Zhang, “Disentangled representation learning for 3d face shape,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [44] S. Laine, T. Karras, T. Aila, A. Herva, S. Saito, R. Yu, H. Li, and J. Lehtinen, “Production-level facial performance capture using deep convolutional neural networks,” in _ACM Transactions on Graphics (Proceedings of SIGGRAPH)_ , 2017.
  * [45] A. Ranjan, T. Bolkart, S. Sanyal, and M. J. Black, “Generating 3d faces using convolutional mesh autoencoders,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018.
  * [46] Y. Guo, L. Cai, and J. Zhang, “3d face from x: Learning face shape from diverse sources,” _IEEE Transactions on Image Processing_ , 2021.
  * [47] X. Fan, S. Cheng, K. Huyan, M. Hou, R. Liu, and Z. Luo, “Dual neural networks coupling data regression with explicit priors for monocular 3d face reconstruction,” _IEEE Transactions on Multimedia_ , 2020.
  * [48] Y. Chen, F. Wu, Z. Wang, Y. Song, Y. Ling, and L. Bao, “Self-supervised learning of detailed 3d face reconstruction,” _IEEE Transactions on Image Processing_ , 2020.
  * [49] a. C. T. Timothy Cootes, Gareth Edwards, “Active appearance models,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2001.
  * [50] T. F. Cootes, C. J. Taylor, D. H. Cooper, and J. Graham, “Active shape models—their training and application,” _Comput. Vis. Image Underst._ , 1995.
  * [51] P. Sauer, T. Cootes, and C. Taylor, “Accurate regression procedures for active appearance models,” _Proceedings of the British Machine Vision Conference (BMVC)_ , 2011.
  * [52] J. Sung and D. Kim, “Adaptive active appearance model with incremental learning,” _Pattern Recogn. Lett._ , 2009.
  * [53] J. Saragih and R. Goecke, “A Nonlinear Discriminative Approach to AAM Fitting,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2007.
  * [54] A. Asthana, S. Zafeiriou, S. Cheng, and M. Pantic, “Incremental face alignment in the wild,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2014.
  * [55] P. Welinder, P. Perona, and P. Dollar, “Cascaded pose regression,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2010.
  * [56] Z. Feng, J. Kittler, M. Awais, P. Huber, and X. Wu, “Wing loss for robust facial landmark localisation with convolutional neural networks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * [57] L. Liu, G. Li, Y. Xie, Y. Yu, Q. Wang, and L. Lin, “Facial landmark machines: A backbone-branches architecture with progressive representation learning,” _IEEE Transactions on Multimedia_ , 2019.
  * [58] X. Peng, X. Feris, Rogerio S.and Wang, and D. N. Metaxas, “A recurrent encoder-decoder network for sequential face alignment,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2016.
  * [59] H. Zhang, Q. Li, and Z. Sun, “Joint voxel and coordinate regression for accurate 3d facial landmark localization,” in _International Conference on Pattern Recognition (ICPR)_ , 2018.
  * [60] A. Bulat and G. Tzimiropoulos, “How far are we from solving the 2d & 3d face alignment problem? (and a dataset of 230,000 3d facial landmarks),” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * [61] A. Bulat and Y. Tzimiropoulos, “Convolutional aggregation of local evidence for large pose face alignment,” in _Proceedings of the British Machine Vision Conference (BMVC)_ , 2016.
  * [62] A. Bulat and G. Tzimiropoulos, “Two-stage convolutional part heatmap regression for the 1st 3d face alignment in the wild (3dfaw) challenge”,” in _Proceedings of the European Conference on Computer Vision (ECCV) Workshops_ , 2016.
  * [63] J. McDonagh and G. Tzimiropoulos, “Joint face detection and alignment with a deformable hough transform model,” in _Proceedings of the European Conference on Computer Vision (ECCV) Workshops_ , 2016.
  * [64] Z. Sánta and Z. Kato, “3d face alignment without correspondences,” in _Proceedings of the European Conference on Computer Vision (ECCV) Workshops_ , 2016.
  * [65] Y. Liu, A. Jourabloo, W. Ren, and X. Liu, “Dense face alignment,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV) Workshops_ , 2017.
  * [66] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * [67] P. Goyal, P. Dollár, R. B. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He, “Accurate, large minibatch SGD: training imagenet in 1 hour,” _arXiv preprint arXiv:1706.02677_ , 2017.
  * [68] C. Bhagavatula, C. Zhu, K. Luu, and M. Savvides, “Faster than real-time facial alignment: A 3d spatial transformer network approach in unconstrained poses,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * [69] T.-Y. Yang, Y.-T. Chen, Y.-Y. Lin, and Y.-Y. Chuang, “Fsa-net: Learning fine-grained structure aggregation for head pose estimation from a single image,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [70] Z. Liu, Z. Chen, J. Bai, S. Li, and S. Lian, “Facial pose estimation by deep learning from label distributions,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops_ , 2019.
  * [71] H.-W. Hsu, T.-Y. Wu, S. Wan, W. H. Wong, and C.-Y. Lee, “Quatnet: Quaternion-based head pose estimation with multiregression loss,” _IEEE Transactions on Multimedia_ , 2019.
  * [72] H. Zhang, M. Wang, Y. Liu, and Y. Yuan, “Fdn: Feature decoupling network for head pose estimation,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2020.
  * [73] R. Valle, J. M. Buenaposada, and L. Baumela, “Multi-task head pose estimation in-the-wild,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2020.
  * [74] N. Wang, Y. Zhang, Z. Li, Y. Fu, W. Liu, and Y.-G. Jiang, “Pixel2mesh: Generating 3d mesh models from single rgb images,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2016.


# Fuzzy Substring Matching: On-device Fuzzy Friend Search at Snapchat

Vasyl Pihur  Snap, IncUSA<EMAIL_ADDRESS>and  Scott Thompson  Snap,
IncUSA<EMAIL_ADDRESS>
(2018)

###### Abstract.

About 50% of all queries on Snapchat app are targeted at finding the right
friend to interact with. Since everyone has a unique list of friends and that
list is not very large (maximum a few thousand), it makes sense to perform
this search locally, on users’ devices. In addition, the friend list is
already available for other purposes, such as showing the chat feed, and the
latency savings can be significant by avoiding a server round-trip call.
Historically, we resorted to substring matching, ranking prefix matches at the
top of the result list. Introducing the ability to perform fuzzy search on a
resource-constrained device and in the environment where typo’s are prevalent
is both prudent and challenging. In this paper, we describe our efficient and
accurate two-step approach to fuzzy search, characterized by a skip-bigram
retrieval layer and a novel local Levenshtein distance computation used for
final ranking.

approximate string matching, fuzzy search, Levenshtein distance, Smith-
Waterman algorithm, skip-bigrams, local string alignment, information
retrieval

††copyright: acmcopyright††journalyear: 2018††doi: 10.1145/1122445.1122456

##  1\. Introduction

Snapchat is one of the mainstream social applications with hundreds of
millions of active daily users that exchange around 5 billion snaps a day
(both photos and videos, not including text messages). Finding the right
friends to send this astronomical volume of communications to necessitates
convenient searching capabilities. Our universal search system allows users to
search for existing friends, new users to friend, lenses, stickers, shows,
places, games and many other content types. About 50% of all searches result
in a friend selection, making it a critical point of user search experience.

Friends list is readily available on the local device to power the app’s chat
feed and is limited in size to a few thousands. It is also unique to each
user. All these considerations, together with the desire to avoid the latency
due to the server call, make it a perfect candidate for local, on-device
search experience. Historically, we checked for a substring match between the
query and the friend’s name, despite the obvious high prevalence of typo’s
(Palin et al., 2019) and name ambiguities, such as “Lucas” vs “Lukas”, for
example. Therefore, an efficient search that allows for the approximate name
matches is clearly desirable.

At the core of all fuzzy search approaches lies the idea of a fuzzy or
approximate string comparison (Navarro, 2001). How close is the query string
to each of the strings in the corpus? It is usually answered in terms of
string edits, such as a total sum of all insertions, deletions and
substitutions necessary to transform one string into another. The Levenshtein
distance (Levenshtein, 1966) is a string metric for measuring the difference
between two strings in those terms and is widely used for fuzzy search
implementations. It corresponds to a very popular global alignment
Needleman–Wunsch algorithm(Needleman and Wunsch, 1970) which describes exactly
which insertions, deletions and substitutions are taking place.

However, the Levenshtein distance, as a metric to compute the distance between
the search query and a friend name, is not ideal for our on-device friend
search use case. There are two main reasons for this:

  1. (1)

It is relatively expensive to compute, taking $O(nm)$ time where $n$ is the
length of the search query and $m$ is the length of the friend name.

  2. (2)

It is a global distance that is not suitable for an interactive search
experience where users add one character at a time and may be aiming for a
partial string match (for example, “smi” in “James Smith”).

While the first difficulty with using the Levenshtein distance is well known
and, in all fairness, the quadratic time complexity for solving such a complex
problem as fuzzy string matching is nothing to sneeze at, the second one
deserves more discussion.

If the user enters “mik” as a search query, as one would guess looking for her
“Mike” friends, computing the Levenshtein distance with the friend corpus that
has the following friends in the list [“Mike Petterson”, “Jennifer Mikoilan”,
“Mark”] produces some undesirable results. In the first case, the query
matches the prefix of the first name and the Levenshtein distance is 12, in
the second case, it matches the prefix of the last name and has a distance of
15, while in the last case (where the user entered only their first name when
registering on the platform), it does not match much at all and it has a
distance of only 2!

What is happening here is the issue of global alignment of the two strings
versus the local one. Most of the search queries are not complete in a sense
that the user attempted to enter the whole friend name when looking for
someone. They enter one character at a time and expect to see friends that
“partially” match the query string. For this specific application, a prefix
match is clearly the most desirable and should ideally have a distance of 0.
One can make an argument that both “Mike Petterson” and “Jennifer Mikoilan”
should both have a distance of 0 (no string edits are required for a local,
substring match), while “Mark” should have a distance of 2, since it requires
a substitution of “i” for “a” and the insertion of “r”.

This idea of local alignment led us to explore the ubiquitous Smith-Waterman
sequence alignment algorithm(Smith and Waterman, 1981), widely used in
genetics for determining the exact place of a short genetics sequence with
respect to a reference genome. It is the right approach, but it does not
easily produce a metric, given how the algorithm is defined, so some
modifications are necessary for our purposes.

In the following sections, we will describe our solutions to the two
challenges that prevented us from using the Levenshtein distance out of the
box. The first one solves the computational problem and the second one
modifies the Levenshtein distance computation to produce a local alignment
score, instead of the global one. In essence, the proposed local Levenshtein
distance is related to the Smith-Waterman algorithm in the same way as the
original Levenshtein distance is related to the Needleman–Wunsch one.

’ a’ | ’ab’ | ’bc’ | ’c ’ | ’ 1’ | ’12’ | ’2 ’ | ’ a’ | ’a1’ | ’ b’ | ’ac’ | ’b ’ | ’c1’ | ’ 2’ | ’1 ’ | ’2a’ | ’ 1’
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | $\frac{1}{2}$ | $\frac{1}{2}$ | $\frac{1}{2}$ | $\frac{1}{2}$ | $\frac{1}{2}$ | $\frac{1}{2}$ | $\frac{1}{2}$ | $\frac{1}{2}$
Table 1. Skip-bigrams for the string “abc 12” given $\lambda=\frac{1}{2}$ and
$k=1$. Notice the additional bigrams containing the empty character in the
front and the initials at the end. Also, $a1$ is the initials bigram which was
appended to the end of the string.

##  2\. Two-step fuzzy search

In all large-scale search applications or, as in our case, the resource-
constrained ones, a rule of thumb is to substitute expensive computations with
cheaper ones. The whole approach of retrieval versus ranking in search is
based on this idea, where retrieval is a set of cheaper operations that can be
performed on all or most elements of the corpus, while the final ranking is
usually much more expensive and can be performed on the top-$K$ retrieved
results for fine-tuning to produce the final ordered set of relevant results.

So we will use a novel (as far as we know) local version of the Levenshtein
distance for ranking and a skip-bigrams based string comparison for the
lightweight retrieval layer.

###  2.1. Skip-Bigrams Retrieval

Instead of operating in the string character space, as is commonly done for
most fuzzy string comparison algorithms, we will instead compute a distance
between two strings that is based on skip-bigrams(Guthrie et al., 2006). When
we talk about bigrams here, we are talking about two characters, not two
“words”. For example, the string “abc” has two bigrams, “ab” and “bc”. These
can be thought of as 0-skip bigrams, as no characters between the first and
second characters were skipped. This same string also has a 1-skip bigram “ac”
that skips the character “b”. No higher order skip bigrams are present because
of the string length.

There are at least two desirable properties of the skip-bigrams for our
purposes. The first one is that the cardinality of all possible skip-bigrams
does not depend on the skip order (its size is still the number of all
possible characters squared) and is relatively small in practice, since most
character combinations are not observed in a limited corpus. Moving, for
example, to trigrams would dramatically increase the number of things we need
to track.

However, 1-skip bigram is, to a certain degree, equivalent to a trigram, yet
has this second desirable property of being “fuzzy”, meaning that its second
character can be arbitrary. Higher order skip-bigrams allow for even more
fuzziness.

Not tracking the position of bigrams within the string allows for significant
gains in efficiency, while at the same time offers the ability to accommodate
character insertions and deletions. The penalty we pay for this flexibility is
that we require a second, more expansive, computation to validate the results.

####  2.1.1. Skip-bigramgs Generation

For each string considered (as well as for the query string), we prepand it
with an empty “ ” character. The reason for doing that is that we want prefix
matches to rank higher than simple substring matches from the middle of the
string.

In addition, since a large portion of our friend names have a display name in
the form of “first_name last_name”, we would like to allow for the ability to
search by their initials 111Thanks to Ben Hollis for the suggestion.. For
example, “Mike Petterson” should show up in search results for “mp”. For this
purpose, we append initials at the end of the original string with a space
separator.

Thus, before any bigrams are generated, we modify our input strings with these
two modifications. Here are a few examples:

    ’abc’               -> ’ abc’
    ’abc 123’           -> ’ abc 123 a1’
    ’mike petterson jr’ -> ’ mike petterson jr mp’

We then generate bigrams up to the order $k$, where the weight of each bigram
is given by

$\lambda^{k},$

where $\lambda$ is the decay parameter and $k$ is the order of the skip-
bigram. In a case when the skip-bigram is present in more than one order, the
maximum order is used. Practically, these weights are stored in a hashmap
where the keys are the skip-bigrams and values are the corresponding weights.

For example, the string “abc 12” is converted to the bigrams map shown in
Table 1 when $\lambda=\frac{1}{2}$ and $k=1$. It takes $O(m)$ time complexity
to construct the skip-bigram representation of a string where $m$ is the
length of the string. Of course, one has to do that for each string in the
corpus over which the search is made. This initial, one-time cost associated
with this retrieval layer needs to be paid only once, with all subsequent
computations having a fixed cost of querying the bigram hashmap.

####  2.1.2. Bigrams distance function

We compute the following distance between two strings based on their bigrams
representations

$BD(q,s)=\sum_{B_{q}}(q_{i}-s_{i})^{2}-I(q_{i}=s_{i})q_{i}^{2},$

where $q$ is the query string, $s$ is the target string,
$B_{q}={b_{1},\dots,b_{n}}$ is the set of skip-bigrams from the query string,
$Q={q_{1},\ldots,q_{n}}$ are the scores for each skip-bigram from the query
string representation, $S={s_{1},\ldots,s_{n}}$ are the scores for each skip-
bigrams from the target string representation and $I(a=b)$ is the identity
function equal to 1 if true and 0 otherwise. In a case when a bigram is not
present in the target string, its score $s_{i}=0$.

As one can see, we penalize mismatches in skip-bigram weights and reward equal
weight matches (the more negative the score, the closer the match). This
results in an efficient and fast (constant time after construction of the
hashmap) distance computation across all target strings, producing a ranked
list of results where, by design, the prefix matches are always at the top,
substring matches follow next and lastly fuzzy results round up the list.

We could have stopped here and presented the ordered list, but the problem is
that the results from this step are more fuzzy than desired, even at
relatively conservative distance thresholds. This is due to the fact that the
typical query length is less than 5 characters and few spurious bigram
collisions across the target string result in a small distance value. For
example, “mik” will match “m123ik” quite well, despite the fact that three
insertions would be necessary and it would be hard to expect the user to make
so many typo’s.

###  2.2. Local Levenshtein distance (LLD)

Given that our queries are shorter than 5 characters in most cases, even two
substitutions, insertions or deletions look too fuzzy to our users with
negative engagement consequences. After all, two substitutions out of four
characters is already only a 50% match which is pretty fuzzy. Therefore,
ideally we should be showing results that are one insertions, deletion or
substitution away, at most.

We already discussed the undesired global properties of the Levenshtein
distance and the promise of the Smith-Waterman algorithm to provide a more
local match. Combining the two approaches, we propose a new, asymmetric and
local Levenshtein metric. We will first describe the Local Levenshtein
distance computation in Algorithm 1 and then point out the differences with
the original Levenshtein distance.

Algorithm 1 Local Levenshtein Distance (inputs: $q$ \- a query string, $s$ \-
a target string).

1:procedure LLD

2: n := len(q)

3: m := len(s)

4: d[0..m, 0..n] := 0

5:

6: for $i:=1$ to $n$ do

7: d[i, 0] := i

8:

9: minDist := Inf

10: for $i:=1$ to $n$ do

11: for $j:=1$ to $m$ do

12: if q[i] = s[j] then

13: cost := 0

14: else

15: cost := 1

16:

17: top := d[i-1, j] + 1

18: left := d[i, j-1] + 1

19: diag := d[i-1, j-1] + cost

20: d[i, j] := min(top, left, diag)

21:

22: if i = n then

23: minDist = min(minDist, d[i, j])

24:

25: return(minDist)

There are two major differences with the global Levenshtein distance:

  1. (1)

We do _not_ initialize the first row of the matrix $d$ to $0,\ldots,m$. This
idea is borrowed from the Smith-Waterman algorithm and is generally applicable
across all local alignment schemes. The reason is that we do not want to
penalize for starting a first character match anywhere along the target
string.

  2. (2)

Instead of returning $d[n,m]$, the global score of aligning all characters of
the query string with all characters with the target string, we return the
minimum of the last row. This, in fact, is the smallest distance of matching
all characters of the query string to an arbitrary _sub-sequence_ of
characters in the target string.

These two small modifications make a huge difference and the metric exhibits
behavior that we want: prefix and substring matches have a distance value of
0, while a non-zero score captures the number of modifications required to
align the query string anywhere along the target string.

To get a better sense on how local vs global algorithms differ, we compute
both in Table 2 and Table 3 for the same query “mike” and the target string
“hi mcke!”. For the global comparison, the minimum is 4 and is found in the
bottom right corner of the table, while the local one has a minimum of 1 and
it is found on the vertical letter “e”, finishing the match for “mcke”. The
result from the local Levenshtein distance indicates that there exists an
approximate _substring_ match with a single character modification and the
exact position of that alignment ends on the second to last character.

One obvious extension here is to have different costs for different
substitutions which is influenced by the keyboard layout and would likely need
to be language specific. Letter “a” is often substituted for “s” in English
and should have a smaller cost than any other more distant combinations. This
is all complicated by the existence of multiple keyboard layouts in different
languages and different methods for entering search queries (typing vs
swiping) and so forth. For the first iteration, we set the cost to 1 in all
cases. It is possible to also tune the cost of deletions and insertions,
perhaps based on the observed user tendencies towards them. This again will
remain the focus of future work.

|  | h | i |  | m | c | k | e | !
---|---|---|---|---|---|---|---|---|---
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
m | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1
i | 2 | 2 | 1 | 2 | 1 | 1 | 2 | 2 | 2
k | 3 | 3 | 2 | 2 | 2 | 2 | 1 | 2 | 3
e | 4 | 4 | 3 | 3 | 3 | 3 | 2 | $None$ | 2
Table 2. Local Levenshtein distance between query “mike” and target string “hi mcke!”. Notice the first row being all 0’s and the minimum distance of 1 occurring at row 5 and column 8, indicating a single substitution of “i” for “c”. |  | h | i |  | m | c | k | e | !
---|---|---|---|---|---|---|---|---|---
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
m | 1 | 2 | 3 | 4 | 3 | 4 | 5 | 6 | 7
i | 2 | 3 | 2 | 3 | 4 | 3 | 4 | 5 | 6
k | 3 | 4 | 3 | 4 | 5 | 4 | 3 | 4 | 5
e | 4 | 5 | 4 | 5 | 6 | 5 | 4 | 3 | $None$
Table 3. Global Levenshtein distance between query “mike” and target string
“hi mcke!”. This is just to contrast this with the local version. Notice that
the distance is equal to 4 (bottom right) and both the first row and the first
column are filled with non-zero counts.

###  2.3. Combining retrieval and Local Levenshtein distance

In the offline phase, we pre-compute all skip-bigrams for all target strings
in the corpus and save them in hashmaps, one hashmap for one target string
(Algorithm 2).

Algorithm 2 Offline: Build bigrams hashmaps for the $K$ strings in the corpus
($k$ \- a skip-bigram order, $\lambda$ \- a decay factor, a set of $K$
documents with strings $s_{1},\ldots,s_{K}$).

1:procedure Build Bigrams Hashmaps

2: for $i:=1$ to $K$ do

3: $M_{i}$ := Bigrams($s_{i}$, k, $\lambda$)

4: return($M$)

In the online (querying) phase, we then perform Algorithm 3 where we loop over
all target strings in the corpus and output strings with Local Levenshtein
distance $t<=2$.

Algorithm 3 Online: Fuzzy Search (inputs: $q$ \- a query string, $k$ \- a
skip-bigram order, $\lambda$ \- a decay factor, a set of $K$ hashmaps built
offline by Algorithm 2.

1:procedure Fuzzy Search

2: queryBigrams := Bigrams(q, k, $\lambda$)

3: finalResults := []

4: for $i:=1$ to $K$ do

5: bd := BD(queryBigrams, $M_{i}$)

6: if bd ¡= $t_{1}$ then

7: lld := LLD(q, $s_{i}$)

8: if lld ¡= $t_{2}$ then

9: finalResults := append(finalResults, $s_{i}$)

10:

11: return(sort(finalResults))

We are currently experimenting with different parameter configurations.
However, we have settled on both $t_{1}$ and $t_{2}$ to be equal to 1 and the
$\lambda$ parameter is preferred to be 1, as well. The argument for the skip
order $k$ is still being investigated, but in practice it looks like 1 will
also be sufficient (we do not observe a higher degree of friend
discoverability with large skip numbers). We also found that enabling fuzzy
capabilities for search queries with one or two characters is not necessary,
as it introduces too many noisy results even with a Levenshtein distance of 1
(every string matches for a single character in this case and a single
character match is sufficient for the two character case which is too fuzzy
for practical applications).

##  3\. Discussion

When we embarked on the fuzzy search capabilities, the number one issue we
needed to solve was performance. Searching over several thousands of friends
on a low-end Android device after each character that the user types is
expensive and any proposed solution would have to be reasonably light. We are
pleased to report that we have not encountered any performance issues after
many months of experimentation. In addition, there are several major
optimization that could be done to further increase the efficiency. For
example, a C++ implementation would be still much faster, or an incremental
local Levenshtein distance computation could be implemented where each new
input character just adds a new row to Table 2, instead of recomputing the
whole table after each character. There are, of course, other known
optimizations for computing the Levenshtein distance itself (Ukkonen, 1985).

We are still experimenting with the final ranking, which is currently based on
the local Levenshtein distance first and then the bigrams distance second.
With $\lambda=1$, this puts prefix matches first, substring matches second and
then fuzzy matches last. Of course other factors, such as how recently you
have interacted with a particular friend, are also important and need to be
incorporated into the final search ranking through well-known ranking
techniques (Liu, 2011).

The proposed approach to fuzzy search has been specifically designed with a
small corpus in mind (at most several tens of thousands items), but more
importantly where “documents” in this corpus are very short. Here, the name of
each friend is likely under two dozen characters and often much shorter. This
is obviously key to the efficiency aspect of the bigrams algorithm which loses
its discriminating abilities as the number of bigrams in a target string grows
large. We specifically avoided any form of tokenization because it was not
necessary for our application. For much larger applications and more complex
documents, other approaches may prove more practical (Boytsov, 2011).

## References

  * (1)
  * Boytsov (2011) Leonid Boytsov. 2011\.  Indexing Methods for Approximate Dictionary Searching: Comparative Analysis.  _ACM J. Exp. Algorithmics_ 16, Article 1.1 (may 2011), 91 pages.  https://doi.org/10.1145/1963190.1963191
  * Guthrie et al. (2006) David Guthrie, Ben Allison, Wei Liu, Louise Guthrie, and Yorick Wilks. 2006.  A Closer Look at Skip-gram Modelling. In _Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC’06)_. European Language Resources Association (ELRA), Genoa, Italy.  http://www.lrec-conf.org/proceedings/lrec2006/pdf/357_pdf.pdf
  * Levenshtein (1966) V. I. Levenshtein. 1966\.  Binary Codes Capable of Correcting Deletions, Insertions and Reversals.  _Soviet Physics Doklady_ 10 (Feb. 1966), 707\.
  * Liu (2011) Tie-Yan Liu. 2011\.  _Learning to Rank for Information Retrieval._ Springer. I–XVII, 1–285 pages.
  * Navarro (2001) Gonzalo Navarro. 2001\.  A Guided Tour to Approximate String Matching.  _ACM Comput. Surv._ 33, 1 (mar 2001), 31–88.  https://doi.org/10.1145/375360.375365
  * Needleman and Wunsch (1970) S. B. Needleman and C. D. Wunsch. 1970.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  _J. Mol. Biol._ 48 (1970), 443–453.
  * Palin et al. (2019) Kseniia Palin, Anna Feit, Sunjun Kim, Per Kristensson, and Antti Oulasvirta. 2019.  How do People Type on Mobile Devices?: Observations from a Study with 37,000 Volunteers. 1–12.  https://doi.org/10.1145/3338286.3340120
  * Smith and Waterman (1981) T. F. Smith and M. S. Waterman. 1981.  Identification of common molecular subsequences. In _Journal of Molecular Biology_ , Vol. 147(1). 195–197.
  * Ukkonen (1985) Esko Ukkonen. 1985\.  Algorithms for approximate string matching.  _Information and Control_ 64, 1 (1985), 100–118.  https://doi.org/10.1016/S0019-9958(85)80046-2 International Conference on Foundations of Computation Theory.