参考文献：EDLines: A real-time line segment detector with a false detection control ----Cuneyt Akinlar  , Cihan Topal

 1. Introduction

这种算法根本不需要参数调整，只需为所有类型的图像运行一组默认参数即可。

传统的直线段检测算法开始于计算边缘图，通常由著名的Canny边缘检测器（Canny, 1986）。接下来是Hough变换（Hough, 1962; Illinworth and Kittler, 1988; Kalviainen et al., 1996），提取含有一定数量的边缘点的所有的线。线碎成线段通过间隙和长度阈值（Duda and Hart, 1972）。这些方法通常很慢，它们通常将非连续的线段组合在一起产生大量错误检测。

有许多变种的Hough变换（HT），例如，Randomized Hough transform (Xu et al., 1990), Progressive Probabilistic Hough transform (Kiryati et al., 1991; Matas et al., 2000;Galambos et al., 2001), Elliptical Gaussian kernel-based Hough transform (Fernandes and Oliveira, 2008; KHT software package),and many others (Princen et al., 1990; Gorman and Clowes, 1976;Lam et al., 1994; Kang et al., 2007; Chao et al., 2009),每一个试图弥补标准Hough变换不同的缺点。在这些技术中，（Fernandes and Oliveira, 2008; KHT software package）提出一个有效的HT程序方案。给定一个二进制边缘图，KHT实现软件实时性能而成为伪线检测算法的鲁棒性。
KHT也有默认的参数设置，可用于所有的边缘图。然而，所有基于Hough变换的技术都需要一个二值边缘映射作为输入，它们通常在（角度，半径）表示中生成无限长的线段（而不是线段），然后必须细分为线段。对于这些技术来说，干净的输入边映射是非常关键的，但是用于边缘图生成的参数不是自动的，必须由用户决定。
图1显示了通过OpenCV的Hough产生的线段变换的方法，即cvhough-lines2功能。为了得到这一结果，在Canny边缘检测和直线提取中分别设置了不同的阈值，并给出了最佳结果。虽然在房屋上检测到的一些长线段是准确的，但有许多不恰当的线段检测，特别是围绕着各向异性结构，如灌木丛、草地和树木。Hough变换通过KHT软件包产生结果，虽然比OpenCV的cvHoughLines2要快得多，但KHT产生无限长的线而不是线段，它必须被分解成线段的后处理步骤。根据记录，KHT软件包只需要16.5毫秒（5毫秒生成边缘图加11.5 ms线提取）在图1的房子的图像，并输出360条线。

代替使用霍夫变换（Hough transform）, Chan and Yip (1996) and Etemadi (1992)提出了经过边缘图的计算后用不同的技术来提取线段。具体来说，Etemadi’s method (Etemadi, 1992)是基于从一个给定的边缘图像素生成链，然后通过遍历这些链提取直线段和弧线。虽然线段和弧线的提取过程是无参数的，但是边缘检测仍然是需要参数的，留给用户添加。这种方法产生良好的局部线段和弧线，但它产生了太多的错误的部分，特别是在嘈杂的背景或含有复杂的结构，如树木，草，多云的天空，或类似的各向异性结构。图1显示了Etemadi’s的结果只有直线段显示。

可选择使用的二进制边缘图线段检测，也有技术，其工作只是利用像素的梯度方向（(Burns et al., 1986; Beveridge et al., 1996; Desolneux et al., 2000, 2008; Grompone von Gioi et al., 2008a,b, 2010).）。第一个这样的建议是由Burns al（1986）and Beveridge et al. (1996)提出的，在每个像素处计算水平线方向，然后通过组合具有相同方向的像素来生成线段。从像素开始，观察相邻像素的水平线角，如果它们具有相同的方向，将它们结合起来。虽然这项工作对于最近的一些线探测器奠定了基础，但它所产生的结果类似Etemadi’s method产生太多有大量错误的线段。

Desolneux et al. (2000, 2008)通过使用 Burn’s 像素定位的思想，提出了一个通过控制错误的数量的无参数线检测。他们的想法是计算在一个特定的方向上的对齐像素（aligned pixels）的数量，如果观察到的结构是有感知意义，接受一组像素作为一个线段。这就是所谓的从Gestalt theory 的论赫姆霍兹原则（Helmholtz principle）(Desolneux et al., 2008)并作为线的验证方法。虽然这种方法有望不产生错误，但是许多有效的短线段失踪（见Desolneux et al.’s的结果如图1所示）。这种方法在自然界中也是非常全球性的，可以产生非常长的线，而实际上这些线应该被分解成几个较小的线段（观察两个不同楼层上的窗户被组合了）。此外，该算法计算量非常大，因此速度非常慢（在给定的图像上需要超过10秒）。

