a Line Segment Detector
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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 马尔科夫随机场
- 下一篇: audio to text