用于遥感图像目标快速匹配识别的改进混合溢出树算法

陈彦彤，徐　伟，朴永杰，王灿进，陈　娟

(1.中国科学院 长春光学精密机械与物理研究所，吉林 长春 130033；2.中国科学院大学，北京 100049)



用于遥感图像目标快速匹配识别的改进混合溢出树算法

陈彦彤1，2，徐伟1*，朴永杰1，王灿进1，陈娟1

(1.中国科学院 长春光学精密机械与物理研究所，吉林 长春 130033；2.中国科学院大学，北京 100049)

提出一种基于标记的混合溢出树(SHSPT)特征匹配算法，用于遥感图像的目标匹配识别。针对特征数据建立和预处理，提出了基于中心点的数据分割方法，通过定义数据密集区域的中心，舍去边缘稀疏数据，提取出分割后的数据。进行特征匹配时，使用二进制数组表示数据空间，标记分割后的特征向量数据，通过比特操作计算特征向量间的距离，缩短计算时间。最后对特征匹配方法进行改进，采用待匹配特征距离的均值代替尺度不变特征变换(SIFT)匹配算法的次临近特征距离，从而得到更多的匹配点。实验证明，基于标记的混合溢出树特征匹配算法占用内存空间比传统的混合溢出树算法减少约68%，匹配准确度与原算法接近，匹配时间平均缩短了约32.8%，解决了航天遥感图像数据量大，特征维数较高，匹配识别时间长，占用计算机内存大等问题。

遥感目标识别；特征标记；数据分割；图像匹配；混合溢出树算法

1　引　言

近年来，我国航天遥感技术不断发展，遥感图像在空间分辨率、时间分辨率和光谱分辨率方面不断提高，其应用领域也愈加广阔[1]。特别是在军事方面，遥感图像目标匹配识别对于战场侦察、战术规划、军事测绘、海洋监测等都有着重要的战略意义[2-3]。

目标匹配识别技术[4-7]主要是利用特征匹配来识别目标，特征匹配是从两组特征点集中找到两两距离最临近的特征匹配对，匹配对的集合即为所识别到的目标[8-10]。目前寻找特征匹配对的方法大致可分为两种，一种是穷举法[11]，即将数据集中的点与查询点逐一进行距离比较，这种方法不需要进行数据预处理，实现简单，但是搜索效率较低，不适用于大规模数据集的检索；第二种是建立数据索引，然后进行快速匹配，例如M-tree[12]搜索算法、Kd-tree[13]搜索算法、宽度优先搜索算法(Breadth First Search，BFS)[14]等。这些搜索算法虽然提高了搜索效率，但为保证搜索的准确性，需要耗费大量的时间进行“回溯”操作，降低了搜索速度。

针对这个问题，学者们提出了很多改进方案。其中Lee提出了Spill-tree算法[15]，采用冗余分割的方式，避免了回溯操作，但同时也降低了查询的准确率；Moore提出了Hybrid Spill-tree的搜索策略[16]，该方法结合了M-tree的深度优先搜索算法(Depth First Search，DFS)[17]和Spill-tree的冗余分割算法，在非重叠结点使用回溯搜索，在重叠结点使用失败搜索，从而提高了查询精度，也适用于较高维数据的检索，但面对遥感图像大规模的数据量，仍然不能满足快速处理的需求。

目前对于遥感图像的特征匹配仍然存在以下问题：(1)遥感图像背景复杂，特征数据分布较广，这给建立数据索引时的数据分割带来了困难；(2)遥感图像数据量巨大，且生成的特征维数较高，给算法的计算效率和计算机存储带来挑战；(3)在高分辨情况下，特征的独特性不高，传统的特征匹配方法会导致大量的误匹配。针对这些问题，本文提出了适用于遥感图像的基于标记的混合溢出树特征匹配识别方法(Signed Hybrid Spill-tree，SHSPT)，首先通过筛选数据中心点的分割方式，更准确地对大规模遥感数据进行分割；然后应用基于二进制标记的方法，提高特征匹配速度，降低计算机存储占用空间；最后通过改进尺度不变特征变换(Scale Invariant Feature Transform，SIFT)的特征匹配方法，提出了基于比值的K临近均值匹配，从而能得到更多的匹配点，并去除误匹配点，优化匹配结果。

