Hanjie's Blog

我的MBP Pro是2012late版本，系统为10.11.6。最近使用的时候发现卡顿十分明显（特别是用Clion等大程序的时候）。打开活动监视器，发现WindowServer服务占用了很多CPU资源，上网查了一下，最简单的方法是关闭透明效果¹，但是关掉后就不好看了，而且原来开着也没有问题。

然后看到了可以通过重置NVRAM解决²³，尝试了一下，占比貌似的缺降下来了。

可是没过几天，机器又卡了，在网上又差了一下，看到又一个解决方法⁴，在System Preferences > Keyboard中， 将Key Repeat跟Delay Until Repeat往左边设置：

貌似又好了，希望是最终解决方法。

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

背景

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

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

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

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

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

方法

直线检测

\(L_0= \lbrace ^0l_i \mid ^0l_i =(^0p_{i,0}, ^0p_{i,1}), 0≤i<M_0 \rbrace\)

假设已知有前后相继拍摄的两张图片\(I_0\)和\(I_1\)。使用LSD³，EDLines⁴⁵等直线检测算法，在图片\(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})\)：

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\)。

2. 以\(^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。

3. 使用一维光流匹配法⁶，对图\(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。

实验结果

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

1
2
3
4
5
6
7

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

Test

1
2

#!bash
./bin/test_edline_detector