储岳中 徐 波 高有涛 邰伟鹏



基于近邻传播聚类与核匹配追踪的遥感图像目标识别方法

储岳中*①②徐 波③高有涛①邰伟鹏②

①(南京航空航天大学航天学院 南京 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)资助课题