EN中文

Journal of Geo-information Science >

2024 , Vol. 26 >Issue 7: 1629 - 1645

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

Multi-view Line Matching Based on Multi-view Stereo Vision and Leiden Graph Clustering

  • LAN Zeqing , 1 ,
  • WANG Jingxue , 1, 2, * ,
  • WANG Liqin 3
Expand
  • 1. School of Geomatics, Liaoning Technical University, Liaoning, Fuxin 123000, China
  • 2. Collaborative Innovation Institute of Geospatial Information Service, Liaoning Technical University, Fuxin 123000, China
  • 3. Land Resource Surveying and Planning Institute of Liaoyang City, Liaoyang 111000, China
*WANG Jingxue, E-mail:

Received date: 2024-02-04

  Revised date: 2024-03-27

  Online published: 2024-06-25

Supported by

National Natural Science Foundation of China(41871379)

Liaoning Revitalization Talents Program(XLYC2007026)

Fundamental Applied Research Foundation of Liaoning Province(2022JH2/101300273)

Fold

Abstract

Accurate matching of line features is of paramount importance in the reconstruction and optimization of three-dimensional models. However, traditional dual-view line matching encounters challenges due to a limited number of views, resulting in suboptimal robustness in line matching. For line extraction results with breaks, the number of lines extracted for the same line on different images is different, resulting in poor integrity of straight line matching results. To address these issues, this paper proposes a multi-view line matching algorithm that combines Multiple-View Stereo (MVS) and Leiden graph clustering. The algorithm commences by employing the line extraction algorithm and the MVS three-dimensional reconstruction algorithm on input multi-view images for line information extraction and multi-view three-dimensional information extraction, respectively. This process yields lines on each view, dense three-dimensional points encapsulating the image scene, and the correspondence between object-side three-dimensional points and their corresponding image-side two-dimensional points. Building upon this foundation, the algorithm constructs line descriptors in the image domain by considering lines and their matching point sets within their neighborhoods. Subsequently, leveraging the three-dimensional line projection angle constraints, point-line position relationship constraints, and corresponding point constraints, the algorithm filters matching candidates based on these three geometric constraints. Harnessing the similarity relationships between lines on each view, an undirected graph is constructed. Here, lines on each view serve as nodes, and the similarity scores between lines act as edge weights. Simultaneously, connected components composed of single nodes are removed from the undirected graph, resulting in the set of connected components that represent the initial matching results. In the final stage of this process, nodes of each connected component are reconnected based on same-view collinear constraints, forming many sub-undirected graphs. The Leiden algorithm is then applied to cluster the nodes of these sub-undirected graphs. The clusters composed of a single node in the clustering results represent unsuccessfully matched lines, while clusters composed of two or more nodes signify the presence of corresponding lines across multiple views. Ultimately, the algorithm achieves accurate line matching on multi-view images. The experimental results show that the line matching results using the proposed algorithm are improved in terms of the number of line matches and the matching accuracy relative to other comparison algorithms.

Key words： multi-view line matching; feature matching; geometric constraints; undirected graphs; dense 3D points; multi-view stereo vision; Leiden algorithm

Cite this article

LAN Zeqing , WANG Jingxue , WANG Liqin . Multi-view Line Matching Based on Multi-view Stereo Vision and Leiden Graph Clustering[J]. Journal of Geo-information Science, 2024 , 26(7) : 1629 -1645 . DOI: 10.12082/dqxxkx.2024.240080

1 引言

