基于最小二乘修正的隨機Hough變換直線(xiàn)檢測

　　摘要：利用Hough變換進(jìn)行直線(xiàn)檢測時(shí)，由于直線(xiàn)在參數空間中的映射容易受到鄰近目標、噪聲以及本身非理想狀態(tài)的干擾，算法中的投票過(guò)程較易出現無(wú)效累積，進(jìn)而導致虛檢、漏檢及端點(diǎn)定位不準等問(wèn)題。針對傳統方法的上述缺陷，提出了一種基于ρθ域最小二乘擬合修正的隨機Hough變換的直線(xiàn)檢測方法。首先， 在隨機抽樣時(shí)利用像素-長(cháng)度比值對抽樣的有效性進(jìn)行判定，剔除不在直線(xiàn)上的抽樣點(diǎn)對;然后， 對鄰域相關(guān)點(diǎn)進(jìn)行ρθ域的最小二乘擬合，得到修正后的直線(xiàn)參數用于累加投票，投票過(guò)程中設定累加閾值，通過(guò)檢測峰值點(diǎn)逐次檢出疑似長(cháng)直線(xiàn);最后， 通過(guò)設定斷裂閾值對每條長(cháng)直線(xiàn)進(jìn)行篩選和分段，定位出直線(xiàn)段的端點(diǎn)。仿真實(shí)驗表明，所提方法在投票時(shí)有效抑制了復雜環(huán)境對局部最大值的干擾，使直線(xiàn)檢測的準確率得到顯著(zhù)提升。

　　關(guān)鍵詞：直線(xiàn)檢測;隨機Hough變換;最小二乘法;參數空間;投票有效性

　　引言

　　在圖像處理和計算機視覺(jué)領(lǐng)域，目標識別是一個(gè)重要的課題，而直線(xiàn)的檢測又是其中最為基本的內容之一。直線(xiàn)檢測之前通常需要對圖像進(jìn)行預處理，如去噪、增強、分割、邊緣檢測等，將圖像轉換為只包含邊緣信息的二值圖像再進(jìn)行直線(xiàn)檢測[1-2]。圖像直線(xiàn)檢測的難點(diǎn)在于，既要正確捕獲直線(xiàn)目標，又要保證一定的寬容度以適應非理想直線(xiàn)的情形。

　　Hough變換(Hough Transform， HT)是處理直線(xiàn)檢測問(wèn)題的一種經(jīng)典算法，在諸多領(lǐng)域得到了廣泛應用[3-5]。它的主要思想是，在參數空間的離散化網(wǎng)格中，利用“多對一”映射將各個(gè)像素點(diǎn)映射到參數空間，然后通過(guò)累加“投票”得到共線(xiàn)的像素點(diǎn)在參數空間的映射，進(jìn)而得到圖像中直線(xiàn)的參數。這種方法為在參數域進(jìn)行直線(xiàn)檢測提供了新的思路，但實(shí)際應用中由于非理想直線(xiàn)和復雜場(chǎng)景干擾，效果不佳。一方面圖像中的潛在直線(xiàn)往往因為噪聲的干擾而偏離理想狀態(tài)，出現諸如局部彎曲或斷裂的現象，參數空間峰值點(diǎn)不容易被檢測到，導致漏檢;另一方面，潛在直線(xiàn)周邊的其他非直線(xiàn)目標像素的存在，使參數空間相應位置出現偽峰，導致虛檢。

