直線檢測算法匯總

1、場景需求

在計算機視覺領域，我們經常需要做一些特殊的任務，而這些任務中經常會用到直線檢測算法，比如車道線檢測、長度測量等。盡管直線檢測的任務看起來比較簡單，但是在具體的應用過程中，你會發(fā)現這里面還是有很大的優(yōu)化空間，本文對常用的一些比較經典的直線檢測算法進行匯總

2、Hough_line直線檢測算法

Hough變換是一個比較有名的計算機視覺處理算法，該算法可以用來做很多的任務，常用的任務包括直線檢測、圓檢測、橢圓檢測等，下面我們將對該算法進行簡單的分析并進行代碼實戰(zhàn)。

2.1 Hough_line實現步驟

步驟1-首先，它創(chuàng)建一個二維數組或累加器（用于保存兩個參數的值），并將其初始設置為零；

步驟2-用r來表示行，用θ來表示列；

步驟3-數組的大小取決于你所需要的精度。假設您希望角度的精度為1度，則需要180列（直線的最大度數為180）；

步驟4-對于r，可能的最大距離是圖像的對角線長度。因此，取一個像素精度，行數可以是圖像的對角線長度。

2.2 Hough_line代碼實戰(zhàn)

2.3 效果展示與分析

上圖展示了一些Hough_line算法的直線檢測效果。為了驗證該算法的有效性，我選擇了3個不同的具有挑戰(zhàn)性的場景，建筑物、答題卡和門。通過觀察上面的結果我們可以知道該算法基本上能夠檢測出圖中的直線，但是檢測的結果并不是很好，有很多重復和漏檢的情況。除此之外，該算法最大的缺點就是需要根據圖片去調節(jié)參數，關鍵的參數是lines = cv2.HoughLines(edges,1,np.pi/180, 200) 中的200，該值設置的越大圖片中檢測出來的直線數量會越少，你需要根據你自己的測試場景進行調節(jié)。

2.4 HoughP_line代碼實戰(zhàn)

HoughP_line是Hough_line算法的改進版，具有更快的速度和更好的效果。

2.5 效果展示與分析

上圖展示了一些HoughP_line算法的直線檢測效果。上圖都是使用lines = cv2.HoughLinesP(edges,1,np.pi/180, 80, 30, 10) 這個固定的參數來計算出結果的，通過觀察我們可以發(fā)現，HoughLinesP不僅使用起來比較方便，基本上不需要進行調節(jié)參數；除此之外，該算法能夠獲得更好的直線檢測效果。因此，當你想用Hough直線檢測算法，建議你優(yōu)先使用HoughP_line算法。

3、LSD直線檢測算法

LSD是opencv中集成的一個直線檢測算法，該算法的直線檢測效果優(yōu)于Hough算法，而且具有較好的檢測速度，推薦使用。

3.1 LSD算法簡介

LSD快速直線檢測算法是由Rafael Grompone、Jeremie Jackbowicz、Jean-Michel Morel于2010年發(fā)表在PAMI上的文獻《LSD:a Line Segment Dectctor》中提出的，該算法時間復雜度較霍夫變換低。LSD算法通過對圖像局部分析，得出直線的像素點集，再通過假設參數進行驗證求解，將像素點集合與誤差控制集合合并，進而自適應控制誤檢的數量 。一般來說，要檢測圖像中的直線，最基本的思想是檢測圖像中梯度變化較大的像素點集，LSD算法也正是利用梯度信息和行列線（level-line）來進行直線檢測的。

3.2 LSD代碼實戰(zhàn)

3.3 效果展示與分析

上圖展示了一些LSD算法的直線檢測效果。通過觀察上面的結果，我們可以發(fā)現該算法的檢測結果遠遠優(yōu)于Hough和HoughP算法；除此之外，上述的檢測結果都是使用LSD算法的默認參數進行執(zhí)行，如果針對特定的參數進行調節(jié)，可以取得更好的結果，這種情況一般是在你的特定需求場景中對默認的一些參數進行微調操作，往往能獲得意想不到的結果。

上圖展示了LSD直線檢測算法的一些超參數，具體的細節(jié)請看該鏈接。需要說明的是該算法具有3中不同的模式，具體的模式如下圖所示，默認情況下使用模式2（即1），但是經過測試我發(fā)現模式1（即0）通常輸出的效果會更好一些，具體的情況需要你根據你的場景進行分析。

4、FLD直線檢測算法

4.1 FLD算法簡介

FLD直線檢測算法是在該論文中被引入的，該論文中嘗試著使用直線特征來代替原始的SURF點特征進行建筑物識別。與點特征進行相比，線特征具有更容易發(fā)現和更好的魯棒性，線特征基本上不會受到光照、遮擋、視角變化的影響。下面展示了該算法的直線檢測效果，從圖中我們可以看出，線特征比點特征更好一些。

4.2 FLD算法代碼實戰(zhàn)

上圖展示了FLD直線檢測算法的檢測效果。通過觀察我們可以發(fā)現該算法具有很好的檢測效果，基本上可以檢測出圖中所有的直線，和LSD的性能類似，具體使用哪種算法需要你根據自己的應用場景去進行選擇。

5、EDlines直線檢測算法

5.1 EDlines算法簡介

EDlines直線檢測算法是在該論文中提出的。本文提出了一個快速、無參數的線段檢測器，命名為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對給定的圖像。

5.2 EDlines算法實現步驟

步驟1-首先，給定一個灰度圖像，運行新的邊緣檢測、邊緣繪制（ED）算法，產生一套干凈的，像素相鄰的鏈，我們稱之為邊緣。邊緣線段直觀地反應對象的邊界。

