算法流程
本文算法整体流程如图1所示。该算法首先采用LSD(Line Segment Detector)直线提取算法对多视图像进行直线提取，并通过MVS算法重建得到覆盖图像场景的稠密三维点以及物方三维点与其对应的像方二维点之间的对应关系。
然后在此基础上，在像方根据直线及其邻域内的匹配点集构建直线描述符；采用三维直线投影角度约束和点-线位置关系约束及同名点约束筛选可能存在对应关系的候选匹配；根据直线描述符计算不同影像上候选匹配直线间的相似性得分；以各视图上的直线为节点，直线间相似性得分作为边权重，构建多视图直线的无向图；通过广度优先搜索策略遍历无向图获取所有连通分量，删除由单节点构成的连通分量；依据同视图上的共线条件约束对每个连通分量节点间的连接关系进行重构得到子无向图；最后利用Leiden图聚类算法对得到的子无向图节点进行聚类，聚类结果中由单节点构成的簇则是未成功匹配的直线，其他由2个或多个节点构成的簇，即为多视图上的同名直线。
图1 基于多视立体视觉与Leiden图聚类的多视图直线匹配算法流程
关键技术
2.1 LSD直线提取及MVS稠密点重建
LSD直线检测算法首先计算图像中所有点的梯度大小和方向；然后将梯度方向变化小且相邻的点作为一个连通域；接着根据每一个域的矩形度判断是否需要按照规则将其断开以形成多个矩形度较大的域；最后对生成的所有的域做改善和筛选，保留其中满足条件的域，即为最后的直线检测结果。
MVS算法首先为每个图像选择一个合适的参考图像形成立体像对；然后对每个立体图像对使用基于Patch的立体匹配算法生成深度图，该算法为每个像素初始化一个随机的三维平面，通过空间传播和随机分配迭代优化每个像素的平面参数，以最小化与参考图像的匹配成本；接着对每个深度图进行一致性检查，移除不一致的点得到精炼的深度图；最后将所有精炼的深度图反向投影到三维空间并进行合并，生成稠密三维点，同时移除重复的点。
2.2 直线描述符构建
MVS算法在得到物方稠密三维点的同时，也获得了物方三维点与其对应的各视图上二维点之间的对应关系。物方三维点集记为X={Xi|i=1,2,...,N}，其中N为物方三维点数目。
将第j张视图上提取的直线集合记为Lj={lkj|k=1,2,...,NLj; j=1,2,...,M}，其中NLj为第j张视图上提取直线的数目，M为多视图像输入的图像的数目。
图2 直线描述符示意
2.3 匹配候选约束
按照上述直线描述符构建方法对每张影像上提取的直线进行描述符构建，即可在每张影像上得到若干直线描述符。若直接使用直线描述符计算多张影像间直线的相似度，其复杂度相对较高且在后续无向图构建时会引入过多的噪声边影响后续操作。为解决这一问题，在进行相似度计算之前首先使用三维直线投影角度约束，点-线位置关系约束及同名点约束对匹配直线进行筛选，达到减少直线搜索范围的效果，提高算法匹配效率。
三维直线投影角度约束
不同视图上相同的特征直线在物方三维空间中应该具有相同的属性，但由于重建过程中的误差累积导致不同视图中相同的特征直线经过投影矩阵反投影到三维空间时其位置不会完全契合。但由于直线信息具有较强几何约束，当其反投影的三维直线间的角度值满足某一设定阈值时，在本文中即可认为此组直线具有较强相似性。
点-线位置关系约束
位于不同视图的同名直线间，其直线描述符D(lkj)中的同名点位于对应直线的同一侧。当同侧同名点个数大于同名点个数的一半，认为匹配候选满足点-线位置关系约束。
同名点约束
当同名点个数大于两直线描述符中点较少的那个描述符的点个数的五分之一，则认为匹配候选满足同名点约束。
图3 点-线位置关系示意
2.4 无向图构建及连通分量过滤
经过上述三维直线投影角度约束，点-线位置关系约束及同名点约束的筛选减少了直线匹配候选的数目，只有在以上3种情况都满足时才进行直线间的相似性得分计算。不同视图间根据直线描述符计算直线间的相似性得分。
然后以各视图上的直线为节点，直线间的相似性分数为边权重为边权重构建无向图。通过采用先对整体直线构建无向图获取连通分量，再对各个连通分量分别进行处理的方式可有效节约内存，便于后续聚类处理。
图4 无向图及其连通分量
2.5 基于同视图共线约束的子无向图构建
对得到的各个连通分量，需进一步加入同视图共线约束对连通分量的所有节点重新连接构建子无向图。同视图共线约束定义为：当两直线来自同一视图，若两直线同时满足直线间夹角Ang(lk1j,lk2j)<2.5°，直线间垂直距离d(lk1j,lk2j)<2，直线间重叠距离O(lk1j,lk2j)=0，则视为两直线共线反之则不共线。
2.6 基于Leiden图聚类的子无向图节点聚类
对子无向图Gη采用Leiden图聚类算法对其节点进行聚类即可得到最终的直线匹配结果。最终每个社区（簇）中包含的节点对应的直线即为一组同名直线。
Leiden算法通过优化质量函数来保证所有节点都是局部最优分配的，该算法由3个阶段组成：①节点的局部移动；②改善社区划分；③基于改善的社区对网络进行聚合，使用未改善的社区为聚合网络创建初始社区。
H = 1/(2m) * ∑[ec - γNC2] 其中： m - 网络中所有边权重的总和 ec - 社区c内部边权重的2倍 NC - 社区c内部节点权重的总和（本文中NC=0）
实验结果与分析
为了验证本文方法的性能，本文在3个场景上与文献[13]、文献[18]的方法进行了对比分析。在场景A、场景B、场景C中分别选取了6、16、16张影像进行直线匹配。
表1 直线匹配结果
| 场景 | 视图编号 | 使用方法 | 各视图提取直线数/条 | 同名直线数/条 | 正确率/% | ||
|---|---|---|---|---|---|---|---|
| 视图1 | 视图2 | 视图3 | |||||
| 场景A | 03/17/53 | 文献[13] | 8713 | 5166 | 4522 | 152 | 100.0 |
| 文献[18] | 8713 | 5166 | 4522 | 659 | 91.4 | ||
| 本文方法 | 8713 | 5166 | 4522 | 584 | 99.1 | ||
在运行时间上，本文从场景A的32张影像，场景B的28张影像，场景C的59张影像使用openmvg+openmvs重建稠密点所耗费的时间分别是11、16、19分钟。
图5 不同直线匹配算法的运行时间
本文方法中最耗时的部分为直线描述符构建。在该阶段中，需要将所有的稠密三维点放入各视图对应的直线邻域中，其时间复杂度为O(M·N)，并且由于使用的openmvs副产品提供的可见信息，真实的复杂度远小于O(M·N)。
图6 不同影像数量下各方法运行时间
结论
4.1 总结
本文提出一种基于多视立体视觉与图聚类算法的多视图直线匹配方法。该方法基于MVS算法成果构建直线描述符，准确地描述了多视图直线间的相似性关系，并结合物方直线间角度、点-线位置关系和同名点数目这三重几何约束确定初始匹配候选，提高匹配候选准确性，缩小直线搜索范围。
通过构建无向图记录各视图上的直线间的关系，采用对无向图各个连通分量分别处理的方式减小了内存压力有利于节点聚类；最后对各个连通分量基于同视图共线约束构建子无向图并使用Leiden算法对节点进行聚类，实现了多视图上的多对多、多对一的有效直线匹配，最终得到多视图上准确的直线匹配结果。
实验结果中，在效果最好的场景B上，共匹配了1343条直线，较文献[13]方法多出1238条，较文献[18]方法的多出了214条；同时在匹配正确率上，本文方法正确率为100%，较文献[18]的90.6%的正确率则高出9.4%。且在所有场景中本文方法的匹配正确率都达到了99%以上。
4.2 讨论
在整个实验过程中，本文方法并没有针对某个场景或视图对算法中的阈值进行调整，最终仍能得到较好匹配结果。因为在本文算法的初始匹配阶段中仅需得到宽泛的匹配，所以本文算法对相似性得分表现出不敏感的性质。得益于此，本文方法在阈值设定方面较为宽松，对数据的适应能力较强。
但是该方法也具有局限性，由于在整个算法过程中十分依赖于可靠的三维点信息，对于MVS算法重建效果较差稠密点效果不好的区域，本文方法则很难取得理想的效果，针对该问题有待进一步深入研究。
* 以上内容由AI自动生成，内容仅供参考。对于因使用本网站以上内容产生的相关后果，本网站不承担任何商业和法律责任。