基于多尺度稀疏近鄰圖的近鄰保持嵌入算法*

于 露

(長(zhǎng)春財(cái)經(jīng)學(xué)院 信息工程學(xué)院， 長(zhǎng)春 130122)

人臉識(shí)別技術(shù)在自動(dòng)控制領(lǐng)域具有廣泛的應(yīng)用.鄒香玲[1]將人臉識(shí)別技術(shù)應(yīng)用在智能監(jiān)控系統(tǒng)中，并利用云計(jì)算對(duì)大規(guī)模認(rèn)證系統(tǒng)進(jìn)行了優(yōu)化；高翔等[2]提出一種結(jié)合人眼檢測(cè)和定位的人臉識(shí)別方法，并將其用于智能會(huì)議系統(tǒng)中；王文明等[3]提出了一種在具備全景圖合成功能應(yīng)用型機(jī)器人視覺中加裝人臉識(shí)別功能的方法，該方法被成功用于多領(lǐng)域的機(jī)器人監(jiān)控系統(tǒng)中；李定遠(yuǎn)等[4]將基于PCA算法下的人臉識(shí)別技術(shù)應(yīng)用于身份驗(yàn)證環(huán)節(jié)，解決了液壓控制系統(tǒng)運(yùn)行時(shí)的身份驗(yàn)證問題.基于近鄰圖的流形學(xué)習(xí)降維算法[5-7]是解決模式識(shí)別任務(wù)中“維度災(zāi)難”的有效手段，這些通過拉普拉斯特征映射進(jìn)行計(jì)算的流形學(xué)習(xí)降維算法有一個(gè)共性：在原始的高維空間上建立一個(gè)樣本近鄰圖，使用近鄰圖來保持原始流形空間的局部特征，然后通過求解特征值將原始流形空間上的數(shù)據(jù)映射到低維空間.正是由于該共性，文獻(xiàn)[5]中提出了圖嵌入框架理論，很多現(xiàn)有的降維算法[6-9]都可歸入到圖嵌入框架之中.在圖嵌入框架理論中，近鄰圖的作用是盡量保持樣本之間的關(guān)系在降維前后不發(fā)生改變，因此，近鄰圖對(duì)于圖嵌入降維算法來說起著至關(guān)重要的作用.文獻(xiàn)[9]指出，近鄰圖是降維算法的核心，選擇一個(gè)好的近鄰圖構(gòu)建方法比選擇一個(gè)好的降維算法更重要.近鄰保持嵌入算法通過近鄰圖來保持降維前的局部流形結(jié)構(gòu)，因此它是一個(gè)典型的基于近鄰圖流形學(xué)習(xí)降維算法.但NPE算法有如下兩個(gè)不足：1)具有二維結(jié)構(gòu)的數(shù)據(jù)樣本或人臉圖片被轉(zhuǎn)化成了向量形式，這樣構(gòu)建的近鄰圖沒有考慮原始人臉圖片的二維結(jié)構(gòu)信息且參數(shù)k指定困難；2)NPE算法對(duì)于存在遮擋的人臉圖片魯棒性不強(qiáng)，當(dāng)人臉圖片存在遮擋時(shí)NPE取得的識(shí)別率較低.本文提出了多尺度稀疏近鄰圖構(gòu)造方法，并稱使用該方法構(gòu)造的近鄰圖為多尺度稀疏近鄰圖(multi-scale sparse neighbor graph，MSNG).對(duì)于每個(gè)待識(shí)別的人臉圖片，近鄰圖構(gòu)造方法都會(huì)建立一個(gè)九個(gè)尺度的圖像金字塔，并且計(jì)算金字塔中每個(gè)尺度與其他圖片對(duì)應(yīng)的稀疏近鄰.兩個(gè)圖片能否成為近鄰將由兩個(gè)圖片金字塔之間稀疏近鄰的個(gè)數(shù)決定.本文將該方法構(gòu)造的近鄰圖(MSNG)與NPE算法結(jié)合，提出了基于多尺度稀疏近鄰圖的近鄰保持嵌入算法(MSNG-NPE).與傳統(tǒng)NPE算法相比，MSNG-NPE算法優(yōu)勢(shì)如下：

1) 稀疏表示算法對(duì)遮擋具有很強(qiáng)的魯棒性.多尺度稀疏近鄰圖構(gòu)造方法通過計(jì)算一張人臉圖片在每個(gè)尺度上的稀疏近鄰來確定人臉圖片在近鄰圖中的近鄰，這樣構(gòu)造出來的近鄰圖對(duì)于人臉的遮擋具有魯棒性.

2) 對(duì)于每張人臉圖片，都建立一個(gè)具有九尺度的高斯金字塔，通過計(jì)算金字塔中每個(gè)尺度圖片的稀疏近鄰來構(gòu)建近鄰圖.

3) 原始的近鄰圖構(gòu)造方法需要預(yù)先指定近鄰參數(shù)k，而本文提出的近鄰圖構(gòu)造方法不需要指定近鄰參數(shù).

