王欣波，王亚伟，厉宝山，张 宁，姜 涛，徐 刚，魏 丽

（1.中国科学院自动化研究所，北京 100190；2.佛山市科自智能系统技术有限公司，广东佛山 528010；3.渤海造船厂集团有限公司，辽宁葫芦岛 125000）

0 引言

特征线匹配是基于图像的三维重建中的关键问题之一，目前已广泛应用于构建摄影测量中的图像查找、基于特征的对象识别、图像拼接、运动检测、古建筑的三维场景恢复[1-3]等领域。现有的特征线匹配方法[4-12]可分为3 类。（1）基于特征线几何属性的匹配方法：该方法主要依赖提取特征线的长度、方向等几何属性进行特征线的匹配。由于缺乏有效的约束条件，此类方法存在算法复杂度高、特征线误匹配率高等问题。（2）基于特征线邻域灰度的匹配方法：该方法主要依赖特征线周围的邻域灰度相似信息，因此适用于纹理丰富的图像，在纹理重复严重的场景中存在误匹配率高的问题。（3）基于特征线几何约束的匹配方法：该方法主要借助多视几何中单应矩阵、极线约束等几何约束，进行误匹配的剔除。因此理论基础强，匹配结果严重依赖于几何模型，因此不适用于视差变化较大、纹理重复的场景。

因此，针对结构复杂、纹理重复严重的场景，受采集环境、采集设备、采集对象等因素影响，提取的特征线具有断线情况严重、局部描述相似的特点，若采用上述特征线匹配方法，特征线匹配结果存在特征线匹配数量少、特征线匹配误匹配率高等问题，进而影响到后续结果。

针对上述问题，本文融合特征线区域信息和局部特征点信息，从灰度、尺度、旋转等多角度，采用多重约束的思想，提出了一种新的特征线匹配方法。输入两幅待匹配图像，该方法首先采用LSD 方法检测图像的特征线，利用SIFT 方法检测图像特征点。为了提高特征线匹配效率，将特征线和特征点信息融合为图像特征集合，并计算每一条特征线矩形支持区域；其次在特征线矩形支持区域内，依据核线约束和特征线两端点及两侧紧邻点间局部特征信息的NCC 度量值，计算特征线的待匹配特征线的支持区域；采用核线约束和灰度约束确定的候选匹配特征线，有效解决了图像特征线的旋转和尺度产生的误匹配问题；最后从匹配特征线间的角度、垂直距离和水平距离3个角度出发，结合灰度相似性度量，在待匹配特征线的支持区域内采用多重约束进一步约束确定同名特征线，从而有效解决了一对多（多对一）的特征线误匹配问题。

1 算法原理

相较于特征点匹配，特征线具有更强的几何约束信息，因此广泛应用于特征匹配过程中。依据特征线的区域信息和局部特征点信息，本文提出的一种基于多重约束的图像特征线匹配算法流程如图1 所示。该算法主要分为5 个过程：（1）输入待匹配的两幅图像，采用LSD算法检测待匹配图像的特征线，利用SIFT 算法检测待匹配图像的几何特征点信息，融合特征线和特征点组合位特征集合；（2）依据特征线周围邻域特征点信息，计算特征线支持区域及每一条特征线周围的邻域特征点集；（3）采用NCC 方法度量特征线间的灰度相似性，获得同名点匹配集合；（4）结合核线约束条件，确定待匹配图像中特征线的支持区域，核线约束有效地保证了特征线匹配的旋转不变性和尺度不变性；（5）在待匹配图像特征线的支持区域内，综合采用特征线间的角度、垂直距离、水平距离进一步约束特征线的匹配。进而解决由于特征线检测方法导致的“一对多”或“多对一”特征线误匹配问题。

图1 特征线匹配流程

2 具体方法

2.1 相关定义

给定两幅待匹配图像{IA，IB}，IA为输入原始图像，IB为待匹配图像；首先利用LSD 对图像IA进行特征线提取后生成特征线集合LA={lA1，lA2，lA3，…，lAm}，采用LSD 对图像IB进行特征线提取后生成特征线集合LB={lB1，lB2，lB3，…，lBn}。利用SIFT对图像IA进行特征点提取后生成特征点集合PA={pA1，pA2，pA3，…，pAw}，采用SIFT 对图像IB进行特征点提取后生成特征点集合PB={pB1，pB2，pB3，…，pBv}。已有方法对两幅图像进行特征检测后的结果为LA={lA2，lA2，lA3，…，lAm}、LB={lB2，lB2，lB3，…，lBn}和PA={pA1，pA2，pA3，…，pAw}、PB={pB1，pB2，pB3，…，pBv}。其中：pAi={(XAi，gAi)，i=1，2，…，w}，pBj={(XBj，gBj)，j=1，2，…，v}；n为图像IA提取的特征线数量；w为图像IA提取的特征点数量；m为图像IB提取的特征线数量；v为图像IB提取的特征点数量；X为图像中的检测到特征点p的几何位置即为（x，y）；g为图像中检测到特征点的灰度信息。结合上述特征点和特征线信息，相关定义如下。

