摘 要： 特征提取是模式識別研究領(lǐng)域的一個熱點(diǎn)問題。為了更好地解決人臉識別中的特征提取問題，在分布的非參數(shù)間距最大準(zhǔn)則算法的基礎(chǔ)上，根據(jù)最近鄰線的算法思想，在點(diǎn)?線距離的基礎(chǔ)上，提出一種新的算法，即最近鄰線非參數(shù)鑒別分析算法，并通過在人臉數(shù)據(jù)庫上的識別，驗證了該算法的有效性。

關(guān)鍵詞： 特征提??； 最近鄰線非參數(shù)鑒別分析； 算法； 人臉識別

中圖分類號： TN702.2?34； TP391.41 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2015）13?0145?04

Abstract： Feature extraction is one of the hot topics in the field of pattern recognition. To solve the problem of feature extraction in face recognition， a new algorithm which is called nearest neighbor line nonparametric discriminating analysis （NNL?NDA） algorithm is proposed. It is based on the algorithm of distributed nonparametric maximum spacing criteria， according to nearest neighbor line idea and in comparison with point to line distance. The validity of the algorithm is verified by recognition in face database.

Keywords： feature extraction； NNL?NDA； algorithm； face recognition

在線性特征提取方法中，通常采用Fisher線性鑒別準(zhǔn)則[1?2]。但做特征提取時Fisher線性鑒別準(zhǔn)則對原始樣本的分布情況提出兩個要求[3]：樣本的分布須是單峰值的；每類樣本均值須不同。但在實際應(yīng)用中很難達(dá)到這兩個要求。因此，F(xiàn)ukunaga等提出了非參數(shù)鑒別分析[4?5]（Nonparametric Discriminant Analysis，NDA）的方法，這個方法將原先的Fisher鑒別準(zhǔn)則法進(jìn)行優(yōu)化，即利用相應(yīng)的散布矩陣差替代相應(yīng)的散布矩陣的比值，不過NDA方法仍受相應(yīng)的散布矩陣奇異的影響。因此，可用分步的非參數(shù)間距最大準(zhǔn)則[6]算法來解決這個問題。根據(jù)最近鄰線思想[7?10]，在點(diǎn)?線距離的基礎(chǔ)上提出了一種新的稱為最近鄰線非參數(shù)鑒別分析[11]的算法，并且通過在ORL人臉庫進(jìn)行實驗識別驗證了此算法的有效性。

1 間距最大準(zhǔn)則（MMC）

MMC準(zhǔn)則的目的是要將原始的高維空間數(shù)據(jù)壓縮到低維空間并且仍然能夠保證較好的可分性。所以，在特征提取的過程中，應(yīng)當(dāng)在變化之后的低維空間內(nèi)保持類間距離的最大化。那么，特征提取的準(zhǔn)則定義如下：

[J=12i=1Cj=1CdCi，Cj] （1）

式（1）表示的是任意兩類之間的距離，可定義其為最大鑒別準(zhǔn)則，MMC的準(zhǔn)則目的就是要使這個[J]值盡可能大。

類與類之間的距離，通過類中心點(diǎn)的距離來度量，即：

[dCi，Cj=dmi，mj] （2）

式中：[mi，][mj]分別代表類別[Ci]和[Cj]的類中心，但是如果簡單就以[dCi，Cj]作為分類依據(jù)，在距離度量中，可能會出現(xiàn)散布矩陣的奇異。所以在出現(xiàn)不同樣本分布混亂或重疊時，這種分類就不可行。

重新對類間距離進(jìn)行定義：

[dCi，Cj=dmi，mj-SCi-SCj] （3）

式中：[SCi]表示[Ci]的散布度量的值。在實際使用時，用[trSi]來代替[SCi]，表示類別[Ci]的散布度量的信息。

將[trSi]代入式（3），得出：

[J=12i=1Cj=1Cdmi，mj-SCi-SCj=12i=1Cj=1Cdmi，mj-trSi-trSj=12i=1Cj=1Cdmi，mj-12i=1Cj=1CtrSi+trSj] （4）

