(Face Alignment) One Millisecond Face Alignment with an Ensemble of Regression Trees 笔记

人脸关键点检测，也可以认为是人脸对齐（face alignment）可以采用多种方法进行实现，其中一种比较有代表性的方法是使用回归来完成这一功能。2014年CVPR上“One Millisecond Face Alignment with an Ensemble of Regression Trees”这篇文章是回归方法中的一种，Dlib库中的人脸关键点检测就是依据这一方法进行了实现。

论文主要特点

1，使用级联的回归树（ensemble of regression trees）来实现人脸对齐
2，将此方法拓展使得可以轻易的处理缺失数据
3，在速度和准确率上都得到了很优秀的效果

论文主要方法

此方法与之前的“Cascaded pose regression”和“Face alignment by explicit
shape regression”方法属于同一个类型，其核心都是使用了两层的回归来建立数学模型。

在第一层回归，其迭代公式为：

{\hat{S}}^{(t + 1)} = {\hat{S}}^{(t)} + γ_{t} (I, {\hat{S}}^{(t)})

其中S是形状向量，存储着所有脸部关键点的位置， $γ_{t}$ 是一层的回归器，其输入为当前的形状向量和训练图片，其输出则是对所有的关键点的位置更新量。可以看到，在第一层的级联回归器中，每经过一级级联回归器，就会对所有关键点位置进行一次更新来达到更正确的位置。

在第二层回归，也就是 $γ_{t}$ 内部也是一次回归的过程，在本篇文章中采用的是Gradient Tree Boosting Algorithm的方法来得到一系列的回归树（Regression Tree)最终完成第二级的回归，需要注意的是，第二级回归的对象是当前预测值和真实值的差值。

第一层回归训练过程

首先，有训练数据集 $(I_{1}, S_{1}), . . . (I_{n}, S_{n})$ ，其中 $I_{i}$ 图片， $S_{i}$ 为人脸关键点的位置。
在第一层的回归训练中，数据组织形式可以写为 $(I_{π i}, {\hat{S_{i}}}^{(t)}, Δ S_{i}^{(t)})$ ，其中 $I_{π i}$ 为数据集中的图片， ${\hat{S_{i}}}^{(t)}$ 是第一层级联回归的第t层的预测关键点位置， $Δ S_{i}^{(t)}$ 是这一层回归结果和真实值的差值。
其迭代公式为：

{\hat{S}}^{(t + 1)} = {\hat{S}}^{(t)} + γ_{t} (I, {\hat{S}}^{(t)})

Δ S_{i}^{(t + 1)} = S_{π i} - {\hat{S}}^{(t + 1)}

按照这样的方式不断进行迭代，当第一层回归级联层数设置为K层时，就会产生 $γ_{1}, γ_{2}, . . ., γ_{k}$ 这些回归器，这K个回归器就是我们通过训练所要得到的回归模型。

第二层回归训练过程

第二层的训练就是要具体到每一个 $γ_{t}$ 是如何训练得到的，第二层的回归器可以有多种方法实现，比如随机蕨（Random Fern）或者本篇文章中使用的回归树。在本篇文章中使用Gradient Boosting Tree Algorithm算法实现。

回归树模型

首先简单的介绍回归树。回归树是一种将特征空间进行分割，之后在每一个分割空间进行拟合的简单模型。其数学表达式可以些为：

f (x) = \sum_{m = 1}^{M} c_{m} I (x \in R_{m})

式中

R_{1}, R_{2}, . . ., R_{m}

为m个划分的子空间，

c_{m}

为每个子空间对应的权值，加和之后就是这一个回归树模型的输出。建立回归树的过程也就是寻找使误差和模型输出最小的划分和权值的过程。
以平方误差为例，定义误差为

\sum (y_{i} - f (x_{i}))

, 首先考虑最优的

c_{m}

，设定预测模型中表示为

{\hat{c}}_{m}

，可以很容易的看到在每个划分的子空间

R

中，最优的

c_{m}

就是当前子空间对应的真实预测值的平均，可以表示为：

{\hat{c}}_{m} = a v e (y_{i} ∣ x_{i} \in R_{m})

这样就很容易找到了适合的

c_{m}

，于是如何建立回归树这一问题的关键在于如何确定特征子空间的划分。这一寻找过程可以描述如下：

