論文回顧之一 一種新的直線段檢測算法---LSD：a Line Segment Detector

原文地址：http://blog.csdn.net/polly_yang/article/details/10085401

近來比較忙+生病，沒有大段的時間學習PGM，臨睡前回顧一篇論文--《LSD: a Line Segment Detector》，這篇文章發表于PAMI2010。特別之處在于能快速檢測圖像中的線段，同時使用了錯誤控制的方法，使得檢測結果比較準確。最后，LSD結果輸出是線段的坐標與屬性，比如起點，終點，線段的粗細。

? ? 首先，我們需要回顧一下，為什么需要檢測圖像中的直線段？直線段作為圖像中邊緣的一種，又有什么特殊之處呢？在Marr關于視覺的計算理論中提到，視覺是一種處理過程，經過這個過程我們能從圖像中發現外部世界中有什么東西和它們在什么地方。同時，我們還知道，信息處理具有三個層次：（1）第一個層次是信息處理的計算理論（theory），也就是研究是對什么信息進行計算和為什么要進行這些計算；（2）第二個層次是算法（algorithm），也就是如何進行所需要的計算，或者說是設計算法；（3）第三個層次是實現算法的機制，也就是研究某一算法的特定構成。對于視覺系統，觀看圖像的過程，也可以看做是信息處理的過程。從圖像推理得到物體的形狀信息的過程也可以對應為三個階段：（1）初始簡圖（primal sketch），這個初始簡圖可以是輪廓圖像，也可以是一堆具有特定意義的特征點構成的掩碼，或者是像素的光強等信息；（2）2.5維簡圖（2.5 dimensional sketch），2.5維簡圖是對初始簡圖進行一系列的處理和運算，推導出的一個能反映某些幾何特征的表象，它和初始簡圖都是以觀察者為核心；（3）三維模型（3D model）。

? ? 那么哪些信息可以用來構造圖像的初始簡圖呢？一個形象的例子是畫畫。畫家速寫時，用很少的邊，點，線等符號，就可以勾勒出大致的景物。當然，這樣的景物與實際景物在人體視網膜上產生的以像素為單位的亮度矩陣式不一樣的，但是人們也可以輕松的識別出他們。這說明視覺對圖形所做的第一個運算就是把他們轉換成一些原始符號構成的描述，這些描述所反映的不止是亮度的絕對值的大小，還有圖像中的亮度變化和局部的幾何特征。

? ? 初始簡圖是一種基元。它可以由若干邊緣段（edge segments），線（line segment），斑點（blob）和端點（terminations）構成，這些雜亂的基元構成的初始簡圖又被稱作未處理的初始簡圖，當這些基元通過各種方式進行聚合、概括和抽象以形成更大、更加抽象的標記（tokens）時，這樣的初始簡圖又被稱為完全的初始簡圖。

? ? 這也就是邊緣檢測之所以稱為圖像處理和機器視覺的基本問題的原因。邊緣檢測的直接目的是尋找未處理的初始簡圖。它通常尋找圖像中亮度變化明顯的點，當這些點位置相鄰且方向相近時，則構成了邊緣中的特殊邊緣-直線段。目前流行的直線檢測算法主要是霍夫變換，它的優勢是不受圖像旋轉的影響，易于進行幾何圖像的快速變換。基于霍夫變換的改進方法也很多，其中一個重要的方法是廣義霍夫變換，可以用來檢測任意形狀的曲線。?

最簡單的霍夫變換是在圖像中識別直線。在平面直角坐標系(x-y)中，一條直線可以用方程

表示。對于直線上一個確定的點(,)，有

這表示參數平面(k-b)中的一條直線。因此，圖像中的一個點對應參數平面中的一條正弦曲線，圖像中的一條直線對應參數平面中的一個點。對圖像上所有的點作霍夫變換，最終所要檢測的直線對應的一定是參數平面中直線相交最多的那個點。這樣就在圖像中檢測出了直線。在實際應用中，直線通常采用參數方程

.

類似的還有檢測線段、圓、圓弧、橢圓、矩形等的霍夫變換。

? ? ??廢話了這么多，終于開始回顧LSD了，使用LSD主要是在遙感圖像中幾何形狀明顯的目標進行檢測時用到。利用LSD，可以快速的檢測圖像中的直線段，然后根據目標的幾何特征設計快速算法，以快速確定疑似目標區域。