（1）定义1。目标特征线的矩形支持区域RAi：设给定图像IA中任意特征线lAi，采用下式计算特征线lAi的矩形支持区域RAi：

其中L(lAi)为特征线lAi矩形支持区域的长，即特征线长度；2ε为定义的矩形支持区域的宽；D（）表示为欧氏距离。

（2）定义2。矩形支持区域RAi的局部特征点集合RPAi：设给定图像IA中任意特征线lAi，采用下式计算矩形支持区域RAi的局部特征点集合RPAi：

（3）定义3。NCC同名特征点度量：给定图像IA中任意特征线lAi，其矩形支持区域RAi内特征点任一pAi查找同名点pBj的过程为：假设选取的滑动窗口的长和宽分别为2a+1，2b+1，特征点pAi、pBj位于滑动窗口的中心，特征点pAi、pBj的NCC度量值NCC(pAi,pBi)为：

由定义3可知：确定模板下任意两个特征点的NNC度量结果范围为[-1，1]，也就是说在当前模板下，若任意两个特征点对pAi、pBj灰度完全匹配，则NCC值为1；若任意两个特征点对pAi、pBj灰度完全不相关，则NCC值为-1。NCC方法度量的特征间相关性有效地约束了特征点间的灰度变化，进一步保证了特征点间的灰度不变性。

2.2 特征线匹配过程

受到图像采集环境、采集设备等因素影响，待匹配中同一对象间存在尺度、旋转等变换，因此采用LSD提取的特征线存在特征线不完备、提取特征线错误率较高等问题。究其原因，主要问题在两图像中同一对象提取的特征线长度、方向、灰度等信息都不一致，同一特征线两端点间经常存在不一致的情况，最终影响到特征线匹配结果。针对上述问题，本文结合特征线和邻域特征点信息，采用核线约束确定待匹配特征线的支持区域，进而解决了特征线匹配过程中的旋转和尺度问题；利用特征线间的角度距离，垂直距离和水平距离对待匹配的错误特征线进行剔除，进一步删除了误匹配的特征线。结合图1 中的流程，特征线匹配过程如下。

2.2.1 计算待匹配特征线的支持区域

输入图像IA、IB，结合定义（1）～（3）计算：图像IA任一特征线li的特征线矩形支持区域Ri、矩形支持区域Ri的局部特征点集合，并组合为特征集合。依据特征线li的特征线矩形支持区域Ri范围内且位于特征线两侧距离特征线最近的特征点为基础，计算待匹配图像IB中待匹配特征线的支持区域。

待匹配图像IB中待匹配特征线的支持区域具体如图2 所示，在图中，给定图像IA任一特征线lAi，设d1，d2为特征线lAi的两个端点坐标，p1，p2为特征线lAi矩形支持区域RAi的两个局部特征点。利用图像对间的核线约束条件，设图像IA、IB的核线为h1，h2。理想情况下，d1、d2、p1、p2在待匹配图像IB中的匹配信息为，即端点的连线li′应该为图像IA中特征线li的正确匹配特征线。然而受到图像采集环境、采集设备的影响，特征线匹配过程中的确定存在一定的问题。

图2 构建待匹配特征线的支持区域

针对上述问题，本文基于核线约束思想，将待匹配特征线的约束限制在局部区域内，进一步提高特征线匹配的效率，首先构建待匹配图像IB中特征线li的局部支持区域。具体过程为：首先选择图像IA特征线li，图像IB特征线，依据NCC度量图像两对端点（d1、d2）与（、）；其次若（d1、d2）与（、）间满足NCC度量条件，选择li的局部特征点集合RPAi中的特征点p1、p2，选择的局部特征点集合RPAi中的特征点、，并计算（、）的核线h1、h2；然后以、的连线为基础，过、两点做平行于的两条平行直线；最后平行直线且与核线h1、h2相交，构成的四边形区域可定义为图像IB中待匹配特征线li的支持区域RBj。

2.2.2 支持区域内候选匹配特征线的确定

由于待匹配图像间同一对象的特征线间存在端点不一致的情况，为了提高匹配特征线效率，在待匹配支持区域内结合特征线间的角度、距离等信息对特征线进行剔除。具体过程为：在图像IB中确定图像IA特征线li中的支持区域RBj后，将li与图像IB内所有特征线进行计算，若图像IB中任一特征线与支持区域RBj的交集不为空，将该特征线标记为特征线li的候选待匹配特征线。具体如图2 所示，经过观察，图像IA特征线li与支持区域RBj内的候选特征线存在以下几种情况，可罗列为特征线l1、l2、l3、l4、l5、l6、l7。若采用单一的NCC 和距离度量函数，与特征线li匹配的特征线可能存在一对多（多对一）的情况。

