人臉識(shí)別經(jīng)典算法三：Fisherface（LDA） - 全文

Fisherface是由Ronald Fisher發(fā)明的，想必這就是Fisherface名字由來(lái)。Fisherface所基于的LDA（Linear Discriminant Analysis，線性判別分析）理論和特征臉里用到的PCA有相似之處，都是對(duì)原有數(shù)據(jù)進(jìn)行整體降維映射到低維空間的方法，LDA和PCA都是從數(shù)據(jù)整體入手而不同于LBP提取局部紋理特征。如果閱讀本文有難度，可以考慮自學(xué)斯坦福公開(kāi)課機(jī)器學(xué)習(xí)或者補(bǔ)充線代等數(shù)學(xué)知識(shí)。

同時(shí)作者要感謝cnblogs上的大牛JerryLead，本篇博文基本摘自他的線性判別分析（Linear Discriminant Analysis）[1]。

1、數(shù)據(jù)集是二類情況

通常情況下，待匹配人臉要和人臉庫(kù)內(nèi)的多張人臉匹配，所以這是一個(gè)多分類的情況。出于簡(jiǎn)單考慮，可以先介紹二類的情況然后拓展到多類。假設(shè)有二維平面上的兩個(gè)點(diǎn)集x（x是包含橫縱坐標(biāo)的二維向量），它們的分布如下圖（1）（分別以藍(lán)點(diǎn)和紅點(diǎn)表示數(shù)據(jù)）：

原有數(shù)據(jù)是散布在平面上的二維數(shù)據(jù)，如果想用一維的量（比如到圓點(diǎn)的距離）來(lái)合理的表示而且區(qū)分開(kāi)這些數(shù)據(jù)，該怎么辦呢？一種有效的方法是找到一個(gè)合適的向量w（和數(shù)據(jù)相同維數(shù)），將數(shù)據(jù)投影到w上（會(huì)得到一個(gè)標(biāo)量，直觀的理解就是投影點(diǎn)到坐標(biāo)原點(diǎn)的距離），根據(jù)投影點(diǎn)來(lái)表示和區(qū)分原有數(shù)據(jù)。以數(shù)學(xué)公式給出投影點(diǎn)到到原點(diǎn)的距離：?y=wTx。圖（1）給出了兩種w方案，w以從原點(diǎn)出發(fā)的直線來(lái)表示，直線上的點(diǎn)是原數(shù)據(jù)的投影點(diǎn)。直觀判斷右側(cè)的w更好些，其上的投影點(diǎn)能夠合理的區(qū)分原有的兩個(gè)數(shù)據(jù)集。但是計(jì)算機(jī)不知道這些，所以必須要有確定的方法來(lái)計(jì)算這個(gè)w。

首先計(jì)算每類數(shù)據(jù)的均值（中心點(diǎn)）：

這里的i是數(shù)據(jù)的分類個(gè)數(shù)，Ni代表某個(gè)分類下的數(shù)據(jù)點(diǎn)數(shù)，比如u1代表紅點(diǎn)的中心，u2代表藍(lán)點(diǎn)的中心。

數(shù)據(jù)點(diǎn)投影到w上的中心為：

如何判斷向量w最佳呢，可以從兩方面考慮：1、不同的分類得到的投影點(diǎn)要盡量分開(kāi)；2、同一個(gè)分類投影后得到的點(diǎn)要盡量聚合。從這兩方面考慮，可以定義如下公式：

J(w)代表不同分類投影中心的距離，它的值越大越好。

上式稱之為散列值（scatter matrixs），代表同一個(gè)分類投影后的散列值，也就是投影點(diǎn)的聚合度，它的值越小代表投影點(diǎn)越聚合。

結(jié)合兩個(gè)公式，第一個(gè)公式做分子另一個(gè)做分母：

上式是w的函數(shù)，值越大w降維性能越好，所以下面的問(wèn)題就是求解使上式取最大值的w。

把散列函數(shù)展開(kāi)：

可以發(fā)現(xiàn)除w和w^T外，剩余部分可以定義為：

其實(shí)這就是原數(shù)據(jù)的散列矩陣了，對(duì)不對(duì)。對(duì)于固定的數(shù)據(jù)集來(lái)說(shuō)，它的散列矩陣也是確定的。

另外定義：

Sw稱為Within-class scatter matrix。

回到

展開(kāi)J(w)的分子并定義SB，SB稱為Between-class scatter。

這樣就得到了J(w)的最終表示：

上式求極大值可以利用拉格朗日乘數(shù)法，不過(guò)需要限定一下分母的值，否則分子分母都變，怎么確定最好的w呢?？梢粤?p align="center">

其中w是矩陣，所以求導(dǎo)時(shí)可以把

上式兩邊同乘以

可以發(fā)現(xiàn)w其實(shí)就是矩陣

通過(guò)上式求解w還是有些困難的，而且w會(huì)有多個(gè)解，考慮下式：

將其帶入下式：

其中λw是以w為變量的數(shù)值，因?yàn)?u1-u2)^T和w是相同維數(shù)的，前者是行向量后者列向量。繼續(xù)帶入以前的公式：

