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

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

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

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

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

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

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

1.1 HOG

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

1.2 收縮因子

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

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

1.3 指標

(1)Silhouette指標

樣本t的Silhouette指標為:

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

(2)Hartigan指標

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

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

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

2 基于HOG的AP改進算法

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

2.1 算法的主要思想

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

2.2 算法的主要步驟

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

(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指標值Sil1。

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

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

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

3 算法性能分析

3.1 仿真實驗

對于本文提出的改進算法,依次用ORL、BioID和YALE 3類圖像分別進行實驗，并與AP算法的實驗結(jié)果進行比較。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張。

當聚類結(jié)果的錯誤率大于20%時，錯誤率指標可能不準確。因為計算錯誤率程序比較簡單，不能處理復雜的情況，此時可以采用外部有效性指標FM(Fowlkes-Mallows)對聚類結(jié)果的質(zhì)量進行評價[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之間，且越大表示一致性越好，當聚類結(jié)果與正確類標完全一致時，F(xiàn)M=1。

3.2 實驗結(jié)果分析

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

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

參考文獻

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

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

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

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

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

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

[9]張璐，陳淑榮.基于ROI區(qū)域強分辨力 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]陳偉.基于網(wǎng)格的K-means算法與聚類有效性指標[D].天津：天津大學，2009.