影像匹配是摄影测量和计算机视觉领域持续研究的关键核心问题。由于直线特征相较于点特征包含更加丰富的物体结构信息，其在真正射影像质量提升[1]；三维重建与优化[2⇓⇓-5]；机器人定位[6]等方面有着较为广泛的应用。但与点匹配相比，直线匹配具有更大的挑战。由于影像在拍摄过程中受遮挡、光照、噪声、视角变换等以及直线提取算法的影响，导致同一直线特征在不同的影像上不能同时被提取出来，或者提取结果差异较大，如提取结果存在不同程度的直线断裂，使同一条直线在不同影像上产生数目不等，直线端点不对应等问题导致直线匹配结果较差，其精度和数量无法满足后续研究需要。
针对上述问题，众多学者对直线匹配算法进行了大量研究，现有的直线匹配方法根据其匹配方式的不同可将其分为2类，分别是基于几何约束的直线匹配方法和基于描述子约束的直线匹配方法。基于几何约束的直线匹配方法常用的几何约束如极线约束、三角网约束以及点线不变约束等。如Zeng等[7]通过极线约束对图像对的直线上的点进行匹配并结合直线特征实现直线的精确匹配。张云生等[8]使用可靠种子点构造相应的三角网来约束初始候选匹配，并通过基于自适应移动窗口的直线相关方法来确定最终的线与线的对应关系。王竞雪等[9]通过直线邻域内匹配点的信息将直线投影到三维空间，计算直线间的垂直距离，重叠距离和点与直线间的位置关系来确定最终的直线匹配关系。基于描述子约束的直线匹配方法则根据直线的局部邻域构造直线描述符并以此来计算直线间的相似度进行直线匹配。Bay等[10]构造了一个颜色直方图作为直线描述符，并使用拓扑过滤器对错误的候选匹配进行剔除。Wang等[11]提出MSLD(Mean-Standard deviation Line Descriptor, MSLD)均值-标准差直线描述子，其首先将直线的平行邻域定义为像素支持区域，然后对其进行分区用于梯度统计，计算不同分区内梯度统计的均值和标准差以生成直线描述符。受MSLD启发，Zhang等[12]提出LBD(Line Band Descriptor, LBD)线带描述符。与MSLD垂直划分支撑区域不同， LBD沿平行直线方向划分支撑区域。每个子区域被称为一个带。对每个带进行梯度统计，同时考虑其上下的带，并将全局高斯权重函数和局部高斯权重函数应用于感兴趣区域的每一行，匹配过程中同时考虑了直线的局部几何特征。
然而上述的直线匹配方法都用于双视图直线匹配。受遮挡，阴影，视角变化等因素的影响，双视图直线匹配结果的鲁棒性较弱。对三维直线重建的完整性和准确性而言，实现多视图之间的直线匹配是必要的。从理论上讲，双视图直线匹配方法能够扩展到多个视图，但随视图数量的增加，导致匹配误差的累积，进而降低匹配精度。且上述算法都仅考虑了直线邻域的局部几何特征或纹理特征，没有考虑多视图场景的整体结构信息。然而在多视直线匹配中，多视图对应场景的整体结构信息至关重要。Fu等[13]中有提到当匹配不同视图中的重复纹理图案时，额外的几何信息将大大提高鲁棒性。
因此基于多视图的直线匹配方法被提出。Heuel等[14]将二维和三维中的几何实体点、线和平面及其不确定性以齐次坐标表示，提出基于不确定的射影几何进行直线的匹配和三维重建，首先使用来自不同视图的任意两条直线估计三维直线，然后将三维直线重新投影到其他视图，根据几何属性计算直线一致性进行匹配。由于不确定性体现在平面相交等几何计算中，因此该方法表现出良好的鲁棒性，然而由于没有考虑光度相似性，其结果很容易受到遮挡影响。Schmid等[15-16]描述了2种类似的多视图线匹配方法。Werner等[2]扩展了这2种方法并发布了一个名为Lmatch (LMATCH: Matlab Toolbox for Matching Line Segments accross Multiple Calibrated Images)的开源工具包。在Lmatch中，从2个视图开始，根据归一化互相关分数遍历和匹配图像线。为了降低时间复杂度，强制执行成对极线几何约束过滤错误匹配。两个视图匹配后使用类似的标准扩展到其他视图。该方法在小尺度的多视图数据集上表现出良好的精度。然而，因为必须遍历所有视图才能构建单个匹配使得该方法的计算成本很高。在该方法中，首先从具有最近相机中心的2个视图生成线匹配，以获得更好的初始两视图匹配。然而，较近的相机中心并不能保证2个视图中有更多的重叠区域。此外，当尺度发生剧烈变化时，计算出的用于评估图像线相似性的互相关分数并不可靠。Elaksher等[17]中计算了每个图像线匹配假设的几何和光度匹配成本。其几何匹配成本是通过从2D线匹配迭代重建3D线得出的残差向量来评估的，其光度成本是由沿着每条图像线放置固定大小的窗口，并对窗口中像素的强度值进行统计分析得到。使用两个成本函数生成和评估所有可能的匹配假设，然后选择具有最小匹配成本的匹配集并计算3D线。然而，由于该方法是针对航空图像集提出的，其图像是有序的并且保证了相邻图像之间的重叠，对于无序的宽基线图像集，由于窗口大小是固定的，所描述的光度成本不适合缩放变化。并且由于其较大的搜索空间，计算成本也不可接受。Wei等[18]中首先在候选特征线对之间建立几何约束，将附加约束的场景平面理 论[19]用于候选匹配特征线对，并使用候选线对导出的局部单应性来验证点和线候选，对于多视图匹配，采用三焦点张量来关联不同视图中的候选；然后构建无向图统一多视图中点和线的几何约束，其中节点为候选的点和线，节点间的边为点和线的几何约束；之后采用重新加权随机游走[20]对无向图节点进行排序；最后对排序后的节点进行分配匹配，并提出了一种用于多视图匹配的聚类方法。其结果在匹配数目和正确率上都取得了不错的效果。然而对于直线提取结果存在断裂时，该算法无法有效实现直线多对一或多对多的匹配，且在部分弱纹理区域其直线匹配的可靠性较弱。
为了提高直线匹配的可靠性。Fu等[13]基于MVS算法[21]提出一种基于无向图的多视图直线匹配方法。通过MVS算法可得到丰富的光度信息与场景的整体结构信息，利用MVS算法获取的稠密三维点与图像直线间的关系可准确地对直线特征进行描述，有效提高直线匹配的完整性和准确性。该方法在利用MVS算法获取稠密三维点的基础上，对各个视图上的特征直线构建直线描述符并以此计算直线间的相似性得分，从而以直线为节点、以直线间的相似性得分为边权重构建无向图。通过对图的连通分量进行主成分分析[22]并使用带有共线约束的DBSCAN(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)聚类方法[23]对直线进行聚类，得到正确率较高的直线匹配结果。然而受聚类方法影响，该算法在聚类过程中有效剔除错误匹配的同时也删除了很多正确的匹配，导致匹配同名直线的数目较少。针对该问题，本文提出一种新的多视图直线匹配算法。该算法在直线相似性计算过程中加入了更为严格的几何约束，并采用Leiden图聚类算法[24]用于初始匹配结果优化，确定最终直线匹配结果。该算法在保证直线匹配准确率的基础上，提高了直线匹配的数目。
在本文中通过构建无向图获取连通分量，其中连通分量是一个宽泛的匹配，包含了各视图中存在相似性关联的所有直线，即若某一视图中某一直线存在断裂情况，断裂的直线也都会在同一连通分量中。同时得益于MVS算法的优秀性能，同一连通分量中的直线会限制在一个相对较小的范围内，经过加入共线约束后的Leiden图聚类算法处理后，可将连通分量中不同视图中的同名直线确定出来。这使得本文方法在面对直线提取结果存在断裂的情况下，仍可取得较好的匹配效果。

2 算法原理