其中式（4）的后半部分可以簡化成如下形式：

[12i=1Cj=1CtrSi+trSj=i=1CtrSi=tri=1CSi=trSw] （5）

對于公式（4）的前半部分，采用歐氏距離，可以得出：

[12i=1Cj=1Cdmi，mj=12i=1Cj=1Cmi-mjTmi-mj =12i=1Cj=1Cmi-m0+m0-mjTmi-m0+m0-mj] （6）

將公式（6）展開并加入如下公式：

[i=1Cm0-mi=0] （7）

可推出與公式（6）等價的一個公式：[12i=1Cj=1Cmi-m0+m0-mjTmi-m0+m0-mj= tri=1Cmi-m0mi-m0T=trSb] （8）

因此，特征提取準(zhǔn)則函數(shù)公式（1）可轉(zhuǎn)化成如下形式：

[J=trSb-trSw=trSb-Sw] （9）

這樣實現(xiàn)了不同類之間的距離最大，同類之間的距離最小，也就是使同類間距離最緊湊。

MMC的方法在一定范圍內(nèi)能有效地解決Fisher方法中產(chǎn)生的問題，但解決類內(nèi)散布矩陣的問題還需要進(jìn)一步探討。Qiu等提出了分步式非參數(shù)間距最大準(zhǔn)則（Stepwise Nonparametric Margin Maximum Criterion， SNMMC）方法。

2 分步式非參數(shù)間距最大準(zhǔn)則（SNMMC）

SNMMC的目的與MMC方法一樣，盡量使類間距離最大而類內(nèi)距離最小。在該算法設(shè)計中，不去具體定義類的中心點(diǎn)，只是考慮某一樣本與它周圍樣本的分布情況，從而來定義相應(yīng)的散布矩陣。算法的思想描述如下：

對于一個樣本[x∈Ci][i=1，2，…，C]，那么定義相應(yīng)的類間最近距離：

[xE=x?Cix-x≤z-x，?z?Ci] （10）

類推，得到類內(nèi)最遠(yuǎn)距離的定義：

[xI=x∈Cix-x≥z-x，?z∈Ci] （11）

因此，找出每個點(diǎn)的類間最近點(diǎn)和類內(nèi)最遠(yuǎn)點(diǎn)，以此來計算每個樣本點(diǎn)[x]的非參數(shù)類間和類內(nèi)差異：

[ΔE=x-xE] （12）

[ΔI=x-xI] （13）

由此，得到新的類間散布矩陣和類內(nèi)散布矩陣定義如下：

[Sb=i=1NωiΔEiΔEiT] （14）

[Sw=i=1NωiΔEiΔEiT] （15）

式中的[ωi]為樣本的權(quán)值，定義如下：

[ωi=ΔIiαΔIiα+ΔEiα] （16）

式中：[α]作為一個控制參數(shù)來使用，取值在0到無窮大之間。這個樣本的取值盡量不靠近樣本中心點(diǎn)。公式（16）的值越大說明樣本離類別的邊界越近，反之值越小說明樣本越靠近類中心。[α]控制其變化的過程。

公式（12）和（13）給出，[ΔEi]表示的是樣本[xi]和不在樣本[xi]類中的最臨近點(diǎn)之間的距離，而[ΔIi]表示的是樣本[xi]和屬于樣本[xi]所在類空間內(nèi)的最遠(yuǎn)點(diǎn)之間的距離。

對于給定樣本[xi，]相應(yīng)的非參數(shù)距離可以表示如下：

[θi=ΔEi2-ΔIi2] （17）

對于一個樣本[xi]而言，相應(yīng)的非參數(shù)距離大小可以去估計分類的準(zhǔn)確性。即非參數(shù)距離值越小，樣本分類的正確性越低，反之，值越大其正確率越高。

假設(shè)樣本在進(jìn)行特征提取后可以得到[d]維空間的特征向量，可以得出一個轉(zhuǎn)換矩陣[W]（[n×d]），由此得出投影矩陣[xnew=WTx。]投影之后的非參數(shù)類間和類內(nèi)差異分別是：

