EN中文

Journal of Geo-information Science >

2020 , Vol. 22 >Issue 9: 1766 - 1778

DOI: https://doi.org/10.12082/dqxxkx.2020.190334

Pair-wise Line Matching Algorithm based on Feature Similarity Constraints of Geometric Attributes between the Lines

  • HE Wanying , 1 ,
  • WANG Jingxue , 1, 2, *
Expand
  • 1. School of Geomatics, Liaoning Technical University, Fuxin 123000, China
  • 2. Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 611756, China
*WANG Jingxue, E-mail:

Received date: 2019-06-25

  Request revised date: 2019-10-23

  Online published: 2020-11-25

Supported by

National Natural Science Foundation of China(41871379)

Key Laboratory of Earth Observation and Geospatial Information Science of NASG(201801)

Copyright

Copyright reserved © 2020
Fold

Abstract

Many same or similar line features may hinder line matching in the image, matching only based on the similarity between individual line, which easily lead to the failure of the algorithm. Therefore, this paper proposed a reliable pair-wise line matching algorithm based on feature similarity constraints of geometric attributes between the lines. There are two challenges in constructing robust feature similarity constraints based on pair-wise line matching. The first challenge is to generate grouped line pairs under unstable lines extraction. This algorithm is handled by the basic geometric relationships such as distance and angle between the lines. The second challenge is to design a reliable feature descriptor robust to large viewpoint changes taking into account that the line pairs may not be coplanar and their endpoints are inaccurate. This algorithm salient not only against a range of viewpoint changes for close-range image but also large affine transformation. The construction method is described as follows. Firstly, line segments are extracted by using a line segment detector method and the corresponding points obtained by using SIFT matching points in the reference image and searching image.The algorithm generates grouped line pairs from lines extracted from the reference image and searching image according to the basic geometric relationships such as distance and angle between the lines, and it takes the grouped line pairs as matching primitives. Then the method employs the epipolar constraint to evaluate candidate line pairs. Line matching algorithm based on geometric attributes of lines for descriptor and similarity measure of line pairs are presented which is more distinctive by describing the relationship between every two pairs. The configuration of two line pairs is described by distinguishing two cases, in the first case, the similarity of the two line pairs is called as affine similarity; In another case, it is called general similarity. The affine similarity and general similarity are used as the overall similarity measure in this algorithm and are determined based on the calculated feature vectors between the target line pairs and each candidate line pairs. Instead of screening all candidate line pairs, the optimal line pairs mapping that maximizes the similarity measure between the two line pairs. Finally, the direction constraint which can provide a solution for angle transformation caused by image rotation in line pairs matching is used to perform the correspondence of individual line, it resolves the corresponding line pairs into two pairs of corresponding individual lines, and obtains one to one matching results after the post-processing of checking. Five typical groups of close-range image pairs with angle, rotation, and scale transformation are used as the experimental dataset, which is used to complete the line pairs matching experiments by the proposed algorithm. In comparison with other line matching algorithms, the proposed method can obtain more accurate line matching results in different typical close-range image pairs, and its matching ratio increased by 14.5. The experiment results demonstrate that the effect of threshold selection is weak and the algorithm is robust which achieves reliable line matching results.

Key words： pair-wise line matching; epipolar constraint; geometric attributes of lines; affine invariance; feature vectors; feature similarity constraint; direction constraint

Cite this article

HE Wanying , WANG Jingxue . Pair-wise Line Matching Algorithm based on Feature Similarity Constraints of Geometric Attributes between the Lines[J]. Journal of Geo-information Science, 2020 , 22(9) : 1766 -1778 . DOI: 10.12082/dqxxkx.2020.190334

1 引言