通过扩展Burns’s工作为线段的生成，并结合他们通过 Desolneux’s线验证方法定于亥姆霍兹原理Helmholtz principle (Desolneux et al., 2008), Grompone von Gioi et al. (2008a,b, 2010)最近提出了一个无参数的线检测算法，称为线段检测器（LSD），可产生精确的线段，并控制错误检测的数量。虽然LSD对大多数类型的图像产生良好的效果（见图1中的LSD结果），但它在背景含有一些白噪声的图像中失败，而且它的运行时间仍然是令人望而却步的，这使得它不适合实时应用。

在本文中，我们提出了一个快速、无参数的线段检测器，命名为EDLines (Akinlar and Topal, 2011)，它产生强大的和准确的结果，比最快的已知线段检测器速度更快，达到11倍；换句话说，the LSD by Grompone von Gioi et al. (2008a,b, 2010). 我们的探测器还包括一个线的验证步骤定于亥姆霍兹原理Helmholtz principle (Desolneux et al., 2008)，这让它控制错误检测的数量。 EDLines得到的结果，我们看到的是，LSD非常相似，有所有主要的线段检测，并有极少数误报。此外， EDLines运行实时以炫目的速度为9.45毫秒，约10倍的速度比LSD对给定的图像。

EDLines包括三个步骤：

（）给定一个灰度图像，we first run our fast，新的边缘检测、边缘绘制（ED）算法，产生一套干净的，像素相邻的链，我们称之为边缘。边缘线段直观地反应对象的边界。

（）然后，利用直线度准则，即最小二乘直线拟合法，从生成的像素链中提取线段。

（）最后，线的验证步骤定于亥姆霍兹原理Helmholtz principle (Desolneux et al., ; Grompone von Gioi et al.,2008a)是用来消除虚假线段的检测。

本文的其余部分组织如下：
2节简要地描述了我们的边缘检测、边缘绘制（ED）算法（Topal et al., 2010; Topal and Akinlar, submitted for publication;Edge Drawing Web Site）。
3节介绍了如何由ED产生的像素链来拟合线段。
4节描述了线的验证步骤。
5节讨论了算法的内部默认参数，这些参数是固定的，对于不同的图像从不改变。
6节比较EDLines 的现象在文中通过实验，7节总结全文。

2. Edge detection by Edge Drawing

边缘绘制Edge Drawing (ED)是我们最近提出的新的、快速的边缘检测算法。是什么使ED脱颖而出，是以下：而其他边缘检测器则输出一个二值边缘图像作为输出，其中检测到的边缘像素通常是独立的、不相交的、不连续的实体；

ED产生一组边缘段，这些段是干净的、连续的，即连接的边缘像素链。因此，虽然其他边缘检测器的输出需要进一步处理，以产生潜在的对象边界，这可能甚至不可能或导致不准确；

ED不仅产生完美的连接对象的边界，默认情况下，但它也实现了这一惊人的速度相比其他边缘检测器。

给定一个灰度图像，Edge Drawing检测的四个步骤：

（1）图像先通过一个过滤器，例如，高斯，抑制噪声和输出平滑图像---用一个5×5高斯核（默认）。
（2）计算梯度的幅值和在平滑图像的每个像素的方向。任何已知的梯度算子，e.g., Prewitt, Sobel, Scharr, etc.可在这一步。
（3）我们计算一组像素，称为锚（anchors），这是一个边缘像素有非常高的概率（edgels）。锚对应于梯度算子产生最大值的像素，即梯度图的峰值。
（4）最后，我们连接第三步计算的锚，绘制它们之间的边。整个过程类似于孩子的边界完成拼图，在那里孩子被赋予一个物体的虚线边界，并要求他通过连接点完成边界。

从一个锚（点），ED利用相邻像素的梯度幅值和方向，通过梯度极值（gradient maximas）走到下一个锚。如果你把渐变图想象成一座3D的山，这很像是从山顶爬到山顶。

图2显示了ED在128×128像素的灰度图像的动作。图2（b）显示的梯度图，其中白色像素对应于高梯度值（山顶）。图2（c）示出了一组与梯度图的峰值相对应的锚点，并清楚地描述了图像中矩形的边界。

最终的边缘图，如图2（d），是通过连接的锚（点）获得。正如前面提到的，ED不仅产生类似于其他边缘检测器的二进制边缘图，而且它还产生一组边缘段，这些段是由对象边界相对应的像素链连接而成。

