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

陳賽英，何建農

(福州大學 數學與計算機科學學院，福建 福州350108)

目前,圖像目標識別算法已經廣泛應用于各個領域，包括軍事、交通、公安、醫學、工業、遙感圖像處理、攝影測量自動化等[1]。

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

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

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

1 相關概念及算法

1.1 HOG

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

1.2 收縮因子

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

在數值實驗中，φ取值為4.1，因此ρ=0.729。收縮因子可以調節收斂系數，以加速收斂過程。

1.3 指標

(1)Silhouette指標

樣本t的Silhouette指標為:

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

(2)Hartigan指標

Hartigan指標適用于類數估計,其滿足Ha≤10的最小類數作為最優的聚類個數:

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

1.4 AP算法

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

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

2 基于HOG的AP改進算法

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

2.1 算法的主要思想

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

2.2 算法的主要步驟

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

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

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

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

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

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

其中，ρ是收縮因子，調節收斂系數λ，以加速AP算法的收斂過程。

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

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

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

(9)輸出最優聚類數目和對應的聚類結果,算法終止。

3 算法性能分析

3.1 仿真實驗

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

圖1 ORL人臉庫示例圖片

圖2 BioID人臉庫示例圖片

圖3 YALE人臉庫示例圖片

表1 實驗結果

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

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

其中，C、C′是聚類中兩個不同的類，C11表示在 C、C′上的同一類數據對的數量；C01表示在C′上但不在C上的同一類數據對的數量；C10表示在C上但不在C′上的同一類數據對的數量；C00表示不在C、C′上的同一類數據對的數量。FM值處于0與1之間，且越大表示一致性越好，當聚類結果與正確類標完全一致時，FM=1。

3.2 實驗結果分析

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

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

參考文獻

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

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

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

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

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

[6]何鵬，王福剛，王成琳.基于馬爾科夫隨機場的爐膛火焰圖像分割[J].電子技術應用，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].計算機工程與設計,2011(6):2119-2123.

[9]張璐，陳淑榮.基于ROI區域強分辨力 HOG特征的視頻行人檢測[J].微型機與應用，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]陳偉.基于網格的K-means算法與聚類有效性指標[D].天津：天津大學，2009.