直線段檢測算法---LSD：a Line Segment Detector
LSD的核心是像素合并于誤差控制。利用合并像素來檢測直線段并不是什麼新鮮的方法，但是合并像素的方法通常運算量較大。LSD号稱是能線上性時間（linear-time）内得到亞像素級準确度的直線段檢測算法。LSD雖然号稱不需人工設定任何參數，但是實際使用時，可以設定采樣率和判斷倆像素是否合并的方向差。我們知道，檢測圖像中的直線其實就是尋找圖像中梯度變化較大的像素。LSD的目标在于檢測圖像中局部的直的輪廓，這也是我們稱之為直線分割的原因。輪廓是圖像中的某些特殊區域，在這些區域，圖像的灰階從黑到白或者從白到黑的劇烈變化。是以，梯度和level-line是兩個重要的概念，如下圖所示：
算法首先計算每個像素的level-line angle（此文章下面的[2]）以構成一個level-line 場。該場被分割為連通的若幹個部分，它們方向近似相同并且在容忍度τ内，這樣可以得到一系列regions，這些 regions被稱為 line support regions（支援域）。如下圖所示：
每一個line support region其實就是一組像素，它也是直線段（line segment）的候選。同時，對于這個line support region，我們可以觀察它的最小外接矩形。直覺上來講，當一組像素構成的區域，特别細長時，那麼這組像素更加可能是直線段。line support region的一個主慣性軸作為矩形的主方向，矩形的大小選擇為覆寫整個區域。
矩形中的像素的level-line angle與最小外接矩形的主方向的角度差在容忍（tolerance）τ内的話，那麼這個點被稱作"aligned point"（同性點）。通過統計最小外接矩形内的所有像素數n和其内的alinedg points個數k，用來判定這個line support region是否是一個直線段。判定的準則使用的是a contrario approach and the Helmholtz principle。
LSD算法的具體解釋：
輸入：灰階圖
輸出：一系列的直線分割結果。
1.以 s=0.8的尺度對輸入圖像進行高斯核采樣。
2.計算每一個點的梯度值以及梯度方向（level-line orientation），其中gx和gy分别為水準和垂直方向梯度。
3.根據梯度值對所有點進行僞排序（pseudo-ordered），建立狀态清單，所有點設定為UNUSED。
[設定圖像梯度強度範圍到[0, 1023](大于1023的梯度強度，強制設定為1023),建立1024個連結清單，周遊整個梯度圖，根據梯度強度，相同梯度值像素坐标放入同一張連結清單中,将1024個連結清單，按從大到小順序，合成一張大連結清單(首部為1023連結清單，尾部為0)]
4.将梯度值小于ρ的點狀态表中相應位置設定為USED。
5.取對外連結表頭部存儲圖像坐标位置，作為種子像素，
do：
a.以seed為起點，根據梯度角方向相似(搜尋周圍UNUSED并且方向在門檻值[ -τ, τ]範圍内的點)，進行區域擴散。(每擴散一個像素，将該像素坐标從連結清單中删除，并且做标記(狀态改為USED)，之後新的區域擴散，無法再擴散到在像素)。
b.将擴散區域進行矩形拟合,R。
c.判斷同性點（aligned pt）密度是否滿足門檻值D，若不滿足，截斷（cut）R變為多個矩形框，直至滿足。
d.計算NFA(拟合矩形精度誤差)。
e.改變R使NFA的值更小直至NFA <= ε ，R加入輸出清單;如果改變了還不滿足或者矩形區域太小，舍去。
6.繼續回到第5步，從連結清單中，找到下一個種子點，從剩下圖像進行區域擴散，至到周遊完全圖，得到所有檢測到的直線。
【1】将輸入的圖像縮小為原來大小的80%，即縮放尺度為80%（S=0.8），目的在于減弱甚至消除很多圖像中出現的鋸齒效應。注意：80%的縮放因子意味着x和y方向都縮放為原來的80%，即總的像素為原來的64%。
縮小是通過高斯采樣來進行的：圖像首先采用高斯核進行濾波進而避免鋸齒效應，再進行降采樣。高斯核的标準差是由 Σ / S來決定的，此處的S是縮放因子，參數Σ設定為0.6，以此來保持鋸齒效應和圖像模糊之間的平衡。
【2】梯度計算
【3】梯度排序
梯度值越大，越是顯著的邊緣點，更适合作為種子點。但是對梯度值進行完全排序是一個時耗性很高的工作。是以簡單的将梯度值劃分為1024個等級（bins），這1024個等級涵蓋了梯度由0~255的變化範圍，這種排序是一個線性的時耗。LSD首先将最大梯度的像素作為種子點，種子點從梯度值最高的bin開始搜尋，依次往下，直至所有點标記為UNUSED。
【4】梯度門檻值（小梯度值抑制）
小梯度值點往往出現在平滑區域，或者僅僅是噪聲。不在關注的範圍内，但是他們的存在往往會嚴重影響直線角度的計算。在LSD計算過程中，梯度幅值小于ρ的像素點将被拒絕參與line support region或者矩形的建構過程。
【5】區域增長
line support region是通過合并方向近似相同的像素得到。其實在這裡，這個合并的過程更多的是依賴于區域生長算法。
輸入：level-line 場LLA，種子像素P，和角度容忍度 τ以及對應每個像素的狀态變量
輸出：一組像素區域
區域生長算法用于生成一個line support region。最初的區域角θregion是種子點（P）的level-line angle，遞歸的，将已經在區域的像素（P）的未使用的鄰居用來測試，
and the ones whose level-line angle is equal to the region angle θregion up to a tolerance τ are added to the region.
每次添加一個新的像素到該區域，區域的角度就被更新為：
下标j：用于周遊區域中的所有像素，如此持續進行，直到沒有任何像素添加到矩形當中。
角度容忍度 τ設定為22.5度,或者說π/8弧度，so it was set to obtain p = 1/8。在該誤差容忍度範圍内的像素點都将被選擇到矩形中，這是因為他們在很大程度上跟矩形的方向保持一緻。
如下圖所示，實驗發現，22.5是一個較好的參數。
【6】矩形估計
上一步形成line-support region一系列相鄰的離散點，需要将他們包含在一個矩形框内R，這個可以看做寬度為R的寬，長度為R的長的候選直線。R選擇能包含line-support region的最小矩形，所有點的梯度規範化值平均計算重心，R長軸的方向設定為R的方向。
矩形的中心(c x , c y )：
G（j）是像素j的梯度幅值，下标j用于周遊矩形區域内的所有像素。
矩形的主方向被設定為矩陣的最小特征值對應的特征向量的角度：
【7】NFA計算
自己的了解：其實這個NFA，就是通過你的觀察圖中矩形中的aligned points所占比例的大小與引入的一個新的模型 （a contrario model）的aligned points作比較的機率，來限制這個矩形是不是可以作為一條“線段”。（就如同作者所希望的，這個aligned points越多，越有可能是一條“線段”）
矩形驗證：
用來驗證矩形是否可以作為檢測線段的方法是基于a contrario approach and the Helmholtz principle .
the Helmholtz principle：在完美噪聲圖像圖像中不應該檢測到目标。
a contrario approach：一個不會檢測到目标的噪聲圖像。
對于本課題，contrario model H0是一個像素值為level-line angle的圖像，其level-line angle随機分解為獨立且服從平均分布于[0,2π]。
（即主要有以下兩個屬性： （1）{LLA(j)}，是 level-line場，其中j是像素，由獨立随機變量組成；（2）LLA(j)在[0,2π]上均勻分布。 ）
這裡用NFA（Number of False Alarms）來評判observe img中某個候選R小于contrario model中相同位置R裡同性點（aligned points）的數量的機率，如果NFA的值很大，認為在觀測圖像中aligned points比contrario model中aligned points小的機率很大，将其認為是common，平常的，背景中的一部分。如果NFA的值很小，認為目标是相對突出（rare）的，是一個合适的“直線”。
其中，Ntest為目前大小（n*m）圖像中直線（矩形框）的數量。在n*m的圖像中直線的起點和終點分别有m*n種選擇，是以一共有(n*m）*(n*m)種起點和終點搭配。線段的寬度為(n*m)^0.5，是以在m*n大小的圖像中有（n*m）^2.5 種不同直線。The precision p is initially set to the value τ /π.We will note γ the number different p values potentially tried. Each rectangle with each p value is a different test.Thus, the final number of tests is
PH0是對應 contrario model H0 的一個機率，I是在模型H0下的随機圖像。（H0是圖像梯度方向的噪聲模型而不是一個圖像的噪聲模型。）
k(r,I) 為contrario model ，I 中 r 矩形裡aligned pt的數量。
k(r,i) 為observe img，i 中 r 矩形裡aligned pt的數量。
一個關鍵概念是p-aligned points，是指矩形中的level-line angle與最小外接矩形的主方向的角度差在容忍（tolerance）pπ内的像素點。 precision p最初設定的值為τ /π（角度正負容忍誤差為τ ，總容忍誤差為2τ 。那麼在contrario model中，某個點為aligned point的機率為 p=2*τ / 2*π =τ / π），
k(r, I) 服從二項分布，是以：
是以，NFA的數量與矩形r有關：
簡化r和i的公式：
其中，N和M是采樣過後圖像的列和行，n：矩形的像素的總數，k：p-aligned點數。
二項分布：
解釋：設k(r,i)=k。那麼，在 I 中的 r 矩形裡，總像素個數為 n，I 中的 r 矩形裡aligned pt個數k(r,I)大于等于k的話，可選擇的值為k(r,i)、k(r,i)+1、k(r,i)+2，......n。
NFA計算：
若NFA(r) ≤ ε，那麼可以認為結果有效。As stated before,we set ε = 1 .
其中，E是期望算子，1是訓示符函數，r是考慮的矩形集合，而I是H0上的随機圖像。
該定理指出在 contrario model H0上的ε-meaningful 矩形的平均數量小于ε。是以，噪聲檢測的次數通過ε控制的并且可以根據需要往小的調整。
換句話說，這表明LSD滿足亥姆霍茲原理（具體證明可以看原文）。
【8】Aligned Points Density
在某些情況下，這τ角度容忍度的方法産生一個錯誤的解釋。這個問題可能會出現兩直線邊緣存在于圖像形成一個夾角小于容忍度τ。如下圖顯示了一個線支援區域（灰色）和與其對應的矩形的例子：
在LSD中，這個問題是通過檢測有問題的線支援區域并将其切割成兩個較小的區域來處理的，希望在适當的位置将該區域分割出來以解決問題。這個“角度問題”的檢測是基于矩形中同性點的密度。
當這個問題不存在時，矩形非常适合于線支援區域，并且同性點的密度很高。另一方面，當“角問題”出現時，正如前面的圖所看到的，同性點的密度很低。同樣，當一個稍微彎曲的邊被一系列直邊近似地逼近時，近似的程度（多少線段被用來覆寫曲線的一部分）與同性點的密度有關；是以，對齊點密度也與線段近似曲線的精度有關。
同性點密度的計算公式：
規定一個門檻值D ，在這裡設定D=0.7，文章認為這個數字既能保證同一個R中的同性點屬性相近，也能保證R不會被過分的分割為小的矩形。
若d > D（同性點密度門檻值），accepted。否則，需要将R截斷。
R截斷的方法有兩種：“縮小角度誤差門檻值”與“縮小區域半徑”的方法。在這兩種方法中，區域中的一部分像素被保留，而另一些則重新标記為NOT USED，是以它們可以在将來的線支援區域中再次使用。
縮小角度容忍門檻值：簡單的将τ值縮小，再次從目前R的seed開始搜尋，看是否滿足要求。
縮小區域半徑：逐漸去除遠離種子的像素，直到滿足标準或區域太小而被拒絕為止。當線支援區域對應于一條曲線時，該方法效果最好，并且在滿足密度準則之前需要減少區域，通常意味着對曲線有一定程度的近似。
【9】矩形的改進
如果目前的R仍舊不能滿足NFA(要求：NFA(r) ≤ ε)，以下的方法将對其進行改進。考慮到在有些情況下，删除line-support region中的一個點會減少R的 length-1個點（想象為對角線）。對不滿足NFA的R，采取以下政策：
1.減小p=p/2
2.短邊減少一行
3.長邊減少一行
4.長邊減少另一行
5.減小p=p/2
直至滿足NFA（NFA(r) ≤ ε）或 R過小被拒 或 p為原來的1/32。
備注：
[1]二項分布的計算：
[2] 梯度的數學基本概念 https://wenku.baidu.com/view/d3dbe40903d8ce2f00662358.html
導數：場中沿不同方向的變化率
梯度：确定下降最快的方向
轉載自：直線段檢測算法---LSD：a Line Segment Detector
OpenCV中的demo實作
#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;
if (argc != 2)
{
std::cout << "Usage: lsd_lines [input image]. Now loading ../data/building.jpg" << std::endl;
in = "../data/building.jpg";
}
else
{
in = argv[1];
}
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;
}