一种基于KLT的直线段匹配算法
罗汉杰. 直线段匹配方法、装置、存储介质及终端[P]. 中国专利: CN109919190A, 2019-06-21. Github: https://github.com/HanjieLuo/line_matching
背景
在计算机视觉系统中，其中一种重要任务是图像中的特征匹配。我们在多张图片中提取出一些特征纹理，并且将这些纹理匹配起来。在传统的方法中，我们一般使用梯度值大的，处于边角位置的点作为特征来进行匹配。但在实际使用中，图像中能够提取的，稳定的特征点是有限的。
我们发现，比起特征点，图像中的直线具有更强的稳定性和抗干扰能力；并且在室内等经典场景中，直线纹理出现的概率比特征点要多。
而传统的基于描述子的直线匹配方法（如LBD1，MSLD2等），采用直线的局部外观特征和几何约束特征，对每一根直线段进行数学建模，然后进行匹配。但这些方法运算量巨大，难以满足实时任务的需求；并且，匹配的成功率也一般。
对于相继拍摄的前后两张图片，可以观察到特征纹理的偏移量较小。基于这个前提，我们可以对直线段使用一些本用于特征点的，高效的匹配方法来实现直线匹配功能。
本文提出了一种图像直线段的匹配方法，它使用了高效的一维光流法特征点匹配方法，对直线段上的点进行匹配操作，然后对匹配点进行统计，从而实现直线段跟踪的功能。
方法
直线检测
\(L_0= \lbrace ^0l_i \mid ^0l_i =(^0p_{i,0}, ^0p_{i,1}), 0≤i<M_0 \rbrace\)
假设已知有前后相继拍摄的两张图片\(I_0\)和\(I_1\)。使用LSD3，EDLines45等直线检测算法，在图片\(I_0\)中获得直线段集合\(L_0= \lbrace ^0l_i \mid ^0l_i =(^0p_{i,0}, ^0p_{i,1}), 0≤i<M_0 \rbrace\)，\(M_0\)表示线段数目；\(^0p_{i,0}\)，\(^0p_{i,1}\)分别表示图\(I_0\)上第\(i\)根线段\(^0l_i\)的两个端点的二维坐标，\(p=[px,py]^T\)，\(T\)表示矩阵转置，\(p\)为一列向量。同样，我们图片\(I_1\)中获得直线段集合\(L_1= \lbrace ^1l_i \mid ^1l_i =(^1p_{k,0}, ^1p_{k,1}),0≤k<M_1 \rbrace\)。
锚点匹配
对图\(I_0\)上的每一条线段\(^0l_i ∈L_0\)，\(^0l_i =(^0p_{i,0}, ^0p_{i,1})\)：
- 计算线段的方向向量\(^0a_i =[^0a_{i,0}, ^0a_{i,1}]^T = (^0p_{i,1} -^0p_{i,0})/‖^0p_{i,1}-^0p_{i,0}‖\)和法向量\(^0n_i =[-^0a_{i,1}, ^0a_{i,0}]^T\)。
- 以\(^0p_{i,0}\)为起点，\(^0p_{i,1}\)为终点，\(^0a_i\)为方向，每隔距离\(s\)，选取一系列锚点，并将它们的坐标集合记作\(^0Q_{i} = \lbrace^0q_{i,j} \mid 0≤j<N_{i} \rbrace\)，\(N_i\)为线段\(^0l_{i}\)的锚点数目，\(s\)我们一般设置为20。
- 使用一维光流匹配法6，对图\(I_0\)线段\(^0l_{i}\)上每一个锚点\(^0q_{i,j}\)，在图\(I_1\)上，以\(^0q_{i,j}\)为起始位置，\(^0n_{i}\)为搜索方向，在图\(I_1\)上找到匹配点\(^1q_{i,j}\)。
点-线匹配
经过上一个步骤后，我们在图\(I_1\)上找到图\(I_0\)上所有锚点\(^0q_{i,j}\)的匹配点\(^1q_{i,j}\)。在这一个步骤中，我们希望知道匹配点是属于图\(I_1\)上哪一条直线段的，我们称这一步骤为点-线匹配。
\(^0q_{i,j}\)为图\(I_0\)上的锚点，\(^1q_{i,j}\)为在图\(I_1\)上的相应匹配点；图\(I_1\)的直线段集合为\(L_1\)，\(L_1= \lbrace ^1l_{k} \mid ^1l_{k} =(^1p_{k,0}, ^1p_{k,1}), 0≤k<M_1 \rbrace\)。
对于任意点\(q\)，到直线段\(l=(p_0, p_1)\)有最短距离\(d\)：
\[\begin{aligned} v &= p_1 - p_0 \newline u &= p_0 - q \newline t &= min(max(-(v^T u)/(v^T v),0),1) \newline d &= ‖tv+u‖ \end{aligned}\]
其中\(v\)，\(u\)，\(t\)为中间变量。对于每一个匹配点\(^1q_{i,j}\)，做：
计算到图\(I_1\)所有直线段\(^1l_{k}\)的最短距离，获的距离集合$ d_k \(。比较\) d_k \(，获得的最短距离\)d_{min}=min( d_k )\(和所对应的直线段\)^1l_{closest(i,j)}$，\(0≤closest(i,j)<M_1\)。如果\(d_{min}<d_{threshold}\)，则我们认为点\(^1q_{i,j}\)是属于直线\(^1l_{closest(i,j)}\)的。\(d_{threshold}\)为一经验阀值，我们设置为1。
通过上述步骤，我们获得了匹配点在图\(I_1\)上所对应的直线段。因此，每一个图\(I_0\)上的锚点，都有可能匹配到图\(I_1\)上的任一直线段。
线-线匹配
对于图\(I_0\)上的任意直线段\(^0l_i\)，\(0≤i<M_0\)，拥锚点\(^0q_{i,j}\)，\(0≤j<N_i\)；每一个锚点在图\(I_1\)上存在唯一的匹配点\(^1q_{i,j}\)，并且我们知道匹配点落在了图\(I_1\)的任一直线\(^1l_{closest(i,j)}\)上。
对于任一直线段\(^0l_i\)：
统计它拥有的锚点在图\(I_1\)所匹配直线段，假设最多有\(Z_i\)个锚点匹配到了直线\(^1l_{match(i)}\)上, \(0≤match(i)<M_1\)。如果\(Z_i/N_i >R\)，则我们称这两条直线\(^0l_i\)与直线\(^1l_{match(i)}\)互相匹配。\(R\)为一经验阀值，我们设置为0.4。