基于多級分類的大類別人臉識別研究

 收稿日期：2007-09-11；

修回日期：2008-01-02

基金項目：國家自然科學基金資助項目(60503026)



作者簡介：張生亮(1964-)，男，山西文水人，博士，主要研究方向為模式識別、圖像處理（ZSL-1964@126.com）；

楊靜宇(1941-)，男，教授，博導，主要研究方向為模式識別、機器視覺、智能系統.

(1.山西財經大學 應用數學系， 太原 030006； 2.南京理工大學 計算機學院， 南京 210094)

摘要：

提出了一種新的多級分類的人臉識別算法。在類別數較大的人臉識別系統中，要想用一種特征一次性地把所有類別都分開是不現實的。首先使用快速的二維投影在大范圍內找出測試樣本的若干候選類別，然后對不同的測試樣本分別在其候選子集中抽取特征，進而判斷測試樣本屬于哪個類別。在200人的人臉庫上進行了實驗，識別率由71.23%提高到83.75%。

關鍵詞：人臉識別; 特征抽取; 多級分類; 組合鑒別

中圖分類號：TP391.4

文獻標志碼：A

文章編號：1001-3695(2008)10-3069-03

Large scale face recognition based on multilevel classification

ZHANG Sheng-liang1， 2， YANG Jing-yu2

(1.Dept.of Application Mathematics， Shanxi University of Finance Economics， Taiyuan 030006， China;

2.College of Computer Science， Nanjing University of Science Technology， Nanjing 210094， China)

Abstract:

This paper presented a novel multilevel classification method. In practical face recognition system， the number of the classes is usually large. It caused the correct recognition rate not satisfied if only using one features classified the all probe samples one times. First， marked 20 candidate classes for each probe sample by a two dimensional projection approach. Se-cond， for each probe sample， employed 20 class’s candidate training samples to calculate the optimal discriminant vectors， then projected the probe sample and the candidate samples into the vectors and classified the probe sample. The proposed algorithm was evaluated by a 200 persons FERET face database. For elimination the illumination change， adjusted every image’s mean and standard deviation to 0.5 and 0.15 respectively. The 10 times experiments average accurate rate directly using combined discriminant analysis is 71.23%， while the average rate of multilevel classification is 83.75%.

Key words：face recognition; feature extraction; multilevel classification; combined discriminant analysis

大型的人臉數據庫，類別數可能達幾千人，訓練樣本上萬幅。例如文獻[1]所介紹的人臉庫就包含了1 040人的99 450幅圖像。對較大的人臉識別系統，如果指望用某個特征一次性地對待識樣本進行正確分類是不現實的。從模式識別的角度考慮，類別數越大，識別的困難程度和系統的復雜性就越大。許多特征提取方法的鑒別能力會隨著類別數目的增加而下降。對幾十個人有效的算法，對幾百人甚至幾千人的識別問題常常不再有效。

根據人的經驗，如果在大范圍內搜索自己要找的人，總是先尋找那些相似的候選人員，很快地排除那些差異較大的人，然后在這些候選類別中再仔細辨認，從而確定目標，這就是所謂的多級分類。具體地講就是在大范圍內挑出與測試樣本最相似的一些類別作為候選子集，然后進一步分類、識別。多級分類的第一階段應當采用高可靠性和計算量小的快速算法，將明顯差異大的對象盡可能多地去除，為進一步識別提供一個相對小的候選子集。第二階段在劃定的小范圍內，應用對小類別有效的鑒別方法進行分類，這樣有利于提高識別的正確率。

在大類別人臉識別的第一階段，本文先用二維投影算法(如二維主分量分析，即2DPCA[2~4])查找測試樣本相近的k（如20）候選類別；然后對每個測試樣本用組合鑒別分析方法[3]在其20個候選的類別中計算最佳鑒別矢量集；抽取特征后，判別測試樣本屬于哪個類別。在FERET人臉庫上的實驗表明，經過篩選后的組合鑒別分析方法識別率提高12.53%，速度也能滿足實時性的要求。

1候選類別的選擇

