儲(chǔ)岳中 徐 波 高有濤 邰偉鵬

?

基于近鄰傳播聚類與核匹配追蹤的遙感圖像目標(biāo)識(shí)別方法

儲(chǔ)岳中*①②徐 波③高有濤①邰偉鵬②

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

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

目標(biāo)識(shí)別；近鄰傳播；核匹配追蹤；分類

1 引言

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

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

2 核匹配追蹤算法

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

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

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

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

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

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

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

3.1 近鄰傳播聚類

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

3.2 AP-KMP算法

基于AP聚類的核匹配追蹤算法詳細(xì)步驟如表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 對(duì)數(shù)據(jù)集，計(jì)算相似度矩陣S，并利用相似度的均值初始化偏向參數(shù)p。使用AP算法獲取數(shù)據(jù)集的合適劃分，得到以C個(gè)聚類中心為代表的字典子集；然后對(duì)每一個(gè)子集空間 ，計(jì)算核函數(shù)字典基函數(shù)。步驟2 在每一個(gè)字典子集空間，根據(jù)標(biāo)準(zhǔn)KMP算法，可以得到權(quán)值系數(shù)。從核函數(shù)字典集中，根據(jù)式(5)選擇最小殘差對(duì)應(yīng)的基函數(shù)矢量和權(quán)系數(shù)。步驟3 計(jì)算判決函數(shù)： , L為迭代次數(shù)。步驟4 設(shè)，如果且則返回步驟2，對(duì)每一個(gè)字典子集，迭代次數(shù)L=L+1，否則轉(zhuǎn)步驟5。步驟5 得到分類器，然后利用式(6)識(shí)別目標(biāo)。

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

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

4 實(shí)驗(yàn)與分析

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

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

4.2 遙感圖像識(shí)別

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

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

5 結(jié)束語

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

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

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

表4不同分類方法識(shí)別結(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] 緱水平, 焦李成. 基于多尺度幾何分析與核匹配追蹤的圖像識(shí)別[J]. 模式識(shí)別與人工智能, 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] 李青, 焦李成, 周偉達(dá). 基于模糊核匹配追尋的特征模式識(shí)別[J]. 計(jì)算機(jī)學(xué)報(bào), 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é)報(bào), 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] 緱水平, 焦李成, 張向榮, 等. 基于免疫克隆與核匹配追蹤的快速圖像目標(biāo)識(shí)別[J]. 電子與信息學(xué)報(bào), 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均值聚類核匹配追蹤的彈道中段目標(biāo)識(shí)別方法[J]. 通信學(xué)報(bào), 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)明, 等. 基于直覺模糊核匹配追蹤的目標(biāo)識(shí)別方法[J]. 電子學(xué)報(bào), 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 算法的說話人識(shí)別方法[J]. 儀器儀表學(xué)報(bào), 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] 儲(chǔ)岳中, 徐波, 高有濤. 一種融合人工免疫系統(tǒng)與AP算法的分類器設(shè)計(jì)[J]. 南京航空航天大學(xué)學(xué)報(bào), 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] 儲(chǔ)岳中, 徐波. 基于流形分析與AP算法RBF神經(jīng)網(wǎng)絡(luò)分類器[J]. 華中科技大學(xué)學(xué)報(bào), 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é)報(bào), 2008, 19(11): 2803-2813.

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

儲(chǔ)岳中： 男，1971年生，博士生，副教授，研究方向?yàn)槟Ｊ阶R(shí)別與機(jī)器學(xué)習(xí).

徐 波： 男，1966年生，博士，教授，博士生導(dǎo)師，研究方向?yàn)楹教靹?dòng)力學(xué)與控制.

高有濤： 男，1983年生，博士，講師，研究方向?yàn)樾l(wèi)星編隊(duì)飛行的動(dòng)力學(xué)與控制.

邰偉鵬： 男，1979 年生，博士生，講師，研究方向?yàn)樾盘?hào)與圖像處理.

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

儲(chǔ)岳中 mychu@126.com

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

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