基于几何约束及0-1规划的视频帧间线段特征匹配算法

李海丰，胡遵河，范龙飞，姜子政，陈新伟

(1.中国民航大学 计算机科学与技术学院，天津 300300； 2.福建省信息处理与智能控制重点实验室(闽江学院)，福州 350121)

(*通信作者电子邮箱chenxw_mju@126.com)

基于几何约束及0-1规划的视频帧间线段特征匹配算法

李海丰1,2，胡遵河1，范龙飞1，姜子政1，陈新伟2*

(1.中国民航大学 计算机科学与技术学院，天津 300300； 2.福建省信息处理与智能控制重点实验室(闽江学院)，福州 350121)

(*通信作者电子邮箱chenxw_mju@126.com)

针对线段因遮挡、断裂以及端点提取不准确等原因造成的线段特征匹配困难问题，特别是现有匹配算法在匹配过程中出现“多配多”时直接采取“最相似匹配”而导致丢失大量真实匹配的问题，提出了一种基于多重几何约束及0-1规划的线段特征匹配算法。首先，基于校正后视频帧间线段特征的空间相邻性计算线段匹配的初始候选集；然后，基于极线约束、单应矩阵模型约束以及点-线相邻性约束等多重几何约束，对候选集进行筛选从而剔除部分错误匹配；其次，将线段匹配问题建模为一个大规模0-1规划问题；最后，设计了一种基于分组策略的两阶段求解算法对该问题进行求解，从而实现线段特征的“一配一”精确匹配。实验结果表明，该算法与LS(Line Sigature)、LJL(Line-Junction-Line)方法相比，匹配正确率接近，但匹配线段数量分别提高了60%和11%。所提算法可以实现视频帧间的线段特征匹配，为基于线特征的视觉SLAM(Simultaneously Localization and Mapping)奠定基础。

线段匹配; 几何约束; 0-1规划；特征匹配；视觉SLAM

0 引言

特征匹配是计算机视觉领域研究的核心问题之一。点特征的匹配方法已经比较成熟可靠，如尺度不变特征转换(Scale-Invariant Feature Transform, SIFT)[1]、加速鲁棒特征(Speeded Up Robust Features, SURF)[2]等。与点特征相比，在同样的噪声条件下，图像中的线特征受噪声影响更小，且对光照条件和阴影不敏感。因此，基于线特征的视觉SLAM(Simultaneously Localization and Mapping)日益兴起[3]。然而，线段端点位置的不准确、遮挡、断裂等因素使线段特征的匹配极具挑战性。

近年来，许多学者致力于解决线段特征的匹配问题。可将线段匹配算法分为两大类：个体匹配和组匹配。在个体匹配算法中，线段邻域的梯度信息[4-5]和颜色信息[6-7]常被用来作为线段的特征描述。然而，基于颜色或梯度信息的线段匹配方法受光照影响比较大，且不适用于场景中线特征的颜色信息很相似的情形。另一类个体匹配算法利用了多种几何约束信息，如王伟玺等[8]利用不同视图间线段端点的对极几何约束，借助点对应的相关性作为衡量线段间相似性的标准来进行线段特征匹配；然而，该方法的准确性不高。娄安颖等[9]利用单应矩阵约束实现了遥感图像中的线段特征匹配。梁艳等[10]和李俊瑶等[11]分别结合极线约束和单应矩阵约束进行线段特征匹配。Fan等[12]提出了基于点对应的线特征匹配算法，将不同视图间线段邻域内的点对应作为衡量线段之间相似性的度量，是一种具有较高准确性和鲁棒性的线段匹配方法。然而，该方法存在以下问题：当场景中缺少点特征时，很多真实存在的线对应无法被找到；点特征的匹配错误可能会导致相应的线段匹配错误。线段的组匹配方法[13-15]将图像中的多条线段看成一个整体，线段间的相对位置关系可以为线段的匹配提供一定的几何约束。其中，文献[14]提出的LS(Line Signature)方法目前已被广泛应用，而文献[15]中的LJL(Line-Junction-Line)算法作为一种新的线段匹配算法，已在实验中取得了较好效果。然而，该类方法具有较高的计算复杂度，且容易受到线段端点位置不准确的影响。