由于w擴(kuò)大縮小任何倍不影響結(jié)果，所以可以約去兩遍的未知常數(shù)λ和λw（存疑）：

到這里，w就能夠比較簡(jiǎn)單的求解了。

2、數(shù)據(jù)集是多類的情況

這部分是本博文的核心。假設(shè)有C個(gè)人的人臉圖像，每個(gè)人可以有多張圖像，所以按人來(lái)分，可以將圖像分為C類，這節(jié)就是要解決如何判別這C個(gè)類的問(wèn)題。判別之前需要先處理下圖像，將每張圖像按照逐行逐列的形式獲取像素組成一個(gè)向量，和第一節(jié)類似設(shè)該向量為x，設(shè)向量維數(shù)為n，設(shè)x為列向量（n行1列）。

和第一節(jié)簡(jiǎn)單的二維數(shù)據(jù)分類不同，這里的n有可能成千上萬(wàn)，比如100x100的圖像得到的向量為10000維，所以第一節(jié)里將x投影到一個(gè)向量的方法可能不適用了，比如下圖：

圖（2）

平面內(nèi)找不到一個(gè)合適的向量，能夠?qū)⑺械臄?shù)據(jù)投影到這個(gè)向量而且不同類間合理的分開(kāi)。所以我們需要增加投影向量w的個(gè)數(shù)（當(dāng)然每個(gè)向量維數(shù)和數(shù)據(jù)是相同的，不然怎么投影呢），設(shè)w為：

w1、w2等是n維的列向量，所以w是個(gè)n行k列的矩陣，這里的k其實(shí)可以按照需要隨意選取，只要能合理表征原數(shù)據(jù)就好。x在w上的投影可以表示為：

所以這里的y是k維的列向量。

像上一節(jié)一樣，我們將從投影后的類間散列度和類內(nèi)散列度來(lái)考慮最優(yōu)的w，考慮圖（2）中二維數(shù)據(jù)分為三個(gè)類別的情況。與第一節(jié)類似，μi依然代表類別i的中心，而Sw定義如下：

其中：

代表類別i的類內(nèi)散列度，它是一個(gè)nxn的矩陣。

所有x的中心μ定義為：

類間散列度定義和上一節(jié)有較大不同：

代表的是每個(gè)類別到μ距離的加和，注意Ni代表類別i內(nèi)x的個(gè)數(shù)，也就是某個(gè)人的人臉圖像個(gè)數(shù)。

上面的討論都是投影之間的各種數(shù)據(jù)，而J(w)的計(jì)算實(shí)際是依靠投影之后數(shù)據(jù)分布的，所以有：

分別代表投影后的類別i的中心，所有數(shù)據(jù)的中心，類內(nèi)散列矩陣，類間散列矩陣。與上節(jié)類似J(w)可以定義為：

回想我們上節(jié)的公式J(w)，分子是兩類中心距，分母是每個(gè)類自己的散列度?，F(xiàn)在投影方向是多維了（好幾條直線），分子需要做一些改變，我們不是求兩兩樣本中心距之和（這個(gè)對(duì)描述類別間的分散程度沒(méi)有用），而是求每類中心相對(duì)于全樣本中心的散列度之和。得到：

最后化為：

還是求解矩陣的特征向量，然后根據(jù)需求取前k個(gè)特征值最大的特征向量。

另外還需注意：

由于SB中的（μi-μ）秩為1，所以SB的至多為C（矩陣的秩小于等于各個(gè)相加矩陣的和）。又因?yàn)橹懒饲癈-1個(gè)μi后，最后一個(gè)μc可以用前面的μi來(lái)線性表示，因此SB的秩至多為C-1，所以矩陣的特征向量個(gè)數(shù)至多為C-1。因?yàn)镃是數(shù)據(jù)集的類別，所以假設(shè)有N個(gè)人的照片，那么至多可以取到N-1個(gè)特征向量來(lái)表征原數(shù)據(jù)。（存疑）

如果你讀過(guò)前面的一篇文章PCA理論分析，會(huì)知道PCA里求得的特征向量都是正交的，但是這里的

如前所述，如果在一個(gè)人臉集合上求得k個(gè)特征向量，還原為人臉圖像的話就像下面這樣：

得到了k個(gè)特征向量，如何匹配某人臉和數(shù)據(jù)庫(kù)內(nèi)人臉是否相似呢，方法是將這個(gè)人臉在k個(gè)特征向量上做投影，得到k維的列向量或者行向量，然后和已有的投影求得歐式距離，根據(jù)閾值來(lái)判斷是否匹配。具體的方法在人臉識(shí)別經(jīng)典算法一：特征臉?lè)椒ǎ‥igenface）里有，可前往查看。需要說(shuō)明的是，LDA和PCA兩種方法對(duì)光照都是比較敏感的，如果你用光照均勻的圖像作為依據(jù)去判別非均勻的，那基本就慘了。

參考文獻(xiàn)：

[1]Jerry Lead 線性判別分析（Linear Discriminant Analysis）（一）