特征抽取的本質是降維過程，在降維的同時保持模式的分類信息沒有大的損失。常用的基于向量的特征抽取方法有PCA、LDA、Fisherfaces、KPCA[5，6]等。在模式是人臉圖像時，圖像轉換為向量后維數一般很高，這些基于向量的特征抽取方法會遇到計算和存儲方面的考驗。在訓練樣本數較少時，常用的減少計算量的方法是使用奇異值分解定理，將計算矩陣RRT的本征值本征向量問題轉換為求解矩陣RTR的問題。這在人臉類別數較少時是可行的。但如果訓練樣本數也很多時，計算量太大使得現在的計算機無法計算。Yang Jian等人[2，3]提出了二維投影的分析方法，計算量小、速度快捷，為在大范圍內尋找測試樣本的候選類別提供了有力的工具。

二維主分量分析(2DPCA)[3，4] 無須將圖像轉換為向量，而是直接進行圖像投影。圖像投影就是將m×n的圖像矩陣A，通過Y=AX的線性變換直接投影到n維列向量X上，得到一個m維列向量Y， 稱為圖像A的投影特征向量。X的選取準則是使得投影后的特征Y具有更好的可分性。類似于PCA，2DPCA的鑒別矢量集取為圖像總體散布矩陣Gt的d個最大本征值對應的本征向量。設模式類別有C個，即ω1，ω2，…，ωC，相應地第i類有樣本ni個，每個樣本是m×n矩陣，可得到圖像總體散布矩陣Gt、圖像類內散布矩陣Gw和圖像類間散布矩陣Gb：

其中：P(ωi)為第i類模式的先驗概率，一般取為P(ωi)=ni/N；i為第i類模式的均值向量矩陣（i=1，2，…，C）;為模式總體的均值矩陣。

2DPCA[4]取Gb最大的d個本征值對應的標準正交本征向量為最優投影軸進行投影，抽取特征，一般可取得比用Gt更好的識別率。Gt的計算與訓練樣本的總數N有關，而Gb的計算與類別數C有關，Gb的計算量Gt稍小些。

將LDA推廣到二維得到2DLDA[7]。本文通過計算G-1tGb的d個最大本征值對應的本征向量作為投影軸，提取人臉的2DLDA特征。特征抽取方法如下：

設最優圖像投影軸為X1，…，Xd，令Yk=(A-)Xk（k=1，2，…，d），則得到一組圖像投影特征向量Y1，…，Yd，將它們合并，作為圖像A的投影特征矩陣Y=[Y1，…，Yd]，用于分類識別。

假設C類圖像的均值矩陣i(i=1，2，…，C)按照上面的方法投影后的特征矩陣為Wi(i=1，…，C)，測試樣本A投影后的特征矩陣記為B。B與各類中心的距離定義為

Hi=‖B-Wi‖F(5)

將Hi(i=1，2，…，C)按從小到大次序排列，取前k(如取k=20)個類別為與測試樣本A最相似的k個類別，也即用二維投影篩選出的測試樣本A的候選類別。

對特別大的系統，將其按一定的規模(如200人)劃分為s個子集，對每個測試樣本在每個子集分別查找k個候選類別。將這些最近的類別合在一起，構成一個k×s的訓練樣本集，再進行相應的篩選，直到找到一個相對較小的候選子集。

2在候選子集中的識別算法

在模式識別中，如果訓練樣本的數量大大低于樣本的維數，可以認為是小樣本下的分類問題。進一步，如果樣本維數很高，那么就是高維小樣本識別問題。過去受計算機處理能力的限制，研究人臉識別多是對人數較少的人臉庫進行的，已取得了一些有效的算法。雖然人臉識別不是一個高維小樣本問題，但經過之前的處理，找出候選子集后就可以認為是高維小樣本問題。本文用基于Fisher準則的組合鑒別分析方法[5]抽取高維小樣本情況下的鑒別特征。

設有一含N個樣本的集合F，F中每一樣本X為n維向量，設模式類別有c個：ω1，ω2，…，ωc，ωi類有樣本 ni個，Xij表示ωi類的第j個樣本，它們的總體散布矩陣St、類內散布矩陣Sw及類間散布矩陣Sb分別定義如下：

一般取P(ωi)=ni/N為第i類訓練樣本的先驗概率，mi為第i類訓練樣本的均值，m0為全體訓練樣本的均值。Sw、Sb、St都是對稱非負定矩陣。

