图像配准是图像应用的关键步骤(Wei等，2017; Yang等，2017; Eastman等，2011; Zhao等，2020; Chen等，2015)，一般包括局部不变特征点匹配、直线匹配和区域匹配等算法(贾迪等，2019)，以及局部不变特征与区域匹配结合等算法(Feng等，2019b; 许斌等，2018)。目前的遥感图像匹配方法主要有基于区域和基于特征的方法及针对山地影像的光流跟踪法(Feng等，2019a)。基于特征的方法由于在亮度变化、重复性纹理和几何失真等复杂场景时依然显示出较高的鲁棒性，成为遥感图像匹配研究的热点，其中SIFT(scale invariant feature transform)(Lowe，2004)是应用最为经典的特征描述子之一，并出现了很多针对耗时和精确性等方面的改进版本(耿娟等，2016; 张庆鹏和曹宇，2019)，提出了大量基于特征的图像匹配方法。该类方法有两个主要步骤：1)提取鲁棒特征点并基于最近邻距离比(nearest neighbor distance ratio, NNDR) (Lowe，2004)确定初始匹配; 2)基于几何模型过滤错误匹配。然而，由于重复纹理导致的特征模糊性，使基于NNDR的初始匹配存在大量错误匹配(Raguram等，2008)，因此需要额外的错误匹配剔除步骤(Li和Hu，2010; Ma等，2012)。按照错误匹配过滤方式的不同，现有的图像匹配算法可分为3类：基于几何模型的方法、基于局部空间结构的方法和基于图结构的方法。

1) 基于几何模型的匹配算法。该方法先基于NNDR比较局部特征(如SIFT特征的相似度)，然后迭代估算几何模型过滤外点，从而实现遥感图像的匹配。初始匹配方法包括暴力(brute force)匹配、近似最近邻(approximate nearest neighbor，ANN)搜索匹配(Agarwal等，2009; Crandall等，2011)和级联哈希(cascade hash，CH)匹配(Strecha等，2012; Cheng等，2014)。初始匹配中一般存在较多的错误匹配，通常使用随机样本一致性算法(random sample consensus，RANSAC)(Fischler和Bolles，1981; Hartley和Zisserman，2000; Raguram等，2008; Moisan等，2012; Chum等，2003)对错误匹配进行过滤，首先迭代选择随机数据样本估计模型，然后基于一定的阈值统计内点数量，以内点数量最多的模型为最终的图像变换模型，以此过滤外点匹配。针对无人机影像进行特征匹配，王晓红等人(2018)提出利用多重约束条件的外点过滤算法，首先检测影像特征点并构建初始匹配，再计算SIFT特征尺度邻域内的特征主方向，最后基于RANSAC估算单应性矩阵实现了更精确的错误匹配过滤。该方法在一般的刚体变换下效果良好，但在重复纹理条件下存在大量错误匹配时，估算出的几何模型不能准确反映图像变换关系，基于该几何模型的错误匹配过滤结果精度会大幅降低(Brown和Lowe，2002)。

2) 基于局部空间关系的匹配算法。为了应对RANSAC的匹配方法在重复的结构场景下性能退化问题，研究人员提出了几种基于局部空间结构一致性的算法。这些算法的基本原理在于：在查询和目标图像之间的转换过程中，匹配特征点的局部空间结构几乎保持不变，基于局部结构一致性原理可以消除图像的错误匹配。Ma等人(2014)提出一种鲁棒向量场一致性(vector field consensus，VFC)方法，通过在两幅图像之间插值一个向量场建立对应关系，采用最大后验估计方法从初始匹配中选择内点匹配。Li(2015)根据地面目标点在目标图像和查询图像之间位置不变性构建特征点几何向量相似性约束，实现了合成孔径雷达图像的正确匹配。Hu等人(2015)将描述符投影到一个单应空间，根据点之间的测地距离判断这些初始匹配的几何一致性和空间连续性，然后基于这种一致性确立正确的图像匹配。Yang等人(2017)通过欧几里德距离和形状建立高斯混合模型度量几何结构相似性，基于能量优化和运动一致性的几何约束更新变换模型以过滤错误匹配。Bian等人(2017)通过计算相邻匹配的数量提出一种基于网格的运动统计(grid-based motion statistics，GMS)方法。

