呂思思， 梁久禎

（江南大學(xué) 物 聯(lián)網(wǎng)工程學(xué)院，江蘇 無 錫 214122）

人臉作為一個重要的生物特征，傳遞著重要的信息。一方面，因為其唯一性的特點，能夠傳達(dá)個體的身份信息，所以人臉識別是基于生物特征識別技術(shù)的身份認(rèn)證中最主要的方法之一，與其他生物特征識別技術(shù)相比具有獨特的優(yōu)勢。另一方面，人臉面部的表情又可以反映個體的思想感情和情緒狀態(tài)，通過分析可以獲知個體的內(nèi)心態(tài)度和情感變化。對此許多研究機(jī)構(gòu)和學(xué)者針對人臉展開了相關(guān)的研究工作，人臉表情的研究已成為模式識別和人工智能領(lǐng)域的熱點。目前人臉表情研究在日常生活中有很好的應(yīng)用前景，主要體現(xiàn)在對相關(guān)學(xué)科的促進(jìn)、智能人機(jī)交互、心理狀態(tài)分析、醫(yī)療診斷技術(shù)、圖像實時傳輸、動畫電影制作及娛樂產(chǎn)品開發(fā)等多個方面［1］。

在人臉研究中，因為簡單、分類能力強(qiáng)等優(yōu)點，基于線性子空間的方法已成為主流的特征提取方法?；诰€性子空間分析的特征提取方法是根據(jù)一定的性能目標(biāo)來尋找一個線性空間變換，將高維數(shù)據(jù)投影到低維線性子空間上，使投影后提取的特征數(shù)據(jù)更能滿足目標(biāo)要求，并且達(dá)到壓縮原始數(shù)據(jù)維數(shù)的目的，為數(shù)據(jù)的描述提供方便，并降低計算的復(fù)雜度。在人臉特征提取中常用的線性子空間分析方法有主成分分析（Principal Component Analysis，簡稱PCA）［2］、線性判別分析（Linear Discriminate Analysis，簡稱 LDA）［3］、獨立成分分析（Independent Component Analysis，簡稱ICA）［4］等。近年來的研究發(fā)現(xiàn)，人臉圖像很可能位于一個非線性流形上［5－7］，基于流形學(xué)習(xí)（manifold learning）的人臉研究算法被提出。流形是線性子空間的一種非線性推廣，是局部可坐標(biāo)化的一個拓?fù)淇臻g。流形學(xué)習(xí)本質(zhì)上是一種非線性降維方法，旨在發(fā)現(xiàn)嵌入在高維數(shù)據(jù)空間的低維光滑流形。具有代表性的流形學(xué)習(xí)方法有局部線性嵌入 （Locally Linear Embedding，簡稱 LLE）［6］、拉 普 拉 斯 特 征 映 射 （Laplacian Eigenmaps，簡稱 LE）［8］、等 距 映 射 （Isometric Mapping，簡稱Isomap）［7］、局部保持投影（Locality Preserving Projections，簡稱 LPP）［9－10］等。

然而，由于人臉研究問題中的高維圖像和大規(guī)模樣本的關(guān)系，線性子空間法和流形學(xué)習(xí)算法均需要進(jìn)行復(fù)雜的計算，制約著研究任務(wù)的快速性和有效性，這是該領(lǐng)域中研究的焦點和難點。人類在解決和處理大量復(fù)雜信息問題時，總是按各自的特征和性能將其分解為若干較簡單的子問題或模塊，然后對每個分割成的粒進(jìn)行處理，降低了問題的難度和復(fù)雜度。粒計算［11］是基于不同層次的粒度上對問題進(jìn)行觀察、分析和求解，對于模式識別、圖像處理、數(shù)據(jù)挖掘、知識工程等實際問題，粒計算是一種降低計算復(fù)雜度的有效方法。

