一种基于KLT的直线段匹配算法

罗汉杰. 直线段匹配方法、装置、存储介质及终端[P]. 中国专利: CN109919190A, 2019-06-21. Github: https://github.com/HanjieLuo/line_matching

背景

在计算机视觉系统中，其中一种重要任务是图像中的特征匹配。我们在多张图片中提取出一些特征纹理，并且将这些纹理匹配起来。在传统的方法中，我们一般使用梯度值大的，处于边角位置的点作为特征来进行匹配。但在实际使用中，图像中能够提取的，稳定的特征点是有限的。

我们发现，比起特征点，图像中的直线具有更强的稳定性和抗干扰能力；并且在室内等经典场景中，直线纹理出现的概率比特征点要多。

linematching1

而传统的基于描述子的直线匹配方法（如LBD¹，MSLD²等），采用直线的局部外观特征和几何约束特征，对每一根直线段进行数学建模，然后进行匹配。但这些方法运算量巨大，难以满足实时任务的需求；并且，匹配的成功率也一般。

对于相继拍摄的前后两张图片，可以观察到特征纹理的偏移量较小。基于这个前提，我们可以对直线段使用一些本用于特征点的，高效的匹配方法来实现直线匹配功能。

本文提出了一种图像直线段的匹配方法，它使用了高效的一维光流法特征点匹配方法，对直线段上的点进行匹配操作，然后对匹配点进行统计，从而实现直线段跟踪的功能。

方法

直线检测

$L_0={\{}^0{l}_i{\mid }^0{l}_i={(}^0{p}_{i,0}{,}^0{p}_{i,1}),0\le i<M_0\}$

假设已知有前后相继拍摄的两张图片$I_0$和$I_1$。使用LSD³，EDLines⁴⁵等直线检测算法，在图片$I_0$中获得直线段集合$L_0={\{}^0{l}_i{\mid }^0{l}_i={(}^0{p}_{i,0}{,}^0{p}_{i,1}),0\le i<M_0\}$，$M_0$表示线段数目；${}^0{p}_{i,0}$，${}^0{p}_{i,1}$分别表示图$I_0$上第$i$根线段${}^0{l}_i$的两个端点的二维坐标，$p=[px,py{]}^T$，$T$表示矩阵转置，$p$为一列向量。同样，我们图片$I_1$中获得直线段集合$L_1={\{}^1{l}_i{\mid }^1{l}_i={(}^1{p}_{k,0}{,}^1{p}_{k,1}),0\le k<M_1\}$。

linematching2

锚点匹配

对图$I_0$上的每一条线段${}^0{l}_i\in L_0$，${}^0{l}_i={(}^0{p}_{i,0}{,}^0{p}_{i,1})$：

1. 计算线段的方向向量${}^0{a}_i={[}^0{a}_{i,0}{,}^0{a}_{i,1}{]}^T={(}^0{p}_{i,1}{-}^0{p}_{i,0})/{\Vert }^0{p}_{i,1}{-}^0{p}_{i,0}\Vert$和法向量${}^0{n}_i=[{-}^0{a}_{i,1}{,}^0{a}_{i,0}{]}^T$。

linematching3

2. 以${}^0{p}_{i,0}$为起点，${}^0{p}_{i,1}$为终点，${}^0{a}_i$为方向，每隔距离$s$，选取一系列锚点，并将它们的坐标集合记作${}^0{Q}_i={\{}^0{q}_{i,j}\mid 0\le j<N_i\}$，$N_i$为线段${}^0{l}_i$的锚点数目，$s$我们一般设置为20。

linematching4

3. 使用一维光流匹配法⁶，对图$I_0$线段${}^0{l}_i$上每一个锚点${}^0{q}_{i,j}$，在图$I_1$上，以${}^0{q}_{i,j}$为起始位置，${}^0{n}_i$为搜索方向，在图$I_1$上找到匹配点${}^1{q}_{i,j}$。

linematching5

点-线匹配