本文算法整体流程如图1所示。该算法首先采用LSD(Line Segment Detector)直线提取算法[25]对多视图像进行直线提取，并通过MVS算法重建得到覆盖图像场景的稠密三维点以及物方三维点与其对应的像方二维点之间的对应关系。然后在此基础上，在像方根据直线及其邻域内的匹配点集构建直线描述符；采用三维直线投影角度约束和点-线位置关系约束及同名点约束筛选可能存在对应关系的候选匹配；根据直线描述符计算不同影像上候选匹配直线间的相似性得分；以各视图上的直线为节点，直线间相似性得分作为边权重，构建多视图直线的无向图；通过广度优先搜索策略遍历无向图获取所有连通分量，删除由单节点构成的连通分量；依据同视图上的共线条件约束对每个连通分量节点间的连接关系进行重构得到子无向图；最后利用Leiden图聚类算法对得到的子无向图节点进行聚类，聚类结果中由单节点构成的簇则是未成功匹配的直线，其他由2个或多个节点构成的簇，即为多视图上的同名直线。
图1 基于多视立体视觉与Leiden图聚类的多视图直线匹配算法流程

Fig. 1 Algorithmic flow of Multi-view line matching based on multi-view stereo vision and Leiden graph clustering

2.1 LSD直线提取及MVS稠密点重建

本文在预处理阶段采用了LSD直线提取算法对影像进行直线提取以及MVS算法获取场景稠密点。下面对这2个算法原理进行概述：LSD直线检测算法首先计算图像中所有点的梯度大小和方向；然后将梯度方向变化小且相邻的点作为一个连通域；接着根据每一个域的矩形度判断是否需要按照规则将其断开以形成多个矩形度较大的域；最后对生成的所有的域做改善和筛选，保留其中满足条件的域，即为最后的直线检测结果。MVS算法首先为每个图像选择一个合适的参考图像形成立体像对；然后对每个立体图像对使用基于Patch的立体匹配算法生成深度图，该算法为每个像素初始化一个随机的三维平面，通过空间传播和随机分配迭代优化每个像素的平面参数，以最小化与参考图像的匹配成本；接着对每个深度图进行一致性检查，移除不一致的点得到精炼的深度图；最后将所有精炼的深度图反向投影到三维空间并进行合并，生成稠密三维点，同时移除重复的点。

2.2 直线描述符构建

MVS算法在得到物方稠密三维点的同时，也获得了物方三维点与其对应的各视图上二维点之间的对应关系。物方三维点集记为X={Xi| i=1,2, …,N}，其中N为物方三维点数目。将第 j张视图上提取的直线集合记为Lj={lkj| k=1,2,…, N L j j=1,2,…,M}，其中 N L j为第j张视图上提取直线的数目，M为输入的图像的数目。假定Xi为物方任一三维点，其在第j张视图上的二维点记为 x i j。假定第j张视图上的第k条直线记为 l k j，以该直线为中心，建立2w+1的邻域窗口（本文设置w为2个像素），确定位于该窗口内的匹配点。如图2所示，物方三维点X2在视图3，视图17，视图53中分别对应二维点 x 2 3 ,   x 2 17 ,   x 2 53，同时二维点 x 2 3 ,   x 2 17 ,   x 2 53分别位于直线 l 421 3 ,   l 212 17 ,   l 256 53的邻域窗口内。
图2 直线邻域窗口同名点示意

Fig. 2 Schematic diagram of the corresponding points in the line neighborhood window

图3 直线描述符示意

Fig. 3 Schematic diagram of line descriptor

将直线 l k j邻域内的点构成的集合记为 D l k j = x i j |   1 ≤ i ≤ N }，该点集 D l k j视为直线 l k j的描述符。当直线邻域内没有匹配点时，则该直线不构建描述符不参与后续匹配。为了避免同一视图直线间产生直接的相似性关联影响后续匹配，当两条直线的邻域窗口重叠时，位于重叠部分的点不会计入2条直线中的任何一条直线的描述符 D l k j。如图3所示，点 x 4 j位于直线 l 1 j和直线 l 2 j的直线邻域的重叠部分，因此该点不计入任一描述符，直线 l 1 j的直线描述符为 D l 1 j = { x 1 j ,   x 2 j ,   x 3 j }，直线 l 2 j的直线描述符为 D l 2 j = { x 5 j ,   x 6 j }。

2.3 匹配候选约束

按照上述直线描述符构建方法对每张影像上提取的直线进行描述符构建，即可在每张影像上得到若干直线描述符，记第j张影像上的描述符集合为 D e s j =   D l k j   |   k = 1,2 , ⋯ ,   N L j '，其中 N L j '为在第j张视图下构建的直线描述符个数，且可能存在 N L j ' ≠ N L j。若直接使用直线描述符计算多张影像间直线的相似度，其复杂度相对较高且在后续无向图构建时会引入过多的噪声边影响后续操作。为解决这一问题，在进行相似度计算之前首先使用三维直线投影角度约束，点-线位置关系约束及同名点约束对匹配直线进行筛选，达到减少直线搜索范围的效果，提高算法匹配效率。下面对这3个约束条件进行详细介绍。

2.3.1 三维直线投影角度约束

