直线匹配-LSD算法

转自https://www.cnblogs.com/Jessica-jie/p/7523364.html

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

第二部分：Line detection and description

1.尺度空间中提取线段

为了克服在线检测碎片问题和提高大尺度变化的性能，我们的检测框架采用由对原始图像进行高斯下采样（ with a set of 尺度因子and 高斯模糊）的尺度空间金字塔组成（N层图像）。我们首先用Edline算法每层的尺度空间产生一组线。每条直线都有一个方向，它是由从直线左侧到右侧的大部分边缘像素点的梯度构成的。然后通过在尺度空间中找到对应的直线来组织它们。在尺度空间中所有的线，他们被分配一个唯一的ID，如果在图像中他们相关相同的事件，将其存储在一个称为LineVecs的向量中（即图像的同一区域具有相同的方向）。线检测方法不同于Wang et al.[5] ,通过重新组织从尺度空间提取的所有的线段形成LineVecs，从而降低了图匹配问题的维数。最终提取的结果是一组LineVecs如下图：

如图1所示，每个Linevec可能包括尺度空间的多条线。为描述一个LineVec局部外观，对于其中的每条线，我们会在被提取的线段的每层图中产生一种线描述符。

2.条带（Band）来表示线的支持域

在octave image给出了线段，描述符将从线段支持域（LSR）计算。该支持区域被划分为一组条带{B1；B2；...；Bm}，每个条带都是LSR的子区域并且他们之间的平行的，条代数m的和每个条带的宽度w，条带的长度等于线段的长度，如下图当m =5 ，w=3的LSR例子。

类似于 MSLD[11],引入两个方向构成a local 2D coordinate frame（局部二维坐标系），用于区分具有相反梯度方向的平行线并使描述符旋转不变。根据线的方向为，正交方向（垂直方向）被定义为顺时针垂直的方向。该线的中点被选为这个局部坐标系的原点。LSR中的每个像素的梯度投影到这个局部框架，其中的：image frame中的像素梯度，：local frame中的像素梯度。

对于SIFT[23] and MSLD，两个高斯函数应用在每一行沿着的方向。首先，全局权重系数是在LSR的第i行，其中是第i行到LSR中心行的距离，第二，考虑一个条带Bj，以及他在相邻的条带Bj-1，Bj+1 ,局部权重系数在Bj第k行，其中第k行到Bj中心行的距离，全球的高斯窗的目的是给予在LSR中沿方向远离线的微小变化梯度很小的关注度（敏感性）。局部高斯窗的目的是减少边界效应，它避免了像素从一个条带移动到下一个的描述符突然改变。

此方法描述子区域的优点：首先，它对方向的小的位置变化更有鲁棒性，因为在这种情况下，带内图像的大部分内容保持不变，只有带边界略有变化。注意，这个特性很重要，因为一般来说，由于线路端点不稳定，线的位置精度在方向中要比方向低。第二，它的计算效率更高，因为每个条带之间在方向没有重叠，高斯权重直接应用于每一行，而不是每个像素。

3.构造条带描述符

（the Line Band Descriptor） LBD:

每条条带的描述子BDj：通过其最近的两相邻行的条带Bj-1 ; Bj+1来计算。特别是，对于在顶部和底部的条带带B1和Bm，在计算B1和Bm的描述子时行在LSR之外不会被考虑在内。（所以下面n的取值会把j=1||m单独出来）

BDj的计算（其实就是描述的上下左右四个方向）：

k：表示在条带Bj的第k行，我们累积的像素的梯度在这行；：高斯权重。

条带描述矩阵the band description matrix (BDM)：

BDj由BDMj矩阵的均值向量Mj and标准方差 Sj 得到：

LBD的均值部分和标准方差部分由于其大小不同，分别进行规范化处理。此外，为减少非线性光照变化的影响，对LBD每个维度的进行抑制，使它小于一个阈值（经验：0.4的是一个很好的值）。最后，我们重新规范约束向量得到单元的LBD。