线段因遮挡、断裂以及端点提取不准确等造成线段特征匹配的“多配多”匹配问题。为了获得线段的“一配一”匹配，现有方法绝大多数在匹配阶段采用相似度最大原则，即匹配时取相似度最大的一对线段作为匹配结果。然而，对于线段相似度接近的场景，上述方法容易发生错配，在初始匹配阶段就采用相似度最大原则也容易丢失大量真实匹配；而且相似度最大原则实质上是一种局部最优匹配，并未考虑线段匹配的全局最优。特征编组[16]及图优化[17]等方法被一些学者用于了线段的全局匹配并取得了一定的效果。

本文针对视频帧间线段特征匹配问题，设计了一种基于多重几何约束及0-1规划的线段匹配算法。视频帧间特征匹配实质上是一种短基线特征匹配问题。本文算法结合了多种几何约束，同时将匹配的点特征及线段间距离作为一种线段相似度对匹配结果进行筛选，最后构建了0-1规划模型对“多配多”匹配问题进行建模和求解，实现了优化的“一配一”线段特征匹配。

1 问题描述

三维空间中的同一线段，在摄像机以不同视角采集的两幅图像中所呈现的投影线段，称为一组匹配线段。本文所要解决的线段特征匹配定义如下：

定义1 线段特征匹配。两幅图像中的一对线段特征，如果该对线段特征在三维空间中共线并且有重合，则称该对线段是一对匹配的线段特征。

基于上述符号定义，本文所研究问题的定义如下：

定义2 给定视频帧序列υ，提取关键帧集合κ，对于任意相邻的关键帧Fk,Fk+1∈κ，提取线段特征并进行一一对应的匹配，最终获得Lk,k+1。

2 本文算法

本文设计了基于多重几何约束的视频帧间线段特征匹配算法。如图1所示，首先，对视频中的关键帧进行提取，以达到避免病态对极几何和消除信息冗余的目的；然后，利用SIFT算法[1]及LSD(Line Segment Detector)算法[18]分别提取关键帧中的点特征和线段特征，并对线段特征进行删除、合并等预处理；最后，基于空间相邻性、单应矩阵模型以及点-线相邻性等几何约束对线段特征进行匹配、筛选，并最终基于0-1规划实现线段的优化匹配。

图1 匹配算法流程Fig. 1 Flowchart of the matching algorithm

2.1 基于多重几何约束的线段初始匹配

在提取了线段特征之后，本文基于多重几何约束进行线段的初始匹配及筛选。首先基于空间相邻性获取初始的线段匹配候选集；然后分别基于极线约束、单应矩阵模型约束以及点-线相邻性约束等几何约束对初始匹配集进行筛选，删除部分错误匹配。

2.1.1 基于空间相邻性求解线段特征初始匹配集

摄像机在采集相邻关键帧时平移量较小，而如果在没有旋转变化的情况下，较小的摄像机平移所产生的特征在图像中的变化也较小。因此，本文首先基于基本矩阵估计出相邻关键帧间摄像机的旋转变换；然后通过对后一关键帧施加该旋转变换的逆变换而使其与前一关键帧之间只有平移变化；最后，比较变换后两关键帧间的线段特征位置以确定线段的初始匹配结果。

基本矩阵的估计方法为：在随机抽样一致(RANdom Sample Consensus, RANSAC)框架下，利用SIFT点特征，通过最小化重投影误差[19]完成。

然后，通过式(1)对基本矩阵F进行分解，从而获得摄像机在两帧之间的旋转变换R。

F=(K)-T[t]×RK-1

(1)

其中:K为摄像机的内参数矩阵，可通过标定获得；R和t分别为两帧之间摄像机的旋转矩阵和平移向量；符号[·]×为叉乘运算的斜对称矩阵表示。

1)方向约束。

根据线段端点的坐标，求出线段的倾角。匹配线段的方向约束为：

2)位置约束。

其中，Td>0为一设定阈值。

满足上述1)、2)两个约束条件的所有线段构成初始匹配集。初始匹配集中可能会包含“一配多”或“多配多”的关系，即前一关键帧中的一条线段在后一关键帧中可能存在多条与之匹配的线段，反之亦然。此步为线段的初始匹配，目的是找到尽可能多的潜在的匹配线段，本文将在下面的步骤中利用多重几何约束对此处的初始匹配结果进行过滤和优化。

2.1.2 基于多重几何约束的候选解筛选

上述初始匹配集中存在错误匹配、“一配多”“多配多”等问题，为了减少匹配候选解的个数、降低后续优化中的变量维度，对初始匹配集进行如下筛选。