理想条件下，不同视图上相同的特征直线在物方三维空间中应该具有相同的属性，但由于重建过程中的误差累积导致不同视图中相同的特征直线经过投影矩阵反投影到三维空间时其位置不会完全契合。但由于直线信息具有较强几何约束，当其反投影的三维直线间的角度值满足某一设定阈值时，在本文中即可认为此组直线具有较强相似性。因此本文通过设定角度阈值作为确定直线匹配候选条件之一。算法原理为假设三维点Xi的空间坐标为(X, Y, Z)，其中Z代表深度值。在得到直线描述符 D l k j后，根据 D l k j中所有二维点 x i j对应的三维点Xi的深度值的中位数假定直线所在的深度，再利用相机位姿与假定的深度值可将直线从二维平面反投影到三维空间当中，通过直线在三维空间中的位置关系可求得不同视图直线间的夹角。在计算角度时不考虑深度值Z，相当于将三维直线投影到XOY面上计算角度值，如图4所示。将不同视图的直线 l k 1 j 1和 l k 2 j 2投影到三维空间记作 l k 1 j 1 '和 l k 2 j 2 '，然后将 l k 1 j 1 '和 l k 2 j 2 '投影到XOY面上记为 l k 1 j 1 ' '和 l k 2 j 2 ' '，计算直线 l k 1 j 1 ' '和 l k 2 j 2 ' '的角度值 A n g ( l k 1 j 1 ' ' , l k 2 j 2 ' ' )。当Ang l k 1 j 1 ' ' , l k 2 j 2 ' ' < 10 °，认为匹配候选满足角度约束条件。
图4 投影直线角度示意

Fig. 4 Schematic diagram of the angle between two projected lines

2.3.2 点-线位置关系约束及同名点约束

除上述不同视图中的直线在三维物方空间中的角度约束之外，其在二维空间中的点-线位置关系约束与同名点约束也是候选匹配的重要条件。其主要原理为位于不同视图的同名直线间，其直线描述符 D ( l k j )中的同名点位于对应直线的同一侧。如图5所示，直线 l 1 1的直线描述符 D ( l 1 1 ) = { x 1 1 ,   x 2 1 ,   x 3 1 ,   x 4 1 }，直线 l 2 2的直线描述符 D ( l 2 2 ) = { x 1 2 ,   x 2 2 ,   x 3 2 ,   x 4 2 ,   x 5 2 , x 6 2 }。由2.2节可知，点 x 1 1 ,   x 2 1 ,   x 3 1 ,   x 4 1和点 x 1 2 ,   x 2 2 ,   x 3 2 ,   x 4 2分别为三维点X1, X2, X3,X4在视图1与视图2上的投影，因此直线 l 1 1和直线 l 2 2的同名点集合 D ( l 1 1 ) ⋂ D ( l 2 2 ) = { X 1 ,   X 2 ,   X 3 ,   X 4 }。由于其中点 x 2 1位于直线 l 1 1的下方，而其同名点点 x 2 2则位于直线 l 2 2的上方，它们不在直线的同一侧。同理，同名点 x 4 1及点 x 4 2也不位于直线的同一侧。图中位于同侧的同名点集合 T ( l 1 1 , l 2 2 ) = { X 1 , X 3 }。当 T ( l k 1 j 1 , l k 2 j 2 ) > D ( l k 1 j 1 ) ⋂ D ( l k 2 j 2 ) / 2（此处 j 1 = 1， j 2 = 2， k 1 = 1， k 2 = 2），即同侧同名点个数 T ( l k 1 j 1 , l k 2 j 2 )大于同名点个数 D ( l k 1 j 1 ) ⋂ D ( l k 2 j 2 )的一半，认为匹配候选满足点-线位置关系约束；当 D ( l k 1 j 1 ) ⋂ D ( l k 2 j 2 ) > m i n ( D ( l k 1 j 1 ) ,   D ( l k 2 j 2 ) ) / 5，即同名点个数 D ( l k 1 j 1 ) ⋂ D ( l k 2 j 2 )大于两直线描述符中点较少的那个描述符的点个数 m i n ( D ( l k 1 j 1 ) ,   D ( l k 2 j 2 ) )的五分之一，则认为匹配候选满足同名点约束。
图5 点-线位置关系示意

Fig. 5 Schematic diagram of point-line position relationship

2.4 无向图构建及连通分量过滤

经过上述三维直线投影角度约束，点-线位置关系约束及同名点约束的筛选减少了直线匹配候选的数目，只有在以上3种情况都满足时才进行直线间的相似性得分计算。不同视图间根据直线描述符计算直线间的相似性得分。然后以各视图上的直线为节点，直线间的相似性分数为边权重构建无向图。通过采用先对整体直线构建无向图获取连通分量，再对各个连通分量分别进行处理的方式可有效节约内存，便于后续聚类处理。
根据2.2小节与2.3小节，计算出不同直线间的相似性得分。直线之间的相似性得分的计算方式如下：
    S i m l k 1 j 1 ,   l k 2 j 2 = D l k 1 j 1 ⋂ D l k 2 j 2 m a x ( D l k 1 j 1 ,   D l k 2 j 2 ) ,       条 件   1   0   ,                                                                                 其 他
式中： j 1 ≠ j 2，即表示直线位于不同的视图。其中条件1即为2.3小节所述的3个约束条件，当同时满足这3个条件时则视为满足条件1，即可计算2条直线相似性得分，否则相似性得分直接为0。此处 ∙代表集合中的元素个数。 D l k 1 j 1 ⋂ D l k 2 j 2表示两直线同名点的个数， m a x ( D l k 1 j 1 ,   D l k 2 j 2 )为两直线描述符中点较多的那个描述符的点个数，在计算相似性得分时将两直线描述符中点较多的那个描述符的点个数 m a x ( D l k 1 j 1 ,   D l k 2 j 2 )作为分母可减少噪声对直线间相似性得分计算的影响。
以各个视图直线为节点，选择不同视图间的直线节点计算相似性得分 S i m l k 1 j 1 ,   l k 2 j 2，当 S i m l k 1 j 1 ,   l k 2 j 2 > 0时在2个节点之间建立连边，边的权重则为两节点的相似性得分 S i m l k 1 j 1 ,   l k 2 j 2。将所有边连接完成后得到无向图G，即无向图的节点最多为 ( M ∙ N L j )。
对构建的无向图G采用广度优先遍历策略对所有节点进行遍历得到的连通分量的集合记为 C = C η |   η = 1,2 ,   ∙ ∙ ∙ ,   N C η }，其中 N C η表示连通分量的个数。该策略从一个节点开始，遍历其所有的邻居节点，再从邻居节点继续重复上述操作直到遍历完成，记作一个连通分量 C η = { l k j }。图6展示了一个简易的无向图，其中相同颜色节点构成一个连通分量记 C 1 = { l 3 3 }， C 2 = { l 1 1 ,   l 1 2 ,   l 2 3 }， C 3 = { l 2 2 ,   l 5 4 }。得到无向图G的所有连通分量后，删除仅包含一个节点的连通分量，如图6中的连通分量C1。
图6 无向图及其连通分量