2　中心点数据分割

数据分割是建立数据索引的第一步，Hybrid Spill-tree算法通过选取给定数据集中距离最远的点作为端点，然后将数据以递增的方式排序，采用冗余分割的方式把数据平均分为两组。但在实际应用中，往往会因为数据分布的不均匀或偏移较大，导致冗余分割后的重叠节点较少。根据文献[13]方法，对一组分布不均匀的二维数据集{a，b，c，d，e，f，g，h，i}进行分割，若采取平均分割的方式，则数据集被分为{a，b，c，d，e，f}和{g，h，i}，如图1(a)所示。若以中心点e为分割点，虽然数据被平均分为{a，b，c，d，e}和{e，f，g，h，i}，但依然无法判断处于冗余区域中待匹配点的归属问题，如图1(b)所示。

(a)平均分割方式(a)Average separate method(b)中心点分割方式(b)Center point separate method

本文采用基于“中心点”的方法，构建分裂树。假定数据集为{a，b，c，d，e，f，g，h，i}，具体步骤如下：

(1)以中心点e(mid)作为数据中心，令数据密集端的a点作为左端点(left point)，在右端选取到e的距离与a到e的距离最接近的点作为右端点(right point)，在这里为h点，然后舍去数据稀疏端的边缘点i，如图2所示。

图2　中心点的分割示意图

(2)过中心点e作一条垂直于坐标轴的直线L，将数据集平均分为两部分，再作两条与L距离都为t的平行分割直线LL和LR，将它们分别作为区域RC与LC的边界，在坐标轴上选取距离右端点为2t的两点M、N，这样就将数据分为3组，如图3所示。

图3　分裂树构建示意图

(3)对于数据集中的任意一点x，定义x到左端点的距离为D(left，x)，x到M的距离为D(M，x)，x到N的距离为D(N，x)，则：

(1)

原数据集被冗余分割为两组，其中LC={a，b，c，d，e}，RC={d，e，f，g，h}，重叠部分为{d，e}。

3　二进制数据标记

二进制数据能够大幅降低计算机的存储空间，并且简化数据运算。根据二维数据集{a，b，c，d，e，f}，以点的形式在坐标轴上表示，因此，本文提出将平面划分为不同的区域，把数据集以区域代码的形式表示出来，如图4所示。

图4　二进制数据空间

通过二进制数据空间，将数据集以二进制的形式表示出来，如表1所示。

表1　标记后的数据集

二进制数组将数据空间划分为16个数据子空间，根据二进制数据空间，原始数据被转换为二进制数组的形式，但会出现不同数据对应同一标记的情况，如表1中：c(0.3，0.7)，d(0.4，0.6)，对应同一标记0110。根据二进制数据空间，不同数据对应同一标记的概率P为：

P=(1/2n)D，

(2)

其中：n为二进制数据空间的比特个数；D为数据的向量维数。在实际应用中，由于遥感图像的特征维数较高，这种情况发生的概率较小，因此并不会影响最终的匹配识别结果。

4　SHSPT特征匹配

针对遥感图像数据量大、特征分布广的特点，本文提出基于二进制标记的SHSPT数据搜索算法，其构造过程如下：首先对每个SIFT算法生成的128维遥感图像特征数据进行标记处理，将特征数据的两个维度作为一组，共需要标记64组，如图5所示。为了提高标记的精度，采用4位二进制数进行标记，因此可将特征空间划分为256(24×24)个子空间。

图5　遥感图像特征标记方式

然后由Hybrid Spill-tree算法和中心点数据分割方法可知，阈值ρ<1，实验中取为0.7。对每个根结点v，设其包含的点数为N(v)，使用重叠缓冲区分裂点集，若其任意子结点包含的点数超过ρ*N(v)，则停止分裂，将t设为0，即该结点的左右子树没有重叠区域，并且标记v为一个非重叠的结点；若该结点的两个子结点包含的点数均不超过ρ*N(v)，则标记为重叠结点。这样可以保证每次分裂后，子结点包含的点数均小于父结点包含的点数，最后SHSPT的索引深度为O(log(n))。