2)单应矩阵约束。由文献[19]可知，摄像机在只有旋转运动的情况下，所采集的图像匹配的特征满足单应矩阵模型。本文所研究的是视频帧间线段特征匹配，摄像机在采集相邻关键帧时距离较近，摄像机平移较小，与场景中特征距离摄像机的距离相比该平移可近似忽略，因此关键帧中匹配的线段特征应近似满足同一个单应矩阵模型。本文基于RANSAC框架，首先，从线段特征候选匹配集中随机选择四组匹配线段组成随机样本，根据归一化DLT(Direct Linear Transform)算法求得单应矩阵H;然后对初始匹配集中的每组匹配线段计算映射之后的欧氏距离d⊥，如果d⊥

2.2 基于0-1规划的线段匹配算法

根据上面的步骤可以从相邻关键帧中找到包含所有可能的线段匹配的候选集。在该候选集中，任意一条线段可能存在多个与之匹配的线段，即存在“多配多”的匹配关系。而在实际应用中，一条线段在另一帧图像中最多只能与一条线段匹配。因此，需要从候选集中的“多配多”匹配关系中寻找最终的“一配一”的匹配结果。

图2 点-线相邻性示意图Fig. 2 Illustration of point-line adjacency

2.2.1 问题建模

对于候选集中的每对匹配线段，可以通过计算相似度来度量该对线段的匹配程度。相似度越大，表明该对线段的匹配性越好，越有可能是真实的匹配。这样，上述线段特征匹配问题可以被描述为：从候选解集中选取一些合适的匹配结果，在满足上述“一配一”匹配约束的前提下，使匹配结果的相似度之和最大。

(2)

上述线段全局匹配问题可被定义为如下0-1规划问题：

(3)

需要满足如下约束条件：

(4)

式(4)中的约束条件保证了一条线段在另一幅图像中最多有一条线段与之匹配。

(5)

2.2.2 问题求解

由于视频帧中的线段较多，导致式(3)中优化变量非常多，直接求解式(3)中的大规模0-1规划问题将非常耗时，甚至无法求出结果。在上面的候选集确定以及基于几何约束的匹配线段筛选过程中，已经去除了大量不可能的匹配，即已令大量的xi, j=0，从而使待优化变量的数量大大减少。但通过实验我们发现剩余的待优化变量数量仍然较大。为了降低运算量，本文提出了基于分组策略的两阶段求解算法。

首先，基于K-Means算法对候选集Μ中Fk图像帧中的线段进行聚类分组，使其分为m个距离相近的线段子集。具体做法为：首先从属于Μ的Fk中的线段任意选择m个对象作为初始聚类中心；而对于所剩下其他线段，则根据它们与这些聚类中心的相似度(此处为线段中点的距离)，分别将它们分配给与其最相似的聚类；然后再计算每个所获新聚类中所有线段中点的几何中心作为该聚类的聚类中心；不断重复这一过程直到标准测度函数开始收敛为止。本文以线段距离聚类中心的均方差作为标准测度函数。

根据上述聚类，将候选解集Μ分解为m个子集。然后，分两个阶段对线段全局匹配问题进行求解。在第一阶段，分别对每个子集根据式(3)所示模型对其进行求解。由于每个子集的优化变量数量较少，所以可采用分枝定界算法求解。每个子集求解后，对于子集内部的线段会得到“一配一”的匹配关系。在第二阶段，将所有子集求解的结果合并，保留仍然具有“一配一”匹配关系的线段作为匹配的最终结果。对于剩下的那部分因子集求解结果合并而出现的“一配多”的线段，重新利用式(3)中模型对其求解。此时，由于剩余线段较少，所以问题规模大幅降低。

下面举例说明上述求解过程。如图3所示，线段的候选匹配集为：

图3 基于分组策略的两阶段线段匹配求解示例Fig. 3 Example of two-stage line matching based on grouping strategy

本文之所以能按照上述方式对候选匹配集进行聚类分组，是因为根据本文候选集的确定方法，只有位置相邻的线段才可能具有相同的候选匹配。因此，上述聚类分组方法具有合理性。由于本文采用了基于分组策略的两阶段线段匹配求解算法，分组及合并的过程可能导致无法获得全局最优解。然而，对于线段匹配问题，具有较低计算代价的近似最优解是可以接受的。后续实验部分将对匹配算法的性能进行验证。

3 实验与分析

利用C++语言及计算机视觉库OpenCV实现了本文算法。硬件为戴尔计算机，i7- 3处理器，4 GB内存，500 GB硬盘，摄像机为佳能600D。实验中，所需参数的取值分别为：α=100，β=1，Tθ=2°，Td=40，TH=20。