本文針對人臉研究中高維數(shù)據(jù)的高計算復(fù)雜度問題，在粒計算的思想上，提出基于圖像粒的LLE算法，旨在降低計算復(fù)雜度；并基于加權(quán)思想，實現(xiàn)圖像粒LLE算法。在不同層次的粒度下分別實現(xiàn)LLE算法，分析粒計算方法的計算復(fù)雜度和圖像信息丟失情況。在Frey人臉圖像庫上進(jìn)行實驗，結(jié)果表明，基于圖像粒的方法降低了算法計算復(fù)雜度，提高了速率，并對圖像信息的保持具有一定的有效性。

1 局部線性嵌入（LLE）算法

LLE算法能夠?qū)崿F(xiàn)高維輸入數(shù)據(jù)點映射到一個全局低維坐標(biāo)系，同時保留了鄰接點之間的關(guān)系，使降維的數(shù)據(jù)保持原有的拓?fù)浣Y(jié)構(gòu)。算法認(rèn)為在流形上小的每個局部是一個局部歐式空間，因此鄰域內(nèi)數(shù)據(jù)的結(jié)構(gòu)是線性的，每個樣本點及其近鄰樣本之間是線性關(guān)系，從而一個樣本點可以用其近鄰樣本的線性組合來重構(gòu)。通過最小化重構(gòu)誤差，可以得到近鄰樣本之間的線性表示權(quán)重，其中蘊(yùn)含著數(shù)據(jù)集的局部領(lǐng)域的結(jié)構(gòu)信息。LLE算法根據(jù)權(quán)值矩陣，在低維數(shù)空間中構(gòu)造出與原樣本集具有類似鄰域結(jié)構(gòu)的嵌入向量集合，從而保證了原樣本集中的近鄰樣本的嵌入向量仍然是近鄰，且嵌入空間中的鄰域結(jié)構(gòu)與原樣本集合的鄰域結(jié)構(gòu)保持相似。

1.1 LLE算法步驟

LLE算法的具體步驟為：

（2）重構(gòu)權(quán)值矩陣。每個樣本點xi及其領(lǐng)域點xij之間的重構(gòu)權(quán)值為wij，定義誤差函數(shù)為：

且滿足條件：

通過極小化（1）式來實現(xiàn)重構(gòu)權(quán)值wij的構(gòu)造。

在約束條件（2）式下，（1）式中的誤差函數(shù)可寫為：

其中，Zi＝（xi－xij）為第i個樣本點xi的局部協(xié)方差矩陣；w＝［wi1，wi2，…，wik］T為第i個樣本點的局部重建權(quán)值。

求解 （ 3）式是一個約束最小乘方問題，可用Lagrange乘子法，則有：即可求得wi，（4）式中c通常取1。

（3）計算低維嵌入。將所有的樣本點映射嵌入到低維空間中，映射嵌入滿足的條件為：

其中，yi為xi的輸出量；Φ（Y）為損失函數(shù)。

優(yōu)化輸出向量Y滿足以下2個條件：

其中，I為單位矩陣。wij（i＝1，2，…，N）可存儲在N×N的稀疏矩陣W 中 ，當(dāng)xj為xi的近鄰點時，Wi，j＝wij；否則，Wi，j＝0。用Wi表 示W(wǎng) 矩 陣的第i列，Ii表示N×N單位矩陣的第i列，輸出向量Y＝［y1，y2，…，yN］。（5）式可寫為：

其中，M＝（I－W）（I－W）T。結(jié)合約束條件，利用Lagrange乘子，則有：

要使損失函數(shù)（5）式達(dá)到最小，取Y為M 的最小d（d＜D）個非零特征值所對應(yīng)的特征向量。通常最小特征值幾乎為0，因此取第2～（d＋1）間的特征值所對應(yīng)的特征向量作為輸出結(jié)果Y。

1.2 算法復(fù)雜度分析

（1）選取鄰域計算復(fù)雜度為O（DN2），近鄰數(shù)k通常是較小的數(shù)，有k≤D。

（2）重構(gòu)權(quán)值矩陣的計算復(fù)雜度為O（（D＋k）k2N）。

