- 相關(guān)推薦
基于最小二乘修正的隨機(jī)Hough變換直線檢測
摘要：利用Hough變換進(jìn)行直線檢測時(shí)，由于直線在參數(shù)空間中的映射容易受到鄰近目標(biāo)、噪聲以及本身非理想狀態(tài)的干擾，算法中的投票過程較易出現(xiàn)無效累積，進(jìn)而導(dǎo)致虛檢、漏檢及端點(diǎn)定位不準(zhǔn)等問題。針對傳統(tǒng)方法的上述缺陷，提出了一種基于ρθ域最小二乘擬合修正的隨機(jī)Hough變換的直線檢測方法。首先， 在隨機(jī)抽樣時(shí)利用像素-長度比值對抽樣的有效性進(jìn)行判定，剔除不在直線上的抽樣點(diǎn)對;然后， 對鄰域相關(guān)點(diǎn)進(jìn)行ρθ域的最小二乘擬合，得到修正后的直線參數(shù)用于累加投票，投票過程中設(shè)定累加閾值，通過檢測峰值點(diǎn)逐次檢出疑似長直線;最后， 通過設(shè)定斷裂閾值對每條長直線進(jìn)行篩選和分段，定位出直線段的端點(diǎn)。仿真實(shí)驗(yàn)表明，所提方法在投票時(shí)有效抑制了復(fù)雜環(huán)境對局部最大值的干擾，使直線檢測的準(zhǔn)確率得到顯著提升。
關(guān)鍵詞：直線檢測;隨機(jī)Hough變換;最小二乘法;參數(shù)空間;投票有效性
引言
在圖像處理和計(jì)算機(jī)視覺領(lǐng)域，目標(biāo)識(shí)別是一個(gè)重要的課題，而直線的檢測又是其中最為基本的內(nèi)容之一。直線檢測之前通常需要對圖像進(jìn)行預(yù)處理，如去噪、增強(qiáng)、分割、邊緣檢測等，將圖像轉(zhuǎn)換為只包含邊緣信息的二值圖像再進(jìn)行直線檢測[1-2]。圖像直線檢測的難點(diǎn)在于，既要正確捕獲直線目標(biāo)，又要保證一定的寬容度以適應(yīng)非理想直線的情形。
Hough變換(Hough Transform， HT)是處理直線檢測問題的一種經(jīng)典算法，在諸多領(lǐng)域得到了廣泛應(yīng)用[3-5]。它的主要思想是，在參數(shù)空間的離散化網(wǎng)格中，利用“多對一”映射將各個(gè)像素點(diǎn)映射到參數(shù)空間，然后通過累加“投票”得到共線的像素點(diǎn)在參數(shù)空間的映射，進(jìn)而得到圖像中直線的參數(shù)。這種方法為在參數(shù)域進(jìn)行直線檢測提供了新的思路，但實(shí)際應(yīng)用中由于非理想直線和復(fù)雜場景干擾，效果不佳。一方面圖像中的潛在直線往往因?yàn)樵肼暤母蓴_而偏離理想狀態(tài)，出現(xiàn)諸如局部彎曲或斷裂的現(xiàn)象，參數(shù)空間峰值點(diǎn)不容易被檢測到，導(dǎo)致漏檢;另一方面，潛在直線周邊的其他非直線目標(biāo)像素的存在，使參數(shù)空間相應(yīng)位置出現(xiàn)偽峰，導(dǎo)致虛檢。
利用較小采樣集合代替全點(diǎn)集的改進(jìn)方法取得了較好的效果，最早且有代表性的是Xu等[6]的隨機(jī)Hough變換(Randomized Hough Transform， RHT)和Kiryati等[7]的概率Hough變換(Probabilistic Hough Transform， PHT)，但因全局采樣而引入大量無效累積，復(fù)雜場景效果不佳。毛俊勇等[8]在所建立的點(diǎn)屬于某直線上不確定性度量概率模型基礎(chǔ)上，根據(jù)隨機(jī)選擇的兩點(diǎn)間直線參數(shù)，按照Bayesian法則用基于不確定度量的參數(shù)空間軟投票，但檢測算法的分辨率受到度量模型和投票網(wǎng)格的限制。Ji等[9]引入局部增強(qiáng)算子，通過增加參數(shù)空間中直線峰值和噪聲之間的差異，得到更準(zhǔn)確的局部最大值，但累加過程仍然基于標(biāo)準(zhǔn)Hough變換(Standard Hough Transform， SHT)，需要全局計(jì)算，效率不高。王競雪等[10]在Hough變換前采用相位編組(Phase Grouping)方法進(jìn)行邊緣跟蹤，降低了直線間干擾，但對多條直線相交的等復(fù)雜連通情形效果不理想。Lee等[11]和Chung等[12]采用多參數(shù)的離散Hough變換，在孤立直線檢測中比SHT具有更高檢測率，但多參數(shù)的引入導(dǎo)致了較大計(jì)算量。
RHT隨機(jī)選取點(diǎn)對，避免了傳統(tǒng)Hough變換“多對一”映射的缺陷，卻使得累積具有很大的盲目性，而且噪聲和互相干擾使得參數(shù)計(jì)算精度受到影響�；诖�，本文提出了一種在參數(shù)空間進(jìn)行最小二乘修正的隨機(jī)Hough變換方法。首先進(jìn)行邊緣點(diǎn)隨機(jī)抽樣，對抽樣兩點(diǎn)之間是否可能存在直線進(jìn)行判斷并篩選; 然后對其所有鄰域相關(guān)點(diǎn)進(jìn)行ρθ域的最小二乘擬合，根據(jù)修正后的直線參數(shù)在累加網(wǎng)格進(jìn)行累加，通過搜索累加最大值計(jì)算得到檢測直線參數(shù); 最后通過斷裂-尺度閾值定位出線段的端點(diǎn)，完成直線段的檢測。這種方法有效地減少了隨機(jī)Hough變換的無效累加，提高了累加效率，并避免了在參數(shù)空間累加網(wǎng)格中搜索局部最大值的過程，有效減少了直線檢測的誤檢和漏檢，得到定位準(zhǔn)確的直線段。
一、基于最小二乘修正的RHT算法
1.1隨機(jī)Hough變換
Hough變換是一種經(jīng)典的利用參數(shù)空間的累加統(tǒng)計(jì)來完成圖像空間檢測任務(wù)的方法。它將圖像xy空間的點(diǎn)映射為參數(shù)ρθ空間的一條曲線，而將圖像空間的一條給定形狀的曲線映射為參數(shù)空間的一個(gè)點(diǎn)，圖像空間曲線上的點(diǎn)在參數(shù)空間的像經(jīng)過累加，就得到了一個(gè)累加權(quán)值較高的點(diǎn)，反向映射得到前面所述的圖像空間的曲線。
Hough變換的基本原理如圖1所示，設(shè)L是圖像空間的直線，在圖像空間直角坐標(biāo)系下的方程為：
ρ=x cos θ+y sin θ(1)
式中：ρ為直角坐標(biāo)系原點(diǎn)到直線L的距離，θ為直線L與y軸的夾角。點(diǎn)P(θ， ρ)就是直線L在參數(shù)ρθ空間的映射。標(biāo)準(zhǔn)的Hough變換針對每個(gè)前景像素進(jìn)行映射，其計(jì)算復(fù)雜度比較高，不適合實(shí)時(shí)處理。因此，一種基于概率統(tǒng)計(jì)的隨機(jī)Hough變換開始應(yīng)用于數(shù)字圖像處理領(lǐng)域。
圖片
圖1直線在參數(shù)空間的映射
隨機(jī)Hough變換(RHT)的基本思想是在圖像空間的前景像素(通常為邊緣點(diǎn))中隨機(jī)選取兩個(gè)點(diǎn)，將通過這兩點(diǎn)的直線映射到參數(shù)空間。通過這種多到一的映射，RHT避免了標(biāo)準(zhǔn)Hough變換(SHT)中一到多映射所需的龐大計(jì)算量。
設(shè)邊緣像素點(diǎn)集Γ={P(x，y)}，從中隨機(jī)選取兩個(gè)相異點(diǎn)P1(x1，y1)、P2(x2，y2)，得到通過這兩點(diǎn)的唯一直線L12，且其參數(shù)可依次由式(2)、(3)計(jì)算得到。
θ12=tan-1y1-y2x2-x1(2
ρ12=y1+y22 sin θ12+x1+x22 cos θ12(3 將該組參數(shù)(θ12， ρ12)作為索引進(jìn)行累加，即令該參數(shù)所屬的網(wǎng)格的累加值遞加一。經(jīng)過一定數(shù)目的累加之后，在網(wǎng)格累加值中搜索局部最大值，這些網(wǎng)格的參數(shù)(θmax， ρmax)對應(yīng)的直線就構(gòu)成了一個(gè)直線集合，它包含但不限于實(shí)際圖像中的直線L，需要進(jìn)行進(jìn)一步篩選。
點(diǎn)集Γ中的邊緣點(diǎn)Pk到該直線L的距離為：
disk=ρ-xk cos θ-yk sin θ(4
通過判斷點(diǎn)到直線的距離是否小于某一閾值δ，距離小于該閾值的點(diǎn)就認(rèn)為從屬于該直線L，構(gòu)成集合ΓL，如圖2所示。另外，事先確定一個(gè)數(shù)目門限Nth，如果點(diǎn)集內(nèi)的點(diǎn)的個(gè)數(shù)大于Nth，則直線L是實(shí)際直線;否則不為實(shí)際直線，將其排除。這樣就能判斷直線L在距離閾值δ下是否實(shí)際存在。排除后剩余的直線就是RHT檢測到的直線。
圖片
圖2通過δ閾值篩選直線示意圖
傳統(tǒng)的RHT有效降低了傳統(tǒng)HT的計(jì)算復(fù)雜度，但仍然存在無效累積的問題，給ρθ域的局部最大值搜索帶來較大噪聲，在復(fù)雜場景下易檢測出虛假直線目標(biāo)，或漏檢實(shí)際直線目標(biāo)。
1.2ρθ域的最小二乘擬合
傳統(tǒng)的RHT方法為克服虛檢、漏檢提供了思路，本文在RHT基礎(chǔ)上利用距離閾值中的點(diǎn)進(jìn)行參數(shù)域的最小二乘修正。
最小二乘法(Least Square Method， LSM)是一種經(jīng)典的優(yōu)化手段。傳統(tǒng)的最小二乘直線擬合采用直線的斜率和截距兩個(gè)參數(shù)，優(yōu)化的目標(biāo)函數(shù)是觀測點(diǎn)到直線豎直距離的二次方，亦即y方向上坐標(biāo)差值的二次方，這使得優(yōu)化過程嚴(yán)重依賴坐標(biāo)系。因此本文采用在參數(shù)域的直接最小二乘擬合。
圖像空間的直線L可由式(1)表示，對于空間一點(diǎn)Pk(xk，yk)，Pi到直線L的距離可以由式(4)表示。于是，基于最小二乘準(zhǔn)則的直線擬合也可描述為以下約束優(yōu)化問題：
min f=∑nk=1(ρ-yk sin θ-xk cos θ)2(5)
s.t. -π/2 < θ ≤ π/2
或其等效約束優(yōu)化問題：
min g(a，b，c)=∑nk=1(axk+byk+c)2(6)
s.t. a2+b2=1
式(5)所描述的優(yōu)化問題，其優(yōu)化函數(shù)是一個(gè)擬凸函數(shù)，在非邊界處有全局最小值，因此求偏導(dǎo)化簡可得：
tan (2θop)=2∑ni=1∑nj=1xiyj-n∑ni=1xiyi∑ni=1∑nj=1(xixj-yiyj)-n∑ni=1(x2i-y2i)
ρop=1nsin θop∑ni=1yi+cos θop∑ni=1xi
f(θop，ρop)≤f(θ，ρ)
-π/2< θop <π/2(7)
式中：θop、 ρop為最優(yōu)解; n為參與擬合的樣本點(diǎn)個(gè)數(shù)。
實(shí)際求解過程中會(huì)遇到反正切函數(shù)值對應(yīng)多解的問題。解決方法是先將可能的兩組最優(yōu)θop求解出來，再代入優(yōu)化函數(shù)通過判斷f是否達(dá)到最小來得到唯一的最優(yōu)解。
這里對1.1節(jié)得到δ鄰域點(diǎn)集ΓL中所有點(diǎn)在參數(shù)域進(jìn)行最小二乘擬合，通過求解降低偏差較大噪聲點(diǎn)的干擾，得到較為準(zhǔn)確的直線參數(shù)參與投票。
1.3提出的直線檢測算法流程
正如第1.1節(jié)所述，標(biāo)準(zhǔn)RHT在參數(shù)累加時(shí)，不考慮參數(shù)的有效性，將通過兩個(gè)沒有關(guān)聯(lián)的點(diǎn)的直線參數(shù)作為一次累加，這樣既降低了累加的效率，同時(shí)也給ρθ域的局部最大值搜索引入噪聲。
本文在標(biāo)準(zhǔn)RHT的基礎(chǔ)上，在累加之前通過兩點(diǎn)連線的鄰域內(nèi)點(diǎn)的密度判斷當(dāng)前累加參數(shù)的有效性，并通過ρθ域的最小二乘擬合鄰域內(nèi)點(diǎn)得到累加參數(shù)。當(dāng)累加網(wǎng)格的最大值等于累加閾值時(shí)，記錄這個(gè)最大值并根據(jù)網(wǎng)格分辨率解算出一條直線，將這條直線從圖像中去除，然后重新進(jìn)行累加。這個(gè)過程重復(fù)直到某次有效累加達(dá)到最大累加次數(shù)或者無效累加達(dá)到最大失敗次數(shù)為止。
將本文方法與標(biāo)準(zhǔn)Hough變換(SHT)在參數(shù)域的比較映射結(jié)果。圖3(a)是包含兩條非理想直線的二值圖像。圖3(b)、(c)分別是標(biāo)準(zhǔn)Hough變換及本文方法的參數(shù)域映射。圖3(d)～(f)是(a)中添加了短線噪聲之后的相應(yīng)結(jié)果。標(biāo)準(zhǔn)Hough變換映射的峰有明顯的“拖尾”，且隨著短線噪聲的加入更加顯著，甚至出現(xiàn)了多個(gè)偽峰。而提出的方法映射的峰能量集中，即使增加短線噪聲干擾也沒有“拖尾”和偽峰出現(xiàn)。這與前面所作的理論分析結(jié)論相一致�？梢钥闯�，提出方法的累積修正對提高參數(shù)域的局部最大值搜索精度，進(jìn)而降低直線檢測虛檢、漏檢率，有重大意義。
假設(shè)已給定累加閾值A(chǔ)max、最大累加次數(shù)Nmax和最大失敗次數(shù)Fmax，以及直線寬容度閾值(距離閾值)δ和連線內(nèi)點(diǎn)比例閾值Pth，則算法的詳細(xì)步驟為：
步驟1初始化累加網(wǎng)格，累加次數(shù)n和失敗次數(shù)f置零。
步驟2從二值圖像所有邊緣點(diǎn)中隨機(jī)抽取兩個(gè)。
步驟3考查選取的兩點(diǎn)間連線的δ鄰域內(nèi)邊緣點(diǎn)個(gè)數(shù)與兩點(diǎn)之間距離的比值： 若比值大于Pth，則累加次數(shù)n加1并跳到步驟4; 否則失敗次數(shù)f加1，跳到步驟5。
步驟4對δ鄰域內(nèi)所有點(diǎn)進(jìn)行最小二乘擬合，計(jì)算直線參數(shù) (ρ，θ)，并將其對應(yīng)的網(wǎng)格累加值加1。若累加網(wǎng)格的最大值等于Amax，則記錄直線參數(shù)，并直線δ鄰域內(nèi)邊緣點(diǎn)從邊緣點(diǎn)集合去除，跳到步驟1;否則，繼續(xù)步驟5。
步驟5若累加次數(shù)n等于Nmax或失敗次數(shù)f等于Fmax，則算法結(jié)束。
二、斷裂尺度閾值定位線段
改進(jìn)的RHT得到的是若干條長直線貫穿整幅圖像。實(shí)際應(yīng)用中，定位出具體直線段的兩個(gè)端點(diǎn)才具有更大的實(shí)用價(jià)值。本文提出用斷裂尺度閾值來獲取直線端點(diǎn)的位置。
將檢測到的長直線δ鄰域內(nèi)的邊緣點(diǎn)垂直投影到直線上，計(jì)算出投影點(diǎn)在直線上的相對位置，并按這個(gè)位置將邊緣點(diǎn)進(jìn)行排序。根據(jù)設(shè)定的斷裂閾值Thgap和最短尺度閾值Thseg，先利用相對位置間隔大于Thgap的條件，將鄰域邊緣點(diǎn)劃分到幾條直線段中，然后將線段長度低于Thseg的線段作為短線噪聲剔除。
經(jīng)過斷裂尺度閾值分段的直線段，既能避免因引入短線噪聲而出現(xiàn)虛假線段，也有較好的抗斷裂性能，防止出現(xiàn)過分割。
三、仿真實(shí)驗(yàn)結(jié)果
3.1檢測結(jié)果評價(jià)指標(biāo)
為了對實(shí)驗(yàn)結(jié)果進(jìn)行量化，需要確定具體評價(jià)指標(biāo)。本文采用漏檢率和虛檢率表征檢測準(zhǔn)確度。
假設(shè)實(shí)驗(yàn)原圖中有Nr條直線段，經(jīng)過檢測，得到的Nd條標(biāo)注，漏檢記為Nm條，虛檢記為Ne條，規(guī)定如下：
1)對于一條標(biāo)注，標(biāo)注直線段與原直線段走向大于2°的，或夾角小于等于2°但標(biāo)注線段被原直線段覆蓋長度小于50%，認(rèn)為錯(cuò)檢(虛檢)，Ne加1;
2)對于一條原始直線段，原直線段與標(biāo)注直線段走向大于2°的，或夾角小于等于2°但標(biāo)注線段共同覆蓋原直線段長度小于80%，認(rèn)為漏檢，Nm加1。
于是仿真實(shí)驗(yàn)的漏檢率ηm和虛檢率ηe可以分別定義為：
ηm=Nm/Nr
ηe=Ne/Nd (8
直線檢測結(jié)果的精度可用上述指標(biāo)進(jìn)行衡量，漏檢率和虛檢率越低，直線檢測的精度越高。
3.2結(jié)果和評價(jià)
圖4(a)是一幅512×512像素的仿真圖像，其中有13條長短不同且部分存在相交、平行或共線的近似直線段，同時(shí)添加40條隨機(jī)短線噪聲。
圖片
圖4仿真實(shí)驗(yàn)結(jié)果
對仿真圖像分別采用標(biāo)準(zhǔn)Hough變換、隨機(jī)Hough變換和本文方法進(jìn)行直線提取，其中直線斷裂閾值設(shè)為20像素，最短檢測直線閾值設(shè)為30像素。圖中檢測到的直線段兩端分別用“×”符號表示。
對比采用同樣參數(shù)設(shè)置的三組結(jié)果，圖4 (b)標(biāo)準(zhǔn)Hough變換的檢測結(jié)果有顯著漏檢產(chǎn)生，主要集中于直線較短或彎折較為明顯的地方，即使檢測到的直線段，也存在端點(diǎn)定位不準(zhǔn)的情況。SHT對于尺度較小的直線目標(biāo)檢測性能較差，并且易受到直線彎折、短線噪聲等的影響。
圖4(c)隨機(jī)Hough變換的直線虛檢率略有上升，但漏檢率明顯低于標(biāo)準(zhǔn)Hough變換，原圖的每條線段目標(biāo)都能被部分檢出;但線段的端點(diǎn)仍然不夠準(zhǔn)確，而且存在同一線段目標(biāo)被檢出為多條斷開短線目標(biāo)，這些問題在右側(cè)平行線處尤其顯著。這組結(jié)果表明，RHT雖然在漏檢性能上優(yōu)于SHT，但難以解決鄰近平行線目標(biāo)和直線段目標(biāo)過度分段問題。
圖4(d)本文方法精確檢出原圖存在的每條直線，沒有出現(xiàn)虛檢漏檢的情況，并且每條直線段的端點(diǎn)定位準(zhǔn)確，尤其在面對右側(cè)兩組平行線交叉這種復(fù)雜的情況時(shí)，仍然沒有出現(xiàn)SHT、RHT存在的漏檢、虛檢、過度分段等問題，保持了優(yōu)異的檢測性能。
檢測結(jié)果的漏檢虛檢指標(biāo)如表1所示。
繼續(xù)探究三種方法在不同噪聲條件下的檢測性能。仍然采用上述直線，但隨機(jī)添加不同數(shù)目的短線噪聲，依次得到圖5中兩種指標(biāo)的變化曲線。從圖中可以看出，三種方法的檢測準(zhǔn)確度大體上隨著短線擾動(dòng)數(shù)目的增加而下降;對比已有兩種算法，SHT的抗虛檢性能較好而RHT的抗漏檢性能較好，并且兩種方法都隨噪聲變化出現(xiàn)較大波動(dòng);本文方法在漏檢、虛檢性能方面都是要優(yōu)于兩種已有算法的，并且其檢測性能并沒有隨噪聲的變化發(fā)生明顯波動(dòng)，有著較好的穩(wěn)定性和魯棒性。
圖片
圖5在不同短線噪聲影響下的檢測結(jié)果
四、結(jié)語
本文提出通過參數(shù)域的最小二乘修正來改進(jìn)隨機(jī)Hough變換直線檢測：直接在參數(shù)空間引入最小二乘擬合方法，并對隨機(jī)Hough變換的投票步驟提出改進(jìn)，最后在提取長直線的基礎(chǔ)上引入斷裂尺度閾值確定線段端點(diǎn)。
仿真圖像的直線提取實(shí)驗(yàn)可以證明，本文提出的基于最小二乘估計(jì)修正改進(jìn)的隨機(jī)Hough算法可以有效地改進(jìn)標(biāo)準(zhǔn)Hough變換以及隨機(jī)Hough變換的固有缺陷。經(jīng)過有效性篩選和最小二乘擬合之后的累加效率更高，噪聲像素和鄰近直線像素的干擾更小，虛檢率和漏檢率顯著降低;同時(shí)，對直線形變的寬容度更好，直線端點(diǎn)的定位性能更加優(yōu)越。
參考文獻(xiàn)：
[1]DONG J， YANG X， YU Q. Fast line segment detection based on edge connection[J]. Acta Optica Sinica， 2013， 33(3)：213-220. (董晶， 楊夏， 于起峰. 基于邊緣連接的快速直線段檢測算法[J]. 光學(xué)學(xué)報(bào)， 2013， 33(3)：213-220.)
【基于最小二乘修正的隨機(jī)Hough變換直線檢測】相關(guān)文章：
基于最小二乘模型的Bayes參數(shù)辨識(shí)方法03-07
基于小波變換的諧波檢測法03-28
基于FPGA的快速傅立葉變換03-19
一種基于分?jǐn)?shù)階傅立葉變換的LFM信號檢測簡化方法11-22
基于自相關(guān)平方函數(shù)與小波變換結(jié)合的帶噪語音基音檢測03-07
基于最小因子定律的時(shí)間營銷法03-24
基于IHS變換的遙感影像融合方法研究11-22