基于Hough變換的三次方Bezier曲線檢測算法研究

孫文赟， 韓 斌

（江蘇科技大學(xué)電氣與信息工程學(xué)院，江蘇 張家港 215600）

經(jīng)典Hough變換[1]常用于直線（段）、圓（?。?、橢圓和拋物線的檢測，Ballard[2]提出的廣義Hough變換(Generalized Hough Transform，簡稱GHT)可用于檢測任意形狀，隨后出現(xiàn)了大量對GHT的改進(jìn)，文獻(xiàn)[3-4]使用對偶點方法降低GHT的復(fù)雜度，文獻(xiàn)[5]使用模糊推論系統(tǒng)提高GHT的精確度。在應(yīng)用方面，文獻(xiàn)[6]提出一種改進(jìn)型廣義 Hough變換并用于茄子果實位姿識別。

Bezier曲線于1962年由Pierre Bezier發(fā)現(xiàn)并用于汽車設(shè)計，是目前計算機(jī)圖形學(xué)中相當(dāng)重要的參數(shù)曲線，也應(yīng)用于工程圖紙和測量曲線的矢量化等領(lǐng)域[7-8]。

在GHT的基礎(chǔ)上，本文針對Bezier曲線的特點，提出了一種使用 Hough變換的三次方Bezier曲線檢測算法。只需給出待檢測三次方Bezier曲線的大致繪制圖案，算法根據(jù)所給出的待檢圖形的數(shù)字圖像建立曲線模型，然后在復(fù)雜圖像中檢測該形狀曲線出現(xiàn)的位置、大小和方向。算法由待檢圖形建模和曲線檢測兩個部分組成。

1 待檢曲線建模

1.1 點陣圖像的矢量化

所需檢測曲線圖像是像素點陣圖，需將其矢量化以便用于檢測，目前已經(jīng)有一些關(guān)于點陣圖矢量化的研究成果[9]，并投入應(yīng)用領(lǐng)域。這些算法大多使用最小二乘法擬合曲線，其中，文獻(xiàn)[9]提出的算法具有代表性。該算法首先提取模板圖像的骨架并使用八方向鏈碼的方法追蹤曲線，得到規(guī)格點序列 {Qi|i= 0,1,2…n-1}。使用最小二乘 法 對{Qi}擬合使Qi=(Xi,Yi)的 均 方 誤 差 最 小 ， 求 出d0,d1,d2,d3。最終三次方Bezier曲線的4個控制點由公式計算得到。

1.2 待檢曲線的規(guī)格化

本文將待檢Bezier曲線規(guī)格化，以使得其具有平移、縮放和旋轉(zhuǎn)不變特征。

圖1 二次方Bezier曲線

定義1 將二次方Bezier曲線經(jīng)過平移、旋轉(zhuǎn)、縮放，使首尾的兩個控制點為(0,0)和(0,1)，中間控制點(a,b)即反映了原曲線的形狀特征，稱此變換為Bezier曲線的規(guī)格化。

二次方 Bezier曲線的規(guī)格化及其逆變換的計算方法為

其中：R()、S()、T()為標(biāo)準(zhǔn)旋轉(zhuǎn)縮放、平移變換

二次方Bezier曲線的形狀特征

三次方的情況類似，使用首末兩個控制點確定變換的形式，第2、第3兩個控制點經(jīng)變換得到(a,b)、(c,d)表示圓曲線的形狀特征。

2 曲線檢測

2.1 R函數(shù)

圖1(b)所示的規(guī)格化Bezier曲線，邊緣點到參考點的距離|r|與邊緣點到參考點連線交切線的夾角φ有確定關(guān)系

式(6)即R函數(shù)。R函數(shù)不受平移、縮放、旋轉(zhuǎn)影響，僅由形狀決定，是曲線特征的另一種表示方式，使用R函數(shù)可以方便地確定參考點，且比原本曲線特征參數(shù)表示簡便、規(guī)范。所以，我們需先將待檢測的圖形轉(zhuǎn)換成R函數(shù)表示。

