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

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

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