Fig. 6 Undirected graphs and their connected components

无向图G中每一个连通分量即代表一个初始匹配，图7展示了一个包含10个节点的连通分量的无向图的网络结构图。图8为图7连通分量中10个节点所代表的不同视图上的直线，如节点0，1为视图A中直线0，1； 节点2，3，4为视图B中直线2，3，4等。
图7 连通分量网络结构

Fig. 7 Diagram of the connected component network

图8 连通分量各个节点对应直线

Fig. 8 Lines corresponding to each node of the connected component

2.5 基于同视图共线约束的子无向图构建

对2.4节得到的各个连通分量，需进一步加入同视图共线约束对连通分量的所有节点重新连接构建子无向图。同视图共线约束定义为：当两直线来自同一视图，若两直线同时满足直线间夹角 A n g l k 1 j ,   l k 2 j < 2.5 °，直线间垂直距离 d ( l k 1 j ,   l k 2 j ) < 2，直线间重叠距离 O l k 1 j ,   l k 2 j = = 0，则视为两直线共线反之则不共线。其中垂直距离为两直线中点到另一直线的垂直距离的均值，即 d l k 1 j ,   l k 2 j = ( d 1 + d 2 ) / 2；重叠距离为将直线 l k 2 j的2个端点投影至另一直线 l k 1 j产生的重叠部分 d 3， O l k 1 j ,   l k 2 j = d 3，二者计算方式分别如图9所示。
图9 垂直距离及重叠距离示意

Fig. 9 Schematic diagram of vertical distance and overlap distance

增加共线约束后的相似性得分 S i m 2 l k 1 j 1 ,   l k 2 j 2的计算公式为：
          S i m 2 l k 1 j 1 , l k 2 j 2 = - 10   000 ,               条 件 2 S i m l k 1 j 1 , l k 2 j 2 ,     其 他       j 1 =   j 2     S i m 2 l k 1 j 1 , l k 2 j 2 = S i m l k 1 j 1 , l k 2 j 2                     其 他
式中：条件2即为上述的直线不共线时的条件。 S i m 2 l k 1 j 1 ,   l k 2 j 2 = S i m l k 1 j 1 ,   l k 2 j 2表示与式(1)的计算方式相同。为避免Leiden算法聚类时同一簇中存在来自同一视图且不共线的直线，将来自同一视图且不共线的两直线的相似性得分记为-10 000。根据式(2)重新对连通分量Cη内两两节点间的相似性得分进行计算，当得分 S i m 2 l k 1 j 1 ,   l k 2 j 2 ≠ 0时，对两节点建立边，边权重为两节点间的相似性得分，得到新的子无向图Gη，其中 1 ≤ η ≤ N C η，η表示子无向图序号与连通分量Cη序号相对应。

2.6 基于Leiden图聚类的子无向图节点聚类

对子无向图Gη采用Leiden图聚类算法对其节点进行聚类即可得到最终的直线匹配结果。最终每个社区（簇）中包含的节点对应的直线即为一组同名直线。
Leiden算法通过优化质量函数来保证所有节点都是局部最优分配的，该算法由3个阶段组成： ① 节点的局部移动； ② 改善社区划分； ③ 基于改善的社区对网络进行聚合，使用未改善的社区为聚合网络创建初始社区。Leiden算法的质量函数基于常数波茨模型(Constant Potts Model, CPM)， 式(3)为CPM的定义：
H = ∑ c e c - γ n c 2
式中： ec表示社区c中边的数量； nc为社区c中节点的数量。分辨率参数γ充当一种阈值，社区的密度至少为γ，而社区之间的密度应该低于γ。较高的分辨率会导致更多的社区，较低的分辨率为导致较少的社区。该质量函数保证了社区内部强连接的同时使社区间的分离度良好。在实际应用当中会根据边与节点权重等对质量函数作出调整，如式（4）所示。
H = 1 2 m ∑ c e c - γ N C 2
式中： m为网络中所有边权重的总和； ec为社区c内部边权重的2倍； Nc为社区c内部节点权重的总和。由于本文算法中无节点权重，因此NC=0，所以参数γ不对本文算法造成影响，在本文中参数γ设置为0。由于在2.5小节中对来自同一视图且不共线的节点之间设置了极大的负权值，根据质量函数可知，在社区划分的过程中同一社区中不会存在来自同一视图且不共线的节点。
在Leiden算法中无向图Gη的每个节点最开始都作为一个单独的社区，通过移动节点到另一社区以提高质量函数，之后改善社区划分，聚合网络，再不断重复上述步骤最终将无向图Gη的每个节点划分到最合理的社区，即得到最终同名直线结果。

3 实验与分析