在特征集合中找到用于分割的点 $s$ ，和分割的变量 $j$ ，这样可以将空间划分为两部分; $R_{1} (j, s) = (X ∣ X_{j} \leq s) a n d R_{2} (j, s) = (X ∣ X_{j} \geq s)$
之后在最小平方准则下找到最优的 $j, s$ $min_{j, s} [min_{c 1} \sum_{x_{i} \in R_{1} (j, s)} (y_{i} - c_{1})^{2} + min_{c 2} \sum_{x_{i} \in R_{2} (j, s)} (y_{i} - c_{2})^{2}]$ 其中的 $c_{1}, c_{2}$ 可以通过上面提到的公式找到，即：
${\hat{c}}_{1} = a v e (y_{i} ∣ x_{i} \in R_{1} (j, s)) a n d {\hat{c}}_{2} = a v e (y_{i} ∣ x_{i} \in R_{2})$

于是，通过这样的方式就可以建立一个回归树模型。

Boosting 方法

Boosting方法是一种强有力的方法，既可以应用于分类问题上，也可以应用于回归问题上。这一方法的思想是将多个弱分类器进行组合，来组成一个高效的分类器。
AdaBoost算法是这一类方法中比较有代表性的，以此为例简单介绍这一方法。首先给出这一算法结构图如下：
(Face Alignment) One Millisecond Face Alignment with an Ensemble of Regression Trees 笔记
这一算法的基本流程为输入样本经过多级分类器 $G_{n} (x)$ 最终得到最优的结果，所有的分类器的输出结果都会作为下一级分类器的输入，在这一过程中不断找寻 $α_{m}$ 作为使分类效果更优秀的m层权重。总而言之，就是在训练过程中，不断提升对正确分类有贡献样本的权重，同时减轻对错误分类贡献的样本的权重，最终将弱分类器组合，产生优秀的分类效果。
这一算法的数学描述如下：
(Face Alignment) One Millisecond Face Alignment with an Ensemble of Regression Trees 笔记

Boosting 应用于加性模型（Additive Model）

加性模型的基本思想是用多个模型累加的结果来代替单一的模型，这样的话可以在一些复杂的非线性问题中取得更优秀的效果。这一思想也可以被应用于Boosting上，具体的思路是在Boosting每层的模型所处理的都是上一步的残差，这样的话最终所有单个模型累加的和才是预测结果。而普通的Boosting只是数据依次通过每层模型，最终输出只是最后一层模型的结果，不是前几层的累加。可以将这一方法描述如下：
(Face Alignment) One Millisecond Face Alignment with an Ensemble of Regression Trees 笔记
于是可以看到和上面的AdaBoost相比，最终输出是 $f_{1} (x) + f_{2} (x) + . . . + f_{m} (x)$ .这就是Boosting应用于加性模型的方法，这一方法在后面的树模型和Gradient Boosting Tree Algorithm有很关键的作用。

Boosting Trees

以下介绍将Boosting方法应用于树的表示，在介绍回归树时我们知道了树模型就是划分特征子空间和找到对应权值的过程，于是可以将分类准则定义为

x \in R_{j} \Rightarrow f (x) = γ_{j}

表示当特征

x

位于空间

R_{j}

，则输出预测结果

γ_{j}

。这样一棵树可以如下表示：

T (x; θ) = \sum_{j = 1}^{J} γ_{j} I (x \in R_{j})

其中 $θ = {R_{j}, γ_{j}}_{1}^{J}$ 。自然，建立一颗树的过程也可以写为

\hat{θ} = a r g min_{θ} \sum_{j = 1}^{J} \sum_{x_{i} \in R j} L (y_{i}, γ_{j})

Boosted Tree模型就是多棵树的加和，当有M棵树时表示为

f_{M} (x) = \sum_{m = 1}^{M} T (x; θ)

于是将Boosting应用于树时，在加性模型中的每一步迭代时，可写为：

{\hat{θ}}_{m} = a r g min_{θ_{m}} \sum_{i = 1}^{M} L (y_{i}, f_{m - 1} (x_{i}) + T (x_{i}; θ_{m}))

Gradient Boosting Tree

这里终于可以描述本篇文章这一算法了。关于梯度下降的相关内容这里不做重复，网上有很多解释，这里主要介绍如何将梯度下降应用于Boosting Tree模型中。
在加性模型当中，对于第 $f_{m - 1} (x_{i})$ 可以将其梯度表示为：

g_{i m} = [\frac{d L (y_{i}, f (x_{i}))}{d f (x_{i})}]_{f (x_{i}) = f_{m - 1 (x_{i})}}

在Gradient Boosting Tree中会面临这样一个问题，如果想要在训练数据中实现梯度下降，找到误差函数的解析解是很容易的，然而当使用在这一算法中时，会面临难以计算的问题，所以此算法可以采用了这样一种思路来完成迭代，在加性模型的每一步中，寻优时的误差不是来自于真实值和预测值的误差，而是来自于加性模型中上一个模型计算的梯度。表达式为：