经过上一个步骤后，我们在图$I_1$上找到图$I_0$上所有锚点${}^0{q}_{i,j}$的匹配点${}^1{q}_{i,j}$。在这一个步骤中，我们希望知道匹配点是属于图$I_1$上哪一条直线段的，我们称这一步骤为点-线匹配。

${}^0{q}_{i,j}$为图$I_0$上的锚点，${}^1{q}_{i,j}$为在图$I_1$上的相应匹配点；图$I_1$的直线段集合为$L_1$，$L_1={\{}^1{l}_k{\mid }^1{l}_k={(}^1{p}_{k,0}{,}^1{p}_{k,1}),0\le k<M_1\}$。

对于任意点$q$，到直线段$l=(p_0,p_1)$有最短距离$d$：

$$\begin{array}{rl}v& =p_1-p_0\\ u& =p_0-q\\ t& =min(max(-(v^{T}u)/(v^{T}v),0),1)\\ d& =\Vert tv+u\Vert \end{array}$$

其中$v$，$u$，$t$为中间变量。对于每一个匹配点${}^1{q}_{i,j}$，做：

计算到图$I_1$所有直线段${}^1{l}_k$的最短距离，获的距离集合$ d_k $。\mathrm{比}\mathrm{较}$ d_k $，\mathrm{获}\mathrm{得}\mathrm{的}\mathrm{最}\mathrm{短}\mathrm{距}\mathrm{离}$d_{min}=min⁡( d_k )$\mathrm{和}\mathrm{所}\mathrm{对}\mathrm{应}\mathrm{的}\mathrm{直}\mathrm{线}\mathrm{段}$^1l_{closest(i,j)}$，$0\le closest(i,j)<M_1$。如果$d_{min}<d_{threshold}$，则我们认为点${}^1{q}_{i,j}$是属于直线${}^1{l}_{closest(i,j)}$的。$d_{threshold}$为一经验阀值，我们设置为1。

通过上述步骤，我们获得了匹配点在图$I_1$上所对应的直线段。因此，每一个图$I_0$上的锚点，都有可能匹配到图$I_1$上的任一直线段。

线-线匹配

对于图$I_0$上的任意直线段${}^0{l}_i$，$0\le i<M_0$，拥锚点${}^0{q}_{i,j}$，$0\le j<N_i$；每一个锚点在图$I_1$上存在唯一的匹配点${}^1{q}_{i,j}$，并且我们知道匹配点落在了图$I_1$的任一直线${}^1{l}_{closest(i,j)}$上。

对于任一直线段${}^0{l}_i$：

统计它拥有的锚点在图$I_1$所匹配直线段，假设最多有$Z_i$个锚点匹配到了直线${}^1{l}_{match(i)}$上, $0\le match(i)<M_1$。如果$Z_i/N_i>R$，则我们称这两条直线${}^0{l}_i$与直线${}^1{l}_{match(i)}$互相匹配。$R$为一经验阀值，我们设置为0.4。

实验结果

Github: https://github.com/HanjieLuo/line_matching

---

1. Zhang, Lilian, and Reinhard Koch. "An efficient and robust line segment matching approach based on LBD descriptor and pairwise geometric consistency." Journal of Visual Communication and Image Representation 24.7 (2013): 794-805.↩︎

2. Wang, Zhiheng, Fuchao Wu, and Zhanyi Hu. "MSLD: A robust descriptor for line matching." Pattern Recognition 42.5 (2009): 941-953.↩︎

3. Von Gioi, Rafael Grompone, et al. "LSD: a line segment detector." Image Processing On Line 2 (2012): 35-55.↩︎

4. Akinlar, Cuneyt, and Cihan Topal. "EDLines: A real-time line segment detector with a false detection control." Pattern Recognition Letters 32.13 (2011): 1633-1642.↩︎

5. http://luohanjie.com/2021-02-03/edline-parallel.html↩︎

6. http://luohanjie.com/2018-12-26/1d-klt-feature-tracker.html↩︎