SHSPT算法中，在非重叠结点使用回溯搜索，在重叠结点使用Defeatist搜索，通过标记数据，可以在特征匹配阶段使用异或运算，以大幅提高匹配速度。

5　基于比值的K临近均值匹配

原有的SIFT特征匹配利用最邻近匹配特征d(1)和次邻近匹配特征d(2)的比值[18]，如公式(3)所示：

d(1)/d(2)≤t.

(3)

(4)

实验中K取总数据的5%，t=0.85toriginal，toriginal与原匹配方法的阈值相同时，认为特征正确匹配。

6　实验结果与分析

为了验证算法的效率，本文取M-tree、Hybrid Spill-tree算法作为对比算法，做了3组实验：(1)3种算法占用计算机内存空间统计实验；(2)特征匹配准确度对比实验；(3)特征匹配时间对比实验。本文实验的硬件环境为：Intel(R) Core(TM) i5-4570 CPU@3.2 GHz，4 G内存，Window 7系统；实验软件平台为Visual Studio2010 + OpenCV 2.4.11。实验选用美国Astrium和Digital Globe公司的高分辨遥感影像数据库中的600幅图像进行算法验证，其中包含Spot6卫星拍摄的像元分辨率为1.5 m的图像200幅，以图6(a)为例；QuickBird卫星拍摄的像元分辨率为0.61 m的图像200幅，以图6(b)为例；WorldView-2卫星拍摄的像元分辨率为0.5 m 的图像200幅，以图6为例。

(a)北京机场图像(a)Beijing airport　(b)墨西哥机场图像(b)Mexico airport　(c)纽约机场图像(c)New York airport

6.1计算机内存占用实验

实验中使用M-tree、Hybrid Spill-tree、SHSPT三种算法，对SIFT提取到的特征进行匹配识别，其中3幅遥感图像中包含的特征向量数据分别为2 721组、4 177组和10 782组，每个数据为128维，图7(彩图见期刊电子版)显示的是3种算法计算机内存占用情况对比。

图7　3种算法占用内存对比

如图7所示，M-tree算法平均占用内存量为63.03 MB，占用量适中；而Hybrid Spill-tree算法平均占用内存量为103.7 MB，占用量较大，这主要因为其采用了冗余分割的算法，处于冗余区域的特征数据需要重复占用内存空间，从而增大了内存消耗；SHSPT算法平均占用内存仅为33.2 MB，相比于Hybrid Spill-tree算法减少了68%。这是因为SHSPT将提取到的特征向量转变为了二进制数组，在计算机的存储机制中，原有算法为浮点型数据，每个数据需要4个字节的存储空间，即32比特，而本文算法中每两组数据仅需1个字节即8比特数据，大幅节省了占用空间。

6.2特征匹配识别精确度比较

遥感图像目标匹配识别的关键因素是匹配识别的精确程度，实验中使用3种算法对3幅遥感图像分别进行飞机目标的匹配识别，但本文算法使用了改进后的匹配方法，识别结果如图8～10(彩图见期刊电子版)所示。

(a)M-Tree(b)Hybrid Spill-Tree(c)SHSPT

(a)M-Tree　(b)Hybrid Spill-Tree　(c)SHSPT

(a)M-Tree　(b)Hybrid Spill-Tree　(c)SHSPT

从实验结果可以看出，M-tree算法的匹配准确度最好，Hybrid Spill-Tree算法和本文算法由于都采用了冗余分割的方式，导致误匹配点增加，但本文算法通过改进特征匹配方法，获得了更多的匹配点，最终提高了匹配识别的正确率，结果优于Hybrid Spill-Tree算法，且与M-tree 算法的准确率接近。表2为3种算法匹配识别正确率的统计结果。

表2　3种算法匹配识别正确率比较

6.3计算复杂度比较

在计算复杂度对比实验中，分别比较了3种算法在特征匹配上的耗时，并得到每种算法的总耗时，如表3所示。

从表3可以看出，M-tree算法的耗时最长，这主要因为其采用了回溯的搜索方式，Hybrid Spill-tree算法耗时次之，而本文算法耗时最短，且随着图像特征点的增加，算法的优势更加明显。这是因为本文方法采用了二进制的匹配方式，在匹配时可以通过异或方式计算特征间的距离，比传统的计算欧式距离的方法计算量更小。