为了解决上述问题，需对错误匹配的特征线进行剔除，从图2 中也可以看到：由于特征线检测方法的不同，待匹配特征线可能分为l2、l3两条特征线的情况，而l4仅仅与支持区域RBj局部相交，l4很可能是错误匹配特征线不在待匹配特征线的支持区域内，所以l4不是待匹配的特征线。综合上述情况，可从角度、垂直距离、水平距离三个角度考虑，在支持区域RBj内剔除错误的匹配特征线，进一步提高特征线匹配效率。具体如下。

（1）角度约束：参照图2，匹配特征线间的角度约束可定义为：选择在支持区域RBj待匹配特征线，如果li与的角度θ小于一定的阈值，则认为是正确的候选待匹配特征线；如果li与的角度大于阈值，则认为是错误的候选待匹配特征线，应剔除。由于角度具有旋转不变性，因此角度约束进一步保证了特征线的旋转不变性。本文为中li与角度θ值定义为特征线间斜率的反正切函数，经过反复实验，θ值设置为小于π/8。

（2）垂直约束：参照图3，匹配特征线间的垂直距离约束可定义为：在支持区域RBj内，待匹配特征线lj的两个端点到特征点li的距离为D1、D3，特征点li的两个端点到待匹配特征线lj的距离为D2、D4，依据上述距离，待匹配特征线lj到特征点li的距离若，则待匹配特征线lj为特征点li的候选特征线。由于距离具有尺度不变性，因此垂直距离的约束进一步保证了特征线匹配间的尺度不变性。经过反复实验，λ为不超过3个像素。

图3 垂直距离约束

（3）水平约束：参照图4，水平距离约束可定义为：在支持区域RBj内，待匹配特征线lj的中点与li中点间的距离可表示为Dh。若，则待匹配特征线lj为特征点li的候选特征线。水平约束的使用有一定的限制：待匹配图像对间的平移向量不应太大。

图4 水平距离约束

2.2.3 待匹配特征线间的灰度相似性约束

上述过程从角度、水平、垂直距离约束出发，保证了特征线匹配具有旋转、尺度不变性，为了提高特征线匹配效率，结合特征线间的灰度相似性进行约束。具体过程为：输入图像IA特征线li和li的支持区域RBj中的候选特征线，首先将特征线li和候选匹配特征线lj离散化长度一致的离散点，设特征线li离散的特征点个数为M、特征线lj离散的特征点个数为N；然后以li、lj为中心轴，在li、lj的矩形支持区域内选择2r条平行线，分别标记为Gr(li)、Gr(lj)，设矩形支持区域内第i条平行线上第j个像素点的灰度值为。考虑到特征线矩形支持区域内平行线的远近对特征线匹配结果的影响，本文采用权重因子ζ对支持区域内平行线的权重进行设置，具体思想为：权重因子ζ在平行支持域内，从特征线出发，依照平行线的两侧递减，因此权重因子定义为如下分段函数：

则Gr(li)、Gr(lj)内平行线上点的灰度值矩阵为：

灰度值矩阵的均值为：

利用NCC度量两个平行支持域的灰度相似性：

采用NCC度量特征线li和候选匹配特征线lj后，进一步保证了特征线li和候选匹配特征线lj具有灰度不变性。且特征线li和候选匹配特征线lj灰度遵循线性变化约束，依照线性约束条件g(A)=αg(B)+β，特征线li和候选匹配特征线的灰度变化关系满足ljG(li)=αG(lj)+β，α、β值本文设置为0.5 和0.5。只要特征线li和候选匹配特征线lj的灰度变化满足上式，则li和lj为正确的特征线匹配；否则，li和lj为错误的匹配，该剔除。

3 实验分析

为了验证本文提出的特征线匹配算法的效率，采用不同场景下的图像对进行验证。实验环境为：采用Windows 10 作为操作系统，采用英特尔Core i7-8750H @ 2.20GHz 为处理器，内存为8G；采用MatlabR2016a 为编程语言，Opencv3.4.5 计算机视觉库，以标准公开数据集中包含旋转变换、尺度变换、光照变化的3对图像对为实验数据，进行特征线匹配实验。

为了减少实验数据的误差，与文献[13]相同，本文采用SIFT进行特征点提取，采用LSD方法进行特征线提取，特征线匹配结果与文献[13]和文献[14]中的算法进行比较。3 组图像的特征点检测结果如表1 所示。具体检测结果如图5 所示，其中第一组和第二组的特征线匹配结果中特征线匹配总数量、正确匹配对数量结果参照文献[13]中数据，第三组图的特征线匹配结果来源于文献[14]中的数据。

表1 数据集信息

图5 对比实验结果

4 结束语

在场景复杂、重复纹理、光照变换的复杂场景中，现有的特征线匹配方法存在匹配数量少、误匹配率高等问题，进而直接影响了特征线匹配结果。针对上述问题，本文融合特征线信和和局部特征点信息，提出了一种基于多重约束的特征线匹配方法，该方法从旋转、尺度、灰度3 个角度对特征线匹配结果进行约束，进而有效解决了复杂场景中误匹配率高的问题。经过实验验证，结果表明在图像差异较大的情况下，特征线匹配数量、特征线匹配效率均优于其他算法，从而进一步验证了本文算法的有效性。