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

儲岳中 徐 波 高有濤 邰偉鵬

?

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

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

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

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

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

1 引言

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

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

2 核匹配追蹤算法

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

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

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

應用于模式識別的判決函數為

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

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

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

3.1 近鄰傳播聚類

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

3.2 AP-KMP算法

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

圖1 AP-KMP算法流程圖

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

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

3.3 算法計算復雜度分析

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

4 實驗與分析

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

4.1 UCI數據集

4.2 遙感圖像識別

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

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

5 結束語

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

表2 4個UCI數據集的5種算法參數設置

表3 4個UCI數據集的5種算法訓練時間和錯誤識別率比較

表4不同分類方法識別結果比較

[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]. 計算機學報, 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] 李恒建, 尹忠科, 王建英. 基于量子遺傳優化算法的圖像稀疏分解[J]. 西南交通大學學報, 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]. 電子與信息學報, 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]. 通信學報, 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] 雷陽, 雷英杰, 周創明, 等. 基于直覺模糊核匹配追蹤的目標識別方法[J]. 電子學報, 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]. 儀器儀表學報, 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] 儲岳中, 徐波, 高有濤. 一種融合人工免疫系統與AP算法的分類器設計[J]. 南京航空航天大學學報, 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]. 華中科技大學學報, 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] 肖宇, 于劍. 基于近鄰傳播算法的半監督聚類[J]. 軟件學報, 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年生，博士生，副教授，研究方向為模式識別與機器學習.

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

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

邰偉鵬： 男，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改回

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