步驟2-然后，利用直線度準則，即最小二乘直線擬合法，從生成的像素鏈中提取線段。

步驟3-最后，線的驗證步驟定于亥姆霍茲原理Helmholtz principle (Desolneux et al., 2008; Grompone von Gioi et al.,2008a)是用來消除虛假線段的檢測。

上圖展示了EDlines直線檢測算法的檢測效果。通過上面的觀察，我們可以發(fā)現：1）該算法能獲得和LSD類似的檢測結果；2）該算法抑制了一部分小的誤檢的直線；3）該算法具有更快的運行速度，是LSD的10倍左右。

6、LSWMS直線檢測算法

6.1 LSWMS算法簡介

LSWMS是一個直線檢測算法。本文介紹了一種精確且實時的直線檢測方法。以前的直線檢測方法都沒有使用到圖像場景的先驗知識，因而不需要對輸入的參數進行微調。該算法在檢測精度和檢測速度之間進行了折中，文中使用了一個高效的采樣方法來進行加速處理，然后，文中使用一種快速的直線增長算法基于bresenham算法用改進的mean-shift算法提供精確的線段，同時保持穩(wěn)健對抗噪音。測試了該策略的性能對于各種各樣的圖像，將其結果與流行的最新線段檢測方法。結果表明，我們的建議優(yōu)于這些工作同時考慮了結果和處理速度。

上圖展示的是LSWMS論文中的結果。由于作者提供的代碼需要在Ubuntu下編譯，我沒有去做這個工作，如果你感興趣你可以去運行在本文的3張測試圖片上面的效果。

7、CannyLines直線檢測算法

7.1 CannyLines算法簡介

CannyLines算法在該論文中被提出。本文提出了一種魯棒的線段檢測算法，有效地檢測出輸入圖像中的線段。首先，提出了一種無參數canny算子cannypf，通過自適應地設置傳統canny算子的低閾值和高閾值，從輸入圖像中穩(wěn)健地提取邊緣映射。其次，提出了直接從邊緣地圖中提取共線點簇的有效像素連接和分割技術，并基于最小二乘法對初始線段進行擬合。第三，通過有效的擴展和合并，生成更長、更完整的線段。最后，根據helmholtz原理對檢測到的所有線段進行了驗證，該原理同時考慮了梯度方向和幅度信息。在一組有代表性的圖像上的實驗結果表明，與常用的兩種線段檢測器lsd和edline相比，我們提出的cannyline線段檢測器能夠提取出更有意義的線段，特別是在人造場景中。

上圖展示了CannyLines直線檢測算法的檢測效果。通過觀察上圖我們可以發(fā)現該算法能夠獲得更加準確的檢測結果，具有更少的誤檢。該算法主要是提高了邊緣檢測的效果，具體的效果如下所示：

8、MCMLSD直線檢測算法

8.1 MCMLSD算法簡介

MCMLSD算法出自于該論文。論文中提出了一個融合兩者優(yōu)點的概率算法。在第一階段，使用全局概率hough方法。在第二階段，在圖像域中分析每個檢測到的行，以定位在霍夫圖中生成峰值的線段。通過將搜索限制在一條直線上，線段的分布線上的點序列可以被建模為馬爾可夫鏈和概率最優(yōu)標簽使用標準動態(tài)規(guī)劃算法精確計算，在線性時間內。馬爾可夫假設同時也產生了一種直觀的排名方法，它使用估計期望值的邊際后驗概率線段上正確標記的點的數目。評估由此產生的馬爾可夫鏈邊緣線段檢測器（mcmlsd）我們開發(fā)并應用了一種新的定量方法控制分段不足和分段過量的評估方法。在YorkUrbanDB數據集的評價結果表明，所提出的MCMLSD方法優(yōu)于以相當大的優(yōu)勢達到最先進水平。

上圖展示了MCMLSD算法的檢測效果。通過上面的觀察，我們可以發(fā)現該算法取得了很好的檢測效果，但是美中不足的是該算法的運行速度比較慢，可能也和matlab代碼有關吧。

9、LSM直線檢測算法

9.1 LSM算法簡介

LSM算法不僅僅是一個直線檢測算法，同時也是一個直線合并算法。論文中提出了一種合并這些斷開的線段的算法，以恢復原始的感知準確的線段。該算法根據角度和空間接近度對線段進行分組。然后將每組中滿足新的自適應合并準則的線段對依次合并成一條線段。重復此過程，直到不再合并行段。我們還提出了一種定量比較線段檢測算法的方法。在york-urban數據集上的結果表明，與最新的線段檢測算法相比，我們的合并線段更接近人類標記的地面真線段。

上圖展示了直線檢測算法LSM的檢測效果。左邊一列表示的是LSD的檢測結果，右邊一列表示的是LSM算法的優(yōu)化效果，圖中不同的顏色表示不同的直線。通過上面的觀察，我們可以發(fā)現LSM可以將一些間斷的直線合并成一條更長的直線，這在現實場景中具有很大的用處，但是我們也會發(fā)現LSM算法會錯誤的將一些直線進行合并，會造成一些誤差。

10、總結

本文對比較經典的直線檢測算法進行了總結和分析。對于直線檢測這個任務而言，它在現實場景中具有很多的應用，對于一個具體的場景，你可以根據自己的需要從本文中選擇出一個合適的直線檢測算法進行應用，如果你的場景比較簡單，HoughP_line算法可能就可以滿足你的要求；如果你同時對速度和精度有要求，可以選擇使用EDlines等；如果你需要獲得盡可能長的直線，那么建議你使用LSM直線檢測算法?？偠灾?，最適合你的場景的算法才是最好的算法。