本文实验环境为i7-8750H处理器，16 G运行内存的笔记本电脑。实验影像数据取自场景(a)、场景(b)、场景(c)景3个不同场景。场景(a)共32张影像，场景(b)共28张影像，场景(c)共59张影像。其中场景(a)、场景(b)的影像为使用大疆M300 RTK(Real-Time Kinematic, RTK)无人机拍摄的影像，场景(c) 的影像为文献[13]中所使用到的影像。本文采用了经典的openmvg+openmvs的三维重建流程获取稠密三维点用于后续实验。图10分别展示了场景(a)、场景(b)、场景(c) 3个场景的影像通过openmvg+openmvs三维重建流程得到的稠密三维点。为排除直线提取算法对匹配效果的影响，本文实验统一采用同样的LSD直线提取结果进行实验。
图10 各场景稠密三维点

Fig. 10 Dense 3D points in each scene

3.1 不同聚类方法对比分析

为了验证本文所用Leiden图聚类算法的优势，在同一连通分量下对Leiden图聚类方法和文献[13]中的聚类方法进行对比，该处对图7展示的连通分量分别使用这2种聚类方法对其节点进行聚类。连通分量各个节点所对应的直线，即未匹配的直线如图8所示。使用文献[13]方法得到的聚类结果，即直线匹配结果如图11所示，本文聚类方法得到的直线匹配结果如图12所示，其中红色的直线为各个视图上成功匹配的同名直线，错误匹配的直线已用蓝色显示。
图11 文献[13] 直线匹配结果

Fig. 11 Line matching results by method in Ref.[13]

图12 本文方法直线匹配结果

Fig. 12 Line matching results by proposed algorithm

表1总结了该连通分量上本文聚类方法与文献[13]聚类方法得到的匹配结果，在A、B、C、D、E 5张视图共10条直线上，文献[13]方法匹配了9条直线，但有4条直线匹配错误，本文方法匹配了8条直线，无错误匹配。实验表明，相较于文献[13]中采用的通过图的主成分分析法将节点置于统一距离度量下再使用带有共线约束的DBSCAN来进行聚类的方法，本文采用的聚类方法在对相同连通分量进行处理时会得到更好的匹配结果。
表1 基于连通分量的直线匹配结果

Tab. 1 Line matching results based on connected components

方法 直线总数/条 匹配直线
数/条		 正确匹配
直线数/条		 正确率/%
文献[13] 10 9 5 55.6
本文方法 10 8 8 100.0

3.2 不同方法直线匹配结果对比分析

为了验证本文方法的性能，本文在图10所示3个场景上与文献[13]、文献[18]的方法进行了对比分析。在场景A、场景B、场景C中分别选取了6、16、16张影像进行直线匹配。并对3个场景的多视图直线匹配结果中均选取了3个代表性的视图上的直线匹配结果进行对比分析。图13展示了本文算法在3个场景上的三视图直线匹配结果。
图13 本文3个视图直线匹配结果

Fig. 13 Three-view line matching results by proposed algorithm

通过表2可以看出，在本文实验中，本文方法在直线匹配数目以及匹配直线正确率上都取得了不错的效果。其中在场景B上的匹配效果最为突出，共匹配了1 343条直线，较文献[13]方法的105条匹配直线高出1 238条，较文献[18]方法的1 129条匹配直线也高出了214条，且在匹配正确率上，本文方法正确率为100%与文献[13]正确率相同，相较文献[18]的90.6%的正确率则高出9.4%。此外在场景A中本文的直线匹配数目584条，正确率99.1%，在场景C视图5678-5679-5680中本文的直线匹配数目439条，正确率100%，在场景C视图5706-5710-5716中本文的直线匹配数目242条，正确率100%，相较文献[13]及文献[18]，除了场景C视图5706-5710-5716中本文方法的匹配数目低于文献[18]外，综合来看本文算法的匹配效果是较好的。
表2 直线匹配结果

Tab. 2 Line matching results

视图编号 使用方法 各视图提取直线数/条 同名直线数/条 正确直线数/条 正确率/%
场景A 03/17/53 文献[13] 8 713/5 166/4 522 152 152 100.0
文献[18] 8 713/5 166/4 522 659 602 91.4
本文方法 8 713/5 166/4 522 584 579 99.1
场景B 04/05/06 文献[13] 6 428/6 139/5 893 105 105 100.0
文献[18] 6 428/6 139/5 893 1 129 1 023 90.6
本文方法 6 428/6 139/5 893 1 343 1 343 100.0
场景C 5678/5679/5680 文献[13] 2 904/2 909/3 031 14 14 100.0
文献[18] 2 904/2 909/3 031 417 414 99.3
本文方法 2 904/2 909/3 031 439 439 100.0
场景C 5706/5710/5716 文献[13] 3 465/3 736/3 893 21 21 100.0
文献[18] 3 465/3 736/3 893 439 394 89.7
本文方法 3 465/3 736/3 893 242 242 100.0
由于算法的局限性，文献[18]方法无法对断裂的直线进行多对一或多对多的匹配。而本文所提方法可对直线进行多对一或多对多的匹配。如图14和图15所示（直线突出显示为蓝色），图14中同名直线5对应图15中的同名直线233，由图14可看出文献[18]方法仅进行了一对一的匹配，而由图15则可看出本文可以对直线进行多对一的匹配。因此实际情况上本文匹配的同名直线中包含的直线数量较文献[18]方法更多。
图14 文献[18]直线匹配结果(场景A，视图03-17-53)

Fig. 14 Line matching by method in Ref.[18] (scene A, view 03-17-53)

图15 本文直线匹配结果（场景A，视图03-17-53）

Fig. 15 Line matching by proposed method (scene A, view 03-17-53)

此外，通过利用MVS算法得到的可靠稠密点所提供的信息，本文方法即使在纹理较弱的区域同样可以对直线间的关系进行可靠的描述，从而在弱纹理区域也取得不错的匹配效果。图17—图19分别展示了在场景B的视图04-05-06中文献[13]，文献[18]及本文方法在图16所圈出的屋顶区域的直线匹配结果。图17—图19中红色直线代表正确匹配，蓝色直线代表错误匹配。
图16 直线匹配区域

