基于HOG-AP的人臉圖像識別算法*

陳賽英，何建農(nóng)

(福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 福州350108)

目前,圖像目標(biāo)識別算法已經(jīng)廣泛應(yīng)用于各個領(lǐng)域，包括軍事、交通、公安、醫(yī)學(xué)、工業(yè)、遙感圖像處理、攝影測量自動化等[1]。

針對圖像目標(biāo)識別國內(nèi)外學(xué)者相繼提出了多種方法,如粒子群優(yōu)化算法和仿生模式識別法等,但這些方法具有局限性。粒子群優(yōu)化算法主要是針對連續(xù)函數(shù)優(yōu)化問題，但當(dāng)自變量是整數(shù)時，例如生產(chǎn)調(diào)度、路由選擇以及很多整數(shù)規(guī)劃問題[2-3],則不能應(yīng)用該算法來解決。仿生神經(jīng)元網(wǎng)絡(luò)是針對高維數(shù)據(jù)進(jìn)行處理，它的計算量非常大，在實現(xiàn)時，需要對數(shù)據(jù)進(jìn)行降維[4]。仿射傳播AP(Affinity Propagation)算法具有簡單、高效的優(yōu)勢，已經(jīng)廣泛應(yīng)用于多種領(lǐng)域，例如設(shè)施選址、圖像識別、圖像分割等[5],但在應(yīng)用中還存在一些問題，如缺乏判定最優(yōu)聚類結(jié)果的指標(biāo)以及收斂性能不夠好。

圖像目標(biāo)識別的關(guān)鍵問題是選取圖像的特征，用于識別的圖像特征有顏色、紋理、形狀、空間關(guān)系等，但是這些特征都存在一些缺點。顏色特征對圖像或圖像區(qū)域的方向、大小等變化不敏感，當(dāng)圖像的分辨率變化時，所計算出來的紋理可能會有較大偏差[6]。空間關(guān)系特征常對圖像或目標(biāo)的旋轉(zhuǎn)、反轉(zhuǎn)、尺度變化等比較敏感。而方向梯度直方圖HOG(Histograms of Oriented Gradients)描述子具有如下的優(yōu)點：可以描述局部的形狀信息，不受平移、旋轉(zhuǎn)和光照變化的影響，可以很好地表征圖像局部像素點之間的關(guān)系[5,7-8]。

基于以上原因，本文對AP算法進(jìn)行改進(jìn)，提出了提取圖像的HOG特征進(jìn)行聚類識別的改進(jìn)算法。

1 相關(guān)概念及算法

1.1 HOG

HOG描述子的主要思想是一幅圖像中物體的表象和形狀可以被像素強(qiáng)度梯度或邊緣的方向分布很好地描述。其實現(xiàn)方法是,先將圖像分成小的方格單元連通區(qū)域,然后采集方格單元中各像素點的梯度方向或邊緣方向直方圖,最后把這些直方圖組合起來就可以構(gòu)成特征描述子[7,9]。

1.2 收縮因子

[10]的研究表明,使用收縮因子可以有效保證算法收斂。收縮因子的公式為：

在數(shù)值實驗中，φ取值為4.1，因此ρ=0.729。收縮因子可以調(diào)節(jié)收斂系數(shù)，以加速收斂過程。

1.3 指標(biāo)

(1)Silhouette指標(biāo)

樣本t的Silhouette指標(biāo)為:

其中，a(t)為聚類Cj中的樣本t與類內(nèi)所有其他樣本的平均不相似度或距離；d(t,Ci)為樣本 t到另一個類 Ci的所有樣本的平均不相似度或距離，則:

(2)Hartigan指標(biāo)

Hartigan指標(biāo)適用于類數(shù)估計,其滿足Ha≤10的最小類數(shù)作為最優(yōu)的聚類個數(shù):

在有效性指標(biāo)中，Silhouette指標(biāo)[11]具有性能好、簡單易用、既能評價聚類結(jié)果的優(yōu)良程度也能確定聚類個數(shù)的優(yōu)勢，所以得到廣泛的應(yīng)用，選擇它對半監(jiān)督仿射傳播算法的運行進(jìn)行監(jiān)督和指導(dǎo)是合適的。但是Silhouette指標(biāo)在聚類個數(shù)為1時沒有定義,于是采用 Hartigan指標(biāo)[11]進(jìn)一步判斷是否只有一個聚類。

1.4 AP算法

AP算法不需要事先指定聚類數(shù)目，在迭代過程中不斷搜索合適的聚類中心，自動從數(shù)據(jù)點間尋找類中心的位置及個數(shù)。算法開始時把所有的數(shù)據(jù)點都作為潛在的聚類中心，通過數(shù)據(jù)點間的“信息傳遞”來實現(xiàn)聚類過程。與傳統(tǒng)的K均值算法對初始聚類中心的選擇的敏感性相比，AP算法是一種具有確定性的聚類算法，多次獨立運行的聚類結(jié)果一般比較穩(wěn)定[12]。