1 相關(guān)算法

1.1 局部保持嵌入算法

設(shè)含有N個(gè)圖片樣本的人臉數(shù)據(jù)集為I={I1，I2，…，IN}，圖片的尺寸為n×m.令X={x1，x2，…，xN}為數(shù)據(jù)集I中人臉圖片的向量形式.NPE的近鄰圖可以表示為G={V，W}，其中，V為圖G的頂點(diǎn)集合，即V對(duì)應(yīng)著集合X；W為帶權(quán)鄰接矩陣，wij為兩個(gè)樣本xi和xj在近鄰圖中對(duì)應(yīng)的頂點(diǎn)vi和vj之間鄰接邊上的權(quán)值.NPE算法描述如下：

1) 確定近鄰.若xi是xj的k近鄰之一，或者xj是xi的k近鄰之一，則兩個(gè)樣本在圖G中是鄰接的.

2) 計(jì)算權(quán)重.通過最小化目標(biāo)函數(shù)來計(jì)算鄰接邊上的權(quán)值，即

(1)

若Y={y1，y2，…，yN}是集合X在低維空間的數(shù)據(jù)映射，則映射關(guān)系為Y=αTX，其中，α為NPE的映射向量，其計(jì)算表達(dá)式為

XMXTα=λXXTα

(2)

式中，M=(I-W)T(I-W)，且I=diag(1，1，…，1).式(2)的解為α0，α1，…，αd-1，它們與特征值λ0≤λ1≤…≤λd-1相對(duì)應(yīng).

1.2 稀疏表示算法

若X={x1，x2，…，xN}表示數(shù)據(jù)集I中人臉圖片的向量形式.對(duì)于一個(gè)新的樣本Y，稀疏表示的目標(biāo)是使用集合X中盡量少的樣本來表示樣本Y.若Y=Xs0，s0為系數(shù)向量，s0=[0，…，0，a1，a2，…，aj，0，…，0]T.稀疏表示的目標(biāo)函數(shù)[10]為

(3)

式(3)是一個(gè)l1范數(shù)最小化問題，可以通過正交匹配(orthogonal matching pursuit，OMP)算法[11]來計(jì)算.

2 多尺度稀疏近鄰圖的近鄰嵌入算法

設(shè)含有N個(gè)圖片樣本的人臉數(shù)據(jù)集I={I1，I2，…，IN}，圖片的尺寸為n×m.令X={x1，x2，…，xN}表示數(shù)據(jù)集I中人臉圖片的向量形式.MSNG可以表示為MSNG={V，WMSNG}，與傳統(tǒng)近鄰圖類似，V和WMSNG分別表示頂點(diǎn)集合和帶權(quán)鄰接矩陣.MSNG的構(gòu)造過程如下：

1) 建立圖像金字塔.對(duì)于一個(gè)人臉圖片建立如圖1所示的具有九個(gè)尺度圖像金字塔.圖像金字塔中圖像的尺寸從原始尺寸(尺度1)到原始尺寸的20%(尺度9).

圖1 九個(gè)尺度的圖片金字塔Fig.1 Image pyramid with nine scales

3) 計(jì)算每個(gè)人臉圖片Ii的近鄰.設(shè)Nij表示圖片Ij對(duì)應(yīng)金字塔的所有尺度圖片中成為了圖片Ii對(duì)應(yīng)的金字塔中圖片的近鄰，Nij描述了兩個(gè)樣本間的相似程度，即Nij的值越大，兩個(gè)樣本圖片Ii和Ij就越相似.帶權(quán)鄰接矩陣WMSNG可以表示為

(4)

3 實(shí)驗(yàn)仿真

3.1 人臉遮擋魯棒性實(shí)驗(yàn)

本節(jié)實(shí)驗(yàn)在AR人臉數(shù)據(jù)庫(kù)上進(jìn)行，AR人臉數(shù)據(jù)庫(kù)含有來自126位志愿者的超過4 000張的人臉圖片[12].部分AR數(shù)據(jù)庫(kù)中的人臉上有遮擋物，例如墨鏡或者圍巾.本文建立了一個(gè)AR數(shù)據(jù)庫(kù)的子集，該子集中含有50位男性志愿者，其中每個(gè)志愿者13張照片.在這13張照片中有6張照片是含有遮擋的.圖2為本文AR數(shù)據(jù)庫(kù)子集的人臉樣本圖片.

圖2 AR數(shù)據(jù)庫(kù)中的人臉樣本圖Fig.2 Face sample images in AR database

首先對(duì)比MSNG和傳統(tǒng)近鄰圖構(gòu)造方法在人臉上有遮擋情況下正確尋找近鄰的能力.分別使用MSNG和傳統(tǒng)的近鄰圖構(gòu)造方法來尋找AR數(shù)據(jù)庫(kù)中第2個(gè)志愿者的第5張照片的近鄰.設(shè)置傳統(tǒng)近鄰圖構(gòu)造方法的近鄰參數(shù)k=6，將MSNG計(jì)算出來的前6個(gè)近鄰與傳統(tǒng)近鄰圖計(jì)算出來的6個(gè)近鄰進(jìn)行比較，兩種近鄰圖構(gòu)造方法選擇出來的人臉近鄰如圖3所示.

