Face Recognition

Given a database of face images of people, and a new test image, answer the following question:
“The test image contains the face of which individual from the database?”
即基于给定的测试图像，在数据库中找到一个与之匹配的个体。

Challenge

• detection检测
• pose variation姿势变化
• illumination variation光照变化
• expression variation表情变化
• age variation年龄变化
• variation of facial accessories面部组成部分的变化
• caricatures/paintings漫画/绘画的影响

• blur/noise/scanner artifacts模糊、噪声、扫描仪效果影响
  种种如上的变化都需要人脸识别来克服。

  人脸识别基本步骤

  Training Phase训练阶段：

• 收集个体的一张或多张面部照片，称为gallery image，形成数据库
• 归一化图像：把人脸从背景、姿势和光照变化中“抠”出来
• 从归一化的人脸图像中解析出相对的特征出来
• 把相应的提取出来的特征用该图像对应个体的身份标识

Testing Phase测试阶段：

• 选择一张需要测试的图像，probe image。
• 归一化该probe image，把人脸从背景、姿势和光照变化中“抠”出来
• 从归一化的人脸图像中提取出相对的特征出来

• 找到一张gallery image，它的特征与probe image最接近，该gallery image对应的identity就是probe image对应的人的identity

  前提：测试图像中的人对应的identity，必须出现在gallery image中。

PCA算法简介