AP算法主要根據(jù)N個樣本點之間的相似度進(jìn)行聚類,這些相似度組成N×N的相似度矩陣S,如S(i,j)=‖xi-xj‖表示樣本點i和樣本點 j之間的相似度。AP算法通過迭代過程不斷更新每一個點的責(zé)任值(Responsibility值)和有效值(Availability值)，直到自動產(chǎn)生若干個高質(zhì)量的聚類中心，同時將其余的數(shù)據(jù)點分配到相應(yīng)的類中[12]。

2 基于HOG的AP改進(jìn)算法

AP算法存在兩個問題：一是很難確定何時能夠使算法產(chǎn)生最優(yōu)的聚類結(jié)果，即沒有一個判定最優(yōu)聚類結(jié)果的指標(biāo)；二是AP算法中收斂系數(shù)常作為固定參數(shù)在算法運行中保持不變，因此其收斂性能不好。針對AP算法存在的兩個問題，本文提出基于HOG的AP改進(jìn)算法。

2.1 算法的主要思想

首先提取圖像的HOG特征向量；然后在AP算法基礎(chǔ)上引入收縮因子調(diào)節(jié)收斂系數(shù)[10]，以加速AP算法的收斂過程，改善AP算法的收斂性能；最后將評價聚類質(zhì)量的有效性指標(biāo)嵌入算法的迭代過程，依據(jù)比較小的來產(chǎn)生各個聚類中心，其聚類目標(biāo)是有效性指標(biāo)所指示的最好聚類質(zhì)量，因此能夠監(jiān)督并引導(dǎo)算法向著最好聚類質(zhì)量的方向運行[13]。

2.2 算法的主要步驟

(1)計算HOG特征向量。本文計算HOG特征所使用的一些參數(shù)設(shè)置如下:沒有Gamma校正等光照預(yù)處理；梯度計算采用簡單的中心對稱算子；沒有圖像平滑；采樣窗口大小為 8×8,分為 4個 4×4像素的 cell；沒有計算高斯加權(quán)范圍；初始的方向角是0～180°,分為 9個塊；L2-norm的block標(biāo)準(zhǔn)化方法；塊與塊之間沒有重疊。

(2)算法初始化,將步驟(1)的 HOG特征向量作為輸入，計算初始相似度矩陣 S(i,j)=-‖xi-xj‖;偏向參數(shù) p=pm，pm=median(median(S))； 下 降 步 幅 為 step=pmin/10,pmin=max(max(S))，；收斂條件為聚類中心30次循環(huán)無變化、終止參數(shù)為最大循環(huán)次數(shù)Cy=1 000或者聚類中心300次循環(huán)無變化。

(3)A(i,j)、R(i,j)初始化為零矩陣，計算樣本點間的Responsibility值:

其中，A(i,j)表示 j對于 i的 Availability值。

(4)計算樣本點間的Availability值:

(5)Responsibility值和Availability值的更新：

其中，ρ是收縮因子，調(diào)節(jié)收斂系數(shù)λ，以加速AP算法的收斂過程。

(6)運行m次迭代過程，算法產(chǎn)生K1個候選的聚類中心，則給出K1個聚類并計算Silhouette指標(biāo)值Sil1。

(7)以步幅step減小參數(shù)p為p=p+step，繼續(xù)迭代過程，若產(chǎn)生的聚類數(shù)目下降收斂到某個類數(shù)K2，則計算K2個聚類的Sil2，同時計算所有指標(biāo)值中的最大值Silmax，當(dāng) Sil2＜Silmax時，則統(tǒng)計 Silhouette指標(biāo)值連續(xù)下降的次數(shù)Hc；否則，再用步幅step減小參數(shù)p，直到產(chǎn)生更小的類數(shù) Ki。

(8)依此類推,若在迭代的某一步中檢測到Hc＞K1/2(Sil連續(xù)下降表明最優(yōu)結(jié)果已找到)或 K達(dá)到 2，則算法終止，將Silmax對應(yīng)的聚類結(jié)果作為最優(yōu)結(jié)果輸出。若算法終止時Silmax對應(yīng)的聚類個數(shù)K=2,則再計算Hartigan指標(biāo)，判別K=1和K=2哪個更優(yōu)。

(9)輸出最優(yōu)聚類數(shù)目和對應(yīng)的聚類結(jié)果,算法終止。

3 算法性能分析

3.1 仿真實驗

對于本文提出的改進(jìn)算法,依次用ORL、BioID和YALE 3類圖像分別進(jìn)行實驗，并與AP算法的實驗結(jié)果進(jìn)行比較。3類圖像的示例圖片如圖1～圖3所示。實驗結(jié)果如表1所示。

圖1 ORL人臉庫示例圖片

圖2 BioID人臉庫示例圖片

圖3 YALE人臉庫示例圖片

表1 實驗結(jié)果