? ? ? LSD的核心是像素合并于誤差控制。利用合并像素來檢測直線段并不是什么新鮮的方法，但是合并像素的方法通常運算量較大。LSD號稱是能在線性時間（linear-time）內得到亞像素級準確度的直線段檢測算法。LSD雖然號稱不需人工設置任何參數，但是實際使用時，可以設置采樣率和判斷倆像素是否合并的方向差。我們知道，檢測圖像中的直線其實就是尋找圖像中梯度變化較大的像素。因此，梯度和圖像的level-line是LSD提及的兩個基本概念。LSD首先計算每一個像素與level-line的夾角以構成一個level-line場。然后，合并這個場里方向近似相同的像素，這樣可以得到一系列regions，這些 regions被稱為 line support regions。如下圖所示。

? ? 每一個line support region其實就是一組像素，它也是直線段（line segment）的候選。同時，對于這個line support region，我們可以觀察它的最小外接矩形。直觀上來講，當一組像素構成的區域，特別細長時，那么這組像素更加可能是直線段。基于此，作者還統計了line support region的最小外接矩形的主方向。line support region中的一個像素的level-line 角度與最小外接矩形的主方向的角度差在容忍度（tolerance）2τ內的話，那么這個點被稱作"aligned point"。作者統計最小外接矩形內的所有像素數和其內的alinedg points數，用來判定這個line support region是否是一個直線段。判定的準則使用的是“a contrario approach”和“Helmholtz principle”方法。在這里，aligned ?points的數量是我們感興趣的信息。因此作者考慮如下假設：aligned points越多，那么region越可能是直線段。對于一副圖像i和一個矩形r，記k(i,r)為aligned points的數量，n(r)為矩形r內的總像素數。那么，我們希望能夠看到:

? ? ? 其中，Ntest是所有要考慮的矩形的數量。PH0是針對 contrario model H0的一個概率。I是在H0模型下的隨機圖像。在這篇文章中，作者用H0的模型，主要有以下兩個屬性：

? ? ? ?（1）{LLA(j)}，其中j是像素，是一由一組隨機變量組成；（2）LLA(j)在[0,2π]上均勻分布。

? ? ? ?因此，判斷一個像素是不是aligned point可以記作概率：

? ? ? ? ? p =?τ/π

? ? ? ?這樣，再通過誤差控制，最終的直線段檢測算法如下：

? ? ?在上述算法中，還有兩個要點我們沒有解釋。一是line support region具體是怎么得到了，二是怎樣進行誤差控制的。

? ? 前面我們說過，line support region是通過合并方向近似相同的像素得到。其實在這里，這個合并的過程更多的是依賴于區域生長算法。對于一個level-line 場LLA，種子像素P，和容忍度?τ。我們 可以通過簡單的區域生長算法來得到line support region，具體的算法過程參考論文里給出的步驟吧。

? ? ?至于NFA（the number of false alarms）計算，作者使用如下公式計算：

? ?其中，N和M是采樣過后圖像的列和行，B(n,k,p)是一個二項分布。n依舊是矩形內所有像素數，k是矩形內的所有p-aligned point數。此處的p-aligned point是指和矩形的主方向在容忍度pπ下方向相同的像素。如果，那么可以認為結果有效。

? ? ? ? ?在實際使用作者的源碼時，可以調整lsd函數中的scale來調整圖像采樣率。此外，合并角度代碼里默認是22.5度。圖像越小，角度越小，得到的結果越少。不過當圖像采樣不同時，在同一位置可能得到差異特別大的直線段，這個暫時不知道是什么造成的。

? ? ? ?一個比較迷人的結果：

?

LSD:一種直線檢測算法簡介

原文地址：http://blog.csdn.net/carson2005/article/details/9326847

申明：本文是筆者在閱讀了相應的英文文獻后，翻譯整理所得，原文為：Rafael Grompone von Gioi, LSD: a Line Segment Detector

????LSD是一種直線檢測分割算法，它能在線性的時間內得出亞像素級精度的檢測結果。該算法被設計成可以在任何數字圖像上都無需參數調節。它可以自己控制誤檢的數量：平均而言，每張圖有一個誤檢。

相關知識介紹

LSD的目標在于檢測圖像中局部的直的輪廓。這也是我們稱之為直線分割的原因。輪廓是圖像中的某些特殊區域，在這些區域，圖像的灰度從黑到白或者從白到黑的劇烈變化。因此，梯度和level-line是兩個重要的感念，如下圖所示：

總結

以上是生活随笔為你收集整理的【转】 LSD（Line Segment Detector） 直线段检测算法学习~的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。