主成分分析（Principal Component Analysis，PCA）， 是一种统计方法。通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量，转换后的这组变量叫主成分。
主成分分析能降低所研究的数据空间的维数。即用研究m维的Y空间代替p维的X空间(m

PCA在人脸识别中的应用

1. 用N个包含d个元素的向量x⃗ i${\overrightarrow{x}}_i$来表示N张不同的图像
2. ∀i,x⃗ i∈Rd$\mathrm{\forall }i,{\overrightarrow{x}}_i\in R^d$,d可能会很大

3. 目标是从向量x⃗ i${\overrightarrow{x}}_i$中提取出k$k$个特征出来，其中，k<<d$k<<d$
   我们可以把原始的向量从d维空间投影到k维空间上。这就可以用到PCA的方法来降低维度。

   PCA算法

   • 计算给定点的均值。
     x¯⃗ =1N∑Ni=1x⃗ i,x⃗ i∈Rd,x¯⃗ ∈Rd$\overrightarrow{\overline{x}}=\frac{1}{N}\sum _{i=1}^N{\overrightarrow{x}}_i,{\overrightarrow{x}}_i\in R^d,\overrightarrow{\overline{x}}\in R^d$
   • 在每一点减去均值。
     x¯i→=x⃗ i−x¯⃗ $\overrightarrow{{\overline{x}}_i}={\overrightarrow{x}}_i-\overrightarrow{\overline{x}}$
   • 对这些减去了均值的点计算它们的协方差矩阵。
     C=1N−1∑Ni=1x¯i→x¯i→T=1N−1∑Ni=1(x⃗ i−x¯⃗ )(x⃗ i−x¯⃗ )T,C∈Rd∗d$C=\frac{1}{N-1}\sum _{i=1}^N\overrightarrow{{\overline{x}}_i}{\overrightarrow{{\overline{x}}_i}}^T=\frac{1}{N-1}\sum _{i=1}^N({\overrightarrow{x}}_i-\overrightarrow{\overline{x}})({\overrightarrow{x}}_i-\overrightarrow{\overline{x}}{)}^T,C\in R^{d\ast d}$
     -找到协方差矩阵C的特征向量。
     CV=VD,V∈Rd∗d,D∈Rd∗d$CV=VD,V\in R^{d\ast d},D\in R^{d\ast d}$
     V-特征向量的矩阵，每一列代表一个特征向量
     D-关于特征值s的对角矩阵
   • 找出最大的k个特征值，解析出对应的k个特征向量，称为提取特征空间eigenspace:
     V^k=V(:,1:k)${\hat{V}}_k=V(:,1:k)$
   • 把每个点投影到特征空间，对每一点给予一个包含k个特征系数的向量。
     aik=V^Tkx¯i→,aik∈Rk$a_{ik}={\hat{V}}_k^T\overrightarrow{{\overline{x}}_i},a_{ik}\in R^k$
     ai=VTx¯i→,ai∈Rd$a_i=V^T\overrightarrow{{\overline{x}}_i},a_i\in R^d$
     因为V是正交的，所以：
     x¯i→=Vai=V(:,1)ai(1)+V(:,2)ai(2)+...+V(:,d)ai(d)$\overrightarrow{{\overline{x}}_i}=V{a}_i=V(:,1)a_i(1)+V(:,2)a_i(2)+...+V(:,d)a_i(d)$
     ≈V^kaik=V^k(:,1)aik(1)+V^k(:,2)aik(2)+...+V^k(:,k)aik(k)$\approx {\hat{V}}_k{a}_{ik}={\hat{V}}_k(:,1)a_{ik}(1)+{\hat{V}}_k(:,2)a_{ik}(2)+...+{\hat{V}}_k(:,k)a_{ik}(k)$
     我们用k个最大特征值对应的特征向量的线性组合来表示每一张人脸,形成由k个最大的d维特征向量表示的人脸库。

直接应用的问题

如果d过大的话，直接求特征向量会因为内存不足导致无法计算。在我们的实验中，因为d相对来说比较大（112*92=10304），所以直接算的话matlab是无法得出最终结果的，所以只能采取近似的算法。
在我们的实验中，N是远远小于d的，即训练集的大小远远小于图像的大小，这也是人脸识别中的多数情况。在这种情况下，C的秩最多是N-1，所以C会有最多N-1个非零的特征值。
我们能把C表示成以下的方式：
C=1N−1∑Ni=1x¯i→x¯i→T∝X⃗ X⃗ T$C=\frac{1}{N-1}\sum _{i=1}^N\overrightarrow{{\overline{x}}_i}{\overrightarrow{{\overline{x}}_i}}^T\propto \overrightarrow{X}{\overrightarrow{X}}^T$,where,
X⃗ =[x¯1→|x¯2→|...|x¯N→]∈Rd∗N$\overrightarrow{X}=[\overrightarrow{{\overline{x}}_1}|\overrightarrow{{\overline{x}}_2}|...|\overrightarrow{{\overline{x}}_N}]\in R^{d\ast N}$
而由下列的式子有：
XTXw⃗ =λw⃗ ,w⃗ ∈RN$X^{T}X\overrightarrow{w}=\lambda \overrightarrow{w},\overrightarrow{w}\in R^N$
XXT(Xw⃗ )=λ(Xw⃗ )$X{X}^T(X\overrightarrow{w})=\lambda (X\overrightarrow{w})$
Xw⃗ $X\overrightarrow{w}$是C=XXT$C=X{X}^T$的特征向量。直接算C的特征向量复杂度为O(d3)$O(d^3)$,而现在的总复杂度可降为O(N3+dN2)$O(N^3+d{N}^2)$。
所以PCA算法的步骤更改为：

1. 计算给定点的均值。

   x¯⃗ =1N∑Ni=1x⃗ i,x⃗ i∈Rd,x¯⃗ ∈Rd$\overrightarrow{\overline{x}}=\frac{1}{N}\sum _{i=1}^N{\overrightarrow{x}}_i,{\overrightarrow{x}}_i\in R^d,\overrightarrow{\overline{x}}\in R^d$

2. 在每一点减去均值。
   x¯i→=x⃗ i−x¯⃗ $\overrightarrow{{\overline{x}}_i}={\overrightarrow{x}}_i-\overrightarrow{\overline{x}}$

3. 对这些减去了均值的点计算下面的矩阵。
   L=X⃗ TX⃗ ,L∈RN∗N,X⃗ =[x¯1→|x¯2→|...|x¯N→]∈Rd∗N$L={\overrightarrow{X}}^T\overrightarrow{X},L\in R^{N\ast N},\overrightarrow{X}=[\overrightarrow{{\overline{x}}_1}|\overrightarrow{{\overline{x}}_2}|...|\overrightarrow{{\overline{x}}_N}]\in R^{d\ast N}$
4. 找到矩阵L的特征向量。
   LW=WD,$LW=WD,$
   W-特征向量的矩阵，每一列代表一个特征向量
   D-关于特征值s的对角矩阵
5. 找出最大的k个特征值，解析出对应的k个特征向量，称为提取特征空间eigenspace:
   V^k=V(:,1:k)${\hat{V}}_k=V(:,1:k)$
6. 从L的特征向量得到C的特征向量
   V=XW,X∈Rd∗N,W∈RN∗N,V∈Rd∗N$V=XW,X\in R^{d\ast N},W\in R^{N\ast N},V\in R^{d\ast N}$

7. 归一化V的列向量

8. 找出k个最大的特征值以及对应的特征向量，并满足k

Project

训练阶段

• 从第一个人开始，把每个人的10张图像随机抽取7张加入训练集，然后把剩下的三张的序号记录下来。读入图像的时候，先把一张图像读成一个行向量。
• 把所有的训练图像读入到一个矩阵matrix以后，利用matlab自带的mean函数找到每一列的均值，形成一个均值行向量x¯⃗ $\overrightarrow{\overline{x}}$。
• 然后对每一点减去均值得到x¯i→=x⃗ i−x¯⃗ $\overrightarrow{{\overline{x}}_i}={\overrightarrow{x}}_i-\overrightarrow{\overline{x}}$。然后把得到的X$X$作转置操作，使得每一个图像的x¯i→$\overrightarrow{{\overline{x}}_i}$是用一个列向量来表示的。
• 求出矩阵L=XTX$L=X^{T}X$。
• 利用matlab自带函数eigs求出矩阵L前k个最大特征值对应的特征向量矩阵。
• matrix矩阵的协方差矩阵C的前k大特征值对应的特征向量矩阵V可以通过V=XW$V=XW$来求。
• 对矩阵V进行归一化处理。

• 根据aik=V^Tkx¯i→$a_{ik}={\hat{V}}_k^T\overrightarrow{{\overline{x}}_i}$算出所有的特征系数

  测试阶段

• 根据训练阶段记录下来的测试图像的序号，把测试图像读入进矩阵中，每一个行向量代表一张图像。

• 然后对每一点减去均值得到z¯p→=z⃗ p−x¯⃗ $\overrightarrow{{\overline{z}}_p}={\overrightarrow{z}}_p-\overrightarrow{\overline{x}}$。然后对该行向量作转置操作。
• 然后利用ap=V^Tkz¯p→$a_p={\hat{V}}_k^T\overrightarrow{{\overline{z}}_p}$算出该测试图像的特征系数ap$a_p$。
• 对数据库所有的特征系数aik$a_{ik}$,计算与ap$a_p$的残差，利用二范数算出，计算二范数利用matlab自带函数norm。

k的测试

对k的测试，从50到100，每一个k进行10遍随机测试。然后把结果写入到Excel文件中，找出成功率最大的k。从记录下来的’testdata.xlsx’中看出，k为95时成功匹配率最高。所以单独测试k=95时的成功率。

运行函数ShowPicture(k)可以得到所有的400张图像借助均值、特征系数、特征向量等恢复后得到的图像，在文件夹image中保存有k=95时，400张eigenfaces。
如下图所示：

但是，因为有随机性和现在测试次数有限的影响，并不能很好地代表不同k值的效果，成功率仍然存在一定的波动。