直线特征是人类视觉信息中最显著、最直观、最具有代表性的特征。城区建筑物轮廓边缘、屋顶和立面都蕴含着大量的直线特征，包含丰富的语言信息和几何意义，能够较好地表达建筑物结构特征，因此，将直线特征作为匹配基元并实现其可靠匹配是基于影像精细三维建模的基础^[1-4]。目前，摄影测量和计算机视觉领域对直线匹配进行了大量的卓有成效的研究。现有的直线匹配方法可以分为单直线匹配和组直线匹配两类。

单直线匹配方法主要利用单一直线的几何属性信息(如斜率、长度、位置、重叠度、距离等)或邻域灰度信息的特征相似性，结合一定的几何约束对直线逐一进行匹配。文献[5]采用分层次直线符号法，利用直线段的长度、方向、位置和强度、对比度等特征进行直线的相似性匹配；结合核线约束，文献[6]利用直线邻域灰度相关实现直线匹配；结合同名三角网约束，文献[7-8]提出移动窗口的自适应直线相关方法，有效解决位于纹理断裂处的直线匹配问题；结合同名点约束，文献[9]通过窗口行向量平均化计算相似性；文献[10]利用物方平面约束，通过计算参考直线和候选直线间重叠距离和垂直距离，确定同名直线；文献[11]将待匹配线及与其共面的同名点作为整体进行描述及匹配；在无任何约束条件下，文献[12-13]提出了MSLD均值-标准差直线描述子(mean-standard deviation line descriptor, MSLD)，该描述子通过统计像素支撑域内每个子区域4个方向的梯度向量构建描述子矩阵，提高描述子的可区分性及稳健性。目前单直线匹配研究取得了一定的进展^[14-18]，但受限于单一直线描述符，匹配过程中没有考虑邻近直线特征之间关系，匹配结果模糊性一直存在。

组直线匹配多利用满足一定条件的直线组作为匹配基元进行匹配。文献[19]将定义的干线对作为匹配基元，采用全局最优化思想完成异源图像的匹配及配准；文献[20]根据几何特性、灰度特性为直线分配可信度，以组直线为匹配单元，利用马氏距离计算组直线之间的特征相似性进行匹配；文献[21-23]提出了一种组直线匹配方法，首先参考影像上的直线组需满足距离、角度、半邻域灰度相似性3个条件，综合利用核线约束、几何属性约束、空间直方图、灰度相关等约束条件确定搜索影像上的同名直线组。研究结合Daisy描述符、匹配结果冗余及成对质量检核3个方面对匹配结果进行后处理，减少匹配结果不确定性；文献[24]将三维空间共面的直线组作为匹配基元，根据拓扑关系确定直线组，对直线组交点构建描述符，根据标准互相关函数确定同名直线组，该方法对纹理匮乏区域均能取得较好的匹配结果，但对于拍摄倾角变化较大的立体影像还需进一步完善。在现有组直线匹配方法的基础上，本文提出一种顾及拓扑关系的立体影像直线特征可靠匹配算法。该算法将满足一定拓扑关系的直线组作为匹配基元，充分利用直线组间几何信息、拓扑关系等多重约束对直线组进行匹配，并通过对同名直线组分裂、匹配结果后处理获取可靠的直线匹配结果。

1 原理

在已有LSD直线提取结果和渐进三角网约束点密集匹配结果的基础上，本文提出的顾及拓扑关系的立体影像直线特征可靠匹配算法分为特征直线组提取、直线组匹配和匹配结果后处理3个阶段。第1阶段，根据直线间距离、角度等拓扑关系对参考影像、搜索影像提取的直线分别进行特征编组，提取满足预设条件的特征直线组；第2阶段，充分利用直线组间拓扑关系，依次采用核线约束、单应矩阵约束、象限约束和三角形区域灰度相关约束对参考影像、搜索影像上提取的直线组进行匹配，得到两张影像上的同名直线组；第3阶段，将匹配得到的同名直线组分解为同名单直线，并对结果进行后处理，主要包括对结果中“一对多”“多对一”“多对多”匹配结果进行整合，剔除错误的“多”直线匹配结果，并对正确的“多”直线进行拟合，最终得到“一对一”的同名单直线。

1.1 拓扑关系约束的直线编组