3) 基于图结构的匹配算法。图匹配的核心概念是在两个图节点之间基于一定的规则建立图顶点的对应关系。基于此，研究人员提出了几种相应的图像匹配算法。Izadi和Saeedi(2012)利用图边之间的角度距离将特征与其最近邻连接起来，通过迭代剔除离群值计算相似图达到外点过滤的目的。Zhang等人(2014)利用k近邻的三角形区域定义了仿射不变描述子获得候选外点匹配，结合局部仿射不变描述子和全局信息消除外点匹配。为了在重复图案、遮挡和纹理均匀的情况下获得鲁棒的图像匹配，Yuan等人(2017)提出了一种结合几何约束和辐射约束的边缘加权张量的方法，构建高阶图匹配以实现图像特征的匹配。基于正确匹配局部邻域结构稳定的认识，Ma等人(2018)提出一种基于引导的错误匹配过滤算法(guided locality preserving matching，GLPM)，使用较高内点率的初始匹配引导初始匹配中的错误匹配过滤。为了不依赖于高内点率的初始匹配, Ma等人(2019)提出通过搜索每个假设匹配的k近邻构造一个近邻点集。基于局部邻域结构一致性检验消除错误匹配的LPM (locality preserving matching)算法，喜文飞等人(2020)提出利用图论原理构建特征点的能量函数过滤能量较低的特征点，以减少特征匹配的粗差，再结合RANSAC算法进行粗差剔除，获得了更高精度的单应矩阵估算结果。

上述方法大多能在保证较高内点率的前提下快速消除错误，但都有一个共同的问题：都需要一个相对耗时的初始匹配步骤，因此初始匹配步骤制约了基于特征的遥感图像匹配算法速度。为了应对这一问题，本文提出了一种基于空间分治算法思想的快速匹配方法。该方法的核心思路是将图像匹配分解成多个子集的匹配，通过这种分而治之的方法缩短特征匹配搜索范围，从而在缩短图像匹配时间的同时减少错误匹配的概率。本文的贡献在于提出一种构建分治匹配中心和分治匹配区域的方法。实验结果表明，与经典方法和最新方法相比，本文方法在保持较高内点的同时，可以显著减少1~2个数量级的匹配时间。

给定查询图像$\boldsymbol{I}^{\mathrm{q}} $与目标图像$ \boldsymbol{I}^{\mathrm{t}}$，$\boldsymbol{I}^{\mathrm{q}} <\boldsymbol{I}^{\mathrm{t}} $。首先利用最大尺度的SIFT特征快速提取少量的初始匹配; 然后基于初始匹配建立成对分治空间中心点，本文称之为虚拟中心点(virtual center point，VCP)，并基于近邻搜索将特征点分配到相应的成对分治空间; 最后在各个分治空间中分别进行遥感图像特征匹配。本文算法的主要流程如图 1所示, 由于算法源于分治思想，因此将其称为空间分治匹配算法(spatial divide and conquer，SDC)。

由于同一尺度级别的特征更容易正确匹配(Wu，2013)，首先提取SIFT特征并根据SIFT尺度大小按升序排序并选择尺度前10 % 的特征(本文称之为大尺度特征)，然后对其应用暴力匹配建立初始匹配子集。使用大尺度SIFT特征提取初始匹配，是因为它们数量少、质量高。为了提取尽可能多的正确初始匹配，将NNDR阈值设置为0.6。

为了分析SIFT特征的尺度分布，本文随机选择两幅图像$\boldsymbol{A}$和$\boldsymbol{B}$生成了特征尺度直方图，如图 2所示。显然，基于大尺度特征可以建立正确的匹配。图 2中，图 2(a)为两幅图像的前10 % 比例特征点的匹配结果，图中相同颜色的圆圈表示匹配的特征点，用蓝线连接，圆的半径代表其SIFT特征尺度大小。图像大尺度特征点的空间分布具有随机性，特征尺度大小与图像大小相关，图像$\boldsymbol{A}$的特征尺度小于图像$\boldsymbol{B}$的特征尺度。图 2(b)为两幅图像$\boldsymbol{A}$和$\boldsymbol{B}$的特征尺度的直方图。图像$\boldsymbol{A}$和$\boldsymbol{B}$显示的尺度范围不同，前者最大尺度约为40像素，后者最大尺度约为60像素。尽管如此，两幅图像中的特征尺度分布基本相同，都呈现出特征点的数量随尺度增大而减少的趋势，并且小尺度特征占主导地位。柱状图中的每一列表示10 % 特征尺度范围，最后一列表示最大尺度的特征点数，也是本文用来构建少量初始匹配的特征数量。可以看出，最小和最大尺度上的特征点数相差2~3个数量级。由于大规模特征的数量较少，并且重复结构中提取特征点的可能性很低，因此这些特征的可分辨性很高。基于这些少量的大尺度特征可以快速建立可靠的初始匹配，这正是构建空间分治中心的基础。