本章首先通过示例实验，分析本文算法每一步输出的运行过程及中间结果，以说明本文算法中几何约束及优化过程的必要性和有效性；然后，对实验结果进行分析，给出本文算法针对不同场景中图像的实验结果，并与其他算法进行对比。

3.1 实验过程分析

图4(a)为两幅示例图像(视图1和视图2)，图4(b)为从图4(a)中提取出的经过预处理后的线段，线段数量分别为53、49，所有线段均已编号。

图4 示例图像及其线段提取结果Fig. 4 Example images and their line segment extraction results

首先，基于线段特征的空间相邻性计算线段匹配的初始候选集，得到如图5(a)所示的匹配矩阵：第1列为图4(a)视图1图像中线段的编号，第1行为图4(a)视图2图像中的线段编号，“1”表示对应位置的两线段匹配，“0”表示不匹配。此时，可以看到一行(或一列)中存在多个值等于1的情况，说明存在大量的“多对多”匹配关系，此例中共有270个变量需要优化。

然后，基于极线约束、单应矩阵模型约束以及点-线相邻性约束等多重几何约束，对图5(a)所示候选解集进行筛选并剔除部分错误匹配，更新后的匹配矩阵如图5(b)所示。可以看出，矩阵中值为“1”的元素大大减少，说明大量的错误匹配已被剔除；但仍存在一行(或一列)中存在多个值等于1的情况，说明仍存在“多配多”匹配关系。

图5 初始候选集与更新后的匹配矩阵示意图Fig. 5 Schematic diagram of matching matrices for initial and updated candidate set

最后，利用2.2节的匹配算法进行匹配。此时，尽管该优化问题中待优化变量的数量为53×49=2 646个，但从上述匹配矩阵可以看出，大量的元素已被置为0，经过多几何约束之后，真正需要优化的变量仅为106个，大大降低了问题求解的复杂度。利用基于0-1规划的线段匹配算法所获得线段的“一配一”匹配结果如图6所示。

图6 示例图像中线段匹配结果Fig. 6 Line segment matching results for example images

3.2 实验结果及分析

分别采用公共数据集HRBB[20]和笔者采集的数据集进行实验。实验数据共包含10对图像作为代表性的视频关键帧：HRBB中室内走廊场景4对，自采集室内办公场景1对，室外校园场景5对。

线段匹配部分图像的结果如图7所示，图中同一行的两幅图像为一对，其中具有相同标号的线段为一组匹配的线段。

为了进一步说明本文算法的性能，将本文算法与目前被广泛应用的LS方法[14]和最新的LJL方法[15]进行对比，对比实验的统计结果如表1所示。由表1可知，本文算法和LS方法、LJL方法的平均匹配准确率接近(95.3%与97.4%、98.2%),平均运行时间相差不大(14.9 s与13.5 s、13.6 s)；但本文算法所提取的匹配线段数量分别高出LS和LJL方法60%和11%，如图8所示。本文算法之所以能够找到更多的匹配线段，原因在于：本文算法并未采用其他绝大多数匹配方法为了获得“一配一”结果所采用的“最大相似性”以及“左右一致性”匹配原则，明显降低了在匹配中间环节中丢失真实匹配的数量。需指出，虽然在上述实验中LS和LJL方法的综合性能不及本文算法，但上述两个方法可用于长基线(long base-line)图像的线段匹配问题，应用范围比本文算法更大。

图7 线段匹配部分结果Fig. 7 Partial result of line segment matching

图8 线段匹配数量对比Fig. 8 Amount comparison of line segment correspondences

4 结语

本文设计了一种基于多重几何约束及0-1规划的视频帧间线段特征匹配算法。首先，针对视频帧间特征在图像空间中平移较小的特点，通过除摄像机旋转变换差异并结合待匹配特征的空间相邻性，获得了线段匹配的初始候选匹配集；然后，基于极线约束、单应矩阵模型约束以及点-线相邻性约束等对候选解集进行筛选从而剔除了部分错误匹配；最后，将线段匹配问题建模为一个大规模0-1规划问题，并设计了一种基于分组策略的两阶段求解算法对该问题进行求解，从而实现了线段特征的“一配一”精确匹配。该算法可以解决线段因遮挡、断裂以及端点提取不准确等造成的线段特征匹配困难，特别是现有匹配算法在匹配过程中出现“多配多”时直接采取“最相似匹配”而导致丢失大量真实匹配等问题。

表1 实验对比结果Tab. 1 Comparison of experimental results