采用LSD算法^[25]对参考影像、搜索影像分别进行直线提取，结果表示为L={l₁, l₂, …, l_I}，R={r₁, r₂, …, r_J}，I、J分别为参考影像、搜索影像上提取直线的数目。对参考影像、搜索影像提取的直线分别进行编组，得到特征直线组。对影像上任一直线段l_i，两端点分别为a和b，长度为len，将其作为目标直线，直线{l_i+1, l_i+2, …, l_I}为待编组的直线，具体编组过程如下：

(1) 以目标直线l_i为中心建立矩形窗口作为目标直线邻域窗口。如图 1所示，沿目标直线两端及垂直直线方向的两侧，分别扩展d个像素长度，得到大小为(2d+1)×(len+2d)的矩形窗口为目标直线的邻域窗口。

(2) 依次判断待编组的直线与目标直线邻域窗口关系，如某一待编组直线l_i′在目标直线邻域窗口内或与邻域窗口相交，且与目标直线l_i的夹角θ在一定的角度范围内，则该直线l_i′与目标直线l_i构成一特征直线组，记为P^L(l_i, l_i′, C^L)，C^L为特征直线组的交点坐标。

(3) 分别选择l_i和l_i′端点中与交点C^L距离较近的点作为l_i和l_i′的起点，与点C^L距离较远的点作为直线l_i和l_i′的终点。如图 1所示，b、e分别为两直线的起点，a、c分别为两直线的终点。

对每张影像上提取的直线依次进行编组，分别得到参考影像和搜索影像上的特征直线组集合，记为PL={P₁^L(l_i¹, l_i′¹, C₁^L), P₂^L(l_i², l_i′², C₂^L), …, P_M^L(l_i^M, l_i′^M, C_M^L)}，PR={P₁^R(r_j¹, r_j′¹, C₁^R), P₂^R(r_j², r_j′², C₂^R), …, P_N^R(r_j^N, r_j′^N, C_N^R)}，其中，M和N分别为参考影像和搜索影像上直线组的数目。图 2为参考影像、搜索影像上编组得到的直线组，其中圆点为直线组中两条直线的交点。

1.2 顾及拓扑关系的直线组匹配

以参考参考、搜索影像上编组得到的直线组作为匹配基元进行匹配，匹配过程中依次采用核线约束、单应矩阵约束、象限约束、不规则三角形区域灰度相关约束。对参考影像上任一直线组，确定搜索影像上满足上述四种约束条件的特征直线组为其同名直线组。

1.2.1 核线约束

如图 3(a)所示，参考影像上任一特征直线组P_m^L(l_i^m, l_i′^m, C_m^L)，计算其交点C_m^L在搜索影像上的核线。计算搜索影像上各特征直线组交点{C₁^R, C₂^R, …, C_N^R}到核线的距离，距离小于一定阈值T_d的特征直线组为候选直线组。如图 3(b)所示，其中交点C₁^R、C₂^R、C_n^R对应的直线组为候选直线组。

1.2.2 单应矩阵约束

单应矩阵表示两个平面之间的可逆齐次变换，同一平面上的点，在两张影像上成像的同名点坐标记为u =[x_L, y_L]^T，v =[x_R, y_R]^T，则u点可通过式(1)变换到v点

式中，H为单应矩阵，通过两张影像上至少4对同名点进行求解。对于实际影像而言，一般都存在地形起伏或者景深变换，因此全局单应矩阵不适用于整张影像。本文对任一待匹配直线组分别选取其邻域范围内同名点计算局部单应矩阵，用于近似表示该直线组所在局部影像区域之间的对应关系，用于限定核线上的搜索范围。如图 3(a)所示，以参考直线组交点C_m^L为中心，以两直线l_i^m和l_i′^m终点方向所构成扇形区域内包含的同名点计算局部单应矩阵H，图 3中实心三角点为用于计算局部单应矩阵的同名点。为了确保用于单应矩阵计算所需同名点的数目，迭代扩大扇形半径直到同名点数目满足为止。

根据局部单应矩阵H和式(1)，将参考影像上参考直线组交点C_m^L映射到搜索影像上，得到点，如图 3(b)所示；计算搜索影像上各候选直线组交点到点的距离，剔除距离大于阈值T_h的候选直线组。

1.2.3 象限约束