构建分治空间中心需要知道每个子集的大致中心位置。为了确定分治空间中心点对，首先查询图中构建虚拟中心点(virtual center point，VCP)，称为虚拟中心点是表示该点不一定代表提取特征点的实际位置，而只是作为分治空间的搜索中心。

构建VCP样点的关键是确定采样点间距，从而确定分治空间窗口的大小。采样点越密集、窗口越小，反之亦然。给定一幅具有$N_{I} $个特征点的遥感图像，假设特征点均匀分布的理想情况下，若在每个窗口中有$N_{w} $个特征点，且VCP位于其中心，那么

$ W_{\mathrm{num}}=N_{I} /N_{w} $

(1)

式中，$W_{\mathrm{num}}$是窗口数，$N_{w} $为经验值。

因此，基于$W_{\mathrm{num}}$的方形窗口的边长为

$ L=\min (W, H) /\sqrt{W_{\text {num }}} $

(2)

式中，$W$和$H$分别是图像的宽度和高度。可以看出，$W_{\mathrm{num}}$越大、$L$越小，反之亦然。

接下来，将VCP设置变换到目标图像，构建分治空间中心点对。首先，在查询图像中任意选择一个大尺度特征点作为起始点，以$L$为间距生成VCP集，表示为$\boldsymbol{V}^{\mathrm{q}}=\left[v_{0}^{\mathrm{q}}, v_{1}^{\mathrm{q}}, v_{2}^{\mathrm{q}}, v_{3}^{\mathrm{q}}, \cdots, v_{N}^{\mathrm{q}}\right]$。然后，利用大尺度特征点的少量初始匹配，估计仿射模型矩阵$\boldsymbol{A}$，利用仿射模型将该集合转换到目标图像，确定每个对应的VCP集合在目标图像中的大致位置，即

$ \boldsymbol{V}^{\mathrm{t}}=\boldsymbol{V}^{\mathrm{q}} \boldsymbol{A} $

(3)

式中，$\boldsymbol{V}^{\mathrm{t}}=\left[v_{0}^{\mathrm{t}}, v_{1}^{\mathrm{t}}, v_{2}^{\mathrm{t}}, v_{3}^{\mathrm{t}}, \cdots, v_{N}^{\mathrm{t}}\right]$。

由于图像大小不同，并不是所有的采样点都可以转换成目标图像。因此有必要在目标图像之外删除VCP集，得到图像匹配的分治空间中心点对$\boldsymbol{C}$。具体为

$ \boldsymbol{C}(k)= \begin{cases}\left(v_{i}^{\mathrm{q}}, v_{i}^{\mathrm{t}}\right) & v_{i}^{\mathrm{t}} \in \boldsymbol{I}^{\mathrm{t}} \\ \emptyset & \text { 其他 }\end{cases} $

(4)

式中，$\boldsymbol{C}=\left[\left(v_{0}^{\mathrm{q}}, v_{0}^{\mathrm{t}}\right),\left(v_{1}^{\mathrm{q}}, v_{1}^{\mathrm{t}}\right),\left(v_{2}^{\mathrm{q}}, v_{2}^{\mathrm{t}}\right), \cdots,\left(v_{K}^{\mathrm{q}}, v_{K}^{\mathrm{t}}\right)\right], K \leqslant N$。

图 3描述了基于仿射变换获得的$\boldsymbol{C}$。VCP从左侧的查询图像转换到相同尺寸(图 3(a))和不同尺寸(图 3(b))的右侧目标图像。当图像旋转时，查询图像中的一些点会转换为不包含特征点的黑色区域。基于式(4), 在进行图像匹配前排除了部分不会存在匹配的分治空间点集。从图 3可以看出，两个图像之间的重叠区域相对有限，大多数区域并无匹配。建立分治空间点集，可以减少大量不必要的特征匹配搜索运算。