特征匹配是进行遥感分析、摄影测量和场景三维重建的关键环节。目前,将点特征、线特征和面特征作为匹配基元的匹配算法都取得了突破性的进展[1,2,3],不同于点特征,线特征的属性信息丰富,更适用于纹理信息匮乏的人造场景,能较好的体现出场景内建筑物的轮廓边缘信息;相较于面特征,线特征的提取和描述难度较小,因此,利用线特征获得匹配信息的方法在目标检测、目标跟踪以及精细三维建模[4,5,6]等领域具有不可或缺的作用。为弥补直线匹配方式存在的不足,国内外学者相继拓展了直线匹配的方法和模式,现有的匹配方法主要可分为2大类,一类为单一直线匹配,另一类为组直线匹配。
单一直线匹配方法需要结合直线自身的固有属性例如方向、长度、位置、重叠度等[7,8,9]或直线邻域内的同名点[10]、梯度[11]和灰度等信息进行,虽然此类方法计算简单,但常依赖有效的几何约束条件。梁艳等[12]借助直线端点的核线约束及局部仿射变换,并利用直线支撑域的灰度信息完成匹配,但该算法易受同名点数量和精度的影响;欧阳欢等[13]结合同名点约束将直线特征进行离散化描述的直线匹配算法在应对复杂匹配问题上具有可靠性;张云生等[14]构建直线特征的三角网约束,结合移动窗口的自适应相关系数法可改善直线位于断裂、半遮挡以及纹理缺乏等区域造成的错误匹配;Jia等[15],Fan等[16]将待匹配直线及其邻域内同名点的投影仿射不变量作为整体进行描述与验证,此算法对于误匹配点及非共面直线具有较强的可用性;王志衡等[17],Wang等[18]提出MSLD均值-标准差直线描述子（Mean-Standard Deviation Line Descriptor）,在无任何约束条件下直接构建支撑域内直线梯度特征向量并建立描述矩阵,提高了现有描述子的适应性和鲁棒性,但该类描述子对尺度变化较于敏感;Ramalingam 等[19]通过已知同名点连接的虚线与目标直线相交形成的交叉比构造匹配新点生成同名直线的算法,在宽基线匹配及三维重建等方面表现出一定的优越性。
相较于单一直线匹配方法,组直线匹配方法充分考虑直线与邻近直线的关系,能较好地反映出直线间的几何关系,避免了单直线匹配过程中由于线特征提取不完整、易断裂、端点不一致等原因造成的匹配结果模糊,组直线匹配从整体角度出发依据2组直线对间的特征相似性获取同名直线组。文贡坚[20]在几何和辐射约束下构建两幅影像共同的直线集上所有可能的特征编组,根据每个特征直线组内部直线之间的匹配关系,全局求解每个最优特征编组的匹配度。Micusik等[21,22,23]首先利用影像内组直线交点与同名特征点之间的联系实现匹配,该类算法将匹配直线问题转移到匹配点,但由于直线对交点较多、获取的同名点相对稀疏导致这一方式具有局限性;王竞雪等[24]对提取直线的共有特征分别编组,然后采用编组后的直线组作为匹配基元,匹配过程中结合两直线间的拓扑关系及其几何约束条件完成匹配,此算法解决了直线提取过程中的断裂问题且提高了匹配正确率;Li等[25]提出从2幅影像中匹配直线的分层算法,首先在分组匹配时,为了可靠地处理影像之间可能发生的尺度变化,2个相邻直线及其相交部分用于构建LJL（Line-Junction-Line）描述符,通过对描述符向量的距离评估筛选出候选直线,然后再利用单应矩阵约束确定匹配直线,此算法抗噪性能较好,但最优匹配特征线获取的过程计算量大,不具有普遍适用性;Wang[26]为适应弱纹理影像和大视点变化下的非平面结构场景,根据相邻直线空间接近程度把线段聚集成局部组直线LS（Line Signature）,将每个局部组描述为一个特征向量并利用向量间的相似性度量完成直线匹配,但该算法对于存在多个位置关系比较接近的组直线特征,判断其特征向量的相似性易造成误匹配,且随着正确匹配数目逐渐减少,其复杂度也会显著增加,成功率大为下降,匹配算法有待改进。因此,Wang等[26]匹配算法的基础上,本文联合几何约束条件以及直线组交点分布的方位特征,提出基于直线间几何属性特征相似性约束的组直线匹配算法,该算法首先根据2张影像提取直线的几何关系分别进行特征编组,然后利用核线约束减少待匹配直线组的搜索范围,进而获取与目标直线组相对应的候选直线组集,最后将直线间丰富的几何属性信息描述为特征向量,利用向量间仿射不变性所构建的交比和仿射相似度参数计算直线组的相似性,并对获取总体相似性最大的同名直线组采用分裂成单直线的方式完成直线匹配。

2 算法原理

2.1 算法流程

本文提出基于直线间几何属性特征相似性约束的组直线匹配算法流程如图1所示,该算法在已用LSD （Line Segment Detector）提取直线并通过SIFT（Scale Invariant Feature Transform）匹配获取目标影像和待匹配影像同名点的基础上,首先利用相邻直线间的几何关系将目标影像、待匹配影像提取的直线分别进行编组,提取满足角度、距离等约束条件的直线组;其次将编组后的直线组作为匹配基元,计算目标影像直线组交点在待匹配影像上的核线来获取相应的候选直线组集;再利用直线组的几何属性特征计算目标直线组和候选直线组描述符的相似性,从而获得两幅影像上的同名直线组;最后利用同名直线组单直线的对应关系进行直线段的方向约束将直线组分解为同名单直线完成初步匹配,然后对匹配结果进行检核,过程中主要对结果出现“一对多”、“多对一”的情况进行整合,剔除匹配结果错误的“多”直线,且对正确的“多”直线进行拟合,处理后得到两幅影像上的同名单直线为最终的匹配结果。
图1 特征直线组匹配算法流程

Fig. 1 Flow chart of pair-wise line matching

2.2 定义直线编组的方法