表3　特征提取算法耗时比较

7　结　论

本文在Hybrid Spill-tree算法的基础上，提出一种基于标记的混合溢出树的特征匹配算法，并应用于遥感图像的目标匹配识别。在特征数据建立和预处理阶段，采用基于中心点的分割方式，解决了由于数据偏移导致的冗余分割区域特征点过少的问题；在特征匹配阶段，采用标记的方式，将遥感图像特征向量转换为二进制数据，以减少计算机内存消耗，并通过异或运算度量特征向量间的距离，以缩短计算时间；最后改进了SIFT特征匹配方法，采用K邻近匹配特征距离的均值代替次邻近距离，最大限度地保留了匹配特征点。实验证明，应用SHSPT搜索算法对遥感图像进行目标匹配识别时，计算机内存占用量较传统算法减少约68%，匹配的准确度更高，耗时缩短了约32.8%，适用于遥感图像目标的快速匹配识别。

[1]金光，徐伟. “吉林一号”小型高分辨率多光谱遥感卫星[J]. 空间对地观测工程与技术，2014，12(2)：25-32.

JIN G， XU W. Light weight high resolution multispectral small satellite [J].SpaceEarthObservationEngineeringAndTechnology， 2014， 12(2): 25-32. (in Chinese)

[2]陈彦彤，王绍举. 高分辨遥感图像目标识别技术综述[J]. 中国光学，2014，7(增)：17-23.CHEN Y T， WANG SH J. Review of target recognition technology for high resolution remote sensing image [J].ChineseOptics， 2014， 7(S): 17-23. (in Chinese)

[3]张仲瑜，焦淑红. 多特征融合的红外舰船目标检测方法[J]. 红外与激光工程，2015，44(增)：29-34.

ZHANG ZH Y， JIAO SH H. Infrared ship target detection method based on multiple feature fusion [J].InfraredandLaserEngineering， 2015， 44(S): 29-34. (in Chinese)

[4]田浩南，张叶. 基于边缘及特征点匹配的立体图像质量评价[J]. 液晶与显示，2015，30(4)：666-672.

TIAN H N， ZHANG Y. Quality evaluation of stereo image based on edge and characteristic point matching [J].ChineseJournalofLiquidCrystalsandDisplays， 2015， 30(4): 666-672. (in Chinese)

[5]BURGHARDT T， DAMEN D. Correspondence，matching and recognition [J].InternationalJournalofComputerVision， 2015， 113(3): 161-162.

[6]赵立荣，朱玮，曹永刚，等. 改进的加速鲁棒特征算法在特征匹配中的应用[J]. 光学 精密工程，2013，21(12)：3263-3271.ZHAO L R， ZHU W， CAO Y G，etal.. Application of improved SURF algorithm to feature matching [J].Opt.PrecisionEng.， 2013， 21(12): 3263-3271. (in Chinese)[7]张博研，李广泽，武星星. Quickbird遥感影像的车辆自动检测与运动参数估计[J]. 液晶与显示，2015，30(4)：687-694.

ZHANG B Y， LI G Z， WU X X. Speed estimation and automatic detection of moving vehicle from Quickbird satellite image [J].ChineseJournalofLiquidCrystalsandDisplays， 2015， 30(4): 687-694. (in Chinese)

[8]ZAMIR A R， SHAH M. Image Geo-Localization based on multiple nearest neighbor feature matching using generalized graphs [J].IEEETrans.onPatternAnalysisandMachineIntelligence， 2014， 36(8): 1546-1558.

[9]邵振峰，陈敏. 尺度旋转以及亮度稳健的高分辨率影像直线特征匹配[J]. 光学 精密工程，2013，21(3)：790-798.

SHAO ZH F， CHEN M. Line-based matching for high-resolution images with robustness for scale， rotation andillumination [J].Opt.PrecisionEng.， 2013， 21(3): 790-798. (in Chinese)

[10]王志强，程红，杨桄，等. 全局图像配准的目标快速定位方法[J]. 红外与激光工程，2015，44(增)：225-229.

WANG ZH Q， CHENG H， YANG G，etal.. Fast target location method of global image registration [J].InfraredandLaserEngineering， 2015， 44(S): 225-229. (in Chinese)