本文所述算法实际上是一种面向短基线(short base-line)图像序列的线段匹配方法。当采集两幅图像时的摄像机之间基线较长时，特征在图像空间中的位置变化较大，不能直接依据本文所提的空间相邻性来确定初始候选匹配集。可考虑首先基于点特征估计基本矩阵，然后分解该基本矩阵获得摄像机的平移向量和旋转矩阵，据此计算旋转变换矩阵以使两幅图像具有相同的视角；此时，再利用空间相邻性可获得线段匹配的候选解集。

此外，长基线的图像对不再满足本文所述的单应矩阵约束。但是对于室内或者城市环境等人造场景，由于场景中存在大量的平面，而每个平面内的线段特征符合由该平面诱导的单应矩阵模型约束。在此类场景中，可考虑基于RANSAC方法迭代估计所有平面的单应矩阵模型，分别寻找每个平面内的匹配线段。这样，不仅可以剔除不符合任意单应矩阵模型的错误匹配，同时可以根据线段所处平面对其进行分组。

如果将本文算法用于视觉SLAM中，虽然特征匹配时间较长，但表1中数据表明，完全可以通过在线段提取环节挑选出误差较小、数量相对较少的线段，从而明显降低线段匹配所需时间。

References)

[1] LOWE D G. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[2] BAY H, TUYTELAARS T, VAN GOOL L. SURF: Speeded Up Robust Features [C]// ECCV 2006: Proceedings of the 2006 9th Equopean Conference on Computer Vision, LNCS 3951. Berlin: Springer-Verlag, 2006: 404-417.

[3] 武涛,孙凤池,苑晶,等.一种基于线段特征的室内环境主动SLAM方法[J].机器人,2009,31(2):166-170,178. (WU T, SUN F C, YUAN J, et al. An active SLAM approach based on line segment feature in indoor environment[J]. Robot, 2009, 31(2): 166-170, 178.)

[4] WANG Z, WU F, HU Z. MSLD: a robust descriptor for line matching [J]. Pattern Recognition, 2009, 42(5): 941-953.

[5] ZHANG L, KOCH R. An efficient and robust line segment matching approach based on LBD descriptor and pairwise genometric consistency [J]. Journal of Visual Communication and Image Representation, 2013, 24(7): 794-850.

[6] WANG Z-H, ZHI S-S, LIU H-M. MSHS: the mean-standard deviation curve matching algorithm in HSV space [C]// ICMLC 2012: Proceedings of the 2012 International Conference on Machine Learning and Cybernetics. Piscataway, NJ: IEEE, 2012: 1064-1069

[7] CUI X, KAN J, LI W. A new line matching method based on color invariantsin the RGB orthogonal color space [J]. Journal of Computational Information Systems, 2015, 11(9): 3265-3273.

[8] 王伟玺，安菲佳，王竞雪.多重约束条件下的影像直线匹配算法研究[J].测绘科学，2014，39(11):15-19. (WANG W X， AN F J， WANG J X. Line matching algorithm for imagery under multiple constraint conditions [J]. Science of Surveying and Mapping, 2014, 39(11): 15-19.).

[9] 娄安颖，宋伟东，刘薇.基于单应矩阵的直线匹配[J].遥感信息，2011(3):9-13. (LOU A Y, SONG W D, LIU W. Matching straight lines on the basic of homography[J]. Remote Sensing Information, 2011(2): 9-13.)

[10] 梁艳，盛业华，张卡，等.利用局部仿射不变及核线约束的近景影像直线特征匹配[J]. 武汉大学学报(信息科学版)，2014，39(2):299-233. (LIANG Y, SHENG Y H, ZHANG K, et al. Linear feature matching method based on local affine invariant and epiolar constraint close-range images [J]. Geomatics and Information Science of Wuhan University，2014, 39(2): 299-233.)

[11] 李俊瑶,顾宏斌,孙瑾,等.基于多重约束条件的线特征多级匹配方法[J].计算机科学,2014,41(S2): 83-87. (LI J Y, GU H B, SUN J, et al. Multi-lever line matching method based on multiple constraints [J]. Computer Science, 2014, 41(S2): 83-87.)

[12] FAN B, WU F, HU Z. Robust line matching through line-point invariants [J]. Pattern Recognition, 2012, 45(2): 794-805.

[13] 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.

[14] LU W, ULRICH N,SUYA Y. Wide-baseline image matching using line signatures [C]// ICCV 2009: Proceedings of the 2009 IEEE International Conference on Computer Vision. Washington, DC: IEEE Computer Society, 2009:1311-1318.