　　利用較小采樣集合代替全點(diǎn)集的改進(jìn)方法取得了較好的效果，最早且有代表性的是Xu等[6]的隨機Hough變換(Randomized Hough Transform， RHT)和Kiryati等[7]的概率Hough變換(Probabilistic Hough Transform， PHT)，但因全局采樣而引入大量無(wú)效累積，復雜場(chǎng)景效果不佳。毛俊勇等[8]在所建立的點(diǎn)屬于某直線(xiàn)上不確定性度量概率模型基礎上，根據隨機選擇的兩點(diǎn)間直線(xiàn)參數，按照Bayesian法則用基于不確定度量的參數空間軟投票，但檢測算法的分辨率受到度量模型和投票網(wǎng)格的限制。Ji等[9]引入局部增強算子，通過(guò)增加參數空間中直線(xiàn)峰值和噪聲之間的差異，得到更準確的局部最大值，但累加過(guò)程仍然基于標準Hough變換(Standard Hough Transform， SHT)，需要全局計算，效率不高。王競雪等[10]在Hough變換前采用相位編組(Phase Grouping)方法進(jìn)行邊緣跟蹤，降低了直線(xiàn)間干擾，但對多條直線(xiàn)相交的等復雜連通情形效果不理想。Lee等[11]和Chung等[12]采用多參數的離散Hough變換，在孤立直線(xiàn)檢測中比SHT具有更高檢測率，但多參數的引入導致了較大計算量。

　　RHT隨機選取點(diǎn)對，避免了傳統Hough變換“多對一”映射的缺陷，卻使得累積具有很大的盲目性，而且噪聲和互相干擾使得參數計算精度受到影響�；�于此，本文提出了一種在參數空間進(jìn)行最小二乘修正的隨機Hough變換方法。首先進(jìn)行邊緣點(diǎn)隨機抽樣，對抽樣兩點(diǎn)之間是否可能存在直線(xiàn)進(jìn)行判斷并篩選; 然后對其所有鄰域相關(guān)點(diǎn)進(jìn)行ρθ域的最小二乘擬合，根據修正后的直線(xiàn)參數在累加網(wǎng)格進(jìn)行累加，通過(guò)搜索累加最大值計算得到檢測直線(xiàn)參數; 最后通過(guò)斷裂-尺度閾值定位出線(xiàn)段的端點(diǎn)，完成直線(xiàn)段的檢測。這種方法有效地減少了隨機Hough變換的無(wú)效累加，提高了累加效率，并避免了在參數空間累加網(wǎng)格中搜索局部最大值的過(guò)程，有效減少了直線(xiàn)檢測的誤檢和漏檢，得到定位準確的直線(xiàn)段。

　　一、基于最小二乘修正的RHT算法

　　1.1隨機Hough變換

　　Hough變換是一種經(jīng)典的利用參數空間的累加統計來(lái)完成圖像空間檢測任務(wù)的方法。它將圖像xy空間的點(diǎn)映射為參數ρθ空間的一條曲線(xiàn)，而將圖像空間的一條給定形狀的曲線(xiàn)映射為參數空間的一個(gè)點(diǎn)，圖像空間曲線(xiàn)上的點(diǎn)在參數空間的像經(jīng)過(guò)累加，就得到了一個(gè)累加權值較高的點(diǎn)，反向映射得到前面所述的圖像空間的曲線(xiàn)。

　　Hough變換的基本原理如圖1所示，設L是圖像空間的直線(xiàn)，在圖像空間直角坐標系下的方程為：

　　ρ=x cos θ+y sin θ(1)

　　式中：ρ為直角坐標系原點(diǎn)到直線(xiàn)L的距離，θ為直線(xiàn)L與y軸的夾角。點(diǎn)P(θ， ρ)就是直線(xiàn)L在參數ρθ空間的映射。標準的Hough變換針對每個(gè)前景像素進(jìn)行映射，其計算復雜度比較高，不適合實(shí)時(shí)處理。因此，一種基于概率統計的隨機Hough變換開(kāi)始應用于數字圖像處理領(lǐng)域。

　　圖片

　　圖1直線(xiàn)在參數空間的映射

　　隨機Hough變換(RHT)的基本思想是在圖像空間的前景像素(通常為邊緣點(diǎn))中隨機選取兩個(gè)點(diǎn)，將通過(guò)這兩點(diǎn)的直線(xiàn)映射到參數空間。通過(guò)這種多到一的映射，RHT避免了標準Hough變換(SHT)中一到多映射所需的龐大計算量。

