基于近鄰傳播聚類與核匹配追蹤的遙感圖像目標識別方法

儲岳中 徐 波 高有濤 邰偉鵬

?

基于近鄰傳播聚類與核匹配追蹤的遙感圖像目標識別方法

儲岳中*①②徐 波③高有濤①邰偉鵬②

①(南京航空航天大學(xué)航天學(xué)院 南京 210016)②(安徽工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 馬鞍山 243002)③(南京大學(xué)天文與空間科學(xué)學(xué)院 南京 210093)

核匹配追蹤算法在生成函數(shù)字典的過程中常采用貪婪算法進行全局最優(yōu)搜索，導(dǎo)致算法學(xué)習(xí)時間過長。該文針對這一缺陷，提出一種基于近鄰傳播(Affinity Propagation, AP)聚類與核匹配追蹤相結(jié)合的分類方法(AP-Kernel Matching Pursuit, AP-KMP)，該方法利用聚類算法來優(yōu)化核匹配追蹤算法中的字典劃分過程，使用近鄰傳播聚類將目標數(shù)據(jù)集劃分為若干小型字典空間，隨后KMP算法在小型字典空間進行局部搜索，從而縮短學(xué)習(xí)時間。針對部分UCI數(shù)據(jù)集和遙感圖像數(shù)據(jù)集，分別采用AP-KMP算法與另4種經(jīng)典算法進行分類比較實驗，結(jié)果表明該文算法在時間開銷和分類性能上均有一定的優(yōu)越性。

目標識別；近鄰傳播；核匹配追蹤；分類

1 引言

圖像目標識別是模式識別的重要分支，采用核匹配追蹤(KMP)算法作為分類器進行圖像目標識別是近年來提出的一種新型模式識別方法。核匹配追蹤的基本思想是利用核函數(shù)將低維數(shù)據(jù)映射到高維Hilbert空間中，采用樣本間的核函數(shù)值來表示樣本在高維空間中的向量內(nèi)積，并依據(jù)此值構(gòu)成基函數(shù)字典，最后利用貪婪算法求解觀測值的近似[1]。核匹配追蹤分類器的分類性能幾乎與支撐矢量機相當，但比支撐矢量機具有更為稀疏的解，已成功應(yīng)用于目標識別[2]、圖像識別[3,4]和數(shù)據(jù)挖掘[5]等領(lǐng)域。當樣本數(shù)據(jù)規(guī)模較大時，通常情況下核匹配追蹤算法只是隨機選擇訓(xùn)練樣本，所采用的貪婪算法在信號分解的每一步都要對基函數(shù)字典進行全局搜索，很容易導(dǎo)致計算量過大，分類器的識別性能也不穩(wěn)定。近年來，很多學(xué)者提出算法來降低匹配追蹤算法的計算量。文獻[6]采用量子遺傳優(yōu)化，文獻[7]利用免疫克隆的全局高效尋優(yōu)能力來克服核匹配追蹤算法計算量大、耗時長的缺陷，文獻[8]等利用直覺FCM算法將KMP算法中核字典劃分成若干個小字典，在此基礎(chǔ)上進行局部搜索，有效克服了KMP算法因全局搜索導(dǎo)致耗時長的缺陷。文獻[9]將遺傳算法用于匹配追蹤，提出進化追蹤原子分解，并提出一種多字典原子分解實現(xiàn)方法，但該方法存在字典存儲量大的問題。文獻[2]提出一種最優(yōu)方向法與廣義K均值聚類相結(jié)合的方法，用于核匹配追蹤函數(shù)字典的學(xué)習(xí)，實驗表明能較好地提高具有高維特征的稀疏信號擬合性能，尤其適合有一定衰減的信號。文獻[10]針對高維大數(shù)據(jù)集，提出一種改進的核梯度匹配追蹤算法，對所獲得的基向量集進行正交約束限制，在手寫數(shù)字識別和語音識別上取得了較好的效果。

