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

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

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

Abstract：Featureextractionisoneofthehottopicsinthefieldofpatternrecognition.Tosolvetheproblemoffeatureextractioninfacerecognition，anewalgorithmwhichiscallednearestneighborlinenonparametricdiscriminatinganalysis（NNL?NDA）algorithmisproposed.Itisbasedonthealgorithmofdistributednonparametricmaximumspacingcriteria，accordingtonearestneighborlineideaandincomparisonwithpointtolinedistance.Thevalidityofthealgorithmisverifiedbyrecognitioninfacedatabase.

Keywords：featureextraction；NNL?NDA；algorithm；facerecognition

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

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

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

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

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

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

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

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

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

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

式中：[SCi]表示[Ci]的散布度量的值。在實(shí)際使用時(shí)，用[trSi]來(lái)代替[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）的后半部分可以簡(jiǎn)化成如下形式：

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

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

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

將公式（6）展開(kāi)并加入如下公式：

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

可推出與公式（6）等價(jià)的一個(gè)公式：[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）

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

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

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

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

對(duì)于一個(gè)樣本[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）

因此，找出每個(gè)點(diǎn)的類間最近點(diǎn)和類內(nèi)最遠(yuǎn)點(diǎn)，以此來(lái)計(jì)算每個(gè)樣本點(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）

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

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

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

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

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

假設(shè)樣本在進(jìn)行特征提取后可以得到[d]維空間的特征向量，可以得出一個(gè)轉(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）

在這個(gè)優(yōu)化過(guò)程中，致力于找到這樣的樣本，使其并非在原始樣本空間而是在投影空間上，使得類間距離最大，而類內(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）可以寫(xiě)為：

[W=argmaxWtrWTSb-SwW]（22）

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

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

3.1最近鄰線算法（NNL）

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

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

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

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

[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=argminidx，xN1ixN2i]（29）

3.2算法的實(shí)現(xiàn)

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

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

[ΔE=x-pE]（30）

[ΔI=x-pI]（31）

式中：[pE]是通過(guò)最近鄰線思想取得的點(diǎn)，這個(gè)途徑是從不同于樣本[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，]可以計(jì)算得到相應(yīng)的投影矩陣。

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

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

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

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

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

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

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

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

4實(shí)驗(yàn)與分析

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

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

5結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

[3]CHENGYQ，ZHUANGYM，YANGJY.Optimalfisherdiscriminantanalysisusingtherankdecomposition[J].PatternRecognition，1992，25（1）：101?111.

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

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

[6]CHERKASSKYV，MULIERF.Learning