規(guī)格化三次方Bezier曲線對應(yīng)的R函數(shù)的計算方法及其推導(dǎo)過程如下：

三次方Bezier曲線的參數(shù)方程為

整理得關(guān)于t的三次多項式

整理得關(guān)于t的四次方程

此即為式(6)所對應(yīng)的R函數(shù)。

2.2 使用R函數(shù)的Hough變換

與所有Hough變換算法類似，本文算法的主要思想是先投票再統(tǒng)計：使用一個三維累加器數(shù)組A，對于每個邊緣點嘗試各種s和φ，通過R函數(shù)求得參考點可能的位置，對其投票，所有投票結(jié)束后統(tǒng)計最大值，最大值所在位置即(x0,y0)、s。投票部分的偽代碼為：

上述偽代碼中：

①處S為曲線大小s的最大值，從規(guī)格化曲線的定義可知，曲線的大小為其在圖像中初始點和終止點的距離，所以s≤S≤圖像對角線長度。

②處使用±是無法避免的，這是因為邊緣方向有二義性，可以理解為一對相差π的角度，從而導(dǎo)致推測的參考點不唯一。

③處使用模糊模板進(jìn)行投票，以克服輸入圖像噪聲干擾和輸入方向不精確的問題[5]。templateN×N(i,j)為寬度為N的正方形模板，理想的模板是二維高斯函數(shù)

當(dāng)s變化時，投票點靠近／遠(yuǎn)離邊緣點，投票點的誤差隨之變?。兇螅{(diào)整窗口的大小，以適應(yīng)不同情況，窗口的大小可按下式計算

其中，θe是允許的誤差夾角，較小時可取tan(θe)≈θe，常數(shù)E為曲線位置可能存在的絕對誤差，表示向上取奇數(shù)操作。

④處使用一個關(guān)于s的增函數(shù)w(s)作為投票權(quán)值調(diào)節(jié)因子，解決當(dāng)s較小時投票的集中程度大，影響判斷的問題，經(jīng)多次實驗調(diào)整，取w(s)=s0.7625合適。

③、④兩處可先用A[s][x0][y0]++替代，待投票完成后對累加器A中各層進(jìn)行平滑濾波并調(diào)節(jié)權(quán)值，從而避免大量浮點數(shù)累加，降低算法復(fù)雜度，且結(jié)果不變。

Hough投票的時間、空間復(fù)雜度分別為

其中，W、H為長寬，N為邊緣點數(shù)量，S為曲線大小s的最大值，Φ為角度分割數(shù)量。這也是整個算法的時間、空間復(fù)雜度。

Hough變換利用曲線邊緣方向忽視其自身旋轉(zhuǎn)，降低Hough空間的維數(shù)，達(dá)到減少存儲空間并降低計算量的目的，但帶來的曲線方向無法直接求出其副作用。

2.3 計算曲線方向

在已知曲線特征、位置和大小的基礎(chǔ)上，使用模糊匹配法求其方向。使用一個一維累加器數(shù)組B，對已知(x0,y0)、s的Bezier曲線嘗試不同的旋轉(zhuǎn)角度，“繪制”空間域上假設(shè)曲線，使用一個中心元素最大、外圍元素較小的窗口在假設(shè)曲線上滑動，與實際曲線進(jìn)行模糊比較，并根據(jù)吻合程度對當(dāng)前角度投票，所有投票結(jié)束后統(tǒng)計最大值，其位置即θ。

關(guān)于θ的投票數(shù)是所有在對應(yīng)假設(shè)曲線上的滑動窗口的吻合程度總和，即

窗口模板的取值方法與前文相同。當(dāng)窗口靠近或遠(yuǎn)離參考點(x0,y0)時，調(diào)整窗口的大小N，使得所有窗口可以恰好覆蓋實際曲線可能存在的圓形區(qū)域，窗口的寬度的取值為

其中，(xwc,ywc)是窗口的中心位置，常數(shù)Δθ為角度變化的步長，較小時可取 tan(Δθ)≈ Δθ。

3 實驗結(jié)果與分析

本文選用尺寸為800×600的機(jī)械制圖掃描圖像進(jìn)行三次方Bezier曲線檢測算法的實驗，編寫程序?qū)ζ溥M(jìn)行若干步驟的處理，得到了正確結(jié)果。