近年來，為了對圖像進行更為準確的描述與識別，往往會引入多種特征描述方法，導(dǎo)致圖像特征信息非常豐富，若采用核匹配追蹤分類器對圖像目標直接識別，往往效果不佳，為此可采用聚類方法對圖像特征矩陣進行聚類分析，在保持圖像有用信息的同時，盡可能簡化圖像數(shù)據(jù)的分布信息，在此基礎(chǔ)上再采用核匹配追蹤分類器進行圖像目標識別，將有效縮短訓(xùn)練時間，并提高識別率。本文的研究目的是將近鄰傳播聚類算法融入核匹配追蹤學(xué)習(xí)機，用于圖像特征數(shù)據(jù)的分類，為圖像目標識別探索一種新的方法。為此，本文提出一種基于近鄰傳播聚類與核匹配追蹤融合的圖像目標識別算法(AP-KMP)。為驗證算法性能，首先通過UCI數(shù)據(jù)集和遙感圖像數(shù)據(jù)進行分類實驗與測試，然后，針對本文算法與現(xiàn)有相關(guān)算法做比較實驗，實驗結(jié)果表明AP-KMP算法用于圖像目標識別時，較已有經(jīng)典算法在時間開銷與識別率上具有一定的優(yōu)越性。

2 核匹配追蹤算法

2.1 基本匹配追蹤(Basic Matching Pursuit, BMP)算法

式(4)所表示的優(yōu)化過程顯然非常耗時，通常采用折中的方法：在迭代運算結(jié)束后僅進行一次后擬合[11]。

2.2 正交核匹配追蹤(Orthogonal Kernel Matching Pursuit, OKMP)算法

應(yīng)用于模式識別的判決函數(shù)為

核匹配追蹤受啟發(fā)于支撐矢量機，但對核函數(shù)的要求沒有支撐矢量機嚴格，一方面不必滿足Mercer條件，另一方面可以選擇多個不同核函數(shù)來生成函數(shù)字典。

3 基于近鄰傳播聚類核匹配追蹤算法

關(guān)于聚類算法在核匹配追蹤中的應(yīng)用，文獻[8]等提出了基于直覺模糊C均值聚類(FCM)算法的核匹配追蹤算法，并用于彈道中段目標識別。文獻[14]等將粒子群優(yōu)化算法與模糊C均值聚類相結(jié)合提出一種粒子群聚類方法，并將其應(yīng)用于說話人梅爾倒譜系數(shù)個性特征參數(shù)提取，在此基礎(chǔ)上構(gòu)建核匹配追蹤分類器以完成說話人識別。但是，F(xiàn)CM算法對初始聚類中心和初始聚類數(shù)選擇敏感，同時易陷入局部最優(yōu)，這在一定程度上限制了該方法在匹配追蹤算法中應(yīng)用。

3.1 近鄰傳播聚類

近鄰傳播(AP)算法是文獻[15]提出的一種動態(tài)聚類算法，該算法是根據(jù)樣本之間的相似度矩陣進行聚類，但不需要事先指定初始聚類數(shù)目，算法運行中將所有的樣本點都作為潛在的聚類中心，避免了傳統(tǒng)聚類算法中的聚類結(jié)果受限于初始類代表點的選擇，算法傳播的是每一數(shù)據(jù)點與最近鄰點或次近鄰點間的信息，故稱為近鄰傳播算法[16]。與傳統(tǒng)聚類算法相比，AP算法在大多數(shù)據(jù)集上的聚類時間開銷均有優(yōu)越性，聚類結(jié)果也比較穩(wěn)定。為此，本文提出了一種基于AP聚類的核匹配追蹤目標識別方法，用于遙感圖像目標識別。

3.2 AP-KMP算法

基于AP聚類的核匹配追蹤算法詳細步驟如表1所示，圖1為本算法的流程圖。