根据局部单应矩阵H，将参考影像上参考直线组P_m^L(l_i^m, l_i′^m, C_m^L)映射到搜索影像上，得到；如图 3(b)所示，在搜索影像上，对建立以为原点的局部坐标系，x轴和y轴分别与像素坐标系的x轴和y轴平行，记录中直线和直线终点所在象限分别为Q₁和Q₂；对搜索影像上各候选直线组分别以其交点为原点建立局部坐标系，判断每个候选直线组中两直线终点所在象限是否为Q₁和Q₂，是，保留该候选直线组，否则，舍弃该候选直线组。

1.2.4 不规则三角形区域灰度相关约束

对满上述3个约束的候选直线组，采用不规则三角形区域灰度相关约束确定最终同名直线组。

1.2.4.1 建立单直线对应关系

首先根据直线组中两直线所在象限建立参考直线组和候选直线组中单直线对应关系。固定参考影像上参考直线组P_m^L(l_i^m, l_i′^m, C_m^L)中l_i^m为起始边，l_i′^m为终止边。根据直线和直线所在象限Q₁和Q₂确定候选直线组中与其对应的起始边和终止边，这里分两种情况：

当Q₁≠Q₂时，即参考直线组中两条直线在两个不同的象限，候选直线组P_n^R(r_iⁿ, r_i′ⁿ, C_n^R)中，如果r_iⁿ终点所在象限为Q₁，则r_iⁿ为起始边，r_i′ⁿ为终止边，反之，如果r_i′ⁿ终点所在象限为Q₁，则r_i′ⁿ为起始边，r_iⁿ为终止边，更新候选直线组为P_n^R(r_i′ⁿ, r_iⁿ, C_n^R)。

当Q₁=Q₂时，即参考直线组P_m^L(l_i^m, l_i′^m, C_m^L)中两条直线在同一象限，根据向量叉积判断从l_i^m到l_i′^m是顺时针还是逆时方向旋转，对应的，判断候选直线组P_n^R(r_iⁿ, r_i′ⁿ, C_n^R)中从r_iⁿ到r_i′ⁿ是否与从l_i^m到l_i′^m的旋转方向一致，如果不一致，更新候选直线组为P_n^R(r_i′ⁿ, r_iⁿ, C_n^R)，否则，候选直线组不变。

1.2.4.2 对应三角形区域提取

如图 3(a)所示，以参考直线组交点C_m^L、起始边终点a、终止边终点c构成三角形ΔaC_m^Lc所包含的区域作为灰度相关区域，并采用扫描线算法确定三角形区域内所包含的像素点坐标及其灰度值，灰度值记为G={g₁, …, g_i, …, g_Ng}，Ng为区域内包含的像素点数目。

如图 3(b)所示，分别计算参考直线组起始边终点a、终止边终点c在搜索影像上的核线H_a、H_c，分别计算H_a、H_c与候选直线组中起始边和终止边的交点，记为a′和c′。搜索影像上以候选直线组交点、a′点和c′点构成三角形所包含的区域作为灰度相关区域。

利用参考影像、搜索影像灰度相关区域的3个顶点坐标，根据式(2)计算两灰度相关区域仿射变换参数

式中，a₀、a₁、a₂、b₀、b₁、b₂表示仿射变换的6参数；x和y表示参考影像上灰度相关区域顶点坐标，x′和y′表示搜索影像上对应的灰度相关区域对应顶点坐标。

根据仿射变换参数和参考影像上灰度相关区域ΔaC_k^Lc内包含的像素点坐标计算搜索影像上灰度相关区域内对应像素点的坐标，并根据双线性插值方法计算得到对应像素点的灰度值，记为F={f₁, …, f_i, …, f_Ng}。

1.2.4.3 灰度相关计算

根据相关系数式(3)计算参考影像、搜索影像灰度相关区域的灰度相关系数ρ

式中，g_i和f_i分别为参考影像、搜索影像灰度相关区域内对应像素的灰度值；g和f分别为对应的灰度相关区域内所有像素灰度值的平均值。选取相关系数最大且大于一定阈值T_ρ的灰度相关区域对应的候选直线组为P_m^L(l_i^m, l_i′^m, C_m^L)的同名特征直线组。

1.3 匹配结果后处理