直线编组是将目标影像、待匹配影像提取的直线利用其相邻特征的相似性组合在一起,从而将匹配特征转化为组直线特征。在已有LSD直线提取结果的基础上,根据直线间的拓扑关系对目标影像和待匹配影像提取的直线分别进行特征编组,相应的直线集合为 L L = l 1 , l 2 , · · · , l M 和 L R = r 1 , r 2 , · · · , r N , M , N 分别表示目标影像和待匹配影像提取到的直线数目。以目标影像直线的编组过程为例,假定目标直线为 l i ,待编组直线为 l i + 1 , l i + 2 , · · · , l M ,详细地编组过程描述如下：
（1）首先保证目标直线与待编组直线存在交点。选用该约束条件是由于直线交点具有较高的稳定性,其定位对直线端点的精确程度要求较低,大大避免了对直线连续性的要求,直线交点的分布更能直观反映出编组直线的几何属性信息,因此,满足该条件的直线 l i ' 与目标直线 l i 暂时编为一组,记为 C L ( l i , l i ' , P L ) ,其中 l i 为直线组的交点坐标;
（2）其次对获得的直线组 l j 进行角度约束。判断目标直线 l i 与编组直线 l i ' 所形成的夹角 θ 1 是否满足在一定的范围内,需预先设置合理的角度限值;
（3）最后将（2）中获得的直线组 C L ( l i , l i ' , P L ) 进行距离约束。分别赋予2条直线 l i 和 l i ' 方向向量,判定目标直线 l i 和编组直线 l i ' 端点中与交点 P L 距离较近的点作为 l i 和 l i ' 向量的起始点,反之作为终点,计算 l i 两端点分别到 l i ' 两端点的距离,将4个距离中的最大值 T d 设置在一定范围内,避免因为直线边缘化而生成无意义的编组增加编组数量,与此同时计算2条直线 l i 和 l i ' 的自身长度分别大于该直线起始点到交点 P L 的距离,其描述方式作为直线组几何属性的重要约束条件,便于后续计算直线组的特征相似性。如图2所示,定义两直线 l i 和 l i ' 的方向向量分别为 p 1 p 2 → 和 q 1 q 2 → （箭头代表它们的方位）,交点为 P ,由于 p 1 P → < p 1 p 2 → , q 1 P → < q 1 q 2 → ,有向直线对标记的长度比可表示为 μ 1 = ( p 1 P → · p 1 p 2 → ) p 1 p 2 → 2 和 μ 2 = ( q 1 P → · q 1 q 2 → ) q 1 q 2 → 2 ,此时, μ 1 , μ 2 ∈ ( 0,1 ) 。
图2 目标直线组

Fig. 2 Finding intersection line pairs

上述编组方式适合于任何近景影像,但确定初始直线组时直线间角度不能过大或过小,如果超出合理的限值,对于编组后直线组计算的属性信息应用于匹配约束的意义不大,与此同时直线间的距离不能太远,否则编组直线组的关联性差,共面可能性小。因此,按照合理的限值对2张影像进行编组,最终分别得到目标影像的直线编组特征集为 CL ： CL = C 1 L ( l i 1 , l i ' 1 , P 1 L ) , C 2 L ( l i 2 , l i ' 2 , P 2 L ) , · · · , C M L ( l i M , l i ' M , P M L ) , 待匹配影像的直线编组特征集为 CR ： CR = C 1 R ( r j 1 , r j ' 1 , P 1 R ) , C 2 R ( r j 2 , r j ' 2 , P 2 R ) , · · · , C N R ( r j N , r j ' N , P N R ) 。其中 M , N 分别表示目标影像和待匹配影像提取到的直线数目。

2.3 提取直线间几何属性特征匹配直线组

在已有SIFT匹配获取影像同名点的基础上,以2.2中编组得到的直线组作为匹配基元,匹配过程中对目标影像上任一直线组采用核线约束筛选出待匹配影像上的候选直线组;再依据直线组间具有的几何属性描述目标直线组与候选直线组的特征关系,找到目标直线组到候选直线组集的最佳映射,最大化2个直线组之间的相似性度量,确定候选直线组集中相似值最大的特征直线组为其同名直线组。
2.3.1 核线约束
直线组匹配过程中,利用同名匹配点计算目标影像上任意特征直线组交点在待匹配影像上的核线,借用核线约束可以将匹配空间从二维搜索限制到一维,在很大程度上减小了搜索范围,提高了匹配效率。如图3（a）所示,满足目标影像上预设条件的特征直线组为 C m L ( l i m , l i ' m , P m L ) ,计算其交点 P m L ,确定待匹配影像上直线组交点 P 1 R , P 2 R , · · · , P n R 到核线 H 的距离小于一定阈值 T h 的直线组作为候选直线组,如图3（b）所示待匹配影像上交点 P 1 R , P 2 R , P 3 R , P n R 对应的直线组 C m L ( l i m , l i ' m , P m L ) 为候选直线组。
图3 核线约束示意

Fig. 3 Diagram of epilolar constraint

2.3.2 直线组的几何属性信息描述
由于实验影像存在一定的视差变化,导致直线组对应直线端点的相对位置发生适度地改变,因而利用仿射矩阵或单应矩阵找寻同名特征易出现错误匹配,基于文献[26]本文提出通过限制直线组几何属性信息的变换程度完成组直线匹配,该算法利用直线组中两直线角度、长度比等属性构成的特征描述符计算目标直线组与各候选直线组的相似性测度因而完成同名特征的判断。图4详细考虑了有向直线对4个端点存在的六种相对位置关系,以 图4（a）第一种情况为例,为了实现影像的尺度和旋转不变性,将 p 1 p 2 → 作为参考向量,用连接向量2个端点的方式判断直线对方向向量 p 1 p 2 → 和 q 1 q 2 → 的相对位置关系,其连接后构成的相对角度属性在图4（a）中标记为 θ 1 ∼ 5 ,长度比可表示为 lin e 1 = q 1 q 2 → p 1 p 2 → , lin e 2 = q 1 p 1 → p 1 p 2 → , lin e 3 = q 1 p 2 → p 1 p 2 → , lin e 4 = q 2 p 1 → p 1 p 2 → , lin e 5 = q 2 p 2 → p 1 p 2 → 。已知向量两端点的绝对位置只能利用4个点坐标进行描述,并且特征直线组相似性的判断对于不同的参考点产生不同的结果,因此需要增添上述10个属性信息描述每个端点相对于其他端点的位置关系。如图4（b）中 q 1 到 q 1 ' 相对于 p 2 的位置距离变化不大而相对于 p 1 的位置距离变化较大。
图4 直线编组情况

Fig. 4 Generating grouped line pairs

此外,为了避免光照变化等因素的影响,该算法需要借助梯度属性描述直线组的局部外观信息,梯度属性 g = g 2 g 1 ,其中 g 1 、 g 2 分别为特征直线组中两直线的平均梯度幅值,结合2.2中直线组交点 P 计算出的距离比 μ 1 = ( p 1 P → · p 1 p 2 → ) p 1 p 2 → 2 和 μ 2 = ( q 1 P → · q 1 q 2 → ) q 1 q 2 → 2 ,构成了直线组特征向量的13个属性特征,可用特征向量 v 表示为： v = μ 1 , μ 2 , lin e 1 , lin e 2 , lin e 3 , lin e 4 , lin e 5 , θ 1 ∼ 5 , g 。本文算法利用直线组方向向量 p 1 p 2 → 和 q 1 q 2 → 的端点坐标计算出直线组几何特征属性 μ 1 , μ 2 , lin e 1 , lin e 2 , lin e 3 , lin e 4 , lin e 5 , θ 1 ∼ 5 以及梯度属性 g 共13个属性信息,并将其视为特征向量的存储中介,使后续相似度测度的计算更加有效。
2.3.3 特征直线组的相似性约束
假设目标直线组和候选直线组的特征向量分别表示为 v = μ 1 , μ 2 , lin e 1 , · · · , lin e 5 , θ 1 ∼ 5 , g 和 v ' = μ 1 ' , μ 2 ' , lin e 1 ' , · · · , lin e 5 ' , θ 1 ∼ 5 ' , g ' ,当直线组同时满足 μ 1 - μ 1 ' 和 μ 2 - μ 2 ' 小于阈值 T μ 时,近景影像中局部特征的几何变换可以近似为仿射变换,因此,将描述特征直线组的相似性度量称为仿射相似度,否则称为一般相似度。若要完全实现仿射不变性,需利用特征直线组 μ 1 ∼ 2 和 μ 1 ∼ 2 ' 的属性信息,结合直线特征的相对角度值 θ 1 、长度比 lin e 1 的变化计算仿射相似性,能获取可靠的匹配结果,从而提高特征直线组的显著性。
仿射相似度 S a 计算为：
S a = d μ 1 + d μ 2 + d θ 1 + d lin e 1 + d g Γ = true - ∞                                     其他
其中：
d μ i = 1 - μ i - μ i ' T μ i ∈ 1,2 d θ 1 = 1 - θ 1 - θ 1 ' π 2 d lin e 1 = 1 - max ( lin e 1 , lin e 1 ' ) min ( lin e 1 , lin e 1 ' ) - 1 T line d g = 1 - max ( g , g ' ) min ( g , g ' ) - 1 T g Γ ≡ d μ i , d θ 1 , d lin e 1 , d g ≥ 0 & ( θ 1 - π ) ( θ 1 ' - π ) ≥ 0
式中： d μ i 、 d θ 1 、 d lin e 1 、 d g 分别表示目标直线组和候选直线组间的属性特征;参数 T μ 、 T line 、 T g 是与属性特征相关的阈值;条件 Γ ≥ 0 代表在 Γ 内的所有元素必须同时满足不小于0;条件 ( θ 1 - π ) ( θ 1 ' - π ) ≥ 0 θ 1 , θ 1 ' ∈ [ 0,2 π ] 用于避免直线组间不切实际的局部变形情况。若直线组间各个属性特征构成的条件 Γ < 0 ,赋予直线组间的仿射相似度为无穷大,无需完成剩余计算,迭代停止。为了增强影像局部特征对比度,分别对不同属性进行归一化处理,使属性特征 d μ i 、 d θ 1 、 d lin e 1 、 d g ∈ [ 0,1 ] 。
当 μ 1 - μ 1 ' 和 μ 2 - μ 2 ' 大于阈值 T μ 时,基于直线组4个端点之间的相对位置测量一般相似度 S g 见式（3）, d θ i , d lin e i , d g 的计算方式与式（2）相同。
S g = ∑ i = 1 5 d lin e i + ∑ i = 1 5 d θ i + d g   d lin e i , d θ i , d g ≥ 0 - ∞                                     其他
结合以上2种情况,计算直线组几何属性的总体相似性S为：
S = S a         μ i - μ i ' ≤ T μ 1 4 S g 其他
2.3.4 同名直线组的获取
根据直线组几何属性相似度的总结,给定目标直线组,计算其与每个候选直线组的总体相似性,找到目标直线组到候选直线组的最佳映射,确定候选直线组集中总体相似值最大的特征直线组为其同名直线组。假设目标影像里任一直线组为 ( l i , l i ' ) ,对应待匹配影像筛选出的候选特征直线组集为： ( r j 1 , r j ' 1 ) , ( r j 2 , r j ' 2 ) , · · · , ( r j N , r j ' N ) ,两直线组 ( l i , l i ' ) 和 ( r j 1 , r j ' 1 ) 的总体相似性为 S ij ,其中, N 表示候选直线组的数目, S LS 为同名直线组的相似值。
S LS = max N S ij

2.4 匹配结果后处理

获取的同名直线组 ( l i , l i ' ) 和 ( r j 1 , r j ' 1 ) 并不一定按照 l i 与 r j 1 、 l i ' 与 r j ' 1 对应的方式构成两对同名直线,也可能 l i 与 r j ' 1 、 l i ' 与 r j 1 对应,因此,根据直线组中单直线对应关系进行直线段的方向约束,确保匹配得到的每对同名直线组分裂为2对同名单直线;若同名直线组中单直线 l i 和其中一条单直线 r j 1 对应的方向差为 γ ,保证方向差与影像旋转角度 β 的差值小于规定阈值 T β ,即 γ - β < T β ,则认为匹配的两对同名直线分别为 l i 与 r j 1 , l i ' 与 r j ' 1 。为获得直线组中对应单直线的方向差 γ ,利用同名直线 l i 和 r j 1 端点坐标分别计算斜率 k 1 和 k 2 ,然后根据式（6）获得 γ 的值。
tan γ = ( k 2 - k 1 ) ( 1 + k 1 × k 2 )
由于直线编组过程中相同直线可能参与多次编组与匹配,获得重复的匹配结果并且结果中包括“一对多”、“多对一”的情况,根据文献[27]提出的整合算法对该匹配结果进行后处理,首先记录目标、待匹配影像上同名直线的索引号,然后按照从左到右,再从右到左的顺序依次遍历存储的直线索引,为保证最后匹配结果的唯一性,对直线索引中“一对多”、“多对一”的“多”直线进行检核,若其对应的“多”直线中每条直线的斜率相同且直线间满足共线,则将该情况视为正确的“多”直线进行拟合,用拟合完成后的直线代替原有的“多”直线,若不满足上述情况则将该组匹配结果剔除,最终得到“一对一”的同名单直线。

3 实验与分析

3.1 实验环境与数据源

为验证所提特征组直线匹配算法的可行性和有效性,借助编程平台MATLAB R2014a,实验环境为AMD A10 PRO-7800B R7 CPU、4G内存、64位的操作系统,共采用5组典型的近景影像作为原始数据完成匹配实验,如图5（a）-图5（e）所示,其中图 5（a）-图5（c）影像数据来源于网站http://www.robots.ox.ac.uk/~vgg/data[28],图5（d）-图5（e）影像数据来源于网站http://www.vision.ee.ethz.ch/showroom/zubud/[11]。影像大小分别为800像素×600像素的视角变换、850像素×680像素旋转角度约为25°的旋转变换、800像素×600像素伴随1.5倍尺度缩放的尺度变换、640像素×480像素不同时相的前景变换、640像素×480像素重复纹理的视点变换。
图5 本文算法直线匹配结果

Fig. 5 Matching results of our approach for different scenes.

3.2 匹配参数设置

本文利用直线间角度和距离约束获得初始编组,须研究编组过程中直线夹角 θ 1 、端点距离阈值 T d 取值范围对匹配结果的影响;此外特征直线组相似度的计算共涉及 T μ , T line , T g 3个系数阈值,若阈值发生波动,验证其是否直接影响本文算法的匹配性能也是至关重要的,因此本文以图6（c）具有较大尺度变换的第3组影像数据为例,通过对比分析确定不同的系数阈值完成后续匹配。
图6 实验影像

Fig. 6 Test images

参数阈值 T h 用于核线约束精简候选特征组直线的数量;由于2幅影像存在的视角变化导致同名单直线在不同影像上无法对应,参数阈值 T β 用于同名直线组分裂两对同名单直线;匹配过程中对上述2个参数的取值较为宽泛,本文采用经验化阈值 T h = 1 , T β = 20 ° 。在匹配参数一致的条件下,本文对 θ 1 ∈ [ 30 ° , 150 ° ] 、 θ 1 ∈ [ 45 ° , 135 ° ] 、 θ 1 ∈ [ 15 ° , 165 ° ] 3个取值范围、相应 T d 分别为80个像素、100个像素、120个像素以及 T μ , T line , T g 系数阈值的取值进行匹配实验,实验中以同名直线数目和匹配正确率为标准,逐步缩小 T μ , T line , T g 的取值区间, T μ ∈ [ 0.1,0.5 ] ,步长为0.1,其余2个系数阈值 T line , T g 的选取方法与 T μ 相同,但取值范围不同, T line , T g ∈ [ 1,5 ] ,步长为1。匹配结果验证如表1—表3所示。
表1 直线夹角θ1∈[30°,150°]的直线匹配结果

Tab. 1 Line matching results by different parameterθ1∈[30°,150°]

Td=80/像素 Th=1/像素 Tβ=20°
Tμ值 Tline值 Tg值 整合后同名
直线数目/对		 正确匹配
数目/对		 匹配
正确率∕%
0.1 1 1 225 212 94.22
0.2 2 2 230 218 94.78
0.3 3 3 234 223 95.30
0.4 4 4 231 219 94.81
0.5 5 5 227 214 94.27
表2 直线夹角θ1∈[45°,135°]的直线匹配结果

Tab. 2 Line matching results by different parameterθ1∈[45°,135°]

Td=100/像素 Th=1/像素 Tβ=20°
Tμ值 Tline值 Tg值 整合后同名
直线数目/对		 正确匹配
数目/对		 匹配
正确率∕%
0.1 1 1 260 254 97.44
0.2 2 2 263 257 97.45
0.3 3 3 269 263 97.76
0.4 4 4 265 259 97.20
0.5 5 5 262 256 97.17
表3 直线夹角θ1∈[15°,165°]的直线匹配结果

Tab. 3 Line matching results by different parameterθ1∈[15°,165°]

Td=120/像素 Th=1/像素 Tβ=20°
Tμ值 Tline值 Tg值 整合后同名
直线数目/对		 正确匹配
数目/对		 匹配
正确率∕%
0.1 1 1 250 241 96.40
0.2 2 2 257 248 96.50
0.3 3 3 266 257 96.62
0.4 4 4 263 254 96.58
0.5 5 5 260 251 96.54
从表1—表3可以看出随着直线夹角 θ 1 、距离 T d 的改变,该组影像的同名直线数目和匹配正确率均平稳波动,当 θ 1 ∈ [ 45 ° , 135 ° ] 、 T d = 100 时,匹配直线数目最多且错误匹配较少,可获得较高的匹配正确率。当直线夹角 θ 1 、距离 T d 固定不变时,改变系数阈值 T μ , T line , T g 的取值,发现本文算法受该类阈值影响微弱且匹配过程中表现出较强的鲁棒性,兼顾误匹配和偶然因素的影响,本文实验均选取区间中间值 T μ = 0.3 、 T line = T g = 3 的条件下进行。

3.3 不同算法对比分析

在前面匹配参数设置分析试验的基础上,本文选取参数 θ 1 ∈ [ 45 ° , 135 ° ] , T d = 100 , T μ = 0.3 , T line = T g = 3 对图5所示影像进行组直线匹配,为了更加客观的评价本文算法,在初始同名点及直线提取结果相同的条件下,本文还实现了文献[11]基于LBD描述子、文献[26]基于直线组LS以及文献[19]基于同名点交叉比的直线匹配算法。其中文献[11]实现过程中在原文献描述子的基础上,增加三角网约束与核线约束搜索候选直线用于提高匹配正确率,其与文献[26]、文献[19]的结果整合都采用本文的后处理算法。匹配结果如图5所示,鉴于文章篇幅,仅针对本文算法的匹配结果进行显示,随机标记图中直线特征为不同颜色,相同颜色为同名直线特征。表4统计了不同算法的直线匹配结果,分别对目标影像和待匹配影像参与编组匹配的直线组数目、同名直线组数目、同名直线数目、整合后同名直线数目、正确匹配数目以及匹配正确率、运行时间进行记录,其中正确匹配数目通过人工目视判断。
表4 4种算法匹配结果对比分析

Tab. 4 Comparative analysis of matching results by four methods

实验影像 编组直线组数目/对 不同算法 同名直线
组数目/对		 同名单直线
对数目/对		 整合后同名
直线数目/对		 正确匹配
数目/对		 匹配
正确率∕%		 运行
时间/s
目标影像 待匹配影像
图6(a) 2570 2620 文献[11]
文献[26]
文献[19]
本文算法		 N/A 327 322
341
390
446		 302
321
382
435		 93.7
94.1
97.9
97.5		 101
206
685 1250
N/A 911 135
487 915 217
图6(b) 1603 2218 文献[11]
文献[26]
文献[19]
本文算法		 N/A 223 221
193
366
277		 184
185
357
271		 83.3
95.7
97.5
97.8		 63
301 553 119
N/A 605 107
254 387 135
图6(c) 2359 1887 文献[11]
文献[26]
文献[19]
本文算法		 N/A 109 99
237
214
269		 85
222
207
263		 85.8
93.7
96.7
97.8		 28
456 807 139
N/A 344 132
143
329 593
图6(d) 3793 3345 文献[11]
文献[26]
文献[19]
本文算法		 N/A 378 346
333
371
287		 303
313
364
284		 87.6
94.0
98.1
99.0		 104
564 908 202
N/A 770 129
372 668 164
图6(e) 3196 3474 文献[11]
文献[26]
文献[19]
本文算法		 N/A 303 262
386
297
397		 242
372
273
388		 92.4
96.4
91.9
97.7		 81
466 732 238
N/A 680 96
338 642 241
结合图5和表4分析不同算法的直线匹配结果,可以直观看出匹配正确率基本呈增长趋势,与文献[11]、文献[26]算法相比,本文算法针对每组影像得到的匹配正确率均达到97.5%以上。受不同影像上同一建筑物前景变换、纹理丰富等因素的影响,文献[11]利用LBD描述子匹配得到的同名直线数目最少,这是由于LBD描述子的构建过程中未考虑对应直线支撑区域大小不一的情况,影响同名直线相似性的计算,使匹配得到同名直线数目及正确率波动较大,匹配结果不理想,而本文算法利用直线组几何属性所形成的特征向量描述相关区域的相似性,对不同变换下的实验影像具有普适性。本文算法特征直线组相似性度量的核心与文献[26]相同,因此本文算法可看作该算法的改进,由表4可知,本文算法的匹配正确率略高于文献[26],但在匹配数量上却少于文献[26],这是由于文献[26]算法利用线段局部聚类的方式提出半局部特征进行全局搜索可匹配出较多的同名直线组,尽管其同名直线组与同名直线数目暂时多于本文算法,但经过本文后处理方式进行整合,发现其结果蕴含大量的冗余匹配,直接导致分裂后同名直线数目的锐减,增加了直线误匹配的概率,匹配正确率也随之降低,特别对于图5（a）、（c）存在视角变换和尺度变换的影像更为敏感,算法的稳定性较差。本文算法与文献[26]算法不同的是利用直线间的拓扑关系编组特征直线对,同时借助核线约束、直线间几何属性特征相似性约束提高同名直线组搜索的可靠性,显著降低了冗余匹配,提高了匹配正确率,充分体现了本文算法的优越性。文献[19]通过已有的匹配点构造虚拟线生成新的特征点,然后根据同一平面内点-线不变性来计算待匹配直线的相关性,若直线之间满足这种不变性则认为是同名直线,该算法的匹配正确率与本文算法相差无几,但对于图5（e）重复纹理的视点变换影像匹配正确率较低,这是由于文献[19]没有对构造不变量的特征点做约束要求,这将导致与点对应的直线出现偏差,对于细节信息纹理相似的影像匹配结果的可靠性较弱。
从匹配时间上来看文献[11]、文献[19]的算法运算速度明显快于本文算法,文献[26]与本文算法运算速度都相对较慢,这是由于文献[11]、文献[19]同作为单直线匹配算法分别仅在构建LBD描述子、构造点-线不变量时较为耗时,而文献[26]以及本文算法都将直线组作为匹配基元,匹配前需对直线完成聚类或编组,因此消耗较大,其中本文算法最为耗时的原因是匹配过程中涉及直线间几何属性特征向量的描述,影响了算法的运算效率,但该过程的更新与改进,正是本文算法与其他算法相比提高匹配可靠性的关键所在。此外,从表4还可看出匹配同名直线组数目越多,分裂获得同名单直线数目越多,同时也伴随着匹配结果中“一对多”、“多对一”关系的增多,整合后得到的同名直线数目却没有增多,其原因在于本文后处理对“多”结果进行拟合和检核过程中删除了大部分错误匹配,而其中也包含一些匹配正确的结果被误删,尤其存在较多的错误匹配时,同名直线数目会发生大幅度的减小,后续将对该部分展开针对性的研究,充分利用匹配结果中的冗余信息。
受拍摄角度影响,图5（e）2幅影像中窗户轮廓被部分遮挡,由于不同影像上同一地物被遮挡后的直线特征提取不完整,对应直线端点不一致,无法匹配出正确直线,如何解决影像中部分非连续短直线受遮挡的问题具有一定的挑战性,本文算法在应对此类问题时表现出较好的稳健性,将图5（e）局部放大,如图7所示,其中图7（a）为文献[19]局部直线匹配结果,图7（b）为本文局部直线匹配结果。不难发现,文献[19]算法仅依靠同一平面内点-线的不变性来判断同名直线,易出现部分误匹配的情况,而本文算法结合直线间几何属性特征的相似性约束能呈现出较好的匹配效果,尤其当影像中存在多个相似或相近的纹理特征时,本文算法也同样适应,如图7（c）—图7（d）所示。此外,为了更好地反映本文算法的稳定性和准确性,阈值的选取一般与本文保持一致,即 θ 1 ∈ [ 45 ° , 135 ° ] , T d = 100 , T h = 1 , T β = 20 ° , T μ = 0.3 , T line = T g = 3 ,相同的实验条件下,侧重分析匹配总数和匹配正确率均能取得较好的结果,其中阈值 T h , T β 未对直线匹配结果造成直接影响,在一定范围内可依照实际需求进行设置。
图7 不同算法的局部直线匹配结果

Fig. 7 Local line matching results of different algorithms

4 结论

由于单直线匹配算法缺乏考虑邻近直线间的几何关系,本文提出一种基于直线间几何属性特征相似性约束的组直线匹配算法,该算法通过构建直线组间仿射不变性交比计算直线组的相似性,并以同名直线组分裂成单直线的方式完成直线匹配,其研究成果如下：
（1）通过本文定义直线编组的方法使得直线间特征编组具有任意性,无需考虑任何对应关系,充分简化了直线编组过程。同时,利用核线约束确定候选直线组,可以将匹配空间从二维降到一维,减小了搜索范围,其所消耗的时间控制在130~250 s之间,加快了匹配速度。
（2）当影像中存在多个相同或相近的直线时,仅利用单直线特征间的相似性容易造成误匹配。而本文算法根据特征直线组的几何属性信息,利用角度、长度比等所形成的特征向量计算目标直线组与候选直线组特征向量的仿射相似性,能获取可靠的直线匹配结果,尤其对于实验过程中旋转变换影像组的匹配正确率提升达到了14.5%,且每组实验影像的误匹配率均低至2.5%。
（3）通过本文的匹配结果后处理将“一对多”、“多对一”的情况进行整合,该过程使得直线提取过程中断裂的直线得到合并,同名直线数目约为其他算法的1.4~2.7倍,进而获得2幅影像上同名直线组间、同名单直线间的一一对应关系,最终将匹配结果全部转化为“一对一”的同名直线,匹配正确率最高可达到99.0%。
通过选用不同条件下的近景影像进行阈值分析及直线匹配实验,与LBD描述子和基于直线组LS算法相比,本文算法充分考虑了邻近直线特征关系、纹理相似处单一直线描述子的不稳定性,采用提取特征直线组几何属性信息和计算仿射相似性的方式最大限度地弥补上述问题对直线匹配算法的限制,结果表明该算法具有较好的稳健性和可靠性,尤其对于缺失几何和结构信息的影像,有利于下一步的三维重建并为深入研究组直线匹配提供了一种新思路。相应的,本文算法也存在一定的局限性,主要表现在仅仅采用单一的核线约束未能准确筛选出候选直线组;直线重复编组造成编组后的直线组匹配结果冗余;同时依据直线间几何属性特征向量的仿射不变量交比作为相似性测度须顾及直线共面性条件,对存在较小几何形变的影像可以适用,但对于尺度和畸变差异过大的影像适用性较低。为了进一步提高算法的高效性及适用性,后续对上述存在的问题仍然需要深入研究。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Novak D, Baltsavias E, Schindler K. Reliable image matching with recursive[C]. Proceedings of the Conference on Photogrammetric Image Analysis, 2011: 49-60.

[2]
傅丹, 王超, 徐一丹, 等. 一种直线段匹配的新方法[J]. 国防科技大学学报, 2008,30(1):115-119.

[ Fu D, Wang C, Xu Y D, et al. A new algorism of matching line segments[J]. Journal of National University of Defense Technology, 2008,30(1):115-119. ]

[3]
寇媛, 徐景中. 基于结构特征的遥感影像匹配[J]. 中国图象图形学报, 2013,18(5):565-573.

[ Kou Y, Xu J Z. Algorithm for remote sensing images matching based on the structure characteristics[J]. Journal of Image and Graphics, 2013,18(5):565-573. ]

[4]
Zhang L. Automatic Digital Surface Model (DSM) Generation from Linear Array Images[D]. Zurich: Institute of Geodesy and Photogrammetry, 2005.

[5]
邓刘洋, 沈占锋, 柯映明. 城市建成区遥感影像边界提取与扩张分析[J]. 地球信息科学学报, 2018,20(7):996-1003.

[ Deng L Y, Shen Z F, Ke Y M. Built-up area extraction and urban expansion analysis based on remote sensing images[J]. Journal of Geo-information Science, 2018,20(7):996-1003. ]

[6]
高新凯. 基于几何不变量的直线匹配与三维建模[D]. 大连:大连理工大学, 2017.

[ Gao X K. Line matching and 3D modeling using geometric invariants[D]. Dalian: Dalian University of Technology, 2017. ]

[7]
席学强, 王润生. 基于直线特征的图像-模型匹配算法[J]. 国防科技大学学报, 2000,22(6):70-74.

[ Xi X Q, Wang R S. An algorithm of image model matching based on straight line features[J]. Journal of National University of Defense Technology, 2000,22(6):70-74. ]

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

[ Shao Z F, Chen M. Line-based matching for high-resolution images with robustness for scale, rotation and illumination[J]. Optics and Precision Engineering, 2013,21(3):790-798. ]

[9]
Schmid C, Zisserman A. Automatic line matching across views[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1997: 666-671.

[10]
王竞雪, 崔昊. 局部点、线仿射不变性约束的近景影像直线段匹配[J]. 地球信息科学学报, 2019,21(2):137-146.

[ Wang J X, Cui H. Line segment matching based on local point-line affine invariance constraints for close-range image[J]. Journal of Geo-information Science, 2019,21(2):137-146. ]

[11]
Zhang L L, Koch R. An efficient and robust line segment matching approach based on LBD descriptor and pairwise geometric consistency[J]. Journal of Visual Communication and Image Representation, 2013,24(7):794-805.

[12]
梁艳, 盛业华, 张卡, 等. 利用局部仿射不变及核线约束的近景影像直线特征匹配[J]. 武汉大学学报·信息科学版, 2014,39(2):229-233.

[ Liang Y, Sheng Y H, Zhang K, et al. Linear feature matching method based on local affine invariant and epipolar constraint for close-range images[J]. Geomatics and Information Science of Wuhan University, 2014,39(2):229-233. ]

[13]
欧阳欢, 范大昭, 纪松, 雷蓉. 结合离散化描述与同名点约束的线特征匹配[J]. 测绘学报, 2018,47(10):1363-1371.

[ Ou Y H, Fan D Z, Ji S, et al. Line matching based on discrete description and conjugate point constraint[J]. Acta Geodaetica et Cartographica Sinica, 2018,47(10):1363-1371. ]

[14]
张云生, 朱庆, 吴波, 等. 一种基于三角网约束的立体影像线特征多级匹配方法[J]. 武汉大学学报·信息科学版, 2013,38(5):522-527.

[ Zhang Y S, Zhu Q, Wu B, et al. A hierarchical stereo line matching method based on a triangle constraint[J]. Geomatics and Information Science of Wuhan University, 2013,38(5):522-527. ]

[15]
Jia Q, Gao X K, Fan X, et al. Novel Coplanar Line-Points Invariants for Robust Line Matching Across Views[C]. Proceeding of the 14th European Conference on Computer Vision, 2016: 599-611.

[16]
Fan B, Wu F C, Hu Z Y. Robust line matching through line-point invariants[J]. Pattern Recognition, 2012,45(2):794-805.

[17]
王志衡, 吴福朝. 均值-标准差描述子与直线匹配[J]. 模式识别与人工智能, 2009,22(1):32-39.

[ Wang Z H, Wu F C. Mean-standard deviation descriptor and line matching[J]. Pattern Recognition and Artificial Intelligence, 2009,22(1):32-39. ]

[18]
Wang Z H, Wu F C, Hu Z Y. MSLD: A Robust Descriptor for Line Matching[J]. Pattern Recognition, 2009,42(5):941-953.

[19]
Ramalingam S, Antunes M, Snow D, et al. Line-sweep: Cross-ratio for wide-baseline matching and 3D reconstruction[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2015: 1238-1246.

[20]
文贡坚. 一种基于特征编组的直线立体匹配全局算法[J]. 软件学报, 2006,17(12):2471-2484.

[ Wen G J. A global algorithm for straight line stereo matching based on feature grouping[J]. Journal of Software, 2006,17(12):2471-2484. ]

[21]
Micusik B, Wildenauer H, Kosecka J. Detection and matching of rectilinear structures[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2008.

[22]
Kim H, Lee S. Simultaneous line matching and epipolar geometry estimation based on the intersection context of coplanar line pairs[J]. Pattern Recognition Letters, 2012,33(10):1349-1363.

[23]
Kim H, Lee S, Lee Y. Wide-baseline stereo matching based on the line intersection context for real-time workspace modeling[J]. Journal of the Optical Society of America A Optics Image Science & Vision, 2014,31(2):421-35.

[24]
王竞雪, 朱庆, 王伟玺. 顾及拓扑关系的立体影像直线特征可靠匹配算法[J]. 测绘学报, 2017,46(11):1850-1858.

[ Wang J X, Zhu X, Wang W X. Reliable line matching algorithm for stereo images with topological relationship[J]. Acta Geodaetica et Cartographica Sinica, 2017,46(11):1850-1858. ]

[25]
Li K, Yao J, Lu X H, et al. Hierarchical line matching based on Line-Junction-Line structure descriptor and local homography estimation[J]. Neurocomputing, 2016,184:207-220.

[26]
Wang L, Neumann U, You S. Wide-baseline image matching using Line Signatures[C]. Proceedings of the 12th IEEE Conference on Computer Vision, 2009: 1311-1318.

[27]
王竞雪, 宋伟东, 王伟玺. 同名点及高程平面约束的航空影像直线匹配算法[J]. 测绘学报, 2016,45(1):87-95.

[ Wang J X, Song W D, Wang W X. Line matching algorithm for aerial image based on corresponding points and Z-Plane constraints[J]. Acta Geodaetica et Cartographica Sinica, 2016,45(1):87-95. ]

[28]
Mikolajczyk K, Tuytelaars T, Schmid C, et al. A comparison of affine region detectors[J]. International Journal of Computer Vision, 2005,65(1-2):43-72.

Options
Outlines

/

〈 〉