[15] LI K, YAO J, LU X H. Hierarchical line matching based on Line-Junction-Line structure descriptor and local homography estimation [J]. Neurcomputing, 2016, 184(C): 207-220.

[16] 文贡坚.一种基于特征编组的直线立体匹配全局算法[J].软件学报,2006,16(12):2471-2484. (WEN G J. A global algorithm for straight line stereo matching based on feature grouping [J]. Journal of Software, 2006, 16(12): 2471-2484.)

[17] 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.

[18] VON G, 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.

[19] HARTLEY R, ZISSERMAN A. Multiple View Geometry in Computer Vision [M]. 2nd ed. New York: Cambridge University Press, 2004: 1-206.

[20] LU Y, SONG D. Visual navigation using heterogeneous landmarks and unsupervised geometric constraints [J]. IEEE Transactions on Robotics, 2015, 31(3): 1-14.

This work is partially supported by the National Natural Science Foundation of China (61305107), the Tianjin Key Research Program of Application Foundation and Advanced Technology (14JCZDJC32500), the Open Fund Project of Fujian Provincial Key Laboratory of Information Processing and Intelligent Control (MJUKF201732), the Fundamental Research Funds for the Central Universities (3122016B006).

LIHaifeng, born in 1984, Ph. D., lecturer. His research interests include computer vision, robot navigation.

HUZunhe, born in 1989, M. S. candidate. His research interests include visual navigation.

FANLongfei, born in 1989, M. S., assistant experimentalist. His research interests include pattern recognition.

JIANGZizheng, born in 1990, M. S. candidate. His research interests include computer vision.

CHENXinwei, born in 1984, Ph. D., lecturer. His research interests include machine learning.

Linesegmentfeaturematchingalgorithmacrossvideoframesbasedongeometricconstraintsand0-1programming

LI Haifeng1,2, HU Zunhe1, FAN Longfei1, JIANG Zizheng1, CHEN Xinwei2*

(1.CollegeofComputerScienceandTechnology,CivilAviationUniversityofChina,Tianjin300300,China；2.FujianProvincialKeyLaboratoryofInformationProcessingandIntelligentControl(MinjiangUniversity),FuzhouFujian350121,China)

To deal with the problems in line segment matching due to occlusion, fragmentation and inaccurate extraction of line segment endpoints, especially when the criteria of “most similar matching” was taken in “multiple-to-multiple” matching which may lead to fateful true correspondences lost, a line segment matching algorithm based on geometric constraints and 0-1 programming was proposed. Firstly, a candidate matching set was initially computed based on the spatial adjacency after correcting the vedio frames. Secondly, the multiple geometric constraints, such as epipolar constraint, homography matrix and point-to-line adjacency, were employed to remove the false positive correspondences. Then, the matching problem was modeled into a large scale 0-1 programming. Finally, a two-stage method based on grouping strategy was designed to solve this problem, so as to realize the “one to one” exact matching of line segment feature. The experimental results show that, compared with LS (Line Sigature) and LJL (Line-Junction-Line) methods, the propsed method has a similar performance in correct matching ratio but a larger matching amount over 60% and 11%, respectively. The proposed method can fulfill the line segment matching across vedio frames, which lays the foundation for line-based visual SLAM (Simultaneously Localization and Mapping).

line segment matching; geometric constraint; 0-1 programming; feature matching; visual SLAM (Simultaneously Localization and Mapping)

TP242

A

2017- 01- 16;

2017- 03- 03。

国家自然科学基金资助项目(61305107)；天津市应用基础与前沿技术研究计划重点项目(14JCZDJC32500)；福建省信息处理与智能控制重点实验室开放课题项目(MJUKF201732)；中央高校基本科研业务费资助项目(3122016B006)。

李海丰(1984—)，男，内蒙古通辽人，讲师，博士，CCF会员，主要研究方向：计算机视觉、机器人导航； 胡遵河(1989—)，男，山东菏泽人，硕士研究生，主要研究方向：视觉导航； 范龙飞(1989—)，男，河北邢台人，助理实验师，硕士，主要研究方向：模式识别； 姜子政(1990—)，男，辽宁本溪人，硕士研究生，主要研究方向：计算机视觉； 陈新伟(1984—)，男，福建龙岩人，讲师，博士，主要研究方向：机器学习。

1001- 9081(2017)08- 2292- 06

10.11772/j.issn.1001- 9081.2017.08.2292