Graph matching using spectral technique
在引入线检测和描述之后，本节我们介绍方法来构造关系图的两组LineVecs之间建立匹配结果图。在此之前，先引入一些预处理，通过排除清晰的非匹配来减少图匹配问题的维数。
1.生成候选匹配对
LineVecs检测参考和查询图像根据他们的一元几何属性和它们的局部外观相似性，如果他们没有通过下面的测试，被认为是不匹配的。
一元几何属性：一元几何属性在我们的工作中被认为是linevecs方向。值得注意的是，在同一linevec线具有相同的方向，所以每个linevec具有独特的方向。乍一看，在图像对中对相应的linevecs方向是模糊的和不可靠的图像对可以任意旋转的变化。虽然这是正确的，但图像对之间往往存在近似的全局旋转角。只要可以减少候选匹配的数量，我们就可以使用这个属性。
在[ 6 ]中，旋转的近似关系是引用和查询图像（ reference and query images. ）是从点特征对应计算的。受此启发，虽然我们没有这样的点对应的信息，我们可以直接计算参考和查询图像的linevec方向直方图。我们首先计算两图像的linevecs两方向直方图，得到归一化直方图
，下标r表示参考图像，q表示查询图像。后，我们改变
通过角度
（0 to 2pi）并且对全局近似旋转角
搜索。在直方图中以角度为指标，估计为：
在实践中，如果透视变换可以通过旋转近似，则移位的直方图距离
较小，例如下图：
估计的：0.349 rad；移位的直方图距离：0.243。此外，如果图像中提取的线的重复性很低，则基于直方图的方法可能会失败，即错误的旋转角度可以被该算法接受。
为了提高这种方法的鲁棒性，对于同一方向直方图中的直线，它们的长度也被累加起来。因此，对应于方向直方图，有一个长度向量，其第i个元素是所有线的累积长度落在方向直方图的第i个bin中。在我们的实验中，我们接受估计的全球旋转角当最小偏移直方图距离小于阈值
时，并且最小偏移长度向量距离小于阈值
。一旦被接受，一对LineVecs就会被匹配，如果
，
是它们的方向之间的夹角，没有进一步检查它们的外观相似性，它们被认为是不匹配的。如果两个图像之间没有可接受的旋转角度，那么只有外观相似性被测试。
局部相似性：用线描述符的距离度量局部外观相似性。对于每行的LineVec，我们从线提取的octave image，生成一个LBD描述符向量V。当从一对图像中提取的两组LineVec做匹配， a reference LineVec and a test LineVec的所有描述符之间的距离被评估，最小的描述距离用来测量LineVec外观相似s。如果
（
是局部外观不同的容忍度），那么相应的两LineVec不会进一步考虑。
完成检查LineVecs的一元几何属性和他们的本地外观相似性后，通过这些测试的配对被视为候选匹配。应该选择一组宽松的阈值，否则会有很大的机会错过正确匹配。在我们的实验中，阈值凭经验设定为
。候选匹配的数量比实际匹配的数量要大，因为人们不能仅仅依赖于上述的验证来决定最终的匹配结果。然而，与直接组合相比，检查仍然大大减少了下列图形匹配问题的维数。
2.建立关系图
对于一组候选匹配，我们建立了一个关系图的节点代表潜在的对应，在链接的权重表示他们成对之间的一致性。
给定一组k候选匹配，关系图被一个邻接矩阵A表示，其大小为k×k。行为i，列为j的A的元素的值是候选的LineVec匹配的一致性评分
和
是reference image的LineVecs，
shiquery image的LineVecs。由候选配对的成对几何属性和外观相似性计算一致性得分。
为了描述两LineVecs的成对几何特征
，我们选择两条线
它导致这两LineVecs之间的最小描述距离和在原始图像定位端点位置。随后，我们描述的几何属性通过其交叉比率
，投影比例
，相对角
如下图：
计算同理。通过线的方向很方便计算出来。这三个属性对平移、旋转和缩放的变化是不变的。
我们利用LBD描述子矢量V来表示线条的局部外观。假设这个描述子对于LineVecs有最小距离
在reference
and query images是
，对于LineVecs
是
。我们得到两套配对几何属性和两个候选匹配和的局部外观：
和
。
一致性评价（the consistent score）
的计算：
是几何相似性；
是局部外观相似性；
是条件
：在中的每个元素不超过1。与[5]相比，在我们的工作中，
的定义对线检测的碎片问题有更好的稳定性，因为只要在参考图像和查询图像中的有一对匹配线被很好地提取出来，那么无论另一对如何提取，可能非常小。
的定义有同样优势。
我们设置
对于所有候选匹配，我们计算它们之间的一致性得分，并获得邻接矩阵A。
Leordeanu [ 31 ]为更好的结果，建议A对角线上的元素为0，并且
保持对称性。
3.生成最终匹配结果
匹配的问题现在简化为寻找匹配簇
最大化总的一致性得分
，这样可以满足映射约束。我们使用一个指标向量
表示这个簇
，否则为0。因此匹配问题被表述为：
，其中x受制于映射约束。一般二次规划技术计算量太大，无法解决这个问题。我们采用光谱技术，放松的映射约束和积分约束x，它的元素可以在采取实际值在[0,1]。
通过Raleigh的比例定理，
会最大化
是A的主要的特征向量。它仍然是进行特征向量使用映射约束和获得的最优解的一个强大的近似
算法：
最后一行的线段匹配可以从linevecs LM的匹配结果直接检索。注意，在LineVec的线位于图像的同一区域，并且具有同一方向，因此，每对linevec的匹配，线段匹配有一对就足够检索了。
原文：http://www.cnblogs.com/Jessica-jie/p/7545554.html