二.描述符性能评价

在检测我们提出的图像匹配算法之前，我们线分析一下LSR参数的影响，例如条带的数量m和条带的宽度w，评价LBD的性能与MSLD描述子做比较。

Mikolajczyk and Schmid [33]建立一个基准，评价局部描述符的性能。我们使用这个框架来比较线描述符的性能。实验数据集包括八组图像：光照变化、面内旋转、jpeg压缩、图像模糊、图像遮挡、低纹理场景中视点变化和纹理场景，以及尺度变化。

针对这一部分所描述的描述符的匹配性能，我们选择了最近邻匹配准则，根据描述符的距离对线进行匹配，避免了由于不同描述符偏爱不同阈值而造成距离阈值的偏差。这种匹配准则的另一个优点是，召回率（正确匹配的数量除以地面对应的数目）和匹配精度（正确匹配的数量除以总数量的匹配）是唯一的决定正确匹配的数量由于不同的描述符的分母是相等的。

描述子维数

下图显示了所有的图像正确匹配的数量是由这两个参数（m和w）影响的。It is clear that LBD and MSLD share similar rules: the performance increases fast at the beginning with the increment of m or w, then reaches the best performance when m=9 and w is about 7 or 9, after that there is a steady performance decrease.

The results are well explained by the fact that larger values of m and w (i.e. larger LSR) make the descriptor more distinctive（独特的） while they also reduce the repeatability（可重复性） of the LSR.

We also evaluate the time performances of these two descriptors which are given in Table 1.

Although the time performances may change from image to image, their relative relationship will keep the same. We only show the results which are generated from an example image with the size of 900×600 and 573 extracted lines. Basically, the larger m and w are, the more computational time is consumed.

LBD is less sensitivity（敏感） to the increase of m and w than that of MSLD, especially for the increase of w.Based on the aforementioned evaluation, through the rest of the paper, the descriptor will be computed from a LSR with m= 9 and w= 7, resulting in a 72-dimensional descriptor. Then the computing times of LBD and MSLD for the example image are 28 ms, and 137 ms, respectively.

2.MSLD and LBD更多比较

比较每组照片的，MSLD and LBD recall ratios如下图：

(a) shows the performances of MSLD and LBD for the image illumination changes. From image 1 to image 5, the lighting condition gets worse. The recall ratios decrease with the increment（增长） of the lighting distortion（照明畸变）.

(b) shows the results for images which are generated by a set of in-plane rotation varying from15° to75° .It is interesting that when the rotation angle is 45 (between image 3 and the reference image), LBD and MSLD perform worst because of the aliasing of discrete lines（离散线的混叠）.

(c) and (d) show the descriptor performance against the image compression（压缩） and the image blurring（模糊）, respectively. Not surprisingly, the performances decrease with the increment of the image compression ratio（压缩比） or the image blurring.

(e) shows the descriptor performance against image occlusion（遮挡）. To evaluate the occlusion effect, we first artificially（人工地） add some vertical line（垂直线） features in a background image, then shift the region of interest along the vertical direction of the artificial image to generate a set of smaller images as shown in Fig. 5(e). This process makes sure that for the most of the lines, their LSR in the image sequence（图像序列） will change gradually (some part of the LSR moves out or in). The results show that the descriptor performance decreases with the increment of the image occlusion.

(f) shows the descriptor performance in the lowtexture scene（低纹理场景）. Images in this sequence are captured in front of the window with small view point changes. The results do not show drastic change（巨大的变化） in performance because of the small baseline between images.

(g) shows the descriptor performance against large view point change. The view angles between the query images and the reference image range approximately from
-70° to 60° . No doubt, the descriptors perform better when the absolute value of the view angle is smaller (image3 and image4).

(h) shows the most challenging case for the descriptors, i.e, the large scale change. The scale ratio(比率) between the query images and the reference image range from 0.9 to 0.3. The performance decreases fast with the scale change.

第二部分：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：