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 线段特征匹配。两幅图像中的一对线段特征，如果该对线段特征在三维空间中共线并且有重合，则称该对线段是一对匹配的线段特征。

本文所使用的符号定义如下：υ={f₁, f₂, …, f_j}表示原始视频帧序列；κ={F_i|i=1, 2, …, n}表示关键帧集合；l_i^k表示从F_k中提取的第i条线段；Ω^k表示从F_k中提取的线段的集合；(l_i^k, l_j^k+1)表示关键帧F_k和F_k+1中的一对匹配线段l_i^k和l_j^k+1; L_{k, k+1}表示关键帧F_k和F_k+1中所有匹配线段的集合。

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

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

2 本文算法

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

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

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

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

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

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

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

$\mathit{\boldsymbol{F}} = {\left( \mathit{\boldsymbol{K}} \right)^{ - {\rm{T}}}}{\left[ \mathit{\boldsymbol{t}} \right]_ \times }\mathit{\boldsymbol{R}}{\mathit{\boldsymbol{K}}^{ - 1}}$

(1)

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

在消除了两关键帧间的旋转差异后，位于两帧中的两条线段l_i^k、l_j^k+1被认为是匹配线段需满足如下两个约束：

1) 方向约束。

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

$\theta _i^k - \theta _j^{k + 1} ＜ {T_\theta }$

其中：θ_i^k、θ_j^k+1是待匹配线段l_i^k和l_j^k+1的倾角，T_θ为设定的角度阈值。

2) 位置约束。

计算图像空间原点距离两条线段l_i^k和l_j^k+1所在直线的距离分别为d_i^k和d_j^k+1，则几何位置约束为：

$\left| {d_i^k - d_j^{k + 1}} \right| ＜ {T_d}$

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

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

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

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

1) 极线约束。由两视图的对极几何^[19]可知，一幅图像中的点定义了另一幅视图中对应点所在的对极线。由本文线段匹配的定义，F_k和F_k+1中一对匹配的线段(l_i^k, l_j^k+1)必须满足如下约束：l_j^k+1必须位于由l_i^k的两个端点所确定的两条对极线内部，或者与对极线相交。根据上面步骤中已经计算出来的基本矩阵F，可确定l_i^k端点在F_k+1中的对极线。对于不满足上述极线约束的匹配线段进行删除。

2) 单应矩阵约束。由文献[19]可知，摄像机在只有旋转运动的情况下，所采集的图像匹配的特征满足单应矩阵模型。本文所研究的是视频帧间线段特征匹配，摄像机在采集相邻关键帧时距离较近，摄像机平移较小，与场景中特征距离摄像机的距离相比该平移可近似忽略，因此关键帧中匹配的线段特征应近似满足同一个单应矩阵模型。本文基于RANSAC框架，首先，从线段特征候选匹配集中随机选择四组匹配线段组成随机样本，根据归一化DLT(Direct Linear Transform)算法求得单应矩阵H; 然后对初始匹配集中的每组匹配线段计算映射之后的欧氏距离d_⊥，如果d_⊥＜T_H，则该组线段匹配为内点，否则为外点；最后，选择获得内点数目最多的H作为真实值，并利用所有内点集重新优化估计H，删除所有外点(不符合模型的匹配线段)。通过单应矩阵模型可进一步过滤线段初始匹配集中的错误匹配。值得注意的是，当摄像机运动明显时，图像中的匹配特征不再符合单应矩阵模型，此时可通过放宽条件的门限值来弱化本条件约束。

3) 点-线相邻性约束。对于关键帧中每条初始匹配的线段，以该线段为中心构建一个矩形邻域，即对于关键帧F_k中的线段l_i^k以及F_k+1中的匹配线段l_j^k+1，各自构建一个矩形邻域Ne(l_i^k)和Ne(l_j^k+1)。对于每一对匹配的SIFT特征点(p_i, p_i^′)，如果p_i位于邻域Ne(l_i^k)内，但p_i^′不位于邻域Ne(l_j^k+1)内，则线段l_i^k和l_j^k+1之间的不匹配度加1。如图 2所示，其中由于Ne(l_i^k)中的两个点特征对应的匹配点不位于Ne(l_j^k+1)中，所以l_i^k和l_j^k+1之间的不匹配度为2。最后，对于F_k中的每一条线段，在F_k+1中所有不匹配度大于某一设定阈值的匹配线段将被从匹配集中删除。

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

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

2.2.1 问题建模

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