确定分治空间中心点对集后，通过搜索每一对中心点附近的特征点，构建分治空间点集。

搜索近邻特征点的方法有4种：穷举搜索法、分维数搜索法、k-维树(k-dimensional tree, kd-tree)法和区域树(range-tree)法。由于区域树(de Berg等，2000) 具有较高的搜索效率，时间复杂度为O(log²M+ k)，因此本文采用区域树进行分治空间中心点的近邻搜索。具体来说，对于图像中任意一点v(x, y)，假设其位于边长为$L$的矩形$P$的内中心，且$ x \in [x-L / 2: x+L / 2]$和$ y \in[y-L / 2: y+L / 2]$，将搜索矩形$P$范围内所有点集的查询称为“矩形范围”查询。该查询方法要求数据维度正交，因此也称为“正交范围”查询。本研究搜索2维图像中一定范围内的近邻坐标点，符合正交性，因此2维区域树是近邻点快速查询的最优选择。

首先，提取$\boldsymbol{I}^{\mathrm{q}} $和$ \boldsymbol{I}^{\mathrm{t}}$中的SIFT特征的空间位置，再根据查询图像和目标图像的2维坐标分别构造区域树rt^q和rt^t。然后，以$L$为边长的正方形范围基于区域树搜索每一分治空间中心点对$\boldsymbol{C}\left(v_{n}^{\mathrm{q}}, v_{n}^{\mathrm{t}}\right)$的分治空间点集$\boldsymbol{W}_{n}^{\mathrm{q}}$和$\boldsymbol{W}_{n}^{\mathrm{t}}$，其中n为分治空间点集的索引。最后，形成分治空间点集对的集合$\boldsymbol{S} $，其中, $\boldsymbol{S}=\left[\left(\boldsymbol{W}_{0}^{\mathrm{q}}, \boldsymbol{W}_{0}^{\mathrm{t}}\right),\left(\boldsymbol{W}_{1}^{\mathrm{q}}, \boldsymbol{W}_{1}^{\mathrm{t}}\right),\left(\boldsymbol{W}_{2}^{\mathrm{q}}, \boldsymbol{W}_{2}^{\mathrm{t}}\right), \cdots\right. \left.\left(\boldsymbol{W}_{n}^{\mathrm{q}}, \boldsymbol{W}_{n}^{\mathrm{t}}\right)\right]_{0}$。

图 4是两个范围树搜索的示意图。图 4(a)查询图像与目标图像尺寸下相同且无相对旋转; 图 4(b)查询图像与目标图像尺寸不同且存在相对旋转。为了便于查看，只随机选择少量数据进行显示。黄色方框代表搜索范围，方框中心的红点代表VCP。在左侧的查询图像中，VCP均匀分布，间隔距离为$L$。绿线代表VCP匹配。可以看到两幅图像中的黄色方框大致位于同一个区域。利用VCP搜索相邻特征点后，即实现了分治空间的构建。

利用区域树完成分治空间点集构建后，进行分治空间内的特征匹配。kd-tree方法是特征匹配的常用方法，但需要额外的时间建立搜索树，且由于图像特征划分在多个窗口内，而每个窗口内的特征数量较少，此时kd-tree方法优势不明显，直接采用暴力匹配即可实现特征的快速匹配。

与传统暴力匹配方法不同，本文算法对图像顺序有要求，即$\boldsymbol{I}^{\mathrm{q}} <\boldsymbol{I}^{\mathrm{t}} $，要求较小的图像与较大的图像匹配，这个顺序对算法性能至关重要。由于分治空间内的特征点匹配基于NNDR方法，该方法搜索目标图像中最近和次最近的特征点描述子，然后通过计算两者的距离比判断两个特征是否匹配。如果目标图像中的特征点数目明显较少，则可能找不到足够的点达到最近邻比阈值，从而导致匹配失败。图 5展示了图像顺序对特征匹配影响，图中$ p$和$ q$分别是图 5(a)和图 5(b)查询图像中的一个特征点, $ f$和$ s$分别是目标图像中的第一和第二近邻点，线段$ pf$和$ qf$表示相同的匹配，每条蓝线附近的数字表示特征描述符的距离，而不是两点在图像上的欧几里德距离。从图 5可以看出，当目标分治空间中只有一个特征点存在时，没有次近的特征点构建NNDR，此时也会导致匹配失败，因此必须确保图像的大小顺序。本文算法通过测量两幅图像尺寸自动控制排序，设定尺寸较大的图像为目标图。