[δE=WTΔE] （18）

[δI=WTΔI] （19）

其目的是使得非參數(shù)距離[δEi2-δIi2]越大越好。

[W=argmaxWi=1NωiδEi2-δIi2] （20）

在這個優(yōu)化過程中，致力于找到這樣的樣本，使其并非在原始樣本空間而是在投影空間上，使得類間距離最大，而類內(nèi)距離最小。

基于這樣的考慮，有：

[i=1NωiδEi2-δIi2=i=1NωiWTΔEiTWTΔEi-i=1NωiWTΔIiTWTΔIi=tri=1NωiWTΔEiWTΔEiT-tri=1NωiWTΔIiWTΔIiT=trWTi=1NωiΔEiΔEiTW-trWTi=1NωiΔIiΔIiTW=trWTSbW-trWTSwW=trWTSb-SwW]（21）

式中：[tr?]代表矩陣的秩；[Sb]和[Sw]分別代表矩陣的非參數(shù)類間散布矩陣和矩陣的類內(nèi)散布矩陣。

因此，公式（20）可以寫為：

[W=argmaxWtrWTSb-SwW] （22）

公式（22）被稱為非參數(shù)最大間距準(zhǔn)則。

3 最近鄰線非參數(shù)鑒別分析（NNL?NDA）

3.1 最近鄰線算法（NNL）

最近鄰線的定義：假設(shè)[xN1i] 和[xN2i]是樣本[x]在第[i]類中的兩個最近的鄰點(diǎn)，那么樣本[x]在第[i]類中的最近鄰線就用這兩個點(diǎn)構(gòu)成的直線[xN1ixN2i]來表示。那么最近鄰線距離就是點(diǎn)[x]到最近鄰線[xN1ixN2i]的距離，其定義如下：

[dx，xN1ixN2i=x-piN1N2] （23）

式中樣本[x]在最近鄰線[xN1ixN2i]上的投影點(diǎn)表示為[piN1N2]。

投影點(diǎn)[piN1N2]的計算如下：

[piN1N2=t1ixN1i+t2ixN2i] （24）

其中：

[t1i+t2i=1] （25）

根據(jù)LLE算法能得到：

[tji=kC-1jklmC-1lm] （26）

其中：

[C=Clml=1，2；m=1，2] （27）

[Cjk=x-xNjiTx-xNkj] （28）

其中最近鄰線的定義為：

[xN1nearxN2near=argmini dx，xN1ixN2i] （29）

3.2 算法的實現(xiàn)

在本文的方法中，NNL算法可以用來對距離進(jìn)行度量計算。這里可以通過相應(yīng)的非參類間和類內(nèi)距離來實現(xiàn)相關(guān)的散布矩陣。

算法中使用的非參類間和類內(nèi)差異進(jìn)行重新定義：

[ΔE=x-pE] （30）

[ΔI=x-pI] （31）

式中：[pE]是通過最近鄰線思想取得的點(diǎn)，這個途徑是從不同于樣本[x]所屬的類別[Ck]中獲得；[pI]則與[pE]相反，是由[xN1far，][xN2far]得到的點(diǎn)。

由此可以定義新的非參類間：

[Sb=i=1MωiΔEiΔEiT] （32）

定義新的類內(nèi)散布矩陣：

[Sw=i=1MωiΔIiΔIiT] （33）

根據(jù)以下定義的函數(shù)：

[WNNL-NDA=argmaxtrWWTSb-SwW] （34）

式中限定[WTW=I，]可以計算得到相應(yīng)的投影矩陣。

由此，可以將NNL?NDA算法描述如下：

通過[T]次變換后得到一個轉(zhuǎn)換矩陣[W]。假設(shè)，在經(jīng)過[t]步轉(zhuǎn)換之后得到[dt]維的數(shù)據(jù)，得到的維數(shù)應(yīng)滿足[dt-1>dt>dt+1]，其中[d0=D]，[dT=d]。[D]和[d]分別代表了圖像的原始維數(shù)和要經(jīng)過轉(zhuǎn)換后需要得到的維數(shù)。

