LSD算法概略

简介

LSD是一种线性时间复杂度的局部线段检测器，可以得出亚像素级的图像结果，并且不需要调节很多参数，对图像适应性较好。算法的源码以及视频分析可以在IPOL得到。

算法思想

计算level-lines.leve-lines的定义如下图所示

然后leve-lines方向相近的会在一定的约束下组成连通区域称为line support regions如下图所示：

对一个line support regions采用一个外接矩形来表示，region中的level-lines的方向与外接矩形方向相同的点称为aligned points,它的数目与方框内总的点的数目的比值是作为评价是否是线段的依据。

评价方法基于a contrario approach和Helmholtz principle其基本思想就是一张完全噪声的图片是不会检测出信息的。
算法流程如下：

LSD的检测结果会随着图像尺寸的变化而变化，检测的阈值也会随着图像尺寸的变化而变化。

具体算法过程

1. 将图片缩小到原来的80%，采用高斯采样的方式，可有效避免锯齿带来的不好影响。
2. 梯度场计算，使用2x2核进行计算，并使得LSD的线段具有方向性，起点和终点与图像边界的矢量有关。同时2x2的模板计算出的结果中心在相邻像素位置中间，有利于产生连续的结果。
3. LSD属于贪心算法，会从梯度值最大的像素点开始搜索，为了减少计算量，采用为排序的方式，将梯度分成1024个bin，然后依次从高到低取得像素。
4. 通过一定的方式计算到梯度阈值，对梯度进行过滤。
5. 区域生长算法，如下图所示：
   
6. 外接矩形估计
7. 得到区域外接矩形之后进行NFA(num of false alarms)的计算。
   在计算时间复杂度上该算法会对每个像素执行一次计算，整体上可以算是线性的检测算法
   目前该算法在OpenCV 3.0及以后的版本中也加入进来，但是仍在contrib分支中，需要自行编译，示例代码如下

#include "iostream"
#include "string""
#include "opencv2/core/core.hpp"
#include "opencv2/core/utility.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include "opencv2/imgcodecs.hpp"
#include "opencv2/highgui/highgui.hpp"
using namespace std;
using namespace cv;
int main(int argc, char** argv)
{
    std::string in;
    cv::CommandLineParser parser(argc, argv, "{@input|../data/building.jpg|input image}{help h||show help message}");
    if (parser.has("help"))
    {
        parser.printMessage();
        return 0;
    }
    in = parser.get<string>("@input");
    Mat image = imread(in, IMREAD_GRAYSCALE);
#if 0
    Canny(image, image, 50, 200, 3); // Apply canny edge
#endif
    // Create and LSD detector with standard or no refinement.
#if 1
    Ptr<LineSegmentDetector> ls = createLineSegmentDetector(LSD_REFINE_STD);
#else
    Ptr<LineSegmentDetector> ls = createLineSegmentDetector(LSD_REFINE_NONE);
#endif
    double start = double(getTickCount());
    vector<Vec4f> lines_std;
    // Detect the lines
    ls->detect(image, lines_std);
    double duration_ms = (double(getTickCount()) - start) * 1000 / getTickFrequency();
    std::cout << "It took " << duration_ms << " ms." << std::endl;
    // Show found lines
    Mat drawnLines(image);
    ls->drawSegments(drawnLines, lines_std);
    imshow("Standard refinement", drawnLines);
    waitKey();
    return 0;
}

效果如下：