查询图像和目标图像中的特征点数量分别用M和N表示，M＜N。构建区域树的时间复杂度和空间复杂度都为$ \mathrm{O}(M \log M+N \log N)$。当查询图像和目标图像大尺度特征数量分别为u和v时，初始匹配过程的时间复杂度和空间复杂度分别为O(uv)和O(1)。建立区域树的时间复杂度为O(NlogN)，基于区域树搜索一对初始匹配点的时间复杂度为$\mathrm{O}\left(\log ^{2} M+k^{4}+\log ^{2} N+k^{\mathrm{t}}\right)$，其中k^q和k^t分别是查询和目标窗口的报告点数。

为了便于快速搜索，区域树必须在不同级别保存子树索引，其空间复杂度为O(MlogM+NlogN)。当每个查询窗口中至少有m个特征点时，需要M/m个VCP覆盖整个查询图像。因此，最近邻搜索的时间复杂度约为O((M/m)(log²M+log²N))，存储这些最近邻的空间复杂度为O(M+N)。假设目标窗口中有n个点，每对窗口的计算复杂度为O(mn); 所有窗口的匹配计算的时间复杂度为O(M/m)(mn)，以O(nM)表示; 空间复杂度为O(K)，其中K是匹配数。

综上所述，空间分治匹配算法的时间复杂度为$\mathrm{O}(M \log M+N \log N)+\mathrm{O}(u v)+\mathrm{O}(n M)+ \mathrm{O}\left((M / m)\left(\log ^{2} M+\log ^{2} N\right)\right)$。由于$M \ll N$，且$u, v \ll M, N$，因此，$\mathrm{O}(M \log M+N \log N) \ll 2 \times \mathrm{O}(N \log N), \mathrm{O}(u v)+\mathrm{O}(n M) \ll 2 \times \mathrm{O}(n M)$。时间复杂度可以近似为$\mathrm{O}\left((n+\log N) N+(M / m) \log ^{2} N\right)$。空间复杂度为$\mathrm{O}(M \log M+N \log N)+\mathrm{O}(M+N)+ O(K)$，一般为$K \ll M \ll N \ll M \log M \ll N \log N$，因此，空间分治匹配算法的空间复杂度可简写为$\mathrm{O}(N \log N)$。

为验证SDC算法的性能，在不同传感器遥感图像上与现有算法进行对比实验。实验在小米15.6 pro笔记本电脑上进行，软硬件配置为ubuntu16.04操作系统，Intelcorei5-8250U处理器和8 GB运行内存，SDC算法和比较算法均基于C+ +实现。

实验选取我国各地不同类型的卫星遥感数据，包括四川西部的Landsat 8多波段合成图像、北京的SPOT卫星图像、武汉东南部的GF-3合成孔径雷达(synthetic aperture radar，SAR)数据和青岛的ZY-3卫星数据。每种传感器的图像数据选择4对进行实验，图像尺寸在816 × 716~2 976 × 2 273像素之间，最大相对旋转角度为30°。这些图像涵盖了多种类型的地理环境，包括山脉、城市和沿海平原。这些都是高空卫星遥感影像数据，因此地面的起伏在成像上的影响较小。本文首先分析了不同参数设置对性能的影响，然后从内点率和运行时间两方面与其他最新的匹配方法进行比较。

由于每个窗口假设的点数决定了VCP的数量和窗口的大小，因此调节每个窗口的平均特征点数量会极大影响所提算法的性能。为了分析窗口大小对匹配时间和匹配比的影响，首先选取一组分辨率在795×530~3 976×2 652像素之间的图像进行实验。