（3）由于矩陣M具有很強(qiáng)的稀疏性，計算d維嵌入的計算復(fù)雜度為O（dN2）。

該算法時間復(fù)雜度為：

通常，映射嵌入的維數(shù)d是一個較小的數(shù)，顯然有d＜D，故LLE算法復(fù)雜度近似為：

圖像的最基本單位是像素，許多圖像處理方法都是建立在像素這個層次上。而在很多實際問題中，并不需要完全以像素為單位來進(jìn)行處理，只需對圖像保持一定的信息。對于包含1 000張128×128的人臉圖像的樣本數(shù)據(jù)，每幅圖像維數(shù)D＝128×128＝16 384，直接應(yīng)用LLE算法時，計算復(fù)雜度T＝O（DN2）＝O（1010）；若對圖像按8×8大小分塊，每個塊作為一個粒進(jìn)行處理，則圖像維數(shù)降低為D＝16×16＝256，計算復(fù)雜度T＝O（108）。圖像粒是一個降低計算復(fù)雜度的有效方法。

1.3 加權(quán)預(yù)處理

在人臉研究中，針對人臉圖像的不同區(qū)域研究的重點各不相同。人臉表情的研究分析中，人臉的眼睛、嘴巴等區(qū)域作為較重要分析部位。在選擇近鄰點中，在計算2個樣本圖像之間的歐式距離時，先對圖像進(jìn)行加權(quán)預(yù)處理，給定每個像素點一個權(quán)值，增大較為重要部位的像素點的權(quán)重，計算結(jié)果增大了對重要部位的像素點的相似度計算，對近鄰點的選擇產(chǎn)生一定的變化。

每個樣本圖像xi＝［x1i，x2i，…，xDi］T，其權(quán)值計算公式為：

其中，m＝1，2，…，D；

每個像素點進(jìn)行如下加權(quán)：

2 圖像粒

粒計算融合了模糊集、粗糙集及人工智能等領(lǐng)域的研究成果，其思想源于有關(guān)模糊集的信息?；芯浚?2］。所謂信息粒是指人類在解決和處理大量復(fù)雜信息問題時，按各自的特征和性能將其分解為若干較簡單的子問題或模塊，每個分割成的塊被看作一個粒，而這種處理信息的過程即為信息粒化。粒計算是在解決問題過程中運(yùn)用粒（granule）概念的一種理論和方法，基本單位是粒，一個?？梢钥醋魇怯蓛?nèi)部屬性描述的個體元素的集合［13］，這些個體元素因為相似性、不可區(qū)分性及一致性等結(jié)合在一起。不同的?；瘻?zhǔn)則生成不同的粒層次和粒結(jié)構(gòu)，在不同的粒層次下解決問題時往往會產(chǎn)生具有不同特性的方法。

粒度是一個物理學(xué)概念，它在計算機(jī)界則被用作“信息粗細(xì)的平均度量”。信息粒度的提出，主要是因為很多專家和學(xué)者都認(rèn)識到人工智能在處理現(xiàn)實世界的問題時，常常采用從不同層次觀察問題的策略。對于一個問題，有時需要在不同的粒度層次上對問題進(jìn)行求解，因此需要研究不同粒度世界的關(guān)系。

設(shè)R表示由論域X上一切等價關(guān)系組成的集合，可以定義如下等價關(guān)系，即粒度的“粗”和“細(xì)”。

定義1 設(shè)R1，R2∈R，如果對于任意x，y∈X，都有xR1y?xR2y，那么稱R1比R2細(xì)，記作R1≤R2。

定義2 假設(shè)存在一個概念φ，屬于概念φ的所有元素記作φ的意義集m（φ），表示為m（φ）＝｛x∈U，x｜≈φ｝，其中U表示論域；｜≈表示一種公式可滿足性符號，將m（φ）稱作一個粒。