圖1 AP-KMP算法流程圖

表1基于AP聚類的核匹配追蹤算法(AP-KMP)

輸入 樣本數(shù)據(jù)集, RBF核函數(shù)的核參數(shù), AP算法最大迭代次數(shù)B, KMP算法最大迭代次數(shù)T，誤差閾值。輸出 函數(shù)字典，最優(yōu)權(quán)系數(shù)和基函數(shù)數(shù)據(jù)，判決函數(shù)。步驟1 對數(shù)據(jù)集，計算相似度矩陣S，并利用相似度的均值初始化偏向參數(shù)p。使用AP算法獲取數(shù)據(jù)集的合適劃分，得到以C個聚類中心為代表的字典子集；然后對每一個子集空間 ，計算核函數(shù)字典基函數(shù)。步驟2 在每一個字典子集空間，根據(jù)標準KMP算法，可以得到權(quán)值系數(shù)。從核函數(shù)字典集中，根據(jù)式(5)選擇最小殘差對應(yīng)的基函數(shù)矢量和權(quán)系數(shù)。步驟3 計算判決函數(shù)： , L為迭代次數(shù)。步驟4 設(shè)，如果且則返回步驟2，對每一個字典子集，迭代次數(shù)L=L+1，否則轉(zhuǎn)步驟5。步驟5 得到分類器，然后利用式(6)識別目標。

3.3 算法計算復(fù)雜度分析

對于基本KMP算法，在迭代分解的每一步都要對基函數(shù)字典進行全局搜索，這里通過分析一次匹配的情況來評估算法的計算量。如果字典規(guī)模為，迭代次數(shù)，顯示KMP算法一次匹配的時間復(fù)雜度為()[7]。對于AP-KMP算法，設(shè)通過AP算法劃分的小字典空間平均規(guī)模為n(n<)，因此KMP算法一次匹配的時間復(fù)雜度為(nt)，顯然這種基函數(shù)字典的劃分有效提高了算法的時間復(fù)雜性，當字典規(guī)模越大，這種劃分的意義就越大。

4 實驗與分析

為了驗證本文算法的性能，本文設(shè)計兩組實驗，分別選擇UCI數(shù)據(jù)集和遙感圖像數(shù)據(jù)進行分類測試，并將樣本分為訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集，采用多重交叉實驗來驗證算法的平均性能。

4.1 UCI數(shù)據(jù)集

4.2 遙感圖像識別

本文參考文獻[7]的實驗策略，采用的圖像樣本是經(jīng)過圖像分割，將圖像目標與背景分離而得到的128×128的飛機和艦船二值遙感圖像，包括目標的各種姿態(tài)及殘缺情況下的樣本，共計852幅，其中飛機511幅，艦船341幅，部分圖像示例如圖2所示。對所有圖像進行基于Hu不變矩的形狀特征提取，每幅圖像可得7維特征向量。實驗中取30%樣本作為訓(xùn)練樣本，其余作為測試樣本。依然使用前文5種算法采用十重交叉做比較實驗，相關(guān)參數(shù)設(shè)置參考表2，少量微調(diào)。實驗結(jié)果如表4所示。結(jié)果表明，本文算法平均訓(xùn)練時間與FCM-KMP算法相當，較另3個算法有所改善，而平均測試時間在所有算法中最短，平均識別率也有較大幅度提高。

圖2 含有部分艦船和飛機的遙感圖像示例

5 結(jié)束語

