FROM:http://blog.csdn.net/polly_yang/article/details/10085401

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

? ? ? ? ? p =?τ/π

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

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

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

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

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

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

? ? ? ?一個比較迷人的結(jié)果：

?

總結(jié)

以上是生活随笔為你收集整理的a Line Segment Detector的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。