對于一幅大小為h×w的圖像，I＝Ih×w表示該圖像的所有像素；圖像中任意一個像素或塊，記作b＝［h1，h2］×［w1，w2］，顯然有0≤h1＜h2＜h且0≤w1＜w2＜w；則Ib即為一個粒：m（Ib）＝｛（i，j）∈b?［0，h）×［0，w）｝，最細(xì)的粒是像素層次上的，即只含有1個像素，最粗的粒是包含整幅圖像所有像素的塊。

定義3 粒m（φ）的大小定義為：

L（m（φ））＝ Card（m（φ））／Card（U） （10）其中，Card（m（φ））表示m（φ）中包含的元素個數(shù)；Card（U）表示論域U的元素總數(shù)。

在一幅大小為128×128的圖像I中，若Ib為I中的一個塊，b＝［0，3］×［0，3］。由定義2知Ib為 一 個 粒，大 小 為L（m（Ib））＝Card（m（Ib））／Card（I）＝（4×4）／（128×128）＝1／1 024。對于整幅圖像，最細(xì)的粒大小為L（m（Ifine））＝1／（128×128）＝1／16 384，最粗的粒大小為L（m（Icoarse））＝1。

定義4 將圖像I分塊b1，b2，…，bt，每塊為一個粒m（Ib），每個粒中所有像素的均值為E1，E2，…，Et，這組均值的方差為σ。定義圖像粗糙度r（I）＝e－σ，顯然有0＜r（I）≤1。

對于一幅圖像，所分的塊越小，即粒越細(xì)，σ越大，e－σ越小，即圖像粗糙度r（I）越小，信息丟失量越少；反之，粒越大，圖像越粗糙，即丟失的信息量越多。

定義5 假設(shè)I1、I2為2個相鄰層次上的圖像粒，不妨令L（m（I1））＜L（m（I2）），定義圖像粒差異D（I1，I2）＝r（I1）－r（I2）。

3 圖像粒實驗

選擇Frey人臉數(shù)據(jù)庫進(jìn)行實驗，該數(shù)據(jù)庫包含同一人在一段視頻中截取的1 965幅不同表情、姿態(tài)的圖像，每幅圖像大小為20×28像素，每像素256灰度級，這樣每幅人臉圖像為560維灰度圖像。部分圖像如圖1所示。

圖1 Frey人臉數(shù)據(jù)庫中部分圖像

3.1 圖像粒LLE實驗

人臉數(shù)據(jù)庫中圖像應(yīng)用LLE算法降維處理后的分布情況如圖2所示。

圖2 Frey庫圖像在像素粒度上應(yīng)用LLE的二維線性嵌入

人臉圖像映射到由LLE算法的前2個坐標(biāo)所描述的二維平面上，一些有代表性的面孔顯示在對應(yīng)數(shù)據(jù)點的旁邊。由圖2可以看出，人臉圖像有2個明顯的變化方向。從上到下有明顯的人臉角度的變化，即從面向左側(cè)、正面、面向右側(cè)的轉(zhuǎn)變；從左到右有明顯的人臉表情的變化，即左邊的閉著嘴巴的不開心的表情，逐漸向右邊轉(zhuǎn)變?yōu)殚_心的微笑著的表情。

按圖像粒的方法進(jìn)行實驗。對圖像分別以2×2、4×4大小的圖像粒進(jìn)行分塊，計算每個粒中所包含的所有像素的均值，則每幅人臉圖像轉(zhuǎn)變?yōu)?40維、35維灰度圖像，對圖像原始的高維數(shù)據(jù)進(jìn)行了降維。1 965幅人臉圖像應(yīng)用圖像粒預(yù)處理并應(yīng)用LLE算法降維后的分布情況如圖3所示。

將人臉圖像映射到由LLE算法的前2個坐標(biāo)所描述的二維平面上，部分?jǐn)?shù)據(jù)點的邊上顯示對應(yīng)的原始人臉圖像。實驗結(jié)果與圖2相比，圖3中人臉圖像的整體分布形狀上有變化，而人臉的連續(xù)性變化情況沒有明顯改變，仍然維持在從上到下角度的變化、從左到右的表情的變化趨勢。但隨著粒的增大，圖像信息丟失程度增加，圖像集中程度高，區(qū)分不明顯。