核匹配追蹤算法通過核映射將輸入樣本映射到高維特征空間，由核函數(shù)來構(gòu)成基函數(shù)字典，實現(xiàn)了非線性問題的處理，但為了獲取一個較優(yōu)的字典劃分需要大量計算，導(dǎo)致計算時間過長，影響它的實際應(yīng)用。核匹配追蹤學(xué)習(xí)過程花費的時間是與訓(xùn)練規(guī)模的大小成比例的，因此本文提出了利用AP聚類算法對訓(xùn)練數(shù)據(jù)集的規(guī)模進行壓縮，在保存核匹配追蹤統(tǒng)計信息的同時，自動搜索最佳聚類類別數(shù)來控制基函數(shù)字典訓(xùn)練的規(guī)模，從而達到算法速度和識別率的折中。通過對UCI數(shù)據(jù)和遙感圖像數(shù)據(jù)進行識別測試，實驗結(jié)果表明本文方法能夠有效減少訓(xùn)練時間，從而可以控制算法的識別性能和計算時間二者之間的平衡。

表2 4個UCI數(shù)據(jù)集的5種算法參數(shù)設(shè)置

表3 4個UCI數(shù)據(jù)集的5種算法訓(xùn)練時間和錯誤識別率比較

表4不同分類方法識別結(jié)果比較

[1] Pascal V and Yoshua B. Kernel matching pursuit[J]., 2002, 48(1): 165-187.

[2] Nguyen H V and Nasser M N. Design of non-linear kernel dictionaries for object recognition[J]., 2013, 22(12): 5123-5135.

[3] 緱水平, 焦李成. 基于多尺度幾何分析與核匹配追蹤的圖像識別[J]. 模式識別與人工智能, 2007, 20(6): 776-781.

Gou Shui-ping and Jiao Li-cheng. Image recognition based on multi-scale geometric analysis and kernel matching pursuit[J]., 2007, 20(6): 776-781.

[4] 李青, 焦李成, 周偉達. 基于模糊核匹配追尋的特征模式識別[J]. 計算機學(xué)報, 2009, 32(8): 1687-1694.

Li Qing, Jiao Li-cheng, and Zhou Wei-da.Pattern recognition based on the fuzzy kernel matching pursuit[J]., 2009, 32(8): 1687-1694.

[5] Ramin P, Hossein N Z, and Louis T. Auditory-inspired sparse representation of audio signals[J]., 2011, 53(5): 643-657.

[6] 李恒建, 尹忠科, 王建英. 基于量子遺傳優(yōu)化算法的圖像稀疏分解[J]. 西南交通大學(xué)學(xué)報, 2007, 42(1): 19-23.

Li Heng-jian, Yin Zhong-ke, and Wang Jian-ying. Image sparse decomposition based on quantum genetic algorithm[J]., 2007, 42(1): 19-23.

[7] 緱水平, 焦李成, 張向榮, 等. 基于免疫克隆與核匹配追蹤的快速圖像目標識別[J]. 電子與信息學(xué)報, 2008, 30(5): 1104-1108.

Gou Shui-ping, Jiao Li-cheng, Zhang Xiang-rong,. Kernel matching pursuit based on immune clonal fast algorithm for image object recognition[J].&, 2008, 30(5): 1104-1108.

[8] 雷陽, 孔韋韋, 雷英杰. 基于直覺模糊c均值聚類核匹配追蹤的彈道中段目標識別方法[J]. 通信學(xué)報, 2012, 33(11): 136-143.

Lei Yang, Kong Wei-wei, and Lei Ying-jie. Technique for target recognition based on intuitionistic fuzzy c-means clustering and kernel matching pursuit[J]., 2012, 33(11): 136-143.

[9] Adelino R and Sliva F D. Atomic decomposition with evolutionary pursuit[J]., 2003, 13(2): 317-337.

[10] Kubo Y, Watanabe S, Nakamura A,.. Basic vector orthogonalization for an improved kernel gradient matching pursuit method[C]. 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, Japan, 2012: 1909-1912.

[11] 雷陽, 雷英杰, 周創(chuàng)明, 等. 基于直覺模糊核匹配追蹤的目標識別方法[J]. 電子學(xué)報, 2011, 39(6): 1441-1446.

