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

背景

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

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

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

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

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

方法

直线检测

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

锚点匹配

对图$I_0$上的每一条线段$^0l_i ∈L_0$，$^0l_i =(^0p_{i,0}, ^0p_{i,1})$：

a. 计算线段的方向向量$^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$。

b. 以$^0p_{i,0}$为起点，$^0p_{i,1}$为终点，$^0a_i$为方向，每隔距离$s$，选取一系列锚点，并将它们的坐标集合记作$^0Q_{i} ={^0q_{i,j}|0≤j<N_{i}}$，$N_i$为线段$^0l_{i}$的锚点数目，$s$我们一般设置为20。

c. 使用一维光流匹配法^[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={^1l_{k} │^1l_{k} =(^1p_{k,0}, ^1p_{k,1}), 0≤k<M_1 }$。

对于任意点$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。

实验结果

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

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

A parallel implementation of EDLine algorithm which based on the Line Segment Detector module of opencv_contrib. Compared to the original version, the parallel one results in a almost 50% time reduction on PC with 4 cores CPU.

Requirements

The code is tested on Ubuntu 14.04. It requires the following tools and libraries: CMake, OpenCV 3.4.

Building

#!bash
git clone https://github.com/HanjieLuo/EDLine_parallel.git
cd EDLine_parallel
mkdir build
cd build
cmake  ..
make

Test

#!bash
./bin/test_edline_detector

Reference

Barfoot, Timothy D. State estimation for robotics. Cambridge University Press, 2017.

Reference

Möller, Tomas, and Ben Trumbore. "Fast, minimum storage ray-triangle intersection." Journal of graphics tools 2.1 (1997): 21-28.

I developed an deformable surface tracking demo based on Ngo's work^[1].

The blue mesh in the video is the projection of the resulting 3D surfaces using ground truth keypoint matches while the red dots denote the projections of the mesh vertices onto the ground-truth surface.

Notes on the paper: