参考文章：An efficient and robust line segment matching approach based on LBD descriptor and pairwise geometric consistency ----Lilian Zhang  , Reinhard Koch

第三部分：Graph matching using spectral technique

介绍线检测和描述之后，本节我们介绍方法来构造两组LineVecs之间的关系图并且在图中建立匹配结果。在此之前，先引入一些预处理，通过排除明显的不匹配来减少图匹配问题的维数。

1.生成候选匹配对

检测参考和查询图像的LineVecs，根据他们的一元几何属性和它们的局部外观相似性，如果他们没有通过测试，被认为是不匹配的。

一元几何属性：一元几何属性在我们的工作中被认为是linevecs方向。值得注意的是，在同一linevec中的线具有相同的方向，所以每个linevec具有独特的方向。乍一看，在图像对中对相应的linevecs方向是模糊的和不可靠的，图像对有任意旋转的变化。但图像对之间往往存在近似全局旋转角是正确的。为了可以减少候选匹配的数量，我们使用这个属性。

在[ 6 ]中，引用和查询图像（ reference and query images）的旋转的近似关系是从点特征对应关系计算的。受此启发，虽然我们没有这样的点对应的信息，我们可以直接计算参考和查询图像的LineVec方向直方图。我们首先计算两图像的LineVecs方向直方图，得到规范化直方图，下标r表示参考图像，q表示查询图像。然后，我们通过角度改变，并且对全局近似旋转角搜索。By taking the angle as index in the histogram for simplicity，估计为：

在实践中，如果偏移的直方图距离较小，透视变换可以通过旋转近似，例如下图：

估计的：0.349 rad；偏移的直方图距离：0.243。此外，如果图像中提取的线的重复性很低，则基于直方图的方法可能会失败，即错误的旋转角度可能被该算法接受。

为了提高这种方法的鲁棒性，对于直方图落入同一bins的直线，它们的长度被累加起来。因此，对应于方向直方图，有一个长度向量，其第i个元素是所有线的累积长度落在方向直方图的第i个bin中。在我们的实验中，当最小偏移直方图距离小于阈值（0.4）时，并且最小偏移长度向量距离小于阈值（1），我们接受估计的全球旋转角。一旦被接受，一对LineVecs就会被匹配，如果（pi/4），是它们的方向之间的夹角，它们被认为是不匹配的。如果两个图像之间没有可接受的旋转角度，那么只测试外观相似性。

 局部外观相似性：用线描述符的距离度量局部外观相似性。

对于LineVec的每个直线，我们从线提取的（octave image）图像中生成一个LBD描述符向量V。当从一对图像中提取的两组LineVec做匹配， a reference LineVec and a test LineVec的所有描述符之间的距离被评估，最小的描述距离用来测量LineVec外观相似s。如果（0.35）（是局部外观不同的容忍度），那么相应的两LineVec不会进一步考虑。

检查LineVecs的一元几何属性和局部外观相似性后，通过这些测试的配对被视为候选匹配。应该选择一组宽松的阈值，否则会有很大的机会错过正确匹配。在我们的实验中，阈值凭经验设为。候选匹配的数量比实际匹配的数量要大，因为人们不能仅仅依赖于上述的验证来决定最终的匹配结果。然而，与直接组合相比，以上检查仍然大大减少了下列图形匹配问题的维数。

 2.建立关系图
对于一组候选匹配，我们建立了一个关系图的节点代表潜在的对应，在连接的权重表示他们成对之间的一致性。

注意：在代码中，left image对应reference image，Right image对应query image，是在每个图中选取了两条线段，标注为。

给定一组k候选匹配，关系图被一个邻接矩阵A表示，其大小为k×k [30]。行为i，列为j的A的元素的值是候选的LineVec匹配的一致性得分和,其中是reference image的LineVecs，是query image的LineVecs。由成对几何属性和候选配对的外观相似性计算一致性得分。

成对几何属性：为了描述两LineVecs的成对几何特征，我们选择两条线，which lead to这两LineVecs之间的最小描述距离并且在原始图像定位端点位置。随后，我们描述的几何属性通过其交叉比率，投影比例，相对角如下图：

计算同理。通过线的方向很方便计算出来。这三个属性对平移、旋转和缩放的变化是不变的。

外观相似性（前面已提到过）：我们利用LBD描述子矢量V来表示线条的局部外观。假设这个描述子对于LineVecs有最小距离在reference and query images，对于LineVecs是。we get two sets of pairwise geometric attributes and local appearances for two candidate matchesandas：

和。

一致性得分（the consistent score）的计算：

其中是几何相似性；是局部外观相似性；是条件

：在中的每个元素不超过1。与[5]相比，在我们的工作中，的定义对线检测的碎片问题有更好的稳定性，因为只要在参考图像和查询图像中的有一对匹配线被很好地提取出来，那么无论另一对如何提取，会非常小。的定义有同样优势。

我们设置

对于所有候选匹配，我们计算它们之间的一致性得分，并获得邻接矩阵A。

Leordeanu [ 31 ]为更好的结果，建议A对角线上的元素为0，并且保持对称性。

3.生成最终匹配结果

匹配的问题现在简化为寻找匹配簇最大化总的一致性得分，这样可以满足映射约束。

我们使用一个指标向量表示这个簇，否则为0。

因此匹配问题被表述为：，其中x受制于映射约束。一般二次规划技术计算量太大，无法解决这个问题。我们采用光谱技术，对x放宽的映射约束和积分约束，使得它的元素可以在采取实际值在[0,1]。

通过Raleigh的比例定理[30]，最大化的是A的主要的特征向量。它仍然是使用映射约束二值化特征向量和获得最优解的一个强大的近似。映射约束应用在这里有片面性约束[ 16,14 ]和一对一的约束。该算法的详细信息如下：

最后的线段匹配可以从linevecs LM的匹配结果直接检索。注意，在LineVec的线位于图像的同一区域，并且具有同一方向，因此，对于每对linevec的匹配，线段匹配有一对就足够检索了。

 线匹配实验

表3总结了该算法的参数设置。

表4中显示了比较结果：整体看来LBD+S&G的效果是比较好的。

LP：Line matching leveraged by point correspondences（逐点匹配）

LS：Wide-baseline image matching using line signatures（基于线特征的宽基线图像匹配）

MSLD： a robust descriptor for line matching

Match precision：匹配的精度