圖3 Frey庫圖像應(yīng)用圖像粒LLE的二維線性嵌入

算法的計算復(fù)雜度問題，體現(xiàn)在實驗的運(yùn)行時間上。以像素為粒進(jìn)行實驗時，從讀取圖像開始到LLE算法結(jié)束為運(yùn)行所用時間；以圖像粒進(jìn)行實驗時，運(yùn)行時間還包括了對圖像的分塊以及計算每個粒中所有像素均值所用的時間，總的運(yùn)行時間有所變化。在不同粒度大小下實驗的運(yùn)行時間見表1所列。

表1 不同圖像粒下實現(xiàn)LLE的時間 s

表1中k為選擇的近鄰個數(shù)。由表1可以看出，對每個選擇的近鄰數(shù)k，運(yùn)行時間隨著圖像粒的增大而減少，降低了計算復(fù)雜度。

雖然實驗減少了運(yùn)行時間，提高了速度，但以圖像粒方法對圖像進(jìn)行處理時，圖像的信息有丟失。隨著粒的增大，二維嵌入中分布的點（即對應(yīng)的圖像）的區(qū)分卻不明顯，是因為隨著粒的增大，圖像的信息損失程度增大，一些細(xì)節(jié)上的差別信息丟失。

下面分析針對不同圖像粒大小進(jìn)行實驗時人臉圖像信息量的情況。根據(jù)定義4，計算每張圖像在不同大小的圖像粒處理方法時的圖像粗糙度。圖1所示的9張人臉圖像的粗糙度、信息熵及粒差異見表2所列。從表2可以看出，隨著圖像粒的增大，圖像粗糙度增加，即圖像變得越粗糙，損失的信息量越多；隨著圖像粒的增大，圖像信息熵減少；隨著圖像粒的增大，相鄰層次上的圖像粗糙度之差變大，圖像變粗糙的程度越快，圖像信息的損失越嚴(yán)重。

表2 不同圖像粒下Frey庫圖像應(yīng)用LLE的粗糙度、信息熵和粒差異

3.2 加權(quán)預(yù)處理的圖像粒LLE實驗

將Frey人臉數(shù)據(jù)庫中圖像分別以1×1、2×2、4×4大小的圖像粒進(jìn)行分塊，計算每個粒中所包含的所有像素的均值，對圖像原始的高維數(shù)據(jù)進(jìn)行降維，然后應(yīng)用加權(quán)預(yù)處理的圖像粒LLE算法，降維處理后映射到前2個坐標(biāo)所描述的二維平面上，人臉圖像分布情況如圖4所示，數(shù)據(jù)點的旁邊顯示的是對應(yīng)的面孔。

圖4 Frey庫圖像在不同粒度上應(yīng)用加權(quán)預(yù)處理LLE的二維線性嵌入

由圖4可以看出，人臉圖像有2個明顯的變化方向，從上到下人臉角度的變化和從左到右人臉表情的變化?？v向變化上，人臉從面向左側(cè)、到正面、最后面向右側(cè)；橫向變化中，人臉表情從左邊的閉著嘴巴不開心逐漸向右邊轉(zhuǎn)變?yōu)殚_心微笑的表情。在像素粒度和2×2粒度變化下，人臉圖像分布維持上述連續(xù)變化規(guī)律，但隨著粒增大，圖像信息損失程度增大，一些細(xì)節(jié)上的差別信息丟失，在4×4粒度下圖像集中度高，中間部分很難進(jìn)行區(qū)分。和3.1的實驗相比，在對應(yīng)粒度下，本節(jié)實驗的二維線性嵌入人臉分布較為明顯。