根据直线组中单直线应关系将匹配得到的每对同名直线组分裂为两对同名单直线，由于直线编组过程中同一直线可能出现在多个直线组中，参与多次匹配，会得到多次匹配结果。同时由于直线提取结果断裂和错误匹配，匹配结果中存在“一对多”“多对一”“多对多”匹配情况，因此需要对匹配结果进行后处理。在确保匹配结果中对应关系唯一性的基础上，对结果中非“一对一”的“多”直线进行检核，剔除错误的“多”直线匹配结果，并对正确的“多”直线进行拟合，最终得到“一对一”的同名单直线。

首先，根据文献[10]中匹配结果整合算法对分裂得到的同名单直线依次实现从左到右，再从右到左的“一对多”匹配结果整合。然后，对整合后同名直线对应关系中“一对多”“多对一”“多对多”结果中的“多”直线进行拟合，如果拟合直线斜率与原有的多条直线斜率均一致且“多”直线间重叠度为0，则用拟合直线代替原有的“多”直线，否则将该组匹配结果删除。最终得到参考影像上与搜索影像上“一对一”的同名直线。

2 试验与分析

为了验证本文算法的有效性，共采用一组航空影像、两组近景影像用于直线匹配试验。第1组为图 4(a)所示的DMC数字航空影像的子影像对，影像集中在人工建筑物密集区域，提取的直线特征多为建筑物边缘，影像大小分别为499× 463像素、487×450像素；第2组为图 4(b)所示存在尺度变化的近景影像对，两张影像之间尺度比约为1:1.5，影像大小均为600×800像素；第3组为图 4(c)所示存在旋转的近景影像对，两张影像旋转角度约为40°，影像上地物细节信息较为丰富。试验过程中，首先对图 4所示3组影像实现渐进三角网约束点密集匹配及LSD直线提取，然后在此基础上进行直线匹配。匹配过程中参数阈值设置如下：T_d=5，T_h=20，T_ρ=0.7。

2.1 直线编组参数选取

本文采用直线组作为匹配基元进行直线匹配，而直线编组结果对直线匹配结果产生直接的影响。本文编组过程中共包含直线邻域扩展长度d和直线夹角θ角度范围两个参数，因此本文采用第1组航空影像数据，在d和θ取不同值的情况下进行直线编组及匹配试验，分析编组过程中不同参数值对编组的影响，进而研究其对匹配结果的影响，通过对比分析确定编组参数用于后续匹配。

在匹配参数一致的条件下，本文对θ∈[45°, 135°]、θ∈[30°, 150°]、θ∈[15°, 165°]3个取值范围及d分别取5、10、15、20、25值的情况下进行匹配试验，结果分别如表 1、表 2、表 3所示。其中，第1列为d的取值；第2、3列为参考影像、搜索影像上编组得到的直线组的数目；第4列为匹配得到的同名直线组的数目；第5列为同名直线组分裂后得到同名直线的数目。但是由于匹配结果中存在“一对多”“多对一”“多对多”对应关系，因此结果中包含参考影像、搜索影像上直线数目不相同，第6、7列为匹配结果中分别包含的参考影像、搜索影像上提取直线的数目；第8列为经过对“一对多”“多对一”“多对多”结果整合、拟合、检核后得到的最终的同名直线数；第9列为正确匹配的数目，第10列为匹配的正确率。

图 4(a)两张影像上提取直线的数目分别为398条、406条。一方面，由于一条直线可能存在多个组中，因此编组得到的直线组数会多于直线提取的数目；另一方面，由于夹角和邻域范围的设定，会存在一些直线未被编组，因此编组得到直线组数也会少于直线提取的数目。

从表 1、表 2、表 3中可以看出随着θ角度范围增大、d值增大，参考影像、搜索影像上编组得到的直线组数目越多，匹配得到的同名直线组数目越多，对应分裂后同名单直线数目越多，且包含参考影像、搜索影像上直线数目越多。但是随着结果中“一对多”“多对一”“多对多”对应关系增多，匹配后处理后得到的同名直线的数目并没有因此而增多。这是由于本文在对“多”结果的拟合和检核的过程中采用了“一刀切”的方法，导致部分正确的匹配结果也被删除掉，影响最终同名直线的数目。尤其在误匹配较多的情况下，同名直线数目会大幅度的减小，例如，当d=25时，参考影像、搜索影像上编组后得到直线组的重复率较小，直线组匹配正确率不高，错误匹配较多，最终同名直线数目较小。后续将针对后处理中合并和检核过程进行针对性的研究。此外，针对图 4(a)所示影像，匹配结果中误匹配多发生在人字形的屋顶处，主要是由于不同视角产生的直线投影不同导致直线提取结果的不同而引起的错误匹配。