\hat{θ} = a r g min_{θ} \sum_{i = 1}^{N} (- g_{i m} - T (x_{i}; θ))^{2}

于是我们可以得到完整的Gradient Tree Boosting 算法：
(Face Alignment) One Millisecond Face Alignment with an Ensemble of Regression Trees 笔记
比较值得注意的就是在2.(b)中回归树 $R_{j m}$ 区域拟合的是梯度 $γ_{i m}$ ，在2.(d)中使用了加性模型(Additive Model)的迭代方式。

论文中使用的Gradient Boosting Tree Algorithm

首先给出论文中使用的训练 $γ_{r}$ ，即第二层回归器的训练算法。
(Face Alignment) One Millisecond Face Alignment with an Ensemble of Regression Trees 笔记
对比上面给出的原始算法可以看到，本论文中使用了平方误差 $\frac{1}{2} [y_{i} - f (x_{i})]^{2}$ 作为Loss Function，于是直接求导得到 $y_{i} - f (x_{i})$ ，在每一步迭代中使用这一梯度作为拟合对象，最终构建模型。

需要注意的一点是，在每一个二层回归中，输入回归对象是每一个第一层回归完成后的误差 $Δ S_{i}^{t}$ 作为每一个第二层回归的输入，而不是直接真实关键点位置作为输入。

以上就是这篇文章所使用算法的基本介绍，在 The Elements of Statisticlal Learning 中第9，10章对这一算法有详细和全面介绍，如有不清楚可以参考。

算法实现中的几个细节

Shape invariant split test

这一方法解决的是在输入图片每次进行回归迭代找寻最优的下一步关键点位置时，如何确定下一步关键点的坐标。这里给出的方法是采用预测值基于真实值的相对坐标。举个例子，当 $k_{u}$ 表示当前待选特征点序号时，此时这一点的横坐标为 $X_{k u}$ ，找到与其最近的真实特征点，其横坐标表示为 $U$ , 那么二者之间的差值表示为 $δ X_{u} = U - X_{k u}$ ，于是加入旋转和尺度变换，可以用表示为 $U = X_{k} u + \frac{1}{s_{i}} R_{i}^{T} δ X_{u}$ ,同理 $y$ 也是一样的，这样就可以把特征点的绝对坐标转换为相对坐标。

建立回归树时如何选择节点

在建立过程中会产生一系列的节点，之后在这其中选择最优节点。在拟合回归树中使用平方误差作为代价函数。待选节点为 $θ$ ，最优节点表示为 $θ^{*}$ 。此时的目标时最小化下列式子：

E (Q, θ) = \sum_{s \in {l, r}} \sum_{i \in Q {θ, s}} ∥ r_{i} - μ_{θ, s} ∥^{2}

式子中，l,s 分别代表左右子树， $μ_{θ, s}$ 代表按照当前划分产生的结果。用回归树拟合的目的是最小化这一过程。
首先很容易理解在左右子树其平方和最小值为左右子树分别的平均值，表示为

μ_{θ, s} = \frac{1}{∣ Q_{θ, s} ∣} \sum_{i \in Q {θ, s}} r_{i} f o r s \in {l, r}

将这一公式代入上式打开平方的形式，进行推导舍弃与 $θ$ 无关项，可以得到

a r g min E (Q, θ) = a r g max \sum_{s \in {l, r}} ∣ Q_{θ, s} ∣ μ_{θ, s}^{T} μ_{θ, s}

根据左右子树之间的关系已知左子树的值就可以算出右子树，所以对于上面的优化问题，事实上只需要计算一边的值即可。这样就完成了单颗回归树拟合的问题。

特征点的选择

在随机选取特征的过程中，如何控制随机生成的位置距离当前特征点的距离是一个问题，距离太远显然不如距离近一些好。于是引入参数 $λ$ ，使用指数形式来控制这一距离

P (u, v) \propto e^{- λ ∥ u - v ∥}

缺失值的处理

在建立回归树选择节点时，其代价函数可以被很容易的拓展为适应处理缺失值的形式，可以写为

E (Q, θ) = \sum_{s \in {l, r}} \sum_{i \in Q {θ, s}} (r_{i} - μ_{θ, s})^{T} W_{i} (r_{i} - μ_{θ, s})

其中 $W_{I}$ 就是处理缺失值的权向量，如果不缺失它的值为1，缺失值为0。与此相对应，在建立回归树时面对残差也可以乘上这一缺失值的权向量。

参考文献

The Elements of Statisticlal Learning
One Millisecond Face Alignment with an Ensemble of Regression Trees
Face Alignment by Explicit Shape Regression