　　設邊緣像素點(diǎn)集Γ={P(x，y)}，從中隨機選取兩個(gè)相異點(diǎn)P1(x1，y1)、P2(x2，y2)，得到通過(guò)這兩點(diǎn)的唯一直線(xiàn)L12，且其參數可依次由式(2)、(3)計算得到。

　　θ12=tan-1y1-y2x2-x1(2

　　ρ12=y1+y22 sin θ12+x1+x22 cos θ12(3 　　將該組參數(θ12， ρ12)作為索引進(jìn)行累加，即令該參數所屬的網(wǎng)格的累加值遞加一。經(jīng)過(guò)一定數目的累加之后，在網(wǎng)格累加值中搜索局部最大值，這些網(wǎng)格的參數(θmax， ρmax)對應的直線(xiàn)就構成了一個(gè)直線(xiàn)集合，它包含但不限于實(shí)際圖像中的直線(xiàn)L，需要進(jìn)行進(jìn)一步篩選。

　　點(diǎn)集Γ中的邊緣點(diǎn)Pk到該直線(xiàn)L的距離為：

　　disk=ρ-xk cos θ-yk sin θ(4

　　通過(guò)判斷點(diǎn)到直線(xiàn)的距離是否小于某一閾值δ，距離小于該閾值的點(diǎn)就認為從屬于該直線(xiàn)L，構成集合ΓL，如圖2所示。另外，事先確定一個(gè)數目門(mén)限Nth，如果點(diǎn)集內的點(diǎn)的個(gè)數大于Nth，則直線(xiàn)L是實(shí)際直線(xiàn);否則不為實(shí)際直線(xiàn)，將其排除。這樣就能判斷直線(xiàn)L在距離閾值δ下是否實(shí)際存在。排除后剩余的直線(xiàn)就是RHT檢測到的直線(xiàn)。

　　圖片

　　圖2通過(guò)δ閾值篩選直線(xiàn)示意圖

　　傳統的RHT有效降低了傳統HT的計算復雜度，但仍然存在無(wú)效累積的問(wèn)題，給ρθ域的局部最大值搜索帶來(lái)較大噪聲，在復雜場(chǎng)景下易檢測出虛假直線(xiàn)目標，或漏檢實(shí)際直線(xiàn)目標。

　　1.2ρθ域的最小二乘擬合

　　傳統的RHT方法為克服虛檢、漏檢提供了思路，本文在RHT基礎上利用距離閾值中的點(diǎn)進(jìn)行參數域的最小二乘修正。

　　最小二乘法(Least Square Method， LSM)是一種經(jīng)典的優(yōu)化手段。傳統的最小二乘直線(xiàn)擬合采用直線(xiàn)的斜率和截距兩個(gè)參數，優(yōu)化的目標函數是觀(guān)測點(diǎn)到直線(xiàn)豎直距離的二次方，亦即y方向上坐標差值的二次方，這使得優(yōu)化過(guò)程嚴重依賴(lài)坐標系。因此本文采用在參數域的直接最小二乘擬合。

　　圖像空間的直線(xiàn)L可由式(1)表示，對于空間一點(diǎn)Pk(xk，yk)，Pi到直線(xiàn)L的距離可以由式(4)表示。于是，基于最小二乘準則的直線(xiàn)擬合也可描述為以下約束優(yōu)化問(wèn)題：

　　min f=∑nk=1(ρ-yk sin θ-xk cos θ)2(5)

　　s.t. -π/2 < θ ≤ π/2

　　或其等效約束優(yōu)化問(wèn)題：

　　min g(a，b，c)=∑nk=1(axk+byk+c)2(6)

　　s.t. a2+b2=1

　　式(5)所描述的優(yōu)化問(wèn)題，其優(yōu)化函數是一個(gè)擬凸函數，在非邊界處有全局最小值，因此求偏導化簡(jiǎn)可得：

　　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í)際求解過(guò)程中會(huì )遇到反正切函數值對應多解的問(wèn)題。解決方法是先將可能的兩組最優(yōu)θop求解出來(lái)，再代入優(yōu)化函數通過(guò)判斷f是否達到最小來(lái)得到唯一的最優(yōu)解。

　　這里對1.1節得到δ鄰域點(diǎn)集ΓL中所有點(diǎn)在參數域進(jìn)行最小二乘擬合，通過(guò)求解降低偏差較大噪聲點(diǎn)的干擾，得到較為準確的直線(xiàn)參數參與投票。

　　1.3提出的直線(xiàn)檢測算法流程

　　正如第1.1節所述，標準RHT在參數累加時(shí)，不考慮參數的有效性，將通過(guò)兩個(gè)沒(méi)有關(guān)聯(lián)的點(diǎn)的直線(xiàn)參數作為一次累加，這樣既降低了累加的效率，同時(shí)也給ρθ域的局部最大值搜索引入噪聲。

　　本文在標準RHT的基礎上，在累加之前通過(guò)兩點(diǎn)連線(xiàn)的鄰域內點(diǎn)的密度判斷當前累加參數的有效性，并通過(guò)ρθ域的最小二乘擬合鄰域內點(diǎn)得到累加參數。當累加網(wǎng)格的最大值等于累加閾值時(shí)，記錄這個(gè)最大值并根據網(wǎng)格分辨率解算出一條直線(xiàn)，將這條直線(xiàn)從圖像中去除，然后重新進(jìn)行累加。這個(gè)過(guò)程重復直到某次有效累加達到最大累加次數或者無(wú)效累加達到最大失敗次數為止。

　　將本文方法與標準Hough變換(SHT)在參數域的比較映射結果。圖3(a)是包含兩條非理想直線(xiàn)的二值圖像。圖3(b)、(c)分別是標準Hough變換及本文方法的參數域映射。圖3(d)～(f)是(a)中添加了短線(xiàn)噪聲之后的相應結果。標準Hough變換映射的峰有明顯的“拖尾”，且隨著(zhù)短線(xiàn)噪聲的加入更加顯著(zhù)，甚至出現了多個(gè)偽峰。而提出的方法映射的峰能量集中，即使增加短線(xiàn)噪聲干擾也沒(méi)有“拖尾”和偽峰出現。這與前面所作的理論分析結論相一致�？梢钥闯�，提出方法的累積修正對提高參數域的局部最大值搜索精度，進(jìn)而降低直線(xiàn)檢測虛檢、漏檢率，有重大意義。

　　假設已給定累加閾值Amax、最大累加次數Nmax和最大失敗次數Fmax，以及直線(xiàn)寬容度閾值(距離閾值)δ和連線(xiàn)內點(diǎn)比例閾值Pth，則算法的詳細步驟為：

　　步驟1初始化累加網(wǎng)格，累加次數n和失敗次數f置零。

　　步驟2從二值圖像所有邊緣點(diǎn)中隨機抽取兩個(gè)。

　　步驟3考查選取的兩點(diǎn)間連線(xiàn)的δ鄰域內邊緣點(diǎn)個(gè)數與兩點(diǎn)之間距離的比值： 若比值大于Pth，則累加次數n加1并跳到步驟4; 否則失敗次數f加1，跳到步驟5。

　　步驟4對δ鄰域內所有點(diǎn)進(jìn)行最小二乘擬合，計算直線(xiàn)參數 (ρ，θ)，并將其對應的網(wǎng)格累加值加1。若累加網(wǎng)格的最大值等于A(yíng)max，則記錄直線(xiàn)參數，并直線(xiàn)δ鄰域內邊緣點(diǎn)從邊緣點(diǎn)集合去除，跳到步驟1;否則，繼續步驟5。

　　步驟5若累加次數n等于Nmax或失敗次數f等于Fmax，則算法結束。

　　二、斷裂尺度閾值定位線(xiàn)段

　　改進(jìn)的RHT得到的是若干條長(cháng)直線(xiàn)貫穿整幅圖像。實(shí)際應用中，定位出具體直線(xiàn)段的兩個(gè)端點(diǎn)才具有更大的實(shí)用價(jià)值。本文提出用斷裂尺度閾值來(lái)獲取直線(xiàn)端點(diǎn)的位置。

　　將檢測到的長(cháng)直線(xiàn)δ鄰域內的邊緣點(diǎn)垂直投影到直線(xiàn)上，計算出投影點(diǎn)在直線(xiàn)上的相對位置，并按這個(gè)位置將邊緣點(diǎn)進(jìn)行排序。根據設定的斷裂閾值Thgap和最短尺度閾值Thseg，先利用相對位置間隔大于Thgap的條件，將鄰域邊緣點(diǎn)劃分到幾條直線(xiàn)段中，然后將線(xiàn)段長(cháng)度低于Thseg的線(xiàn)段作為短線(xiàn)噪聲剔除。

　　經(jīng)過(guò)斷裂尺度閾值分段的直線(xiàn)段，既能避免因引入短線(xiàn)噪聲而出現虛假線(xiàn)段，也有較好的抗斷裂性能，防止出現過(guò)分割。

　　三、仿真實(shí)驗結果

　　3.1檢測結果評價(jià)指標

　　為了對實(shí)驗結果進(jìn)行量化，需要確定具體評價(jià)指標。本文采用漏檢率和虛檢率表征檢測準確度。

　　假設實(shí)驗原圖中有Nr條直線(xiàn)段，經(jīng)過(guò)檢測，得到的Nd條標注，漏檢記為Nm條，虛檢記為Ne條，規定如下：

　　1)對于一條標注，標注直線(xiàn)段與原直線(xiàn)段走向大于2°的，或夾角小于等于2°但標注線(xiàn)段被原直線(xiàn)段覆蓋長(cháng)度小于50%，認為錯檢(虛檢)，Ne加1;

　　2)對于一條原始直線(xiàn)段，原直線(xiàn)段與標注直線(xiàn)段走向大于2°的，或夾角小于等于2°但標注線(xiàn)段共同覆蓋原直線(xiàn)段長(cháng)度小于80%，認為漏檢，Nm加1。