實驗步驟的數(shù)據(jù)流程圖如圖2所示，首先提取掃描圖像的邊緣并裁剪某個曲線部分，提取曲線特征得到各種參數(shù)，根據(jù)形狀參數(shù)使用此算法在圖中找出曲線的位置、大小和角度。結(jié)果表明，算法的誤差在允許的范圍內(nèi)。

使用GHT方法，建立大小為100的離散R表代替連續(xù)的R函數(shù)，其它保持不變，得到另一組結(jié)果，對比表1中兩種方法，本文改進(jìn)方法的精確度優(yōu)于GHT方法。

圖2 實驗步驟的數(shù)據(jù)流程圖

表1 實驗結(jié)果數(shù)據(jù)

4 結(jié) 論

廣義Hough變換[2]中使用到的R表與本文的R函數(shù)類似，區(qū)別在于：（1）R表使用采樣的方法記錄離散、有限的邊緣點到參考點的關(guān)系；（2）R表存儲的是r向量，本文R函數(shù)僅返回其模值。和廣義 Hough變換相比，本文算法對特征的描述更加精確，廣義 Hough變換方法可以檢測包括Bezier曲線在內(nèi)的任意形狀，但當(dāng)邊緣像素和參考點的距離較遠(yuǎn)時，臨近邊緣像素的φ近似，查表法將會得到相同的r，最終導(dǎo)致對參考點的投票分散，而本文使用比R表精確的R函數(shù)方法不會出現(xiàn)這類問題。

[1]Hough P V C. Method and means for recognizing complex patterns: U S, 3069654 [P]. 1962-12-18.

[2]Ballard D H. Generalizing the hough transform to detect arbitrary shapes [J]. Pattern Recognition, 1982,13: 111-122.

[3]Ser P K, Siu W C. Non-analytic object recognition using the hough transform with the matching technique [J]. Computers and Digital Techniques, 1994,141(1): 11-16.

[4]劉宏申, 程 健, 高尚義. 對偶點廣義 Hough變換算法的改進(jìn)[J]. 計算機(jī)工程與設(shè)計, 2009, 30(2):423-425.

[5]Izadinia H, Sadeghi F, Ebadzadeh M M. Fuzzy generalized hough transform invariant to rotation and scale in noisy environment [C]//Proceedings of the 18th International Conference on Fuzzy Systems.Piscataway NJ, USA: IEEE Press, 2009: 153-158.

[6]姚立健, 丁為民, 張培培, 等. 基于改進(jìn)型廣義Hough 變換的茄子果實位姿識別方法[J]. 農(nóng)業(yè)工程學(xué)報, 2009, 25(12): 128-132.

[7]Yuan Huaqiang, Ye Yangdong, Deng Jianguang, et al.A fingerprint feature extraction algorithm based on curvature of Bezier curve [J]. Progress in Natural Science, 2007, 17(11): 1376-1381.

[8]殷明霞, 劉群輝, 桂幸民. 利用Bezier樣條曲線進(jìn)行葉輪機(jī)可視化設(shè)計[J]. 航空動力學(xué)報, 2006, 21(1):156-160.

[9]余學(xué)軍, 彭立中. 二值圖像曲線輪廓提取的新算法[J].中國圖象圖形學(xué)報, 2002, 7A(3): 272-275.