在给出的例子中，ED产生四个边，为每个矩形的边界。给定这些边缘段，线段提取的剩余部分是重温这些像素链，并将像素拟合成线。下一节描述如何完成。

3. Line segment extraction

最小二乘拟合_直线原理：https://wenku.baidu.com/view/93b7e2b65f0e7cd185253642.html

给定一个由连续的边缘像素链组成的边缘段，这个步骤的目标是将这个链分割成一个或多个直线段。其基本思想是依次跟踪像素，然后用最小二乘线拟合法对像素线进行拟合，直到误差超过某个阈值，例如，1个像素误差。

当误差超过这个门槛，我们生成一个新的线段。然后，该算法递归处理链的剩余像素，直到处理所有像素。

表1显示该算法从一个像素链中提取的线段。其思想是用最小二乘线拟合法（第一次圈）生成最小长度的初始线段，再通过增加像素点来扩大线段（第二次圈）。

最小线长度的值取决于线验证参数，并在第5.4节中进行说明。在检测到最小长度的初始线段之后，我们只需浏览链的剩余像素并计算每个像素到当前拟合线的距离。

我们将像素添加到当前线，只要像素在当前线的一定距离内，例如1个像素的误差。直观地说，我们将继续添加像素到当前线段，直到我们转向一个角落和线的方向改变。

在这一点上，我们输出当前线段。然后对链的剩余像素进行递归处理，以提取更多的线段。

4. Line validation

类似Desolneux et al. (2000)和LSD (Grompone von Gioi et al., 2008b, 2010)，我们的验证方法是基于亥姆霍兹原理 Helmholtz principle，其主要的状态是一个感知有意义的结构，这种结构的期望（分组或完全形态）的偶然性必须很低(Desolneux et al., 2008)。这是一个“矛盾”的方法，其目标被检测作为背景模型的极端值。如Desolneux et al.(2000)，一个合适的背景模型是所有像素（梯度角）是独立的。他们发现，最简单的模型是高斯白噪声。

这里用NFA（Number of False Alarms）来评判observe img中某个候选R小于contrario model中相同位置R里同性点（aligned  points）的数量的概率，用如果NFA的值很大，认为在观测图像中aligned points比contrario model中aligned points小的概率很大，将其认为是common，平常的，背景中的一部分。如果NFA的值很小，认为目标是相对突出（rare）的，是一个合适的“直线”。
用亥姆霍兹原理进行验证，Desolneux定义什么是所谓的“假警报的数”（Number of False Alarms，NFA）的线段如下（Desolneux et al.，2000）：设A是这样一段，长度为“n”有至少“k”点的方向与A的方向对齐在像素大小为N × N的图像中。定义一个作为NFA：

其中代表潜在的线段数在N×N图像中。这是因为线段具有两个端点，并且每个端点可以位于像素中的任何一个点，因此总的个线段。概率“P”用在二项分布（binomial tail）的计算中，精确线的方向，其价值将在5节讨论。

如果其 ，一个事件（a line segment in this case）称为。  Desolneux et al. (2000)建议设置为1，相当于对每个图像的一个虚假的检测。根据这些定义，我们验证提取的线段：对于线段的长度为n，我们计算沿线段每个像素的梯度角并且计算对齐像素 “k”的数量。然后我们计算NFA（n，k），如果为有效，接受线段，否则该线被拒绝。It is important to point out that we perform the gradient computation in the validation step over the original non-filtered image as required by the ‘‘a contrario’’ framework.我们也要注意线的验证是EDLines可选的最后一步，如果认为不必要，可以省略的选项。我们观察到线的验证只拒绝短的线段。长的线从背景有明显的显现，并且永不被拒绝。因此，一个只使用长线（如立体匹配）的应用程序可以完全跳过亥姆霍兹原理的线路验证，并使用一个基于某原理的线验证方法可以快速测试，例如，选择比某个阈值更长的线。这将进一步加快EDLines。

 5. Internal parameters---内部参数

5.1. Gradient magnitude and direction computation---梯度幅度和方向计算

Recall from Section 2 that the first step in our Edge Drawing(ED) algorithm is the computation of the image gradient. To compute the gradient magnitude and the level line angle at pixel (x, y),
we follow Burns et al. (1986) and Desolneux et al. (2008), and LSD(Grompone von Gioi et al., 2010; LSD), and use a 2 × 2 mask asfollows:

是像素值，是梯度幅值，是水平线角度。

