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