2.2 本文算法匹配结果及不同方法对比分析

通过2.1节不同参数对比分析试验，本文选取参数θ∈[30°, 150°]，d=20对图 4所示影像进行直线匹配试验。为了与本文算法进行更加客观的对比分析，在初始同名点及直线提取结果相同的条件下，本文实现了文献[13]中基于MSLD描述子的直线匹配方法，实现过程中在原文献描述子基础上，增加了利用同名三角约束匹配候选直线，对其结果也采用本文的后处理算法进行处理。文献[13]根据最小欧氏距离与次最小欧氏距离的比值小于阈值T_N确定同名直线，T_N=0.8。两种方法直线匹配结果显示如图 5-图 7所示，人工目视判读直线匹配结果是否正确，其中红色线为正确匹配直线，蓝色线为错误匹配直线。两种算法直线匹配结果统计如表 4所示，其中第1列为试验影像，第2、3列为参考影像、搜索影像上提取直线的数目，第4列为采用的算法，第5列为匹配得到同名直线的数目，后5列表示的含义与表 1所述含义一致。从中可以看出对于图 4(a)航空影像和图 4(b)存在尺度变化影像，本文算法取得较好的结果。航空影像上特征线多位于建筑物边缘，而不同影像上同一建筑物两侧纹理信息的一致性较弱，MSLD构建描述子过程中同时考虑直线两侧信息，这对不同影像上同一建筑物边缘相似性的计算会产生影响，而本文算法利用直线组构建相关区域，对于位于同一屋顶面上的直线组不会受纹理断裂的影响；对于尺度变化影像，主要是因为MSLD描述子本身没有考虑尺度变化，而本文算法在确定三角形灰度相关区域时用到仿射变换，因此对于小尺度变化的影像具有一定的适应性；但对于图 4(c)所示纹理丰富，细节较多的影像，MSLD的结果要好于本文算法。这是由于MSLD描述子利用梯度特征，其稳健性强于单纯基于区域的灰度相关，尤其对于细节信息丰富的影像，MSLD能产生较好的匹配效果，产生较少的错误匹配。而本文单纯基于区域灰度相关的匹配结果可靠性较弱，初始匹配会产生较多的错误匹配，后处理后删除掉大部分错误匹配，但是同名直线的数目也大幅度减小。后续研究将会考虑用基于梯度的描述子代替传统的灰度相关。

此外，匹配过程中涉及3个参数阈值T_d、T_h、T_ρ的设定。其中，T_d和T_h主要用于核线约束和单应矩阵约束匹配候选，在本文算法匹配过程中这两种约束较为宽泛，在一定范围内受阈值影响较小，后续象限约束较为严格。相关系数阈值采用经验化阈值，取为0.7。

3 结论

本文探索了一种顾及拓扑关系的立体影像直线特征可靠匹配算法。该算法主要特点表现在以下几个方面：①在已有单应矩阵的基础上，提出了象限约束，使得特征编组具有任意性，不用考虑任何对应关系，简化了编组过程；②对位于同一面片上的直线组，能有效避免纹理断裂对匹配产生的影响，提高匹配的可靠性，同时，三角形灰度区域建立过程中引入的仿射变换使得该方法适用于存在一定尺度变化的影像；③对“一对多”“多对一”“多对多”的匹配结果进行整合，并对整合结果中的“多”直线进行检核，对正确的“多”直线进行拟合，剔除错误的“多”直线匹配结果，得到“一对一”的同名直线。此算法一方面解决了直线提取过程中产生的断裂，另一方面提高了匹配的正确率。

下一步研究工作：①目前算法没有充分利用匹配结果中的冗余信息，同时匹配结果后处理过程中，采用“一刀切”政策，部分正确的匹配结果被删除，使得匹配直线数目大大减少，后续将重点研究充分利用冗余信息提高后处理的高效性及有效性；②现有研究是基础性和探索性的，后续将现有算法中基于灰度的描述符替换成基于梯度信息的描述符，提高描述符的稳定性和可靠性；③进一步将考虑未被编组的直线，使其加入匹配。