Fig. 16 Line matching area

图17 文献[13]匹配结果（场景B，视图04-05-06）

Fig. 17 Line matching results by method in Ref.[13] (scene B, view 04-05-06)

图18 文献[18]匹配结果（场景B，为视图04-05-06）

Fig. 18 Line matching results by method in Ref.[18] (scene B, view 04-05-06)

图19 本文匹配结果（场景B，视图04-05-06）

Fig. 19 Line matching results by proposed method (scene B, view 04-05-06)

在图16圈出的纹理较弱的区域中，如图19所示，本文得到了较多的匹配的直线且无错误匹配。文献[13]与本文是基于相同的稠密点对直线关系进行描述，但在本文实验中，文献[13]算法所使用的图主成分分析的方法并不能十分有效地将同名直线在统一的距离度量下与其他直线区分出来，导致添加共线约束的DBSCAN算法在聚类时去掉了大量的正确匹配，如图17，文献[13]的匹配结果中无错误匹配但匹配的直线数量较少。而文献[18]使用的几何约束在该区域中并不能很好地对直线间的相似性关系进行描述。如图18所示，该方法虽取得了较多匹配的直线，但包含了过多的错误匹配，图中错误匹配直线均用蓝色显示。通过实验结果对比可知，在该弱纹理区域中本文方法取得的直线匹配结果较其他2种方法无论是匹配直线的数量还是正确率都是最优的。

3.3 运行时间分析

在运行时间上，本文从场景A的32张影像，场景B的28张影像，场景C的59张影像使用openmvg+openmvs重建稠密点所耗费的时间分别是11、16、19 min钟。而在场景A、场景B、场景C 3个不同的场景上，文献[13]、文献[18]和本文的直线匹配算法运行的时间如图20所示。本文方法中最耗时的部分为2.2节直线描述符构建。在该阶段中，需要将所有的稠密三维点放入各视图对应的直线邻域中，其时间复杂度为O(M·N)，并且由于使用的openmvs副产品提供的可见信息，真实的复杂度远小于O(M·N)。在图构建阶段时间复杂度为O(N1)，其中N1为实验中选择计算的视图对的对数。由于在使用文献[18]提供的测试代码时需要手动选择对哪些视图对进行计算，为控制变量相同， 3种方法选择的视图对都是完全相同的。因本文方法与文献[13]方法的主要差别在于对连通分量处理的部分，而在整个直线匹配过程中对连通分量进行处理所占用的时间较少，在3个场景中文献[13]及本文方法在连通分量处理部分所用的时间均在1 min内，因此本文方法的时间复杂度与文献[13]方法基本相同。在文献[18]方法中，其耗时最多的阶段为图构建阶段，其次为随机游走为节点排序阶段，在不考虑内部计算的复杂程度，其图构建阶段的整体时间复杂度为O(N1)，随机游走阶段时间复杂度为O(C·N1)，其中C为迭代次数。但从图21可看出其内部计算的复杂程度远大于本文。图21展示了在场景(c)中输入不同数量的影像时算法的运行时间，由于本文方法和文献[13]方法主要耗时是在直线描述符构建阶段，该阶段的耗时取决于三维点数目N，因此在增加影像数量后本文方法的运行时间无显著变化。而在文献[18]方法中其耗时最多2个阶段的时间都是与N1成正比，受其内部计算的复杂度的影响，在增加影像数目时，即N1增加时，其运行时间变化显著。与文献[18]相比，在场景A、场景B上，本文方法的运行时间即使在加上稠密点重建的耗时后，整体用时仍比文献[18]方法用时更短；而在场景C上，实验最多只对16张影像进行了匹配，由图21可知，理论上在一定数量后本文方法的运行时间应较文献[18]方法更短，受限于设备运行内存原因没有进行具体实验。
图20 不同直线匹配算法的运行时间

Fig. 20 Running time of different line matching algorithms

图21 不同影像数量下各方法运行时间

Fig. 21 Running time of different line matching algorithms under different number of images

4 结论

4.1 总结

本文提出一种基于多视立体视觉与图聚类算法的多视图直线匹配方法。该方法基于MVS算法成果构建直线描述符，准确地描述了多视图直线间的相似性关系，并结合物方直线间角度、点-线位置关系和同名点数目这三重几何约束确定初始匹配候选，提高匹配候选准确性，缩小直线搜索范围；通过构建无向图记录各视图上的直线间的关系，采用对无向图各个连通分量分别处理的方式减小了内存压力有利于节点聚类；最后对各个连通分量基于同视图共线约束构建子无向图并使用Leiden算法对节点进行聚类，实现了多视图上的多对多、多对一的有效直线匹配，最终得到多视图上准确的直线匹配结果。实验结果中，在效果最好的场景B上，共匹配了1 343条直线，较文献[13]方法多出1 238条，较文献[18]方法的多出了214条；同时在匹配正确率上，本文方法正确率为100%，较文献[18]的90.6%的正确率则高出9.4%。且在所有场景中本文方法的匹配正确率都达到了99%以上。综合考虑直线匹配数目及准确率，实验表明本文方法相较对比算法表现出更好的效果。

4.2 讨论

在整个实验过程中，本文方法并没有针对某个场景或视图对算法中的阈值进行调整，最终仍能得到较好匹配结果。因为在本文算法的初始匹配阶段中仅需得到宽泛的匹配，所以本文算法对相似性得分表现出不敏感的性质。得益于此，本文方法在阈值设定方面较为宽松，对数据的适应能力较强。但是该方法也具有局限性，由于在整个算法过程中十分依赖于可靠的三维点信息，对于MVS算法重建效果较差稠密点效果不好的区域，本文方法则很难取得理想的效果，针对该问题有待进一步深入研究。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Wang Q, Yan L, Sun Y B, et al. True orthophoto generation using line segment matches[J]. The Photogrammetric Record, 2018, 33(161):113-130. DOI:10.1111/phor.12229