实验表明，窗口大小与运算速度和内点率成反比。本文定义具有平均特征数的分治空间点集为“假设窗口”，每个“假设窗口”的特征数n对运行耗时和其他参数的影响如表 1所示。可以看出，“假设窗口”中包含的特征数(n)越多，则窗口尺寸越大、窗口对的数目($W_{\mathrm{num}}$)越小。查询图像的所有窗口中的平均特征数(F_w^q)和目标图像的所有窗口中的平均特征数(F_w^t)均与n正相关，而且较大的n需要更长的运行时间，因为分治空间内的特征匹配仍然基于暴力匹配方法，其时间复杂度为O(n²)。因此，窗口中的特征点越多，建立匹配所需的时间就越长。从整个图像中提取的总匹配数(M_total)和提取的内点匹配数量(M_inlier)的总体变化不大，在n增加的情况下呈现下降趋势。因此，“假设窗口”中的特征点数量是影响运行耗时(running time, RT)的主要因素。对于当前实验，当使用空间分治算法进行图像匹配时，参数n设置在5~10之间，以确保较快的运算速度。

通过以上对SDC算法的性能分析，可以看出窗口越小，匹配效率越高。实验也表明本文算法在不同地理环境下的遥感影像匹配中表现良好。由于高空卫星图像中，地形起伏对图像的影响可以忽略不计, 因此基于单应变换估算匹配精确性具有较高精度，可作为图像匹配质量的判断依据。具体来说，对于任意落在同一平面的一对匹配特征点$p_{1}\left(u_{1}, v_{1}\right)$和$p_{2}\left(u_{2}, v_{2}\right)$, 其归一化坐标为$\boldsymbol{p}_{1}=\left[u_{1}, v_{1}, 1\right]^{\mathrm{T}}$, $\boldsymbol{p}_{2}=\left[u_{2}, v_{2}, 1\right]^{\mathrm{T}}$。基于4个以上匹配点对可以计算存在的单应变化矩阵$\boldsymbol{H}$，具体为

$ \left[\begin{array}{c} u_{1} \\ v_{1} \\ 1 \end{array}\right]=\left[\begin{array}{lll} h_{1} & h_{2} & h_{3} \\ h_{4} & h_{5} & h_{6} \\ h_{7} & h_{8} & h_{9} \end{array}\right] \cdot\left[\begin{array}{c} u_{2} \\ v_{2} \\ 1 \end{array}\right]=\boldsymbol{H} \cdot\left[\begin{array}{l} u_{2} \\ v_{2} \\ 1 \end{array}\right] $

(5)

然后以$\boldsymbol{H}$为基准，根据投影误差$\varepsilon $确定匹配的正确性，其中$\varepsilon=d\left(P^{\mathrm{q}}, H P^{\mathrm{t}}\right) $。当$\varepsilon $小于阈值$\tau $时，认为该匹配是一个内点匹配，否则认为是一个外点匹配。在文中，将$\tau $设置为1。

图 6描述了SDC算法在图像匹配中的匹配效果，其中蓝线和黄线分别表示内点匹配和外点匹配，为了便于观察，只随机选择了100对匹配进行展示。可以看出，SDC算法具有较高的匹配精度，在严格的误差阈值(1像元)下，100对随机选择的匹配点中，只有2~3个外点匹配，SDC算法在不同地理区域的图像上都具有较好的匹配结果。其原因在于特征相似度计算在分治空间内进行，降低了误匹配的可能性，在提高匹配精度的同时缩短了匹配时间。

为验证本文提出的SDC算法的匹配效率，选取36幅不同尺寸的遥感图像，与现有最先进的RANSAC(Fischler和Bolles，1981)、VFC(Ma等，2012)、GMS(Bian等，2017)和GLPM(Ma等，2018)算法从内点率和运行耗时两方面进行比较。

首先对各算法提取的匹配和内点匹配的绝对数量进行比较。通常使用精确度和召回率评估图像匹配性能。因此要计算匹配召回率，就必须确定正确匹配的数量。现有研究中的正确匹配是通过手动选择计算的，而为了验证本文算法在不同图像大小下的性能，选择了20对图像进行实验，从中提取了多达10 000个匹配项，显然手动选择是不可行的。参考Kurz和Himane(2011)方法，本文使用单应矩阵的投影误差确定匹配是否正确。首先选择少量的大尺度SIFT特征进行严格NNDR阈值的初始匹配，由于匹配的数量较少，因而可以直观地检查是否存在不正确的匹配。在没有错误匹配发生的情况下，可以计算出更精确的单应矩阵$\boldsymbol{H}$，然后根据第2.1节提到的方法对确定错误匹配。