其中，ORL是提取ORL人臉數(shù)據(jù)庫中的4類人的人臉圖像的HOG特征得到的數(shù)據(jù)集，每類各10張，共40張。BioID是提取BioID人臉數(shù)據(jù)庫中的4類人的人臉圖像的HOG特征得到的數(shù)據(jù)集,每類40張,共160張。YALE是提取YALE人臉數(shù)據(jù)庫中的5類人的人臉圖像的HOG特征得到的數(shù)據(jù)集，每類各10張,共50張。

當(dāng)聚類結(jié)果的錯誤率大于20%時，錯誤率指標(biāo)可能不準(zhǔn)確。因為計算錯誤率程序比較簡單，不能處理復(fù)雜的情況，此時可以采用外部有效性指標(biāo)FM(Fowlkes-Mallows)對聚類結(jié)果的質(zhì)量進(jìn)行評價[11]。FM計算公式為：

其中，C、C′是聚類中兩個不同的類，C11表示在 C、C′上的同一類數(shù)據(jù)對的數(shù)量；C01表示在C′上但不在C上的同一類數(shù)據(jù)對的數(shù)量；C10表示在C上但不在C′上的同一類數(shù)據(jù)對的數(shù)量；C00表示不在C、C′上的同一類數(shù)據(jù)對的數(shù)量。FM值處于0與1之間，且越大表示一致性越好，當(dāng)聚類結(jié)果與正確類標(biāo)完全一致時，F(xiàn)M=1。

3.2 實驗結(jié)果分析

從表1可以看出,在仿射傳播算法中嵌入指標(biāo)，使算法向最好聚類質(zhì)量的方向運行，可得到更加接近正確類數(shù)的類數(shù)、提高FM值、降低錯誤率，可是時間卻沒有節(jié)省；而引入收縮因子之后，加速了AP算法的收斂過程，比單獨嵌入指標(biāo)，時間上明顯減少。

本文首先提取圖像的HOG特征向量，然后用基于HOG的AP改進(jìn)算法對圖像聚類進(jìn)行識別。改進(jìn)算法引入收縮因子調(diào)節(jié)收斂系數(shù)，加速了AP算法的收斂過程，改善了AP算法的收斂性能，并同時將評價聚類質(zhì)量的有效性指標(biāo)嵌入算法的迭代過程，使算法向最好聚類質(zhì)量的方向運行。實驗表明，本文算法對小類數(shù)樣本具有較好的識別能力，不僅得到更接近正確類數(shù)的結(jié)果，較大幅度提高了FM值，還顯著地降低了錯誤率，是一種有效的圖像目標(biāo)識別新算法。

參考文獻(xiàn)

[1]蓋光建.基于圖像的特征信息提取與目標(biāo)識別[D].哈爾濱：哈爾濱理工大學(xué)，2009.

[2]李太勇，吳江，朱波,等.一種基于距離度量的自適應(yīng)粒子群優(yōu)化算法[J].計算機(jī)科學(xué)，2010，37(10)：214-216.

[3]孫焱，和多田淳三，翁培奮.基于粒子群優(yōu)化算法的行人識別與跟蹤方法研究[J].計算機(jī)工程與設(shè)計，2011(3):988-990.

[4]王憲寶，陸飛，陳勇,等.仿生模式識別的算法實現(xiàn)與應(yīng)用[J].浙江工業(yè)大學(xué)學(xué)報，2011，39(1)：71-74.

[5]趙健，唐潔，謝瑜.仿射傳播算法在圖像聚類應(yīng)用中的實現(xiàn)與分析[J].計算機(jī)應(yīng)用研究，2012，29(10)：3980-3982.

[6]何鵬，王福剛，王成琳.基于馬爾科夫隨機(jī)場的爐膛火焰圖像分割[J].電子技術(shù)應(yīng)用，2012,38（11）:133-135.

[7]DALAL N,TRIGGS B.Histograms of oriented gradients for human detection[C].IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Washington,2005,2:886-893.

[8]黃茜，劉軍，彭嘯,等.基于局部二元模式特征的行人檢測[J].計算機(jī)工程與設(shè)計,2011(6):2119-2123.

[9]張璐，陳淑榮.基于ROI區(qū)域強(qiáng)分辨力 HOG特征的視頻行人檢測[J].微型機(jī)與應(yīng)用，2013,32(7):46-49.

[10]DUECKD,FREY B J,JOJICN,et al.Constructing treatment portfolios using affinity propagation[C].Proceedings of International Conference on Research in Computational Molecular Biology(RECOMB),Singapore,Springer,2008:360-371.

[11]DUDOIT S,FRIDLYAND J.A prediction-based resampling method for estimating the number of clusters in a dataset[J].Genome Biology,2002,3(7):1-21.

[12]FREY B J,DUECK D.Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.

[13]陳偉.基于網(wǎng)格的K-means算法與聚類有效性指標(biāo)[D].天津：天津大學(xué)，2009.