[11]CHOI H H， BAE S J. Fast parallelk-NN search in high-dimensional spaces[C].Proc.oftheFourthInternationalConferenceonCreativeContentTechnologies， 2012: 32-37.

[12]LIU B Y， SADEGHI F， TAPPEN M. Probabilistic label trees for efficient large scale image classification [C]. 2013IEEEConferenceonComputerVisionandPatternRecognition(CVPR)， 2013: 843-850.

[13]BINDICK S， STIEBLER M， KRAFCZYK M. Fast kd-tree-based hierarchical radiosity for radiative heat transport problems [J].InternationalJournalforNumericalMethodsinEngineering， 2011， 86(9): 1082-1100.

[14]CHEN Y， XU M， LIU H L，etal.. An improved image mosaic based on Canny edge and an 18-dimensional descriptor [J].Optik， 2014， 125(17): 4745-4750.

[15]LI Z H， NEE A Y C， ONG S K，etal.. Tampered image detection using image matching [C]. 5thInternationalConferenceonComputerGraphics，ImagingandVisualization(CGIV)， 2008: 174-179.

[16]LEE H J， KIM H L， CHANG J W. An efficient high-dimensional indexing scheme using a clustering technique for content-based retrieval [C].Proc.oftheInternationalConferenceonComputationalScienceandEngineering， 2009: 318-323.

[17]MAHMUD M S， SARKER U， ISLAM M M. A greedy approach in path selection for DFS based maze-map discovery algorithm for an autonomous robot [C].Proc.ofInternationalConferenceonComputerandInformationTechnology(ICCIT)， 2012: 22-24.

[18]ANDREA COSTANZO， IRENE AMERINI， ROBERTO CALDELLI. Forensic analysis of SIFT keypoint removal and injection [J].IEEETrans.OnInformationForensicsandSecurity， 2014， 9(9): 1450-1464.

陈彦彤(1989-)，男，辽宁沈阳人，博士研究生，2012年于吉林大学获得学士学位，主要从事模式识别及机器视觉方面的研究。E-mail: chenyantong1@yeah.net

导师简介：

徐伟(1981-)，男，黑龙江大庆人，博士，研究员，2003年于吉林大学获得学士学位，2008年于中国科学院长春光学精密机械与物理研究所获得博士学位，主要从事星载一体化卫星技术及高可靠一体化航天电子学系统等方面的研究。E-mail: xwciomp@126.com

(版权所有未经许可不得转载)

Improved hybrid spill-tree algorithm for fast target matching recognition of satellite images

CHEN Yan-tong1， 2， XU Wei1*， PIAO Yong-jie1， WANG Can-jin1， CHEN Juan1

(1.ChangchunInstituteofOptics，FineMechanicsandPhysics，ChineseAcademyofSciences，Changchun130033，China；2.UniversityofChineseAcademyofSciences，Beijing100049，China)*Correspondingauthor，E-mail：xwciomp@126.com

An improved Hybrid Spill-tree algorithm based on the signed method defined as Signed Hybrid Spill-tree (SHSPT) was proposed for target matching of remote sensing images. For establishing data and preprocessing， a data separate method based on a center point was proposed， the separated data were extracted by defining the center of dense data， and the edge data were abandoned. In the feature matching， binary array were used to express the data space and to mark the feature vector. Then， the bit operation was used to compute the distance between the feature vectors and to shorten the computing time. Finally， the feature matching algorithm was improved. The average value of the feature distance was used to replace the secondary characteristic distance from the Scale Invariant Feature Transform(SIFT)matching algorithm to obtain more matching points. The test results show that the computer memory by proposed algorithm is reduced 68% than that of traditional hybrid spill-tree method， and matching accuracy is closed to that of the traditional one. In addition， the method reduces 32.8% matching time. It solves the problems of remote sensing images in larger data amounts， higher dimensions， longer matching time and larger computer memory.

remote target recognition; feature mark; data partition; image matching; hybrid spill-tree algorithm

2016-01-18；

2016-03-04.

国家863高技术研究发展计划资助项目(No.2012AA121502)

1004-924X(2016)09-2310-08

TP753

A

10.3788/OPE.20162409.2310