基于霍夫變換的二值邊緣圖擬合直線的研究

基于霍夫變換的二值邊緣圖擬合直線的研究

1擬合直線擬合在項(xiàng)目中，通常需要線性調(diào)整，如實(shí)驗(yàn)數(shù)據(jù)分析、統(tǒng)計(jì)數(shù)據(jù)分析、數(shù)據(jù)處理中的二值邊緣方案，合成連續(xù)的直線，并在3d系統(tǒng)中獲得三維物體圖像的方案。直線擬合在計(jì)算數(shù)學(xué)中有多種方法,最常用的是平方逼近,即最小二乘法。最小二乘法的定義是∑i=1N[yi?φ(xi)]2=min∑i=1Ν[yi-φ(xi)]2=min(1)其中(xi,yi)為已知數(shù)據(jù)點(diǎn);φ(x)為擬合函數(shù),直線擬合時(shí)為一次多項(xiàng)式。顯然,最小二乘法考慮的是已知數(shù)據(jù)點(diǎn)到擬合函數(shù)(直線擬合時(shí)為直線)的距離平方和為最小。這里存在兩個(gè)問題,一是已知數(shù)據(jù)點(diǎn)集中若存在干擾點(diǎn)或噪聲時(shí),擬合函數(shù)并不通過最多的數(shù)據(jù)點(diǎn),擬合誤差較大;二是已知數(shù)據(jù)點(diǎn)集趨向于分布在多條直線附近時(shí),需事先對已知數(shù)據(jù)進(jìn)行分離預(yù)處理,否則擬合結(jié)果沒有意義。對數(shù)據(jù)點(diǎn)集進(jìn)行分離預(yù)處理是一項(xiàng)既難又費(fèi)時(shí)的工作,有時(shí)甚至不可能。霍夫變換(HoughTransform)是模式識(shí)別領(lǐng)域中對二值圖像進(jìn)行直線檢測的有效方法,它檢測已知點(diǎn)的共線性,是一種全局性的檢測方法。當(dāng)已知數(shù)據(jù)點(diǎn)集中存在干擾點(diǎn)和噪聲時(shí),它可以很好地抑制干擾和噪聲,同時(shí)它還可以將已知數(shù)據(jù)點(diǎn)集擬合成多條直線。但是,霍夫變換的精度卻不容易控制,當(dāng)實(shí)際問題對擬合直線的精度要求較高時(shí),則不能用霍夫變換。霍夫變換的輸出是共線點(diǎn)直線方程的參數(shù),當(dāng)需要得到線段時(shí),還需進(jìn)一步處理。本文將霍夫變換與最小二乘法相結(jié)合,研究對實(shí)驗(yàn)數(shù)據(jù)和圖像處理中的邊緣圖進(jìn)行直線擬合的方法。首先,用霍夫變換剔除數(shù)據(jù)點(diǎn)集中的干擾點(diǎn)和噪聲,并將分布在不同直線附近的點(diǎn)分離出來;然后,用最小二乘法擬合各直線。該方法既解決了直接使用最小二乘法擬合直線時(shí)存在的兩個(gè)問題;同時(shí)也解決了直接使用霍夫變換時(shí),擬合直線精度不高和直線段有效區(qū)間不容易控制的問題。2霍夫變換原理和實(shí)現(xiàn)方法2.1直線檢測的化方式1962年,P.V.C.Hough根據(jù)數(shù)學(xué)對偶性原理提出了檢測圖像直線的方法,此后,該方法被不斷地研究和發(fā)展,主要應(yīng)用于模式識(shí)別領(lǐng)域中對二值圖像進(jìn)行直線檢測。其原理如圖1所示,在標(biāo)準(zhǔn)參數(shù)化方式下,平面直角坐標(biāo)系中的直線l表達(dá)為ρ=xcos?+ysin?,ρ≥0,0≤?<2π(2)其中,ρ為l相對于原點(diǎn)的距離,?為ρ與x軸的夾角。根據(jù)式(2),直線l上不同的點(diǎn)在參數(shù)空間中被變換為一族相交于p點(diǎn)的正弦曲線。顯然,若能確定參數(shù)空間中的p點(diǎn)(局部最大值),就實(shí)現(xiàn)了直線檢測。由上述霍夫變換原理可知,霍夫變換具有如下性質(zhì):(1)直角坐標(biāo)系中的一個(gè)點(diǎn)映射到參數(shù)空間中為一條曲線;(2)參數(shù)空間中的一個(gè)點(diǎn)對應(yīng)直角坐標(biāo)系中的一條直線;(3)直角坐標(biāo)系中的共點(diǎn)線映射到參數(shù)空間中為一條曲線;(4)直角坐標(biāo)系中的共線點(diǎn)映射到參數(shù)空間中后為一個(gè)交于同一點(diǎn)的曲線族。2.2霍夫變換m工程中的實(shí)驗(yàn)數(shù)據(jù)和圖像處理中的二值邊緣圖,通常都是離散數(shù)據(jù),因此,根據(jù)霍夫變換性質(zhì),可按下列步驟實(shí)現(xiàn)霍夫變換。(1)將參數(shù)空間量化成m×n(m為?的等份數(shù),n為ρ的等份數(shù))個(gè)單元,并設(shè)置累加器矩陣Qm×n;(2)給參數(shù)空間中的每個(gè)單元分配一個(gè)累加器Q(i,j),并把累加器的初始值置為零;(3)取出直角坐標(biāo)系中的點(diǎn)(xi,yi)(i=1,2,3…s,s為直角坐標(biāo)系中的已知點(diǎn)數(shù))代入式(2),并以量化后的?值計(jì)算出ρ;(4)在參數(shù)空間中,找到?和ρ所對應(yīng)的單元,并將該單元的累加器加1,即Q(i,j)=Q(i,j)+1;(5)當(dāng)直角坐標(biāo)系中的點(diǎn)都經(jīng)過(3)、(4)兩步遍歷后,檢驗(yàn)參數(shù)空間中每個(gè)累加器的值,累加器值最大的單元所對應(yīng)的?和ρ即為直角坐標(biāo)系中直線方程式(2)的參數(shù)。由上述霍夫變換過程可知,如果參數(shù)空間中的?和ρ量化過粗,則參數(shù)空間中的凝聚效果較差,找不出直線的準(zhǔn)確參數(shù)?和ρ;反之,?和ρ量化過細(xì),那么計(jì)算量將增大。另外,當(dāng)直角坐標(biāo)系中的點(diǎn)分布在R條直線附近時(shí),可在第5步檢測累加器時(shí),取出累加器中前R個(gè)值最大的單元所對應(yīng)的?k和ρk(k=1,2,…,R),以?k和ρk(k=1,2,…,R)為直角坐標(biāo)系中直線方程式(2)的參數(shù),即可同時(shí)實(shí)現(xiàn)多條直線的擬合。3擬合直線的參數(shù)假設(shè)采集到的數(shù)據(jù)集為M=(xi,yi)T,(i=1,2,…,s,s為數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)數(shù)),M中的數(shù)據(jù)點(diǎn)分布在R條直線附近,根據(jù)實(shí)驗(yàn)?zāi)康囊蠼o定誤差閾值為dk。(1)霍夫變換。將式(2)改寫成ρk=xicos?k+yisin?k(k=1,2,…,s;k=1,2,…,R)(3)根據(jù)式(3),對M作霍夫變換,可得擬合直線的參數(shù)(?k,ρk)。(2)找出擬合直線(?k,ρk)附近的點(diǎn)集M*k。將式(3)表示的法線式直線方程改寫成斜截式y(tǒng)i=akxi+bk(4)其中ak=?cos?ksin?k,bk=?ρksin?kak=-cos?ksin?k,bk=-ρksin?k計(jì)算M中的點(diǎn)到由式(4)確定的直線的距離dki=|akxi+bk?yi|1+a2k√,(xi,yi)∈M,(i,=1,2,?,s,k=1,2,?,R)dki=|akxi+bk-yi|1+ak2,(xi,yi)∈Μ,(i,=1,2,?,s,k=1,2,?,R)(5)如果dki<dk(6)則(xi,yi)?M*k(xkj,ykj),(j=1,2,…s*,s*≤s)(7)M*k為符合誤差閾值要求的第k條霍夫變換直線附近的點(diǎn)集。(3)以點(diǎn)集M*k為擬合數(shù)據(jù),分別擬合各直線,可得直線方程式(4)的參數(shù)(a*k,b*k。以((xkj)min,ykj)∈M*k和((xkj)max,ykj)∈M*k為端點(diǎn),可確定各直線段的區(qū)間,即ykj=a*kxkj+b*k,(xkj)min≤xkj≤(xkj)max(8)4實(shí)驗(yàn)4.1霍夫變換擬合直線已知某實(shí)驗(yàn)中得到的實(shí)驗(yàn)數(shù)據(jù)如表1所示。(1)首先對數(shù)據(jù)進(jìn)行預(yù)處理,檢查它們是否分布于一條直線附近。如圖2(a)所示,實(shí)驗(yàn)數(shù)據(jù)分布在一條直線附近。(2)將實(shí)驗(yàn)數(shù)據(jù)直接作最小二乘法擬合,得直線的斜率a直=0.6142,截距b直=13.8112,擬合結(jié)果如圖2(b)所示。(3)將實(shí)驗(yàn)數(shù)據(jù)作霍夫變換?；舴蜃儞Q時(shí),參數(shù)空間的量化值為:0≤?<360,0≤ρ<1000,形成360×1000個(gè)單元,累加器最大值為11,輸出參數(shù)為?=120°,ρ=13。將直線方程式(2)寫成斜截式,代入?=120°,ρ=13,得直線的斜率a霍=0.5774,截距b霍=15.0111。擬合結(jié)果如圖2(c)所示。(4)利用第3步霍夫變換結(jié)果,設(shè)誤差閾值d=5,剔除干擾點(diǎn)2后,用最小二乘法擬合,得直線的斜率a=0.5650,截距b=15.4886。擬合結(jié)果如圖2(d)所示。霍夫變換擬合的直線與最小二乘法擬合的直線斜率和截距不同,這是因?yàn)?霍夫變換考慮的是擬合直線通過最多的數(shù)據(jù)點(diǎn),而最小二乘法考慮的是所有數(shù)據(jù)點(diǎn)距離擬合直線的平方和最小。顯然,當(dāng)數(shù)據(jù)集中存在干擾點(diǎn)或噪聲時(shí),直接采用最小二乘法擬合,其擬合結(jié)果誤差較大。此時(shí),應(yīng)先采用霍夫變換剔除干擾點(diǎn)或噪聲,然后采用最小二乘法擬合。若實(shí)驗(yàn)結(jié)果需要擬合的直線通過最多數(shù)據(jù)點(diǎn)時(shí),可采用霍夫變換進(jìn)行直線擬合。3.2直線擬合的數(shù)值結(jié)果已知某次實(shí)驗(yàn)所得數(shù)據(jù)如表2所示。當(dāng)對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行預(yù)處理后,發(fā)現(xiàn)其分布在兩條直線附近,如圖3(a)所示。根據(jù)實(shí)驗(yàn)?zāi)康牡囊?采用兩種直線擬合方法。(1)直接采用霍夫變換進(jìn)行直線擬合?；舴蜃儞Q時(shí),參數(shù)空間的量化值為:0≤?<360,0≤ρ<1000,形成360×1000個(gè)單元,累加器最大值分別為13和12。L1的擬合參數(shù)?1=60°,ρ1=63.7,L2的擬合參數(shù)?2=125°,ρ2=2.5擬合結(jié)果如圖3(b)所示。(2)首先采用霍夫變換找出分布在擬合直線附近的點(diǎn),然后采用最小二乘法擬合。在尋找擬合直線附近的點(diǎn)時(shí),取誤差閾值d=6。圖3(c)為L2的擬合結(jié)果,圖3(d)為L1的擬合結(jié)果。4.3維生物圖像中的部分照片生成在模式識(shí)別、計(jì)算機(jī)視覺和CAD系統(tǒng)中,經(jīng)常需要獲得三維物體圖像的線圖,以便后續(xù)處理。圖4所示是L型多面體的綜合圖像及其各棱線的編號(hào),圖像大小為360×400像素。(1)圖像預(yù)處理加入1%的模擬噪聲后,采用圖5所示的3×3模板算子,得到如圖6(a)所示的二值邊緣圖。(2)參數(shù)空間的量化值為:0≤?<360,0≤ρ<800。檢測到的棱線結(jié)果如圖6(b)所示,各棱線的參數(shù)如表3所示,其中?和ρ為棱線的法線式參數(shù),a和b為棱線的斜截式參數(shù)。(3)通過霍夫變換來確定閉合線周圍的點(diǎn)根據(jù)式(5),取誤差閾值dk=4(像素),檢測到的棱線周圍點(diǎn)如圖6(c)所示。(4)最小二乘法調(diào)整根據(jù)第3步檢測到的棱線周圍點(diǎn),采用最小二乘法擬合。擬合結(jié)