從圖3a可以看出：人臉近鄰1～4都屬于第二個(gè)志愿者.盡管人臉圖片2～4存在遮擋，但是MSNG還是正確將其作為人臉圖片5的近鄰.從圖3b可以看出：傳統(tǒng)的近鄰圖構(gòu)造方法計(jì)算出來的6個(gè)近鄰圖片都不屬于第二個(gè)志愿者.通過這個(gè)實(shí)驗(yàn)可以看出，在存在遮擋的情況下，傳統(tǒng)的近鄰圖構(gòu)造方法無法正確計(jì)算出每個(gè)樣本的k近鄰，從而導(dǎo)致所構(gòu)造的近鄰圖質(zhì)量不高，最終導(dǎo)致識(shí)別率低.

在AR數(shù)據(jù)庫(kù)上進(jìn)行人臉識(shí)別實(shí)驗(yàn)，Gm/Pn表示在一輪實(shí)驗(yàn)中每個(gè)志愿者選擇m張圖片用于訓(xùn)練，其余n張圖片用于測(cè)試.對(duì)于每一輪實(shí)驗(yàn)，都隨機(jī)產(chǎn)生50組Gm/Pn的數(shù)據(jù)，本輪最終的實(shí)驗(yàn)結(jié)果為這50組數(shù)據(jù)得到結(jié)果的平均值.表1對(duì)比了NPE算法和MSNG-NPE算法的平均識(shí)別率，NPE算法的近鄰參數(shù)設(shè)置為Gm.

從表1中可以看出，由于遮擋干擾了近鄰圖的構(gòu)建，NPE算法取得了很低的識(shí)別率，但是MSNG-NPE算法取得了較為滿意的識(shí)別率.

3.2 人臉識(shí)別實(shí)驗(yàn)

本節(jié)在ORL和YALE數(shù)據(jù)庫(kù)上進(jìn)行人臉識(shí)別實(shí)驗(yàn).YALE數(shù)據(jù)庫(kù)中有11個(gè)志愿者，每人11張照片，總共有121張人臉圖片[13]，YALE數(shù)據(jù)庫(kù)中照片尺寸是100×100；ORL數(shù)據(jù)庫(kù)中有40個(gè)志愿者，每人10張照片，共有400張人臉圖片[14]，ORL數(shù)據(jù)庫(kù)中照片的尺寸是112×92，設(shè)置傳統(tǒng)近鄰圖構(gòu)造方法的近鄰參k=6.圖4、5分別為ORL和YALE人臉庫(kù)的樣本照片，表2、3分別是在ORL和YALE人臉庫(kù)上進(jìn)行人臉識(shí)別的實(shí)驗(yàn)結(jié)果.

圖3 志愿者2第5張照片的近鄰比較Fig.3 Comparison in neighbors of No.5face image of No.2 volunteer

圖4 ORL數(shù)據(jù)庫(kù)中的人臉樣本圖Fig.4 Face sample images in ORL database

圖5 YALE數(shù)據(jù)庫(kù)中的人臉樣本圖Fig.5 Face sample images in YALE database

測(cè)試類型NPEMSNG-NPEG2/P861.5471.01G3/P770.4177.88G4/P677.3883.84G5/P582.3786.01G6/P485.2385.89G7/P388.0589.32

表3 YALE數(shù)據(jù)庫(kù)上的平均識(shí)別率Tab.3 Average recognition accuracy in YALE database %

從表2、3中的實(shí)驗(yàn)結(jié)果可以看出：隨著訓(xùn)練樣本數(shù)量的增加，兩個(gè)算法的平均識(shí)別率都逐漸提高；在ORL和YALE數(shù)據(jù)庫(kù)上進(jìn)行實(shí)驗(yàn)時(shí)，使用MSNG-NPE算法所取得的人臉識(shí)別率都超過了使用NPE算法進(jìn)行人臉識(shí)別所取得的識(shí)別率.

4 結(jié) 論

本文提出了一種近鄰圖構(gòu)造方法，方法對(duì)于每個(gè)人臉圖片建立一個(gè)具有九個(gè)尺度的圖片金字塔，并計(jì)算金字塔中每個(gè)尺度圖片的稀疏近鄰.用兩個(gè)人臉圖片金字塔之間成為稀疏近鄰的個(gè)數(shù)來決定是否這兩個(gè)人臉圖片在最終的近鄰圖中可以成為近鄰.之后，將MSNG與NPE算法結(jié)合，提出了MSNG-NPE算法，在幾個(gè)著名人臉數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)結(jié)果顯示，MSNG-NPE算法具有比傳統(tǒng)的NPE算法更好的識(shí)別效果.