定义M={(l_i^k, l_j^k+1)|l_i^k∈Ω^k, l_j^k+1∈Ω^k+1}为通过几何约束处理后得到的候选集，其中(l_i^k, l_j^k+1)为其中的一对匹配线段；定义匹配线段(l_i^k, l_j^k+1)的相似度函数为ε(l_i^k, l_j^k+1); 定义匹配线段选择变量x_{i, j}，如果(l_i^k, l_j^k+1)作为匹配结果被最终选择，则x_{i, j}的值为1，否则为0，即

${x_{i,j}} = \left\{ {\begin{array}{*{20}{l}} {1,} & {\left( {l_i^k,l_j^{k + 1}} \right){\rm{被选择}}}\\ {0,} & {{\rm{其他}}} \end{array}} \right.$

(2)

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

$\mathop {\arg \max }\limits_X \sum\limits_i {\sum\limits_j {\varepsilon (l_i^k,l_j^{k + 1}){x_{i,j}}} } $

(3)

需要满足如下约束条件：

$\sum\limits_i {{x_{i,j}}} \le 1,{\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_j {{x_{i,j}}} \le 1$

(4)

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

相似度函数ε(l_i^k, l_j^k+1)可定义为：

$\varepsilon (l_i^k,l_j^{k + 1}) = \alpha \cdot {N_{sift}}(l_i^k,l_j^{k + 1}) + \beta \cdot \frac{1}{{\left| {d_i^k - d_j^{k + 1}} \right|}}$

(5)

其中：N_sift(l_i^k, l_j^k+1)表示位于两条线段邻域内的匹配的SIFT点的个数，即当一对SIFT匹配点分别位于l_i^k和l_j^k+1的邻域内时，N_sift(l_i^k, l_j^k+1)的值加1；d_i^k-d_j^k+1表示线段l_i^k和l_j^k+1距离图像空间原点的差的绝对值；α和β为大于0的系数，且满足α远大于β。

式(5) 中，α·N_sift(l_i^k, l_j^k+1)表示两条线段邻域内SIFT匹配点的个数越多，两条线段越相似；$\beta \cdot \frac{1}{{\left| {d_i^k - d_j^{k + 1}} \right|}}$表示两条线段位置越近越相似。之所以要求α远大于β，是考虑当线段邻域内存在SIFT匹配点时，SIFT点的个数作为主要因素度量两条线段的相似度；而当线段邻域内没有SIFT匹配点时，才以线段的相对位置度量线段的相似性。

2.2.2 问题求解

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

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

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

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

$M = \left\{ {\begin{array}{*{20}{l}} {(l_1^k,l_1^{k + 1}),(l_1^k,l_3^{k + 1}),(l_1^k,l_4^{k + 1})}\\ {(l_2^k,l_2^{k + 1}),(l_2^k,l_4^{k + 1}),(l_2^k,l_5^{k + 1})}\\ {(l_3^k,l_4^{k + 1}),(l_3^k,l_6^{k + 1})}\\ {(l_4^k,l_5^{k + 1}),(l_4^k,l_7^{k + 1})}\\ {(l_5^k,l_7^{k + 1}),(l_5^k,l_8^{k + 1}),(l_5^k,l_9^{k + 1})} \end{array}} \right.$

基于K-Means算法将M分为两组，分组过程以F_k中线段的空间位置作为聚类依据。从图 3中可以看出，分组使F_k中的线段分为不重叠的两组，而与之对应的F_k+1中线段的分组可能会出现重叠。分组后，分别对两组中的候选集依据式(3) 所示模型进行求解。获得的第一组的匹配结果为(l₁^k, l₃^k+1)、(l₂^k, l₅^k+1)，第二组的匹配结果为(l₃^k, l₆^k+1)、(l₄^k, l₅^k+1)、(l₅^k, l₇^k+1)。合并该匹配结果发现，(l₂^k, l₅^k+1)和(l₄^k, l₅^k+1)使得l₅^k+1有两条与之匹配的线段，需要进一步优化。而余下的(l₁^k, l₃^k+1)、(l₃^k, l₆^k+1)和(l₅^k, l₇^k+1)已经满足“一配一”约束，可以作为最终匹配结果。因此，在第二阶段针对合并后的匹配集，M中剩余的未确定的候选解集中包含(l₂^k, l₂^k+1)、(l₂^k, l₄^k+1)、(l₂^k, l₅^k+1)、(l₄^k, l₅^k+1)。对剩余的候选解再次进行0-1规划，从而获得最终的“一配一”线段匹配结果。

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

3 实验与分析

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

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

3.1 实验过程分析

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

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

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

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

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)图像的线段匹配问题，应用范围比本文算法更大。

4 结语

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

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

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

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