Line Segmentation Detection

LSD算法是一个直线提取算法,在opencv 中也有封装,它的主要思想是通过求导得到灰度的梯度,因为灰度梯度的方向的垂直方向就是线条的方向,将有相同方向的向量用矩形圈起来,再将举行精细化,最后就可以得到的一条线段了。

首先,我们看下图,这里的图片首先根据梯度的垂线构造了一个level-line field,它把和梯度的垂直方向的线叫做level-line,所以这个field就是由这样的线组成的场。有了这个场,因为有直线的区域我们总能够找到,很多方向相同的level-line,这样我们就能得到右边这些颜色区域了,也就是所谓的line support region。





  1. 缩放至80% (Guassian Subsampling)
  2. 计算horizontal & vertical方向的gradient
  3. gradient pseudo-ordering:

    LSD is a greedy algorithm and the order in which pixels are processed has an impact on the result. Pixels with high gradient magnitude correspond to the more contrasted edges. In an edge, the central pixels usually have the highest gradient magnitude. So it makes sense to start looking for line segments at pixels with the highest gradient magnitude.

    Sorting algorithms usually require O(n log n) operations to sort n values. However,a simple pixel pseudo-ordering is possible in linear-time. To this aim, 1024 bins are created corresponding to equal gradient magnitude intervals between zero and the largest observed value on the image. Pixels are classi ed into the bins according to their gradient magnitude. LSD uses rst seed pixels from the bin of the largest gradient magnitudes; then it takes seed pixels from the second bin, and so on until exhaustion of all bins. 1024 bins are enough to sort almost strictly the gradient values when the gray level values are quantized in the integer range $[0,255]$.

  4. gradient threshold:

    Pixels with small gradient magnitude correspond to at zones or slow gradients. Also, they naturally present a higher error in the gradient computation due to the quantization of their values. In LSD the pixels with gradient magnitude smaller than  are therefore rejected and not used in the construction of line-support regions or rectangles.

  5. region growing:
  6. rectangular approximation
  7. NFA computation:

    A key concept in the validation of a rectangle is that of $p$-aligned points, namely the pixels in the rectangle whose level-line angle is equal to the rectangle’s main orientation, up to a tolerance $p\pi$.

    NFA = (NM)^{5/2}\gamma \sum_{j=k}^n \begin{pmatrix} n \ j \end{pmatrix}p^j (1-p)^{n-j}

    The rectangles with $NFA(r)\leq \epsilon$ are validated as detections.

  8. Aligned Points Density
    • reduce angle tolerance
    • reduce region radius
  9. rectangle improvement


  1. Von Gioi R G, Jakubowicz J, Morel J M, et al. LSD: a line segment detector[J]. Image Processing On Line, 2012, 2: 35-55.
  2. Von Gioi R G, Jakubowicz J, Morel J M, et al. LSD: A fast line segment detector with a false detection control[J]. IEEE transactions on pattern analysis and machine intelligence, 2008, 32(4): 722-732.

Powered by Hexo and Hexo-theme-hiker

Copyright © 2018 - 2024 LucasXU All Rights Reserved.

UV : | PV :