對于Sw可逆的情況，可以直接求取廣義本征方程Sbφ=λSwφ的d個最大本征值對應的本征向量φ1，φ2，…，φd作為鑒別矢量集。

對高維小樣本的情況，Sw總是奇異的。對Fisher準則而言，總體散度為零的空間沒有鑒別信息，組合鑒別分析的第一步就是用PCA去掉St的零空間，將向量樣本壓縮到St的非零空間。后續分析都在一個維數相對較低的空間中進行。

設β1，β2，…，βn表示St的標準正交本征矢量，則Rn=span{β1，定義1Rn的子空間Φt=span{β1，β2，…，βm}，其正交補空間為Φ⊥t=span{βm+1，…，βn}。 其中:m=rank(St)；β1，…，βm為St的非零本征值所對應的標準正交的本征向量。那么Φt為矩陣St的非零空間，Φ⊥t為矩陣St的零空間。

記P=(β1，β2，…，βm)，對n維向量X通過投影變換Y=PTX得到m維的訓練樣本集。經投影降維后的新樣本散布矩陣為S~b=PTSbP，S~t=PTStP，S~w=PTSwP。就Fisher準則而言，最優鑒別矢量集可在Rn的子空間Φt內選取，不損失任何最優鑒別信息，證明參見文獻[3]。

設γ1，…，γm為S~w的標準正交本征矢量，則Rm=span{γ1，…，γm}。定義2Rm的子空間Φ~w=span{γ1，…，γq}。其中：γ1，…，γq為S~w的非零本征值所對應的標準正交本征向量；q=rankS~w。Φ~w的正交補空間為Φ~⊥w=span{γq+1，…，γm}。

在此引用文獻[5]的兩個定理和推論。

定理1在空間Rm內，若X≠0，則XTS~wX=0，當且僅當X∈Φ~⊥w。推論在空間Rm內，對任一X≠0且X∈Φ~w，有XTS~wX≠0。

定理2任意X∈Φ~⊥w且X≠0，有XTS~bX>0恒成立。

m維空間的組合鑒別矢量集是類內散布矩陣S~w的零空間Φ~⊥w和非零空間Φ~w中鑒別矢量集的組合。第一類是滿足條件XTS~wX=0和XTS~bX>0，用準則J~b(Y)=YTS~bY求取鑒別矢量集，各鑒別矢量間正交；第二類滿足條件XTS~wX>0和XTS~bX>0，用準則J~(Y)=YTS~bY/（YTS~wY）求取鑒別矢量集。將兩類鑒別矢量集合在一起構成總的組合鑒別矢量集。由于rankS~b一般為類別數C減1，組合鑒別矢量集最多可取2C-2個。

3光照強弱的標準化方法

直方圖均衡化是消除光照強弱影響的常用方法。但直方圖均衡化后圖像不自然，對比度大，不符合人的視覺要求，相應的識別性能也不好。由于一幅圖像所有像素的均值反映的是圖像的亮度，而灰度值的方差反映的是圖像的對比度。如圖1所示，如果規定灰度圖像的均值取0.5，方差取0.15，圖像將基本消除光照強弱的影響。

一幅圖像為f(m，n)，m=1~M，n=1~N，圖像所有像素灰度的均值和方差新圖像fnew分別為

4在FERET人臉庫上的實驗

實驗是在FERET人臉庫[8]的子庫上進行的。該子庫包含200個人的1 400幅圖像(每人7幅)，這些圖像的文件名均包含了標志字符串“ba”“bj”“bk”“be”“bf”“bd”“bg”。這些字符串標志了每幅圖像的變化情形，如姿態、表情、光照等。“bj”是表情變化，“bk”是光照變化，“bd”“be”“bf”“bg”包含了姿態的變化(±15° and ±25°)。在本實驗使用已經裁剪好的80×80的圖像。圖2為FERET人臉庫中某人的7幅圖像。

為了減少計算量，將相鄰的四個像素灰度平均后合成一個像素，使樣本都成為40×40的圖像。許多實驗表明，將人臉圖像降低到合適的分辨率后，不但會提高運算速度，也會取得較高的識別率。為了消除光照強弱對識別的影響，用消除光照變化的方法對圖像進行預處理。

實驗取每個人3幅圖像訓練，剩余4幅測試。人臉識別中常顯得每個人的訓練樣本不足。特別是考慮到姿態的變化，如果未包含某一方向的訓練樣本，抽取出特征以后進行特征比對匹配時會產生出許多錯誤的分類。例如，只用向右旋轉人臉圖像訓練，而用向左旋轉后的圖像測試，會增加出錯的概率。由于人臉是基本對稱的，通過增加鏡像圖像[9]作為訓練樣本，對提高有姿態變化的人臉識別效果顯著。將每人的3個訓練樣本作鏡像變換，產生出3個鏡像樣本，與原有的3個訓練樣本一起進行訓練，構成擴大的訓練樣本集。圖像A的鏡像=A×M。其中：M是一個與A的列數相同的方矩陣，且除反對角線上的元素為1外其余元素都為0。這樣共有1 200個訓練樣本， 800個測試樣本。用1，2，…，7分別對應圖像文件含有標志符“ba”“bd”“be”“bf”“bg”“bj”“bk”的樣本，用一個隨機程序生成1~7排列，序列前三個數字對應的是每人的訓練樣本，后四個對應測試樣本。用三種二維投影方法篩選測試樣本的20個候選類別，取6個最佳投影軸，正確率列在表1中。2DPCAGt、2DPCAGb、2DLDA分別為取Gt、Gb及G-1tGb的6個最大本征值對應的本征向量作為投影軸。

表2中“在候選中組合鑒別”是指利用2DPCAGb對每個測試樣本找出20個候選類別后，進行的組合鑒別分析取38個特征進行計算的結果；“在全部類組合鑒別”是指不進行篩選直接進行組合鑒別分析的方法，所選取的特征數為350個。表2中的2DPCAGb指二維投影抽取特征后的首選識別率。

表2在全部類與候選類中識別的正確率對比

訓練樣本在候選中組合鑒別在全部類組合鑒別在全部類2DPCAGb在全部類

5結束語

本文提出了一種針對類別數較多的人臉識別問題的多級分類算法。利用快速的二維投影分析找出測試樣本的若干候選類別，然后對不同的測試樣本在其相應的候選子集中進一步確定其所屬類別。第一步排除了與測試樣本差異較大的大多數類別后，縮小了搜索范圍，也減少了所需抽取特征的數量。在200人的人臉庫上進行了實驗，表2中的數據表明了該方法是有效的。這種多級分類的方法為實際中處理大樣本集的人臉識別系統提供了一種可行的方案。

參考文獻：

[1]張曉華，山世光，曹波. CAS-PEAL大規模中國人臉圖像數據庫及其基本評測介紹[J]. 計算機輔助設計與圖形學學報，2005，17(1):9-17.

[2]YANG Jian， ZHANG D， YANG Jing-yu， et al. Two-dimensional PCA: a new approach to appearance-based face representation and recognition[J]. IEEE PAMI， 2004，26(1):131-137.

[3]LIU Ke， CHENG Yong-qing， YANG Jing-yu， et al. Algebraic feature extraction for image recognition based on an optimal discriminant criterion[J]. Pattern Recognition， 1993，26(6):903-911.

[4]張生亮，陳伏兵，謝永華，等.基于類間散布矩陣的二維主分量分析[J]. 計算機工程， 2006，32(11):44-46.

[5]楊健，楊靜宇，葉暉. Fisher線性鑒別分析的理論研究及其應用[J].自動化學報， 2003，29(4):481-493.

[6]劉青山，盧漢清，馬頌德.綜述人臉識別中的子空間方法[J]. 自動化學報， 2003，29(6):900-911.

[7]LI Ming， YUAN Bao-zong. 2DLDA: a statistical linear discriminant analysis for image matrix[J]. Pattern Recognition Letters， 2005，26(5):527-532.

[8]PHILLIPS P J. The facial recognition technology(FERET) database[EB/OL].(2004).http://www.itl.nist.gov /iad/humanid/feret/feret_master.html.

[9]張生亮，陳伏兵，楊靜宇. 對單訓練樣本的人臉識別問題的研究[J]. 計算機科學， 2006，33(2):225-229.