[2]
Werner T, Zisserman A. New techniques for automated architectural reconstruction from photographs[M]// Computer Vision — ECCV 2002. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002:541-555. DOI:10.1007/3-540-47967-8_36

[3]
赵红蕊, 秦进春, 谭琪凡. 基于直线特征优化的建筑物三维重建[J]. 建筑科学与工程学报, 2022, 39(4):81-89.

[Zhao H R, Qin J C, Tan Q F. 3D reconstruction of buildings based on line feature optimization[J]. Journal of Architecture and Civil Engineering, 2022, 39(4):81-89.] DOI:10.19815/j.jace.2021.07138

[4]
曹林. 基于倾斜影像线特征的建筑物三维模型重建与优化方法研究[D]. 郑州: 战略支援部队信息工程大学, 2020.

[ Cao L. Research on 3D Building Model Reconstruction and Optimization Method Based on Line Festures of Oblique Images[D]. Zhengzhou: Information Engineering University, 2020.]

[5]
池雨灿. 基于图像边缘特征的空间目标重建与评估方法[D]. 哈尔滨: 哈尔滨工业大学, 2019.

[ Chi Y C. Reconstruction and Evaluation Based on Image Edge Feature for Space Target[D]. Harbin: Harbin Institute of Technology, 2019.]

[6]
Aider O A, Hoppenot P, Colle E. A model-based method for indoor mobile robot localization using monocular vision and straight-line correspondences[J]. Robotics and Autonomous Systems, 2005, 52(2/3):229-246. DOI:10.1016/j.robot.2005.03.002.

[7]
Zeng J X, Yu S, Fu X, et al. A line segments matching method based on epipolar-line constraint and line segment features[J]. Journal of Software, 2011, 6(9):1746-1754. DOI:10.4304/jsw.6.9.1746-1754

[8]
张云生, 朱庆, 吴波, 等. 一种基于三角网约束的立体影像线特征多级匹配方法[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.] DOI:10.13203/j.whugis2013.05.002.

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

DOI

[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.] DOI:10.11947/j.AGCS.2016.20140527

[10]
Bay H, Ferraris V, Van Gool L. Wide-baseline stereo matching with line segments[C]// 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). IEEE, 2005:329-336. DOI:10.1109/CVPR.2005.375

[11]
Wang Z H, Wu F C, Hu Z Y. MSLD: A robust descriptor for line matching[J]. Pattern Recognition, 2009, 42(5):941-953. DOI:10.1016/j.patcog.2008.08.035

[12]
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. DOI:10.1016/j.jvcir.2013.05.006

[13]
Fu K P, Shen S H, Hu Z Y. Line matching across views based on multiple view stereo[J]. Acta Automatica Sinica, 2014, 40(8):1680-1689. DOI:10.1016/s1874-1029(14)60017-3

[14]
Heuel S, Forstner W. Matching, reconstructing and grouping 3D lines from multiple views using uncertain projective geometry[C]// Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR. IEEE, 2001:II. DOI:10.1109/CVPR.2001.991006

[15]
Schmid C, Zisserman A. Automatic line matching across views[C]// Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, 1997:666-671. DOI:10.1109/CVPR.1997.609397

[16]
Schmid C, Zisserman A. The geometry and matching of lines and curves over multiple views[J]. International Journal of Computer Vision, 2000, 40(3):199-233. DOI: 10.1023/A:1008135310502

[17]
Elaksher A F. Automatic line matching across multiple views based on geometric and radiometric properties[J]. Applied Geomatics, 2011, 3(1):23-33. DOI:10.1007/s12518-011-0044-2

[18]
Wei D, Zhang Y, Liu X, et al. Robust line segment matching across views via ranking the line-point graph[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2021, 171:49-62. DOI:10.1016/j.isprsjprs.2020.11.002

[19]
Luong Q T, Viéville T. Canonic representations for the geometries of multiple projective views[M]// Computer Vision — ECCV '94. Berlin, Heidelberg: Springer Berlin Heidelberg, 1994:589-599. DOI:10.1007/3-540-57956-7_66

[20]
Cho M, Lee J, Lee K M. Reweighted random walks for graph matching[C]// European Conference on Computer Vision. Berlin, Heidelberg: Springer, 2010:492-505.10.1007/978-3-642-15555-0_36

[21]
Shen S H. Accurate multiple view 3D reconstruction using patch-based stereo for large-scale scenes[J]. IEEE Transactions on Image Processing: a Publication of the IEEE Signal Processing Society, 2013, 22(5):1901-1914. DOI:10.1109/TIP.2013.2237921

[22]
Saerens M, Fouss F, Yen L, et al. The principal components analysis of a graph, and its relationships to spectral clustering[C]// European Conference on Machine Learning. Berlin, Heidelberg: Springer, 2004:371-383.10.1007/978-3-540-30115-8_35

[23]
Sander J, Ester M, Kriegel H P, et al. Density-based clustering in spatial databases: The algorithm GDBSCAN and its applications[J]. Data Mining and Knowledge Discovery, 1998, 2(2):169-194. DOI:10.1023/A:1009745219419

[24]
Traag V A, Waltman L, van Eck N J. From Louvain to Leiden: Guaranteeing well-connected communities[J]. Scientific Reports, 2019, 9(1):5233. DOI:10.1038/s41598-019-41695-z

PMID

[25]
Grompone von Gioi R, Jakubowicz J, Morel J M, et al. LSD: A fast line segment detector with a false detection control[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(4):722-732. DOI:10.1109/TPAMI.2008.300

PMID

Options
Outlines

/

〈 〉