Lei Yang, Lei Ying-jie, Zhou Chuang-ming,.. Techniques for target recognition based on intuitionistic fuzzy kernel matching pursuit[J]., 2011, 39(6): 1441-1446.

[12] Jiao L C and Li Q. Kernel matching pursuit classifier ensemble[J]., 2006, 39(4): 587-594.

[13] Zhao S L, Wu P, and Liu Y P. An online kernel learning algorithm based on orthogonal matching pursuit[J]., 2012, 7(9): 2076-2082.

[14] 安冬, 榮超群, 楊丹, 等. 基于PSOA 聚類和KMP 算法的說話人識別方法[J]. 儀器儀表學(xué)報, 2013, 34(6): 1306-1311.

An Dong, Rong Chao-qun, Yang Dan,.. Speaker recognition method based on PSOA clustering and KMP algorithm[J]., 2013, 34(6): 1306-1311.

[15] Frey B J and Dueck D. Clustering by passing messages between data points[J]., 2007, 315(5814): 972-976.

[16] 儲岳中, 徐波, 高有濤. 一種融合人工免疫系統(tǒng)與AP算法的分類器設(shè)計[J]. 南京航空航天大學(xué)學(xué)報, 2013, 45(2): 232-238.

Chu Yue-zhong, Xu Bo, and Gao You-tao. Design of classifier based on combination of artificial immune system and AP algorithm[J].&, 2013, 45(2): 232-238.

[17] 儲岳中, 徐波. 基于流形分析與AP算法RBF神經(jīng)網(wǎng)絡(luò)分類器[J]. 華中科技大學(xué)學(xué)報, 2012, 40(8): 93-97.

Chu Yue-zhong and Xu Bo. RBF neural network classifier based on manifold analysis and AP algorithm[J].&, 2012, 40(8): 93-97.

[18] 肖宇, 于劍. 基于近鄰傳播算法的半監(jiān)督聚類[J]. 軟件學(xué)報, 2008, 19(11): 2803-2813.

Xiao Yu and Yu Jian. Semi-supervised clustering based on affinity propagation algorithm[J]., 2008, 19(11): 2803-2813.

儲岳中： 男，1971年生，博士生，副教授，研究方向為模式識別與機器學(xué)習(xí).

徐 波： 男，1966年生，博士，教授，博士生導(dǎo)師，研究方向為航天動力學(xué)與控制.

高有濤： 男，1983年生，博士，講師，研究方向為衛(wèi)星編隊飛行的動力學(xué)與控制.

邰偉鵬： 男，1979 年生，博士生，講師，研究方向為信號與圖像處理.

Technique of Remote Sensing Image Target Recognition Based onAffinity Propagation and Kernel Matching Pursuit

Chu Yue-zhong①②Xu Bo③Gao You-tao①Tai Wei-peng②

①(,,210016,)②(,,’243002,)③(&,,210093,)

The processing of generating dictionary of function in Kernel Matching Pursuit (KMP) often uses greedy algorithm for global optimal searching, the dictionary learning time of KMP is too long. To overcome the above drawbacks, a novel classification algorithm (AP-KMP) based on Affinity Propagation (AP) and KMP is proposed. This method utilizes clustering algorithms to optimize dictionary division process in KMP algorithm, then the KMP algorithm is used to search in these local dictionary space, thus reducing the computation time. Finally, four algorithms and AP-KMP are carried out respectively for some UCI datasets and remote sensing image datasets, the conclusion of which fully demonstrates that the AP-KMP algorithm is superior over another four algorithms in computation time and classification performance.

Target recognition; Affinity Propagation (AP); Kernel Matching Pursuit (KMP); Classification

TP391.4

A

1009-5896(2014)12-2923-06

10.3724/SP.J.1146.2014.00422

儲岳中 mychu@126.com

2014-03-21收到，2014-06-05改回

國家自然科學(xué)基金(11078001)和國家863計劃項目(2012AA121602)資助課題