在Grompone von Gioi et al. (2010)指出，用这样一个简单的梯度算子的原因是为了减少计算梯度的依赖从而保持像素尽可能独立；因为，像素独立是亥姆霍兹原理的“矛盾”验证所要求的。

5.2. Line validation parameters

Recall from Section 4，我们的线验证是基于线段的长度和线上的对齐像素（aligned pixels）数。应用这个定义，我们需要定义什么'aligned”。我们借Desolneux et al. (2000)的定义：两个点（或线段）P和Q具有相同的方向，即对齐，如果P的角度和Q的之间角度有pi /n度，则有1/n精度。Desolneux还指出，“in agreement with Pyschophysics and numerical experimentation, ‘n’ should not exceed 8”。Burns et al. (1986) and LSD (Grompone von Gioi et al.,2010) 也得出了同样的结论。因此，如果它们的角度在pi/8＝22.5°内(实验发现，角度公差22.5是一个较好的参数)，我们假设两个点（或一个点和一个线段）是对齐的。这对应于8个不同的角度取向和精度为“P = 1/8=0.125,用在NFA计算的概率。

5.3.Gradient threshold, anchor threshold and scan interval---梯度阈值，锚阈值和扫描间隔

[1]梯度阈值

在ED中梯度计算完后，像素的梯度值小于一个确定的阈值则被忽略在锚点的计算和连接中。这让我们消除的像素绝对不能包含边缘元素（edgels），因此没有线段。Following the discussion in Grompone von Gioi et al. (2010),我们设置以便去掉角度误差大于角度公差的点。两个连续像素的最大的量化误差等于2（在相邻像素得到+ 1和-1误差），和22.5°角度公差（参见5.2节），我们计算梯度阈值由以下公式在Grompone von Gioi et al.（2010）给出：

遍历梯度图并且消除梯度值小于阈值（=5.22）的像素，我们得到了我们所说的“边缘地区”的图像。这些像素可能位于一个边缘。

[2]锚阈值和扫描间隔

ED还有两个参数：锚定阈值和扫描间隔(called Detail Ratio in Topal et al. (2010)).As explained in Section 2,阈值梯度群计算后，被称为边缘区域（图2（b）），ED计算一组锚（图2（c）），这是连接使用智能搜寻程序，得到最终的边缘（图2（d））Topal et al., 2010)。目前，ED进行锚计算通过非极大值抑制有个阈值，称为锚阈值。而经典的非极大值抑制，如果在梯度方向上像素的梯度值大于或等于相邻像素的值，考虑一个像素是一个边缘像素的候选人，如果在梯度方向上它的梯度值大于其相邻的邻居 by an amount of Anchor Threshold，ED认为一个像素是锚。锚计算需要阈值的原因是选择质量锚，因为这将有高质量的边缘段。锚定阈值的最佳值没有理论依据；其选择纯粹是经验性的。因此，在对EDLines许多不同类型的图像实验，我们的结论是，锚阈值为3会有高质量的边缘段。
       ED的另一个参数，扫描间隔，用于在不同的行/列间隔中选择锚点。此参数的目标是调整锚的数量，从而，在最终边缘图中的细节量。用扫描间隔“k”，ED扫描每第 kth行/列为锚。因此，扫描间隔为1，ED扫描每行/列，即每一个像素；扫描间隔为4，ED扫描每第四行/列。当锚的数量减少时，最终边界图中的细节也减少了，反之亦然。如果我们想要检测给定图像中的所有线段，想要制作一个图像中所有细节的边缘地图；因此，我们设定扫描间隔为1 。

5.4. Line fit parameters---直线拟合参数

      像素链拟合成线相关的两个参数：（1）最小直线长度；（2）最大均方线拟合误差。

Recall from Section 4，一个线段的长度为“n”，“k”个对齐点，如果被验证。对于最小长度线是有效的，k”必须等于“n”。所以，我们得到。提取的最小直线长度“n”从这个公式，我们得到：，其中p = 0.125。e.g.一个512×512图像的最小直线长度是12像素。在直线拟合步骤开始时，使用该公式计算最小线长度，并且我们不会检测到比最短有效线更短的线段。

最大均方线拟合误差是由EDLines直线拟合步骤使用的另一个参数（指的是表1的算法）。在扩展线段时，我们不断地计算像素到当前拟合直线的距离。如果错误超过某个阈值，我们输出当前的线段，并开始一个新的线段。在我们的算法中，在不同的图像集上进行了大量的实验，我们将此参数为1像素误差。

 6. Experiments

Originall ---full resolution：全分辨率；依次是：一半分辨率；四分之一分辨率。