在像素粒度上進(jìn)行實驗時，從讀取圖像到算法結(jié)束為運(yùn)行所用時間；以圖像粒進(jìn)行實驗時，運(yùn)行時間包括對圖像的分塊、計算每個粒中所有像素均值以及計算圖像像素權(quán)值所用的時間，實驗結(jié)果見表3所列，由表3可看出，運(yùn)行時間隨著圖像粒的增大而減少，降低了計算復(fù)雜度。

表3 不同圖像粒下實現(xiàn)加權(quán)預(yù)處理LLE的時間 s

根據(jù)定義4、定義5計算圖1中的9張人臉圖像在不同大小的圖像粒處理時的圖像粗糙度、信息熵和圖像粒差異，見表4所列。從表4可看出，隨著圖像粒的增大，圖像粗糙度增加，即圖像變得越粗糙，損失的信息量越多；相鄰層次上的圖像粗糙度之差變大，圖像變粗糙的程度越快，圖像信息的損失越嚴(yán)重。這與圖像信息熵的計算結(jié)果一致。

表4 不同圖像粒下Frey庫圖像應(yīng)用加權(quán)預(yù)處理LLE粗糙度、信息熵和粒差異

4 結(jié)束語

本文提出了一種基于粒計算思想的局部線性嵌入方法，首先以粒度大小對圖像進(jìn)行分塊處理，隨后進(jìn)行LLE算法。從Frey人臉庫上的實驗結(jié)果分析可知，該方法對人臉圖像信息的保持具有一定的有效性，能對姿態(tài)和表情進(jìn)行區(qū)別和分類；同時，對圖像實現(xiàn)了數(shù)據(jù)降維，降低了計算復(fù)雜度。從數(shù)據(jù)可看出，隨著圖像粒度的增大，運(yùn)行時間減少，而圖像粗糙度增加，這樣可以選擇一個最佳的粒度大小，既保持了一定的圖像信息量，又減少運(yùn)行時間，提高效率。

［1］ 朱明旱.基于流行學(xué)習(xí)的人臉表情識別研究［D］.長沙：中南大學(xué)，2009.

［2］ Turk M A，Pentland A P.Face recognition using eigenfaces［C］／／Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition，1991：586－591.

［3］ Belhumeur P N，Hespanha J P，Kriegman D J.Eigenfaces vs.Fisherfaces：recognition using class specific linear projection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19（7）：711－720.

［4］ Bartlett M S，Movellan J R，Sejnowski T J.Face recognition by independent component analysis［J］.IEEE Transactions on Neural Networks，2002，13（6）：1450－1464.

［5］ Tenenbaum J B，Silva V D，Langford J C.A global geometric framework for nonlinear dimensionality reduction ［J］.Science，2000，290（5500）：2319－2323.

［6］ Roweis S T，Saul L K.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000，290 （5500）：2323－2326.

［7］ Shashua A，Levin A，Avidan S.Manifold pursuit：a new approach to appearance based recognition ［C］／／Proceedings of 16th International Conference on Pattern Recognition，2002：590－594.

［8］ Belkin M，Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation［J］.Neural Computation，2003，15（6）：1373－1396.

［9］ He Xiaofei，Niyogi P.Locality preserving projections［C］／／Proc of the Conf on Neural Information Processing Systems.Vancouver，Canada，2003：153－160.

［10］ He Xiaofei，Yan Shuicheng，Hu Yuxiao，et al.Face recognition using Laplacianfaces［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（3）：328－340.

［11］ Lin T Y.Granular computing，announcement of the BISC special Interest group on granular computing［EB／OL］.［1997－08－09］.http：／／www.cs.uregina.ca／～yao／GrCl.

［12］ 張燕平，羅 斌，姚一豫，等.商空間與粒計算：結(jié)構(gòu)化問題求解理論與方法［M］.北京：科學(xué)出版社，2010：144－156.

［13］ 張 鈸，張 鈴.粒計算未來發(fā)展方向探討［J］.重慶郵電大學(xué)學(xué)報：自然科學(xué)版，2010，22（5）：538－540.