　　于是仿真實(shí)驗的漏檢率ηm和虛檢率ηe可以分別定義為：

　　ηm=Nm/Nr

　　ηe=Ne/Nd (8

　　直線(xiàn)檢測結果的精度可用上述指標進(jìn)行衡量，漏檢率和虛檢率越低，直線(xiàn)檢測的精度越高。

　　3.2結果和評價(jià)

　　圖4(a)是一幅512×512像素的仿真圖像，其中有13條長(cháng)短不同且部分存在相交、平行或共線(xiàn)的近似直線(xiàn)段，同時(shí)添加40條隨機短線(xiàn)噪聲。

　　圖片

　　圖4仿真實(shí)驗結果

　　對仿真圖像分別采用標準Hough變換、隨機Hough變換和本文方法進(jìn)行直線(xiàn)提取，其中直線(xiàn)斷裂閾值設為20像素，最短檢測直線(xiàn)閾值設為30像素。圖中檢測到的直線(xiàn)段兩端分別用“×”符號表示。

　　對比采用同樣參數設置的三組結果，圖4 (b)標準Hough變換的檢測結果有顯著(zhù)漏檢產(chǎn)生，主要集中于直線(xiàn)較短或彎折較為明顯的地方，即使檢測到的直線(xiàn)段，也存在端點(diǎn)定位不準的情況。SHT對于尺度較小的直線(xiàn)目標檢測性能較差，并且易受到直線(xiàn)彎折、短線(xiàn)噪聲等的影響。

　　圖4(c)隨機Hough變換的直線(xiàn)虛檢率略有上升，但漏檢率明顯低于標準Hough變換，原圖的每條線(xiàn)段目標都能被部分檢出;但線(xiàn)段的端點(diǎn)仍然不夠準確，而且存在同一線(xiàn)段目標被檢出為多條斷開(kāi)短線(xiàn)目標，這些問(wèn)題在右側平行線(xiàn)處尤其顯著(zhù)。這組結果表明，RHT雖然在漏檢性能上優(yōu)于SHT，但難以解決鄰近平行線(xiàn)目標和直線(xiàn)段目標過(guò)度分段問(wèn)題。

　　圖4(d)本文方法精確檢出原圖存在的每條直線(xiàn)，沒(méi)有出現虛檢漏檢的情況，并且每條直線(xiàn)段的端點(diǎn)定位準確，尤其在面對右側兩組平行線(xiàn)交叉這種復雜的情況時(shí)，仍然沒(méi)有出現SHT、RHT存在的漏檢、虛檢、過(guò)度分段等問(wèn)題，保持了優(yōu)異的檢測性能。

　　檢測結果的漏檢虛檢指標如表1所示。

　　繼續探究三種方法在不同噪聲條件下的檢測性能。仍然采用上述直線(xiàn)，但隨機添加不同數目的短線(xiàn)噪聲，依次得到圖5中兩種指標的變化曲線(xiàn)。從圖中可以看出，三種方法的檢測準確度大體上隨著(zhù)短線(xiàn)擾動(dòng)數目的增加而下降;對比已有兩種算法，SHT的抗虛檢性能較好而RHT的抗漏檢性能較好，并且兩種方法都隨噪聲變化出現較大波動(dòng);本文方法在漏檢、虛檢性能方面都是要優(yōu)于兩種已有算法的，并且其檢測性能并沒(méi)有隨噪聲的變化發(fā)生明顯波動(dòng)，有著(zhù)較好的穩定性和魯棒性。

　　圖片

　　圖5在不同短線(xiàn)噪聲影響下的檢測結果

　　四、結語(yǔ)

　　本文提出通過(guò)參數域的最小二乘修正來(lái)改進(jìn)隨機Hough變換直線(xiàn)檢測：直接在參數空間引入最小二乘擬合方法，并對隨機Hough變換的投票步驟提出改進(jìn)，最后在提取長(cháng)直線(xiàn)的基礎上引入斷裂尺度閾值確定線(xiàn)段端點(diǎn)。

　　仿真圖像的直線(xiàn)提取實(shí)驗可以證明，本文提出的基于最小二乘估計修正改進(jìn)的隨機Hough算法可以有效地改進(jìn)標準Hough變換以及隨機Hough變換的固有缺陷。經(jīng)過(guò)有效性篩選和最小二乘擬合之后的累加效率更高，噪聲像素和鄰近直線(xiàn)像素的干擾更小，虛檢率和漏檢率顯著(zhù)降低;同時(shí)，對直線(xiàn)形變的寬容度更好，直線(xiàn)端點(diǎn)的定位性能更加優(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. (董晶， 楊夏， 于起峰. 基于邊緣連接的快速直線(xiàn)段檢測算法[J]. 光學(xué)學(xué)報， 2013， 33(3)：213-220.)

【基于最小二乘修正的隨機Hough變換直線(xiàn)檢測】相關(guān)文章：

基于HOUGH變換的雷達圖像圓檢測03-07

基于最小二乘模型的Bayes參數辨識方法03-07

基于小波變換的諧波檢測法03-28

基于FPGA的快速傅立葉變換03-19

一種基于分數階傅立葉變換的LFM信號檢測簡(jiǎn)化方法11-22

基于自相關(guān)平方函數與小波變換結合的帶噪語(yǔ)音基音檢測03-07

基于最小因子定律的時(shí)間營(yíng)銷(xiāo)法03-24

基于IHS變換的遙感影像融合方法研究11-22

一種基于小波變換的二級簽名認證方法03-07