表 2显示了通过各种匹配算法获得的总匹配数和内点数。传统的基于RANSAC的匹配方法提取了最多的匹配，BF-RANSAC是基于暴力匹配(BF)的RANSAC，ANN-RANSAC是基于近似最近邻(ANN)匹配的RANSAC，CH-RANSAC是基于级联哈希(CH)匹配的RANSAC，其中最直接的BF-RANSAC匹配方法搜索到最多的匹配。在其他算法中，VFC提取到的匹配几乎与BF-RANSAC相同，略微居于其次的是GMS算法。而GLPM和本文SDC算法提取的匹配数量相对较少，但是内点的比例也很高。有两个原因导致SDC算法获得的匹配较少：1)SDC是一种空间分治算法，匹配点对的数目取决于分治空间的大小。此外，分治空间之间的间隙是不可避免的，因此一些特征被排除在外。2)当影像地面存在起伏时，仿射估计可能不够精确，导致VCP变换不准确，变换后的分治空间会偏离实际应该在的位置，导致部分特征点的匹配发生在不同的分治空间内。虽然SDC算法相对于其他算法丢失了部分匹配，然而在实时遥感匹配中通常不需要匹配所有特征。当匹配点在图像中均匀分布时，可以估计出精确的几何模型，而SDC算法的匹配点分布在分治空间中心的采样时即已决定其均匀性。

为验证本文算法的匹配效率，对各算法的内点率和运行时间进行比较。各种遥感影像传感器的匹配效率如图 7和图 8所示，每种传感器类型选择9幅图像进行匹配实验，图 7是内点率比较，图 8是运行时间比较。从图 7和图 8可以看出，SDC算法内点率虽然比其他算法略低，但对于各种传感器图像，仍然保持了最低90 % 的较高水平。在运行时间上，VFC、GMS、ANN-RANSAC和CH-RANSAC等最新算法的时间效率相近，CH-RANSAC的速度稍快。但与本文算法相比，这些算法在Landsat和SPOT图像上的耗时约10倍多，在GF-3和ZY-3上的耗时约为2~5倍多; 与经典的BF-RANSAC算法相比，SDC算法的效率提高了100倍左右。可以看出，SDC算法显著提高了遥感图像匹配的效率。

结合4个传感器的36幅图像的内点率和运行时间，可以得出各算法的总体性能。图 9通过箱线图进一步展示了各种算法的综合性能。如图 9(a)所示，基于RANSAC的方法以及基于空间结构的方法VFC和GMS产生了最高的内点率，而SDC算法获得了相对较低的内点率。虽然SDC算法比其他算法的精度稍低，但平均精度仍然在98 % 以上，可以满足大多数实际遥感图像拼接应用的要求。另一方面，SDC算法在运行耗时方面表现出了优异性能，如图 9(b)所示，该算法的平均运行时间比其他算法中最优的缩短到1/100~1/10。这种突出的时间效率对实时遥感图像拼接应用具有实用价值，是SDC算法的主要优势。

本文提出了一种基于空间分治的快速遥感图像匹配方法。与传统的和最先进的匹配方法相比，该方法在保证较高内点率的同时将运行耗时缩短到1/100~1/10。本文方法简单直观，利用严格的NNDR提取大尺度特征构造了少量初始匹配; 在查询图像中按一定的间隔构建分治空间中心点。基于初始匹配估计一个仿射模型，将查询图像分治空间中心点转换到目标图像，在两个图像之间构造分治空间中心点对集; 然后，基于区域树搜索每个分治空间中心点的近邻特征点集，构建分治空间点集。在成对分治空间内进行图像匹配。通过多种不同纹理条件的遥感图像的实验表明，与其他方法相比，分治空间匹配方法具有较高的精度和较低的运行时间。其优越的时间性能在遥感拼接镶嵌等应用中具有实际价值。由于各个分治空间的匹配过程相互独立，因此采用并行计算可以进一步提高算法的速度。不足之处是，分治空间匹配的关键是分治空间中心的准确映射，而在低空无人机遥感等场景中，受地形起伏因素的影响，会导致分治空间中心映射不准确，从而导致算法性能下降，这是下一步需要改进的地方。