假定循環(huán)次數(shù)為[T]，算法描述如下：

（1） 根據(jù)最近鄰線的思想得出每一個樣本的[pE]和[pI]值；

（2） 根據(jù)公式（32）和（33）計算得出在[dt-1]維下的類間散布矩陣和類內(nèi)散布矩陣；

（3） 根據(jù)公式（34）計算得到在[dt-1]維下的轉(zhuǎn)換矩陣[Wt]，其中的[Wt]是一個[dt-1×dt]的矩陣；

（4） 進(jìn)行投影矩陣的映射，得到新維數(shù)下的樣本矩陣[x=WTtx]。

令[W=t=1TWt，]可以構(gòu)成最終的變換矩陣。

4 實驗與分析

實驗在ORL人臉數(shù)據(jù)庫上進(jìn)行。訓(xùn)練樣本集的產(chǎn)生是從樣本庫中隨機(jī)挑選每個類別中的9個人臉來進(jìn)行，這樣，訓(xùn)練樣本集的人臉的個數(shù)就是40×9，測試樣本集就是從余下的人臉數(shù)據(jù)產(chǎn)生，針對不同的訓(xùn)練樣本數(shù)，均進(jìn)行10次不相同的實驗。其結(jié)果見表1，表2。

表1和表2分別顯示了NNL?NDA與其他經(jīng)典的人臉識別算法在ORL人臉數(shù)據(jù)庫上的識別性能的比較；圖1和圖2分別顯示了在類別數(shù)目不同的情況下采用不同的分類器方法得到的識別率。

5 結(jié) 語

本文在最近鄰線思想的基礎(chǔ)上，提出了一種新的特征提取方法——NNL?NDA方法。在新方法中，特征提取的過程運(yùn)用NNL的思想理論將樣本的結(jié)構(gòu)信息融入其中，通過在ORL人臉數(shù)據(jù)庫中的實驗，很好地驗證了該算法的有效性。

參考文獻(xiàn)

[1] 戴文戰(zhàn)，周昌亮.一種改進(jìn)Fisher準(zhǔn)則的線性鑒別分析方法[J].計算機(jī)工程與應(yīng)用，2013（3）：210?212.

[2] 崔法毅.改進(jìn)的Fisher鑒別分析兩步算法研究及其在人臉識別中的應(yīng)用[D].秦皇島：燕山大學(xué)，2012.

[3] CHENG Y Q， ZHUANG Y M， YANG J Y. Optimal fisher discriminant analysis using the rank decomposition [J]. Pattern Recognition， 1992， 25（1）： 101?111.

[4] 曹林，陳登.基于小波近似分量非參數(shù)鑒別分析人臉識別算法[J].北京信息科技大學(xué)學(xué)報：自然科學(xué)版，2011（6）：20?23.

[5] 薛寺中，戴飛，陳秀宏.一種非參數(shù)核函數(shù)鑒別分析法及其在人臉識別中的應(yīng)用[J].計算機(jī)科學(xué)，2012（6）：507?518.

[6] CHERKASSKY V， MULIER F. Learning from data： concepts， theory and methods [M]. New York：John Viley Sons， 1997.

[7] 仲媛.最近鄰分類的若干改進(jìn)算法研究[D].南京：南京理工大學(xué)，2012.

[8] VICKERS A J. Parametric versus non?parametric statistics in the analysis of randomized trials with non?normally distributed data [J]. BMC Medical Research Methodology， 2005， 5（1）： 1?12.

[9] 金忠，楊靜宇，陸建峰.一種具有統(tǒng)計不相關(guān)性的最優(yōu)鑒別矢量集[J].計算機(jī)學(xué)報，1999，22（10）：1105?1108.

[10]BELHUMEUR P N， HESPANHA J P， KRIEGMAN D J. Eigenfaces vs. fisherfaces： recognition using class specific linear projection [C]// 1996 the 4th European Conference on Computer Vision Cambridge. UK： ECCV， 1996， 19（7）： 711?720.

[11] 鄭宇杰.特征提取方法及其應(yīng)用研究[D].南京：南京理工大學(xué)，1996.